[Tux3] Another modest code drop

[Shapor Naghibzadeh]

On Wed, Jul 30, 2008 at 9:46 PM, Daniel Phillips <phillips at phunq.net> wrote:
> The split.c code is now generally better, and actually runs the test
> case correctly, which the previous version did not.
>
> Turning the groups vector upside down like the entries vector made
> things considerably more regular.  The leaf_insert function is now
> pretty readable, which is something of an achievement given all the
> corner case in it.
>
>   http://tux3.org/tux3?f=35d77cb24c1f;file=test/leaf.c
>
> One neat thing about this insert is, there is only one memmove on
> the fast path, and that one usually moves zero bytes.  Otherwise as
> can be seen, the fast path is very fast.

>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.

Shapor
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test.patch
Type: application/octet-stream
Size: 638 bytes
Desc: not available
URL: <http://phunq.net/pipermail/tux3/attachments/20080802/27a31d48/attachment.obj>