Tux3 filesystem interest ()

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

# 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  */

(Continue reading)

headers

Daniel Phillips | 3 Aug 13:13

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

On Saturday 02 August 2008 23:44, Shapor Naghibzadeh wrote:
> # HG changeset patch
> # User shapor <at> yzf.shapor.com
> # Date 1217745661 25200
> # Node ID 2c679288390fb11949fa30625be33b257db9ba02
> # Parent  e0d569213df6ba1ed4e8d2029b8de596f71403ca
> Fix entry table overflow (by splitting groups).

Incorporated in a heavily modified form.  Thanks a lot for the analysis
the correct fix.  Note that one more thing had to be done: after
splitting a group the new entry can be destined for either group, so a
check is needed followed by advancing to the next group if necessary.

The lookup function now needs to be fixed to handle multiple groups
with the same loghi logical address bits.  Merge can violate the count
rule, so that needs to be fixed.

The code got longer and scarier looking, but efficiency stayed about
the same.  Is all this fiddling around really worth it just to squeeze
33% more entries into a leaf?  Yes, I think so.

Regards,

Daniel

headers

Shapor Naghibzadeh | 3 Aug 19:19

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

On Sun, Aug 3, 2008 at 4:13 AM, Daniel Phillips <phillips <at> phunq.net> wrote:

> Incorporated in a heavily modified form.  Thanks a lot for the analysis
> the correct fix.  Note that one more thing had to be done: after
> splitting a group the new entry can be destined for either group, so a
> check is needed followed by advancing to the next group if necessary.

Heavily modified to the point of not working, unfortunately.  :)

232         if (group == grbase || loghi < group->loghi || (entries -
group->count)->limit == grouplim) {
233                 int split = group != grbase && group->count == grouplim;

Oops, you only set split = 1 if we have the pathological case of one
extent per entry (this passed due to the poor test case).  My patch
has a better test case in it.

Later on you also assume you are splitting only groups with 255
entries causing more brokenness outside of the one-extent-per-entry
case.

You are right though, I forgot to advance to the next group if necessary.

Shapor

headers

Daniel Phillips | 3 Aug 23:09

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

On Sunday 03 August 2008 10:19, Shapor Naghibzadeh wrote:
> Heavily modified to the point of not working, unfortunately.  :)

That'll teach me 

> You are right though, I forgot to advance to the next group if necessary.

Ah perfection, she is elusive.

Daniel