Refactor DeviceTree parsing.

5 files changed, 518 insertions, 130 deletions

diff --git a/kernel/src/allocators.rs b/kernel/src/allocators/mod.rs
index e69de29..e69de29 100644
--- a/kernel/src/allocators.rs
+++ b/kernel/src/allocators/mod.rs
diff --git a/kernel/src/collections/stack_linked_list.rs b/kernel/src/collections/stack_linked_list.rs
index ce9ee8e..19b9272 100644
--- a/kernel/src/collections/stack_linked_list.rs
+++ b/kernel/src/collections/stack_linked_list.rs
@@ -4,7 +4,7 @@ use core::fmt;
 
 /// A linked list whose nodes can be stack-allocated.
 #[derive(Clone, Copy, Eq, Ord, PartialEq, PartialOrd)]
-pub struct StackLinkedList<'list, T>(pub Option<(T, &'list StackLinkedList<'list, T>)>);
+pub struct StackLinkedList<'list, T>(Option<(T, &'list StackLinkedList<'list, T>)>);
 
 impl<'list, T> StackLinkedList<'list, T> {
     /// An empty linked list.
@@ -15,6 +15,12 @@ impl<'list, T> StackLinkedList<'list, T> {
         StackLinkedList(Some((head, self)))
     }
 
+    /// Attempts to return the head and tail of the list.
+    pub fn uncons(&self) -> Option<(&T, &'list StackLinkedList<'list, T>)> {
+        let (hd, tl) = self.0.as_ref()?;
+        Some((hd, tl))
+    }
+
     /// Returns an iterator over the elements in the list.
     pub fn iter<'iter: 'list>(&'iter self) -> impl 'iter + Iterator<Item = &'list T> {
         struct Iter<'iter, 'list, T>(&'iter StackLinkedList<'list, T>);
@@ -42,3 +48,31 @@ impl<'list, T: fmt::Debug> fmt::Debug for StackLinkedList<'list, T> {
         fmt.debug_list().entries(self.iter()).finish()
     }
 }
+
+impl<'list, T: Copy> IntoIterator for StackLinkedList<'list, T> {
+    type Item = T;
+
+    type IntoIter = OwnedIter<'list, T>;
+
+    fn into_iter(self) -> OwnedIter<'list, T> {
+        OwnedIter(self)
+    }
+}
+
+/// An (owned) iterator over a `StackLinkedList`.
+#[derive(Clone)]
+pub struct OwnedIter<'list, T>(StackLinkedList<'list, T>);
+
+impl<'list, T: Copy> Iterator for OwnedIter<'list, T> {
+    type Item = T;
+
+    fn next(&mut self) -> Option<T> {
+        match (self.0).0 {
+            Some((hd, tl)) => {
+                self.0 = *tl;
+                Some(hd)
+            }
+            None => None,
+        }
+    }
+}
diff --git a/kernel/src/device_tree.rs b/kernel/src/device_tree.rs
index d843234..5fdc3e9 100644
--- a/kernel/src/device_tree.rs
+++ b/kernel/src/device_tree.rs
@@ -1,9 +1,14 @@
 //! Support for the DeviceTree format.
 
-use crate::collections::stack_linked_list::StackLinkedList;
+use crate::{collections::stack_linked_list::StackLinkedList, prelude::*, util::FromEndianBytes};
 use bstr::BStr;
 use contracts::requires;
-use core::{fmt, iter, slice};
+use core::{
+    fmt, iter,
+    num::ParseIntError,
+    slice,
+    str::{self, Utf8Error},
+};
 use either::Either;
 
 /// A reference to a flattened DeviceTree (DTB) in memory.
@@ -77,16 +82,26 @@ impl<'dt> FlattenedDeviceTree<'dt> {
             memrsv_count += 1;
         };
 
-        Ok(FlattenedDeviceTree {
+        // Try parsing all of the events in the structure block, so we can report errors from doing
+        // so before anything outside this module can get their hands on them.
+        let fdt = FlattenedDeviceTree {
             header,
             struct_block,
             strings_block,
             memrsv_block,
-        })
+        };
+        fdt.iter_struct_events_from(0)
+            .try_for_each(|r| r.map(|_| ()))?;
+
+        // Check that the overall structure of the structure block is correct, so we don't need to
+        // worry about errors later.
+        for_each_node(&fdt, &mut |_| Ok(()), &|err| err, 0, StackLinkedList::NIL)?;
+
+        Ok(fdt)
     }
 
     /// Returns the string at the given offset of the strings block.
-    pub fn get_string(&self, offset: u32) -> Result<&BStr, DeviceTreeError> {
+    fn get_string(&self, offset: u32) -> Result<&BStr, DeviceTreeError> {
         let out = &self.strings_block[offset as usize..];
         let i = out
             .iter()
@@ -95,31 +110,66 @@ impl<'dt> FlattenedDeviceTree<'dt> {
         Ok(&out[..i])
     }
 
-    /// Iterates over the properties stored in the DeviceTree, only allocating memory on the stack.
-    pub fn for_each_property<'iter: 'dt, E>(
-        &'iter self,
-        mut func: impl for<'a> FnMut(FdtNodePath<'dt, 'a>, &'dt BStr, &'dt BStr) -> Result<(), E>,
-    ) -> Result<(), Either<DeviceTreeError, E>> {
-        for_each_property(
-            &mut self.struct_events().peekable(),
+    /// Parses nodes out of a flattened DeviceTree and calls the function with each one. This does
+    /// not allocate memory, and may be called before the allocator is configured (at the cost of
+    /// decreased performance).
+    pub fn for_each_node<E>(
+        &'dt self,
+        mut func: impl for<'a> FnMut(FdtNode<'dt, 'a>) -> Result<(), E>,
+    ) -> Result<(), E> {
+        for_each_node(
+            self,
             &mut func,
+            &|_| unreachable!("checked in FlattenedDeviceTree::from_ptr"),
+            0,
             StackLinkedList::NIL,
-        )
+        )?;
+        Ok(())
     }
 
-    /// Returns an iterator over the events in the flattened DeviceTree's structure block.
-    pub fn struct_events<'iter: 'dt>(
+    /// Returns an iterator over the events in the structure block of the DeviceTree, starting at
+    /// the current offset from the start of the structure block.
+    ///
+    /// Panics if the offset is out-of-bounds.
+    fn iter_struct_events_from<'iter: 'dt>(
         &'iter self,
+        start: u32,
     ) -> impl 'iter + Iterator<Item = Result<FdtStructEvent<'dt>, DeviceTreeError>> {
-        let mut ptr = self.struct_block;
-        iter::from_fn(move || loop {
-            break match u32::from_be(ptr[0]) {
+        let mut i = start;
+        iter::from_fn(move || match self.next_struct_event_from(i) {
+            Some(Ok((next, event))) => {
+                let prev = i;
+                assert!(prev < next);
+                i = next;
+                Some(Ok(event))
+            }
+            Some(Err(err)) => Some(Err(err)),
+            None => None,
+        })
+    }
+
+    /// Parses a single point in the structure block of the DeviceTree, returning the offset to
+    /// parse at next and the parse event.
+    ///
+    /// Panics if the offset is out-of-bounds.
+    fn next_struct_event_from<'iter: 'dt>(
+        &'iter self,
+        mut offset: u32,
+    ) -> Option<Result<(u32, FdtStructEvent<'dt>), DeviceTreeError>> {
+        loop {
+            // Read the token type and advance the offset.
+            let token_type = u32::from_be(*self.struct_block.get(offset as usize)?);
+            offset += 1;
+
+            // Branch on the token type to recognize an event.
+            let event = match token_type {
                 // FDT_BEGIN_NODE
                 0x00000001 => {
                     // Save a pointer to the start of the extra data.
-                    let name_ptr = (&ptr[1]) as *const u32 as *const u8;
+                    let name_ptr = (&self.struct_block[offset as usize]) as *const u32 as *const u8;
 
-                    // Look for a null terminator.
+                    // Look for a null terminator. `name_len` is the length of the name, _without_
+                    // the null terminator.
                     //
                     // SAFETY: This method can only be called when the FlattenedDeviceTree was
                     // constructed from a valid flattened DeviceTree.
@@ -135,58 +185,62 @@ impl<'dt> FlattenedDeviceTree<'dt> {
                     // flattened DeviceTree.
                     let name = BStr::new(unsafe { slice::from_raw_parts(name_ptr, name_len) });
 
-                    // Advance the pointer.
-                    let extra_data_count = (name_len + 4) >> 2;
-                    ptr = &ptr[1 + extra_data_count..];
+                    // Parse the name.
+                    let Ok(name) = FdtNodeName::parse(name) else {
+                        return Some(Err(DeviceTreeError::InvalidNodeName));
+                    };
 
-                    // Return the event.
-                    Some(Ok(FdtStructEvent::BeginNode(name)))
-                }
-                // FDT_END_NODE
-                0x00000002 => {
-                    // Advance the pointer.
-                    ptr = &ptr[1..];
+                    // Compute the count and advance the offset.
+                    offset += (name_len as u32 + 4) >> 2;
 
-                    // Return the event.
-                    Some(Ok(FdtStructEvent::EndNode))
+                    // Create the event.
+                    FdtStructEvent::BeginNode(name)
                 }
+                // FDT_END_NODE
+                0x00000002 => FdtStructEvent::EndNode,
                 // FDT_PROP
                 0x00000003 => {
                     // Get the length of the property data and the offset of the name in the
                     // strings block.
-                    let len = u32::from_be(ptr[1]) as usize;
-                    let name_off = u32::from_be(ptr[2]);
+                    let data_len = u32::from_be(self.struct_block[offset as usize]) as usize;
+                    let name_off = u32::from_be(self.struct_block[offset as usize + 1]);
+                    offset += 2;
 
                     // Get the property data as a BStr.
                     //
                     // SAFETY: This is valid by the requirements of a flattened DeviceTree.
+                    //
+                    // TODO: We could refactor this out to a to_bytes call plus a bounds-checked
+                    // slicing operation to get a _bit_ of safety back, at least...
                     let data = BStr::new(unsafe {
-                        slice::from_raw_parts(&ptr[3] as *const u32 as *const u8, len)
+                        slice::from_raw_parts(
+                            &self.struct_block[offset as usize] as *const u32 as *const u8,
+                            data_len,
+                        )
                     });
 
+                    // Advance past the property data.
+                    offset += (data_len as u32 + 3) >> 2;
+
                     // Get the property name as a BStr.
                     let name = match self.get_string(name_off) {
                         Ok(name) => name,
-                        Err(err) => break Some(Err(err)),
+                        Err(err) => return Some(Err(err)),
                     };
 
-                    // Advance the pointer.
-                    let data_count = (len + 3) >> 2;
-                    ptr = &ptr[3 + data_count..];
-
-                    // Return the event.
-                    Some(Ok(FdtStructEvent::Prop(name, data)))
+                    // Create the event.
+                    FdtStructEvent::Prop(name, data)
                 }
                 // FDT_NOP
-                0x00000004 => {
-                    ptr = &ptr[1..];
-                    continue;
-                }
+                0x00000004 => continue,
                 // FDT_END
-                0x00000009 => None,
-                token_type => Some(Err(DeviceTreeError::InvalidTokenType(token_type))),
+                0x00000009 => return None,
+                _ => return Some(Err(DeviceTreeError::InvalidTokenType(token_type))),
             };
-        })
+
+            // Return the new offset and the event.
+            return Some(Ok((offset, event)));
+        }
     }
 }
 
@@ -196,6 +250,7 @@ pub enum DeviceTreeError {
     BadMagic(u32),
     IncompatibleVersion(u32, u32),
     InvalidDeviceTree,
+    InvalidNodeName,
     InvalidTokenType(u32),
     StringMissingNulTerminator(u32),
 
@@ -203,43 +258,6 @@ pub enum DeviceTreeError {
     UnexpectedEvent,
 }
 
-fn for_each_property<'dt, E>(
-    events: &mut iter::Peekable<impl Iterator<Item = Result<FdtStructEvent<'dt>, DeviceTreeError>>>,
-    func: &mut impl for<'a> FnMut(FdtNodePath<'dt, 'a>, &'dt BStr, &'dt BStr) -> Result<(), E>,
-    node: StackLinkedList<&'dt BStr>,
-) -> Result<(), Either<DeviceTreeError, E>> {
-    // Read the first event, which should be the BeginNode starting the node we're trying to read.
-    let event = events
-        .next()
-        .ok_or(Either::Left(DeviceTreeError::UnexpectedEndOfStructBlock))?
-        .map_err(Either::Left)?;
-    let FdtStructEvent::BeginNode(node_name) = event else {
-        return Err(Either::Left(DeviceTreeError::UnexpectedEvent));
-    };
-    let node = node.cons(node_name);
-
-    // Parse properties and subnodes until we get to the end.
-    loop {
-        if matches!(events.peek(), Some(Ok(FdtStructEvent::BeginNode(_)))) {
-            for_each_property(events, func, node)?;
-        } else {
-            let event = events
-                .next()
-                .ok_or(Either::Left(DeviceTreeError::UnexpectedEndOfStructBlock))?
-                .map_err(Either::Left)?;
-            match event {
-                FdtStructEvent::BeginNode(_) => {
-                    return Err(Either::Left(DeviceTreeError::UnexpectedEvent))
-                }
-                FdtStructEvent::EndNode => break Ok(()),
-                FdtStructEvent::Prop(prop, value) => {
-                    func(FdtNodePath(node), prop, value).map_err(Either::Right)?
-                }
-            }
-        }
-    }
-}
-
 /// The flattened DeviceTree header.
 ///
 /// All fields are big-endian.
@@ -270,39 +288,328 @@ struct FdtMemRsv {
 
 /// An event returned from iterating over the structure block of a flattened DeviceTree.
 #[derive(Clone, Copy, Debug)]
-pub enum FdtStructEvent<'dt> {
-    BeginNode(&'dt BStr),
+enum FdtStructEvent<'dt> {
+    BeginNode(FdtNodeName<'dt>),
     EndNode,
     Prop(&'dt BStr, &'dt BStr),
 }
 
-/// The path to a node. Note that the list this contains is in _reverse_ order.
-#[derive(Debug, Eq, PartialEq)]
-pub struct FdtNodePath<'dt, 'list>(pub StackLinkedList<'list, &'dt BStr>);
+/// The name of a node.
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+pub struct FdtNodeName<'dt> {
+    /// The full name, including the unit address.
+    pub full_name: &'dt BStr,
+
+    // The length of the unit name (i.e., the part of the name before the unit address).
+    unit_name_len: usize,
+
+    /// The address of the node.
+    pub unit_address: Option<u64>,
+}
+
+impl<'dt> FdtNodeName<'dt> {
+    /// Returns the unit name; i.e., the part of the name that does not include the unit address.
+    pub fn unit_name(&self) -> &'dt BStr {
+        &self.full_name[..self.unit_name_len]
+    }
 
-impl<'dt, 'list> fmt::Display for FdtNodePath<'dt, 'list> {
+    /// Parses an `FdtNodeName` from bytes.
+    pub fn parse(bytes: &'dt BStr) -> Result<FdtNodeName<'dt>, Either<ParseIntError, Utf8Error>> {
+        if let Some(at_sign_index) = bytes.iter().position(|&b| b == b'@') {
+            let unit_address =
+                str::from_utf8(&bytes[at_sign_index + 1..]).map_err(Either::Right)?;
+            let unit_address = u64::from_str_radix(unit_address, 16).map_err(Either::Left)?;
+            Ok(FdtNodeName {
+                full_name: bytes,
+                unit_name_len: at_sign_index,
+                unit_address: Some(unit_address),
+            })
+        } else {
+            Ok(FdtNodeName {
+                full_name: bytes,
+                unit_name_len: bytes.len(),
+                unit_address: None,
+            })
+        }
+    }
+}
+
+impl<'dt> fmt::Display for FdtNodeName<'dt> {
     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
-        match (self.0).0 {
-            Some((hd, tl)) => write!(fmt, "{}{}/", FdtNodePath(*tl), hd),
-            None => Ok(()),
+        write!(fmt, "{}", self.full_name)
+    }
+}
+
+/// A reference to a node in a flattened DeviceTree.
+#[derive(Clone, Copy)]
+pub struct FdtNode<'dt, 'iter> {
+    fdt: &'dt FlattenedDeviceTree<'dt>,
+    index: u32,
+    parents: StackLinkedList<'iter, u32>,
+}
+
+impl<'dt, 'iter> FdtNode<'dt, 'iter> {
+    /// A constructor that checks the type's invariants.
+    #[requires(matches!(
+        fdt.next_struct_event_from(index),
+        Some(Ok((_, FdtStructEvent::BeginNode(_)))))
+    )]
+    #[requires(parents.into_iter().all(|parent| {
+        matches!(
+            fdt.next_struct_event_from(parent),
+            Some(Ok((_, FdtStructEvent::BeginNode(_))))
+        )
+    }))]
+    fn new(
+        fdt: &'dt FlattenedDeviceTree<'dt>,
+        index: u32,
+        parents: StackLinkedList<'iter, u32>,
+    ) -> FdtNode<'dt, 'iter> {
+        FdtNode {
+            fdt,
+            index,
+            parents,
+        }
+    }
+
+    /// Returns the value corresponding to a prop name for this node.
+    pub fn get_prop<U>(&self, name: U) -> Option<&'dt BStr>
+    where
+        BStr: PartialEq<U>,
+    {
+        self.iter_props().find(|&(k, _)| k == &name).map(|(_, v)| v)
+    }
+
+    /// Returns the value corresponding to a prop name for this node as a big-endian `u32`.
+    pub fn get_prop_u32<U>(&self, name: U) -> Option<u32>
+    where
+        BStr: PartialEq<U>,
+        U: Copy + fmt::Display,
+    {
+        let value = self.get_prop(name)?;
+        if value.len() != 4 {
+            warn!(
+                "{}{} was expected to be 4 bytes, but was {:?}",
+                self.name(),
+                name,
+                value
+            );
+            return None;
+        }
+        let value = value.first_chunk()?;
+        Some(u32::from_be_bytes(*value))
+    }
+
+    /// Returns the `reg` property of this node as an iterator over `(addr, size)` pairs.
+    pub fn get_reg(&self) -> Option<impl Iterator<Item = (&'dt BStr, &'dt BStr)>> {
+        // Get the parent node.
+        let Some(parent) = self.parent() else {
+            warn!("{} did not have a parent", self.name());
+            return None;
+        };
+
+        // Get the size of addresses and sizes from the parent.
+        let Some(address_cells) = parent.get_prop_u32("#address-cells") else {
+            warn!(
+                "{} did not have a valid #address-cells property",
+                parent.name()
+            );
+            return None;
+        };
+        let Some(size_cells) = parent.get_prop_u32("#size-cells") else {
+            warn!(
+                "{} did not have a valid #size-cells property",
+                parent.name()
+            );
+            return None;
+        };
+
+        // Convert the numbers to bytes.
+        let address_size = (address_cells << 2) as usize;
+        let size_size = (size_cells << 2) as usize;
+
+        // Get the `reg` property's value.
+        let value = self.get_prop("reg")?;
+        if value.len() % (address_size + size_size) != 0 {
+            warn!(
+                "{}reg was expected to be a multiple of ({} + {}) bytes, but was {:?}",
+                self.name(),
+                address_size,
+                size_size,
+                value,
+            );
+            return None;
+        }
+
+        Some(
+            (0..value.len())
+                .step_by(address_size + size_size)
+                .map(move |i| {
+                    (
+                        &value[i..i + address_size],
+                        &value[i + address_size..i + address_size + size_size],
+                    )
+                }),
+        )
+    }
+
+    /// Returns the `reg` property of this node as an iterator over `(addr, size)` pairs, requiring
+    /// that they're correctly-sized for `usize`s.
+    pub fn get_reg_usize(&self) -> Option<impl 'dt + Iterator<Item = (usize, usize)>> {
+        let iter = self.get_reg()?.map(|(addr, size)| {
+            (
+                usize::from_big_endian_bytes(addr),
+                usize::from_big_endian_bytes(size),
+            )
+        });
+        Some(iter)
+    }
+
+    /// Returns whether the unit path (i.e., the path to this node, only taking unit names) matches
+    /// the argument.
+    pub fn is_unit<U>(&self, name: &[U]) -> bool
+    where
+        BStr: PartialEq<U>,
+    {
+        self.iter_names_rev()
+            .map(|name| name.unit_name())
+            .eq(name.iter().rev())
+    }
+
+    /// Returns an iterator over the properties of the node.
+    pub fn iter_props(&self) -> impl '_ + Iterator<Item = (&'dt BStr, &'dt BStr)> {
+        // Skip the BeginNode.
+        let offset = match self.fdt.next_struct_event_from(self.index) {
+            Some(Ok((offset, FdtStructEvent::BeginNode(_)))) => offset,
+            _ => unreachable!("checked in FlattenedDeviceTree::from_ptr"),
+        };
+
+        // Yield Prop nodes as long as we can get them.
+        self.fdt
+            .iter_struct_events_from(offset)
+            .map_while(|r| match r {
+                Ok(FdtStructEvent::Prop(key, value)) => Some((key, value)),
+                Ok(FdtStructEvent::BeginNode(_) | FdtStructEvent::EndNode) => None,
+                Err(_) => unreachable!("checked in FlattenedDeviceTree::from_ptr"),
+            })
+    }
+
+    /// Returns a value that can be `Display`ed as the fully-qualified name of the node.
+    pub fn name(&self) -> impl '_ + fmt::Display {
+        struct NameDisplay<'a, 'dt, 'iter>(&'a FdtNode<'dt, 'iter>);
+
+        impl<'a, 'dt, 'iter> fmt::Display for NameDisplay<'a, 'dt, 'iter> {
+            fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+                fn fmt_name_rev<'dt>(
+                    fmt: &mut fmt::Formatter,
+                    mut iter: impl Iterator<Item = FdtNodeName<'dt>>,
+                ) -> fmt::Result {
+                    match iter.next() {
+                        Some(name) => {
+                            fmt_name_rev(fmt, iter)?;
+                            write!(fmt, "{name}/")
+                        }
+                        None => Ok(()),
+                    }
+                }
+
+                fmt_name_rev(fmt, self.0.iter_names_rev())
+            }
         }
+
+        NameDisplay(self)
+    }
+
+    /// Returns the parent of this node.
+    pub fn parent(&self) -> Option<FdtNode<'dt, 'iter>> {
+        let (&hd, &tl) = self.parents.uncons()?;
+        Some(FdtNode::new(self.fdt, hd, tl))
+    }
+
+    /// Returns an iterator over the names of the node and its parents, in reverse order.
+    fn iter_names_rev(&self) -> impl '_ + Clone + Iterator<Item = FdtNodeName<'dt>> {
+        self.parents.cons(self.index).into_iter().map(move |i| {
+            match self.fdt.next_struct_event_from(i) {
+                Some(Ok((_, FdtStructEvent::BeginNode(name)))) => name,
+                _ => unreachable!("checked in FlattenedDeviceTree::from_ptr"),
+            }
+        })
     }
 }
 
-impl<'dt, 'list, U> PartialEq<[U]> for FdtNodePath<'dt, 'list>
-where
-    &'dt BStr: PartialEq<U>,
-{
-    fn eq(&self, other: &[U]) -> bool {
-        self.0.iter().eq(other.iter().rev())
+impl<'dt, 'iter> fmt::Debug for FdtNode<'dt, 'iter> {
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        write!(fmt, "{} ", self.name())?;
+        fmt.debug_map().entries(self.iter_props()).finish()
     }
 }
 
-impl<'dt, 'list, U, const N: usize> PartialEq<[U; N]> for FdtNodePath<'dt, 'list>
-where
-    &'dt BStr: PartialEq<U>,
-{
-    fn eq(&self, other: &[U; N]) -> bool {
-        self.0.iter().eq(other.iter().rev())
+/// Parses nodes out of a flattened DeviceTree and calls the function with each one. This does not
+/// allocate memory, and may be called before the allocator is configured (at the cost of decreased
+/// performance). Returns the offset after parsing the one starting at `index`.
+///
+/// - `'dt` is the lifetime of the DeviceTree.
+/// - `'a` is the lifetime of this function call.
+/// - `'b` is the lifetime of the recursive call to this function that parses its children.
+///
+/// - `E` is the type of errors. We do a pass in `FlattenedDeviceTree::from_ptr` with this as
+///   `DeviceTreeError` (and a `func` that's a no-op) to find any errors we might encounter. In
+///   actual user invocations of this function, it's replaced with the actual user error type (and
+///   `on_error` panics).
+///
+/// - `fdt` is flattened DeviceTree we're parsing inside.
+/// - `func` is the callback to call with nodes.
+/// - `on_error` is a function to call to convert a `DeviceTreeError` to an `E`.
+/// - `index` is the index of the word in the structure block to start parsing at.
+/// - `parents` is an accumulated list of the indices of nodes that are parents of this one.
+fn for_each_node<'dt, 'iter, E>(
+    fdt: &'dt FlattenedDeviceTree<'dt>,
+    func: &mut impl for<'a> FnMut(FdtNode<'dt, 'a>) -> Result<(), E>,
+    on_error: &impl Fn(DeviceTreeError) -> E,
+    index: u32,
+    parents: StackLinkedList<'iter, u32>,
+) -> Result<u32, E> {
+    // Read the first event, which should be the BeginNode starting the node we're trying to read.
+    // We need to ensure that `index` refers to a `BeginNode` so that methods on `FdtNode` (e.g.
+    // `iter_names_rev`) can rely on this. We also take as an inductive invariant that every index
+    // in `parents` refers to a valid `BeginNode`.
+    let (mut offset, event) = fdt
+        .next_struct_event_from(index)
+        .ok_or_else(|| on_error(DeviceTreeError::UnexpectedEndOfStructBlock))?
+        .unwrap_or_else(|_| unreachable!("checked in FlattenedDeviceTree::from_ptr"));
+    if !matches!(event, FdtStructEvent::BeginNode(_)) {
+        dbg!((event, index, parents));
+        return Err(on_error(DeviceTreeError::UnexpectedEvent));
+    }
+
+    // Create the node and call the callback with it.
+    func(FdtNode::new(fdt, index, parents))?;
+
+    // Create a new parents list that includes this node.
+    let new_parents = parents.cons(index);
+
+    // Advance past any prop events.
+    loop {
+        let (next_offset, event) = fdt
+            .next_struct_event_from(offset)
+            .ok_or_else(|| on_error(DeviceTreeError::UnexpectedEndOfStructBlock))?
+            .unwrap_or_else(|_| unreachable!("checked in FlattenedDeviceTree::from_ptr"));
+        if !matches!(event, FdtStructEvent::Prop(_, _)) {
+            break;
+        }
+        offset = next_offset;
+    }
+
+    // Until we find an end node, parse child nodes.
+    loop {
+        let (next_offset, event) = fdt
+            .next_struct_event_from(offset)
+            .ok_or_else(|| on_error(DeviceTreeError::UnexpectedEndOfStructBlock))?
+            .unwrap_or_else(|_| unreachable!("checked in FlattenedDeviceTree::from_ptr"));
+        if matches!(event, FdtStructEvent::EndNode) {
+            break Ok(next_offset);
+        }
+
+        offset = for_each_node(fdt, func, on_error, offset, new_parents)?;
     }
 }
diff --git a/kernel/src/lib.rs b/kernel/src/lib.rs
index 840f397..bc5c5c0 100644
--- a/kernel/src/lib.rs
+++ b/kernel/src/lib.rs
@@ -25,44 +25,47 @@ use crate::prelude::*;
 ///   `device_tree::FlattenedDeviceTree::from_ptr` for the precise requirements.
 /// - This must be called in supervisor mode with paging and traps disabled, but with all traps
 ///   delegated to supervisor mode.
+/// - Any other harts must not be running concurrently with us. TODO: Define their state.
 #[no_mangle]
 pub unsafe extern "C" fn hart0_boot(device_tree: *const u8) -> ! {
+    // Set up the logger.
+    //
+    // TODO: This should really be named something better than console.
     console::init();
 
-    info!("device_tree = {device_tree:?}");
+    // Parse the DeviceTree.
     let flattened_device_tree = unsafe { device_tree::FlattenedDeviceTree::from_ptr(device_tree) }
         .expect("invalid DeviceTree");
-    for event in flattened_device_tree.struct_events() {
-        let event = event.expect("invalid DeviceTree");
-        dbg!(event);
-    }
 
-    // Set up the allocator and the timer subsystem.
-    //
-    // TODO: The timer really oughta be later...
+    // Find the available physical memory areas and initialize the physical memory
+    // free-list.
     flattened_device_tree
-        .for_each_property(|node, prop, value| {
-            if node == ["", "cpus"] && prop == "timebase-frequency" {
-                if value.len() == 4 {
-                    let value = [value[0], value[1], value[2], value[3]];
-                    let timebase_frequency = u32::from_be_bytes(value);
-                    // SAFETY: Nobody is concurrently running, so they can't be concurrently
-                    // modifying this.
+        .for_each_node(|node| {
+            if node.is_unit(&["", "cpus"]) {
+                // TODO: Do this later.
+                if let Some(timebase_frequency) = node.get_prop_u32("timebase-frequency") {
+                    // SAFETY: Other harts are not concurrently running, so they can't be
+                    // concurrently accessing or modifying this.
                     unsafe {
                         drivers::riscv_timer::TIMEBASE_FREQUENCY = timebase_frequency;
                     }
-                    dbg!(timebase_frequency);
-                } else {
-                    warn!("/cpus/timebase-frequency was not a 4-byte quantity");
                 }
-            } else {
-                info!("{node}{prop} = {value:?}");
+            } else if node.is_unit(&["", "memory"]) {
+                // Get the memory ranges.
+                let Some(reg) = node.get_reg_usize() else {
+                    warn!("{}reg was not valid", node.name());
+                    return Ok(());
+                };
+
+                for (addr, size) in reg {
+                    info!("found memory: addr = {addr:#x}, size = {size:#x}");
+                }
             }
             Ok(())
         })
-        .map_err(|err| err.left_or_else(|void| void::unreachable(void)))
-        .expect("invalid DeviceTree");
+        .unwrap_or_else(|err| void::unreachable(err));
 
+    // After this point, everything else is for debugging.
     interrupts::example_timer();
     info!("sleeping forever...");
     loop {
diff --git a/kernel/src/util.rs b/kernel/src/util.rs
index 93c684d..29042c8 100644
--- a/kernel/src/util.rs
+++ b/kernel/src/util.rs
@@ -1,5 +1,7 @@
 //! Miscellaneous utilities.
 
+use core::mem::size_of;
+
 #[cold]
 #[inline(always)]
 fn cold() {}
@@ -48,3 +50,45 @@ macro_rules! dbg {
         ($($crate::dbg!($expr)),+,)
     };
 }
+
+/// A trait for types that can be converted to from big-endian or little-endian byte slices.
+pub trait FromEndianBytes {
+    /// Converts from a big-endian byte slice.
+    fn from_big_endian_bytes(bytes: &[u8]) -> Self;
+
+    /// Converts from a little-endian byte slice.
+    fn from_little_endian_bytes(bytes: &[u8]) -> Self;
+}
+
+macro_rules! impl_FromEndianBytes {
+    ($($ty:ty),* $(,)?) => {
+        $(impl FromEndianBytes for $ty {
+            fn from_big_endian_bytes(bytes: &[u8]) -> $ty {
+                let chunk = match bytes.last_chunk() {
+                    Some(chunk) => *chunk,
+                    None => {
+                        let mut chunk = [0; size_of::<$ty>()];
+                        chunk[size_of::<$ty>() - bytes.len()..]
+                            .copy_from_slice(bytes);
+                        chunk
+                    },
+                };
+                <$ty>::from_be_bytes(chunk)
+            }
+
+            fn from_little_endian_bytes(bytes: &[u8]) -> $ty {
+                let chunk = match bytes.first_chunk() {
+                    Some(chunk) => *chunk,
+                    None => {
+                        let mut chunk = [0; size_of::<$ty>()];
+                        chunk[.. bytes.len()].copy_from_slice(bytes);
+                        chunk
+                    },
+                };
+                <$ty>::from_le_bytes(chunk)
+            }
+        })*
+    };
+}
+
+impl_FromEndianBytes!(i8, i16, i32, i64, isize, u8, u16, u32, u64, usize);