linux-ext4 - Re: ext2 and directory indexing

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20100607125634.GB13440@thunk.org>
Date:	Mon, 7 Jun 2010 08:56:34 -0400
From:	tytso@....edu
To:	Evgeniy Ivanov <lolkaantimat@...il.com>
Cc:	linux-ext4@...r.kernel.org
Subject: Re: ext2 and directory indexing

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
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html