diff options
| author | Richard Qin <richard.qin.x@gmail.com> | 2026-04-21 23:12:07 +0800 |
|---|---|---|
| committer | Richard Qin <richard.qin.x@gmail.com> | 2026-04-21 23:12:07 +0800 |
| commit | 143a1392890a0c0bbcd79b5c77c71a75846fcc27 (patch) | |
| tree | 1b819947fbb95d42f98e4cc291a9514bf5a80d95 /na/fdt | |
| parent | 23fc4a0d6e57eb74248da8fb22d8c6a9d99f69c3 (diff) | |
| download | lume-143a1392890a0c0bbcd79b5c77c71a75846fcc27.tar.gz lume-143a1392890a0c0bbcd79b5c77c71a75846fcc27.tar.xz | |
feat: implement DeviceNode and FdtManager classes for device tree management
Diffstat (limited to 'na/fdt')
| -rw-r--r-- | na/fdt/device_node.cc | 166 | ||||
| -rw-r--r-- | na/fdt/fdt.cc | 555 |
2 files changed, 721 insertions, 0 deletions
diff --git a/na/fdt/device_node.cc b/na/fdt/device_node.cc new file mode 100644 index 0000000..0c8ad46 --- /dev/null +++ b/na/fdt/device_node.cc @@ -0,0 +1,166 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* Copyright (C) 2026 Richard Qin */ + +/* + * device_node.cc — DeviceNode implementation + * + * Provides property lookup and child traversal for the unflattened + * device tree. After construction, the tree is globally read-only. + * + * Reference: docs/specs/fdt.md §3.2 + */ + +#include <lume/device_node.h> + +/* Minimal strcmp — no lib dependency */ +static bool str_eq(const char *a, const char *b) +{ + while (*a && *a == *b) { a++; b++; } + return *a == *b; +} + +/* ------------------------------------------------------------------ */ +/* Construction / Destruction */ +/* ------------------------------------------------------------------ */ + +DeviceNode::DeviceNode(DeviceNode *parent, const char *name) + : name_(name), parent_(parent) +{ + children_list_.init(); + props_list_.init(); + sibling_link_.init(); +} + +DeviceNode::~DeviceNode() +{ + /* Recursively delete children */ + list_node *cur = children_list_.next; + while (cur != &children_list_) { + list_node *next = cur->next; + /* Recover DeviceNode* from sibling_link_ offset */ + DeviceNode *child = list_entry<DeviceNode, &DeviceNode::sibling_link_>(cur); + delete child; + cur = next; + } + + /* Delete properties */ + list_node *pc = props_list_.next; + while (pc != &props_list_) { + list_node *pn = pc->next; + FdtProperty *prop = reinterpret_cast<FdtProperty *>( + reinterpret_cast<uintptr>(pc) - + __builtin_offsetof(FdtProperty, link)); + delete prop; + pc = pn; + } +} + +/* ------------------------------------------------------------------ */ +/* Tree construction (used by FdtManager::unflatten) */ +/* ------------------------------------------------------------------ */ + +void DeviceNode::add_child(DeviceNode *child) +{ + /* Append to end of children list */ + list_node *node = &child->sibling_link_; + node->prev = children_list_.prev; + node->next = &children_list_; + children_list_.prev->next = node; + children_list_.prev = node; +} + +void DeviceNode::add_prop(FdtProperty *prop) +{ + list_node *node = &prop->link; + node->prev = props_list_.prev; + node->next = &props_list_; + props_list_.prev->next = node; + props_list_.prev = node; +} + +/* ------------------------------------------------------------------ */ +/* Property access */ +/* ------------------------------------------------------------------ */ + +const FdtProperty *DeviceNode::get_prop(const char *name) const +{ + const list_node *cur = props_list_.next; + while (cur != &props_list_) { + const FdtProperty *prop = reinterpret_cast<const FdtProperty *>( + reinterpret_cast<uintptr>(cur) - + __builtin_offsetof(FdtProperty, link)); + if (str_eq(prop->name, name)) + return prop; + cur = cur->next; + } + return nullptr; +} + +/* Big-endian helpers for decoding property values */ +static inline uint32 be32(const void *p) +{ + const uint8 *b = static_cast<const uint8 *>(p); + return (uint32(b[0]) << 24) | (uint32(b[1]) << 16) | + (uint32(b[2]) << 8) | uint32(b[3]); +} + +static inline uint64 be64(const void *p) +{ + const uint8 *b = static_cast<const uint8 *>(p); + return (uint64(be32(b)) << 32) | uint64(be32(b + 4)); +} + +uint32 DeviceNode::get_prop_u32(const char *name, uint32 default_val) const +{ + const FdtProperty *p = get_prop(name); + if (!p || p->len < 4) + return default_val; + return be32(p->value); +} + +uint64 DeviceNode::get_prop_u64(const char *name, uint64 default_val) const +{ + const FdtProperty *p = get_prop(name); + if (!p) + return default_val; + if (p->len >= 8) + return be64(p->value); + if (p->len >= 4) + return be32(p->value); + return default_val; +} + +const char *DeviceNode::get_prop_string(const char *name) const +{ + const FdtProperty *p = get_prop(name); + if (!p || p->len == 0) + return nullptr; + return static_cast<const char *>(p->value); +} + +/* ------------------------------------------------------------------ */ +/* Child traversal */ +/* ------------------------------------------------------------------ */ + +DeviceNode *DeviceNode::find_child(const char *name) +{ + list_node *cur = children_list_.next; + while (cur != &children_list_) { + DeviceNode *child = list_entry<DeviceNode, &DeviceNode::sibling_link_>(cur); + if (str_eq(child->name_, name)) + return child; + cur = cur->next; + } + return nullptr; +} + +void DeviceNode::for_each_child(void (*callback)(DeviceNode *)) +{ + list_node *cur = children_list_.next; + while (cur != &children_list_) { + list_node *next = cur->next; + DeviceNode *child = list_entry<DeviceNode, &DeviceNode::sibling_link_>(cur); + callback(child); + cur = next; + } +} 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); +} |
