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] [day] [month] [year] [list]

Message-ID: <AANLkTikQksGJqFlZPUw0aZ87JyYh8w-DedfXyzCNvb9S@mail.gmail.com>
Date:	Mon, 7 Jun 2010 18:10:24 +0400
From:	Evgeniy Ivanov <lolkaantimat@...il.com>
To:	tytso@....edu
Cc:	linux-ext4@...r.kernel.org
Subject: Re: ext2 and directory indexing

On Mon, Jun 7, 2010 at 4:56 PM,  <tytso@....edu> wrote:
> 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".

Thank you for explanation. I've looked into the code and it only
resets EXT2_BTREE_FL and that's all. Thus ext2 doesn't support
indexing, right? Unlike in ext2, in ext3 I see that you set/reset this
flag, check the feature, work with hashes.

>> 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.  :-)

Oh, I followed :) It works fine now (the only confusing thing was
dir_index set by default for ext2 and converting directories).
I'm just wondering about what is ext2 and what is ext3.

>  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?

It's for MINIX 3. There is working and tested ext2 server already, now
only Orlov block allocator and preallocation left. Probably directory
indexing depending on your answer, but ext3 is in the project's TODO
list anyway.


-- 
Evgeniy Ivanov
--
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