XFS directory entries sort order
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!
Signature · 2 lines
Mihai RUSU Email: [email protected] "Linux is obsolete" -- AST
Quoted 7 lines · dizzy
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*.ccode 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
Quoted 6 lines · Andi Kleen
Quoted 4 lines · dizzy
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)?
Quoted 8 lines
Quoted 3 lines
I am trying to figure it out by reading
linux/fs/xfs/xfs_dir2*.ccode 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.
Quoted 6 lines
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.
Quoted 4 lines
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
Quoted 7 lines · Andi Kleen
Quoted 4 lines
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.