Libraries: Add LibDeviceTree for manipulating OpenFirmware Device Trees

Starting with header validation and a dump() method that can be used to
debug future parsing work.

5 files changed, 214 insertions, 0 deletions

diff --git a/Userland/Libraries/CMakeLists.txt b/Userland/Libraries/CMakeLists.txt
index 140ae6e3ee..f51f4d1390 100644
--- a/Userland/Libraries/CMakeLists.txt
+++ b/Userland/Libraries/CMakeLists.txt
@@ -12,6 +12,7 @@ add_subdirectory(LibCrypt)
 add_subdirectory(LibCrypto)
 add_subdirectory(LibDebug)
 add_subdirectory(LibDesktop)
+add_subdirectory(LibDeviceTree)
 add_subdirectory(LibDiff)
 add_subdirectory(LibDl)
 add_subdirectory(LibDSP)
diff --git a/Userland/Libraries/LibDeviceTree/CMakeLists.txt b/Userland/Libraries/LibDeviceTree/CMakeLists.txt
new file mode 100644
index 0000000000..f81192fc3c
--- /dev/null
+++ b/Userland/Libraries/LibDeviceTree/CMakeLists.txt
@@ -0,0 +1,7 @@
+
+set(SOURCES
+  Validation.cpp
+)
+
+serenity_lib(LibDeviceTree DeviceTree)
+target_link_libraries(LibDeviceTree LibC LibCore)
diff --git a/Userland/Libraries/LibDeviceTree/FlattenedDeviceTree.h b/Userland/Libraries/LibDeviceTree/FlattenedDeviceTree.h
new file mode 100644
index 0000000000..75b23c6964
--- /dev/null
+++ b/Userland/Libraries/LibDeviceTree/FlattenedDeviceTree.h
@@ -0,0 +1,41 @@
+/*
+ * Copyright (c) 2021, Andrew Kaster <akaster@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+#include <AK/Endian.h>
+#include <AK/Types.h>
+
+namespace DeviceTree {
+
+// https://devicetree-specification.readthedocs.io/en/v0.3/flattened-format.html
+struct FlattenedDeviceTreeHeader {
+    BigEndian<u32> magic;             // 0xDOODFEED (BE)
+    BigEndian<u32> totalsize;         // Total size of entire blob including padding b/w and after fields
+    BigEndian<u32> off_dt_struct;     // Offset of StructureBlock from beginning of header
+                                      // https://devicetree-specification.readthedocs.io/en/v0.3/flattened-format.html#sect-fdt-structure-block
+    BigEndian<u32> off_dt_strings;    // Offset of StringsBlock from beginning of header
+                                      // https://devicetree-specification.readthedocs.io/en/v0.3/flattened-format.html#sect-fdt-strings-block
+    BigEndian<u32> off_mem_rsvmap;    // Offset of MemoryReservationBlock from beginning of header
+    BigEndian<u32> version;           // 0.3 spec defines version 17
+    BigEndian<u32> last_comp_version; // 0.3 spec back-compatible with version 16, mandated to be 16
+    BigEndian<u32> boot_cpuid_phys;   // Physical ID given in `reg` property of CPU node of boot cpu
+    BigEndian<u32> size_dt_strings;   // Length in bytes of StringsBlock
+    BigEndian<u32> size_dt_struct;    // Length in bytes of StructureBlock
+};
+static_assert(sizeof(FlattenedDeviceTreeHeader) == 40, "FDT Header size must match specification");
+
+// https://devicetree-specification.readthedocs.io/en/v0.3/flattened-format.html#format
+struct FlattenedDeviceTreeReserveEntry {
+    BigEndian<u64> address;
+    BigEndian<u64> size;
+
+    bool operator==(FlattenedDeviceTreeReserveEntry const& other) const { return other.address == address && other.size == size; }
+    bool operator!=(FlattenedDeviceTreeReserveEntry const& other) const { return !(operator==(other)); }
+};
+static_assert(sizeof(FlattenedDeviceTreeReserveEntry) == 16, "FDT Memory Reservation entry size must match specification");
+
+} // namespace DeviceTree
diff --git a/Userland/Libraries/LibDeviceTree/Validation.cpp b/Userland/Libraries/LibDeviceTree/Validation.cpp
new file mode 100644
index 0000000000..1a733f9085
--- /dev/null
+++ b/Userland/Libraries/LibDeviceTree/Validation.cpp
@@ -0,0 +1,143 @@
+/*
+ * Copyright (c) 2021, Andrew Kaster <akaster@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <AK/Endian.h>
+#include <AK/Format.h>
+#include <AK/String.h>
+#include <LibDeviceTree/Validation.h>
+
+namespace DeviceTree {
+
+bool validate_flattened_device_tree(FlattenedDeviceTreeHeader const& header, u8 const* blob_start, size_t blob_size, Verbose verbose)
+{
+    if (header.magic != 0xD00DFEEDU) {
+        if (verbose == Verbose::Yes)
+            warnln("FDT Header has invalid magic value 0x{:08x}. Are you sure it's a flattened device tree?", header.magic);
+        return false;
+    }
+
+    if ((header.off_mem_rsvmap & ~0x7) != header.off_mem_rsvmap) {
+        if (verbose == Verbose::Yes)
+            warnln("FDT Header's MemoryReservationBlock is not 8 byte aligned! Offset: 0x{:08x}", header.off_mem_rsvmap);
+        return false;
+    }
+
+    if ((header.off_dt_struct & ~0x3) != header.off_dt_struct) {
+        if (verbose == Verbose::Yes)
+            warnln("FDT Header's StructureBlock is not 4 byte aligned! Offset: 0x{:08x}", header.off_dt_struct);
+        return false;
+    }
+
+    if (header.totalsize != blob_size) {
+        if (verbose == Verbose::Yes)
+            warnln("FDT Header total size mismatch: {}, expected {}!", header.totalsize, blob_size);
+        return false;
+    }
+
+    if (header.off_dt_struct > blob_size) {
+        if (verbose == Verbose::Yes)
+            warnln("FDT Header reports larger StructureBlock offset than possible: {} but total size is {}!", header.off_dt_struct, blob_size);
+        return false;
+    }
+
+    if (header.off_dt_strings > blob_size) {
+        if (verbose == Verbose::Yes)
+            warnln("FDT Header reports larger StringsBlock offset than possible: {} but total size is {}!", header.off_dt_strings, blob_size);
+        return false;
+    }
+
+    if (header.off_mem_rsvmap > blob_size) {
+        if (verbose == Verbose::Yes)
+            warnln("FDT Header reports larger MemoryReservationBlock offset than possible: {} but total size is {}!", header.off_mem_rsvmap, blob_size);
+        return false;
+    }
+
+    // Verify format is correct. Header --> MemoryReservation --> Structures --> Strings
+    if (header.off_dt_strings <= header.off_dt_struct) {
+        if (verbose == Verbose::Yes)
+            warnln("FDT Header has invalid StringsBlock offset {}, must be after v (@ {})", header.off_dt_strings, header.off_dt_struct);
+        return false;
+    }
+
+    if (header.off_dt_struct <= header.off_mem_rsvmap) {
+        if (verbose == Verbose::Yes)
+            warnln("FDT Header has invalid StructureBlock offset {}, must be after MemoryReservationBlock (@ {})", header.off_dt_struct, header.off_mem_rsvmap);
+        return false;
+    }
+
+    if (header.version != 17) {
+        if (verbose == Verbose::Yes)
+            warnln("Expected FDT header version 17, got {}", header.version);
+        return false;
+    }
+
+    if (header.last_comp_version != 16) {
+        if (verbose == Verbose::Yes)
+            warnln("Expected FDT header last compatible version 16, got {}", header.last_comp_version);
+        return false;
+    }
+
+    auto* mem_reserve_block = reinterpret_cast<FlattenedDeviceTreeReserveEntry const*>(&blob_start[header.off_mem_rsvmap]);
+    u64 next_block_offset = header.off_mem_rsvmap + sizeof(FlattenedDeviceTreeReserveEntry);
+    while ((next_block_offset < header.off_dt_struct) && (*mem_reserve_block != FlattenedDeviceTreeReserveEntry {})) {
+        ++mem_reserve_block;
+        next_block_offset += sizeof(FlattenedDeviceTreeReserveEntry);
+    }
+
+    if (next_block_offset >= header.off_dt_strings) {
+        if (verbose == Verbose::Yes)
+            warnln("FDT malformed, MemoryReservationBlock spill into StructureBlock section!");
+        return false;
+    }
+
+    // check for overlap. Overflow not possible b/c the fields are u32
+    u64 structure_block_size = header.off_dt_struct + header.size_dt_struct;
+    if ((structure_block_size > header.off_dt_strings) || (structure_block_size > blob_size)) {
+        if (verbose == Verbose::Yes)
+            warnln("FDT Header reports invalid StructureBlock block size: {} is too large given StringsBlock offset {} and total size {}", structure_block_size, header.off_dt_strings, blob_size);
+        return false;
+    }
+
+    u64 strings_block_size = header.off_dt_strings + header.size_dt_strings;
+    if (strings_block_size > blob_size) {
+        if (verbose == Verbose::Yes)
+            warnln("FDT Header reports invalid StringsBlock size: {} is too large given total size {}", structure_block_size, blob_size);
+        return false;
+    }
+
+    return true;
+}
+
+bool dump(FlattenedDeviceTreeHeader const& header, u8 const* blob_start, size_t blob_size)
+{
+    outln("/dts-v1/;");
+    outln("// magic:               0x{:08x}", header.magic);
+    outln("// totalsize:           0x{:08x} ({})", header.totalsize, header.totalsize);
+    outln("// off_dt_struct:       0x{:08x}", header.off_dt_struct);
+    outln("// off_dt_strings:      0x{:08x}", header.off_dt_strings);
+    outln("// off_mem_rsvmap:      0x{:08x}", header.off_mem_rsvmap);
+    outln("// version:             0x{:08x}", header.version);
+    outln("// last_comp_version:   0x{:08x}", header.last_comp_version);
+    outln("// boot_cpuid_phys:     0x{:08x}", header.boot_cpuid_phys);
+    outln("// size_dt_strings:     0x{:08x}", header.size_dt_strings);
+    outln("// size_dt_struct:      0x{:08x}", header.size_dt_struct);
+
+    if (!validate_flattened_device_tree(header, blob_start, blob_size, Verbose::Yes))
+        return false;
+
+    // Now that we know the device tree is valid, print out the rest of the information
+    auto* mem_reserve_block = reinterpret_cast<FlattenedDeviceTreeReserveEntry const*>(&blob_start[header.off_mem_rsvmap]);
+    u64 next_block_offset = header.off_mem_rsvmap + sizeof(FlattenedDeviceTreeReserveEntry);
+    while ((next_block_offset < header.off_dt_struct) && (*mem_reserve_block != FlattenedDeviceTreeReserveEntry {})) {
+        outln("/memreserve/ 0x{:08x} 0x{:08x};", mem_reserve_block->address, mem_reserve_block->size);
+        ++mem_reserve_block;
+        next_block_offset += sizeof(FlattenedDeviceTreeReserveEntry);
+    }
+
+    return true;
+}
+
+} // namespace DeviceTree
diff --git a/Userland/Libraries/LibDeviceTree/Validation.h b/Userland/Libraries/LibDeviceTree/Validation.h
new file mode 100644
index 0000000000..069ca6a818
--- /dev/null
+++ b/Userland/Libraries/LibDeviceTree/Validation.h
@@ -0,0 +1,22 @@
+/*
+ * Copyright (c) 2021, Andrew Kaster <akaster@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+#include <LibDeviceTree/FlattenedDeviceTree.h>
+
+namespace DeviceTree {
+
+enum class Verbose {
+    No,
+    Yes
+};
+
+bool validate_flattened_device_tree(FlattenedDeviceTreeHeader const& header, u8 const* blob_start, size_t blob_size, Verbose = Verbose::No);
+
+bool dump(FlattenedDeviceTreeHeader const& header, u8 const* blob_start, size_t blob_size);
+
+}