From 36cc410a6799a205bfc6ccc38abd9d52f2afba64 Mon Sep 17 00:00:00 2001 From: Bob Copeland Date: Fri, 25 Jul 2008 19:45:17 -0700 Subject: omfs: add bitmap routines Add block allocation and block bitmap management routines for OMFS. Signed-off-by: Bob Copeland Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- fs/omfs/bitmap.c | 192 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 192 insertions(+) create mode 100644 fs/omfs/bitmap.c (limited to 'fs/omfs/bitmap.c') diff --git a/fs/omfs/bitmap.c b/fs/omfs/bitmap.c new file mode 100644 index 00000000000..dc75f22be3f --- /dev/null +++ b/fs/omfs/bitmap.c @@ -0,0 +1,192 @@ +#include +#include +#include +#include +#include "omfs.h" + +unsigned long omfs_count_free(struct super_block *sb) +{ + unsigned int i; + unsigned long sum = 0; + struct omfs_sb_info *sbi = OMFS_SB(sb); + int nbits = sb->s_blocksize * 8; + + for (i = 0; i < sbi->s_imap_size; i++) + sum += nbits - bitmap_weight(sbi->s_imap[i], nbits); + + return sum; +} + +/* + * Counts the run of zero bits starting at bit up to max. + * It handles the case where a run might spill over a buffer. + * Called with bitmap lock. + */ +static int count_run(unsigned long **addr, int nbits, + int addrlen, int bit, int max) +{ + int count = 0; + int x; + + for (; addrlen > 0; addrlen--, addr++) { + x = find_next_bit(*addr, nbits, bit); + count += x - bit; + + if (x < nbits || count > max) + return min(count, max); + + bit = 0; + } + return min(count, max); +} + +/* + * Sets or clears the run of count bits starting with bit. + * Called with bitmap lock. + */ +static int set_run(struct super_block *sb, int map, + int nbits, int bit, int count, int set) +{ + int i; + int err; + struct buffer_head *bh; + struct omfs_sb_info *sbi = OMFS_SB(sb); + + err = -ENOMEM; + bh = sb_bread(sb, clus_to_blk(sbi, sbi->s_bitmap_ino) + map); + if (!bh) + goto out; + + for (i = 0; i < count; i++, bit++) { + if (bit >= nbits) { + bit = 0; + map++; + + mark_buffer_dirty(bh); + brelse(bh); + bh = sb_bread(sb, + clus_to_blk(sbi, sbi->s_bitmap_ino) + map); + if (!bh) + goto out; + } + if (set) { + set_bit(bit, sbi->s_imap[map]); + set_bit(bit, (long *) bh->b_data); + } else { + clear_bit(bit, sbi->s_imap[map]); + clear_bit(bit, (long *) bh->b_data); + } + } + mark_buffer_dirty(bh); + brelse(bh); + err = 0; +out: + return err; +} + +/* + * Tries to allocate exactly one block. Returns true if sucessful. + */ +int omfs_allocate_block(struct super_block *sb, u64 block) +{ + struct buffer_head *bh; + struct omfs_sb_info *sbi = OMFS_SB(sb); + int bits_per_entry = 8 * sb->s_blocksize; + int map, bit; + int ret = 0; + u64 tmp; + + tmp = block; + bit = do_div(tmp, bits_per_entry); + map = tmp; + + mutex_lock(&sbi->s_bitmap_lock); + if (map >= sbi->s_imap_size || test_and_set_bit(bit, sbi->s_imap[map])) + goto out; + + if (sbi->s_bitmap_ino > 0) { + bh = sb_bread(sb, clus_to_blk(sbi, sbi->s_bitmap_ino) + map); + if (!bh) + goto out; + + set_bit(bit, (long *) bh->b_data); + mark_buffer_dirty(bh); + brelse(bh); + } + ret = 1; +out: + mutex_unlock(&sbi->s_bitmap_lock); + return ret; +} + + +/* + * Tries to allocate a set of blocks. The request size depends on the + * type: for inodes, we must allocate sbi->s_mirrors blocks, and for file + * blocks, we try to allocate sbi->s_clustersize, but can always get away + * with just one block. + */ +int omfs_allocate_range(struct super_block *sb, + int min_request, + int max_request, + u64 *return_block, + int *return_size) +{ + struct omfs_sb_info *sbi = OMFS_SB(sb); + int bits_per_entry = 8 * sb->s_blocksize; + int ret = 0; + int i, run, bit; + + mutex_lock(&sbi->s_bitmap_lock); + for (i = 0; i < sbi->s_imap_size; i++) { + bit = 0; + while (bit < bits_per_entry) { + bit = find_next_zero_bit(sbi->s_imap[i], bits_per_entry, + bit); + + if (bit == bits_per_entry) + break; + + run = count_run(&sbi->s_imap[i], bits_per_entry, + sbi->s_imap_size-i, bit, max_request); + + if (run >= min_request) + goto found; + bit += run; + } + } + ret = -ENOSPC; + goto out; + +found: + *return_block = i * bits_per_entry + bit; + *return_size = run; + ret = set_run(sb, i, bits_per_entry, bit, run, 1); + +out: + mutex_unlock(&sbi->s_bitmap_lock); + return ret; +} + +/* + * Clears count bits starting at a given block. + */ +int omfs_clear_range(struct super_block *sb, u64 block, int count) +{ + struct omfs_sb_info *sbi = OMFS_SB(sb); + int bits_per_entry = 8 * sb->s_blocksize; + u64 tmp; + int map, bit, ret; + + tmp = block; + bit = do_div(tmp, bits_per_entry); + map = tmp; + + if (map >= sbi->s_imap_size) + return 0; + + mutex_lock(&sbi->s_bitmap_lock); + ret = set_run(sb, map, bits_per_entry, bit, count, 0); + mutex_unlock(&sbi->s_bitmap_lock); + return ret; +} -- cgit v1.2.3-70-g09d2 From d406f66ddb0d7491ddd53e4600c425d76a8a245f Mon Sep 17 00:00:00 2001 From: Harvey Harrison Date: Tue, 29 Jul 2008 22:33:46 -0700 Subject: omfs: sparse annotations Missing cpu_to_be64 on some constant assignments. fs/omfs/dir.c:107:16: warning: incorrect type in assignment (different base types) fs/omfs/dir.c:107:16: expected restricted __be64 [usertype] i_sibling fs/omfs/dir.c:107:16: got unsigned long long fs/omfs/file.c:33:13: warning: incorrect type in assignment (different base types) fs/omfs/file.c:33:13: expected restricted __be64 [usertype] e_next fs/omfs/file.c:33:13: got unsigned long long fs/omfs/file.c:36:24: warning: incorrect type in assignment (different base types) fs/omfs/file.c:36:24: expected restricted __be64 [usertype] e_cluster fs/omfs/file.c:36:24: got unsigned long long fs/omfs/file.c:37:23: warning: incorrect type in assignment (different base types) fs/omfs/file.c:37:23: expected restricted __be64 [usertype] e_blocks fs/omfs/file.c:37:23: got unsigned long long fs/omfs/bitmap.c:74:18: warning: incorrect type in argument 2 (different signedness) fs/omfs/bitmap.c:74:18: expected unsigned long volatile *addr fs/omfs/bitmap.c:74:18: got long * fs/omfs/bitmap.c:77:20: warning: incorrect type in argument 2 (different signedness) fs/omfs/bitmap.c:77:20: expected unsigned long volatile *addr fs/omfs/bitmap.c:77:20: got long * fs/omfs/bitmap.c:112:17: warning: incorrect type in argument 2 (different signedness) fs/omfs/bitmap.c:112:17: expected unsigned long volatile *addr fs/omfs/bitmap.c:112:17: got long * Signed-off-by: Harvey Harrison Acked-by: Bob Copeland Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- fs/omfs/bitmap.c | 6 +++--- fs/omfs/dir.c | 2 +- fs/omfs/file.c | 6 +++--- 3 files changed, 7 insertions(+), 7 deletions(-) (limited to 'fs/omfs/bitmap.c') diff --git a/fs/omfs/bitmap.c b/fs/omfs/bitmap.c index dc75f22be3f..697663b01ba 100644 --- a/fs/omfs/bitmap.c +++ b/fs/omfs/bitmap.c @@ -71,10 +71,10 @@ static int set_run(struct super_block *sb, int map, } if (set) { set_bit(bit, sbi->s_imap[map]); - set_bit(bit, (long *) bh->b_data); + set_bit(bit, (unsigned long *)bh->b_data); } else { clear_bit(bit, sbi->s_imap[map]); - clear_bit(bit, (long *) bh->b_data); + clear_bit(bit, (unsigned long *)bh->b_data); } } mark_buffer_dirty(bh); @@ -109,7 +109,7 @@ int omfs_allocate_block(struct super_block *sb, u64 block) if (!bh) goto out; - set_bit(bit, (long *) bh->b_data); + set_bit(bit, (unsigned long *)bh->b_data); mark_buffer_dirty(bh); brelse(bh); } diff --git a/fs/omfs/dir.c b/fs/omfs/dir.c index 05a5bc31e4b..c0757e99887 100644 --- a/fs/omfs/dir.c +++ b/fs/omfs/dir.c @@ -104,7 +104,7 @@ int omfs_make_empty(struct inode *inode, struct super_block *sb) oi = (struct omfs_inode *) bh->b_data; oi->i_head.h_self = cpu_to_be64(inode->i_ino); - oi->i_sibling = ~0ULL; + oi->i_sibling = ~cpu_to_be64(0ULL); mark_buffer_dirty(bh); brelse(bh); diff --git a/fs/omfs/file.c b/fs/omfs/file.c index 66e01fae438..7e2499053e4 100644 --- a/fs/omfs/file.c +++ b/fs/omfs/file.c @@ -30,11 +30,11 @@ void omfs_make_empty_table(struct buffer_head *bh, int offset) { struct omfs_extent *oe = (struct omfs_extent *) &bh->b_data[offset]; - oe->e_next = ~0ULL; + oe->e_next = ~cpu_to_be64(0ULL); oe->e_extent_count = cpu_to_be32(1), oe->e_fill = cpu_to_be32(0x22), - oe->e_entry.e_cluster = ~0ULL; - oe->e_entry.e_blocks = ~0ULL; + oe->e_entry.e_cluster = ~cpu_to_be64(0ULL); + oe->e_entry.e_blocks = ~cpu_to_be64(0ULL); } int omfs_shrink_inode(struct inode *inode) -- cgit v1.2.3-70-g09d2