XFS directory entries sort order

XFS directory entries sort order

[dizzy]

Hello

Can someone tell me (in English or C :) ) the algorithm of the sorting order 
of the entries in an XFS directory as I would get them with a readdir() (or 
shell "find" command)?

I am trying to figure it out by reading linux/fs/xfs/xfs_dir2*.c code but I 
don't seem to be doing much progress and I was hoping maybe someone that 
knows these details can help.

Thank you!

-- 
Mihai RUSU					Email: dizzy@roedu.net
			"Linux is obsolete" -- AST

Re: XFS directory entries sort order

[Andi Kleen]

dizzy <dizzy@roedu.net> writes:

> Can someone tell me (in English or C :) ) the algorithm of the sorting order 
> of the entries in an XFS directory as I would get them with a readdir() (or 
> shell "find" command)?
>
> I am trying to figure it out by reading linux/fs/xfs/xfs_dir2*.c code but I 
> don't seem to be doing much progress and I was hoping maybe someone that 
> knows these details can help.

I believe it computes a hash over the name and then sorts by the hash
numerical value. At least the b*tree large directories do, small inline
directories might be different (XFS uses different algorithms for
different directory sizes)

The hash function is in xfs_da_btree.c:xfs_da_hashname()

With the recent case insensitive support there are also differences
on the file systems which have that enabled.

Also better don't rely on it never changing.

-Andi

Re: XFS directory entries sort order

[Barry Naujok]

On Wed, 11 Jun 2008 03:20:00 +1000, Andi Kleen <andi@firstfloor.org> wrote:

> dizzy <dizzy@roedu.net> writes:
>
>> Can someone tell me (in English or C :) ) the algorithm of the sorting  
>> order
>> of the entries in an XFS directory as I would get them with a readdir()  
>> (or
>> shell "find" command)?
>>
>> I am trying to figure it out by reading linux/fs/xfs/xfs_dir2*.c code  
>> but I
>> don't seem to be doing much progress and I was hoping maybe someone that
>> knows these details can help.
>
> I believe it computes a hash over the name and then sorts by the hash
> numerical value. At least the b*tree large directories do, small inline
> directories might be different (XFS uses different algorithms for
> different directory sizes)

readdir order is not dependant on the hashes. The order depends on the
order of files being created, unlinked and the length of the filenames
being unlinked/created.

> The hash function is in xfs_da_btree.c:xfs_da_hashname()
>
> With the recent case insensitive support there are also differences
> on the file systems which have that enabled.
>
> Also better don't rely on it never changing.

Yes :)

Barry.

Re: XFS directory entries sort order

[Andi Kleen]

> readdir order is not dependant on the hashes. The order depends on the
> order of files being created, unlinked and the length of the filenames
> being unlinked/created.

Thanks for the correction. It's a long time that I read that source
so it probably got confused with some other fs.

-Andi

Re: XFS directory entries sort order

[Barry Naujok]

On Wed, 11 Jun 2008 09:58:57 +1000, Andi Kleen <andi@firstfloor.org> wrote:

>
>> readdir order is not dependant on the hashes. The order depends on the
>> order of files being created, unlinked and the length of the filenames
>> being unlinked/created.
>
> Thanks for the correction. It's a long time that I read that source
> so it probably got confused with some other fs.

If I read the code correctly, in node-form directories, it will try and
use the same data block that other names with the same hash are located in.

Barry.