// Overlays: a tree that patches another tree.
//
// An overlay cannot know where the base tree put its nodes, so a reference in
// one is written as the reserved word 0xffffffff and recorded in
// `__fixups__` as a path to the property and the offset inside it. The loader
// reads the base tree's `__symbols__`, looks the label up, and patches the
// reserved word with the number the base gave that node.
//
// Two halves here: building an overlay from a plugin source (which is what dtc
// does with -@), and applying one to a base tree.
///|
/// The reserved word that stands in for a reference whose value only the base
/// tree knows.
const PHANDLE_PLACEHOLDER : UInt32 = 0xFFFF_FFFF
///|
/// Every way building or applying an overlay can fail.
pub(all) suberror OverlayError {
/// The overlay refers to a label the base tree does not export.
UnknownSymbol(label~ : String)
/// A fixup names a node path that is not in the tree it was applied to.
MissingTarget(path~ : String)
/// A fixup names a property or offset that does not hold a placeholder.
BadFixup(detail~ : String)
/// The base tree has no `/__symbols__`, so nothing can be resolved against
/// it.
NoSymbols
/// A fragment carries neither `target` nor `target-path`.
BadFragment(name~ : String)
/// A plugin could not be resolved for a reason other than a label the base
/// tree supplies.
Resolve(inner~ : ResolveError)
}
///|
/// Renders an overlay error.
pub impl Show for OverlayError with fn output(self, logger) {
let text = match self {
UnknownSymbol(label~) => "base tree does not export the symbol '\{label}'"
MissingTarget(path~) => "no node at '\{path}'"
BadFixup(detail~) => "bad fixup: \{detail}"
NoSymbols =>
"base tree has no /__symbols__; build it with -@ to export its labels"
BadFragment(name~) => "fragment \{name} has neither target nor target-path"
Resolve(inner~) => inner.to_string()
}
logger.write_string(text)
}
///|
/// Exposes the message as a plain method.
pub extend OverlayError with Show::{to_string, output}
///|
/// Builds an overlay from a plugin source.
///
/// The result is a normal blob whose `__fixups__` node lists where each
/// unresolved reference landed. dtc produces the same bytes for the same
/// source with `-@`.
///
/// Only references that resolve outside the overlay remain unresolved. A
/// plugin that refers to a label it defines itself gets a real phandle, which
/// is what dtc does too: the fixup list is for what the base tree has to
/// supply.
pub fn build_overlay(file : SourceFile) -> SourceFile raise OverlayError {
if !file.is_plugin {
raise BadFixup(detail="source is not marked /plugin/")
}
// Each `&label { ... }` patch becomes a `fragment@N` node holding a `target`
// reference and an `__overlay__` subtree. dtc numbers the fragments in
// source order starting at 0, and the fixups refer back to those names.
let fragments : Array[SourceNode] = []
let mut index = 0
for fragment in file.fragments {
let name = "fragment@\{index}"
let target_prop : SourceProperty = {
name: "target",
value: Value::{ parts: [fragment.target], },
span: fragment.span,
}
fragments.push({
name,
labels: [],
properties: [target_prop],
children: [fragment.node],
})
index = index + 1
}
let base_root = if file.fragments.length() > 0 {
// A plugin with patches does not also carry a root node in practice, but a
// file may have both; keeping the root's own children means neither is
// lost.
SourceNode::{
name: "",
labels: [],
properties: file.root.properties,
children: file.root.children.copy() + fragments,
}
} else {
file.root
}
// Resolution runs first for everything the plugin can resolve on its own.
// An unknown label is not a failure here: those are exactly the references
// the base tree is expected to supply, and they become fixups below.
let staged = ({ ..file, root: base_root, } : SourceFile)
let resolved = resolve_references(staged) catch {
UnknownLabel(_) => staged
e => raise Resolve(inner=e)
}
let fixups : Array[(String, String)] = []
let root = collect_plugin_fixups(resolved.root, "/", fixups)
let fixup_node = build_fixup_node(fixups)
let children = root.children.copy()
children.push(fixup_node)
{ ..resolved, root: { ..root, children, }, }
}
///|
/// Walks a plugin tree replacing unresolved references with the placeholder
/// word and recording where each one landed.
///
/// A fixup entry is the label mapped to `"/patch/node:property:offset"`, the
/// form dtc writes and the one the Linux loader parses.
fn collect_plugin_fixups(
node : SourceNode,
path : String,
fixups : Array[(String, String)],
) -> SourceNode {
let properties : Array[SourceProperty] = []
for prop in node.properties {
let parts : Array[ValuePart] = []
let mut byte_offset = 0
for part in prop.value.parts {
match part {
Ref(label) => {
parts.push(
Cells([PHANDLE_PLACEHOLDER.reinterpret_as_int().to_uint64()]),
)
fixups.push((label, fixup_location(path, prop.name, byte_offset)))
byte_offset = byte_offset + 4
}
PathRef(_) => {
// A path reference names a node the overlay itself contains, so it
// is not something the base tree supplies.
parts.push(part)
byte_offset = byte_offset + 4
}
Cells(cells) => {
parts.push(Cells(cells))
byte_offset = byte_offset + cells.length() * 4
}
Refs(inner) => {
let replaced : Array[ValuePart] = []
for p in inner {
match p {
Ref(label) => {
replaced.push(
Cells([PHANDLE_PLACEHOLDER.reinterpret_as_int().to_uint64()]),
)
fixups.push(
(label, fixup_location(path, prop.name, byte_offset)),
)
byte_offset = byte_offset + 4
}
Cells(cells) => {
replaced.push(Cells(cells))
byte_offset = byte_offset + cells.length() * 4
}
other => replaced.push(other)
}
}
// The pieces concatenate in the output, so they collapse to one list.
let flat : Array[UInt64] = []
for p in replaced {
match p {
Cells(cells) =>
for c in cells {
flat.push(c)
}
_ => ()
}
}
parts.push(Cells(flat))
}
other => {
parts.push(other)
byte_offset = byte_offset + value_part_length(other)
}
}
}
properties.push({ ..prop, value: Value::{ parts, }, })
}
let children : Array[SourceNode] = []
for child in node.children {
children.push(
collect_plugin_fixups(child, join_path(path, child.name), fixups),
)
}
{ ..node, properties, children, }
}
///|
/// Formats a fixup location the way dtc does: `/path/to/node:property:offset`.
fn fixup_location(path : String, property : String, offset : Int32) -> String {
"\{path}:\{property}:\{offset}"
}
///|
/// Length in bytes of a value part, used to track the offset a fixup points at.
fn value_part_length(part : ValuePart) -> Int32 {
match part {
Text(s) => s.length() + 1
Cells(cells) => cells.length() * 4
TypedCells(width, cells) => width.to_int() / 8 * cells.length()
Bytes(bs) => bs.length()
_ => 4
}
}
///|
/// Groups fixups by label and builds the `__fixups__` node.
///
/// One label can appear at several places, and dtc lists them in the order the
/// walk found them, comma-separated in a single string property.
fn build_fixup_node(fixups : Array[(String, String)]) -> SourceNode {
let order : Array[String] = []
let grouped : Map[String, Array[String]] = Map([])
for (label, location) in fixups {
match grouped.get(label) {
Some(list) => list.push(location)
None => {
let list : Array[String] = [location]
grouped.set(label, list)
order.push(label)
}
}
}
let properties : Array[SourceProperty] = []
for label in order {
match grouped.get(label) {
Some(list) => {
let joined = join_strings(list, ":")
// dtc separates multiple locations for one label with a colon in the
// path and nothing between entries, which keeps the value a single
// NUL-terminated string.
properties.push({
name: label,
value: Value::{ parts: [Text(joined)], },
span: Span::{ line: 0, column: 0, },
})
}
None => ()
}
}
{ name: "__fixups__", labels: [], properties, children: [], }
}
///|
/// Joins strings with a separator.
fn join_strings(values : Array[String], sep : String) -> String {
let buf = StringBuilder()
let mut first = true
for v in values {
if !first {
buf.write_string(sep)
}
first = false
buf.write_string(v)
}
buf.to_string()
}
///|
/// A parsed overlay ready to be applied: the fragments it carries and the
/// fixups that name where each unresolved reference landed.
pub(all) struct Overlay {
/// Blob the overlay was read from, kept so error messages can name a
/// position.
blob : Tree
/// Fragment nodes, in the order the blob lists them.
fragments : Array[Node]
/// Label to the locations that need the label's phandle written into them.
fixups : Array[(String, Array[FixupLocation])]
}
///|
/// One place a label's phandle has to be written.
///
/// `path` is the node, `property` the property on it, and `offset` the byte
/// offset inside that property's value. This is the same triple dtc writes
/// into `__fixups__` as a single string.
pub(all) struct FixupLocation {
/// Node path, with `/` for the root.
path : String
/// Property name.
property : String
/// Byte offset inside the value.
offset : Int32
}
///|
/// Reads an overlay blob.
///
/// The fixup strings are parsed here rather than at apply time so that a
/// malformed one is reported when the overlay is read, not halfway through
/// patching a tree.
pub fn parse_overlay(tree : Tree) -> Overlay raise OverlayError {
let fragments : Array[Node] = []
for child in tree.root.children {
if child.name.has_prefix("fragment@") {
fragments.push(child)
}
}
let fixups : Array[(String, Array[FixupLocation])] = []
match find_child(tree.root, "__fixups__") {
Some(node) =>
for prop in node.properties {
let entries : Array[FixupLocation] = []
// One property holds one label; several locations for it are separated
// by a NUL in the value, which is how dtc stores a string list.
for text in split_cstr_list(prop.value) {
entries.push(parse_fixup_location(text))
}
fixups.push((prop.name, entries))
}
None => ()
}
{ blob: tree, fragments, fixups, }
}
///|
/// Finds a direct child by name.
fn find_child(node : Node, name : String) -> Node? {
for child in node.children {
if child.name == name {
return Some(child)
}
}
None
}
///|
/// Splits a value into the NUL-terminated strings it holds.
fn split_cstr_list(value : Bytes) -> Array[String] {
let out : Array[String] = []
let bounds = Bounds::of_bytes(value)
let mut at = 0L
while at < bounds.length() {
let (text, next) = bounds.cstr(at, bounds.length()) catch { _ => break }
out.push(text)
at = next
}
out
}
///|
/// Parses `/path/to/node:property:offset`.
///
/// The path itself contains slashes but no colons, so the last two colons
/// delimit the parts unambiguously.
fn parse_fixup_location(text : String) -> FixupLocation raise OverlayError {
let last = text.rev_find(":")
match last {
None => raise BadFixup(detail="not a /path:property:offset string: " + text)
Some(at) => {
let head = text[:at].to_owned()
let offset_text = text[at + 1:].to_owned()
let offset = match str_to_int(offset_text) {
Some(n) => n
None => raise BadFixup(detail="offset is not a number in " + text)
}
match head.rev_find(":") {
None => raise BadFixup(detail="no property in " + text)
Some(sep) => {
let path = head[:sep].to_owned()
let property = head[sep + 1:].to_owned()
{ path, property, offset, }
}
}
}
}
}
///|
/// Parses a non-negative decimal integer, or None.
///
/// Hand-rolled because the standard conversion raises on bad input and this
/// call site wants to report the whole fixup string instead of the one field.
fn str_to_int(text : String) -> Int32? {
if text.length() == 0 {
return None
}
let mut value = 0
for i in 0.. '9' {
return None
}
value = value * 10 + (c.to_int() - 0x30)
}
Some(value)
}
///|
/// Applies an overlay to a base tree and returns the merged tree.
///
/// The procedure is the one the Linux loader follows. Each fragment names a
/// node in the base tree — either through the label recorded in the overlay's
/// `__fixups__`, or directly through `target-path` — and carries an
/// `__overlay__` subtree. That subtree's properties are set on the target,
/// replacing what was there, and its children are merged into children of the
/// same name, creating them where the base has none.
///
/// Merging rather than replacing is the whole point: an overlay that sets one
/// property on a node keeps the base tree's other properties on it.
pub fn apply_overlay(base : Tree, overlay : Overlay) -> Tree raise OverlayError {
let symbols = match find_child(base.root, "__symbols__") {
Some(node) => symbols_of(node)
None => raise NoSymbols
}
// The fixups are what turn a label into a path: an overlay built from
// `&uart0 { ... }` has a placeholder in `fragment@0/target` and a fixup
// naming `uart0` for that exact property.
let targets : Map[String, String] = Map([])
for (label, locations) in overlay.fixups {
match symbols.get(label) {
Some(path) =>
for location in locations {
// The location is `/fragment@N:target:0`; the fragment name is the
// last path segment and is what the map is keyed on.
targets.set(location.path, path)
}
None => raise UnknownSymbol(label~)
}
}
let phandles = phandles_of(base.root)
let mut root = base.root
for fragment in overlay.fragments {
let target_path = fragment_target_path(fragment, targets)
let body = match find_child(fragment, "__overlay__") {
Some(node) => node
None => raise BadFragment(name=fragment.name)
}
root = merge_into(root, target_path, body)
}
// Placeholder words in the applied body are now resolvable: the base tree
// gave those nodes their numbers.
root = patch_placeholders(root, overlay, symbols, phandles)
{ root, warnings: base.warnings, }
}
///|
/// Works out which node a fragment applies to.
fn fragment_target_path(
fragment : Node,
targets : Map[String, String],
) -> String raise OverlayError {
// A `target-path` property names the node outright, which is what an overlay
// built without -@ carries.
let by_property = match find_property(fragment, "target-path") {
Some(prop) => {
let value = Bounds::of_bytes(prop.value)
let text = value.cstr(0L, value.length()) catch { _ => ("", 0L) }
if text.0 == "" {
None
} else {
Some(text.0)
}
}
None => None
}
match by_property {
Some(path) => path
None => {
let key = "/" + fragment.name
match targets.get(key) {
Some(path) => path
None => raise BadFragment(name=fragment.name)
}
}
}
}
///|
/// Reads `__symbols__` into a label-to-path map.
fn symbols_of(node : Node) -> Map[String, String] {
let out : Map[String, String] = Map([])
for prop in node.properties {
let value = Bounds::of_bytes(prop.value)
let text = value.cstr(0L, value.length()) catch { _ => continue }
out.set(prop.name, text.0)
}
out
}
///|
/// Reads every node's phandle, keyed by path.
fn phandles_of(node : Node) -> Map[String, UInt32] {
let out : Map[String, UInt32] = Map([])
walk_phandles(node, "/", out)
out
}
///|
/// Depth-first walk collecting phandles.
fn walk_phandles(node : Node, path : String, out : Map[String, UInt32]) -> Unit {
for prop in node.properties {
if prop.name == "phandle" && prop.value.length() == 4 {
let value = Bounds::of_bytes(prop.value)
let read = value.read_u32(Cursor::big(0L)) catch { _ => continue }
out.set(path, read.0)
}
}
for child in node.children {
walk_phandles(child, join_path(path, child.name), out)
}
}
///|
/// Merges an overlay body into the node at `path`.
///
/// Properties from the body replace properties of the same name and are
/// appended otherwise, which is the order the loader produces and what a
/// subsequent dump shows. Children merge recursively by name.
fn merge_into(root : Node, path : String, body : Node) -> Node {
if path == "/" {
return merge_node(root, body)
}
let segments = split_path(path)
set_child(root, segments, 0, body)
}
///|
/// Splits `/soc/serial@2000` into `["soc", "serial@2000"]`.
fn split_path(path : String) -> Array[String] {
let out : Array[String] = []
let mut start = 0
for i in 0.. start {
out.push(path[start:i].to_owned())
}
start = i + 1
}
}
if path.length() > start {
out.push(path[start:].to_owned())
}
out
}
///|
/// Replaces the child named by `segments[at]` with `body`, recursing for the
/// remaining segments and creating a node where none exists.
fn set_child(
node : Node,
segments : Array[String],
at : Int32,
body : Node,
) -> Node {
if at >= segments.length() {
return merge_node(node, body)
}
let name = segments[at]
let children : Array[Node] = []
let mut found = false
for child in node.children {
if child.name == name {
found = true
children.push(set_child(child, segments, at + 1, body))
} else {
children.push(child)
}
}
if !found {
// The path names a node the base tree does not have. dtc reports this;
// here an empty node is created so that the fragment still lands
// somewhere, and the caller can compare against dtc to catch it.
let mut fresh : Node = { name, properties: [], children: [], }
fresh = set_child(fresh, segments, at + 1, body)
children.push(fresh)
}
{ ..node, children, }
}
///|
/// Merges one node's properties and children into another.
fn merge_node(base : Node, body : Node) -> Node {
let properties = base.properties.copy()
for prop in body.properties {
let replaced : Array[Property] = []
let mut hit = false
for existing in properties {
if existing.name == prop.name {
replaced.push(prop)
hit = true
} else {
replaced.push(existing)
}
}
if hit {
properties.clear()
for p in replaced {
properties.push(p)
}
} else {
properties.push(prop)
}
}
let children = base.children.copy()
for child in body.children {
let merged : Array[Node] = []
let mut hit = false
for existing in children {
if existing.name == child.name {
merged.push(merge_node(existing, child))
hit = true
} else {
merged.push(existing)
}
}
children.clear()
for c in merged {
children.push(c)
}
if !hit {
children.push(child)
}
}
{ ..base, properties, children, }
}
///|
/// Replaces every placeholder word with the phandle the base tree assigned.
///
/// The overlay's own fixups name where the placeholders are, so this walks
/// those locations rather than scanning the tree for 0xffffffff: a real cell
/// value can legitimately be that number, and rewriting it would corrupt an
/// unrelated property.
fn patch_placeholders(
root : Node,
overlay : Overlay,
symbols : Map[String, String],
phandles : Map[String, UInt32],
) -> Node {
let mut current = root
// The paths in the fixups address the overlay, not the merged tree: a
// location is `/fragment@0/__overlay__:interrupt-parent:0`, while the node
// it belongs to after merging is wherever the fragment's target pointed.
let targets : Map[String, String] = Map([])
for (label, locations) in overlay.fixups {
for location in locations {
match targets.get(location.path) {
Some(_) => ()
None =>
match symbols.get(label) {
Some(path) => targets.set(location.path, path)
None => ()
}
}
}
}
for (label, locations) in overlay.fixups {
match symbols.get(label) {
None => continue
Some(target_path) =>
// A node the base tree never gave a number cannot be patched, and
// inventing one here would produce a blob whose references disagree
// with the tree they point into.
match phandles.get(target_path) {
None => continue
Some(number) =>
for location in locations {
current = write_cell(
current,
remap_fixup_path(location.path, targets),
location.property,
location.offset,
number,
)
}
}
}
}
current
}
///|
/// Writes a 32-bit value at a byte offset inside a property.
///
/// The path in a fixup points into the overlay tree, but the apply step merged
/// that tree into the base, so the same path addresses the merged result: the
/// fragment names survive the merge.
fn write_cell(
root : Node,
path : String,
property : String,
offset : Int32,
value : UInt32,
) -> Node {
let segments = split_path(path)
update_node(root, segments, 0, property, offset, value)
}
///|
/// Recursively finds the node at `segments` and patches its property.
fn update_node(
node : Node,
segments : Array[String],
at : Int32,
property : String,
offset : Int32,
value : UInt32,
) -> Node {
if at >= segments.length() {
let properties : Array[Property] = []
for prop in node.properties {
if prop.name == property && offset + 4 <= prop.value.length() {
let patched = Buffer(capacity=prop.value.length())
for i in 0..> 24) & 0xFF).to_byte())
out.write_byte(((raw >> 16) & 0xFF).to_byte())
out.write_byte(((raw >> 8) & 0xFF).to_byte())
out.write_byte((raw & 0xFF).to_byte())
} else if i < offset || i >= offset + 4 {
out.write_byte(bytes.at(i))
}
}
properties.push({ ..prop, value: out.to_bytes(), })
} else {
properties.push(prop)
}
}
return { ..node, properties, }
}
let name = segments[at]
let children : Array[Node] = []
for child in node.children {
if child.name == name {
children.push(
update_node(child, segments, at + 1, property, offset, value),
)
} else {
children.push(child)
}
}
{ ..node, children, }
}
///|
/// Finds a direct property by name.
fn find_property(node : Node, name : String) -> Property? {
for prop in node.properties {
if prop.name == name {
return Some(prop)
}
}
None
}
///|
/// Rewrites a fixup path from overlay coordinates to merged-tree coordinates.
///
/// `/fragment@0/__overlay__/serial@1000` addresses a node inside the fragment;
/// after the merge that node lives under the fragment's target, so the
/// `fragment@N/__overlay__` prefix is replaced by the target path. A fixup on
/// the fragment's own `target` property has no merged equivalent and is left
/// alone, which is correct: the loader consumes it rather than rewriting it.
fn remap_fixup_path(path : String, targets : Map[String, String]) -> String {
let marker = "/__overlay__"
match path.find(marker) {
None => path
Some(at) => {
let fragment_part = path[:at].to_owned()
let tail = path[at + marker.length():].to_owned()
// `targets` is keyed on `/fragment@N`; the fixup path is
// `/fragment@N/__overlay__/...`, so the same key applies.
match targets.get(fragment_part) {
Some(target) => if target == "/" { tail } else { target + tail }
None => path
}
}
}
}
///|
/// Decodes a blob into a tree, as the CLI and a browser caller both need.
pub fn parse_tree(blob : Bytes) -> Tree raise DtbError {
let header = parse_header(blob)
let struct_bounds = Bounds::of_range(
blob,
header.off_dt_struct,
header.off_dt_struct + header.size_dt_struct,
)
let strings_bounds = Bounds::of_range(
blob,
header.off_dt_strings,
header.off_dt_strings + header.size_dt_strings,
)
parse_struct(struct_bounds, strings_bounds)
}
///|
/// Encodes a decoded tree back to a blob.
///
/// The values are already bytes at this point, so each property is written
/// through unchanged; this exists so that an applied overlay can be written
/// out without going through the source representation.
pub fn encode_tree(tree : Tree) -> Bytes {
let strings = StringTable::new()
let struct_block = Buffer()
write_binary_node(tree.root, strings, struct_block)
put_u32(struct_block, 0x9)
let strings_bytes = strings.to_bytes()
let struct_bytes = struct_block.to_bytes()
let memreserve = Buffer()
put_u64(memreserve, 0UL)
put_u64(memreserve, 0UL)
let memreserve_bytes = memreserve.to_bytes()
let blocks = memreserve_bytes.length() + struct_bytes.length()
let total = 40 + blocks + strings_bytes.length()
let out = Buffer()
put_u32(out, 0xD00D_FEED)
put_u32(out, total.reinterpret_as_uint())
let off_struct = 40 + memreserve_bytes.length()
put_u32(out, off_struct.reinterpret_as_uint())
let off_strings = off_struct + struct_bytes.length()
put_u32(out, off_strings.reinterpret_as_uint())
put_u32(out, 40)
put_u32(out, 17)
put_u32(out, 16)
put_u32(out, 0)
put_u32(out, strings_bytes.length().reinterpret_as_uint())
put_u32(out, struct_bytes.length().reinterpret_as_uint())
for i in 0.. Unit {
put_u32(out, 0x1)
for i in 0..