fdt/
parser.rs

1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4//! Code to parse a Flattened DeviceTree binary blob.
5
6use super::spec;
7use super::spec::U32b;
8use super::spec::U64b;
9use core::fmt::Display;
10use core::mem::size_of;
11use zerocopy::FromBytes;
12use zerocopy::Immutable;
13use zerocopy::KnownLayout;
14
15/// Errors returned when parsing a FDT.
16#[derive(Debug)]
17pub struct Error<'a>(ErrorKind<'a>);
18
19impl Display for Error<'_> {
20    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
21        self.0.fmt(f)
22    }
23}
24
25// TODO: Once core::error::Error is stablized, we can remove this feature gate.
26impl core::error::Error for Error<'_> {}
27
28/// Types of errors when parsing a FDT.
29#[derive(Debug)]
30enum ErrorKind<'a> {
31    /// Buffer is not aligned to u32
32    BufferAlignment,
33    /// Buffer too small for fixed header
34    NoHeader,
35    /// Fixed header magic invalid
36    HeaderMagic,
37    /// Total size described in the fixed header is greater than buffer provided
38    HeaderTotalSize,
39    /// Header version is invalid
40    HeaderVersion,
41    /// Structure block not contained within buffer
42    StructureBlock,
43    /// Structure block not aligned to u32
44    StructureBlockAlignment,
45    /// Memory reservation block not contained within buffer
46    MemoryReservationBlock,
47    /// Memory reservation block did not end with an empty entry
48    MemoryReservationBlockEnd,
49    /// Strings block not contained within buffer
50    StringsBlock,
51    /// No root node present
52    RootNode,
53    /// More than one node at the root
54    MultipleRootNodes,
55    /// Unable to parse FDT token when parsing nodes
56    NodeToken(ParseTokenError),
57    /// Unexpected token when parsing begin node
58    NodeBegin(u32),
59    /// Unexpected token when parsing node properties
60    NodeProp(u32),
61    /// Unexpected token when parsing children nodes
62    NodeChildren(u32),
63    /// Property data buffer len is not a multiple of requested type size
64    PropertyDataTypeBuffer {
65        node_name: &'a str,
66        prop_name: &'a str,
67    },
68    /// Property requested at offset is larger than data buffer
69    PropertyOffset {
70        node_name: &'a str,
71        prop_name: &'a str,
72    },
73    /// Property data is not a a valid string
74    PropertyStr {
75        node_name: &'a str,
76        error: StringError,
77    },
78    /// Unable to parse FDT token when parsing properties
79    PropertyTokenParse {
80        node_name: &'a str,
81        error: ParseTokenError,
82    },
83    /// Unexpected FDT token when parsing properties
84    PropertyToken { node_name: &'a str, token: u32 },
85    /// Property name string is not a valid string
86    PropertyNameStr {
87        node_name: &'a str,
88        error: StringError,
89    },
90    /// FDT end token not present at end of structure block
91    FdtEnd,
92}
93
94impl Display for ErrorKind<'_> {
95    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
96        match self {
97            ErrorKind::BufferAlignment => f.write_str("Buffer is not aligned to u32"),
98            ErrorKind::NoHeader => f.write_str("Buffer too small for fixed FDT header"),
99            ErrorKind::HeaderMagic => f.write_str("FDT header magic field invalid"),
100            ErrorKind::HeaderTotalSize => {
101                f.write_str("FDT header total size greater than provided buffer")
102            }
103            ErrorKind::HeaderVersion => f.write_str("FDT header version invalid"),
104            ErrorKind::StructureBlock => f.write_str("Structure block not contained within buffer"),
105            ErrorKind::StructureBlockAlignment => {
106                f.write_str("Structure block offset is not aligned to u32")
107            }
108            ErrorKind::MemoryReservationBlock => {
109                f.write_str("Memory reservation block not contained within buffer")
110            }
111            ErrorKind::MemoryReservationBlockEnd => {
112                f.write_str("Memory reservation block did not end with an empty entry")
113            }
114            ErrorKind::StringsBlock => f.write_str("Strings block not contained within buffer"),
115            ErrorKind::RootNode => f.write_str("No root node present"),
116            ErrorKind::MultipleRootNodes => f.write_str("More than one node at the root"),
117            ErrorKind::NodeToken(e) => f.write_fmt(format_args!(
118                "Unable to parse FDT token when parsing nodes {}",
119                e
120            )),
121            ErrorKind::NodeBegin(token) => f.write_fmt(format_args!(
122                "Unexpected token when parsing begin node {}",
123                token
124            )),
125            ErrorKind::NodeProp(token) => f.write_fmt(format_args!(
126                "Unexpected token when parsing node properties {}",
127                token
128            )),
129            ErrorKind::NodeChildren(token) => f.write_fmt(format_args!(
130                "Unexpected token when parsing children nodes {}",
131                token
132            )),
133            ErrorKind::PropertyDataTypeBuffer { node_name, prop_name } => f.write_fmt(format_args!(
134                "Property {prop_name} data buffer len is not multiple of type size for node {node_name}"
135            )),
136            ErrorKind::PropertyOffset { node_name, prop_name } => f.write_fmt(format_args!(
137                "Property {prop_name} requested at offset is larger than data buffer for node {node_name}"
138            )),
139            ErrorKind::PropertyStr { node_name, error } => f.write_fmt(format_args!(
140                "Property data is not a a valid string for node {node_name}: {error}"
141            )),
142            ErrorKind::PropertyTokenParse { node_name, error } => f.write_fmt(format_args!(
143                "Unable to parse FDT token when parsing properties for node {node_name}: {error}",
144            )),
145            ErrorKind::PropertyToken { node_name, token } => f.write_fmt(format_args!(
146                "Unexpected FDT token when parsing properties for node {node_name}: {}",
147                token
148            )),
149            ErrorKind::PropertyNameStr { node_name, error } => f.write_fmt(format_args!(
150                "Property name string is not a valid string for node {node_name}: {error}",
151            )),
152            ErrorKind::FdtEnd => f.write_str("FDT end token not present at end of structure block"),
153        }
154    }
155}
156
157/// A parser used to parse a FDT.
158pub struct Parser<'a> {
159    /// The total size used by the dt.
160    pub total_size: usize,
161    /// The strings block.
162    strings_block: &'a [u8],
163    /// The structure block.
164    structure_block: &'a [u8],
165    /// The bsp reg field
166    pub boot_cpuid_phys: u32,
167    /// The memory reservations blocks without the final empty entry.
168    memory_reservations: &'a [u8],
169}
170
171impl<'a> Parser<'a> {
172    /// Read just the `totalsize` field of a FDT header. This is useful when
173    /// attempting to determine the overall size of a device tree.
174    pub fn read_total_size(buf: &[u8]) -> Result<usize, Error<'a>> {
175        let header = spec::Header::read_from_prefix(buf)
176            .map_err(|_| Error(ErrorKind::NoHeader))?
177            .0; // TODO: zerocopy: map_err (https://github.com/microsoft/openvmm/issues/759)
178
179        if u32::from(header.magic) != spec::MAGIC {
180            Err(Error(ErrorKind::HeaderMagic))
181        } else {
182            Ok(u32::from(header.totalsize) as usize)
183        }
184    }
185
186    /// Create a new instance of a FDT parser.
187    pub fn new(buf: &'a [u8]) -> Result<Self, Error<'a>> {
188        if buf.as_ptr() as usize % size_of::<u32>() != 0 {
189            return Err(Error(ErrorKind::BufferAlignment));
190        }
191
192        let header = spec::Header::read_from_prefix(buf)
193            .map_err(|_| Error(ErrorKind::NoHeader))?
194            .0; // TODO: zerocopy: map_err (https://github.com/microsoft/openvmm/issues/759)
195
196        if u32::from(header.magic) != spec::MAGIC {
197            return Err(Error(ErrorKind::HeaderMagic));
198        }
199
200        // Validate total size within buf.
201        let total_size = u32::from(header.totalsize) as usize;
202        if total_size > buf.len() {
203            return Err(Error(ErrorKind::HeaderTotalSize));
204        }
205
206        if u32::from(header.version) < spec::CURRENT_VERSION
207            || u32::from(header.last_comp_version) > spec::COMPAT_VERSION
208        {
209            return Err(Error(ErrorKind::HeaderVersion));
210        }
211
212        // Validate the mem_rsvmap region ends with an empty entry. Currently
213        // the parser does not make these values accessible.
214        let mem_rsvmap_offset = u32::from(header.off_mem_rsvmap) as usize;
215        let mut memory_reservations_len = 0;
216        let mut mem_rsvmap = buf
217            .get(mem_rsvmap_offset..)
218            .ok_or(Error(ErrorKind::MemoryReservationBlock))?;
219        loop {
220            let (entry, rest) = spec::ReserveEntry::read_from_prefix(mem_rsvmap)
221                .map_err(|_| Error(ErrorKind::MemoryReservationBlockEnd))?; // TODO: zerocopy: map_err (https://github.com/microsoft/openvmm/issues/759)
222
223            if u64::from(entry.address) == 0 && u64::from(entry.size) == 0 {
224                break;
225            }
226
227            mem_rsvmap = rest;
228            memory_reservations_len += size_of::<spec::ReserveEntry>();
229        }
230
231        let memory_reservations = buf
232            .get(mem_rsvmap_offset..(mem_rsvmap_offset + memory_reservations_len))
233            .ok_or(Error(ErrorKind::MemoryReservationBlock))?;
234
235        let struct_offset = u32::from(header.off_dt_struct) as usize;
236        let struct_len = u32::from(header.size_dt_struct) as usize;
237
238        if struct_offset % size_of::<u32>() != 0 {
239            return Err(Error(ErrorKind::StructureBlockAlignment));
240        }
241
242        let structure_block = buf
243            .get(struct_offset..(struct_offset + struct_len))
244            .ok_or(Error(ErrorKind::StructureBlock))?;
245
246        // FDT_END must be the last token in the structure block. Ignore it once
247        // checked.
248        let structure_block = structure_block
249            .strip_suffix(&spec::END.to_be_bytes())
250            .ok_or(Error(ErrorKind::FdtEnd))?;
251
252        let strings_offset = u32::from(header.off_dt_strings) as usize;
253        let strings_len = u32::from(header.size_dt_strings) as usize;
254        let strings_block = buf
255            .get(strings_offset..(strings_offset + strings_len))
256            .ok_or(Error(ErrorKind::StringsBlock))?;
257
258        Ok(Self {
259            total_size,
260            strings_block,
261            structure_block,
262            memory_reservations,
263            boot_cpuid_phys: header.boot_cpuid_phys.into(),
264        })
265    }
266
267    /// Returns the root node of this FDT.
268    pub fn root<'b>(&'b self) -> Result<Node<'a>, Error<'a>> {
269        let mut iter = NodeIter {
270            strings_block: self.strings_block,
271            nodes: self.structure_block,
272        };
273
274        let root = iter.next().ok_or(Error(ErrorKind::RootNode))??;
275
276        if iter.next().is_some() {
277            Err(Error(ErrorKind::MultipleRootNodes))
278        } else {
279            Ok(root)
280        }
281    }
282
283    /// Returns an iterator to parse through memory reservations.
284    pub fn memory_reservations(&self) -> MemoryReserveIter<'a> {
285        MemoryReserveIter {
286            memory_reservations: self.memory_reservations,
287        }
288    }
289}
290
291/// Get a string from the strings block at the given offset.
292fn string_from_offset(strings_block: &[u8], offset: U32b) -> Result<&str, StringError> {
293    let offset = u32::from(offset) as usize;
294
295    extract_str_from_bytes(strings_block.get(offset..).ok_or(StringError::Offset)?)
296}
297
298/// An iterator to parse through FDT nodes.
299pub struct NodeIter<'a> {
300    strings_block: &'a [u8],
301    nodes: &'a [u8],
302}
303
304enum ParsedToken<'a> {
305    BeginNode { name: &'a str },
306    Property { name_offset: U32b, data: &'a [u8] },
307    EndNode,
308    Nop,
309    End,
310}
311
312impl ParsedToken<'_> {
313    fn raw(&self) -> u32 {
314        match self {
315            ParsedToken::BeginNode { .. } => spec::BEGIN_NODE,
316            ParsedToken::Property { .. } => spec::PROP,
317            ParsedToken::EndNode => spec::END_NODE,
318            ParsedToken::Nop => spec::NOP,
319            ParsedToken::End => spec::END,
320        }
321    }
322}
323
324/// Errors returned when parsing FDT tokens.
325#[derive(Debug)]
326enum ParseTokenError {
327    /// Unknown token
328    Unknown(u32),
329    /// Buf too small
330    BufLen,
331    /// Buf too small for prop header
332    PropHeader,
333    /// Buf too small for prop data described in prop header
334    PropData,
335    /// Begin node name is not valid
336    BeginName(StringError),
337    /// Buf too small for begin node name alignment
338    BeginNameAlignment,
339}
340
341impl Display for ParseTokenError {
342    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
343        match self {
344            ParseTokenError::Unknown(token) => {
345                f.write_fmt(format_args!("Unknown FDT token {}", token))
346            }
347            ParseTokenError::BufLen => f.write_str("Buffer too small to read token"),
348            ParseTokenError::PropHeader => f.write_str("Buffer too small to read property header"),
349            ParseTokenError::PropData => {
350                f.write_str("Buffer too small to read property data encoded in property header")
351            }
352            ParseTokenError::BeginName(e) => {
353                f.write_fmt(format_args!("Node name is not valid {}", e))
354            }
355            ParseTokenError::BeginNameAlignment => {
356                f.write_str("Buffer is too small for begin node name alignment")
357            }
358        }
359    }
360}
361
362/// Read to the next token from `buf`, returning `(token, remaining_buffer)`.
363fn read_token(buf: &[u8]) -> Result<(ParsedToken<'_>, &[u8]), ParseTokenError> {
364    let (token, rest) = U32b::read_from_prefix(buf).map_err(|_| ParseTokenError::BufLen)?; // TODO: zerocopy: map_err (https://github.com/microsoft/openvmm/issues/759)
365    let token = u32::from(token);
366    match token {
367        spec::BEGIN_NODE => {
368            // Extract the node's name.
369            let name = extract_str_from_bytes(rest).map_err(ParseTokenError::BeginName)?;
370
371            // The string extracted does not contain the null terminator. Add
372            // the length and align up the total size.
373            let aligned_str_len = ((name.len() + 1) + 4 - 1) & !(4 - 1);
374
375            // Attempt to extract the remainder of the slice, not including the
376            // aligned padding bytes.
377            let rest = rest
378                .get(aligned_str_len..)
379                .ok_or(ParseTokenError::BeginNameAlignment)?;
380
381            Ok((ParsedToken::BeginNode { name }, rest))
382        }
383        spec::PROP => {
384            // Read the property header
385            let (header, rest) = spec::PropHeader::read_from_prefix(rest)
386                .map_err(|_| ParseTokenError::PropHeader)?; // TODO: zerocopy: map_err (https://github.com/microsoft/openvmm/issues/759)
387            let len = u32::from(header.len) as usize;
388            let align_up_len = (len + 4 - 1) & !(4 - 1);
389
390            if align_up_len > rest.len() {
391                return Err(ParseTokenError::PropData);
392            }
393
394            // Only return the non-aligned data buf
395            let data = &rest[..len];
396            let (_, rest) = rest.split_at(align_up_len);
397
398            Ok((
399                ParsedToken::Property {
400                    name_offset: header.nameoff,
401                    data,
402                },
403                rest,
404            ))
405        }
406        spec::END_NODE => Ok((ParsedToken::EndNode, rest)),
407        spec::NOP => Ok((ParsedToken::Nop, rest)),
408        spec::END => Ok((ParsedToken::End, rest)),
409        _ => Err(ParseTokenError::Unknown(token)),
410    }
411}
412
413impl<'a> NodeIter<'a> {
414    fn parse(&mut self) -> Result<Option<Node<'a>>, ErrorKind<'a>> {
415        while !self.nodes.is_empty() {
416            // Parse the next token.
417            let (token, rest) = read_token(self.nodes).map_err(ErrorKind::NodeToken)?;
418            debug_assert!(rest.len() % size_of::<U32b>() == 0);
419
420            let name = match token {
421                ParsedToken::Nop => {
422                    self.nodes = rest;
423                    continue;
424                }
425                ParsedToken::BeginNode { name } => name,
426                _ => return Err(ErrorKind::NodeBegin(token.raw())),
427            };
428
429            self.nodes = rest;
430
431            // Find if there is a properties section, which comes before children.
432            let mut prop = self.nodes;
433            'prop: loop {
434                let (token, rest) = read_token(prop).map_err(ErrorKind::NodeToken)?;
435                match token {
436                    ParsedToken::BeginNode { .. } => {
437                        // Begin node means move to parsing children nodes.
438                        break 'prop;
439                    }
440                    ParsedToken::EndNode => {
441                        // End node means this node had no properties.
442                        break 'prop;
443                    }
444                    ParsedToken::Property { .. } | ParsedToken::Nop => {}
445                    token => return Err(ErrorKind::NodeProp(token.raw())),
446                };
447
448                prop = rest;
449            }
450
451            let (prop, rest) = self.nodes.split_at(self.nodes.len() - prop.len());
452            self.nodes = rest;
453
454            // Discover if there are any children, which are signified
455            // by other BEGIN_NODE tokens.
456            let mut children = self.nodes;
457            let mut begin_node_count = 0;
458            'children: loop {
459                let (token, rest) = read_token(children).map_err(ErrorKind::NodeToken)?;
460                match token {
461                    ParsedToken::EndNode => {
462                        if begin_node_count == 0 {
463                            // End of current node
464                            break 'children;
465                        } else {
466                            // Parsing child node, pop node count
467                            begin_node_count -= 1;
468                        }
469                    }
470                    ParsedToken::BeginNode { .. } => {
471                        begin_node_count += 1;
472                    }
473                    ParsedToken::Property { .. } | ParsedToken::Nop => {}
474                    token => return Err(ErrorKind::NodeChildren(token.raw())),
475                };
476
477                children = rest;
478            }
479
480            let (children, rest) = self.nodes.split_at(self.nodes.len() - children.len());
481            self.nodes = rest;
482
483            // Consume END_NODE and return the parsed node
484            let (end_node, rest) = read_token(self.nodes).expect("should be end node");
485            assert!(matches!(end_node, ParsedToken::EndNode));
486            self.nodes = rest;
487
488            return Ok(Some(Node {
489                name,
490                strings_block: self.strings_block,
491                properties: prop,
492                children,
493            }));
494        }
495
496        Ok(None)
497    }
498}
499
500impl<'a> Iterator for NodeIter<'a> {
501    type Item = Result<Node<'a>, Error<'a>>;
502
503    fn next(&mut self) -> Option<Self::Item> {
504        self.parse().map_err(Error).transpose()
505    }
506}
507
508/// A parsed FDT node.
509pub struct Node<'a> {
510    /// The name for this node.
511    pub name: &'a str,
512    strings_block: &'a [u8],
513    properties: &'a [u8],
514    children: &'a [u8],
515}
516
517impl<'a> Node<'a> {
518    /// Returns an iterator to parse through children of this node.
519    pub fn children(&self) -> NodeIter<'a> {
520        NodeIter {
521            strings_block: self.strings_block,
522            nodes: self.children,
523        }
524    }
525
526    /// Returns an iterator to parse through properties of this node.
527    pub fn properties(&self) -> PropertyIter<'a> {
528        PropertyIter {
529            node_name: self.name,
530            strings_block: self.strings_block,
531            properties: self.properties,
532        }
533    }
534
535    /// Find a property with a given name.
536    ///
537    /// Returns `Ok(None)` if the property does not exist.
538    ///
539    /// Returns an error if this node's properties are unable to be parsed.
540    ///
541    /// This method is O(n) for the number of properties on this node, as the
542    /// [`Self::properties`] is used to perform a linear search.
543    pub fn find_property(&self, name: &str) -> Result<Option<Property<'a>>, Error<'a>> {
544        for prop in self.properties() {
545            let prop = prop?;
546
547            if name == prop.name {
548                return Ok(Some(prop));
549            }
550        }
551
552        Ok(None)
553    }
554}
555
556/// An iterator for FDT node properties.
557pub struct PropertyIter<'a> {
558    node_name: &'a str,
559    strings_block: &'a [u8],
560    properties: &'a [u8],
561}
562
563impl<'a> PropertyIter<'a> {
564    fn parse(&mut self) -> Result<Option<Property<'a>>, ErrorKind<'a>> {
565        while !self.properties.is_empty() {
566            // Parse the next token.
567            let (token, rest) =
568                read_token(self.properties).map_err(|error| ErrorKind::PropertyTokenParse {
569                    node_name: self.node_name,
570                    error,
571                })?;
572
573            let (name_off, data, rest) = match token {
574                ParsedToken::Nop => {
575                    self.properties = rest;
576                    continue;
577                }
578                ParsedToken::Property { name_offset, data } => (name_offset, data, rest),
579                _ => {
580                    return Err(ErrorKind::PropertyToken {
581                        node_name: self.node_name,
582                        token: token.raw(),
583                    });
584                }
585            };
586
587            // Read the property name
588            let name = string_from_offset(self.strings_block, name_off).map_err(|error| {
589                ErrorKind::PropertyNameStr {
590                    node_name: self.node_name,
591                    error,
592                }
593            })?;
594
595            self.properties = rest;
596            return Ok(Some(Property {
597                node_name: self.node_name,
598                name,
599                data,
600            }));
601        }
602
603        Ok(None)
604    }
605}
606
607impl<'a> Iterator for PropertyIter<'a> {
608    type Item = Result<Property<'a>, Error<'a>>;
609
610    fn next(&mut self) -> Option<Self::Item> {
611        self.parse().map_err(Error).transpose()
612    }
613}
614
615/// A parsed FDT node property.
616pub struct Property<'a> {
617    node_name: &'a str,
618    /// The name for this property.
619    pub name: &'a str,
620    /// Raw data for this property.
621    pub data: &'a [u8],
622}
623
624impl<'a> Property<'a> {
625    /// Read a value at a given offset, indexed by `size_of::<T>() * index`.
626    /// T must be BigEndian.
627    fn read_val<T: FromBytes + Copy + zerocopy::Unaligned + Immutable + KnownLayout>(
628        &self,
629        index: usize,
630    ) -> Result<T, Error<'a>> {
631        // self.data must be:
632        //  - len must be multiple of size_of(T)
633        //  - index must be within the constructed slice of T
634        //
635        // NOTE: The unaligned bound on T is due to the fact that FDT properties
636        // are only guaranteed to sit on a 4 byte alignment boundary. Thus, to
637        // read types that are greater than 4 bytes, we must bound T to accept
638        // unaligned types so LayoutVerified does not apply alignment and read
639        // incorrect values.
640        <[T]>::ref_from_bytes(self.data)
641            .map_err(|_| {
642                // TODO: zerocopy: map_err (https://github.com/microsoft/openvmm/issues/759)
643                Error(ErrorKind::PropertyDataTypeBuffer {
644                    node_name: self.node_name,
645                    prop_name: self.name,
646                })
647            })?
648            .get(index)
649            .ok_or(Error(ErrorKind::PropertyOffset {
650                node_name: self.node_name,
651                prop_name: self.name,
652            }))
653            .copied()
654    }
655
656    /// Read a u32 from this property, at a given u32 index.
657    pub fn read_u32(&self, index: usize) -> Result<u32, Error<'a>> {
658        let val: u32 = self.read_val::<U32b>(index)?.into();
659
660        Ok(val)
661    }
662
663    /// Read a u64 from this property, at a given u64 index.
664    pub fn read_u64(&self, index: usize) -> Result<u64, Error<'a>> {
665        let val: u64 = self.read_val::<U64b>(index)?.into();
666
667        Ok(val)
668    }
669
670    /// Read the data as a `&str`.
671    pub fn read_str(&self) -> Result<&'a str, Error<'a>> {
672        extract_str_from_bytes(self.data).map_err(|error| {
673            Error(ErrorKind::PropertyStr {
674                node_name: self.node_name,
675                error,
676            })
677        })
678    }
679
680    /// Read data as an iterator of u64 values.
681    pub fn as_64_list(&self) -> Result<impl Iterator<Item = u64> + use<'a>, Error<'a>> {
682        Ok(<[U64b]>::ref_from_bytes(self.data)
683            .map_err(|_| {
684                // TODO: zerocopy: map_err (https://github.com/microsoft/openvmm/issues/759)
685                Error(ErrorKind::PropertyDataTypeBuffer {
686                    node_name: self.node_name,
687                    prop_name: self.name,
688                })
689            })?
690            .iter()
691            .map(|v| v.get()))
692    }
693}
694
695/// Errors when reading a string from the FDT.
696#[derive(Debug)]
697enum StringError {
698    /// Invalid string block offset
699    Offset,
700    /// No null terminator found
701    Null,
702    /// String is not utf8
703    Utf8(core::str::Utf8Error),
704}
705
706impl Display for StringError {
707    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
708        match self {
709            StringError::Offset => f.write_str("Invalid string block offset"),
710            StringError::Null => f.write_str("No null terminator found"),
711            StringError::Utf8(e) => f.write_fmt(format_args!("String is not utf8 {}", e)),
712        }
713    }
714}
715
716/// An iterator to parse through memory reservations.
717pub struct MemoryReserveIter<'a> {
718    memory_reservations: &'a [u8],
719}
720
721impl<'a> MemoryReserveIter<'a> {
722    fn parse(&mut self) -> Result<Option<spec::ReserveEntry>, ErrorKind<'a>> {
723        if self.memory_reservations.is_empty() {
724            return Ok(None);
725        }
726
727        let (entry, rest) = spec::ReserveEntry::read_from_prefix(self.memory_reservations)
728            .map_err(|_| ErrorKind::MemoryReservationBlock)?; // TODO: zerocopy: map_err (https://github.com/microsoft/openvmm/issues/759)
729
730        if u64::from(entry.address) == 0 && u64::from(entry.size) == 0 {
731            return Ok(None);
732        }
733
734        self.memory_reservations = rest;
735
736        Ok(Some(entry))
737    }
738}
739
740impl<'a> Iterator for MemoryReserveIter<'a> {
741    type Item = Result<spec::ReserveEntry, Error<'a>>;
742
743    fn next(&mut self) -> Option<Self::Item> {
744        self.parse().map_err(Error).transpose()
745    }
746}
747
748impl core::error::Error for StringError {}
749
750/// Extract a string from bytes treated as a C String, stopping at the first null terminator.
751fn extract_str_from_bytes(bytes: &[u8]) -> Result<&str, StringError> {
752    // Find the null terminator.
753    // TODO: unstable CStr::from_bytes_until_nul would be nice here.
754    let null_index = bytes
755        .iter()
756        .position(|char| *char == 0)
757        .ok_or(StringError::Null)?;
758
759    core::str::from_utf8(&bytes[..null_index]).map_err(StringError::Utf8)
760}
761
762#[cfg(test)]
763mod test {
764    extern crate alloc;
765
766    use super::*;
767    use crate::builder::Builder;
768    use crate::builder::BuilderConfig;
769    use crate::builder::StringId;
770    use crate::spec::ReserveEntry;
771    use alloc::format;
772    use alloc::string::String;
773    use alloc::vec;
774    use alloc::vec::Vec;
775    use zerocopy::IntoBytes;
776
777    #[derive(Debug, Clone, PartialEq, Eq)]
778    enum DtProp {
779        PropA(u64),
780        PropB(Vec<u8>),
781        Reg(u32),
782        SuperAwesomeProp(String),
783        PropList(Vec<u64>),
784    }
785
786    #[derive(Debug, PartialEq, Eq)]
787    struct DtNode {
788        name: String,
789        children: Vec<DtNode>,
790        properties: Vec<DtProp>,
791    }
792
793    #[derive(Debug, PartialEq, Eq)]
794    struct Dt {
795        boot_cpuid_phys: u32,
796        root: DtNode,
797        memory_reservations: Vec<ReserveEntry>,
798    }
799
800    struct PropIds {
801        propa: StringId,
802        propb: StringId,
803        reg: StringId,
804        saprop: StringId,
805        proplist: StringId,
806    }
807
808    macro_rules! build_fdt_props {
809        ($ids:expr, $node:expr, $builder:expr) => {{
810            let mut new_builder = $builder.start_node(&$node.name).unwrap();
811
812            for prop in &$node.properties {
813                new_builder = match &prop {
814                    DtProp::PropA(val) => new_builder.add_u64($ids.propa, *val).unwrap(),
815                    DtProp::PropB(val) => new_builder.add_prop_array($ids.propb, &[&val]).unwrap(),
816                    DtProp::Reg(val) => new_builder.add_u32($ids.reg, *val).unwrap(),
817                    DtProp::SuperAwesomeProp(val) => new_builder.add_str($ids.saprop, val).unwrap(),
818                    DtProp::PropList(val) => {
819                        // convert to BE first, since the underlying routines require BE data
820                        let big_endians = val
821                            .iter()
822                            .map(|v| {
823                                zerocopy::byteorder::U64::<zerocopy::byteorder::BigEndian>::new(*v)
824                            })
825                            .collect::<Vec<_>>();
826
827                        new_builder
828                            .add_prop_array(
829                                $ids.proplist,
830                                big_endians
831                                    .iter()
832                                    .map(|v| v.as_bytes())
833                                    .collect::<Vec<_>>()
834                                    .as_slice(),
835                            )
836                            .unwrap()
837                    }
838                };
839            }
840
841            new_builder
842        }};
843    }
844
845    impl Dt {
846        fn build_fdt(&self) -> Vec<u8> {
847            let mut buf = vec![0; 4096 * 256];
848            let memory_reservations = vec![ReserveEntry {
849                address: 1024.into(),
850                size: 2048.into(),
851            }];
852            let mut builder = Builder::new(BuilderConfig {
853                blob_buffer: buf.as_mut_slice(),
854                string_table_cap: 1024,
855                memory_reservations: &memory_reservations,
856            })
857            .unwrap();
858
859            let ids = PropIds {
860                propa: builder.add_string("prop-a").unwrap(),
861                propb: builder.add_string("test,prop-b").unwrap(),
862                reg: builder.add_string("reg").unwrap(),
863                saprop: builder.add_string("Awesome,super-prop").unwrap(),
864                proplist: builder.add_string("prop-list").unwrap(),
865            };
866
867            // build root
868            let root = &self.root;
869            let mut root_builder = build_fdt_props!(&ids, root, builder);
870
871            // build L1 nodes
872            for child in &root.children {
873                let mut child_builder = build_fdt_props!(&ids, child, root_builder);
874
875                // Build L2 nodes
876                for child_l2 in &child.children {
877                    child_builder = build_fdt_props!(&ids, child_l2, child_builder)
878                        .end_node()
879                        .unwrap();
880
881                    assert!(child_l2.children.is_empty());
882                }
883
884                root_builder = child_builder.end_node().unwrap();
885            }
886
887            let builder = root_builder.end_node().unwrap();
888
889            let len = builder.build(self.boot_cpuid_phys).unwrap();
890            buf.truncate(len);
891            buf
892        }
893
894        fn from_fdt(buf: &[u8]) -> Self {
895            let parser = Parser::new(buf).unwrap();
896
897            let parse_props = |parser: &Node<'_>, node: &mut DtNode| {
898                for prop in parser.properties() {
899                    let prop = prop.unwrap();
900                    let name = prop.name;
901
902                    let dt_prop = match name {
903                        "prop-a" => DtProp::PropA(prop.read_u64(0).unwrap()),
904                        "test,prop-b" => DtProp::PropB(prop.data.into()),
905                        "reg" => DtProp::Reg(prop.read_u32(0).unwrap()),
906                        "Awesome,super-prop" => {
907                            DtProp::SuperAwesomeProp(prop.read_str().unwrap().into())
908                        }
909                        "prop-list" => {
910                            let mut list = vec![];
911                            for val in prop.as_64_list().unwrap() {
912                                list.push(val);
913                            }
914                            DtProp::PropList(list)
915                        }
916                        _ => panic!("unexpected name {}", name),
917                    };
918
919                    node.properties.push(dt_prop);
920                }
921            };
922
923            let root = parser.root().unwrap();
924            let mut p_root = DtNode {
925                name: root.name.into(),
926                children: vec![],
927                properties: vec![],
928            };
929
930            parse_props(&root, &mut p_root);
931
932            for child in root.children() {
933                let child = child.unwrap();
934
935                let mut p_child = DtNode {
936                    name: child.name.into(),
937                    children: vec![],
938                    properties: vec![],
939                };
940
941                parse_props(&child, &mut p_child);
942
943                for child_l2 in child.children() {
944                    let child_l2 = child_l2.unwrap();
945
946                    let mut p_child_l2 = DtNode {
947                        name: child_l2.name.into(),
948                        children: vec![],
949                        properties: vec![],
950                    };
951
952                    parse_props(&child_l2, &mut p_child_l2);
953
954                    assert!(child_l2.children().next().is_none());
955
956                    p_child.children.push(p_child_l2);
957                }
958
959                p_root.children.push(p_child);
960            }
961
962            let mut memory_reservations = vec![];
963            parser.memory_reservations().for_each(|entry| {
964                memory_reservations.push(entry.unwrap());
965            });
966
967            Dt {
968                boot_cpuid_phys: parser.boot_cpuid_phys,
969                root: p_root,
970                memory_reservations,
971            }
972        }
973    }
974
975    fn cpu_node(num: usize, apic_id: u32) -> DtNode {
976        DtNode {
977            name: format!("cpu@{}", num),
978            properties: vec![DtProp::Reg(apic_id)],
979            children: vec![],
980        }
981    }
982
983    #[test]
984    fn test_simple_dt() {
985        let dt = Dt {
986            boot_cpuid_phys: 0,
987            root: DtNode {
988                name: "".into(),
989                children: vec![DtNode {
990                    name: "cpus".into(),
991                    children: (0..10).map(|i| cpu_node(i, (i + 10) as u32)).collect(),
992                    properties: vec![DtProp::SuperAwesomeProp("super".into())],
993                }],
994                properties: vec![
995                    DtProp::PropA(0x123456789abcdef),
996                    DtProp::PropB(vec![]),
997                    DtProp::PropB(vec![1]),
998                    DtProp::Reg(0xabcdef),
999                    DtProp::SuperAwesomeProp("this is a string!".into()),
1000                    DtProp::PropList(vec![1, 2, 3, 4, 5]),
1001                    DtProp::PropA(0x223456789abcdef),
1002                ],
1003            },
1004            memory_reservations: vec![ReserveEntry {
1005                address: 1024.into(),
1006                size: 2048.into(),
1007            }],
1008        };
1009
1010        let fdt = dt.build_fdt();
1011        let parsed_dt = Dt::from_fdt(&fdt);
1012        assert_eq!(dt, parsed_dt);
1013    }
1014}
fdt/parser.rs

fdt/
parser.rs
