[Tux3] [PATCH] Fix entry table overflow (by splitting groups)

[Shapor Naghibzadeh]

# HG changeset patch
# User shapor at yzf.shapor.com
# Date 1217745661 25200
# Node ID 2c679288390fb11949fa30625be33b257db9ba02
# Parent  e0d569213df6ba1ed4e8d2029b8de596f71403ca
Fix entry table overflow (by splitting groups).
Add ENOSPC check for leaf.

diff -r e0d569213df6 -r 2c679288390f test/fleaf.c
--- a/test/fleaf.c	Sat Aug 02 13:52:11 2008 -0700
+++ b/test/fleaf.c	Sat Aug 02 23:41:01 2008 -0700
@@ -199,18 +199,20 @@ int leaf_insert(struct leaf *leaf, block
 	unsigned loglo = target & 0xffffff, loghi = target >> 24;
 	void *used = leaf->used + (void *)leaf;
 	// need room for one extent + maybe one group + maybe one entry
+	if (leaf_free(leaf) < sizeof(struct extent) + sizeof(struct group) + sizeof(struct entry))
+		return -1;
 
 	/* find group position */
 	struct group *group;
 	for (group = groups; group > grbase; group--) {
-		if (loghi <= group->loghi)
+		if (loghi < group->loghi || loghi == group->loghi && (group - 1 <= grbase || loghi != (group - 1)->loghi || loglo <= (entries - group->count)->loglo))
 			break;
 		extents += (entries - group->count)->limit;
 		entries -= group->count;
 	}
 
-	/* insert new group if no match  */
-	if (group == grbase || loghi < group->loghi || group->count == 255) {
+	/* insert new group if no match or split is required */
+	if (group == grbase || loghi < group->loghi || (entries - group->count)->limit == 255) {
 		printf("new group at %i\n", group - grbase);
 		memmove(used - sizeof(*group), used, (void *)(group + 1) - used);
 		*group = (struct group){ .loghi = loghi, .count = 0 };
@@ -218,6 +220,16 @@ int leaf_insert(struct leaf *leaf, block
 		grbase--;
 		entries--;
 		leaf->groups++;
+	}
+
+	/* split the group if its out of space */
+	if ((entries - (group - 1)->count)->limit == 255) {
+		group->count = (group - 1)->count / 2;
+		struct entry *ep = entries - 1 - group->count;
+		int remove = (ep + 1)->limit;
+		while (ep > entries - 1 - (group - 1)->count)
+			(ep--)->limit -= remove;
+		(group - 1)->count -= group->count;
 	}
 
 	/* find entry position */
@@ -367,9 +379,12 @@ int main(int argc, char *argv[])
 	printf("--- leaf test ---\n");
 	unsigned hi = 1 << 24, hi2 = 3 * hi;
 	unsigned targets[] = { 0x11, 0x33, 0x22, hi2 + 0x44, hi2 + 0x55, hi2 + 0x44, hi + 0x33, hi + 0x44, hi + 0x99 }, next = 0;
-	for (int i = 0; i < 260;i++)
-		leaf_insert(leaf, i << 13, (struct extent){ .block = i });
-	leaf_dump(leaf);
+	for (int j = 0; j < 2; j++) {
+		for (int i = 0; i < 130; i++)
+			for (int k = 0; k < 3; k++)
+				leaf_insert(leaf, (i * 2 + j) << 13, (struct extent){ .block = i, .version = k });
+		leaf_dump(leaf);
+	}
 	leaf_insert(leaf, targets[next++], (struct extent){ .block = 0x111 });
 	leaf_insert(leaf, targets[next++], (struct extent){ .block = 0x222 });
 	leaf_insert(leaf, targets[next++], (struct extent){ .block = 0x333 });

_______________________________________________
Tux3 mailing list
Tux3 at tux3.org
http://tux3.org/cgi-bin/mailman/listinfo/tux3