summaryrefslogtreecommitdiff
path: root/na/fdt/fdt.cc
diff options
context:
space:
mode:
Diffstat (limited to 'na/fdt/fdt.cc')
-rw-r--r--na/fdt/fdt.cc555
1 files changed, 555 insertions, 0 deletions
diff --git a/na/fdt/fdt.cc b/na/fdt/fdt.cc
new file mode 100644
index 0000000..8262aeb
--- /dev/null
+++ b/na/fdt/fdt.cc
@@ -0,0 +1,555 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/* Copyright (C) 2026 Richard Qin */
+
+/*
+ * fdt.cc — Flattened Device Tree parser implementation
+ *
+ * Implements the two-phase FDT parsing strategy described in fdt.md:
+ *
+ * Phase 1 (Early Scan):
+ * Static methods that linearly walk the raw FDT blob in-place,
+ * performing zero memory allocation. Called before PMM/Slab exist.
+ *
+ * Phase 2 (Unflatten):
+ * Builds a persistent DeviceNode C++ object tree using Slab.
+ * Stub implementation — will be completed when Slab is available.
+ *
+ * Reference: docs/specs/fdt.md
+ */
+
+#include <lume/fdt.h>
+#include <lume/new.h>
+#include <lume/panic.h>
+#include <lume/addr.h>
+
+/* ------------------------------------------------------------------ */
+/* Global singleton (Placement New pattern, see global_init.md §3.1) */
+/* ------------------------------------------------------------------ */
+
+alignas(FdtManager) uint8 g_fdt_buf[sizeof(FdtManager)];
+FdtManager *g_fdt = nullptr;
+
+/* ------------------------------------------------------------------ */
+/* FDT binary format constants (DTSpec v0.4) */
+/* ------------------------------------------------------------------ */
+
+struct fdt_header {
+ uint32 magic;
+ uint32 totalsize;
+ uint32 off_dt_struct;
+ uint32 off_dt_strings;
+ uint32 off_mem_rsvmap;
+ uint32 version;
+ uint32 last_comp_version;
+ uint32 boot_cpuid_phys;
+ uint32 size_dt_strings;
+ uint32 size_dt_struct;
+};
+
+#define FDT_MAGIC 0xd00dfeed
+#define FDT_BEGIN_NODE 1
+#define FDT_END_NODE 2
+#define FDT_PROP 3
+#define FDT_NOP 4
+#define FDT_END 9
+
+/* ------------------------------------------------------------------ */
+/* Minimal string helpers (no lib/ dependency for early boot) */
+/* ------------------------------------------------------------------ */
+
+static inline bool str_starts_with(const char *str, const char *prefix)
+{
+ while (*prefix) {
+ if (*str++ != *prefix++)
+ return false;
+ }
+ return true;
+}
+
+static inline bool str_equals(const char *s1, const char *s2)
+{
+ while (*s1 && *s1 == *s2) {
+ s1++;
+ s2++;
+ }
+ return *s1 == *s2;
+}
+
+/*
+ * Check whether a null-separated string list (e.g. the "compatible"
+ * property) contains @target.
+ */
+static bool prop_contains_string(const char *prop_val, uint32 len,
+ const char *target)
+{
+ uint32 i = 0;
+ while (i < len) {
+ const char *s = prop_val + i;
+ if (str_equals(s, target))
+ return true;
+ while (i < len && prop_val[i] != '\0')
+ i++;
+ i++; // skip '\0' separator
+ }
+ return false;
+}
+
+/* ------------------------------------------------------------------ */
+/* Byte-swap helpers */
+/* ------------------------------------------------------------------ */
+
+/*
+ * Manual 32-bit big-endian to little-endian conversion.
+ * We cannot use __builtin_bswap32 because on RISC-V without the Zbb
+ * extension the compiler emits a call to libgcc's __bswapsi2, which
+ * is unavailable in a freestanding (-nostdlib) environment.
+ */
+static inline uint32 bswap32(uint32 x)
+{
+ return ((x & 0xFF000000u) >> 24) |
+ ((x & 0x00FF0000u) >> 8) |
+ ((x & 0x0000FF00u) << 8) |
+ ((x & 0x000000FFu) << 24);
+}
+
+/*
+ * Read a big-endian cell value from the FDT struct block.
+ * @cells: number of 32-bit cells (1 or 2).
+ * 2-cell values are common for 64-bit addresses/sizes.
+ */
+static inline uint64 read_cells(const uint8 *data, uint32 cells)
+{
+ const uint32 *p = reinterpret_cast<const uint32 *>(data);
+ if (cells == 2) {
+ uint64 high = bswap32(p[0]);
+ uint64 low = bswap32(p[1]);
+ return (high << 32) | low;
+ }
+ return bswap32(p[0]);
+}
+
+/* ------------------------------------------------------------------ */
+/* FdtManager construction */
+/* ------------------------------------------------------------------ */
+
+FdtManager::FdtManager(uint64 fdt_paddr) : fdt_paddr_(ensure_va(fdt_paddr)) {}
+
+/* ------------------------------------------------------------------ */
+/* Phase 1: Early scan — memory layout */
+/* ------------------------------------------------------------------ */
+
+/*
+ * Walk the raw FDT struct block to locate the /memory node and
+ * extract its "reg" property (base address + size).
+ *
+ * Cell sizes (#address-cells, #size-cells) are tracked per depth
+ * level to correctly decode the "reg" value under any bus topology.
+ *
+ * Panics on invalid magic or missing /memory node — there is no
+ * recovery path this early in boot.
+ */
+void FdtManager::early_scan_mem(uint64 fdt_paddr, uint64 *base, uint64 *size)
+{
+ const fdt_header *hdr = reinterpret_cast<const fdt_header *>(fdt_paddr);
+ if (bswap32(hdr->magic) != FDT_MAGIC)
+ kernel_panic("FDT early_scan_mem: invalid magic number", nullptr);
+
+ const uint8 *dt_struct =
+ reinterpret_cast<const uint8 *>(fdt_paddr) + bswap32(hdr->off_dt_struct);
+ const char *dt_strings =
+ reinterpret_cast<const char *>(fdt_paddr) + bswap32(hdr->off_dt_strings);
+
+ uint32 offset = 0;
+ int depth = -1;
+
+ // Per-depth cell sizes (inherit from parent on entry)
+ uint32 address_cells[16] = {2};
+ uint32 size_cells[16] = {1};
+ bool in_memory_node = false;
+
+ while (true) {
+ uint32 token = bswap32(
+ *reinterpret_cast<const uint32 *>(dt_struct + offset));
+ offset += 4;
+
+ if (token == FDT_BEGIN_NODE) {
+ const char *name = reinterpret_cast<const char *>(dt_struct + offset);
+ uint32 name_len = 0;
+ while (name[name_len] != '\0')
+ name_len++;
+ offset = (offset + name_len + 1 + 3) & ~3u; // align to 4 bytes
+
+ depth++;
+
+ // Inherit parent's cell sizes
+ if (depth > 0 && depth < 16) {
+ address_cells[depth] = address_cells[depth - 1];
+ size_cells[depth] = size_cells[depth - 1];
+ }
+
+ // Match top-level "memory" or "memory@..." nodes
+ in_memory_node = (depth == 1 && str_starts_with(name, "memory"));
+
+ } else if (token == FDT_END_NODE) {
+ if (depth >= 0)
+ depth--;
+ in_memory_node = false;
+
+ } else if (token == FDT_PROP) {
+ uint32 len = bswap32(
+ *reinterpret_cast<const uint32 *>(dt_struct + offset));
+ uint32 nameoff = bswap32(
+ *reinterpret_cast<const uint32 *>(dt_struct + offset + 4));
+ offset += 8;
+
+ const char *prop_name = dt_strings + nameoff;
+ const uint8 *prop_val = dt_struct + offset;
+
+ if (depth >= 0 && depth < 16) {
+ // Track cell size overrides at the current depth
+ if (str_equals(prop_name, "#address-cells")) {
+ address_cells[depth] = bswap32(
+ *reinterpret_cast<const uint32 *>(prop_val));
+ } else if (str_equals(prop_name, "#size-cells")) {
+ size_cells[depth] = bswap32(
+ *reinterpret_cast<const uint32 *>(prop_val));
+ }
+ // Decode the "reg" property using the parent's cell sizes
+ else if (in_memory_node && str_equals(prop_name, "reg")) {
+ uint32 p_depth = (depth > 0) ? depth - 1 : 0;
+ *base = read_cells(prop_val, address_cells[p_depth]);
+ *size = read_cells(
+ prop_val + address_cells[p_depth] * 4,
+ size_cells[p_depth]);
+ return; // Success
+ }
+ }
+
+ offset = (offset + len + 3) & ~3u; // align to 4 bytes
+
+ } else if (token == FDT_NOP) {
+ continue;
+ } else if (token == FDT_END) {
+ break;
+ } else {
+ kernel_panic("FDT early_scan_mem: unknown token", nullptr);
+ }
+ }
+
+ kernel_panic("FDT early_scan_mem: /memory node not found", nullptr);
+}
+
+/* ------------------------------------------------------------------ */
+/* Phase 1: Early scan — UART address */
+/* ------------------------------------------------------------------ */
+
+/*
+ * Locate a UART node by matching compatible = "ns16550a" and return
+ * its base address from the "reg" property.
+ *
+ * Unlike early_scan_mem, failure here is non-fatal: we fall back to
+ * the platform's default UART address (0x10000000 for QEMU virt).
+ */
+void FdtManager::early_scan_uart(uint64 fdt_paddr, uint64 *uart_addr)
+{
+ if (!uart_addr)
+ return;
+
+ const fdt_header *hdr = reinterpret_cast<const fdt_header *>(fdt_paddr);
+ if (bswap32(hdr->magic) != FDT_MAGIC)
+ return;
+
+ const uint8 *dt_struct =
+ reinterpret_cast<const uint8 *>(fdt_paddr) + bswap32(hdr->off_dt_struct);
+ const char *dt_strings =
+ reinterpret_cast<const char *>(fdt_paddr) + bswap32(hdr->off_dt_strings);
+
+ uint32 offset = 0;
+ int depth = -1;
+ uint32 address_cells[16] = {2};
+ uint32 size_cells[16] = {1};
+ bool in_uart_node = false;
+
+ while (true) {
+ uint32 token = bswap32(
+ *reinterpret_cast<const uint32 *>(dt_struct + offset));
+ offset += 4;
+
+ if (token == FDT_BEGIN_NODE) {
+ const char *name = reinterpret_cast<const char *>(dt_struct + offset);
+ uint32 name_len = 0;
+ while (name[name_len] != '\0')
+ name_len++;
+ offset = (offset + name_len + 1 + 3) & ~3u;
+
+ depth++;
+ if (depth > 0 && depth < 16) {
+ address_cells[depth] = address_cells[depth - 1];
+ size_cells[depth] = size_cells[depth - 1];
+ }
+ in_uart_node = false;
+
+ } else if (token == FDT_END_NODE) {
+ if (depth >= 0)
+ depth--;
+ in_uart_node = false;
+
+ } else if (token == FDT_PROP) {
+ uint32 len = bswap32(
+ *reinterpret_cast<const uint32 *>(dt_struct + offset));
+ uint32 nameoff = bswap32(
+ *reinterpret_cast<const uint32 *>(dt_struct + offset + 4));
+ offset += 8;
+
+ const char *prop_name = dt_strings + nameoff;
+ const uint8 *prop_val = dt_struct + offset;
+
+ if (depth >= 0 && depth < 16) {
+ if (str_equals(prop_name, "#address-cells")) {
+ address_cells[depth] = bswap32(
+ *reinterpret_cast<const uint32 *>(prop_val));
+ } else if (str_equals(prop_name, "#size-cells")) {
+ size_cells[depth] = bswap32(
+ *reinterpret_cast<const uint32 *>(prop_val));
+ } else if (str_equals(prop_name, "compatible")) {
+ if (prop_contains_string(
+ reinterpret_cast<const char *>(prop_val),
+ len, "ns16550a")) {
+ in_uart_node = true;
+ }
+ } else if (in_uart_node && str_equals(prop_name, "reg")) {
+ uint32 p_depth = (depth > 0) ? depth - 1 : 0;
+ *uart_addr = read_cells(prop_val, address_cells[p_depth]);
+ return; // Found it
+ }
+ }
+
+ offset = (offset + len + 3) & ~3u;
+
+ } else if (token == FDT_NOP) {
+ continue;
+ } else if (token == FDT_END) {
+ break;
+ } else {
+ break; // Unknown token — give up silently
+ }
+ }
+
+ *uart_addr = 0;
+}
+
+/* ------------------------------------------------------------------ */
+/* Phase 2: Unflatten (stub — requires Slab) */
+/* ------------------------------------------------------------------ */
+
+void FdtManager::unflatten()
+{
+ const fdt_header *hdr = reinterpret_cast<const fdt_header *>(fdt_paddr_);
+ if (bswap32(hdr->magic) != FDT_MAGIC)
+ kernel_panic("fdt unflatten: invalid magic", nullptr);
+
+ const uint8 *dt_struct =
+ reinterpret_cast<const uint8 *>(fdt_paddr_) + bswap32(hdr->off_dt_struct);
+ const char *dt_strings =
+ reinterpret_cast<const char *>(fdt_paddr_) + bswap32(hdr->off_dt_strings);
+
+ uint32 offset = 0;
+
+ /* Stack to track current node at each depth (max 16 levels) */
+ DeviceNode *stack[16] = {};
+ int depth = -1;
+
+ while (true) {
+ uint32 token = bswap32(
+ *reinterpret_cast<const uint32 *>(dt_struct + offset));
+ offset += 4;
+
+ if (token == FDT_BEGIN_NODE) {
+ const char *name = reinterpret_cast<const char *>(dt_struct + offset);
+ uint32 name_len = 0;
+ while (name[name_len] != '\0')
+ name_len++;
+ offset = (offset + name_len + 1 + 3) & ~3u;
+
+ depth++;
+ if (depth >= 16)
+ kernel_panic("fdt unflatten: tree too deep", nullptr);
+
+ DeviceNode *parent = (depth > 0) ? stack[depth - 1] : nullptr;
+ DeviceNode *node = new DeviceNode(parent, name);
+ if (!node)
+ kernel_panic("fdt unflatten: OOM creating DeviceNode", nullptr);
+
+ stack[depth] = node;
+
+ if (parent)
+ parent->add_child(node);
+ else
+ root_ = node; /* Root node */
+
+ } else if (token == FDT_END_NODE) {
+ if (depth >= 0)
+ depth--;
+
+ } else if (token == FDT_PROP) {
+ uint32 len = bswap32(
+ *reinterpret_cast<const uint32 *>(dt_struct + offset));
+ uint32 nameoff = bswap32(
+ *reinterpret_cast<const uint32 *>(dt_struct + offset + 4));
+ offset += 8;
+
+ const char *prop_name = dt_strings + nameoff;
+ const void *prop_val = dt_struct + offset;
+
+ if (depth >= 0 && depth < 16 && stack[depth]) {
+ FdtProperty *prop = new FdtProperty;
+ if (!prop)
+ kernel_panic("fdt unflatten: OOM creating FdtProperty", nullptr);
+ prop->name = prop_name;
+ prop->value = prop_val;
+ prop->len = static_cast<int>(len);
+ prop->link.init();
+ stack[depth]->add_prop(prop);
+ }
+
+ offset = (offset + len + 3) & ~3u;
+
+ } else if (token == FDT_NOP) {
+ continue;
+ } else if (token == FDT_END) {
+ break;
+ } else {
+ kernel_panic("fdt unflatten: unknown token", nullptr);
+ }
+ }
+
+ is_unflattened_ = true;
+}
+
+/* Recursive helper: find first node with matching compatible string */
+static DeviceNode *find_compat_recursive(DeviceNode *node, const char *compat)
+{
+ const FdtProperty *prop = node->get_prop("compatible");
+ if (prop) {
+ const char *val = static_cast<const char *>(prop->value);
+ uint32 i = 0;
+ while (i < static_cast<uint32>(prop->len)) {
+ const char *s = val + i;
+ if (str_equals(s, compat))
+ return node;
+ while (i < static_cast<uint32>(prop->len) && val[i] != '\0')
+ i++;
+ i++;
+ }
+ }
+
+ /* Search children */
+ list_node *cur = node->children_list_head();
+ list_node *end = node->children_list_sentinel();
+ while (cur != end) {
+ DeviceNode *child = list_entry<DeviceNode, &DeviceNode::sibling_link_>(cur);
+ DeviceNode *found = find_compat_recursive(child, compat);
+ if (found)
+ return found;
+ cur = cur->next;
+ }
+ return nullptr;
+}
+
+DeviceNode *FdtManager::find_compatible(const char *compat_string)
+{
+ if (!is_unflattened_)
+ kernel_panic("fdt: tree not unflattened yet", nullptr);
+ if (!root_)
+ return nullptr;
+ return find_compat_recursive(root_, compat_string);
+}
+
+DeviceNode *FdtManager::get_node_by_path(const char *path)
+{
+ if (!is_unflattened_)
+ kernel_panic("fdt: tree not unflattened yet", nullptr);
+ if (!root_ || !path)
+ return nullptr;
+
+ /* Skip leading '/' */
+ if (*path == '/')
+ path++;
+ if (*path == '\0')
+ return root_;
+
+ DeviceNode *cur = root_;
+ while (*path && cur) {
+ /* Extract next path component */
+ const char *end = path;
+ while (*end && *end != '/')
+ end++;
+
+ /* Search children for a name matching this component */
+ bool found = false;
+ list_node *lc = cur->children_list_head();
+ list_node *le = cur->children_list_sentinel();
+ while (lc != le) {
+ DeviceNode *child = list_entry<DeviceNode, &DeviceNode::sibling_link_>(lc);
+ /* Compare name up to the component length */
+ const char *cn = child->get_name();
+ const char *p = path;
+ const char *e = end;
+ bool match = true;
+ while (p < e) {
+ if (*cn != *p) { match = false; break; }
+ cn++; p++;
+ }
+ if (match && *cn == '\0') {
+ cur = child;
+ found = true;
+ break;
+ }
+ lc = lc->next;
+ }
+
+ if (!found)
+ return nullptr;
+
+ path = (*end == '/') ? end + 1 : end;
+ }
+ return cur;
+}
+
+/* ------------------------------------------------------------------ */
+/* Public free-function API */
+/* ------------------------------------------------------------------ */
+
+void fdt_init(uint64 fdt_paddr)
+{
+ const uint32 *magic_ptr = reinterpret_cast<const uint32 *>(fdt_paddr);
+ if (bswap32(*magic_ptr) != FDT_MAGIC)
+ kernel_panic("fdt_init: invalid FDT magic number", nullptr);
+
+ g_fdt = new (g_fdt_buf) FdtManager(fdt_paddr);
+}
+
+void fdt_unflatten()
+{
+ g_fdt->unflatten();
+}
+
+DeviceNode *fdt_find_compatible(const char *compat_string)
+{
+ return g_fdt->find_compatible(compat_string);
+}
+
+DeviceNode *fdt_get_node_by_path(const char *path)
+{
+ return g_fdt->get_node_by_path(path);
+}
+
+void fdt_early_get_mem_info(uint64 *base, uint64 *size)
+{
+ FdtManager::early_scan_mem(g_fdt->get_paddr(), base, size);
+}
+
+void fdt_early_get_uart_info(uint64 *uart_addr)
+{
+ FdtManager::early_scan_uart(g_fdt->get_paddr(), uart_addr);
+}
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-29 09:18:51 +0000