LXR linux/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
   8unsigned 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 */
  26static 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 */
  48static 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;
  84out:
  85        return err;
  86}
  87
  88/*
  89 * Tries to allocate exactly one block.  Returns true if successful.
  90 */
  91int 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;
 118out:
 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 */
 130int 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
 162found:
 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
 167out:
 168        mutex_unlock(&sbi->s_bitmap_lock);
 169        return ret;
 170}
 171
 172/*
 173 * Clears count bits starting at a given block.
 174 */
 175int 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}
 195