fs/omfs/bitmap.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 #include <linux/kernel.h>
   3 #include <linux/fs.h>
   4 #include <linux/buffer_head.h>
   5 #include <asm/div64.h>
   6 #include "omfs.h"
   7
   8 unsigned long omfs_count_free(struct super_block *sb)
   9 {
  10         unsigned int i;
  11         unsigned long sum = 0;
  12         struct omfs_sb_info *sbi = OMFS_SB(sb);
  13         int nbits = sb->s_blocksize * 8;
  14
  15         for (i = 0; i < sbi->s_imap_size; i++)
  16                 sum += nbits - bitmap_weight(sbi->s_imap[i], nbits);
  17
  18         return sum;
  19 }
  20
  21 /*
  22  *  Counts the run of zero bits starting at bit up to max.
  23  *  It handles the case where a run might spill over a buffer.
  24  *  Called with bitmap lock.
  25  */
  26 static int count_run(unsigned long **addr, int nbits,
  27                 int addrlen, int bit, int max)
  28 {
  29         int count = 0;
  30         int x;
  31
  32         for (; addrlen > 0; addrlen--, addr++) {
  33                 x = find_next_bit(*addr, nbits, bit);
  34                 count += x - bit;
  35
  36                 if (x < nbits || count > max)
  37                         return min(count, max);
  38
  39                 bit = 0;
  40         }
  41         return min(count, max);
  42 }
  43
  44 /*
  45  * Sets or clears the run of count bits starting with bit.
  46  * Called with bitmap lock.
  47  */
  48 static int set_run(struct super_block *sb, int map,
  49                 int nbits, int bit, int count, int set)
  50 {
  51         int i;
  52         int err;
  53         struct buffer_head *bh;
  54         struct omfs_sb_info *sbi = OMFS_SB(sb);
  55
  56         err = -ENOMEM;
  57         bh = sb_bread(sb, clus_to_blk(sbi, sbi->s_bitmap_ino) + map);
  58         if (!bh)
  59                 goto out;
  60
  61         for (i = 0; i < count; i++, bit++) {
  62                 if (bit >= nbits) {
  63                         bit = 0;
  64                         map++;
  65
  66                         mark_buffer_dirty(bh);
  67                         brelse(bh);
  68                         bh = sb_bread(sb,
  69                                 clus_to_blk(sbi, sbi->s_bitmap_ino) + map);
  70                         if (!bh)
  71                                 goto out;
  72                 }
  73                 if (set) {
  74                         set_bit(bit, sbi->s_imap[map]);
  75                         set_bit(bit, (unsigned long *)bh->b_data);
  76                 } else {
  77                         clear_bit(bit, sbi->s_imap[map]);
  78                         clear_bit(bit, (unsigned long *)bh->b_data);
  79                 }
  80         }
  81         mark_buffer_dirty(bh);
  82         brelse(bh);
  83         err = 0;
  84 out:
  85         return err;
  86 }
  87
  88 /*
  89  * Tries to allocate exactly one block.  Returns true if successful.
  90  */
  91 int omfs_allocate_block(struct super_block *sb, u64 block)
  92 {
  93         struct buffer_head *bh;
  94         struct omfs_sb_info *sbi = OMFS_SB(sb);
  95         int bits_per_entry = 8 * sb->s_blocksize;
  96         unsigned int map, bit;
  97         int ret = 0;
  98         u64 tmp;
  99
 100         tmp = block;
 101         bit = do_div(tmp, bits_per_entry);
 102         map = tmp;
 103
 104         mutex_lock(&sbi->s_bitmap_lock);
 105         if (map >= sbi->s_imap_size || test_and_set_bit(bit, sbi->s_imap[map]))
 106                 goto out;
 107
 108         if (sbi->s_bitmap_ino > 0) {
 109                 bh = sb_bread(sb, clus_to_blk(sbi, sbi->s_bitmap_ino) + map);
 110                 if (!bh)
 111                         goto out;
 112
 113                 set_bit(bit, (unsigned long *)bh->b_data);
 114                 mark_buffer_dirty(bh);
 115                 brelse(bh);
 116         }
 117         ret = 1;
 118 out:
 119         mutex_unlock(&sbi->s_bitmap_lock);
 120         return ret;
 121 }
 122
 123
 124 /*
 125  *  Tries to allocate a set of blocks.  The request size depends on the
 126  *  type: for inodes, we must allocate sbi->s_mirrors blocks, and for file
 127  *  blocks, we try to allocate sbi->s_clustersize, but can always get away
 128  *  with just one block.
 129  */
 130 int omfs_allocate_range(struct super_block *sb,
 131                         int min_request,
 132                         int max_request,
 133                         u64 *return_block,
 134                         int *return_size)
 135 {
 136         struct omfs_sb_info *sbi = OMFS_SB(sb);
 137         int bits_per_entry = 8 * sb->s_blocksize;
 138         int ret = 0;
 139         int i, run, bit;
 140
 141         mutex_lock(&sbi->s_bitmap_lock);
 142         for (i = 0; i < sbi->s_imap_size; i++) {
 143                 bit = 0;
 144                 while (bit < bits_per_entry) {
 145                         bit = find_next_zero_bit(sbi->s_imap[i], bits_per_entry,
 146                                 bit);
 147
 148                         if (bit == bits_per_entry)
 149                                 break;
 150
 151                         run = count_run(&sbi->s_imap[i], bits_per_entry,
 152                                 sbi->s_imap_size-i, bit, max_request);
 153
 154                         if (run >= min_request)
 155                                 goto found;
 156                         bit += run;
 157                 }
 158         }
 159         ret = -ENOSPC;
 160         goto out;
 161
 162 found:
 163         *return_block = (u64) i * bits_per_entry + bit;
 164         *return_size = run;
 165         ret = set_run(sb, i, bits_per_entry, bit, run, 1);
 166
 167 out:
 168         mutex_unlock(&sbi->s_bitmap_lock);
 169         return ret;
 170 }
 171
 172 /*
 173  * Clears count bits starting at a given block.
 174  */
 175 int omfs_clear_range(struct super_block *sb, u64 block, int count)
 176 {
 177         struct omfs_sb_info *sbi = OMFS_SB(sb);
 178         int bits_per_entry = 8 * sb->s_blocksize;
 179         u64 tmp;
 180         unsigned int map, bit;
 181         int ret;
 182
 183         tmp = block;
 184         bit = do_div(tmp, bits_per_entry);
 185         map = tmp;
 186
 187         if (map >= sbi->s_imap_size)
 188                 return 0;
 189
 190         mutex_lock(&sbi->s_bitmap_lock);
 191         ret = set_run(sb, map, bits_per_entry, bit, count, 0);
 192         mutex_unlock(&sbi->s_bitmap_lock);
 193         return ret;
 194 }