[Qemu-devel] [RFC for-2.7 01/11] qdt: IEEE1275-style device tree utility code

[David Gibson]

A number of guests supported by qemu use IEEE12750 (Open Firmware)
style device trees for hardware discovery.  In some cases (mac99,
pseries) they get this device tree via calls to an in-guest Open
Firmware implementation, in others (many ppc and arm embedded
machines) they consume the flattened ("fdt" or "dtb") format described
in ePAPR amongst other places.  In some cases this device tree is
constructed in guest firmware, in others by qemu and in some cases
it's a hybrid.

The upshot is that a number of qemu machine types need to construct
and/or manipulate device trees.  Particularly with the pseries machine
type, the complexity of manipulation it needs has been gradually
increasing over time.

For now, these machine types have generally worked with the device
tree in the flattened format, using either libfdt directly or the
wrappers in device_tree.c.  However, the fdt format was designed
primarily for transferring device trees between components, not for
runtime manipulation:
    * fdt provides no persistent handles on nodes
         Nodes are referenced using offsets in the stream which can be
         altered by insertions or deletions elsewhere in the tree
    * libfdt operations can fail
         At any time the fdt lives in a limited size buffer, and
         operations can fail if it fills.  This can be handled by
         resizing the buffer, but that means logic to catch this case
         on essentially every fdt operation, which is fiddly (in
         practice we usually just allocate a buffer with plenty of
         space and treat failures as fatal errors).
    * fdt manipulation is slow
         This probably isn't a problem in practice, but because it
         uses memmove() liberally, even trivial operations on an fdt
         are usually O(n) in the size of the whole tree.  This can
         often make the obvious way of constructing the tree O(n^2) or
         worse.  This could cause noticeable slow downs if someone
         builds a guest with hundreds or thousands of devices, which
         is an unusual but not unreasonable use case.

This patch introduces a new utility library "qdt" for runtime
manipulation of device trees.  The intention is that machine type code
can use these routines to construct the device tree conveniently,
using a pointer-based representation doesn't have the limitations
above.  They can then use qdt_flatten() to convert the completed tree
to fdt format as a single O(n) operation to pass to the guest.

Signed-off-by: David Gibson <address@hidden>
---
 include/qemu/qdt.h | 102 +++++++++++++++++++++
 util/Makefile.objs |   1 +
 util/qdt.c         | 262 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 365 insertions(+)
 create mode 100644 include/qemu/qdt.h
 create mode 100644 util/qdt.c

diff --git a/include/qemu/qdt.h b/include/qemu/qdt.h
new file mode 100644
index 0000000..bff7143
--- /dev/null
+++ b/include/qemu/qdt.h
@@ -0,0 +1,102 @@
+/*
+ * Functions for manipulating IEEE1275 (Open Firmware) style device
+ * trees.
+ *
+ * Copyright David Gibson, Red Hat Inc. 2016
+ *
+ * This work is licensed unter the GNU GPL version 2 or (at your
+ * option) any later version.
+ */
+#ifndef QEMU_QDT_H__
+#define QEMU_QDT_H__
+
+#include <string.h>
+#include <stdint.h>
+#include <glib.h>
+#include "qemu/queue.h"
+
+typedef struct QDTProperty QDTProperty;
+typedef struct QDTNode QDTNode;
+
+struct QDTProperty {
+    gchar *name;
+    QTAILQ_ENTRY(QDTProperty) list;
+    gsize len;
+    uint8_t val[];
+};
+
+struct QDTNode {
+    gchar *name;
+    QDTNode *parent;
+    QTAILQ_HEAD(, QDTProperty) properties;
+    QTAILQ_HEAD(, QDTNode) children;
+    QTAILQ_ENTRY(QDTNode) sibling;
+};
+
+/*
+ * Node functions
+ */
+
+QDTNode *qdt_new_node(const gchar *name);
+QDTNode *qdt_get_node_relative(QDTNode *node, const gchar *path);
+QDTNode *qdt_get_node(QDTNode *root, const gchar *path);
+QDTNode *qdt_add_subnode(QDTNode *parent, const gchar *name);
+
+static inline QDTNode *qdt_new_tree(void)
+{
+    return qdt_new_node("");
+}
+
+/*
+ * Property functions
+ */
+
+QDTProperty *qdt_new_property(const gchar *name, gconstpointer val, gsize len);
+const QDTProperty *qdt_getprop(const QDTNode *node, const gchar *name);
+void qdt_delprop(QDTNode *node, const gchar *name);
+const QDTProperty *qdt_setprop(QDTNode *node, const gchar *name,
+                               gconstpointer val, gsize len);
+const QDTProperty *qdt_setprop_cells_(QDTNode *node, const gchar *name,
+                                      const uint32_t *val, gsize len);
+const QDTProperty *qdt_setprop_u64s_(QDTNode *node, const char *name,
+                                     const uint64_t *val, gsize len);
+const QDTProperty *qdt_setprop_string(QDTNode *node, const gchar *name,
+                                      const gchar *val);
+void qdt_set_phandle(QDTNode *node, uint32_t phandle);
+
+#define qdt_setprop_bytes(node, name, ...)                              \
+    ({                                                                  \
+        uint8_t vals[] = { __VA_ARGS__ };                               \
+        qdt_setprop((node), (name), vals, sizeof(vals));                \
+    })
+#define qdt_setprop_cells(node, name, ...)                              \
+    ({                                                                  \
+        uint32_t vals[] = { __VA_ARGS__ };                              \
+        qdt_setprop_cells_((node), (name),                              \
+                           vals, sizeof(vals) / sizeof(vals[0]));       \
+    })
+#define qdt_setprop_u64s(node, name, ...)                               \
+    ({                                                                  \
+        uint64_t vals[] = { __VA_ARGS__ };                              \
+        qdt_setprop_u64s_((node), (name),                               \
+                          vals, sizeof(vals) / sizeof(vals[0]));        \
+    })
+static inline const QDTProperty *qdt_setprop_empty(QDTNode *node,
+                                                   const gchar *name)
+{
+    return qdt_setprop_bytes(node, name);
+}
+static inline const QDTProperty *qdt_setprop_dup(QDTNode *node,
+                                                 const gchar *name,
+                                                 const QDTProperty *oldprop)
+{
+    return qdt_setprop(node, name, oldprop->val, oldprop->len);
+}
+
+/*
+ * Whole tree functions
+ */
+
+void *qdt_flatten(QDTNode *root, gsize bufsize, Error **errp);
+
+#endif /* QEMU_QDT_H__ */
diff --git a/util/Makefile.objs b/util/Makefile.objs
index a8a777e..f1d639f 100644
--- a/util/Makefile.objs
+++ b/util/Makefile.objs
@@ -32,3 +32,4 @@ util-obj-y += buffer.o
 util-obj-y += timed-average.o
 util-obj-y += base64.o
 util-obj-y += log.o
+util-obj-y += qdt.o
diff --git a/util/qdt.c b/util/qdt.c
new file mode 100644
index 0000000..e3a449a
--- /dev/null
+++ b/util/qdt.c
@@ -0,0 +1,262 @@
+/*
+ * Functions for manipulating IEEE1275 (Open Firmware) style device
+ * trees.
+ *
+ * Copyright David Gibson, Red Hat Inc. 2016
+ *
+ * This work is licensed unter the GNU GPL version 2 or (at your
+ * option) any later version.
+ */
+
+#include <libfdt.h>
+#include <stdbool.h>
+
+#include "qemu/osdep.h"
+#include "qapi/error.h"
+#include "qemu/qdt.h"
+#include "qemu/error-report.h"
+
+/*
+ * Node functions
+ */
+
+QDTNode *qdt_new_node(const gchar *name)
+{
+    QDTNode *node = g_new0(QDTNode, 1);
+
+    g_assert(!strchr(name, '/'));
+
+    node->name = g_strdup(name);
+    QTAILQ_INIT(&node->properties);
+    QTAILQ_INIT(&node->children);
+
+    return node;
+}
+
+static QDTNode *get_subnode(QDTNode *parent, const gchar *name, size_t namelen)
+{
+    QDTNode *child;
+
+    g_assert(!memchr(name, '/', namelen));
+
+    QTAILQ_FOREACH(child, &parent->children, sibling) {
+        if ((strlen(child->name) == namelen)
+            && (memcmp(child->name, name, namelen) == 0)) {
+            return child;
+        }
+    }
+
+    return NULL;
+}
+
+QDTNode *qdt_get_node_relative(QDTNode *node, const gchar *path)
+{
+    const gchar *slash;
+    gsize seglen;
+
+    do {
+        slash = strchr(path, '/');
+        seglen = slash ? slash - path : strlen(path);
+
+        node = get_subnode(node, path, seglen);
+        path += seglen + 1;
+    } while (node && slash);
+
+    return node;
+}
+
+QDTNode *qdt_get_node(QDTNode *root, const gchar *path)
+{
+    g_assert(!root->parent);
+    g_assert(path[0] == '/');
+    return qdt_get_node_relative(root, path + 1);
+}
+
+QDTNode *qdt_add_subnode(QDTNode *parent, const gchar *name)
+{
+    QDTNode *new = qdt_new_node(name);
+
+    new->parent = parent;
+    QTAILQ_INSERT_TAIL(&parent->children, new, sibling);
+    return new;
+}
+
+/*
+ * Property functions
+ */
+
+QDTProperty *qdt_new_property(const gchar *name, gconstpointer val, gsize len)
+{
+    QDTProperty *prop = g_malloc0(sizeof(*prop) + len);
+
+    prop->name = g_strdup(name);
+    prop->len = len;
+    memcpy(prop->val, val, len);
+    return prop;
+}
+
+static QDTProperty *getprop_(const QDTNode *node, const gchar *name)
+{
+    QDTProperty *prop;
+
+    QTAILQ_FOREACH(prop, &node->properties, list) {
+        if (strcmp(prop->name, name) == 0) {
+            return prop;
+        }
+    }
+    return NULL;
+}
+
+const QDTProperty *qdt_getprop(const QDTNode *node, const gchar *name)
+{
+    return getprop_(node, name);
+}
+
+void qdt_delprop(QDTNode *node, const gchar *name)
+{
+    QDTProperty *prop = getprop_(node, name);
+
+    if (prop) {
+        QTAILQ_REMOVE(&node->properties, prop, list);
+        g_free(prop->name);
+        g_free(prop);
+    }
+}
+
+const QDTProperty *qdt_setprop(QDTNode *node, const gchar *name,
+                               gconstpointer val, gsize len)
+{
+    QDTProperty *prop;
+
+    qdt_delprop(node, name);
+
+    prop = g_malloc0(sizeof(*prop) + len);
+    prop->name = g_strdup(name);
+    prop->len = len;
+    memcpy(prop->val, val, len);
+    QTAILQ_INSERT_TAIL(&node->properties, prop, list);
+    return prop;
+}
+
+const QDTProperty *qdt_setprop_string(QDTNode *node, const gchar *name,
+                                      const gchar *val)
+{
+    return qdt_setprop(node, name, val, strlen(val) + 1);
+}
+
+const QDTProperty *qdt_setprop_cells_(QDTNode *node, const gchar *name,
+                                      const uint32_t *val, gsize len)
+{
+    uint32_t swapval[len];
+    gsize i;
+
+    for (i = 0; i < len; i++) {
+        swapval[i] = cpu_to_fdt32(val[i]);
+    }
+    return qdt_setprop(node, name, swapval, sizeof(swapval));
+}
+
+const QDTProperty *qdt_setprop_u64s_(QDTNode *node, const char *name,
+                                     const uint64_t *val, gsize len)
+{
+    uint64_t swapval[len];
+    gsize i;
+
+    for (i = 0; i < len; i++) {
+        swapval[i] = cpu_to_fdt64(val[i]);
+    }
+    return qdt_setprop(node, name, swapval, sizeof(swapval));
+}
+
+void qdt_set_phandle(QDTNode *node, uint32_t phandle)
+{
+    g_assert((phandle != 0) && (phandle != (uint32_t)-1));
+    qdt_setprop_cells(node, "linux,phandle", phandle);
+    qdt_setprop_cells(node, "phandle", phandle);
+}
+
+/*
+ * Whole tree functions
+ */
+
+static void qdt_flatten_node(void *fdt, QDTNode *node, Error **errp)
+{
+    QDTProperty *prop;
+    QDTNode *subnode;
+    Error *local_err = NULL;
+    int ret;
+
+    ret = fdt_begin_node(fdt, node->name);
+    if (ret < 0) {
+        error_setg(errp, "Error flattening device tree: fdt_begin_node(): %s",
+                   fdt_strerror(ret));
+        return;
+    }
+
+    QTAILQ_FOREACH(prop, &node->properties, list) {
+        ret = fdt_property(fdt, prop->name, prop->val, prop->len);
+        if (ret < 0) {
+            error_setg(errp, "Error flattening device tree: fdt_property(): 
%s",
+                       fdt_strerror(ret));
+            return;
+        }
+    }
+
+    QTAILQ_FOREACH(subnode, &node->children, sibling) {
+        qdt_flatten_node(fdt, subnode, &local_err);
+        if (local_err) {
+            error_propagate(errp, local_err);
+            return;
+        }
+    }
+
+    ret = fdt_end_node(fdt);
+    if (ret < 0) {
+        error_setg(errp, "Error flattening device tree: fdt_end_node(): %s",
+                   fdt_strerror(ret));
+        return;
+    }
+}
+
+void *qdt_flatten(QDTNode *root, gsize bufsize, Error **errp)
+{
+    void *fdt = g_malloc0(bufsize);
+    Error *local_err = NULL;
+    int ret;
+
+    assert(!root->parent); /* Should be a root node */
+
+    ret = fdt_create(fdt, bufsize);
+    if (ret < 0) {
+        error_setg(errp, "Error flattening device tree: fdt_create(): %s",
+                   fdt_strerror(ret));
+        goto fail;
+    }
+
+    ret = fdt_finish_reservemap(fdt);
+    if (ret < 0) {
+        error_setg(errp,
+                   "Error flattening device tree: fdt_finish_reservemap(): %s",
+                   fdt_strerror(ret));
+        goto fail;
+    }
+
+    qdt_flatten_node(fdt, root, &local_err);
+    if (local_err) {
+        error_propagate(errp, local_err);
+        goto fail;
+    }
+
+    ret = fdt_finish(fdt);
+    if (ret < 0) {
+        error_setg(errp, "Error flattening device tree: fdt_finish(): %s",
+                   fdt_strerror(ret));
+        goto fail;
+    }
+
+    return fdt;
+
+fail:
+    g_free(fdt);
+    return NULL;
+}
-- 
2.5.5