[Tux3] Another modest code drop

[Daniel Phillips]

On Saturday 02 August 2008 06:15, Shapor Naghibzadeh wrote:
> From leaf.c:
> 
> 32  * The top level index is a table of groups of entries all having the same
> 33  * high 24 bits of logical address which is only stored once, along with the
> 34  * 8 bit count of entries in the group.  Since there can be more than 256
> 35  * entries at the same logical address, there could be more than one group
> 36  * with the same logical address (not handled yet, which limits the number of
> 37  * different versions in the leaf to 256).
> 
> I might be missing something here, but it looks like its worse than
> that.  Since you don't handle more than one group with the same loghi,
> if a group has more than 255 entries, the count simply loops and you
> start corrupting the leaf.  The attached test illustrates the issue.

You did not miss anything, I did.  I just can't be quite that lazy, and
in the process we will remove that 255 version limitation.  Here is a
partial fix which is just to start a new group not only when loghi is
different, but when the groups count hits 255.  This additional split
criterion fails to preserve the partitioning of logical addresses
between the two groups so that all the members of one group are below
a given address and all the members of the other are above.  This can
be corrected by partitioning the members at group split time for the
overflow case.

-	if (group == grbase || loghi < group->loghi) {
+	if (group == grbase || loghi < group->loghi || group->count == 255) {

Anybody want to take a run at that?  It is admittedly pretty tricky
code to work on, but this is not harder than the stuff that already
works.

Merge can also violate the groups count limit, so an additional check
is needed there too.  But this case is simpler because no there is no
"unpartitioning" to do.

Regards,

Daniel

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