Josep Comes

An AArch64 OS in Rust – Parsing the Device Tree (Part 1)

by Jcomes
Tags: [ARM] [Kernel]

In my previous post, I built a minimal bootloader to load the kernel and pass the address of the Device Tree Blob (DTB) via the x0 register. Up until now, my kernel has been “cheating” – I hardcoded peripheral addresses like the UART (0x09000000) and the GIC (0x08000000) directly into the source code. While this worked for a specific QEMU configuration, it is a shortcut I am now stepping away from to do the job correctly.

The goal for this post is to implement a DTB parser, allowing the kernel to become hardware-agnostic; instead of assuming where devices are, it will query the blob provided by the bootloader to discover the system layout at runtime. We will focus on the structural side of the problem – parsing the FDT header, handling big-endian conversion, and implementing the tag-based traversal logic to walk the tree. This establishes the foundation for the next post, where we will move into interpreting that data to handle address translation and driver matching.

The Flattened Device Tree Format

The DTB is called flattened because it takes a hierarchical tree structure and serializes it into a sequential layout in memory. The parsing turned out to be more interesting than I expected, with specific requirements around memory alignment and property encoding that the kernel must respect to avoid crashes.

All multi-byte values in the DTB are stored in big-endian format, regardless of the host machine’s native byte order. This is a critical detail for our AArch64 kernel, which runs in little-endian. The format is organized into three main parts:

  • Header: A fixed-size structure at the very beginning with magic numbers and offsets to the other sections.
  • Structure Block: The actual tree, encoded as a sequence of tokens (tags) that define nodes and properties.
  • Strings Block: A consolidated table for property names (like compatible or reg) to save space.

The header always comes first, followed by the two blocks at memory offsets defined within that header.

The FDT Header

The header is a 40-byte structure at the beginning of the DTB. In Rust, we represent this with a #[repr(C)] struct to match the memory layout exactly.


#[repr(C)]
struct FdtHeader {
    magic: u32,             // Must be 0xd00dfeed
    totalsize: u32,         // Total DTB size in bytes
    off_dt_struct: u32,     // Offset to structure block
    off_dt_strings: u32,    // Offset to strings block
    off_mem_rsvmap: u32,    // Offset to memory reservation block
    version: u32,           // DTB version number
    last_comp_version: u32, // Last compatible version
    boot_cpuid_phys: u32,   // Physical CPU ID for boot
    size_dt_strings: u32,   // Size of strings block
    size_dt_struct: u32,    // Size of structure block
}

Most of these fields are used for validation and navigation. The magic number (0xd00dfeed) is our first check to ensure the pointer passed in x0 actually points to a valid DTB. The offsets are the most critical part of the header; they allow us to locate the structure and strings blocks within the blob. Finally, the totalsize gives us a boundary for our parser to ensure we don’t read past the end of the provided memory.

FDT Tokens

The structure block encodes the tree as a sequence of 32-bit tokens. To walk the tree, our parser iterates through these tags:

  • FDT_BEGIN_NODE (0x00000001): Marks the start of a node. It’s followed by the node’s name (null-terminated string), padded to 4-byte alignment. As an exception, the root node is represented by an empty string (a single null byte).
  • FDT_END_NODE (0x00000002): Marks the end of a node. All properties and child nodes must appear between FDT_BEGIN_NODE and FDT_END_NODE for that node.
  • FDT_PROP (0x00000003): Indicates a property. It is followed by a property header (described below) and the actual data.
  • FDT_NOP (0x00000004): A no-operation token used for alignment or as a placeholder. Parsers skip over it.
  • FDT_END (0x00000009): Signals the end of the structure block.

Property Header and Metadata

When we encounter an FDT_PROP token, it’s immediately followed by an 8-byte header that tells us what the property is and how big it is:


#[repr(C)]
struct FdtPropertyHeader {
    len: u32,      // Length of property value in bytes
    nameoff: u32,  // Offset into strings block for property name
}

The property value follows this header and is len bytes long. One detail that mirrored my work on the ELF loader is the use of a separate string table. Just as an ELF uses .strtab to deduplicate names, the DTB stores property names like compatible or reg once in the Strings Block. This deduplication is why the header stores a nameoff (an offset) rather than the string itself.

The values themselves are stored as raw bytes. In Rust, I store these as a *const u8 because their interpretation depends entirely on the property name. For example, a property might be a simple string, a single u32, or a complex array of addresses.

A key detail to note is the # prefix convention, such as #address-cells and #size-cells. These are “meta-properties” that define how to interpret data in child nodes rather than describing the device itself. For instance, #address-cells specifies how many 32-bit cells are needed to represent an address in a child node’s reg property. Without these values, it is impossible to parse hardware addresses correctly – a detail we’ll lean on heavily in the next post.

Representing Devices in Memory

Before we can walk the tree, we need a way to store what we find. I defined a PlatformDevice struct to hold the node’s name, its properties, and a pointer to its parent. This mirrors the “Object-oriented” view of hardware used in larger kernels, where each node is a container for its characteristics.


const MAX_PROPS: usize = 16;

struct Property {
    pub name: &'static str,
    pub value: *const u8,  // Raw bytes - interpret later
    pub len: usize,
}

struct PlatformDevice {
    pub parent: *const PlatformDevice,
    pub name: &'static str,
    pub properties: [Property; MAX_PROPS],
    pub prop_count: usize,
}

By using a raw byte pointer (*const u8) for the property value, the parser remains “dumb”. It doesn’t need to know if it’s looking at an integer or a string; it simply records where the data is in the blob. This keeps the initial pass fast and defers the complex interpretation of things like reg addresses to a later stage when we have the proper context.

I’ve capped MAX_PROPS at 16 for now; while some complex nodes in a full system tree might have more, this is plenty for the essential peripherals in our early-stage kernel.

The Parsing Algorithm

The parser walks the structure block token by token, building up a table of PlatformDevice entries. Because the DTB represents a tree, we use a small stack to keep track of the current nesting level and parent-child relationships.


pub fn parse_dtb(dtb: usize) {
    let header = FdtHeader::from_be_bytes(dtb);

    if header.magic != MAGIC {
        panic!();
    }

    let structure_block = dtb + header.off_dt_struct as usize;
    let mut off = 0;
    let mut prop_id = 0;
    let mut device = PlatformDevice::default();
    let mut stack: [usize; 10] = [0; 10];
    let mut stack_depth = 0;

    loop {
        let token = read_be_u32(structure_block as *const u8, off);
        off += 4;

        match token {
            FDT_BEGIN_NODE => { /* ... */ },
            FDT_END_NODE => { /* ... */ },
            FDT_PROP => { /* ... */ },
            FDT_NOP => { /* ignore */ },
            FDT_END => break,
            _ => panic!(),
        }
    }
}

Handling Nodes and Nesting

When we encounter an FDT_BEGIN_NODE token, we initialize a new PlatformDevice. If stack_depth is greater than zero, it means we are inside a parent node, so we assign the parent pointer before moving on to the node name.


FDT_BEGIN_NODE => {
    device = PlatformDevice::default();

    // Set parent pointer if we're nested inside another node
    if stack_depth > 0 {
        device.parent = &DEVICE_TABLE[stack[stack_depth - 1]] as *const PlatformDevice;
    }

    // Read the node name (null-terminated string stored inline)
    let name_start = (structure_block + off) as *const u8;
    let mut name_len = 0;
    while *name_start.add(name_len) != 0 {
        name_len += 1;
    }

    device.name = core::str::from_utf8_unchecked(
        core::slice::from_raw_parts(name_start, name_len)
    );

    // Move past name and align to 4 bytes
    off += name_len + 1;
    off = (off + 3) & !3;

    // Push current device index onto stack for parent tracking
    stack[stack_depth] = DEVICE_COUNT;
    stack_depth += 1;
}

The stack allows us to maintain the hierarchy. By pushing the current DEVICE_COUNT onto the stack, child nodes can look back and see exactly which device is their parent. Note the alignment logic (off + 3) & !3; this is vital because while names can be any length, the FDT spec requires the next token to start on a 4-byte boundary.

Processing Properties

For properties, we read the 8-byte header to find the length and the name offset, then look up the actual string in the strings block.


FDT_PROP => {
    let prop_header = FdtPropHeader::from_be_bytes(structure_block + off);
    off += 8;

    let mut prop = Property::default();
    prop.name = get_property_name(dtb, header.off_dt_strings as usize, prop_header.nameoff);
    prop.len = prop_header.len as usize;
    prop.value = (structure_block + off) as *const u8;

    device.properties[prop_id] = prop;
    prop_id += 1;

    // Move past value and align to 4 bytes
    off += prop.len;
    off = (off + 3) & !3;
}

At this stage, we only save the pointer to the property value. We don’t parse the data yet (such as converting a reg entry into an address) because that requires knowing the #address-cells context of the parent, which we will handle in the next phase.

Completing the Node

The FDT_END_NODE token signals that all properties and sub-nodes for the current device have been processed. We commit the device to our global table and pop the stack.


FDT_END_NODE => {
    device.prop_count = prop_id;
    DEVICE_TABLE[DEVICE_COUNT] = device;
    DEVICE_COUNT += 1;

    prop_id = 0;
    stack_depth -= 1;
}

Next Steps

With this parser, we’ve successfully transformed a raw binary blob into a structured table of PlatformDevice entries. The kernel is no longer blindly executing in memory; it now has a searchable “map” of the hardware it is running on. However, this is only the first half of the job.

While we can now see the nodes and their raw property bytes, we haven’t yet interpreted what those values mean. In the next post, I’ll dig into the reg and interrupts properties to handle address translation using #address-cells and #size-cells. The final goal will be to replace the remaining hardcoded values in head.S with dynamically discovered ones, completing the transition to a hardware-agnostic boot process.

The full implementation of this parser is available in the aarch64_kernel repository on GitHub.

References