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_msg(sb, KERN_ERR, 62 "bogus allocation bitmap size(need : %u, cur : %lld)", 63 need_map_size, map_size); 64 /* 65 * Only allowed when bogus allocation 66 * bitmap size is large 67 */ 68 if (need_map_size > map_size) 69 return -EIO; 70 } 71 sbi->map_sectors = ((need_map_size - 1) >> 72 (sb->s_blocksize_bits)) + 1; 73 sbi->vol_amap = kmalloc_array(sbi->map_sectors, 74 sizeof(struct buffer_head *), GFP_KERNEL); 75 if (!sbi->vol_amap) 76 return -ENOMEM; 77 78 sector = exfat_cluster_to_sector(sbi, sbi->map_clu); 79 for (i = 0; i < sbi->map_sectors; i++) { 80 sbi->vol_amap[i] = sb_bread(sb, sector + i); 81 if (!sbi->vol_amap[i]) { 82 /* release all buffers and free vol_amap */ 83 int j = 0; 84 85 while (j < i) 86 brelse(sbi->vol_amap[j++]); 87 88 kfree(sbi->vol_amap); 89 sbi->vol_amap = NULL; 90 return -EIO; 91 } 92 } 93 94 sbi->pbr_bh = NULL; 95 return 0; 96 } 97 98 int exfat_load_bitmap(struct super_block *sb) 99 { 100 unsigned int i, type; 101 struct exfat_chain clu; 102 struct exfat_sb_info *sbi = EXFAT_SB(sb); 103 104 exfat_chain_set(&clu, sbi->root_dir, 0, ALLOC_FAT_CHAIN); 105 while (clu.dir != EXFAT_EOF_CLUSTER) { 106 for (i = 0; i < sbi->dentries_per_clu; i++) { 107 struct exfat_dentry *ep; 108 struct buffer_head *bh; 109 110 ep = exfat_get_dentry(sb, &clu, i, &bh, NULL); 111 if (!ep) 112 return -EIO; 113 114 type = exfat_get_entry_type(ep); 115 if (type == TYPE_UNUSED) 116 break; 117 if (type != TYPE_BITMAP) 118 continue; 119 if (ep->dentry.bitmap.flags == 0x0) { 120 int err; 121 122 err = exfat_allocate_bitmap(sb, ep); 123 brelse(bh); 124 return err; 125 } 126 brelse(bh); 127 } 128 129 if (exfat_get_next_cluster(sb, &clu.dir)) 130 return -EIO; 131 } 132 133 return -EINVAL; 134 } 135 136 void exfat_free_bitmap(struct exfat_sb_info *sbi) 137 { 138 int i; 139 140 brelse(sbi->pbr_bh); 141 142 for (i = 0; i < sbi->map_sectors; i++) 143 __brelse(sbi->vol_amap[i]); 144 145 kfree(sbi->vol_amap); 146 } 147 148 /* 149 * If the value of "clu" is 0, it means cluster 2 which is the first cluster of 150 * the cluster heap. 151 */ 152 int exfat_set_bitmap(struct inode *inode, unsigned int clu) 153 { 154 int i, b; 155 unsigned int ent_idx; 156 struct super_block *sb = inode->i_sb; 157 struct exfat_sb_info *sbi = EXFAT_SB(sb); 158 159 WARN_ON(clu < EXFAT_FIRST_CLUSTER); 160 ent_idx = CLUSTER_TO_BITMAP_ENT(clu); 161 i = BITMAP_OFFSET_SECTOR_INDEX(sb, ent_idx); 162 b = BITMAP_OFFSET_BIT_IN_SECTOR(sb, ent_idx); 163 164 set_bit_le(b, sbi->vol_amap[i]->b_data); 165 exfat_update_bh(sb, sbi->vol_amap[i], IS_DIRSYNC(inode)); 166 return 0; 167 } 168 169 /* 170 * If the value of "clu" is 0, it means cluster 2 which is the first cluster of 171 * the cluster heap. 172 */ 173 void exfat_clear_bitmap(struct inode *inode, unsigned int clu) 174 { 175 int i, b; 176 unsigned int ent_idx; 177 struct super_block *sb = inode->i_sb; 178 struct exfat_sb_info *sbi = EXFAT_SB(sb); 179 struct exfat_mount_options *opts = &sbi->options; 180 181 WARN_ON(clu < EXFAT_FIRST_CLUSTER); 182 ent_idx = CLUSTER_TO_BITMAP_ENT(clu); 183 i = BITMAP_OFFSET_SECTOR_INDEX(sb, ent_idx); 184 b = BITMAP_OFFSET_BIT_IN_SECTOR(sb, ent_idx); 185 186 clear_bit_le(b, sbi->vol_amap[i]->b_data); 187 exfat_update_bh(sb, sbi->vol_amap[i], IS_DIRSYNC(inode)); 188 189 if (opts->discard) { 190 int ret_discard; 191 192 ret_discard = sb_issue_discard(sb, 193 exfat_cluster_to_sector(sbi, clu + 194 EXFAT_RESERVED_CLUSTERS), 195 (1 << sbi->sect_per_clus_bits), GFP_NOFS, 0); 196 197 if (ret_discard == -EOPNOTSUPP) { 198 exfat_msg(sb, KERN_ERR, 199 "discard not supported by device, disabling"); 200 opts->discard = 0; 201 } 202 } 203 } 204 205 /* 206 * If the value of "clu" is 0, it means cluster 2 which is the first cluster of 207 * the cluster heap. 208 */ 209 unsigned int exfat_find_free_bitmap(struct super_block *sb, unsigned int clu) 210 { 211 unsigned int i, map_i, map_b, ent_idx; 212 unsigned int clu_base, clu_free; 213 unsigned char k, clu_mask; 214 struct exfat_sb_info *sbi = EXFAT_SB(sb); 215 216 WARN_ON(clu < EXFAT_FIRST_CLUSTER); 217 ent_idx = CLUSTER_TO_BITMAP_ENT(clu); 218 clu_base = BITMAP_ENT_TO_CLUSTER(ent_idx & ~(BITS_PER_BYTE_MASK)); 219 clu_mask = IGNORED_BITS_REMAINED(clu, clu_base); 220 221 map_i = BITMAP_OFFSET_SECTOR_INDEX(sb, ent_idx); 222 map_b = BITMAP_OFFSET_BYTE_IN_SECTOR(sb, ent_idx); 223 224 for (i = EXFAT_FIRST_CLUSTER; i < sbi->num_clusters; 225 i += BITS_PER_BYTE) { 226 k = *(sbi->vol_amap[map_i]->b_data + map_b); 227 if (clu_mask > 0) { 228 k |= clu_mask; 229 clu_mask = 0; 230 } 231 if (k < 0xFF) { 232 clu_free = clu_base + free_bit[k]; 233 if (clu_free < sbi->num_clusters) 234 return clu_free; 235 } 236 clu_base += BITS_PER_BYTE; 237 238 if (++map_b >= sb->s_blocksize || 239 clu_base >= sbi->num_clusters) { 240 if (++map_i >= sbi->map_sectors) { 241 clu_base = EXFAT_FIRST_CLUSTER; 242 map_i = 0; 243 } 244 map_b = 0; 245 } 246 } 247 248 return EXFAT_EOF_CLUSTER; 249 } 250 251 int exfat_count_used_clusters(struct super_block *sb, unsigned int *ret_count) 252 { 253 struct exfat_sb_info *sbi = EXFAT_SB(sb); 254 unsigned int count = 0; 255 unsigned int i, map_i = 0, map_b = 0; 256 unsigned int total_clus = EXFAT_DATA_CLUSTER_COUNT(sbi); 257 unsigned int last_mask = total_clus & BITS_PER_BYTE_MASK; 258 unsigned char clu_bits; 259 const unsigned char last_bit_mask[] = {0, 0b00000001, 0b00000011, 260 0b00000111, 0b00001111, 0b00011111, 0b00111111, 0b01111111}; 261 262 total_clus &= ~last_mask; 263 for (i = 0; i < total_clus; i += BITS_PER_BYTE) { 264 clu_bits = *(sbi->vol_amap[map_i]->b_data + map_b); 265 count += used_bit[clu_bits]; 266 if (++map_b >= (unsigned int)sb->s_blocksize) { 267 map_i++; 268 map_b = 0; 269 } 270 } 271 272 if (last_mask) { 273 clu_bits = *(sbi->vol_amap[map_i]->b_data + map_b); 274 clu_bits &= last_bit_mask[last_mask]; 275 count += used_bit[clu_bits]; 276 } 277 278 *ret_count = count; 279 return 0; 280 } 281