fs/exfat/balloc.c

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