From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:50418) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1atSsS-0003hI-LF for qemu-devel@nongnu.org; Fri, 22 Apr 2016 00:39:38 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1atSsQ-0007IV-HM for qemu-devel@nongnu.org; Fri, 22 Apr 2016 00:39:36 -0400 Date: Fri, 22 Apr 2016 14:15:12 +1000 From: David Gibson Message-ID: <20160422041512.GB15176@voom.fritz.box> References: <1461119601-4936-1-git-send-email-david@gibson.dropbear.id.au> <1461119601-4936-2-git-send-email-david@gibson.dropbear.id.au> <57186CAC.2080100@ozlabs.ru> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="b5gNqxB1S1yM7hjW" Content-Disposition: inline In-Reply-To: <57186CAC.2080100@ozlabs.ru> Subject: Re: [Qemu-devel] [RFC for-2.7 01/11] qdt: IEEE1275-style device tree utility code List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Alexey Kardashevskiy Cc: agraf@suse.de, crosthwaite.peter@gmail.com, qemu-ppc@nongnu.org, qemu-devel@nongnu.org --b5gNqxB1S1yM7hjW Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable 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 >=20 >=20 > With few comments, >=20 >=20 > Reviewed-by: Alexey Kardashevskiy >=20 >=20 >=20 >=20 > >--- > > 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 > >+#include > >+#include > >+#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); >=20 >=20 > 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. >=20 >=20 > >+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, gsi= ze 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, >=20 >=20 > 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[] =3D { __VA_ARGS__ }; = \ > >+ qdt_setprop((node), (name), vals, sizeof(vals)); = \ > >+ }) > >+#define qdt_setprop_cells(node, name, ...) = \ > >+ ({ = \ > >+ uint32_t vals[] =3D { __VA_ARGS__ }; = \ > >+ qdt_setprop_cells_((node), (name), = \ > >+ vals, sizeof(vals) / sizeof(vals[0])); = \ >=20 >=20 > 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[] =3D { __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 *old= prop) >=20 > 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 +=3D buffer.o > > util-obj-y +=3D timed-average.o > > util-obj-y +=3D base64.o > > util-obj-y +=3D log.o > >+util-obj-y +=3D 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 > >+#include > >+ > >+#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 =3D g_new0(QDTNode, 1); > >+ > >+ g_assert(!strchr(name, '/')); > >+ > >+ node->name =3D 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) =3D=3D namelen) > >+ && (memcmp(child->name, name, namelen) =3D=3D 0)) { > >+ return child; > >+ } > >+ } > >+ > >+ return NULL; > >+} > >+ > >+QDTNode *qdt_get_node_relative(QDTNode *node, const gchar *path) > >+{ > >+ const gchar *slash; > >+ gsize seglen; > >+ > >+ do { > >+ slash =3D strchr(path, '/'); > >+ seglen =3D slash ? slash - path : strlen(path); > >+ > >+ node =3D get_subnode(node, path, seglen); > >+ path +=3D seglen + 1; > >+ } while (node && slash); > >+ > >+ return node; > >+} > >+ > >+QDTNode *qdt_get_node(QDTNode *root, const gchar *path) > >+{ > >+ g_assert(!root->parent); > >+ g_assert(path[0] =3D=3D '/'); > >+ return qdt_get_node_relative(root, path + 1); > >+} > >+ > >+QDTNode *qdt_add_subnode(QDTNode *parent, const gchar *name) > >+{ > >+ QDTNode *new =3D qdt_new_node(name); > >+ > >+ new->parent =3D parent; > >+ QTAILQ_INSERT_TAIL(&parent->children, new, sibling); > >+ return new; > >+} > >+ > >+/* > >+ * Property functions > >+ */ > >+ > >+QDTProperty *qdt_new_property(const gchar *name, gconstpointer val, gsi= ze len) > >+{ > >+ QDTProperty *prop =3D g_malloc0(sizeof(*prop) + len); > >+ > >+ prop->name =3D g_strdup(name); > >+ prop->len =3D 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) =3D=3D 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 =3D 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 =3D g_malloc0(sizeof(*prop) + len); > >+ prop->name =3D g_strdup(name); > >+ prop->len =3D 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 =3D 0; i < len; i++) { > >+ swapval[i] =3D 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 =3D 0; i < len; i++) { > >+ swapval[i] =3D 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 !=3D 0) && (phandle !=3D (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 =3D NULL; > >+ int ret; > >+ > >+ ret =3D 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 =3D fdt_property(fdt, prop->name, prop->val, prop->len); > >+ if (ret < 0) { > >+ error_setg(errp, "Error flattening device tree: fdt_propert= y(): %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 =3D 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 =3D g_malloc0(bufsize); > >+ Error *local_err =3D NULL; > >+ int ret; > >+ > >+ assert(!root->parent); /* Should be a root node */ > >+ > >+ ret =3D fdt_create(fdt, bufsize); > >+ if (ret < 0) { > >+ error_setg(errp, "Error flattening device tree: fdt_create(): %= s", > >+ fdt_strerror(ret)); > >+ goto fail; > >+ } > >+ > >+ ret =3D 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 =3D 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; > >+} > > >=20 >=20 --=20 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 --b5gNqxB1S1yM7hjW Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1 iQIcBAEBAgAGBQJXGaVQAAoJEGw4ysog2bOSVZgP/2v1xglJ+d8MqoYU3X4m6+Oh rE7sJordx0H4bBNhhcp0mlKUjkr5eW1Ki9ulmi1pO+EjcGzBqIVN9Ma6T5b0IFJV 6W8CKUeDWs5CgHKSwpNHDqYLup+30SJN92tiLtcTYWS18CNGpDHFIPs7aBx7rbzY 1onV0BfT7gJ0aLGpXvJTjR9ylf1u/axHABCyQNPDlN0sYoruPDIvIukCP/fl2J9a 8tiUYB4c1oWQFR+coq0NXVJ+iKOkdiLEVyyIhuq1Jt3dAnRps4Ez1JIuuuC1wvcT f/dgYmi6sq/uojMpGpHeDQTBH7JOZ1aaqIivrUjvXYFJV5gMAEJWGwtQ/t9/FknV gjAfSj69qbsRtra958fNRx54uSDLSZytQ9Ln06YxBHmvjsTNQMCIEKx/2UUvvWoP pF7XWkP+KtFE+ghnAL/Yk9kSe2nsn2lh1Lv3RjJuKqYa+ApRonUYsg8fWHfjbR7Q ORefUWcq8qrcutcaM43cmRaURsztAmSO+8OsoKCHnGHsHQIL4mIMT8AxVKwiF9tO 8RL/KyVd5pQt6RCk1ZCgyWQ8IO/NWXQl4AGEjVsK9RJ0XAtAg+ISZJ8apgbKrE0b +QrmqtS0MQTGyofH7/DLsVzmUW1teRtle1PraaJ8wn0NWlJyynmDNIEEXuHQtutQ UzT5VCLK5sRfqBzOkKEs =qVwd -----END PGP SIGNATURE----- --b5gNqxB1S1yM7hjW--