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

[Alexey Kardashevskiy <aik@ozlabs.ru>]

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


-- 
Alexey