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<'a>(data: &'a [u8]) -> Result<Devicetree<'a>, 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<'a>(data: &'a [u8], offset: &mut usize) -> Result<&'a str, 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]).map_err(|e| ParseError::Utf8Error(e))
163}
164
165/// Parses the structure block from `data`.
166///
167/// The `offset` is used for recursive calls, and will be set to the end of the parsed node when
168/// the function returns.
169///
170/// `strings_block` is a reference to the strings data, and offsets read from properties will be
171/// used to index into this data.
172fn parse_structure_block<'a>(
173    data: &'a [u8],
174    offset: &mut usize,
175    strings_block: &'a [u8],
176) -> Result<Node<'a>, ParseError> {
177    let token = parse_item_and_increment_offset::<U32<BigEndian>>(&data[*offset..], offset)?;
178    if *token != FDT_BEGIN_NODE {
179        return Err(ParseError::MalformedStructure(format!(
180            "Expected FDT_BEGIN_NODE token at offset 0x{:x}, got 0x{:x}",
181            offset, token
182        )));
183    }
184
185    let name = parse_string(&data, offset)?;
186    let mut node = Node::new(name);
187
188    loop {
189        let token =
190            parse_item_and_increment_offset::<U32<BigEndian>>(&data[*offset..], offset)?.get();
191        match token {
192            token if token == FDT_BEGIN_NODE => {
193                // Reset the offset to parse it again in the recursive call.
194                *offset -= std::mem::size_of_val(&token);
195
196                let child_node = parse_structure_block(data, offset, strings_block)?;
197                node.children.push(child_node);
198            }
199            token if token == FDT_PROP => {
200                let length =
201                    parse_item_and_increment_offset::<U32<BigEndian>>(&data[*offset..], offset)?
202                        .get() as usize;
203
204                let mut prop_name_offset =
205                    parse_item_and_increment_offset::<U32<BigEndian>>(&data[*offset..], offset)?
206                        .get() as usize;
207                let prop_name = parse_string(&strings_block, &mut prop_name_offset)?;
208
209                // Parse the property value, and align the offset to the next 4-byte boundary.
210                let value = &data[*offset..*offset + length];
211                *offset += length;
212                *offset = (*offset + 3) & !3;
213
214                node.properties.push(Property { name: prop_name, value });
215            }
216            token if token == FDT_END_NODE => {
217                return Ok(node);
218            }
219            token if token == FDT_NOP => {}
220            token if token == FDT_END => {
221                return Err(ParseError::MalformedStructure("FDT_END inside of node".to_string()));
222            }
223            token => {
224                return Err(ParseError::MalformedStructure(format!(
225                    "Expected valid token at offset 0x{:x}, got 0x{:x}",
226                    offset, token
227                )));
228            }
229        }
230    }
231}
232
233/// Parses an array of `ReserveEntry`'s from `data`.
234fn parse_reserve_entries<'a>(data: &'a [u8]) -> Result<&'a [ReserveEntry], ParseError> {
235    let mut num_entries = 0;
236    let mut offset = 0;
237    loop {
238        let entry: &ReserveEntry = ReserveEntry::ref_from_prefix(&data[offset..])
239            .map_err(|_| {
240                ParseError::MalformedStructure(
241                    "Memory reservation map entry too small or misaligned.".to_string(),
242                )
243            })?
244            .0;
245
246        // If both the address and the size are zero, this is the end of the entries.
247        if entry.address.get() == 0 && entry.size.get() == 0 {
248            return <[ReserveEntry]>::ref_from_prefix_with_elems(data, num_entries)
249                .map(|s| s.0)
250                .map_err(|_| {
251                    ParseError::MalformedStructure("Invalid reserve entry slice".to_string())
252                });
253        }
254
255        offset += std::mem::size_of::<ReserveEntry>();
256        num_entries += 1;
257    }
258}
259
260#[cfg(test)]
261mod test {
262    #[test]
263    fn test_vim3() {
264        let contents = std::fs::read("pkg/test-data/test.dtb").expect("failed to read file");
265        crate::parser::parse_devicetree(&contents).expect("failed to parse devicetree");
266    }
267}
devicetree/parser.rs

devicetree/
parser.rs
