From mboxrd@z Thu Jan 1 00:00:00 1970 From: Bob Copeland Subject: [RFC][PATCH 5/7] omfs: bitmap / block allocation routines Date: Wed, 15 Mar 2006 22:01:44 -0500 Message-ID: <11424781043264-git-send-email-me@bobcopeland.com> References: <11424781041183-git-send-email-me@bobcopeland.com> Reply-To: Bob Copeland Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7BIT Cc: Bob Copeland Return-path: Received: from mail.deathmatch.net ([216.200.85.210]:36068 "EHLO mail.deathmatch.net") by vger.kernel.org with ESMTP id S1752110AbWCPDBr (ORCPT ); Wed, 15 Mar 2006 22:01:47 -0500 In-Reply-To: <11424781041183-git-send-email-me@bobcopeland.com> To: linux-fsdevel@vger.kernel.org Sender: linux-fsdevel-owner@vger.kernel.org List-Id: linux-fsdevel.vger.kernel.org This patch adds routines for allocating free space on the disk. The block bitmap is stored on disk and loaded in entirety at mount time. --- fs/omfs/bitmap.c | 194 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 194 insertions(+), 0 deletions(-) create mode 100644 fs/omfs/bitmap.c c805e8524962d2277276d5337fe72b0f78fd2cd3 diff --git a/fs/omfs/bitmap.c b/fs/omfs/bitmap.c new file mode 100644 index 0000000..2b740a1 --- /dev/null +++ b/fs/omfs/bitmap.c @@ -0,0 +1,194 @@ +#include +#include +#include +#include "omfs.h" + +static int nibblemap[] = {4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0}; + +unsigned long omfs_count_free(struct super_block *sb) +{ + unsigned int i, j, count = 0; + long *map; + unsigned long sum = 0; + struct omfs_sb_info *sbi = OMFS_SB(sb); + + // lock + for (i = 0; i < sbi->s_imap_size; i++) + { + map = sbi->s_imap[i]; + for (j=0; j < sb->s_blocksize && + count + j < sbi->s_num_blocks/8; j++) + sum += nibblemap[map[j] & 0xf] + + nibblemap[(map[j] >> 4) & 0xf]; + count += sb->s_blocksize; + } + // unlock + 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. + * Assumes block lock is held. + */ +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 the run of count bits starting with bit. + */ +static int set_run(struct super_block *sb, int map, + int nbits, int bit, int count) +{ + int i; + struct buffer_head *bh; + struct omfs_sb_info *sbi = OMFS_SB(sb); + + bh = sb_bread(sb, clus_to_blk(sbi, sbi->s_bitmap_ino + map)); + if (!bh) + goto nomem; + + 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 nomem; + } + set_bit(bit, sbi->s_imap[map]); + set_bit(bit, (long*) bh->b_data); + } + mark_buffer_dirty(bh); + brelse(bh); + return 0; +nomem: + return -ENOMEM; +} + +/* + * 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 = 1; + u64 tmp; + + tmp = block; + bit = do_div(tmp, bits_per_entry); + map = tmp; + + // lock + if (map >= sbi->s_imap_size || + test_and_set_bit(bit, sbi->s_imap[map])) + { + ret = 0; + goto out; + } + + if (sbi->s_bitmap_ino > 0) + { + bh = sb_bread(sb, clus_to_blk(sbi, sbi->s_bitmap_ino + map)); + if (!bh) + { + ret = 0; + goto out; + } + set_bit(bit, (long*) bh->b_data); + mark_buffer_dirty(bh); + brelse(bh); + } +out: + printk(KERN_DEBUG + "omfs: requested 1 block at %llx (%s)\n", + block, ret ? "filled" : "unfilled"); + // unlock + 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; + + // 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); + run = count_run(&sbi->s_imap[i], bits_per_entry, + sbi->s_imap_size-i, bit, max_request); + + printk(KERN_DEBUG "run starting at %x is %d bits long\n", + i * bits_per_entry + bit, run); + + + 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); + + printk(KERN_DEBUG + "omfs: requested %d->%d blocks, filled at %llx (%d)\n", + min_request, max_request, *return_block, *return_size); + +out: + if (ret) + printk(KERN_DEBUG + "omfs: requested %d->%d blocks, unfilled at %d\n", + min_request, max_request, i); + // unlock + return ret; +} + -- 1.2.1