[RFC][PATCH 5/7] omfs: bitmap / block allocation routines

[Bob Copeland <me@bobcopeland.com>]

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 <linux/kernel.h>
+#include <linux/fs.h>
+#include <linux/buffer_head.h>
+#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