ext2 and directory indexing

ext2 and directory indexing

[Evgeniy Ivanov]

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.
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?
Does ext2 have directory indexing support (should my implementation of
ext2 do that)?


-- 
Evgeniy Ivanov

Re: ext2 and directory indexing

[Evgeniy Ivanov]

On Sun, Jun 6, 2010 at 3:29 PM, Evgeniy Ivanov <lolkaantimat@gmail.com> 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.
> 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?
> Does ext2 have directory indexing support (should my implementation of
> ext2 do that)?
>

It looks like partitions formatted with mkfs.ext2 have dir_index flag
set. It's the reason why e2fsck sets EXT2_INDEX_FL. Is it ok, that
mkfs.ext2 sets this flag (it manly depends on answer on previous
question).



-- 
Evgeniy Ivanov
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: ext2 and directory indexing

[tytso]

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

Re: ext2 and directory indexing

[Evgeniy Ivanov]

On Mon, Jun 7, 2010 at 4:56 PM,  <tytso@mit.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@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html