tux3: Refactoring balloc stuff

Current balloc is not supporting multiple segments allocation at
once. So, this adds ability for it.

With this, we would be able to allocate more better block placement,
and even possibly have chance to optimize code itself.

Also, this separates balloc to 2 function:

    - find unused bits
    - modify bitmap

With this separation, we can allocate fewer than found unused bits.
This is needed for extent allocation when extent is not fit to leaf.

Signed-off-by: Daniel Phillips <daniel@tux3.org>
Signed-off-by: OGAWA Hirofumi <hirofumi@mail.parknet.co.jp>

8 files changed, 171 insertions, 168 deletions

diff --git a/fs/tux3/balloc.c b/fs/tux3/balloc.c
index 4aadf1cb9bebc4..bb713458450194 100644
--- a/fs/tux3/balloc.c
+++ b/fs/tux3/balloc.c
@@ -250,203 +250,204 @@ static int bitmap_test_and_modify(struct sb *sb, block_t start, unsigned blocks,
 	return 0;
 }
 
-static void save_seg(struct block_segment *seg, int segs, block_t start,
-		     unsigned count)
+static inline int mergable(struct block_segment *seg, block_t block)
 {
-	if (seg[0].count < count) {
-		seg[0].block = start;
-		seg[0].count = count;
-	}
+	return seg->block + seg->count == block;
 }
 
 /*
- * Allocate block segments from specified range.
+ * Find blocks available in the specified range.
  *
- * The specified range is cyclic. I.e. if start + len bigger than
- * volblocks, search wrapped to 0.
+ * NOTE: Caller must check "*block" to know how many blocks were
+ * found. This returns 0 even if no blocks found.
  *
- * userland only
+ * return value:
+ * < 0 - error
+ *   0 - succeed to check
  */
-int balloc_from_range(struct sb *sb, block_t start, block_t len,
-		      unsigned blocks, unsigned flags,
-		      struct block_segment *seg, int segs)
+int balloc_find_range(struct sb *sb,
+	struct block_segment *seg, int maxsegs, int *segs,
+	block_t start, block_t range, unsigned *blocks)
 {
 	struct inode *bitmap = sb->bitmap;
 	unsigned mapshift = sb->blockbits + 3;
 	unsigned mapsize = 1 << mapshift;
 	unsigned mapmask = mapsize - 1;
 	struct buffer_head *buffer;
-	block_t need, found, mapblock;
-
-	trace("balloc find %i blocks, range [%Lx, %Lx]", blocks, start, len);
-	assert(blocks > 0);
-	assert(len <= sb->volblocks);
-	assert(tux3_under_backend(sb));
 
-	/* Initialize seg[] */
-	memset(seg, 0, sizeof(*seg) * segs);
-
-	need = blocks;
-	while (len > 0) {
-		block_t mapstart;
-		unsigned mapoffset, maplimit, maplen;
-		void *p;
-
-		if (unlikely(start >= sb->volblocks)) {
-			if (need < blocks) {
-				/* Found partial free segment */
-				unsigned blks = blocks - need;
-				found = sb->volblocks - blks;
-				save_seg(seg, segs, found, blks);
-			}
+	trace("find %u blocks in [%Lu+%Lu], segs = %d",
+	      *blocks, start, range, *segs);
 
-			start = 0;
-			/*
-			 * Wrapped at end of volblocks, this is not
-			 * contiguous. So resets "need".
-			 */
-			need = blocks;
-		}
+	assert(*blocks > 0);
+	assert(start < sb->volblocks);
+	assert(start + range <= sb->volblocks);
+	assert(*segs < maxsegs);
+	assert(tux3_under_backend(sb));
 
-		mapblock = start >> mapshift;
-		mapstart = mapblock << mapshift;
-		mapoffset = start & mapmask;
-		maplimit = min_t(block_t, mapsize, mapoffset + len);
-		/* If out of range, apply limit */
-		if (unlikely(mapstart + maplimit > sb->volblocks))
-			maplimit = sb->volblocks & mapmask;
-		maplen = maplimit - mapoffset;
+	/* Search across blocks */
+	while (range > 0) {
+		block_t mapblock = start >> mapshift;
+		block_t mapbase = mapblock << mapshift;
+		unsigned offset = start & mapmask;
+		unsigned maplimit = min_t(block_t, mapsize, offset + range);
+		unsigned chunk = maplimit - offset;
+		char *data;
 
 		buffer = blockread(mapping(bitmap), mapblock);
 		if (!buffer) {
 			tux3_err(sb, "block read failed");
-			// !!! error return sucks here
 			return -EIO;
+			/* FIXME: error handling */
 		}
+		data = bufdata(buffer);
+		/* Search within block */
+		do {
+			block_t end = (block_t)offset + *blocks;
+			unsigned limit, next;
+
+			limit = min_t(block_t, end, maplimit);
+			next = find_next_bit_le(data, limit, offset);
+
+			if (next != offset) {
+				unsigned count = next - offset;
+				block_t found = mapbase + offset;
+
+				if (*segs && mergable(&seg[*segs - 1], found)) {
+					trace("append seg [%Lu+%u]", found, count);
+					seg[*segs - 1].count += count;
+				} else {
+					trace("balloc seg [%Lu+%u]", found, count);
+					seg[(*segs)++] = (struct block_segment){
+						.block = found,
+						.count = count,
+					};
+				}
+				*blocks -= count;
 
-		p = bufdata(buffer);
-		while (1) {
-			unsigned idx, mapnext;
-
-			mapnext = min_t(block_t, mapoffset + need, maplimit);
-
-			/* Check if there is no non-zero bits */
-			idx = find_next_bit_le(p, mapnext, mapoffset);
-			if (idx == mapnext) {
-				need -= idx - mapoffset;
-				if (need)
-					break;	/* Need more blocks */
-
-				/* Found requested free blocks */
-				found = mapstart + idx - blocks;
-				save_seg(seg, segs, found, blocks);
-				goto found_range;
-			}
-
-			need -= idx - mapoffset;
-			if (need < blocks) {
-				/* Found partial free segment */
-				unsigned blks = blocks - need;
-				found = mapstart + idx - blks;
-				save_seg(seg, segs, found, blks);
+				if (!*blocks || *segs == maxsegs) {
+					blockput(buffer);
+					return 0;
+				}
 			}
 
-			/* Reset needed blocks */
-			need = blocks;
-
-			/* Skip non-zero bit */
-			mapoffset = find_next_zero_bit_le(p, maplimit, idx + 1);
-			if (mapoffset == maplimit)
-				break;	/* Search next blocks */
-		}
-
-		start += maplen;
-		len -= maplen;
+			offset = find_next_zero_bit_le(data, maplimit, next + 1);
+			/* Remove after tested on arm. (next + 1 can
+			 * be greater than maplimit) */
+			assert(offset <= maplimit);
+		} while (offset != maplimit);
 
+		assert(start + chunk == mapbase + maplimit);
+		start += chunk;
+		range -= chunk;
 		blockput(buffer);
 	}
 
-	if ((flags & BALLOC_PARTIAL) && seg[0].count) {
-		tux3_dbg("partial blocks %u, block %llu, count %u",
-			 blocks, seg[0].block, seg[0].count);
-		found = seg[0].block;
-		blocks = seg[0].count;
-		goto found_partial;
-	}
-
-	return -ENOSPC;
+	return 0;
+}
 
-found_range:
-	/* Found free blocks within one block? */
-	if ((found >> mapshift) == mapblock) {
-		unsigned foundoffset = found & mapmask;
-		int err;
+/*
+ * Allocate block segments from entire volume.  Wrap to bottom of
+ * volume if needed.
+ *
+ * return value:
+ * < 0 - error
+ *   0 - succeed to allocate blocks, at least >= 1
+ */
+int balloc_find(struct sb *sb,
+	struct block_segment *seg, int maxsegs, int *segs,
+	unsigned *blocks)
+{
+	block_t goal = sb->nextblock, volsize = sb->volblocks;
+	int err, newsegs = 0;
 
-		err = bitmap_modify_bits(sb, buffer, foundoffset, blocks, 1);
-		if (err) {
-			blockput(buffer);
-			/* FIXME: error handling */
-			return err;
-		}
-	} else {
-		int err;
+	err = balloc_find_range(sb, seg, maxsegs, &newsegs, goal,
+				volsize - goal, blocks);
+	trace("=> try0: segs = %d, blocks = %u", newsegs, *blocks);
+	if (err)
+		return err;
 
-		blockput(buffer);
-found_partial:
-		err = bitmap_modify(sb, found, blocks, 1);
-		if (err)
+	if (*blocks && newsegs < maxsegs) {
+		err = balloc_find_range(sb, seg, maxsegs, &newsegs, 0, goal,
+					blocks);
+		trace("=> try1: segs = %d, blocks = %u", newsegs, *blocks);
+		if (err < 0)
 			return err;
 	}
 
-	seg->block = found;
-	seg->count = blocks;
-
-	sb->nextblock = found + blocks;
-	if (sb->nextblock >= sb->volblocks)
-		sb->nextblock = 0;
-	//set_sb_dirty(sb);
+	if (!newsegs) {
+		/* FIXME: This is for debugging. Remove this */
+		tux3_warn(sb, "couldn't balloc: blocks %u, freeblocks %Lu",
+			  *blocks, sb->freeblocks);
+		return -ENOSPC;
+	}
 
-	trace("balloc extent [block %Lx, count %x]", found, blocks);
+	*segs = newsegs;
 
 	return 0;
 }
 
-static int __balloc(struct sb *sb, unsigned blocks, unsigned flags,
-		    struct block_segment *seg, int segs)
+int balloc_use(struct sb *sb, struct block_segment *seg, int segs)
 {
-	block_t goal = sb->nextblock;
-	int err;
+	block_t goal;
+	int i;
 
-	/* For now, allow partial unconditionally */
-	err = balloc_from_range(sb, goal, sb->volblocks, blocks, flags,
-				seg, segs);
-	if (err == -ENOSPC) {
-		/* FIXME: This is for debugging. Remove this */
-		tux3_warn(sb, "couldn't balloc: blocks %u, freeblocks %Lu",
-			  blocks, sb->freeblocks);
+	assert(segs > 0);
+
+	for (i = 0; i < segs; i++) {
+		/* FIXME: error handling */
+		int err = bitmap_modify(sb, seg[i].block, seg[i].count, 1);
+		if (err)
+			return err;
 	}
 
-	return err;
+	goal = seg[segs - 1].block + seg[segs - 1].count;
+	sb->nextblock = goal == sb->volblocks ? 0 : goal;
+
+	return 0;
 }
 
-int balloc(struct sb *sb, unsigned blocks, struct block_segment *seg, int segs)
+int balloc_segs(struct sb *sb,
+	struct block_segment *seg, int maxsegs, int *segs,
+	unsigned *blocks)
 {
-	return __balloc(sb, blocks, 0, seg, segs);
+	int err = balloc_find(sb, seg, maxsegs, segs, blocks);
+	if (!err)
+		err = balloc_use(sb, seg, *segs);
+	return err;
 }
 
-int balloc_partial(struct sb *sb, unsigned blocks,
-		   struct block_segment *seg, int segs)
+block_t balloc_one(struct sb *sb)
 {
-	return __balloc(sb, blocks, BALLOC_PARTIAL, seg, segs);
+	struct block_segment seg;
+	unsigned blocks = 1;
+	int err, segs;
+
+	err = balloc_segs(sb, &seg, 1, &segs, &blocks);
+	if (err)
+		return err;
+	assert(segs == 1 && blocks == 0 && seg.count == 1);
+	return seg.block;
 }
 
 int bfree(struct sb *sb, block_t start, unsigned blocks)
 {
 	assert(tux3_under_backend(sb));
-	trace("bfree extent [block %Lx, count %x], ", start, blocks);
+	trace("bfree extent [%Lu+%u], ", start, blocks);
 	return bitmap_test_and_modify(sb, start, blocks, 0);
 }
 
+int bfree_segs(struct sb *sb, struct block_segment *seg, int segs)
+{
+	int i;
+	for (i = 0; i < segs; i++) {
+		/* FIXME: error handling */
+		int err = bfree(sb, seg[i].block, seg[i].count);
+		if (err)
+			return err;
+	}
+	return 0;
+}
+
 int replay_update_bitmap(struct replay *rp, block_t start, unsigned blocks,
 			 int set)
 {
diff --git a/fs/tux3/btree.c b/fs/tux3/btree.c
index 04d06554b5eb8d..16d602ab457130 100644
--- a/fs/tux3/btree.c
+++ b/fs/tux3/btree.c
@@ -52,12 +52,12 @@ static inline unsigned bcount(struct bnode *node)
 
 static struct buffer_head *new_block(struct btree *btree)
 {
-	struct block_segment seg;
+	block_t block;
 
-	int err = btree->ops->balloc(btree->sb, 1, &seg, 1);
-	if (err)
-		return ERR_PTR(err);
-	struct buffer_head *buffer = vol_getblk(btree->sb, seg.block);
+	block = balloc_one(btree->sb);
+	if (block < 0)
+		return ERR_PTR(block);
+	struct buffer_head *buffer = vol_getblk(btree->sb, block);
 	if (!buffer)
 		return ERR_PTR(-ENOMEM); // ERR_PTR me!!! and bfree?
 	return buffer;
@@ -1278,7 +1278,7 @@ int alloc_empty_btree(struct btree *btree)
 	return 0;
 
 error_leafbuf:
-	(btree->ops->bfree)(sb, bufindex(rootbuf), 1);
+	bfree(sb, bufindex(rootbuf), 1);
 	blockput(rootbuf);
 	rootbuf = leafbuf;
 error:
diff --git a/fs/tux3/dleaf.c b/fs/tux3/dleaf.c
index 48eb1b9411580d..5b4a5edc5cc289 100644
--- a/fs/tux3/dleaf.c
+++ b/fs/tux3/dleaf.c
@@ -878,8 +878,6 @@ struct btree_ops dtree1_ops = {
 //	.leaf_resize	= dleaf_resize,
 	.leaf_chop	= dleaf_chop,
 	.leaf_merge	= dleaf_merge,
-	.balloc		= balloc,
-	.bfree		= bfree,
 
 	.leaf_sniff	= dleaf_sniff,
 	.leaf_can_free	= dleaf_can_free,
diff --git a/fs/tux3/dleaf2.c b/fs/tux3/dleaf2.c
index d3163a3dd22e6c..af2fdbd4ab5bc8 100644
--- a/fs/tux3/dleaf2.c
+++ b/fs/tux3/dleaf2.c
@@ -838,8 +838,6 @@ struct btree_ops dtree2_ops = {
 	.leaf_pre_write	= dleaf2_pre_write,
 	.leaf_write	= dleaf2_write,
 	.leaf_read	= dleaf2_read,
-	.balloc		= balloc,
-	.bfree		= bfree,
 
 	.leaf_sniff	= dleaf2_sniff,
 	.leaf_can_free	= dleaf2_can_free,
diff --git a/fs/tux3/filemap.c b/fs/tux3/filemap.c
index cd81980d2fbb64..73d9db42e62cb1 100644
--- a/fs/tux3/filemap.c
+++ b/fs/tux3/filemap.c
@@ -226,11 +226,17 @@ static int map_region1(struct inode *inode, block_t start, unsigned count,
 		seg[0].state = BLOCK_SEG_HOLE;
 	}
 	for (int i = 0; i < segs; i++) {
+		int newsegs;
 		if (seg[i].state != BLOCK_SEG_HOLE)
 			continue;
 
 		count = seg[i].count;
-		if ((err = balloc(sb, count, &seg[i], 1))) { // goal ???
+		err = balloc_segs(sb, &seg[i], 1, &newsegs, &count);
+		if (!err && count != 0) {
+			/* FIXME: should handle partial allocation */
+			err = -ENOSPC;
+		}
+		if (err) {
 			/*
 			 * Out of space on file data allocation.  It happens.  Tread
 			 * carefully.  We have not stored anything in the btree yet,
@@ -365,7 +371,8 @@ static int seg_find(struct btree *btree, struct dleaf_req *rq,
 {
 	struct sb *sb = btree->sb;
 	struct block_segment *seg, *limit;
-	int seg_state, len = seg_len;
+	unsigned len = seg_len;
+	int seg_state;
 	int err = 0;
 
 	assert(rq->seg_idx == rq->seg_cnt);
@@ -376,8 +383,9 @@ static int seg_find(struct btree *btree, struct dleaf_req *rq,
 	limit = min(rq->seg + rq->seg_idx + space, rq->seg + rq->seg_max);
 	for (seg = rq->seg + rq->seg_idx; seg < limit && len; seg++) {
 		struct block_segment tmp;
+		int segs;
 
-		err = balloc_partial(sb, len, &tmp, 1);
+		err = balloc_segs(sb, &tmp, 1, &segs, &len);
 		if (err) {
 			assert(err != -ENOSPC);	/* frontend reservation bug */
 			rq->seg_cnt = rq->seg_idx;
@@ -387,8 +395,6 @@ static int seg_find(struct btree *btree, struct dleaf_req *rq,
 		seg->block = tmp.block;
 		seg->count = tmp.count;
 		seg->state = seg_state;
-
-		len -= tmp.count;
 	}
 	if (err) {
 		struct block_segment *p;
diff --git a/fs/tux3/ileaf.c b/fs/tux3/ileaf.c
index a3c747c26816de..c12d4de3879a52 100644
--- a/fs/tux3/ileaf.c
+++ b/fs/tux3/ileaf.c
@@ -478,7 +478,6 @@ struct btree_ops itree_ops = {
 	.leaf_pre_write	= noop_pre_write,
 	.leaf_write	= ileaf_write,
 	.leaf_read	= ileaf_read,
-	.balloc		= balloc,
 	.private_ops	= &iattr_ops,
 
 	.leaf_sniff	= ileaf_sniff,
@@ -495,7 +494,6 @@ struct btree_ops otree_ops = {
 	.leaf_pre_write	= noop_pre_write,
 	.leaf_write	= ileaf_write,
 	.leaf_read	= ileaf_read,
-	.balloc		= balloc,
 	.private_ops	= &oattr_ops,
 
 	.leaf_sniff	= ileaf_sniff,
diff --git a/fs/tux3/log.c b/fs/tux3/log.c
index d60ccb40b1f9de..7cecc8f92ddf66 100644
--- a/fs/tux3/log.c
+++ b/fs/tux3/log.c
@@ -173,9 +173,9 @@ int tux3_logmap_io(int rw, struct bufvec *bufvec)
 		struct buffer_head *buffer;
 		struct block_segment seg;
 		block_t block, limit;
-		int err;
+		int err, segs;
 
-		err = balloc_partial(sb, count, &seg, 1);
+		err = balloc_segs(sb, &seg, 1, &segs, &count);
 		if (err) {
 			assert(err);
 			return err;
@@ -218,8 +218,6 @@ int tux3_logmap_io(int rw, struct bufvec *bufvec)
 
 		/* Add count of log on this delta to unify logcount */
 		be32_add_cpu(&sb->super.logcount, seg.count);
-
-		count -= seg.count;
 	}
 
 	return 0;
diff --git a/fs/tux3/tux3.h b/fs/tux3/tux3.h
index c073f3b9050571..4161f8d25f445c 100644
--- a/fs/tux3/tux3.h
+++ b/fs/tux3/tux3.h
@@ -576,8 +576,6 @@ struct btree_ops {
 	/* return value: < 0 - error, 0 >= - btree_result */
 	int (*leaf_write)(struct btree *btree, tuxkey_t key_bottom, tuxkey_t key_limit, void *leaf, struct btree_key_range *key, tuxkey_t *split_hint);
 	int (*leaf_read)(struct btree *btree, tuxkey_t key_bottom, tuxkey_t key_limit, void *leaf, struct btree_key_range *key);
-	int (*balloc)(struct sb *sb, unsigned blocks, struct block_segment *seg, int segs);
-	int (*bfree)(struct sb *sb, block_t block, unsigned blocks);
 
 	void *private_ops;
 
@@ -698,12 +696,18 @@ struct buffer_head *blockget(struct address_space *mapping, block_t iblock);
 
 /* balloc.c */
 block_t bitmap_dump(struct inode *inode, block_t start, block_t count);
-int balloc_from_range(struct sb *sb, block_t start, block_t count,
-		      unsigned blocks, unsigned flags,
-		      struct block_segment *seg, int segs);
-int balloc(struct sb *sb, unsigned blocks, struct block_segment *seg, int segs);
-int balloc_partial(struct sb *sb, unsigned blocks,
-		   struct block_segment *seg, int segs);
+int balloc_find_range(struct sb *sb,
+	struct block_segment *seg, int maxsegs, int *segs,
+	block_t start, block_t range, unsigned *blocks);
+int balloc_find(struct sb *sb,
+	struct block_segment *seg, int maxsegs, int *segs,
+	unsigned *blocks);
+int balloc_use(struct sb *sb, struct block_segment *seg, int segs);
+int balloc_segs(struct sb *sb,
+	struct block_segment *seg, int maxsegs, int *segs,
+	unsigned *blocks);
+block_t balloc_one(struct sb *sb);
+int bfree_segs(struct sb *sb, struct block_segment *seg, int segs);
 int bfree(struct sb *sb, block_t start, unsigned blocks);
 int replay_update_bitmap(struct replay *rp, block_t start, unsigned blocks, int set);