mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: Douglas Anderson <dianders@chromium.org>
To: Devicetree-compiler@vger.kernel.org,
	Rob Herring <robh@kernel.org>,
	Krzysztof Kozlowski <krzk+dt@kernel.org>,
	Conor Dooley <conor+dt@kernel.org>,
	Konrad Dybcio <konradybcio@kernel.org>
Cc: Devicetree@vger.kernel.org,
	"Tudor Ambarus" <tudor.ambarus@linaro.org>,
	"Chen-Yu Tsai" <wenst@chromium.org>,
	"Saravana Kannan" <saravanak@kernel.org>,
	"David Gibson" <david@gibson.dropbear.id.au>,
	"André Draszik" <andre.draszik@linaro.org>,
	"Simon Glass" <sjg@chromium.org>,
	linux-kernel@vger.kernel.org,
	"Brian Norris" <briannorris@chromium.org>,
	"Peter Griffin" <peter.griffin@linaro.org>,
	"Julius Werner" <jwerner@chromium.org>,
	"Douglas Anderson" <dianders@chromium.org>
Subject: [PATCH v4 07/14] libpydt: Add DeviceTree live tree representation
Date: Mon, 16 Nov 2026 12:53:04 -0800	[thread overview]
Message-ID: <20261116205320.1621386-8-dianders@chromium.org> (raw)
In-Reply-To: <20261116205320.1621386-1-dianders@chromium.org>

`pylibfdt`'s `Fdt` and `FdtRo` classes operate directly on flattened
device tree blobs, where inserting or deleting nodes and properties
shifts subsequent node offsets. That works well for in-place queries and
localized edits, but makes multi-tree comparison, structural diffing,
and bottom-up tree construction (as needed by the upcoming `fdtfactor`
tool) awkward and error-prone.

Add `pylibfdt/libpydt.py` providing `DeviceTree`, an in-memory live tree
representation where each node holds `props` (a dict mapping property
name to `libfdt.Property`) and `children` (a dict mapping child node
name to child `DeviceTree`), along with `unflatten()` and `flatten()` to
convert between `FdtRo`/`Fdt` blobs and live trees, and helpers for path
lookup, node creation, and pre-order traversal.

Add unit tests in `tests/libpydt_tests.py` covering `DeviceTree`
round-tripping, subtree unflattening, duplicate-name and corrupt-tree
rejection, and navigation helpers.

Assisted-by: Gemini:gemini-pro-prerelease
Signed-off-by: Douglas Anderson <dianders@chromium.org>
---

Changes in v4:
- Start the commit message with the motivation for a live tree and
  condense the summary (Simon Glass)
- Rename devicetree.py to libpydt.py (under pylibfdt/) to avoid
  colliding with PyPI's python-devicetree package, and move its unit
  tests into a separate tests/libpydt_tests.py file (Simon Glass, David
  Gibson)
- Unflatten the tree in a single O(n) pass using fdt.next_node() instead
  of recursive O(d * n) fdt.subnodes() traversal, raising FdtException
  on corrupt/truncated trees, and add a unit test (David Gibson, Simon
  Glass)
- Implement DeviceTree.walk() iteratively with an explicit stack instead
  of recursive yield from, and populate node.props directly in
  unflatten()
- Drop redundant fdt.pack() call from DeviceTree.flatten() (David
  Gibson)
- Drop get_*/set_* typed wrapper methods from DeviceTree in favor of
  Property.as_*() and Property.from_*() plus DeviceTree.set_prop()
  (David Gibson)
- Drop unnecessary copy.deepcopy() and compare unordered node/child sets
  instead of ordered lists in round-trip test (David Gibson)

Changes in v3:
- Move NodeTree out of pylibfdt/libfdt.i into a new devicetree.py module
  and rename it to DeviceTree (David Gibson)
- Store libfdt.Property objects in self.props instead of raw bytes
  (David Gibson)
- Return a packed libfdt.Fdt object from flatten() instead of raw bytes
  and use fdt.set_boot_cpuid_phys() (David Gibson, Simon Glass)
- Raise ValueError in unflatten() on duplicate property or sibling
  subnode names (Simon Glass)

Changes in v2:
- Split live tree representation out of fdtfactor (David Gibson)

 pylibfdt/libpydt.py    | 184 +++++++++++++++++++++++++++++++++++++++++
 pylibfdt/meson.build   |   2 +
 tests/libpydt_tests.py | 106 ++++++++++++++++++++++++
 tests/meson.build      |   2 +-
 tests/run_tests.sh     |  13 ++-
 5 files changed, 302 insertions(+), 5 deletions(-)
 create mode 100644 pylibfdt/libpydt.py
 create mode 100644 tests/libpydt_tests.py

diff --git a/pylibfdt/libpydt.py b/pylibfdt/libpydt.py
new file mode 100644
index 000000000000..6d8501f432ca
--- /dev/null
+++ b/pylibfdt/libpydt.py
@@ -0,0 +1,184 @@
+# SPDX-License-Identifier: (GPL-2.0-or-later OR BSD-2-Clause)
+"""libpydt - Non-flattened in-memory device tree representation in Python."""
+
+import libfdt
+
+
+class DeviceTree:
+    """In-memory live tree representation of a devicetree node and its subtree.
+
+    `props` and `children` are public dictionaries intended to be accessed and
+    manipulated directly by callers (e.g. `node.props['status'].as_str()`,
+    `node.props.get('reg')`, `node.children.get('soc')`), with `set_prop()`
+    provided as a convenience for inserting a `libfdt.Property` under its own
+    `prop.name`.
+
+    Attributes:
+        props: Dict mapping property name (str) to `libfdt.Property`.
+        children: Dict mapping child node name (str) to child `DeviceTree`.
+    """
+
+    def __init__(self):
+        self.props = {}
+        self.children = {}
+
+    @classmethod
+    def unflatten(cls, fdt, offset=0):
+        """Unflatten an FdtRo subtree starting at `offset` into a DeviceTree.
+
+        Args:
+            fdt: An `FdtRo` (or `Fdt`) instance.
+            offset: Starting node offset (default 0 for the root node).
+
+        Returns:
+            A `DeviceTree` representing the node at `offset` and its
+            descendants.
+
+        Raises:
+            ValueError: If a node contains duplicate property names or
+                duplicate sibling subnode names.
+        """
+        stack = []
+        depth = 0
+        while depth >= 0:
+            node = cls()
+            props = node.props
+            for prop in fdt.properties(offset):
+                name = prop.name
+                if name in props:
+                    raise ValueError(f'Duplicate property {name!r}')
+                props[name] = prop
+            if depth == 0:
+                stack = [node]
+            else:
+                parent = stack[depth - 1]
+                subname = fdt.get_name(offset)
+                if subname in parent.children:
+                    raise ValueError(f'Duplicate subnode {subname!r}')
+                parent.children[subname] = node
+                del stack[depth:]
+                stack.append(node)
+            offset, depth = fdt.next_node(offset, depth)
+            if offset < 0:
+                libfdt.check_err(offset)
+        return stack[0]
+
+    def _flatten_subtree(self, sw, name):
+        """Recursively write this DeviceTree and its children into an FdtSw.
+
+        Args:
+            sw: An `FdtSw` sequential-write instance.
+            name: Node name for this subtree (empty string `''` for root).
+        """
+        with sw.add_node(name):
+            for prop_name, val in self.props.items():
+                sw.property(prop_name, val)
+            for child_name, child_node in self.children.items():
+                child_node._flatten_subtree(sw, child_name)
+
+    def flatten(self, mem_rsv=(), boot_cpuid_phys=0):
+        """Serialize this root DeviceTree into a packed `libfdt.Fdt` object.
+
+        Args:
+            mem_rsv: Iterable of (address, size) tuples for the FDT memory
+                reservation block.
+            boot_cpuid_phys: Physical boot CPU ID for the FDT header.
+
+        Returns:
+            Packed `libfdt.Fdt` instance.
+        """
+        sw = libfdt.FdtSw()
+        for addr, size in mem_rsv:
+            sw.add_reservemap_entry(addr, size)
+        sw.finish_reservemap()
+        self._flatten_subtree(sw, '')
+        fdt = sw.as_fdt()
+        fdt.set_boot_cpuid_phys(boot_cpuid_phys)
+        return fdt
+
+    def set_prop(self, prop):
+        """Insert or replace a `libfdt.Property` in `self.props` under `prop.name`.
+
+        Args:
+            prop: `libfdt.Property` instance to store at `self.props[prop.name]`.
+        """
+        self.props[prop.name] = prop
+
+    def get_node(self, path):
+        """Look up a descendant DeviceTree by path without modifying the tree.
+
+        Follows the slash-separated node names in `path` starting from `self`
+        (leading, trailing, and repeated `'/'` characters are ignored, so
+        `'/soc/i2c@4000'` and `'soc/i2c@4000'` behave identically, and `''` or
+        `'/'` returns `self`). If any component along `path` is not present in
+        `children`, returns `None`.
+
+        Args:
+            path: Slash-separated node path starting from `self` (e.g.
+                `'/soc/i2c@4000'` or `'soc/i2c@4000'`).
+
+        Returns:
+            The `DeviceTree` at `path`, or `None` if not found.
+        """
+        node = self
+        for part in path.split('/'):
+            if not part:
+                continue
+            node = node.children.get(part)
+            if node is None:
+                return None
+        return node
+
+    def create_path(self, path):
+        """Return the descendant DeviceTree at `path`, creating missing nodes.
+
+        Looks up a child or deeper descendant `DeviceTree` by following the
+        slash-separated node names in `path` starting from `self` (leading,
+        trailing, and repeated `'/'` characters are ignored, so
+        `'/soc/i2c@4000'` and `'soc/i2c@4000'` behave identically). If any
+        node along `path` does not exist yet in `children`, a new empty
+        `DeviceTree` is created for it automatically (similar to `mkdir -p`).
+        Passing `''` or `'/'` returns `self`.
+
+        Example:
+            root = DeviceTree()
+            # Automatically creates root.children['soc'] and
+            # root.children['soc'].children['i2c@4000'], and returns the
+            # 'i2c@4000' DeviceTree.
+            i2c = root.create_path('/soc/i2c@4000')
+            i2c.set_prop(libfdt.Property.from_str('status', 'okay'))
+
+        Args:
+            path: Slash-separated node path starting from `self` (e.g.
+                `'/soc/i2c@4000'` or `'soc/i2c@4000'`).
+
+        Returns:
+            The `DeviceTree` instance at `path`.
+        """
+        node = self
+        for part in path.split('/'):
+            if not part:
+                continue
+            if part not in node.children:
+                node.children[part] = type(self)()
+            node = node.children[part]
+        return node
+
+    def walk(self, path=''):
+        """Yield `(path, node)` pairs for this subtree in pre-order.
+
+        Args:
+            path: Path prefix for `self` (defaults to `''` for the root node,
+                producing paths like `''`, `'/soc'`, `'/soc/i2c@4000'`).
+
+        Yields:
+            Tuple of `(path, node)` for `self` followed in pre-order by each
+            descendant `DeviceTree`.
+        """
+        stack = [(path, self)]
+        while stack:
+            cur_path, node = stack.pop()
+            yield cur_path, node
+            prefix = cur_path.rstrip('/')
+            for name, child in reversed(node.children.items()):
+                stack.append((f'{prefix}/{name}', child))
diff --git a/pylibfdt/meson.build b/pylibfdt/meson.build
index b13d8021497f..ccf6c1bf78a6 100644
--- a/pylibfdt/meson.build
+++ b/pylibfdt/meson.build
@@ -19,3 +19,5 @@ pylibfdt = py.extension_module(
   dependencies: [libfdt_dep, py.dependency()],
   install: true,
 )
+
+py.install_sources('libpydt.py', pure: false)
diff --git a/tests/libpydt_tests.py b/tests/libpydt_tests.py
new file mode 100644
index 000000000000..0f3d8d68945a
--- /dev/null
+++ b/tests/libpydt_tests.py
@@ -0,0 +1,106 @@
+# SPDX-License-Identifier: (GPL-2.0-or-later OR BSD-2-Clause)
+# libpydt - Tests for in-memory DeviceTree representation in Python
+#
+
+import sys
+import unittest
+
+sys.path.insert(0, '../pylibfdt')
+import libfdt
+from libfdt import FdtSw, Property
+import libpydt
+
+
+class DeviceTreeTests(unittest.TestCase):
+    """Test class for libpydt.DeviceTree"""
+
+    def setUp(self):
+        with open('test_tree1.dtb', mode='rb') as f:
+            self.fdt = libfdt.FdtRo(f.read())
+
+    def testRoundTrip(self):
+        """Test unflattening and flattening a tree via DeviceTree"""
+        tree = libpydt.DeviceTree.unflatten(self.fdt)
+        self.assertIsInstance(tree.props['compatible'], Property)
+        rsvmap = self.fdt.get_mem_rsv_list()
+        cpuid = self.fdt.boot_cpuid_phys()
+        fdt2 = tree.flatten(rsvmap, cpuid)
+        self.assertIsInstance(fdt2, libfdt.Fdt)
+        self.assertEqual(rsvmap, fdt2.get_mem_rsv_list())
+        self.assertEqual(cpuid, fdt2.boot_cpuid_phys())
+
+        tree2 = libpydt.DeviceTree.unflatten(fdt2)
+        nodes1 = {
+            path: (n.props, set(n.children.keys()))
+            for path, n in tree.walk()
+        }
+        nodes2 = {
+            path: (n.props, set(n.children.keys()))
+            for path, n in tree2.walk()
+        }
+        self.assertEqual(nodes1, nodes2)
+
+    def testUnflattenSubtree(self):
+        """Test unflattening a non-root subtree offset"""
+        suboff = self.fdt.path_offset('/subnode@1')
+        sub = libpydt.DeviceTree.unflatten(self.fdt, suboff)
+        self.assertEqual('subnode1', sub.props['compatible'].as_str())
+        self.assertEqual({'subsubnode', 'ss1'}, set(sub.children.keys()))
+
+    def testDuplicates(self):
+        """Test that DeviceTree.unflatten() rejects duplicate names"""
+        sw_prop = FdtSw()
+        sw_prop.finish_reservemap()
+        with sw_prop.add_node(''):
+            sw_prop.property_u32('dup', 1)
+            sw_prop.property_u32('dup', 2)
+        with self.assertRaises(ValueError):
+            libpydt.DeviceTree.unflatten(sw_prop.as_fdt())
+
+        sw_node = FdtSw()
+        sw_node.finish_reservemap()
+        with sw_node.add_node(''):
+            with sw_node.add_node('dup'):
+                pass
+            with sw_node.add_node('dup'):
+                pass
+        with self.assertRaises(ValueError):
+            libpydt.DeviceTree.unflatten(sw_node.as_fdt())
+
+    def testCorruptTree(self):
+        """Test that DeviceTree.unflatten() raises FdtException on corrupt trees"""
+        with open('truncated_property.dtb', mode='rb') as f:
+            fdt_trunc = libfdt.FdtRo(f.read())
+        with self.assertRaises(libfdt.FdtException):
+            libpydt.DeviceTree.unflatten(fdt_trunc)
+
+        # Truncate size_dt_struct so the tree ends mid-subnode
+        corrupt = self.fdt.as_bytearray()
+        fdt_corrupt = libfdt.FdtRo(corrupt)
+        fdt_corrupt._fdt[36:40] = (32).to_bytes(4, 'big')
+        with self.assertRaises(libfdt.FdtException):
+            libpydt.DeviceTree.unflatten(fdt_corrupt)
+
+    def testNavigationAndProps(self):
+        """Test DeviceTree navigation and property setting"""
+        root = libpydt.DeviceTree()
+        self.assertIs(root, root.get_node(''))
+        self.assertIs(root, root.get_node('/'))
+        self.assertIsNone(root.get_node('/soc/i2c@4000'))
+
+        i2c = root.create_path('/soc/i2c@4000')
+        self.assertIs(i2c, root.get_node('/soc/i2c@4000'))
+        self.assertIs(i2c, root.get_node('soc/i2c@4000'))
+        self.assertEqual({'', '/soc', '/soc/i2c@4000'},
+                         {path for path, _ in root.walk()})
+        self.assertEqual({'/', '/soc', '/soc/i2c@4000'},
+                         {path for path, _ in root.walk('/')})
+
+        i2c.set_prop(Property.from_str('status', 'okay'))
+        self.assertEqual('okay', i2c.props['status'].as_str())
+        i2c.set_prop(Property.from_uint32('#address-cells', 1))
+        self.assertEqual(1, i2c.props['#address-cells'].as_uint32())
+
+
+if __name__ == '__main__':
+    unittest.main()
diff --git a/tests/meson.build b/tests/meson.build
index c25500606059..e37567864e04 100644
--- a/tests/meson.build
+++ b/tests/meson.build
@@ -119,7 +119,7 @@ if not pylibfdt_enabled
 else
   env += [
     'PYTHON=' + py.full_path(),
-    'PYTHONPATH=' + meson.project_build_root() / 'pylibfdt',
+    'PYTHONPATH=' + meson.project_build_root() / 'pylibfdt' + ':' + meson.project_source_root() / 'pylibfdt',
     'NO_PYTHON=0',
   ]
 endif
diff --git a/tests/run_tests.sh b/tests/run_tests.sh
index f750faa1f60a..3cacb68438df 100755
--- a/tests/run_tests.sh
+++ b/tests/run_tests.sh
@@ -1149,17 +1149,16 @@ fdtoverlay_tests() {
     run_wrap_test test "$bd" = "$pd"
 }
 
-pylibfdt_tests () {
-    run_dtc_test -I dts -O dtb -o test_props.dtb "$SRCDIR/test_props.dts"
+run_python_tests () {
     TMP=/tmp/tests.stderr.$$
-    $PYTHON "$SRCDIR/pylibfdt_tests.py" -v 2> $TMP
+    $PYTHON "$1" -v 2> $TMP
 
     # Use the 'ok' message meaning the test passed, 'ERROR' meaning it failed
     # and the summary line for total tests (e.g. 'Ran 17 tests in 0.002s').
     # We could add pass + fail to get total tests, but this provides a useful
     # sanity check.
     pass_count=$(grep "ok$" $TMP | wc -l)
-    fail_count=$(grep "^ERROR: " $TMP | wc -l)
+    fail_count=$(grep "^ERROR: \|^FAIL: " $TMP | wc -l)
     total_tests=$(sed -n 's/^Ran \([0-9]*\) tests.*$/\1/p' $TMP)
     cat $TMP
     rm $TMP
@@ -1170,6 +1169,12 @@ pylibfdt_tests () {
     tot_tests=$((tot_tests + $total_tests))
 }
 
+pylibfdt_tests () {
+    run_dtc_test -I dts -O dtb -o test_props.dtb "$SRCDIR/test_props.dts"
+    run_python_tests "$SRCDIR/pylibfdt_tests.py"
+    run_python_tests "$SRCDIR/libpydt_tests.py"
+}
+
 while getopts "vt:me" ARG ; do
     case $ARG in
 	"v")
-- 
2.56.0.679.gc527c65306-goog


  parent reply	other threads:[~2026-11-16 20:53 UTC|newest]

Thread overview: 15+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2026-11-16 20:52 [PATCH v4 00/14] fdtfactor: Introduce fdtfactor to auto-factor overlays Douglas Anderson
2026-11-16 20:52 ` [PATCH v4 01/14] README: Add overview blurbs for dtc and ancillary tools Douglas Anderson
2026-11-16 20:52 ` [PATCH v4 02/14] pylibfdt: Make Property a subclass of bytes instead of bytearray Douglas Anderson
2026-11-16 20:53 ` [PATCH v4 03/14] pylibfdt: Trim Fdt bytearray to totalsize() in FdtSw.as_fdt() Douglas Anderson
2026-11-16 20:53 ` [PATCH v4 04/14] pylibfdt: Add Property.from_*() creation methods Douglas Anderson
2026-11-16 20:53 ` [PATCH v4 05/14] pylibfdt: Unpack Property.as_list() in a single struct.unpack() call Douglas Anderson
2026-11-16 20:53 ` [PATCH v4 06/14] pylibfdt: Speed up FdtRo.properties() with a C helper Douglas Anderson
2026-11-16 20:53 ` Douglas Anderson [this message]
2026-11-16 20:53 ` [PATCH v4 08/14] libfdt: Speed up fdt_find_string_len_() with memchr() Douglas Anderson
2026-11-16 20:53 ` [PATCH v4 09/14] libfdt: overlay: Update base /__local_fixups__ on apply Douglas Anderson
2026-11-16 20:53 ` [PATCH v4 10/14] fdtfactor: Add tool to split DTBs into a base DTB and overlays Douglas Anderson
2026-11-16 20:53 ` [PATCH v4 11/14] fdtfactor: Add -S/--strip-local-fixups option Douglas Anderson
2026-11-16 20:53 ` [PATCH v4 12/14] fdtfactor: Support compressed DTB inputs and outputs Douglas Anderson
2026-11-16 20:53 ` [PATCH v4 13/14] fdtfactor: Add compiled FIT factoring support Douglas Anderson
2026-11-16 20:53 ` [PATCH v4 14/14] fdtfactor: Parallelize blob compression and decompression Douglas Anderson

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20261116205320.1621386-8-dianders@chromium.org \
    --to=dianders@chromium.org \
    --cc=Devicetree-compiler@vger.kernel.org \
    --cc=Devicetree@vger.kernel.org \
    --cc=andre.draszik@linaro.org \
    --cc=briannorris@chromium.org \
    --cc=conor+dt@kernel.org \
    --cc=david@gibson.dropbear.id.au \
    --cc=jwerner@chromium.org \
    --cc=konradybcio@kernel.org \
    --cc=krzk+dt@kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=peter.griffin@linaro.org \
    --cc=robh@kernel.org \
    --cc=saravanak@kernel.org \
    --cc=sjg@chromium.org \
    --cc=tudor.ambarus@linaro.org \
    --cc=wenst@chromium.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox

all inboxes | Powered by JetHome®