devicetree/
parser.rs

1// Copyright 2025 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use std::str::Utf8Error;
6
7use zerocopy::{BigEndian, FromBytes, Immutable, KnownLayout, U32};
8
9use crate::types::*;
10
11/// The magic string that is expected to be present in `Header.magic`.
12const FDT_MAGIC: u32 = 0xd00dfeed;
13
14/// Marks the beginning of a node's representation. It is followed by the node's
15/// unit name as extra data. The name is stored as a null-terminated string.
16const FDT_BEGIN_NODE: u32 = 0x00000001;
17
18/// Marks the end of a node's representation.
19const FDT_END_NODE: u32 = 0x00000002;
20
21/// Marks the beginning of a property in the device tree.
22const FDT_PROP: u32 = 0x00000003;
23
24/// A token that is meant to be ignored by the parser.
25const FDT_NOP: u32 = 0x00000004;
26
27/// Marks the end of the structure block. There should only be one, and it should be the
28/// last token in the structure block.
29const FDT_END: u32 = 0x00000009;
30
31#[derive(Debug)]
32pub enum ParseError {
33    InvalidMagicNumber,
34    UnsupportedVersion,
35    Utf8Error(Utf8Error),
36    MalformedStructure(String),
37    ZeroCopyError,
38}
39
40impl std::fmt::Display for ParseError {
41    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
42        match self {
43            ParseError::InvalidMagicNumber => write!(f, "Invalid magic number"),
44            ParseError::UnsupportedVersion => write!(f, "Unsupported version"),
45            ParseError::Utf8Error(e) => write!(f, "Utf8 error: {}", e),
46            ParseError::MalformedStructure(e) => write!(f, "Malformed structure: {}", e),
47            ParseError::ZeroCopyError => write!(f, "Zero copy error"),
48        }
49    }
50}
51
52impl std::error::Error for ParseError {
53    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
54        match self {
55            ParseError::Utf8Error(e) => Some(e),
56            _ => None,
57        }
58    }
59}
60
61/// Parses a full `Devicetree` instance from `data`.
62pub fn parse_devicetree(data: &[u8]) -> Result<Devicetree, ParseError> {
63    // Parse and verify the header.
64    let header = *parse_item::<Header>(&data)?;
65    verify_header(&header)?;
66
67    // Parse the memory reservation block.
68    let off_mem_rsvmap = header.off_mem_rsvmap.get() as usize;
69    let reserve_entries = parse_reserve_entries(&data[off_mem_rsvmap..])?;
70
71    // Create the strings section.
72    let off_dt_strings = header.off_dt_strings.get() as usize;
73    let size_dt_strings = header.size_dt_strings.get() as usize;
74    let string_data = verify_slice(&data, off_dt_strings, size_dt_strings)?;
75
76    // Parse the structure block.
77    let off_dt_struct = header.off_dt_struct.get() as usize;
78    let size_dt_struct = header.size_dt_struct.get() as usize;
79    let structure_data = verify_slice(&data, off_dt_struct, size_dt_struct)?;
80    let mut struct_offset = 0;
81    // When `parse_structure_block` returns, `struct_offset` will contain the number of bytes that
82    // were parsed for the structure block.
83    let root_node = parse_structure_block(&structure_data, &mut struct_offset, &string_data)?;
84
85    // Verify that the last token is `FDT_END`, reading from the end of the structure block.
86    let token = parse_item::<U32<BigEndian>>(&structure_data[struct_offset..])?.get();
87    if token != FDT_END {
88        return Err(ParseError::MalformedStructure(format!(
89            "Expected FDT_END token at the end of structure block, got 0x{:x}",
90            token
91        )));
92    }
93
94    Ok(Devicetree { header, reserve_entries, root_node })
95}
96
97// Verifies that the provided `Header` is a valid header.
98fn verify_header(header: &Header) -> Result<(), ParseError> {
99    if header.magic.get() != FDT_MAGIC {
100        return Err(ParseError::InvalidMagicNumber);
101    }
102    if header.version.get() < 17 {
103        return Err(ParseError::UnsupportedVersion);
104    }
105
106    Ok(())
107}
108
109/// Creates a slice from `data` from `offset` to `offset + size`.
110///
111/// Returns an error if the slice is out of bounds of `data`.
112fn verify_slice(data: &[u8], offset: usize, size: usize) -> Result<&[u8], ParseError> {
113    if offset + size > data.len() {
114        return Err(ParseError::MalformedStructure(format!(
115            "Attempted to create slice from 0x{:x} to 0x{:x}, where total length was 0x{:x}",
116            offset,
117            offset + size,
118            data.len()
119        )));
120    }
121    Ok(&data[offset..offset + size])
122}
123
124/// Parses a &T out of `data`.
125///
126/// Returns an error if the parse failed.
127fn parse_item<'a, T: FromBytes + KnownLayout + Immutable>(
128    data: &'a [u8],
129) -> Result<&'a T, ParseError> {
130    let token = T::ref_from_prefix(&data).map_err(|_| ParseError::ZeroCopyError)?;
131    Ok(token.0)
132}
133
134/// Parses a &T out of `data`, and increments offset by `size_of::<T>()` if the parse
135/// was successful.
136///
137/// Returns an error if the parse failed.
138fn parse_item_and_increment_offset<'a, T: FromBytes + KnownLayout + Immutable>(
139    data: &'a [u8],
140    offset: &mut usize,
141) -> Result<&'a T, ParseError> {
142    let r = parse_item(data)?;
143    *offset += std::mem::size_of::<T>();
144
145    Ok(r)
146}
147
148/// Parses a null-terminated string from `data`.
149///
150/// When the function returns, `offset` is set to the index after the null character, aligned to a
151/// 4-byte boundary.
152///
153/// Returns an error if the string is not null-terminated, or the string contains invalid utf8
154/// characters.
155fn parse_string(data: &[u8], offset: &mut usize) -> Result<String, ParseError> {
156    let str_slice = &data[*offset..];
157    let null_index = str_slice.iter().position(|c| *c == 0).ok_or(ParseError::ZeroCopyError)?;
158    *offset += null_index + 1;
159    // Align the offset to the next 4-byte boundary.
160    *offset = (*offset + 3) & !3;
161
162    std::str::from_utf8(&str_slice[..null_index])
163        .map_err(|e| ParseError::Utf8Error(e))
164        .map(|s| s.to_string())
165}
166
167/// Parses the structure block from `data`.
168///
169/// The `offset` is used for recursive calls, and will be set to the end of the parsed node when
170/// the function returns.
171///
172/// `strings_block` is a reference to the strings data, and offsets read from properties will be
173/// used to index into this data.
174fn parse_structure_block(
175    data: &[u8],
176    offset: &mut usize,
177    strings_block: &[u8],
178) -> Result<Node, ParseError> {
179    let token = parse_item_and_increment_offset::<U32<BigEndian>>(&data[*offset..], offset)?;
180    if *token != FDT_BEGIN_NODE {
181        return Err(ParseError::MalformedStructure(format!(
182            "Expected FDT_BEGIN_NODE token at offset 0x{:x}, got 0x{:x}",
183            offset, token
184        )));
185    }
186
187    let name = parse_string(&data, offset)?;
188    let mut node = Node::new(name);
189
190    loop {
191        let token =
192            parse_item_and_increment_offset::<U32<BigEndian>>(&data[*offset..], offset)?.get();
193        match token {
194            token if token == FDT_BEGIN_NODE => {
195                // Reset the offset to parse it again in the recursive call.
196                *offset -= std::mem::size_of_val(&token);
197
198                let child_node = parse_structure_block(data, offset, strings_block)?;
199                node.children.push(child_node);
200            }
201            token if token == FDT_PROP => {
202                let length =
203                    parse_item_and_increment_offset::<U32<BigEndian>>(&data[*offset..], offset)?
204                        .get() as usize;
205
206                let mut prop_name_offset =
207                    parse_item_and_increment_offset::<U32<BigEndian>>(&data[*offset..], offset)?
208                        .get() as usize;
209                let prop_name = parse_string(&strings_block, &mut prop_name_offset)?;
210
211                // Parse the property value, and align the offset to the next 4-byte boundary.
212                let value = data[*offset..*offset + length].to_vec();
213                *offset += length;
214                *offset = (*offset + 3) & !3;
215
216                node.properties.push(Property { name: prop_name, value });
217            }
218            token if token == FDT_END_NODE => {
219                return Ok(node);
220            }
221            token if token == FDT_NOP => {}
222            token if token == FDT_END => {
223                return Err(ParseError::MalformedStructure("FDT_END inside of node".to_string()));
224            }
225            token => {
226                return Err(ParseError::MalformedStructure(format!(
227                    "Expected valid token at offset 0x{:x}, got 0x{:x}",
228                    offset, token
229                )));
230            }
231        }
232    }
233}
234
235/// Parses an array of `ReserveEntry`'s from `data`.
236fn parse_reserve_entries(data: &[u8]) -> Result<Vec<ReserveEntry>, ParseError> {
237    let mut entries = Vec::new();
238    let mut offset = 0;
239    loop {
240        let entry: &ReserveEntry = ReserveEntry::ref_from_prefix(&data[offset..])
241            .map_err(|_| {
242                ParseError::MalformedStructure(
243                    "Memory reservation map entry too small or misaligned.".to_string(),
244                )
245            })?
246            .0;
247
248        // If both the address and the size are zero, this is the end of the entries.
249        if entry.address.get() == 0 && entry.size.get() == 0 {
250            return Ok(entries);
251        }
252
253        entries.push(*entry);
254        offset += std::mem::size_of::<ReserveEntry>();
255    }
256}
257
258#[cfg(test)]
259mod test {
260    #[test]
261    fn test_vim3() {
262        let contents = std::fs::read("pkg/test-data/test.dtb").expect("failed to read file");
263        crate::parser::parse_devicetree(&contents).expect("failed to parse devicetree");
264    }
265}
devicetree/parser.rs

devicetree/
parser.rs
