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

[David Gibson]

On Thu, Apr 21, 2016 at 04:01:16PM +1000, Alexey Kardashevskiy wrote:
> On 04/20/2016 12:33 PM, David Gibson wrote:
> >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>
> 
> 
> With few comments,
> 
> 
> Reviewed-by: Alexey Kardashevskiy <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);
> 
> 
> Do you really need both qdt_get_node_relative and qdt_get_node? It would
> make sense (a little) if qdt_get_node() accepted path without leading "/"
> but it does not.

Hm, maybe not.  I'll see if I can combine those.

> 
> 
> >+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,
> 
> 
> s/char/gchar/ ?

Will change, thanks.

> >+                                     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]));       \
> 
> 
> Nit: there is ARRAY_SIZE(x).

Oh, yes.  For some reason I thought I'd looked and not seen it there,
but I was obviously confused.  Will change

> >+    })
> >+#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)
> 
> Out of curiosity - when could I possibly want to use this?

Uh.. I thought I had a use case in the papr stuff I was already using,
but then I couldn't find it.  I'll think about removing this.

> >+{
> >+    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;
> >+}
> >
> 
> 

-- 
David Gibson                    | I'll have my music baroque, and my code
david AT gibson.dropbear.id.au  | minimalist, thank you.  NOT _the_ _other_
                                | _way_ _around_!
http://www.ozlabs.org/~dgibson

signature.asc
Description: PGP signature