MODULES := core/fdt.rad core/platform.rad

CORE := -pkg core -mod core.rad $(addprefix -mod ,$(MODULES))

CHECK_MODULES := check/boot.rad check/fixture.rad

kernel.rv64: main.rad arch/entry.ras core.rad $(MODULES) $(COMPILER)

	$(COMPILE) $(CORE) -pkg kernel -start arch/entry.ras -mod main.rad -entry kernel -o $@

check.rv64: check.rad core.rad $(MODULES) $(CHECK_MODULES) $(COMPILER)

	$(COMPILE) $(CORE) -pkg check -mod check.rad $(addprefix -mod ,$(CHECK_MODULES)) -entry check -o $@

record the contracts established through step 2 of the 22-step plan.

## Firmware discovery

- Accept version-17 FDT blobs up to 64 KiB, at most 256 nodes, and 32 nesting

  levels. Support one- and two-cell addresses, empty bus ranges, and explicit

  translations. Reject duplicate names/properties/phandles, overlapping sections,

  incomplete register tuples, and truncated inputs.

- Decode firmware reservations and /reserved-memory. MMIO is not allocatable RAM.

  CLINT, PLIC, and radiant,finish are machine resources, not user Device authority.

- Hardware hart identifiers fit the eight-entry build limit. CLINT banks and

  PLIC contexts come from interrupts-extended, not the hart identifier itself.

Exercise bounded FDT topology discovery, malformed sections, every truncated prefix, reservations, and disabled CPU nodes.

mod boot;

export mod fixture;

    boot::run();

//! Device-tree parsing and physical-platform behavior checks.

use core::fdt;

use core::platform;

use check::fixture;

/// Set a big-endian word in a test-owned buffer.

fn put(bytes: *mut [u8], offset: u32, value: u32) {

    set bytes[offset] = (value >> 24) as u8;

    set bytes[offset + 1] = (value >> 16) as u8;

    set bytes[offset + 2] = (value >> 8) as u8;

    set bytes[offset + 3] = value as u8;

}

/// Require malformed input to fail without exposing partially decoded state.

fn reject(bytes: *[u8]) {

    let mut tree: fdt::Tree = undefined;

    try fdt::decode(bytes, &mut tree) catch { return; };

    panic "reject: malformed FDT accepted";

}

/// Check platform resources and reject truncated or overlapping sections.

export fn run() {

    let bytes = &fixture::BYTES[..];

    let mut tree: fdt::Tree = undefined;

    try! fdt::decode(bytes, &mut tree);

    let mut machine: platform::Platform = undefined;

    try! platform::discover(&tree, &mut machine);

    assert machine.memoryCount == 1;

    assert machine.memory[0].base == 0;

    assert machine.memory[0].size == 0x8000000;

    assert machine.reserved[0].size == 0x1000000;

    assert machine.hartCount == 2;

    assert machine.harts[1].id == 1;

    assert machine.harts[1].clintIndex == 1;

    assert machine.harts[1].plicContext == 1;

    assert machine.clint.base == 0x2000000;

    assert machine.plic.base == 0xc000000;

    assert machine.devices[0].region.base == 0x10000000;

    assert machine.devices[0].irq == 10;

    for n in 0..bytes.len { reject(&bytes[..n]); }

    let mut corrupt = fixture::BYTES;

    put(&mut corrupt[..], 8, 0xfffffff0);

    reject(&corrupt[..]);

    set corrupt = fixture::BYTES;

    put(&mut corrupt[..], 12, 72);

    reject(&corrupt[..]);

    set corrupt = fixture::BYTES;

    put(&mut corrupt[..], 16, 72);

    reject(&corrupt[..]);

    set corrupt = fixture::BYTES;

    put(&mut corrupt[..], 72, 2);

    reject(&corrupt[..]);

    // A disabled hart must not receive a route in the online set.

    try! fdt::decode(bytes, &mut tree);

    for i in 0..tree.count {

        if fdt::equal(tree.nodes[i].name, "cpu@1") {

            set tree.nodes[i].status = "disabled\0";

        }

    }

    try! platform::discover(&tree, &mut machine);

    assert machine.hartCount == 1;

    assert machine.harts[0].id == 0;

}

//! Encoded two-hart platform used by device-tree behavior checks.

/// A complete version-17 FDT with RAM, CLINT, PLIC, and UART.

export constant BYTES: [u8; 1136] = [

    0xd0, 0x0d, 0xfe, 0xed, 0x00, 0x00, 0x04, 0x70, 0x00, 0x00, 0x00, 0x48, 0x00, 0x00, 0x03, 0xcc,

    0x00, 0x00, 0x00, 0x28, 0x00, 0x00, 0x00, 0x11, 0x00, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, 0x00,

    0x00, 0x00, 0x00, 0xa4, 0x00, 0x00, 0x03, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

    0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00,

    0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02,

    0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x0f, 0x00, 0x00, 0x00, 0x02,

    0x00, 0x00, 0x00, 0x01, 0x6d, 0x65, 0x6d, 0x6f, 0x72, 0x79, 0x40, 0x30, 0x00, 0x00, 0x00, 0x00,

    0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x07, 0x00, 0x00, 0x00, 0x1b, 0x6d, 0x65, 0x6d, 0x6f,

    0x72, 0x79, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, 0x27,

    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x08, 0x00, 0x00, 0x00,

    0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x01, 0x63, 0x70, 0x75, 0x73, 0x00, 0x00, 0x00, 0x00,

    0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,

    0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x0f, 0x00, 0x00, 0x00, 0x00,

    0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x2b, 0x00, 0x0f, 0x42, 0x40,

    0x00, 0x00, 0x00, 0x01, 0x63, 0x70, 0x75, 0x40, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03,

    0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x1b, 0x63, 0x70, 0x75, 0x00, 0x00, 0x00, 0x00, 0x03,

    0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x27, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,

    0x69, 0x6e, 0x74, 0x65, 0x72, 0x72, 0x75, 0x70, 0x74, 0x2d, 0x63, 0x6f, 0x6e, 0x74, 0x72, 0x6f,

    0x6c, 0x6c, 0x65, 0x72, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x0f,

    0x00, 0x00, 0x00, 0x3e, 0x72, 0x69, 0x73, 0x63, 0x76, 0x2c, 0x63, 0x70, 0x75, 0x2d, 0x69, 0x6e,

    0x74, 0x63, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x49,

    0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x51,

    0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x01,

    0x63, 0x70, 0x75, 0x40, 0x31, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x04,

    0x00, 0x00, 0x00, 0x1b, 0x63, 0x70, 0x75, 0x00, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x04,

    0x00, 0x00, 0x00, 0x27, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x01, 0x69, 0x6e, 0x74, 0x65,

    0x72, 0x72, 0x75, 0x70, 0x74, 0x2d, 0x63, 0x6f, 0x6e, 0x74, 0x72, 0x6f, 0x6c, 0x6c, 0x65, 0x72,

    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x0f, 0x00, 0x00, 0x00, 0x3e,

    0x72, 0x69, 0x73, 0x63, 0x76, 0x2c, 0x63, 0x70, 0x75, 0x2d, 0x69, 0x6e, 0x74, 0x63, 0x00, 0x00,

    0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x49, 0x00, 0x00, 0x00, 0x02,

    0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x51, 0x00, 0x00, 0x00, 0x01,

    0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x01,

    0x73, 0x6f, 0x63, 0x00, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x00,

    0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x0f,

    0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x62,

    0x00, 0x00, 0x00, 0x01, 0x63, 0x6c, 0x69, 0x6e, 0x74, 0x40, 0x32, 0x30, 0x30, 0x30, 0x30, 0x30,

    0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x0d, 0x00, 0x00, 0x00, 0x3e,

    0x72, 0x69, 0x73, 0x63, 0x76, 0x2c, 0x63, 0x6c, 0x69, 0x6e, 0x74, 0x30, 0x00, 0x00, 0x00, 0x00,

    0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, 0x27, 0x00, 0x00, 0x00, 0x00,

    0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03,

    0x00, 0x00, 0x00, 0x20, 0x00, 0x00, 0x00, 0x69, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x03,

    0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x07, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x03,

    0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x07, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x01,

    0x70, 0x6c, 0x69, 0x63, 0x40, 0x63, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x00, 0x00, 0x00, 0x00,

    0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x0c, 0x00, 0x00, 0x00, 0x3e, 0x72, 0x69, 0x73, 0x63,

    0x76, 0x2c, 0x70, 0x6c, 0x69, 0x63, 0x30, 0x00, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x10,

    0x00, 0x00, 0x00, 0x27, 0x00, 0x00, 0x00, 0x00, 0x0c, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

    0x00, 0x40, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x49,

    0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x51,

    0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x7d,

    0x00, 0x00, 0x00, 0x7f, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, 0x69,

    0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x0b, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x0b,

    0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x01, 0x75, 0x61, 0x72, 0x74, 0x40, 0x31, 0x30, 0x30,

    0x30, 0x30, 0x30, 0x30, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x09,

    0x00, 0x00, 0x00, 0x3e, 0x6e, 0x73, 0x31, 0x36, 0x35, 0x35, 0x30, 0x61, 0x00, 0x00, 0x00, 0x00,

    0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, 0x27, 0x00, 0x00, 0x00, 0x00,

    0x10, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x03,

    0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x88, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x03,

    0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x99, 0x00, 0x00, 0x00, 0x0a, 0x00, 0x00, 0x00, 0x02,

    0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x09, 0x23, 0x61, 0x64, 0x64,

    0x72, 0x65, 0x73, 0x73, 0x2d, 0x63, 0x65, 0x6c, 0x6c, 0x73, 0x00, 0x23, 0x73, 0x69, 0x7a, 0x65,

    0x2d, 0x63, 0x65, 0x6c, 0x6c, 0x73, 0x00, 0x64, 0x65, 0x76, 0x69, 0x63, 0x65, 0x5f, 0x74, 0x79,

    0x70, 0x65, 0x00, 0x72, 0x65, 0x67, 0x00, 0x74, 0x69, 0x6d, 0x65, 0x62, 0x61, 0x73, 0x65, 0x2d,

    0x66, 0x72, 0x65, 0x71, 0x75, 0x65, 0x6e, 0x63, 0x79, 0x00, 0x63, 0x6f, 0x6d, 0x70, 0x61, 0x74,

    0x69, 0x62, 0x6c, 0x65, 0x00, 0x70, 0x68, 0x61, 0x6e, 0x64, 0x6c, 0x65, 0x00, 0x23, 0x69, 0x6e,

    0x74, 0x65, 0x72, 0x72, 0x75, 0x70, 0x74, 0x2d, 0x63, 0x65, 0x6c, 0x6c, 0x73, 0x00, 0x72, 0x61,

    0x6e, 0x67, 0x65, 0x73, 0x00, 0x69, 0x6e, 0x74, 0x65, 0x72, 0x72, 0x75, 0x70, 0x74, 0x73, 0x2d,

    0x65, 0x78, 0x74, 0x65, 0x6e, 0x64, 0x65, 0x64, 0x00, 0x72, 0x69, 0x73, 0x63, 0x76, 0x2c, 0x6e,

    0x64, 0x65, 0x76, 0x00, 0x69, 0x6e, 0x74, 0x65, 0x72, 0x72, 0x75, 0x70, 0x74, 0x2d, 0x70, 0x61,

    0x72, 0x65, 0x6e, 0x74, 0x00, 0x69, 0x6e, 0x74, 0x65, 0x72, 0x72, 0x75, 0x70, 0x74, 0x73, 0x00,

];

//! Safe kernel mechanisms shared by machine execution and hosted checks.

export mod fdt;

export mod platform;

//! Bounded decoding of flattened device trees, version 17.

/// Maximum nodes accepted from platform firmware.

export constant MAX_NODES: u32 = 256;

/// Maximum nesting depth accepted from platform firmware.

constant MAX_DEPTH: u32 = 32;

/// Maximum firmware reservation entries.

export constant MAX_RESERVED: u32 = 64;

/// Maximum complete device-tree size accepted at boot.

export constant MAX_BYTES: u32 = 65536;

/// Maximum properties retained across the active parser stack.

constant MAX_PROPERTIES: u32 = 256;

/// Parent index of the root node.

export constant NO_PARENT: u32 = 0xffffffff;

/// Device tree header magic.

constant MAGIC: u32 = 0xd00dfeed;

/// Invalid firmware input or exhausted decoder storage.

export union Error: Copy {

    /// Input violates the flattened tree format or supported cell widths.

    Invalid,

    /// Input exceeds a fixed decoder limit.

    Exhausted,

}

/// One physical half-open address range.

export record Range: Copy {

    /// Physical start address.

    base: u64,

    /// Number of bytes in the range.

    size: u64,

}

/// Properties used to discover physical resources.

export record Node: Copy {

    /// Node name without its terminating zero byte.

    name: *[u8],

    /// Parent node index, or NO_PARENT for the root.

    parent: u32,

    /// Number of address cells used by children.

    addressCells: u32,

    /// Number of size cells used by children.

    sizeCells: u32,

    /// Physical register tuples encoded with parent cell widths.

    reg: *[u8],

    /// Bus address translations.

    ranges: ?*[u8],

    /// Zero-terminated compatible strings.

    compatible: *[u8],

    /// Device type string.

    deviceType: *[u8],

    /// Status string; empty means enabled.

    status: *[u8],

    /// Interrupt-controller identifier.

    phandle: u32,

    /// Interrupt-parent identifier; zero inherits from the parent.

    interruptParent: u32,

    /// Number of cells in interrupt specifiers.

    interruptCells: u32,

    /// Interrupt source specifiers.

    interrupts: *[u8],

    /// Interrupt specifiers with controller identifiers.

    extended: *[u8],

    /// Number of PLIC interrupt sources.

    sources: u32,

    /// Timer ticks per second for the CPU bus.

    frequency: u32,

}

/// Decoded nodes and firmware reservations borrowed from the input.

export record Tree: Copy {

    /// Nodes in structure-block order.

    nodes: [Node; MAX_NODES],

    /// Number of initialized node entries.

    count: u32,

    /// Physical reservations from the header reservation map.

    reserved: [Range; MAX_RESERVED],

    /// Number of initialized reservation entries.

    reservedCount: u32,

    /// Total byte size of the firmware blob.

    size: u32,

}

/// Read a big-endian word after checking the complete range.

export fn word(bytes: *[u8], offset: u32) -> u32 throws (Error) {

    if offset > bytes.len or bytes.len - offset < 4 {

        throw Error::Invalid;

    }

    return (bytes[offset] as u32 << 24) | (bytes[offset + 1] as u32 << 16)

        | (bytes[offset + 2] as u32 << 8) | bytes[offset + 3] as u32;

}

/// Read a one-cell or two-cell integer.

export fn cells(bytes: *[u8], offset: u32, count: u32) -> u64 throws (Error) {

    if count == 0 { return 0; }

    if count == 1 { return try word(bytes, offset) as u64; }

    if count <> 2 { throw Error::Invalid; }

    let high = try word(bytes, offset);

    let low = try word(bytes, offset + 4);

    return (high as u64 << 32) | low as u64;

}

/// Compare byte strings without reading beyond either slice.

export fn equal(a: *[u8], b: *[u8]) -> bool {

    if a.len <> b.len { return false; }

    for byte, i in a {

        if byte <> b[i] { return false; }

    }

    return true;

}

/// Return a bounded zero-terminated string without its terminator.

fn string(bytes: *[u8], offset: u32) -> *[u8] throws (Error) {

    if offset >= bytes.len { throw Error::Invalid; }

    let mut end = offset;

    while bytes[end] <> 0 {

        set end += 1;

        if end == bytes.len { throw Error::Invalid; }

    }

    return &bytes[offset..end];

}

/// Check for an exact item in a sequence of zero-terminated strings.

export fn contains(bytes: *[u8], item: *[u8]) -> bool {

    let mut offset: u32 = 0;

    while offset < bytes.len {

        let value = try string(bytes, offset) catch { return false; };

        if equal(value, item) { return true; }

        set offset += value.len + 1;

    }

    return false;

}

/// Test whether firmware enables a node and all its parents.

export fn enabled(tree: *Tree, index: u32) -> bool {

    let mut current = index;

    while current <> NO_PARENT {

        let node = &tree.nodes[current];

        if node.status.len <> 0 and not equal(node.status, "okay\0")

            and not equal(node.status, "ok\0") {

            return false;

        }

        set current = node.parent;

    }

    return true;

}

/// Check a section range against the complete input.

fn section(bytes: *[u8], offset: u32, size: u32) -> *[u8] throws (Error) {

    if offset > bytes.len or size > bytes.len - offset { throw Error::Invalid; }

    return &bytes[offset..offset + size];

}

/// Store one relevant property after validating its representation.

fn property(node: *mut Node, name: *[u8], value: *[u8]) throws (Error) {

    if equal(name, "#address-cells") {

        if value.len <> 4 { throw Error::Invalid; }

        set node.addressCells = try word(value, 0);

        if node.addressCells == 0 or node.addressCells > 2 { throw Error::Invalid; }

    } else if equal(name, "#size-cells") {

        if value.len <> 4 { throw Error::Invalid; }

        set node.sizeCells = try word(value, 0);

        if node.sizeCells > 2 { throw Error::Invalid; }

    } else if equal(name, "reg") {

        set node.reg = value;

    } else if equal(name, "ranges") {

        set node.ranges = value;

    } else if equal(name, "compatible") {

        if value.len == 0 or value[value.len - 1] <> 0 { throw Error::Invalid; }

        set node.compatible = value;

    } else if equal(name, "device_type") {

        set node.deviceType = value;

    } else if equal(name, "status") {

        set node.status = value;

    } else if equal(name, "interrupts") {

        set node.interrupts = value;

    } else if equal(name, "interrupts-extended") {

        set node.extended = value;

    } else {

        let scalar = equal(name, "phandle") or equal(name, "linux,phandle")

            or equal(name, "interrupt-parent") or equal(name, "#interrupt-cells")

            or equal(name, "riscv,ndev") or equal(name, "timebase-frequency");

        if scalar {

            if value.len <> 4 { throw Error::Invalid; }

            let number = try word(value, 0);

            if equal(name, "phandle") or equal(name, "linux,phandle") {

                if number == 0 or number == 0xffffffff { throw Error::Invalid; }

                if node.phandle <> 0 and node.phandle <> number { throw Error::Invalid; }

                set node.phandle = number;

            } else if equal(name, "interrupt-parent") {

                set node.interruptParent = number;

            } else if equal(name, "#interrupt-cells") {

                set node.interruptCells = number;

            } else if equal(name, "riscv,ndev") {

                set node.sources = number;

            } else {

                set node.frequency = number;

            }

        }

    }

}

/// Decode a complete FDT into caller-owned fixed storage.

export fn decode(bytes: *[u8], tree: *mut Tree) throws (Error) {

    if bytes.len < 40 or try word(bytes, 0) <> MAGIC { throw Error::Invalid; }

    let size = try word(bytes, 4);

    if size < 40 or size > bytes.len or size > MAX_BYTES { throw Error::Invalid; }

    let blob = &bytes[..size];

    let structureOffset = try word(blob, 8);

    let stringsOffset = try word(blob, 12);

    let reserveOffset = try word(blob, 16);

    if try word(blob, 20) <> 17 or try word(blob, 24) > 17 {

        throw Error::Invalid;

    }

    let stringsSize = try word(blob, 32);

    let structureSize = try word(blob, 36);

    if structureOffset < 40 or stringsOffset < 40 or reserveOffset < 40

        or (structureOffset & 3) <> 0 or (reserveOffset & 7) <> 0 {

        throw Error::Invalid;

    }

    let structure = try section(blob, structureOffset, structureSize);

    let strings = try section(blob, stringsOffset, stringsSize);

    if structureOffset < stringsOffset + stringsSize

        and stringsOffset < structureOffset + structureSize { throw Error::Invalid; }

    set tree.count = 0;

    set tree.reservedCount = 0;

    set tree.size = size;

    let mut pos = reserveOffset;

    loop {

        let entry = try section(blob, pos, 16);

        let base = try cells(entry, 0, 2);

        let length = try cells(entry, 8, 2);

        set pos += 16;

        if base == 0 and length == 0 { break; }

        if length == 0 or base > 0xffffffffffffffff - length { throw Error::Invalid; }

        if tree.reservedCount == MAX_RESERVED { throw Error::Exhausted; }

        set tree.reserved[tree.reservedCount] = Range { base, size: length };

        set tree.reservedCount += 1;

    }

    if reserveOffset < structureOffset + structureSize and structureOffset < pos

        or reserveOffset < stringsOffset + stringsSize and stringsOffset < pos {

        throw Error::Invalid;

    }

    let mut stack: [u32; MAX_DEPTH] = undefined;

    let mut depth: u32 = 0;

    let mut childSeen: [bool; MAX_DEPTH] = undefined;

    let mut propertyNames: [*[u8]; MAX_PROPERTIES] = undefined;

    let mut propertyStart: [u32; MAX_DEPTH] = undefined;

    let mut propertyCount: u32 = 0;

    set pos = 0;

    loop {

        let token = try word(structure, pos);

        set pos += 4;

        if token == 1 {

            if depth == MAX_DEPTH or tree.count == MAX_NODES { throw Error::Exhausted; }

            if depth == 0 and tree.count <> 0 { throw Error::Invalid; }

            let name = try string(structure, pos);

            if tree.count == 0 and name.len <> 0 { throw Error::Invalid; }

            let padded = (name.len + 4) & ~3;

            let _nameBytes = try section(structure, pos, padded);

            set pos += padded;

            let mut parent = NO_PARENT;

            if depth <> 0 {

                set parent = stack[depth - 1];

                set childSeen[depth - 1] = true;

            }

            for i in 0..tree.count {

                if tree.nodes[i].parent == parent and equal(tree.nodes[i].name, name) {

                    throw Error::Invalid;

                }

            }

            set tree.nodes[tree.count] = Node {

                name, parent, addressCells: 2, sizeCells: 1,

                reg: "", ranges: nil, compatible: "", deviceType: "", status: "",

                phandle: 0, interruptParent: 0, interruptCells: 0,

                interrupts: "", extended: "", sources: 0, frequency: 0,

            };

            set stack[depth] = tree.count;

            set childSeen[depth] = false;

            set propertyStart[depth] = propertyCount;

            set depth += 1;

            set tree.count += 1;

        } else if token == 2 {

            if depth == 0 { throw Error::Invalid; }

            set depth -= 1;

            set propertyCount = propertyStart[depth];

        } else if token == 3 {

            if depth == 0 or childSeen[depth - 1] { throw Error::Invalid; }

            let length = try word(structure, pos);

            let nameOffset = try word(structure, pos + 4);

            set pos += 8;

            let name = try string(strings, nameOffset);

            if name.len == 0 { throw Error::Invalid; }

            for i in propertyStart[depth - 1]..propertyCount {

                if equal(propertyNames[i], name) { throw Error::Invalid; }

            }

            if propertyCount == MAX_PROPERTIES { throw Error::Exhausted; }

            set propertyNames[propertyCount] = name;

            set propertyCount += 1;

            let value = try section(structure, pos, length);

            if length > 0xfffffffc { throw Error::Invalid; }

            let padded = (length + 3) & ~3;

            let _valueBytes = try section(structure, pos, padded);

            set pos += padded;

            try property(&mut tree.nodes[stack[depth - 1]], name, value);

        } else if token == 4 {

            // NOP tokens can occur between structure entries.

        } else if token == 9 {

            if depth <> 0 or tree.count == 0 or pos <> structure.len { throw Error::Invalid; }

            for i in 0..tree.count {

                let id = tree.nodes[i].phandle;

                if id <> 0 {

                    for j in 0..i {

                        if tree.nodes[j].phandle == id { throw Error::Invalid; }

                    }

                }

            }

            return;

        } else {

            throw Error::Invalid;

        }

    }

}

//! Physical resources and interrupt topology from a validated device tree.

use core::fdt;

/// Maximum online harts in this build.

export constant MAX_HARTS: u32 = 8;

/// Maximum disjoint RAM regions in the boot description.

export constant MAX_MEMORY: u32 = 16;

/// Maximum user-visible MMIO regions.

export constant MAX_DEVICES: u32 = 128;

/// Maximum PLIC source identifier, including unused source zero.

export constant MAX_IRQS: u32 = 128;

/// One enabled hart and its machine interrupt-controller routes.

export record Hart: Copy {

    /// Hardware hart identifier.

    id: u32,

    /// Local CPU interrupt-controller phandle.

    controller: u32,

    /// CLINT register bank index.

    clintIndex: u32,

    /// PLIC machine-context index.

    plicContext: u32,

}

/// One user-visible device region.

export record Device: Copy {

    /// Physical register window.

    region: fdt::Range,

    /// PLIC source, or zero for a device without interrupts.

    irq: u32,

}

/// Fixed storage for all discovered platform resources.

export record Platform: Copy {

    /// Physical RAM banks.

    memory: [fdt::Range; MAX_MEMORY],

    /// Number of initialized RAM banks.

    memoryCount: u32,

    /// Firmware reservations.

    reserved: [fdt::Range; fdt::MAX_RESERVED],

    /// Number of initialized reservations.

    reservedCount: u32,

    /// Online harts in device-tree order.

    harts: [Hart; MAX_HARTS],

    /// Number of online harts.

    hartCount: u32,

    /// User-visible devices in device-tree order.

    devices: [Device; MAX_DEVICES],

    /// Number of initialized device regions.

    deviceCount: u32,

    /// CLINT register window.

    clint: fdt::Range,

    /// PLIC register window.

    plic: fdt::Range,

    /// Number of usable PLIC sources.

    irqCount: u32,

    /// Monotonic timer frequency in ticks per second.

    frequency: u32,

}

/// Translate a range through its parent bus mappings.

fn translate(tree: *fdt::Tree, parent: u32, range: fdt::Range) -> fdt::Range throws (fdt::Error) {

    let mut result = range;

    let mut bus = parent;

    while tree.nodes[bus].parent <> fdt::NO_PARENT {

        let node = &tree.nodes[bus];

        let ancestor = &tree.nodes[node.parent];

        let ranges = node.ranges else { throw fdt::Error::Invalid; };

        if ranges.len <> 0 {

            let tupleSize = (node.addressCells + ancestor.addressCells + node.sizeCells) * 4;

            if tupleSize == 0 or ranges.len % tupleSize <> 0 { throw fdt::Error::Invalid; }

            let mut found = false;

            let mut offset: u32 = 0;

            while offset < ranges.len {

                let child = try fdt::cells(ranges, offset, node.addressCells);

                let target = try fdt::cells(ranges, offset + node.addressCells * 4, ancestor.addressCells);

                let size = try fdt::cells(ranges, offset + (node.addressCells + ancestor.addressCells) * 4, node.sizeCells);

                if result.base >= child and result.base - child <= size

                    and result.size <= size - (result.base - child) {

                    let delta = result.base - child;

                    if target > 0xffffffffffffffff - delta

                        or result.size > 0xffffffffffffffff - (target + delta) {

                        throw fdt::Error::Invalid;

                    }

                    set result.base = target + delta;

                    set found = true;

                    break;

                }

                set offset += tupleSize;

            }

            if not found { throw fdt::Error::Invalid; }

        }

        set bus = node.parent;

    }

    return result;

}

/// Decode and translate one register tuple.

fn region(tree: *fdt::Tree, index: u32, offset: u32) -> fdt::Range throws (fdt::Error) {

    let node = &tree.nodes[index];

    if node.parent == fdt::NO_PARENT { throw fdt::Error::Invalid; }

    let parent = &tree.nodes[node.parent];

    let base = try fdt::cells(node.reg, offset, parent.addressCells);

    let size = try fdt::cells(node.reg, offset + parent.addressCells * 4, parent.sizeCells);

    if size == 0 or base > 0xffffffffffffffff - size { throw fdt::Error::Invalid; }

    return try translate(tree, node.parent, fdt::Range { base, size });

}

/// Resolve CPU-local interrupt routing for CLINT and PLIC.

fn routes(tree: *fdt::Tree, node: *fdt::Node, platform: *mut Platform, plic: bool) throws (fdt::Error) {

    if node.extended.len == 0 or node.extended.len % 8 <> 0 { throw fdt::Error::Invalid; }

    let mut offset: u32 = 0;

    while offset < node.extended.len {

        let controller = try fdt::word(node.extended, offset);

        let cause = try fdt::word(node.extended, offset + 4);

        let mut known = false;

        for i in 0..tree.count {

            if tree.nodes[i].phandle == controller and tree.nodes[i].interruptCells == 1 {

                set known = true;

            }

        }

        if not known { throw fdt::Error::Invalid; }

        for i in 0..platform.hartCount {

            let hart = &mut platform.harts[i];

            if hart.controller == controller {

                if plic and cause == 11 {

                    if hart.plicContext <> fdt::NO_PARENT { throw fdt::Error::Invalid; }

                    set hart.plicContext = offset / 8;

                } else if not plic and cause == 3 {

                    if hart.clintIndex <> fdt::NO_PARENT { throw fdt::Error::Invalid; }

                    if offset + 16 > node.extended.len

                        or try fdt::word(node.extended, offset + 8) <> controller

                        or try fdt::word(node.extended, offset + 12) <> 7 {

                        throw fdt::Error::Invalid;

                    }

                    set hart.clintIndex = offset / 16;

                }

            }

        }

        set offset += 8;

    }

}