Btrfs Back References

Back references have three main goals:

• Differentiate between all holders of references to an extent so that when a reference is dropped we can make sure it was a valid reference before freeing the extent.
• Provide enough information to quickly find the holders of an extent if we notice a given block is corrupted or bad.
• Make it easy to migrate blocks for FS shrinking or storage pool maintenance. This is actually the same as #2, but with a slightly different use case.

File Extent Backrefs

File extents can be referenced by:

• Multiple snapshots, subvolumes, or different generations in one subvol
• Different files inside a single subvolume
• Different offsets inside a file

The extent ref structure has fields for:

• Objectid of the subvolume root
• Generation number of the tree holding the reference
• objectid of the file holding the reference
• offset in the file corresponding to the key holding the reference

When a file extent is allocated the fields are filled in:

• (root objectid, transaction id inode objectid, offset in file)

When a leaf is cow'd new references are added for every file extent found in the leaf. It looks the same as the create case, but the transaction id will be different when the block is cow'd.

• (root objectid, transaction id, inode objectid, offset in file)

When a file extent is removed either during snapshot deletion or file truncation, the corresponding back reference is found by searching for:

• (btrfs_header_owner(leaf), btrfs_header_generation(leaf), inode objectid, offset in file)

Btree Extent Backrefs

Btree extents can be referenced by:

• Different subvolumes
• Different generations of the same subvolume

Storing sufficient information for a full reverse mapping of a btree block would require storing the lowest key of the block in the backref, and it would require updating that lowest key either before write out or every time it changed.

Instead, the objectid of the lowest key is stored along with the level of the tree block. This provides a hint about where in the btree the block can be found. Searches through the btree only need to look for a pointer to that block, and they stop one level higher than the level recorded in the backref.

Some btrees do not do reference counting on their extents. These include the extent tree and the tree of tree roots. Backrefs for these trees always have a generation of zero.

When a tree block is created, back references are inserted:

• (root objectid, transaction id or zero, level, lowest objectid)

The level is stored in the objectid slot of the backref to differentiate between Btree back references and file data back references. The highest possible level is 255, and the lowest possible file objectid has been raised to 256. So, if the objectid field in the back reference is less than 256, it corresponds to a Btree block.

When a tree block is cow'd in a reference counted root, new back references are added for all the blocks it points to:

• (root objectid, transaction id, level, lowest objectid)

Because the lowest_key_objectid and the level are just hints they are not used when backrefs are deleted. When a snapshot is created a new reference is taken directly on the root block. This means the owner field of the root block may be different from the objectid of the snapshot. So, when dropping references on tree roots, the objectid of the root structure is always used. When a backref is deleted:

if backref was for a tree root:
     root_objectid = root->root_key.objectid
else
     root_objectid = btrfs_header_owner(parent)

• (root_objectid, btrfs_header_generation(parent) or zero, 0, 0)

Back Reference Key Construction

Back references have four fields, each 64 bits long. This is hashed into a single 64 bit number and placed into the key offset. The key objectid corresponds to the first byte in the extent, and the key type is set to BTRFS_EXTENT_REF_KEY.

Hash overflows on the offset field are handled by adding one to the calculated hash and searching forward. The searching stops when the correct back reference structure is found or