fs/omfs/bitmap.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 #include <linux/kernel.h>
0003 #include <linux/fs.h>
0004 #include <linux/buffer_head.h>
0005 #include <asm/div64.h>
0006 #include "omfs.h"
0007
0008 unsigned long omfs_count_free(struct super_block *sb)
0009 {
0010     unsigned int i;
0011     unsigned long sum = 0;
0012     struct omfs_sb_info *sbi = OMFS_SB(sb);
0013     int nbits = sb->s_blocksize * 8;
0014
0015     for (i = 0; i < sbi->s_imap_size; i++)
0016         sum += nbits - bitmap_weight(sbi->s_imap[i], nbits);
0017
0018     return sum;
0019 }
0020
0021 /*
0022  *  Counts the run of zero bits starting at bit up to max.
0023  *  It handles the case where a run might spill over a buffer.
0024  *  Called with bitmap lock.
0025  */
0026 static int count_run(unsigned long **addr, int nbits,
0027         int addrlen, int bit, int max)
0028 {
0029     int count = 0;
0030     int x;
0031
0032     for (; addrlen > 0; addrlen--, addr++) {
0033         x = find_next_bit(*addr, nbits, bit);
0034         count += x - bit;
0035
0036         if (x < nbits || count > max)
0037             return min(count, max);
0038
0039         bit = 0;
0040     }
0041     return min(count, max);
0042 }
0043
0044 /*
0045  * Sets or clears the run of count bits starting with bit.
0046  * Called with bitmap lock.
0047  */
0048 static int set_run(struct super_block *sb, int map,
0049         int nbits, int bit, int count, int set)
0050 {
0051     int i;
0052     int err;
0053     struct buffer_head *bh;
0054     struct omfs_sb_info *sbi = OMFS_SB(sb);
0055
0056     err = -ENOMEM;
0057     bh = sb_bread(sb, clus_to_blk(sbi, sbi->s_bitmap_ino) + map);
0058     if (!bh)
0059         goto out;
0060
0061     for (i = 0; i < count; i++, bit++) {
0062         if (bit >= nbits) {
0063             bit = 0;
0064             map++;
0065
0066             mark_buffer_dirty(bh);
0067             brelse(bh);
0068             bh = sb_bread(sb,
0069                 clus_to_blk(sbi, sbi->s_bitmap_ino) + map);
0070             if (!bh)
0071                 goto out;
0072         }
0073         if (set) {
0074             set_bit(bit, sbi->s_imap[map]);
0075             set_bit(bit, (unsigned long *)bh->b_data);
0076         } else {
0077             clear_bit(bit, sbi->s_imap[map]);
0078             clear_bit(bit, (unsigned long *)bh->b_data);
0079         }
0080     }
0081     mark_buffer_dirty(bh);
0082     brelse(bh);
0083     err = 0;
0084 out:
0085     return err;
0086 }
0087
0088 /*
0089  * Tries to allocate exactly one block.  Returns true if successful.
0090  */
0091 int omfs_allocate_block(struct super_block *sb, u64 block)
0092 {
0093     struct buffer_head *bh;
0094     struct omfs_sb_info *sbi = OMFS_SB(sb);
0095     int bits_per_entry = 8 * sb->s_blocksize;
0096     unsigned int map, bit;
0097     int ret = 0;
0098     u64 tmp;
0099
0100     tmp = block;
0101     bit = do_div(tmp, bits_per_entry);
0102     map = tmp;
0103
0104     mutex_lock(&sbi->s_bitmap_lock);
0105     if (map >= sbi->s_imap_size || test_and_set_bit(bit, sbi->s_imap[map]))
0106         goto out;
0107
0108     if (sbi->s_bitmap_ino > 0) {
0109         bh = sb_bread(sb, clus_to_blk(sbi, sbi->s_bitmap_ino) + map);
0110         if (!bh)
0111             goto out;
0112
0113         set_bit(bit, (unsigned long *)bh->b_data);
0114         mark_buffer_dirty(bh);
0115         brelse(bh);
0116     }
0117     ret = 1;
0118 out:
0119     mutex_unlock(&sbi->s_bitmap_lock);
0120     return ret;
0121 }
0122
0123
0124 /*
0125  *  Tries to allocate a set of blocks.  The request size depends on the
0126  *  type: for inodes, we must allocate sbi->s_mirrors blocks, and for file
0127  *  blocks, we try to allocate sbi->s_clustersize, but can always get away
0128  *  with just one block.
0129  */
0130 int omfs_allocate_range(struct super_block *sb,
0131             int min_request,
0132             int max_request,
0133             u64 *return_block,
0134             int *return_size)
0135 {
0136     struct omfs_sb_info *sbi = OMFS_SB(sb);
0137     int bits_per_entry = 8 * sb->s_blocksize;
0138     int ret = 0;
0139     int i, run, bit;
0140
0141     mutex_lock(&sbi->s_bitmap_lock);
0142     for (i = 0; i < sbi->s_imap_size; i++) {
0143         bit = 0;
0144         while (bit < bits_per_entry) {
0145             bit = find_next_zero_bit(sbi->s_imap[i], bits_per_entry,
0146                 bit);
0147
0148             if (bit == bits_per_entry)
0149                 break;
0150
0151             run = count_run(&sbi->s_imap[i], bits_per_entry,
0152                 sbi->s_imap_size-i, bit, max_request);
0153
0154             if (run >= min_request)
0155                 goto found;
0156             bit += run;
0157         }
0158     }
0159     ret = -ENOSPC;
0160     goto out;
0161
0162 found:
0163     *return_block = (u64) i * bits_per_entry + bit;
0164     *return_size = run;
0165     ret = set_run(sb, i, bits_per_entry, bit, run, 1);
0166
0167 out:
0168     mutex_unlock(&sbi->s_bitmap_lock);
0169     return ret;
0170 }
0171
0172 /*
0173  * Clears count bits starting at a given block.
0174  */
0175 int omfs_clear_range(struct super_block *sb, u64 block, int count)
0176 {
0177     struct omfs_sb_info *sbi = OMFS_SB(sb);
0178     int bits_per_entry = 8 * sb->s_blocksize;
0179     u64 tmp;
0180     unsigned int map, bit;
0181     int ret;
0182
0183     tmp = block;
0184     bit = do_div(tmp, bits_per_entry);
0185     map = tmp;
0186
0187     if (map >= sbi->s_imap_size)
0188         return 0;
0189
0190     mutex_lock(&sbi->s_bitmap_lock);
0191     ret = set_run(sb, map, bits_per_entry, bit, count, 0);
0192     mutex_unlock(&sbi->s_bitmap_lock);
0193     return ret;
0194 }