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

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 <david@gibson.dropbear.id.au>
---
 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

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 <david@gibson.dropbear.id.au>


With few comments,


Reviewed-by: Alexey Kardashevskiy <aik@ozlabs.ru>




> ---
>   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.


> +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/ ?


> +                                     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).


> +    })
> +#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?


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

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 <david@gibson.dropbear.id.au>
> 
> 
> With few comments,
> 
> 
> Reviewed-by: Alexey Kardashevskiy <aik@ozlabs.ru>
> 
> 
> 
> 
> >---
> >  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;
> >+}
> >
> 
>

On 20.04.2016 04:33, David Gibson wrote:
...
> 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.

Good idea, the FDT format itself is really not very well suited for
dynamic manipulations...

...
> 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.

What does QDT stand for? Maybe add that in the description here.

> + * 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)) {

Too many parenthesis for my taste ;-)

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

In case somebody ever tries to compile this with a C++ compiler ... it's
maybe better avoid using "new" as name for a variable.

> +/*
> + * 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)

Underscore at the end looks somewhat strange ... can't you simply drop that?

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

Can you replace the above four lines with qdt_new_property ?

> +    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);

Do we still need "linux,phandle" nowadays? ... maybe that would be a
good point in time now to slowly get rid of this?
At least the ARM code seems to work already without that, and pseries
should also be fine without it (since SLOF replaces "phandle" and
"linux,phandle" anyway).

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

So the caller has already to know here, how big the flattened device
tree will be at max? That's a somewhat cumbersome interface. Would it be
feasible to determine the size automatically somehow?

Or maybe at least make the caller provide the buffer to the fdt array...
then the caller provides both, buffer pointer and size. That would be
somewhat more consistent interface, I think.

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

Maybe add a sanity check a la "fdt_totalsize(fdt) < bufsize" here and
abort on buffer overflow?
(or move such a check even into qdt_flatten_node ?)

> +    return fdt;
> +
> +fail:
> +    g_free(fdt);
> +    return NULL;
> +}

 Thomas

On Tue, Apr 26, 2016 at 01:00:06PM +0200, Thomas Huth wrote:
> On 20.04.2016 04:33, David Gibson wrote:
> ...
> > 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.
> 
> Good idea, the FDT format itself is really not very well suited for
> dynamic manipulations...
> 
> ...
> > 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.
> 
> What does QDT stand for? Maybe add that in the description here.

"QEMU Device Tree" I guess?  Really I was just looking for something
similar but not the same as fdt, and short.

> > + * 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)) {
> 
> Too many parenthesis for my taste ;-)
> 
> > +            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;
> > +}
> 
> In case somebody ever tries to compile this with a C++ compiler ... it's
> maybe better avoid using "new" as name for a variable.

Good point, will change.

> > +/*
> > + * 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)
> 
> Underscore at the end looks somewhat strange ... can't you simply drop that?

Well.. the idea was that the _ versions are the "internal" ones,
whereas external users will generally use the non-underscore version
(in this case the only difference is that the external one returns a
const pointer).

I don't particularly like that convention, so feel free to suggest
something better.

> > +{
> > +    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);
> 
> Can you replace the above four lines with qdt_new_property ?

Actually, qdt_new_property() is a leftover from an approach I ended up
not liking, I should just remove it.

> > +    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);
> 
> Do we still need "linux,phandle" nowadays? ... maybe that would be a
> good point in time now to slowly get rid of this?
> At least the ARM code seems to work already without that, and pseries
> should also be fine without it (since SLOF replaces "phandle" and
> "linux,phandle" anyway).

Erm.. maybe.  IIRC the addition of support for the new property to the
early boot kernel code on Power was surprisingly late, so it seems
safer to include it, but, we can check.

> > +    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;
> 
> So the caller has already to know here, how big the flattened device
> tree will be at max? That's a somewhat cumbersome interface. Would it be
> feasible to determine the size automatically somehow?

Yes, I was planningto add an autosizing flatten interface, but I
wanted to get the basic concept reviewed before I bothered
implementing that.  It shouldn't be that hard - just realloc()
whenever one of the FDT calls returns -FDT_ERR_NOSPACE.

> Or maybe at least make the caller provide the buffer to the fdt array...
> then the caller provides both, buffer pointer and size. That would be
> somewhat more consistent interface, I think.

Well, I was thinking that we could have the autosizing interface in
the same function by redefining that as a max size, and having 0 or -1
mean no maximum.

> > +    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;
> > +    }
> 
> Maybe add a sanity check a la "fdt_totalsize(fdt) < bufsize" here and
> abort on buffer overflow?

There's really no point - the fdt functions can't succeed if they
overflow the buffer space, so we will have already tripped an error.
The only libfdt functions which will *ever* change fdt_totalsize() are
fdt_create(), fdt_open_int(), fdt_finish() and fdt_pack() and the last
two can only ever reduce it, never increase it.

> (or move such a check even into qdt_flatten_node ?)
> 
> > +    return fdt;
> > +
> > +fail:
> > +    g_free(fdt);
> > +    return NULL;
> > +}
> 
>  Thomas
>

David Gibson <david@gibson.dropbear.id.au> writes:

> On Tue, Apr 26, 2016 at 01:00:06PM +0200, Thomas Huth wrote:
>> On 20.04.2016 04:33, David Gibson wrote:
>> ...
>> > 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.
>> 
>> Good idea, the FDT format itself is really not very well suited for
>> dynamic manipulations...
>> 
>> ...
>> > 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.
>> 
>> What does QDT stand for? Maybe add that in the description here.
>
> "QEMU Device Tree" I guess?  Really I was just looking for something
> similar but not the same as fdt, and short.
>
>> > + * 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)) {
>> 
>> Too many parenthesis for my taste ;-)

Mine too.

>> > +            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;
>> > +}
>> 
>> In case somebody ever tries to compile this with a C++ compiler ... it's
>> maybe better avoid using "new" as name for a variable.
>
> Good point, will change.

My answer to "what if somebody tries to compile this code with a
compiler for a different language" is "hope it won't compile then, for
the innocents' sake".

>> > +/*
>> > + * 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)
>> 
>> Underscore at the end looks somewhat strange ... can't you simply drop that?
>
> Well.. the idea was that the _ versions are the "internal" ones,
> whereas external users will generally use the non-underscore version

I've seen that convention used before.  It's fine with me.

> (in this case the only difference is that the external one returns a
> const pointer).
>
> I don't particularly like that convention, so feel free to suggest
> something better.

Consider getprop_internal() if the length isn't bothersome.  It is when
the name is used all over the place.

do_getprop() would be shorter.  I don't like do_verb names myself.

[...]

On 27.04.2016 08:43, Markus Armbruster wrote:
> David Gibson <david@gibson.dropbear.id.au> writes:
> 
>> On Tue, Apr 26, 2016 at 01:00:06PM +0200, Thomas Huth wrote:
>>> On 20.04.2016 04:33, David Gibson wrote:
[...]
>>>> +/*
>>>> + * 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)
>>>
>>> Underscore at the end looks somewhat strange ... can't you simply drop that?
>>
>> Well.. the idea was that the _ versions are the "internal" ones,
>> whereas external users will generally use the non-underscore version
> 
> I've seen that convention used before.  It's fine with me.

Can't remember to have seen that convention before ... I know that some
people use the underscore at the beginning to mark an internal function,
but at the end?
So if you really want to use the underscore, what about putting it at
the beginning instead?

>> (in this case the only difference is that the external one returns a
>> const pointer).
>>
>> I don't particularly like that convention, so feel free to suggest
>> something better.
> 
> Consider getprop_internal() if the length isn't bothersome.  It is when
> the name is used all over the place.
> 
> do_getprop() would be shorter.  I don't like do_verb names myself.

Both ideas also sound fine to me.

 Thomas

Thomas Huth <thuth@redhat.com> writes:

> On 27.04.2016 08:43, Markus Armbruster wrote:
>> David Gibson <david@gibson.dropbear.id.au> writes:
>> 
>>> On Tue, Apr 26, 2016 at 01:00:06PM +0200, Thomas Huth wrote:
>>>> On 20.04.2016 04:33, David Gibson wrote:
> [...]
>>>>> +/*
>>>>> + * 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)
>>>>
>>>> Underscore at the end looks somewhat strange ... can't you simply drop that?
>>>
>>> Well.. the idea was that the _ versions are the "internal" ones,
>>> whereas external users will generally use the non-underscore version
>> 
>> I've seen that convention used before.  It's fine with me.
>
> Can't remember to have seen that convention before ... I know that some
> people use the underscore at the beginning to mark an internal function,
> but at the end?
> So if you really want to use the underscore, what about putting it at
> the beginning instead?

C99 7.1.3  Reserved identifiers:

         -- All identifiers  that  begin  with  an  underscore  are
            always  reserved for use as identifiers with file scope
            in both the ordinary and tag name spaces.

[...]

On 27.04.2016 09:28, Markus Armbruster wrote:
> Thomas Huth <thuth@redhat.com> writes:
> 
>> On 27.04.2016 08:43, Markus Armbruster wrote:
>>> David Gibson <david@gibson.dropbear.id.au> writes:
>>>
>>>> On Tue, Apr 26, 2016 at 01:00:06PM +0200, Thomas Huth wrote:
>>>>> On 20.04.2016 04:33, David Gibson wrote:
>> [...]
>>>>>> +/*
>>>>>> + * 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)
>>>>>
>>>>> Underscore at the end looks somewhat strange ... can't you simply drop that?
>>>>
>>>> Well.. the idea was that the _ versions are the "internal" ones,
>>>> whereas external users will generally use the non-underscore version
>>>
>>> I've seen that convention used before.  It's fine with me.
>>
>> Can't remember to have seen that convention before ... I know that some
>> people use the underscore at the beginning to mark an internal function,
>> but at the end?
>> So if you really want to use the underscore, what about putting it at
>> the beginning instead?
> 
> C99 7.1.3  Reserved identifiers:
> 
>          -- All identifiers  that  begin  with  an  underscore  are
>             always  reserved for use as identifiers with file scope
>             in both the ordinary and tag name spaces.

Oh, I always thought that underscore + lowercase letter would still be
OK for local variables and functions, since for example
http://www.gnu.org/software/libc/manual/html_node/Reserved-Names.html says:

"In addition to the names documented in this manual, reserved names
include all external identifiers (global functions and variables) that
begin with an underscore (‘_’) and all identifiers regardless of use
that begin with either two underscores or an underscore followed by a
capital letter are reserved names"

... that sounds like the underscore rule only applies to global
functions and variables (and to those where the underscore is followed
by a capital letter or another underscore).

But if I've got your quote right, a leading underscore _always_
indicates a reserved name for functions and variables, no matter whether
they are local or global... Well, you learn something new
every day :-)

 Thomas

Thomas Huth <thuth@redhat.com> writes:

> On 27.04.2016 09:28, Markus Armbruster wrote:
>> Thomas Huth <thuth@redhat.com> writes:
>> 
>>> On 27.04.2016 08:43, Markus Armbruster wrote:
>>>> David Gibson <david@gibson.dropbear.id.au> writes:
>>>>
>>>>> On Tue, Apr 26, 2016 at 01:00:06PM +0200, Thomas Huth wrote:
>>>>>> On 20.04.2016 04:33, David Gibson wrote:
>>> [...]
>>>>>>> +/*
>>>>>>> + * 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)
>>>>>>
>>>>>> Underscore at the end looks somewhat strange ... can't you simply drop that?
>>>>>
>>>>> Well.. the idea was that the _ versions are the "internal" ones,
>>>>> whereas external users will generally use the non-underscore version
>>>>
>>>> I've seen that convention used before.  It's fine with me.
>>>
>>> Can't remember to have seen that convention before ... I know that some
>>> people use the underscore at the beginning to mark an internal function,
>>> but at the end?
>>> So if you really want to use the underscore, what about putting it at
>>> the beginning instead?
>> 
>> C99 7.1.3  Reserved identifiers:

Additional context:

            -- All identifiers  that  begin  with  an  underscore  and
               either  an  uppercase  letter or another underscore are
               always reserved for any use.

>>          -- All identifiers  that  begin  with  an  underscore  are
>>             always  reserved for use as identifiers with file scope
>>             in both the ordinary and tag name spaces.
>
> Oh, I always thought that underscore + lowercase letter would still be
> OK for local variables and functions, since for example
> http://www.gnu.org/software/libc/manual/html_node/Reserved-Names.html says:
>
> "In addition to the names documented in this manual, reserved names
> include all external identifiers (global functions and variables) that
> begin with an underscore (‘_’) and all identifiers regardless of use
> that begin with either two underscores or an underscore followed by a
> capital letter are reserved names"
>
> ... that sounds like the underscore rule only applies to global
> functions and variables (and to those where the underscore is followed
> by a capital letter or another underscore).
>
> But if I've got your quote right, a leading underscore _always_
> indicates a reserved name for functions and variables, no matter whether
> they are local or global... Well, you learn something new
> every day :-)

Almost.  Compare the two clauses carefully: the first one reserves "for
any use", the second one "for use as identifiers with file scope in both
the ordinary and tag name spaces."  The difference is the quantifiers
"file scope" and "ordinary and tag name spaces".

The scopes are function, file, block, function prototype (the parameter
list).  See 6.2.1 Scopes of identifiers.

The name spaces are label, struct/union/enum tag, each struct or union
for its members, and ordinary.  See 6.2.3 Name spaces of identifiers.

Thus, the second clause doesn't apply to labels, struct/union members,
and local variables including arguments.

However, if you need to quote three sections of the standard to convince
yourself that an identifier is okay, perhaps you should pick another one
:)

On Wed, Apr 27, 2016 at 09:28:57AM +0200, Markus Armbruster wrote:
> Thomas Huth <thuth@redhat.com> writes:
> 
> > On 27.04.2016 08:43, Markus Armbruster wrote:
> >> David Gibson <david@gibson.dropbear.id.au> writes:
> >> 
> >>> On Tue, Apr 26, 2016 at 01:00:06PM +0200, Thomas Huth wrote:
> >>>> On 20.04.2016 04:33, David Gibson wrote:
> > [...]
> >>>>> +/*
> >>>>> + * 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)
> >>>>
> >>>> Underscore at the end looks somewhat strange ... can't you simply drop that?
> >>>
> >>> Well.. the idea was that the _ versions are the "internal" ones,
> >>> whereas external users will generally use the non-underscore version
> >> 
> >> I've seen that convention used before.  It's fine with me.
> >
> > Can't remember to have seen that convention before ... I know that some
> > people use the underscore at the beginning to mark an internal function,
> > but at the end?
> > So if you really want to use the underscore, what about putting it at
> > the beginning instead?
> 
> C99 7.1.3  Reserved identifiers:
> 
>          -- All identifiers  that  begin  with  an  underscore  are
>             always  reserved for use as identifiers with file scope
>             in both the ordinary and tag name spaces.

Right.  The kernel uses the _ prefix convention, but it can kind of
get away with it, because it doesn't use the standard library.  For
things in userspace, _ prefixed identifiers are reserved, hence using
the _ suffix instead.