Re: Newbie questions about DIR_ITEM and DIR_INDEX design

[Mark Harmstone <mark@harmstone.com>]

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