This is the third of a multipart series that explains the basics of btrfs’s on-disk format.
At the end of this series, we’ll have a program that can print out the absolute path of every regular file in an unmounted btrfs filesystem image without external libraries or ioctl(2) calls.
Example code is available here.
As explained in part 2, btrfs stores nearly everything on-disk in B-trees. And as promised, I’ll now describe the B-tree data format. First, an example tree:
Each node in a btrfs B-tree is prefixed with a header. The header records the node’s “level”. Level 0 means the node is a leaf node and stores a payload. Level > 0 means the node is an internal node and stores pointers to children nodes. The header also stores the number of “items” the node contains where an “item” is either a pointer to child node if level > 0, else, information on where to find the payload in the node. Recall that each item in a node is sorted by the associated BtrfsKey which allows for efficient binary searches. There’s also some other data but it’s not too important to us.
In our example, root and node 0 contain BtrfsKeyPtrs because they’re not leaf nodes. leaf 0 and leaf 1 contain BtrfsItems because they are leaf nodes.
Now that we understand how trees are laid out on disk, let’s process the rest of the chunk tree.
First, let’s define the necessary structures:
#[repr(C, packed)]
#[derive(Copy, Clone)]
pub struct BtrfsHeader {
pub csum: [u8; BTRFS_CSUM_SIZE],
pub fsid: [u8; BTRFS_FSID_SIZE],
pub bytenr: u64,
pub flags: u64,
pub chunk_tree_uuid: [u8; BTRFS_UUID_SIZE],
pub generation: u64,
pub owner: u64,
pub nritems: u32,
pub level: u8,
}
#[repr(C, packed)]
#[derive(Copy, Clone)]
pub struct BtrfsKeyPtr {
pub key: BtrfsKey,
pub blockptr: u64,
pub generation: u64,
}
#[repr(C, packed)]
#[derive(Copy, Clone)]
pub struct BtrfsItem {
pub key: BtrfsKey,
pub offset: u32,
pub size: u32,
}Note that BtrfsItem::offset is the offset from the end of the associated BtrfsHeader that we can find the payload for the BtrfsItem.
Although not strictly necessary, we also define BtrfsNode and BtrfsLeaf as the following:
#[repr(C, packed)]
#[derive(Copy, Clone)]
pub struct BtrfsNode {
pub header: BtrfsHeader,
// `BtrfsKeyPtr`s begin here
}
#[repr(C, packed)]
#[derive(Copy, Clone)]
pub struct BtrfsLeaf {
pub header: BtrfsHeader,
// `BtrfsItem`s begin here
}We don’t need these structure definitions because all it tells us is that every node in the on-disk B-tree starts with BtrfsHeader. After parsing the header and reading BtrfsHeader::level, we can infer what follows the header.
To walk any tree, we need to start at the root node. The superblock contains the logical offset the chunk tree root lives at. To read it:
fn read_chunk_tree_root(
file: &File,
chunk_root_logical: u64,
cache: &ChunkTreeCache,
) -> Result<Vec<u8>> {
let size = cache
.mapping_kv(chunk_root_logical)
.ok_or_else(|| anyhow!("Chunk tree root not bootstrapped"))?
.0
.size;
let physical = cache
.offset(chunk_root_logical)
.ok_or_else(|| anyhow!("Chunk tree root not bootstrapped"))?;
let mut root = vec![0; size as usize];
file.read_exact_at(&mut root, physical)?;
Ok(root)
}where chunk_root_logical is BtrfsSuperblock::chunk_root.
Walking the actual tree looks like a traditional recursive tree-walking algorithm:
fn read_chunk_tree(
file: &File,
root: &[u8],
chunk_tree_cache: &mut ChunkTreeCache,
superblock: &BtrfsSuperblock,
) -> Result<()> {
let header = tree::parse_btrfs_header(root)
.expect("failed to parse chunk root header");tree::parse_btrfs_header is a simple helper function that extracts the BtrfsHeader out of root and returns a reference to the header.
// Level 0 is leaf node, !0 is internal node
if header.level == 0 {
let items = tree::parse_btrfs_leaf(root)?;If we’re at level 0, we know we’re looking at a leaf node. So we use tree::parse_btrfs_leaf to extract the BtrfsItems.
for item in items {
if item.key.ty != BTRFS_CHUNK_ITEM_KEY {
continue;
}We skip anything that isn’t a chunk item. The chunk tree also contains BTRFS_DEV_ITEM_KEYs which help map physical offsets to logical offsets. However, we only need chunk items for our purpose so we skip everything else.
let chunk = unsafe {
// `item.offset` is offset from data portion of `BtrfsLeaf` where
// associated `BtrfsChunk` starts
&*(root
.as_ptr()
.add(std::mem::size_of::<BtrfsHeader>() + item.offset as usize)
as *const BtrfsChunk)
};As mentioned earlier, BtrfsItem::offset is the offset from the end of the BtrfsHeader. The above code does the proper math to pull out the BtrfsChunk associated with the current item.
chunk_tree_cache.insert(
ChunkTreeKey {
start: item.key.offset,
size: chunk.length,
},
ChunkTreeValue {
offset: chunk.stripe.offset,
},
);
}Finally, we add the chunk entry into our chunk tree cache.
} else {
let ptrs = tree::parse_btrfs_node(root)?;
for ptr in ptrs {
let physical = chunk_tree_cache
.offset(ptr.blockptr)
.ok_or_else(|| anyhow!("Chunk tree node not mapped"))?;
let mut node = vec![0; superblock.node_size as usize];
file.read_exact_at(&mut node, physical)?;
read_chunk_tree(file, &node, chunk_tree_cache, superblock)?;
}
}If we see level != 0, we know we’re looking at an internal node. So we use the tree::parse_btrfs_node helper to parse an internal node. Once we have the BtrfsKeyPtrs, we read the node the key points to and recursively call read_chunk_tree.
Ok(())
}If we haven’t errored out by the end, it means we successfully walked the chunk tree.
Now that we’ve loaded the entire chunk tree into our cache, we can move onto walking the trees that contain the information we actually care about. In the next post, we’ll extract the filesystem tree root from the root tree root.