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/buffer_head.h> 9 10 #include "exfat_raw.h" 11 #include "exfat_fs.h" 12 13 static const unsigned char free_bit[] = { 14 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2,/* 0 ~ 19*/ 15 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3,/* 20 ~ 39*/ 16 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,/* 40 ~ 59*/ 17 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,/* 60 ~ 79*/ 18 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2,/* 80 ~ 99*/ 19 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3,/*100 ~ 119*/ 20 0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,/*120 ~ 139*/ 21 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,/*140 ~ 159*/ 22 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2,/*160 ~ 179*/ 23 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3,/*180 ~ 199*/ 24 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,/*200 ~ 219*/ 25 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,/*220 ~ 239*/ 26 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 /*240 ~ 254*/ 27 }; 28 29 static const unsigned char used_bit[] = { 30 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3,/* 0 ~ 19*/ 31 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4,/* 20 ~ 39*/ 32 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5,/* 40 ~ 59*/ 33 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,/* 60 ~ 79*/ 34 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,/* 80 ~ 99*/ 35 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,/*100 ~ 119*/ 36 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,/*120 ~ 139*/ 37 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,/*140 ~ 159*/ 38 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5,/*160 ~ 179*/ 39 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,/*180 ~ 199*/ 40 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6,/*200 ~ 219*/ 41 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,/*220 ~ 239*/ 42 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 /*240 ~ 255*/ 43 }; 44 45 /* 46 * Allocation Bitmap Management Functions 47 */ 48 static int exfat_allocate_bitmap(struct super_block *sb, 49 struct exfat_dentry *ep) 50 { 51 struct exfat_sb_info *sbi = EXFAT_SB(sb); 52 long long map_size; 53 unsigned int i, need_map_size; 54 sector_t sector; 55 56 sbi->map_clu = le32_to_cpu(ep->dentry.bitmap.start_clu); 57 map_size = le64_to_cpu(ep->dentry.bitmap.size); 58 need_map_size = ((EXFAT_DATA_CLUSTER_COUNT(sbi) - 1) / BITS_PER_BYTE) 59 + 1; 60 if (need_map_size != map_size) { 61 exfat_err(sb, "bogus allocation bitmap size(need : %u, cur : %lld)", 62 need_map_size, map_size); 63 /* 64 * Only allowed when bogus allocation 65 * bitmap size is large 66 */ 67 if (need_map_size > map_size) 68 return -EIO; 69 } 70 sbi->map_sectors = ((need_map_size - 1) >> 71 (sb->s_blocksize_bits)) + 1; 72 sbi->vol_amap = kmalloc_array(sbi->map_sectors, 73 sizeof(struct buffer_head *), GFP_KERNEL); 74 if (!sbi->vol_amap) 75 return -ENOMEM; 76 77 sector = exfat_cluster_to_sector(sbi, sbi->map_clu); 78 for (i = 0; i < sbi->map_sectors; i++) { 79 sbi->vol_amap[i] = sb_bread(sb, sector + i); 80 if (!sbi->vol_amap[i]) { 81 /* release all buffers and free vol_amap */ 82 int j = 0; 83 84 while (j < i) 85 brelse(sbi->vol_amap[j++]); 86 87 kfree(sbi->vol_amap); 88 sbi->vol_amap = NULL; 89 return -EIO; 90 } 91 } 92 93 return 0; 94 } 95 96 int exfat_load_bitmap(struct super_block *sb) 97 { 98 unsigned int i, type; 99 struct exfat_chain clu; 100 struct exfat_sb_info *sbi = EXFAT_SB(sb); 101 102 exfat_chain_set(&clu, sbi->root_dir, 0, ALLOC_FAT_CHAIN); 103 while (clu.dir != EXFAT_EOF_CLUSTER) { 104 for (i = 0; i < sbi->dentries_per_clu; i++) { 105 struct exfat_dentry *ep; 106 struct buffer_head *bh; 107 108 ep = exfat_get_dentry(sb, &clu, i, &bh); 109 if (!ep) 110 return -EIO; 111 112 type = exfat_get_entry_type(ep); 113 if (type == TYPE_UNUSED) 114 break; 115 if (type != TYPE_BITMAP) 116 continue; 117 if (ep->dentry.bitmap.flags == 0x0) { 118 int err; 119 120 err = exfat_allocate_bitmap(sb, ep); 121 brelse(bh); 122 return err; 123 } 124 brelse(bh); 125 } 126 127 if (exfat_get_next_cluster(sb, &clu.dir)) 128 return -EIO; 129 } 130 131 return -EINVAL; 132 } 133 134 void exfat_free_bitmap(struct exfat_sb_info *sbi) 135 { 136 int i; 137 138 for (i = 0; i < sbi->map_sectors; i++) 139 __brelse(sbi->vol_amap[i]); 140 141 kfree(sbi->vol_amap); 142 } 143 144 int exfat_set_bitmap(struct inode *inode, unsigned int clu, bool sync) 145 { 146 int i, b; 147 unsigned int ent_idx; 148 struct super_block *sb = inode->i_sb; 149 struct exfat_sb_info *sbi = EXFAT_SB(sb); 150 151 if (!is_valid_cluster(sbi, clu)) 152 return -EINVAL; 153 154 ent_idx = CLUSTER_TO_BITMAP_ENT(clu); 155 i = BITMAP_OFFSET_SECTOR_INDEX(sb, ent_idx); 156 b = BITMAP_OFFSET_BIT_IN_SECTOR(sb, ent_idx); 157 158 set_bit_le(b, sbi->vol_amap[i]->b_data); 159 exfat_update_bh(sbi->vol_amap[i], sync); 160 return 0; 161 } 162 163 void exfat_clear_bitmap(struct inode *inode, unsigned int clu, bool sync) 164 { 165 int i, b; 166 unsigned int ent_idx; 167 struct super_block *sb = inode->i_sb; 168 struct exfat_sb_info *sbi = EXFAT_SB(sb); 169 struct exfat_mount_options *opts = &sbi->options; 170 171 if (!is_valid_cluster(sbi, clu)) 172 return; 173 174 ent_idx = CLUSTER_TO_BITMAP_ENT(clu); 175 i = BITMAP_OFFSET_SECTOR_INDEX(sb, ent_idx); 176 b = BITMAP_OFFSET_BIT_IN_SECTOR(sb, ent_idx); 177 178 clear_bit_le(b, sbi->vol_amap[i]->b_data); 179 exfat_update_bh(sbi->vol_amap[i], sync); 180 181 if (opts->discard) { 182 int ret_discard; 183 184 ret_discard = sb_issue_discard(sb, 185 exfat_cluster_to_sector(sbi, clu), 186 (1 << sbi->sect_per_clus_bits), GFP_NOFS, 0); 187 188 if (ret_discard == -EOPNOTSUPP) { 189 exfat_err(sb, "discard not supported by device, disabling"); 190 opts->discard = 0; 191 } 192 } 193 } 194 195 /* 196 * If the value of "clu" is 0, it means cluster 2 which is the first cluster of 197 * the cluster heap. 198 */ 199 unsigned int exfat_find_free_bitmap(struct super_block *sb, unsigned int clu) 200 { 201 unsigned int i, map_i, map_b, ent_idx; 202 unsigned int clu_base, clu_free; 203 unsigned char k, clu_mask; 204 struct exfat_sb_info *sbi = EXFAT_SB(sb); 205 206 WARN_ON(clu < EXFAT_FIRST_CLUSTER); 207 ent_idx = CLUSTER_TO_BITMAP_ENT(clu); 208 clu_base = BITMAP_ENT_TO_CLUSTER(ent_idx & ~(BITS_PER_BYTE_MASK)); 209 clu_mask = IGNORED_BITS_REMAINED(clu, clu_base); 210 211 map_i = BITMAP_OFFSET_SECTOR_INDEX(sb, ent_idx); 212 map_b = BITMAP_OFFSET_BYTE_IN_SECTOR(sb, ent_idx); 213 214 for (i = EXFAT_FIRST_CLUSTER; i < sbi->num_clusters; 215 i += BITS_PER_BYTE) { 216 k = *(sbi->vol_amap[map_i]->b_data + map_b); 217 if (clu_mask > 0) { 218 k |= clu_mask; 219 clu_mask = 0; 220 } 221 if (k < 0xFF) { 222 clu_free = clu_base + free_bit[k]; 223 if (clu_free < sbi->num_clusters) 224 return clu_free; 225 } 226 clu_base += BITS_PER_BYTE; 227 228 if (++map_b >= sb->s_blocksize || 229 clu_base >= sbi->num_clusters) { 230 if (++map_i >= sbi->map_sectors) { 231 clu_base = EXFAT_FIRST_CLUSTER; 232 map_i = 0; 233 } 234 map_b = 0; 235 } 236 } 237 238 return EXFAT_EOF_CLUSTER; 239 } 240 241 int exfat_count_used_clusters(struct super_block *sb, unsigned int *ret_count) 242 { 243 struct exfat_sb_info *sbi = EXFAT_SB(sb); 244 unsigned int count = 0; 245 unsigned int i, map_i = 0, map_b = 0; 246 unsigned int total_clus = EXFAT_DATA_CLUSTER_COUNT(sbi); 247 unsigned int last_mask = total_clus & BITS_PER_BYTE_MASK; 248 unsigned char clu_bits; 249 const unsigned char last_bit_mask[] = {0, 0b00000001, 0b00000011, 250 0b00000111, 0b00001111, 0b00011111, 0b00111111, 0b01111111}; 251 252 total_clus &= ~last_mask; 253 for (i = 0; i < total_clus; i += BITS_PER_BYTE) { 254 clu_bits = *(sbi->vol_amap[map_i]->b_data + map_b); 255 count += used_bit[clu_bits]; 256 if (++map_b >= (unsigned int)sb->s_blocksize) { 257 map_i++; 258 map_b = 0; 259 } 260 } 261 262 if (last_mask) { 263 clu_bits = *(sbi->vol_amap[map_i]->b_data + map_b); 264 clu_bits &= last_bit_mask[last_mask]; 265 count += used_bit[clu_bits]; 266 } 267 268 *ret_count = count; 269 return 0; 270 } 271 272 int exfat_trim_fs(struct inode *inode, struct fstrim_range *range) 273 { 274 unsigned int trim_begin, trim_end, count, next_free_clu; 275 u64 clu_start, clu_end, trim_minlen, trimmed_total = 0; 276 struct super_block *sb = inode->i_sb; 277 struct exfat_sb_info *sbi = EXFAT_SB(sb); 278 int err = 0; 279 280 clu_start = max_t(u64, range->start >> sbi->cluster_size_bits, 281 EXFAT_FIRST_CLUSTER); 282 clu_end = clu_start + (range->len >> sbi->cluster_size_bits) - 1; 283 trim_minlen = range->minlen >> sbi->cluster_size_bits; 284 285 if (clu_start >= sbi->num_clusters || range->len < sbi->cluster_size) 286 return -EINVAL; 287 288 if (clu_end >= sbi->num_clusters) 289 clu_end = sbi->num_clusters - 1; 290 291 mutex_lock(&sbi->bitmap_lock); 292 293 trim_begin = trim_end = exfat_find_free_bitmap(sb, clu_start); 294 if (trim_begin == EXFAT_EOF_CLUSTER) 295 goto unlock; 296 297 next_free_clu = exfat_find_free_bitmap(sb, trim_end + 1); 298 if (next_free_clu == EXFAT_EOF_CLUSTER) 299 goto unlock; 300 301 do { 302 if (next_free_clu == trim_end + 1) { 303 /* extend trim range for continuous free cluster */ 304 trim_end++; 305 } else { 306 /* trim current range if it's larger than trim_minlen */ 307 count = trim_end - trim_begin + 1; 308 if (count >= trim_minlen) { 309 err = sb_issue_discard(sb, 310 exfat_cluster_to_sector(sbi, trim_begin), 311 count * sbi->sect_per_clus, GFP_NOFS, 0); 312 if (err) 313 goto unlock; 314 315 trimmed_total += count; 316 } 317 318 /* set next start point of the free hole */ 319 trim_begin = trim_end = next_free_clu; 320 } 321 322 if (next_free_clu >= clu_end) 323 break; 324 325 if (fatal_signal_pending(current)) { 326 err = -ERESTARTSYS; 327 goto unlock; 328 } 329 330 next_free_clu = exfat_find_free_bitmap(sb, next_free_clu + 1); 331 } while (next_free_clu != EXFAT_EOF_CLUSTER && 332 next_free_clu > trim_end); 333 334 /* try to trim remainder */ 335 count = trim_end - trim_begin + 1; 336 if (count >= trim_minlen) { 337 err = sb_issue_discard(sb, exfat_cluster_to_sector(sbi, trim_begin), 338 count * sbi->sect_per_clus, GFP_NOFS, 0); 339 if (err) 340 goto unlock; 341 342 trimmed_total += count; 343 } 344 345 unlock: 346 mutex_unlock(&sbi->bitmap_lock); 347 range->len = trimmed_total << sbi->cluster_size_bits; 348 349 return err; 350 } 351