Re: ext2 and directory indexing

[tytso@mit.edu]

On Sun, Jun 06, 2010 at 03:29:56PM +0400, Evgeniy Ivanov wrote:
> Hello,
> 
> I'm a bit confused by indexing and ext2. It looks like there is no
> hash code in ext2, but ext2_fs.h has EXT2_INDEX_FL (most confusing),
> EXT2_FEATURE_COMPAT_DIR_INDEX and some other HTree things, but
> EXT2_INDEX_FL and EXT2_FEATURE_COMPAT_DIR_INDEX  are not used
> anywhere.

It's there, but in ext2 it was called EXT2_BTREE_FL (same bit
position, different name), since we originally planned to implement it
using a BTREE.  We ultimately implemented directory indexing by
storing the tree information inside what looks like deleted directory
entries to ext2, but since we don't rebalance the trees on deletion,
they're technically not b-trees.  We also hash the keys before storing
them in the tree, which is why you'll sometimes see references to
"hash tree", or "htree".

> I have ext2 partition created with mkfs.ext2 and when I check this
> partition e2fsck converts some directories to the indexed format and
> sets EXT2_INDEX_FL/EXT3_INDEX_FL. But since I failed grep any usage of
> EXT2_INDEX_FL in fs/ext2 that code doesn't reset EXT2_INDEX_FL (some
> time ago I was suggested to make my ext2 implementation to reset this
> flag which looks correct for ext3, but not ext2). Is it expected
> behavior of e2fsck?

Yes, it's expected.  The fact that e2fsck is complaining and
converting directories back to be indexed is because you didn't follow
my advice.  :-)  Sorry for the EXT2_INDEX_FL vs. EXT2_BTREE_FL
confusion; it's something that I suppose we should clean up, but my
advice would have prevented e2fsck from complaining about corrupted
directory and re-indexing the directories.

I'm curious BTW --- for what operating system are you implementing
this ext2 implementation?

					- Ted