Newbie questions about DIR_ITEM and DIR_INDEX design

Newbie questions about DIR_ITEM and DIR_INDEX design

[Sun YangKai]

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

Re: Newbie questions about DIR_ITEM and DIR_INDEX design

[Mark Harmstone]

Hi Sun,

On 20/08/2025 2.59 pm, Sun YangKai wrote:
> 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?

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

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

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

> 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

Re: Newbie questions about DIR_ITEM and DIR_INDEX design

[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

Re: Newbie questions about DIR_ITEM and DIR_INDEX design

[Mark Harmstone]

On 21/08/2025 9.26 am, Sun YangKai wrote:
> 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

Re: Newbie questions about DIR_ITEM and DIR_INDEX design

[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.
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.
> 
> Mark

Thanks,
Sun Yangkai