Newbie questions about DIR_ITEM and DIR_INDEX design
Hello btrfs developers
I am a beginner studying the implementation of btrfs. While examining the structures of DIR_ITEM and DIR_INDEX, I noticed that both store similar content but differ in their offset values. This led me to two questions:
1. The offset field in DIR_ITEM is computed as a CRC32 hash of the filename. In practice, is there a risk of hash collisions? If so, how does the current implementation handle such collisions?
2. The offset field in DIR_INDEX appears to be an auto-incrementing number, possibly indicating the creation order of entries within a directory. Why is this necessary, given that DIR_ITEM already exists?
I would greatly appreciate any insights or references to relevant documentation or code snippets to help me understand these design choices.
Thank you for your time and guidance.
Best regards,
Sun YangKai
Hi Sun,
Quoted 9 lines · Sun YangKai
Hello btrfs developers
I am a beginner studying the implementation of btrfs. While examining the structures of
DIR_ITEMandDIR_INDEX, I noticed that both store similar content but differ in their offset values. This led me to two questions:1. The offset field in
DIR_ITEMis computed as a CRC32 hash of the filename. In practice, is there a risk of hash collisions? If so, how does the current implementation handle such collisions?
I think the mathematics is something like for a hash of n bits, you need approximately 2^(n/2) instances for a 50% chance of a collision. So 65,536 filenames in this case.
If we have a collision, we append a second DIR_ITEM after the first, in the same slot. So it'd only be an issue if you could generate enough hash collisions to fill a 16KB leaf, but I think coming up with such a list would be difficult enough in itself.
The collisions in /usr/share/dict/words, if you want to play around with this yourself:
dolent, Tang
dunghill, fricatrice
accusable, aggrandizement
acarodermatitis, unfallacious
hydrotical, hylomorphist
gratillity, radiobserver
creophagist, machinability
boomdas, Loxiinae
Quoted 3 lines
2. The offset field in
DIR_INDEXappears to be an auto-incrementing number, possibly indicating the creation order of entries within a directory. Why is this necessary, given thatDIR_ITEMalready exists?
Well, the collisions are one reason: each dentry is a directory has to have a unique d_off value. I wouldn't be surprised if it also simplifies the implementation of readdir.
Mark
Quoted 7 lines
I would greatly appreciate any insights or references to relevant documentation or code snippets to help me understand these design choices.
Thank you for your time and guidance.
Best regards,
Sun YangKai
Hi Mark,
Thank you so much for your incredibly helpful, detailed, and patient response. It’s greatly appreciated and has significantly improved my understanding of btrfs design choices.
Best regards,
Sun YangKai
Quoted 8 lines · Sun YangKai
Hi Mark,
Thank you so much for your incredibly helpful, detailed, and patient response. It’s greatly appreciated and has significantly improved my understanding of btrfs design choices.
Best regards,
Sun YangKai
No worries.
It looks like another factor was the fact that the original version of getdents() returned a 32-bit d_off on 32-bit systems - which is okay for a monotonic counter within a directory, but no good if you want to avoid the birthday paradox.
So if you were designing Btrfs from scratch today, you might choose just to have DIR_ITEM, change its hash length to 64 bits, and disallow hash collisions completely.
Mark
Quoted 10 lines
No worries.
It looks like another factor was the fact that the original version of
getdents()returned a 32-bitd_offon 32-bit systems - which is okay for a monotonic counter within a directory, but no good if you want to avoid the birthday paradox.So if you were designing Btrfs from scratch today, you might choose just to have
DIR_ITEM, change its hash length to 64 bits, and disallow hash collisions completely.
This is exactly what I'm thinking. I came up to this because I have a quite large dir whose size is about 66M on my machine. It works well, but with both DIR_ITEM and DIR_INDEX, the size is doubled.
Quoted 2 lines
Mark
Thanks,
Sun Yangkai