1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* 3 * Copyright (C) 2012-2013 Samsung Electronics Co., Ltd. 4 */ 5 6 #include <linux/blkdev.h> 7 #include <linux/slab.h> 8 #include <linux/bitmap.h> 9 #include <linux/buffer_head.h> 10 #include <linux/backing-dev.h> 11 12 #include "exfat_raw.h" 13 #include "exfat_fs.h" 14 15 #if BITS_PER_LONG == 32 16 #define __le_long __le32 17 #define lel_to_cpu(A) le32_to_cpu(A) 18 #define cpu_to_lel(A) cpu_to_le32(A) 19 #elif BITS_PER_LONG == 64 20 #define __le_long __le64 21 #define lel_to_cpu(A) le64_to_cpu(A) 22 #define cpu_to_lel(A) cpu_to_le64(A) 23 #else 24 #error "BITS_PER_LONG not 32 or 64" 25 #endif 26 27 /* 28 * Allocation Bitmap Management Functions 29 */ 30 static bool exfat_test_bitmap_range(struct super_block *sb, unsigned int clu, 31 unsigned int count) 32 { 33 struct exfat_sb_info *sbi = EXFAT_SB(sb); 34 unsigned int start = clu; 35 unsigned int end = clu + count; 36 unsigned int ent_idx, i, b; 37 unsigned int bit_offset, bits_to_check; 38 __le_long *bitmap_le; 39 unsigned long mask, word; 40 41 if (!is_valid_cluster(sbi, start) || !is_valid_cluster(sbi, end - 1)) 42 return false; 43 44 while (start < end) { 45 ent_idx = CLUSTER_TO_BITMAP_ENT(start); 46 i = BITMAP_OFFSET_SECTOR_INDEX(sb, ent_idx); 47 b = BITMAP_OFFSET_BIT_IN_SECTOR(sb, ent_idx); 48 49 bitmap_le = (__le_long *)sbi->vol_amap[i]->b_data; 50 51 /* Calculate how many bits we can check in the current word */ 52 bit_offset = b % BITS_PER_LONG; 53 bits_to_check = min(end - start, 54 (unsigned int)(BITS_PER_LONG - bit_offset)); 55 56 /* Create a bitmask for the range of bits to check */ 57 if (bits_to_check >= BITS_PER_LONG) 58 mask = ~0UL; 59 else 60 mask = ((1UL << bits_to_check) - 1) << bit_offset; 61 word = lel_to_cpu(bitmap_le[b / BITS_PER_LONG]); 62 63 /* Check if all bits in the mask are set */ 64 if ((word & mask) != mask) 65 return false; 66 67 start += bits_to_check; 68 } 69 70 return true; 71 } 72 73 static int exfat_allocate_bitmap(struct super_block *sb, 74 struct exfat_dentry *ep) 75 { 76 struct exfat_sb_info *sbi = EXFAT_SB(sb); 77 struct blk_plug plug; 78 long long map_size; 79 unsigned int i, j, need_map_size; 80 sector_t sector; 81 unsigned int max_ra_count; 82 83 sbi->map_clu = le32_to_cpu(ep->dentry.bitmap.start_clu); 84 map_size = le64_to_cpu(ep->dentry.bitmap.size); 85 need_map_size = ((EXFAT_DATA_CLUSTER_COUNT(sbi) - 1) / BITS_PER_BYTE) 86 + 1; 87 if (need_map_size != map_size) { 88 exfat_err(sb, "bogus allocation bitmap size(need : %u, cur : %lld)", 89 need_map_size, map_size); 90 /* 91 * Only allowed when bogus allocation 92 * bitmap size is large 93 */ 94 if (need_map_size > map_size) 95 return -EIO; 96 } 97 sbi->map_sectors = ((need_map_size - 1) >> 98 (sb->s_blocksize_bits)) + 1; 99 sbi->vol_amap = kvmalloc_objs(struct buffer_head *, sbi->map_sectors); 100 if (!sbi->vol_amap) 101 return -ENOMEM; 102 103 sector = exfat_cluster_to_sector(sbi, sbi->map_clu); 104 max_ra_count = min(sb->s_bdi->ra_pages, sb->s_bdi->io_pages) << 105 (PAGE_SHIFT - sb->s_blocksize_bits); 106 for (i = 0; i < sbi->map_sectors; i++) { 107 /* Trigger the next readahead in advance. */ 108 if (max_ra_count && 0 == (i % max_ra_count)) { 109 blk_start_plug(&plug); 110 for (j = i; j < min(max_ra_count, sbi->map_sectors - i) + i; j++) 111 sb_breadahead(sb, sector + j); 112 blk_finish_plug(&plug); 113 } 114 115 sbi->vol_amap[i] = sb_bread(sb, sector + i); 116 if (!sbi->vol_amap[i]) 117 goto err_out; 118 } 119 120 if (exfat_test_bitmap_range(sb, sbi->map_clu, 121 EXFAT_B_TO_CLU_ROUND_UP(map_size, sbi)) == false) 122 goto err_out; 123 124 return 0; 125 126 err_out: 127 j = 0; 128 /* release all buffers and free vol_amap */ 129 while (j < i) 130 brelse(sbi->vol_amap[j++]); 131 132 kvfree(sbi->vol_amap); 133 sbi->vol_amap = NULL; 134 return -EIO; 135 } 136 137 int exfat_load_bitmap(struct super_block *sb) 138 { 139 unsigned int i, type; 140 struct exfat_chain clu; 141 struct exfat_sb_info *sbi = EXFAT_SB(sb); 142 143 exfat_chain_set(&clu, sbi->root_dir, 0, ALLOC_FAT_CHAIN); 144 while (clu.dir != EXFAT_EOF_CLUSTER) { 145 for (i = 0; i < sbi->dentries_per_clu; i++) { 146 struct exfat_dentry *ep; 147 struct buffer_head *bh; 148 149 ep = exfat_get_dentry(sb, &clu, i, &bh); 150 if (!ep) 151 return -EIO; 152 153 type = exfat_get_entry_type(ep); 154 if (type == TYPE_BITMAP && 155 ep->dentry.bitmap.flags == 0x0) { 156 int err; 157 158 err = exfat_allocate_bitmap(sb, ep); 159 brelse(bh); 160 return err; 161 } 162 brelse(bh); 163 164 if (type == TYPE_UNUSED) 165 return -EINVAL; 166 } 167 168 if (exfat_get_next_cluster(sb, &clu.dir)) 169 return -EIO; 170 } 171 172 return -EINVAL; 173 } 174 175 void exfat_free_bitmap(struct exfat_sb_info *sbi) 176 { 177 int i; 178 179 for (i = 0; i < sbi->map_sectors; i++) 180 __brelse(sbi->vol_amap[i]); 181 182 kvfree(sbi->vol_amap); 183 } 184 185 int exfat_set_bitmap(struct super_block *sb, unsigned int clu, bool sync) 186 { 187 int i, b; 188 unsigned int ent_idx; 189 struct exfat_sb_info *sbi = EXFAT_SB(sb); 190 191 if (!is_valid_cluster(sbi, clu)) 192 return -EINVAL; 193 194 ent_idx = CLUSTER_TO_BITMAP_ENT(clu); 195 i = BITMAP_OFFSET_SECTOR_INDEX(sb, ent_idx); 196 b = BITMAP_OFFSET_BIT_IN_SECTOR(sb, ent_idx); 197 198 set_bit_le(b, sbi->vol_amap[i]->b_data); 199 exfat_update_bh(sbi->vol_amap[i], sync); 200 return 0; 201 } 202 203 int exfat_clear_bitmap(struct super_block *sb, unsigned int clu, bool sync) 204 { 205 int i, b; 206 unsigned int ent_idx; 207 struct exfat_sb_info *sbi = EXFAT_SB(sb); 208 209 if (!is_valid_cluster(sbi, clu)) 210 return -EIO; 211 212 ent_idx = CLUSTER_TO_BITMAP_ENT(clu); 213 i = BITMAP_OFFSET_SECTOR_INDEX(sb, ent_idx); 214 b = BITMAP_OFFSET_BIT_IN_SECTOR(sb, ent_idx); 215 216 if (!test_bit_le(b, sbi->vol_amap[i]->b_data)) 217 return -EIO; 218 219 clear_bit_le(b, sbi->vol_amap[i]->b_data); 220 221 exfat_update_bh(sbi->vol_amap[i], sync); 222 223 return 0; 224 } 225 226 bool exfat_test_bitmap(struct super_block *sb, unsigned int clu) 227 { 228 int i, b; 229 unsigned int ent_idx; 230 struct exfat_sb_info *sbi = EXFAT_SB(sb); 231 232 if (!sbi->vol_amap) 233 return true; 234 235 if (!is_valid_cluster(sbi, clu)) 236 return false; 237 238 ent_idx = CLUSTER_TO_BITMAP_ENT(clu); 239 i = BITMAP_OFFSET_SECTOR_INDEX(sb, ent_idx); 240 b = BITMAP_OFFSET_BIT_IN_SECTOR(sb, ent_idx); 241 242 if (!test_bit_le(b, sbi->vol_amap[i]->b_data)) 243 return false; 244 245 return true; 246 } 247 248 /* 249 * If the value of "clu" is 0, it means cluster 2 which is the first cluster of 250 * the cluster heap. 251 */ 252 unsigned int exfat_find_free_bitmap(struct super_block *sb, unsigned int clu) 253 { 254 unsigned int i, map_i, map_b, ent_idx; 255 unsigned int clu_base, clu_free; 256 unsigned long clu_bits, clu_mask; 257 struct exfat_sb_info *sbi = EXFAT_SB(sb); 258 __le_long bitval; 259 260 WARN_ON(clu < EXFAT_FIRST_CLUSTER); 261 ent_idx = ALIGN_DOWN(CLUSTER_TO_BITMAP_ENT(clu), BITS_PER_LONG); 262 clu_base = BITMAP_ENT_TO_CLUSTER(ent_idx); 263 clu_mask = IGNORED_BITS_REMAINED(clu, clu_base); 264 265 map_i = BITMAP_OFFSET_SECTOR_INDEX(sb, ent_idx); 266 map_b = BITMAP_OFFSET_BYTE_IN_SECTOR(sb, ent_idx); 267 268 for (i = EXFAT_FIRST_CLUSTER; i < sbi->num_clusters; 269 i += BITS_PER_LONG) { 270 bitval = *(__le_long *)(sbi->vol_amap[map_i]->b_data + map_b); 271 if (clu_mask > 0) { 272 bitval |= cpu_to_lel(clu_mask); 273 clu_mask = 0; 274 } 275 if (lel_to_cpu(bitval) != ULONG_MAX) { 276 clu_bits = lel_to_cpu(bitval); 277 clu_free = clu_base + ffz(clu_bits); 278 if (clu_free < sbi->num_clusters) 279 return clu_free; 280 } 281 clu_base += BITS_PER_LONG; 282 map_b += sizeof(long); 283 284 if (map_b >= sb->s_blocksize || 285 clu_base >= sbi->num_clusters) { 286 if (++map_i >= sbi->map_sectors) { 287 clu_base = EXFAT_FIRST_CLUSTER; 288 map_i = 0; 289 } 290 map_b = 0; 291 } 292 } 293 294 return EXFAT_EOF_CLUSTER; 295 } 296 297 int exfat_count_used_clusters(struct super_block *sb, unsigned int *ret_count) 298 { 299 struct exfat_sb_info *sbi = EXFAT_SB(sb); 300 unsigned int count = 0; 301 unsigned int i, map_i = 0, map_b = 0; 302 unsigned int total_clus = EXFAT_DATA_CLUSTER_COUNT(sbi); 303 unsigned int last_mask = total_clus & (BITS_PER_LONG - 1); 304 unsigned long *bitmap, clu_bits; 305 306 total_clus &= ~last_mask; 307 for (i = 0; i < total_clus; i += BITS_PER_LONG) { 308 bitmap = (void *)(sbi->vol_amap[map_i]->b_data + map_b); 309 count += hweight_long(*bitmap); 310 map_b += sizeof(long); 311 if (map_b >= (unsigned int)sb->s_blocksize) { 312 map_i++; 313 map_b = 0; 314 } 315 } 316 317 if (last_mask) { 318 bitmap = (void *)(sbi->vol_amap[map_i]->b_data + map_b); 319 clu_bits = lel_to_cpu(*(__le_long *)bitmap); 320 count += hweight_long(clu_bits & BITMAP_LAST_WORD_MASK(last_mask)); 321 } 322 323 *ret_count = count; 324 return 0; 325 } 326 327 int exfat_trim_fs(struct inode *inode, struct fstrim_range *range) 328 { 329 unsigned int trim_begin, trim_end, count, next_free_clu; 330 u64 clu_start, clu_end, trim_minlen, trimmed_total = 0; 331 struct super_block *sb = inode->i_sb; 332 struct exfat_sb_info *sbi = EXFAT_SB(sb); 333 int err = 0; 334 335 clu_start = max_t(u64, range->start >> sbi->cluster_size_bits, 336 EXFAT_FIRST_CLUSTER); 337 clu_end = clu_start + (range->len >> sbi->cluster_size_bits) - 1; 338 trim_minlen = range->minlen >> sbi->cluster_size_bits; 339 340 if (clu_start >= sbi->num_clusters || range->len < sbi->cluster_size) 341 return -EINVAL; 342 343 if (clu_end >= sbi->num_clusters) 344 clu_end = sbi->num_clusters - 1; 345 346 mutex_lock(&sbi->bitmap_lock); 347 348 trim_begin = trim_end = exfat_find_free_bitmap(sb, clu_start); 349 if (trim_begin == EXFAT_EOF_CLUSTER) 350 goto unlock; 351 352 next_free_clu = exfat_find_free_bitmap(sb, trim_end + 1); 353 if (next_free_clu == EXFAT_EOF_CLUSTER) 354 goto unlock; 355 356 do { 357 if (next_free_clu == trim_end + 1) { 358 /* extend trim range for continuous free cluster */ 359 trim_end++; 360 } else { 361 /* trim current range if it's larger than trim_minlen */ 362 count = trim_end - trim_begin + 1; 363 if (count >= trim_minlen) { 364 err = sb_issue_discard(sb, 365 exfat_cluster_to_sector(sbi, trim_begin), 366 count * sbi->sect_per_clus, GFP_NOFS, 0); 367 if (err) 368 goto unlock; 369 370 trimmed_total += count; 371 } 372 373 /* set next start point of the free hole */ 374 trim_begin = trim_end = next_free_clu; 375 } 376 377 if (next_free_clu >= clu_end) 378 break; 379 380 if (fatal_signal_pending(current)) { 381 err = -ERESTARTSYS; 382 goto unlock; 383 } 384 385 next_free_clu = exfat_find_free_bitmap(sb, next_free_clu + 1); 386 } while (next_free_clu != EXFAT_EOF_CLUSTER && 387 next_free_clu > trim_end); 388 389 /* try to trim remainder */ 390 count = trim_end - trim_begin + 1; 391 if (count >= trim_minlen) { 392 err = sb_issue_discard(sb, exfat_cluster_to_sector(sbi, trim_begin), 393 count * sbi->sect_per_clus, GFP_NOFS, 0); 394 if (err) 395 goto unlock; 396 397 trimmed_total += count; 398 } 399 400 unlock: 401 mutex_unlock(&sbi->bitmap_lock); 402 range->len = trimmed_total << sbi->cluster_size_bits; 403 404 return err; 405 } 406