Repository navigation
Visiting every node through children() takes time quadratic in depth #102
Description
Found while comparing dtoolkit against another device tree parser.
Version: dtoolkit 0.4.1.
What happens. Visiting every node through children() takes time quadratic in the depth of the tree. FdtChildIter::next finds the next sibling with next_sibling_offset, which walks the whole subtree of the previous child, so a depth-first visit costs the sum of all subtree sizes. Fdt::new itself stays linear.
Expected. A visit of every node in time linear in the size of the blob.
Reproduction. A chain of nested nodes named a, visited depth-first with an explicit stack of children() iterators (release build, Linux x86_64):
/// Builds a version-17 FDT blob from a structure block and a strings block.
pub fn blob(structure: &[u8], strings: &[u8]) -> Vec<u8> {
let off_struct = 40 + 16; // header, then one empty reservation entry
let off_strings = off_struct + structure.len();
let total = off_strings + strings.len();
let mut b = Vec::new();
for v in [0xd00dfeed, total, off_struct, off_strings, 40, 17, 16, 0, strings.len(), structure.len()] {
b.extend_from_slice(&(v as u32).to_be_bytes());
}
b.extend_from_slice(&[0; 16]);
b.extend_from_slice(structure);
b.extend_from_slice(strings);
b
}
pub fn token(s: &mut Vec<u8>, t: u32) {
s.extend_from_slice(&t.to_be_bytes());
}
/// FDT_BEGIN_NODE with a padded name.
pub fn begin(s: &mut Vec<u8>, name: &str) {
token(s, 1);
s.extend_from_slice(name.as_bytes());
s.push(0);
while s.len() % 4 != 0 {
s.push(0);
}
}use dtoolkit::Node;
use dtoolkit::fdt::Fdt;
use repro::*;
use std::time::Instant;
fn chain(depth: usize) -> Vec<u8> {
let mut s = Vec::new();
begin(&mut s, "");
for _ in 0..depth {
begin(&mut s, "a");
}
for _ in 0..=depth {
token(&mut s, 2);
}
token(&mut s, 9);
blob(&s, &[])
}
fn main() {
for depth in [1_000, 10_000, 50_000] {
let b = chain(depth);
let fdt = Fdt::new(&b).unwrap();
let t = Instant::now();
let mut stack = vec![fdt.root().children()];
let mut nodes = 0usize;
while let Some(it) = stack.last_mut() {
match it.next() {
Some(child) => {
nodes += 1;
stack.push(child.children());
}
None => {
stack.pop();
}
}
}
println!("depth {depth}: {} bytes, visited {nodes} nodes in {:?}", b.len(), t.elapsed());
}
}Output:
depth 1000: 12072 bytes, visited 1000 nodes in 11.562087ms
depth 10000: 120072 bytes, visited 10000 nodes in 366.721512ms
depth 50000: 600072 bytes, visited 50000 nodes in 9.578380058s
A chain of about 174,000 nodes fits in 2 MiB (Linux's MAX_FDT_SIZE), passes Fdt::new in about 15 ms, and took about four minutes to visit in my measurements. A flat tree of the same size visits in about 12 ms.
Suggestion. When the previous child has been walked, the iterator could resume from where that walk ended, which makes a full visit linear. A flat, single-pass iterator over the structure block (each node with its depth) would also serve callers that want every node.
Activity
m4tx commentedon Oct 26, 2026
I believe this is closely related to #103. One way to fix this would be to provide an iterator over DTB "events" (where "event" is one of: start node, property, end node). We cannot really fix this directly in
children(), as by design this is an iterator over immediate descendants, and because of the flat structure of DTBs, there is no way to obtain the offset of the next sibling without walking through its entire subtree (at least not without extra memory, but using extra memory conflicts withFdtbeing a zero-copy, no-alloc parser).When we have an iterator that allows walking over the flat structure of the DTB, people could use it to achieve O(n) traversal, and we'd be able to implement
DisplayinO(n)as well without stack overflow problems and such.Thanks for reporting this; I'll try to tackle this in the coming weeks (you are also welcome to contribute a fix as well).