Skip to contentSkip to conversation

Newbie questions about DIR_ITEM and DIR_INDEX design

DISCUSSION Sun YangKai 2 participants 5 messages Aug 20, 2025 – Aug 21, 2025 Btrfs file system

lore
Share & tools
lore
#0 lore raw

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

#1 lore raw

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

Quoted 3 lines

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

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

#2 lore raw

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

#3 lore raw
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

#4 lore raw
Quoted 10 lines

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.

Quoted 2 lines

Mark

Thanks,
Sun Yangkai