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

Daniel Phillips
2001-02-22T07:29:47Z

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