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