[Tux3] A modest code drop

[Daniel Phillips]

Hi,

A new file has landed in the test directory: file index btree leaf
operations along the lines of my earlier description, implementing a
compressed two level indexing scheme within a leaf in order to hold the
overhead of indexing down to around 4 bytes per distinct 48 bit logical
address.  For an unversioned file where there is just one extent per
logical address this requires about 12 bytes per extent including
indexing.  For a heavily versioned file with many different versioned
extents per logical address, the leaf space per extent approaches 8
bytes.  Each extent can address 2**6 blocks or 256K of storage, giving
a metadata to data ratio of 2**15, or 32K to one.  So I am beginning to
deliver on my promise of highly compressed metadata.

The indexing scheme is slightly complex with its chopped up fields,
boundary conditions due to not storing sentinels, two level structure
and reversed table format to optimize for the linear writing case,
however the code is not bulky and is very efficient.  The lookup
algorithm in particular is not much more code than a simple linear
search.

The split and merge operations are not done yet, or the delete.  The
test harness falls short of a proper fuzz test.  This code really does
require a random test methodology to harden it up, like the version.c
code, which also has a lot of subtle boundary conditions.  There is
a simple "hand made" test in leaf.c that sets up some basic leaf
contents, runs a few insert operations, then does some lookups.  This
demonstrates that the format is not so complex that a simple human
being cannot deal with it.

I am sure there still a couple of bugs lurking.

  http://tux3.org/tux3?fd=25972ee30667;file=test/leaf.c
  c99 leaf.c && ./a.out

Regards,

Daniel

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