Re: [Ext2-devel] [rfc] Near-constant time directory index for Ext2

[Daniel Phillips <phillips@innominate.de>]

On Thu, 22 Feb 2001, tytso@valinux.com wrote:
> A couple of comments.  If you make the beginning of each index block
> look like a an empty directory block (i.e, the first 8 blocks look like
> this):
> 
> 	32 bits: ino == 0
> 	16 bits: rec_len == blocksize
> 	16 bits: name_len = 0
> 
> ... then you will have full backwards compatibility, both for reading
> *and* writing.  When reading, old kernels will simply ignore the index
> blocks, since it looks like it has an unpopulated directory entry.  And
> if the kernel attempts to write into the directory, it will clear the
> BTREE_FL flag, in which case new kernels won't treat the directory as a
> tree anymore.  (Running a smart e2fsck which knows about directory trees
> will be able to restore the tree structure).

:-)  That's really nice, now I see what you were thinking about with
all those bit clears.

> Is it worth it?  Well, it means you lose an index entry from each
> directory block, thus reducing your fanout at each node of the tree by a
> worse case of 0.7% in the worst case (1k blocksize) and 0.2% if you're
> using 4k blocksizes.

I'll leave that up to somebody else - we now have two alternatives, the
100%, no-compromise INCOMPAT solution, and the slightly-bruised but
still largely intact forward compatible solution.  I'll maintain both
solutions for now code so it's just as easy to choose either in the end.

-- 
Daniel