LibDeviceTree: Add walk_device_tree and use it to dump structured data

We can use this simple parser and its callbacks to implement more
complex parsing in later commits.

5 files changed, 177 insertions, 2 deletions

diff --git a/Userland/Libraries/LibDeviceTree/CMakeLists.txt b/Userland/Libraries/LibDeviceTree/CMakeLists.txt
index 569153aa74..16db2e0aec 100644
--- a/Userland/Libraries/LibDeviceTree/CMakeLists.txt
+++ b/Userland/Libraries/LibDeviceTree/CMakeLists.txt
@@ -1,5 +1,6 @@
 
 set(SOURCES
+  FlattenedDeviceTree.cpp
   Validation.cpp
 )
 
diff --git a/Userland/Libraries/LibDeviceTree/FlattenedDeviceTree.cpp b/Userland/Libraries/LibDeviceTree/FlattenedDeviceTree.cpp
new file mode 100644
index 0000000000..5d2f235dad
--- /dev/null
+++ b/Userland/Libraries/LibDeviceTree/FlattenedDeviceTree.cpp
@@ -0,0 +1,111 @@
+/*
+ * Copyright (c) 2023, Andrew Kaster <akaster@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <AK/ByteBuffer.h>
+#include <AK/Error.h>
+#include <AK/IterationDecision.h>
+#include <AK/MemoryStream.h>
+#include <AK/StringView.h>
+#include <LibDeviceTree/FlattenedDeviceTree.h>
+
+namespace DeviceTree {
+
+static ErrorOr<StringView> read_string_view(ReadonlyBytes bytes, StringView error_string)
+{
+    auto len = strnlen(reinterpret_cast<char const*>(bytes.data()), bytes.size());
+    if (len == bytes.size()) {
+        return Error::from_string_view_or_print_error_and_return_errno(error_string, EINVAL);
+    }
+    return StringView { bytes.slice(0, len) };
+}
+
+ErrorOr<void> walk_device_tree(FlattenedDeviceTreeHeader const& header, ReadonlyBytes raw_device_tree, DeviceTreeCallbacks callbacks)
+{
+    ReadonlyBytes struct_bytes { raw_device_tree.data() + header.off_dt_struct, header.size_dt_struct };
+    FixedMemoryStream stream(struct_bytes);
+    char const* begin_strings_block = reinterpret_cast<char const*>(raw_device_tree.data() + header.off_dt_strings);
+
+    FlattenedDeviceTreeTokenType prev_token = EndNode;
+    StringView current_node_name;
+
+    while (!stream.is_eof()) {
+        auto current_token = TRY(stream.read_value<BigEndian<u32>>());
+
+        switch (current_token) {
+        case BeginNode: {
+            current_node_name = TRY(read_string_view(struct_bytes.slice(stream.offset()), "Non-null terminated name for FDT_BEGIN_NODE token!"sv));
+            size_t const consume_len = round_up_to_power_of_two(current_node_name.length() + 1, 4);
+            TRY(stream.discard(consume_len));
+            if (callbacks.on_node_begin) {
+                if (IterationDecision::Break == TRY(callbacks.on_node_begin(current_node_name)))
+                    return {};
+            }
+            break;
+        }
+        case EndNode:
+            if (callbacks.on_node_end) {
+                if (IterationDecision::Break == TRY(callbacks.on_node_end(current_node_name)))
+                    return {};
+            }
+            break;
+        case Property: {
+            if (prev_token == EndNode) {
+                return Error::from_string_view_or_print_error_and_return_errno("Invalid node sequence, FDT_PROP after FDT_END_NODE"sv, EINVAL);
+            }
+            auto len = TRY(stream.read_value<BigEndian<u32>>());
+            auto nameoff = TRY(stream.read_value<BigEndian<u32>>());
+            if (nameoff >= header.size_dt_strings) {
+                return Error::from_string_view_or_print_error_and_return_errno("Invalid name offset in FDT_PROP"sv, EINVAL);
+            }
+            size_t const prop_name_max_len = header.size_dt_strings - nameoff;
+            size_t const prop_name_len = strnlen(begin_strings_block + nameoff, prop_name_max_len);
+            if (prop_name_len == prop_name_max_len) {
+                return Error::from_string_view_or_print_error_and_return_errno("Non-null terminated name for FDT_PROP token!"sv, EINVAL);
+            }
+            StringView prop_name(begin_strings_block + nameoff, prop_name_len);
+            if (len >= stream.remaining()) {
+                return Error::from_string_view_or_print_error_and_return_errno("Property value length too large"sv, EINVAL);
+            }
+            ReadonlyBytes prop_value;
+            if (len != 0) {
+                prop_value = { struct_bytes.slice(stream.offset()).data(), len };
+                size_t const consume_len = round_up_to_power_of_two(static_cast<u32>(len), 4);
+                TRY(stream.discard(consume_len));
+            }
+            if (callbacks.on_property) {
+                if (IterationDecision::Break == TRY(callbacks.on_property(prop_name, prop_value)))
+                    return {};
+            }
+            break;
+        }
+        case NoOp:
+            if (callbacks.on_noop) {
+                if (IterationDecision::Break == TRY(callbacks.on_noop()))
+                    return {};
+            }
+            break;
+        case End: {
+            if (prev_token == BeginNode || prev_token == Property) {
+                return Error::from_string_view_or_print_error_and_return_errno("Invalid node sequence, FDT_END after BEGIN_NODE or PROP"sv, EINVAL);
+            }
+            if (!stream.is_eof()) {
+                return Error::from_string_view_or_print_error_and_return_errno("Expected EOF at FTD_END but more data remains"sv, EINVAL);
+            }
+
+            if (callbacks.on_end) {
+                return callbacks.on_end();
+            }
+            return {};
+        }
+        default:
+            return Error::from_string_view_or_print_error_and_return_errno("Invalid token"sv, EINVAL);
+        }
+        prev_token = static_cast<FlattenedDeviceTreeTokenType>(static_cast<u32>(current_token));
+    }
+    return Error::from_string_view_or_print_error_and_return_errno("Unexpected end of stream"sv, EINVAL);
+}
+
+} // namespace DeviceTree
diff --git a/Userland/Libraries/LibDeviceTree/FlattenedDeviceTree.h b/Userland/Libraries/LibDeviceTree/FlattenedDeviceTree.h
index 053dc73507..c11d9fcfb2 100644
--- a/Userland/Libraries/LibDeviceTree/FlattenedDeviceTree.h
+++ b/Userland/Libraries/LibDeviceTree/FlattenedDeviceTree.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2021, Andrew Kaster <akaster@serenityos.org>
+ * Copyright (c) 2021-2023, Andrew Kaster <akaster@serenityos.org>
  *
  * SPDX-License-Identifier: BSD-2-Clause
  */
@@ -7,6 +7,10 @@
 #pragma once
 
 #include <AK/Endian.h>
+#include <AK/Error.h>
+#include <AK/Function.h>
+#include <AK/IterationDecision.h>
+#include <AK/StringView.h>
 #include <AK/Types.h>
 
 namespace DeviceTree {
@@ -37,4 +41,23 @@ struct FlattenedDeviceTreeReserveEntry {
 };
 static_assert(sizeof(FlattenedDeviceTreeReserveEntry) == 16, "FDT Memory Reservation entry size must match specification");
 
+// https://devicetree-specification.readthedocs.io/en/v0.3/flattened-format.html#lexical-structure
+enum FlattenedDeviceTreeTokenType : u32 {
+    BeginNode = 1,
+    EndNode = 2,
+    Property = 3,
+    NoOp = 4,
+    End = 9
+};
+
+struct DeviceTreeCallbacks {
+    Function<ErrorOr<IterationDecision>(StringView)> on_node_begin;
+    Function<ErrorOr<IterationDecision>(StringView)> on_node_end;
+    Function<ErrorOr<IterationDecision>(StringView, ReadonlyBytes)> on_property;
+    Function<ErrorOr<IterationDecision>()> on_noop;
+    Function<ErrorOr<void>()> on_end;
+};
+
+ErrorOr<void> walk_device_tree(FlattenedDeviceTreeHeader const&, ReadonlyBytes raw_device_tree, DeviceTreeCallbacks);
+
 } // namespace DeviceTree
diff --git a/Userland/Libraries/LibDeviceTree/Validation.cpp b/Userland/Libraries/LibDeviceTree/Validation.cpp
index a30312a3ea..892a384403 100644
--- a/Userland/Libraries/LibDeviceTree/Validation.cpp
+++ b/Userland/Libraries/LibDeviceTree/Validation.cpp
@@ -4,6 +4,8 @@
  * SPDX-License-Identifier: BSD-2-Clause
  */
 
+#include <AK/AllOf.h>
+#include <AK/CharacterTypes.h>
 #include <AK/DeprecatedString.h>
 #include <AK/Endian.h>
 #include <AK/Format.h>
@@ -138,7 +140,44 @@ ErrorOr<void> dump(FlattenedDeviceTreeHeader const& header, ReadonlyBytes raw_de
         next_block_offset += sizeof(FlattenedDeviceTreeReserveEntry);
     }
 
-    return {};
+    return dump_flattened_device_tree_structure(header, raw_device_tree);
 }
 
+ErrorOr<void> dump_flattened_device_tree_structure(FlattenedDeviceTreeHeader const& header, ReadonlyBytes raw_device_tree)
+{
+    u8 indent = 0;
+    DeviceTreeCallbacks callbacks = {
+        .on_node_begin = [&](StringView token_name) -> ErrorOr<IterationDecision> {
+            outln("{: >{}}FDT_BEGIN_NODE: {}", ""sv, indent * 2, token_name);
+            ++indent;
+            return IterationDecision::Continue;
+        },
+        .on_node_end = [&](StringView) -> ErrorOr<IterationDecision> {
+            --indent;
+            outln("{: >{}}FDT_END_NODE", ""sv, indent * 2);
+            return IterationDecision::Continue;
+        },
+        .on_property = [&](StringView property_name, ReadonlyBytes property_value) -> ErrorOr<IterationDecision> {
+            StringView property_as_string { property_value };
+            // Note: We want to figure out if the value is a string, a stringlist, a number or something unprintable.
+            //     In reality, the entity retrieving the value needs to know if it's a u32, u64, string, stringlist, or "property-encoded-value" a priori
+            bool const is_print = (property_as_string.length() > 0) && all_of(property_as_string.begin(), --property_as_string.end(), [](char c) { return is_ascii_printable(c); });
+            if (is_print)
+                outln("{: >{}}FDT_PROP: {}: {}", ""sv, indent * 2, property_name, property_as_string);
+            else
+                outln("{: >{}}FDT_PROP: {}: {:hex-dump}", ""sv, indent * 2, property_name, property_as_string);
+            return IterationDecision::Continue;
+        },
+        .on_noop = [&]() -> ErrorOr<IterationDecision> {
+            outln("{: >{}}FDT_NOOP", ""sv, indent * 2);
+            return IterationDecision::Continue;
+        },
+        .on_end = []() -> ErrorOr<void> {
+            outln("FDT_END");
+            return {};
+        }
+    };
+
+    return walk_device_tree(header, raw_device_tree, move(callbacks));
+}
 } // namespace DeviceTree
diff --git a/Userland/Libraries/LibDeviceTree/Validation.h b/Userland/Libraries/LibDeviceTree/Validation.h
index fcd21c207e..63cceba81f 100644
--- a/Userland/Libraries/LibDeviceTree/Validation.h
+++ b/Userland/Libraries/LibDeviceTree/Validation.h
@@ -18,5 +18,6 @@ enum class Verbose {
 bool validate_flattened_device_tree(FlattenedDeviceTreeHeader const& header, ReadonlyBytes raw_device_tree, Verbose = Verbose::No);
 
 ErrorOr<void> dump(FlattenedDeviceTreeHeader const& header, ReadonlyBytes raw_device_tree);
+ErrorOr<void> dump_flattened_device_tree_structure(FlattenedDeviceTreeHeader const& header, ReadonlyBytes raw_device_tree);
 
 }