[PATCH 0/4] switch DT creation to using of_attach_node (v2)

[PATCH 0/4] switch DT creation to using of_attach_node (v2)

[Andres Salomon]

This is attempt #2 to make OF core use of_attach_node for both promtree
and flattree building.  This reworks of_attach_node quite a bit to conform
with our expectations of how the DT should look in memory.

It's different in many ways from the original patches, so it's worth
reviewing each in their entirety.


Andres Salomon (4):
      of: rework of_attach_node, removing CONFIG_OF_DYNAMIC
      of/promtree: switch to building the DT using of_attach_node
      of/flattree: minor cleanups
      of/flattree: use of_attach_node to build tree

----
 b/drivers/of/Kconfig |    4 ----
 b/drivers/of/base.c  |   47 ++++++++++++++++++++++++++++++++---------------
 b/drivers/of/fdt.c   |    6 ++++--
 b/drivers/of/pdt.c   |   30 ++++++------------------------
 b/include/linux/of.h |    5 ++---
 drivers/of/fdt.c     |   35 ++++++++++++++---------------------
 include/linux/of.h   |    1 -
 7 files changed, 58 insertions(+), 70 deletions(-)

[PATCH 1/4] of: rework of_attach_node, removing CONFIG_OF_DYNAMIC

[Andres Salomon]

Remove the OF_DYNAMIC config option, which makes of_attach_node/of_detach_node
available without a specific config option.  CONFIG_OF_DYNAMIC wasn't actually
being used by anything, as the drivers which made use of of_attach_node
weren't depending upon or selecting it.

This also reworks of_attach_node to honor node ordering by time, rather than
creating the allnext/sibling list in reverse order.  This has a number of
ramifications worth mentioning:

 - 'last_child' is added to the device_node struct, and used to figure out
   where a node should be added in the tree.  This will take the place of
   the 'next' field.
 - 'allnodes' is no longer used.  It is assumed that the parent node is already
   attached to the tree.  What this really means is a simple assignment of
   "allnodes = root_node;" prior to calling of_attach_node(root_node).
 - The sibling list is guaranteed to retain order by insertion (later
   insertions showing up later in the list).
 - There are no similar guarantees for the allnext list with respect to
   parents, their children, and their siblings.  While siblings are
   guaranteed to be ordered by time, children may come before a sibling,
   or after.  That is, one ordering of the allnext list may be: "/", "/pci",
   "/isa", "/pci/foo", "/pci/bar".  Another perfectly valid ordering (and
   this *will* happen depending upon how insertions are done) is: "/",
   "/pci", "/pci/foo", "/pci/bar", "/isa".  The only thing that is
   guaranteed is that the sibling list will be "/pci", "/isa" (if "/isa"
   is added later), and that "/pci" will come before "/isa" in the allnext
   list.

Signed-off-by: Andres Salomon <dilinger@queued.net>
---
 drivers/of/Kconfig |    4 ----
 drivers/of/base.c  |   47 ++++++++++++++++++++++++++++++++---------------
 include/linux/of.h |    5 ++---
 3 files changed, 34 insertions(+), 22 deletions(-)

diff --git a/drivers/of/Kconfig b/drivers/of/Kconfig
index d06a637..ba90122 100644
--- a/drivers/of/Kconfig
+++ b/drivers/of/Kconfig
@@ -26,10 +26,6 @@ config OF_EARLY_FLATTREE
 config OF_PROMTREE
 	bool
 
-config OF_DYNAMIC
-	def_bool y
-	depends on PPC_OF
-
 config OF_ADDRESS
 	def_bool y
 	depends on !SPARC
diff --git a/drivers/of/base.c b/drivers/of/base.c
index 710b53b..9e94267 100644
--- a/drivers/of/base.c
+++ b/drivers/of/base.c
@@ -849,27 +849,46 @@ int prom_update_property(struct device_node *np,
 	return 0;
 }
 
-#if defined(CONFIG_OF_DYNAMIC)
-/*
- * Support for dynamic device trees.
- *
- * On some platforms, the device tree can be manipulated at runtime.
- * The routines in this section support adding, removing and changing
- * device tree nodes.
- */
-
 /**
  * of_attach_node - Plug a device node into the tree and global list.
  */
 void of_attach_node(struct device_node *np)
 {
+	struct device_node *parent;
 	unsigned long flags;
 
+	parent = np->parent;
+	if (!parent)
+		return;
+
 	write_lock_irqsave(&devtree_lock, flags);
-	np->sibling = np->parent->child;
-	np->allnext = allnodes;
-	np->parent->child = np;
-	allnodes = np;
+	if (parent->child) {
+		/*
+		 * We have at least 1 sibling, and last_child points to the
+		 * last one that we've inserted.
+		 *
+		 * After insertion, the current node will be the last sibling
+		 * in the sibling list (maintaining tree order), but will come
+		 * before any siblings' children in the allnext list.  That
+		 * holds true so long as the device tree is generated in a
+		 * depth-first fashion.  Children added later may screw with
+		 * the allnext ordering, but siblings are always guaranteed to
+		 * remain in the order in which they were added.
+		 */
+		parent->last_child->sibling = np;
+		np->allnext = parent->last_child->allnext;
+		parent->last_child->allnext = np;
+
+	} else {
+		/*
+		 * This node is an only child.  Allnext descends into the
+		 * child nodes from the parent.
+		 */
+		parent->child = np;
+		np->allnext = parent->allnext;
+		parent->allnext = np;
+	}
+	parent->last_child = np;
 	write_unlock_irqrestore(&devtree_lock, flags);
 }
 
@@ -917,5 +936,3 @@ void of_detach_node(struct device_node *np)
 out_unlock:
 	write_unlock_irqrestore(&devtree_lock, flags);
 }
-#endif /* defined(CONFIG_OF_DYNAMIC) */
-
diff --git a/include/linux/of.h b/include/linux/of.h
index bfc0ed1..f398ecd 100644
--- a/include/linux/of.h
+++ b/include/linux/of.h
@@ -49,6 +49,7 @@ struct device_node {
 	struct	property *deadprops;	/* removed properties */
 	struct	device_node *parent;
 	struct	device_node *child;
+	struct	device_node *last_child; /* last to be added to a tree level*/
 	struct	device_node *sibling;
 	struct	device_node *next;	/* next device of same type */
 	struct	device_node *allnext;	/* next in list of all nodes */
@@ -221,11 +222,9 @@ extern int prom_update_property(struct device_node *np,
 				struct property *newprop,
 				struct property *oldprop);
 
-#if defined(CONFIG_OF_DYNAMIC)
-/* For updating the device tree at runtime */
+/* For updating the device tree */
 extern void of_attach_node(struct device_node *);
 extern void of_detach_node(struct device_node *);
-#endif
 
 #else
 
-- 
1.7.2.3

[PATCH 2/4] of/promtree: switch to building the DT using of_attach_node

[Andres Salomon]

Use common functions (of_attach_node) to build the device tree.  This
allows us to drop a bit of code, and improves readability of the
tree building code.

Note that this changes what gets passed to the of_pdt_build_more()
hook.  The only user of this hook is sparc's leon_kernel.c, which ends
up using it to call prom_amba_init.  However, prom_amba_init isn't
actually set in the kernel, so I can't tell whether this actually breaks
behavior or not.

Signed-off-by: Andres Salomon <dilinger@queued.net>
---
 drivers/of/pdt.c |   30 ++++++------------------------
 1 files changed, 6 insertions(+), 24 deletions(-)

diff --git a/drivers/of/pdt.c b/drivers/of/pdt.c
index 4d87b5d..f3ddc2d 100644
--- a/drivers/of/pdt.c
+++ b/drivers/of/pdt.c
@@ -193,11 +193,8 @@ static struct device_node * __init of_pdt_create_node(phandle node,
 	return dp;
 }
 
-static struct device_node * __init of_pdt_build_tree(struct device_node *parent,
-						   phandle node,
-						   struct device_node ***nextp)
+static void __init of_pdt_build_tree(struct device_node *parent, phandle node)
 {
-	struct device_node *ret = NULL, *prev_sibling = NULL;
 	struct device_node *dp;
 
 	while (1) {
@@ -205,34 +202,20 @@ static struct device_node * __init of_pdt_build_tree(struct device_node *parent,
 		if (!dp)
 			break;
 
-		if (prev_sibling)
-			prev_sibling->sibling = dp;
-
-		if (!ret)
-			ret = dp;
-		prev_sibling = dp;
-
-		*(*nextp) = dp;
-		*nextp = &dp->allnext;
-
 		dp->full_name = of_pdt_build_full_name(dp);
+		of_attach_node(dp);
 
-		dp->child = of_pdt_build_tree(dp,
-				of_pdt_prom_ops->getchild(node), nextp);
+		of_pdt_build_tree(dp, of_pdt_prom_ops->getchild(node));
 
 		if (of_pdt_build_more)
-			of_pdt_build_more(dp, nextp);
+			of_pdt_build_more(dp, NULL);
 
 		node = of_pdt_prom_ops->getsibling(node);
 	}
-
-	return ret;
 }
 
 void __init of_pdt_build_devicetree(phandle root_node, struct of_pdt_ops *ops)
 {
-	struct device_node **nextp;
-
 	BUG_ON(!ops);
 	of_pdt_prom_ops = ops;
 
@@ -242,7 +225,6 @@ void __init of_pdt_build_devicetree(phandle root_node, struct of_pdt_ops *ops)
 #endif
 	allnodes->full_name = "/";
 
-	nextp = &allnodes->allnext;
-	allnodes->child = of_pdt_build_tree(allnodes,
-			of_pdt_prom_ops->getchild(allnodes->phandle), &nextp);
+	of_pdt_build_tree(allnodes,
+			of_pdt_prom_ops->getchild(allnodes->phandle));
 }
-- 
1.7.2.3

[PATCH 3/4] of/flattree: minor cleanups

[Andres Salomon]

 - static-ize some functions
 - add some additional comments

Signed-off-by: Andres Salomon <dilinger@queued.net>
---
 drivers/of/fdt.c |    6 ++++--
 1 files changed, 4 insertions(+), 2 deletions(-)

diff --git a/drivers/of/fdt.c b/drivers/of/fdt.c
index af824e7..c9db49c 100644
--- a/drivers/of/fdt.c
+++ b/drivers/of/fdt.c
@@ -139,12 +139,13 @@ static void *unflatten_dt_alloc(unsigned long *mem, unsigned long size,
 /**
  * unflatten_dt_node - Alloc and populate a device_node from the flat tree
  * @blob: The parent device tree blob
+ * @mem: Memory chunk to use for allocating device nodes and properties
  * @p: pointer to node in flat tree
  * @dad: Parent struct device_node
  * @allnextpp: pointer to ->allnext from last allocated device_node
  * @fpsize: Size of the node path up at the current depth.
  */
-unsigned long unflatten_dt_node(struct boot_param_header *blob,
+static unsigned long unflatten_dt_node(struct boot_param_header *blob,
 				unsigned long mem,
 				unsigned long *p,
 				struct device_node *dad,
@@ -230,6 +231,7 @@ unsigned long unflatten_dt_node(struct boot_param_header *blob,
 		}
 		kref_init(&np->kref);
 	}
+	/* process properties */
 	while (1) {
 		u32 sz, noff;
 		char *pname;
@@ -351,7 +353,7 @@ unsigned long unflatten_dt_node(struct boot_param_header *blob,
  * @dt_alloc: An allocator that provides a virtual address to memory
  * for the resulting tree
  */
-void __unflatten_device_tree(struct boot_param_header *blob,
+static void __unflatten_device_tree(struct boot_param_header *blob,
 			     struct device_node **mynodes,
 			     void * (*dt_alloc)(u64 size, u64 align))
 {
-- 
1.7.2.3

[PATCH 4/4] of/flattree: use of_attach_node to build tree

[Andres Salomon]

Use a common function (of_attach_node) to build the device tree.  This
simplifies the flat device tree creation a bit, and as an added bonus allows
us to drop a (now unused) field from the device_node struct.

Signed-off-by: Andres Salomon <dilinger@queued.net>
---
 drivers/of/fdt.c   |   35 ++++++++++++++---------------------
 include/linux/of.h |    1 -
 2 files changed, 14 insertions(+), 22 deletions(-)

diff --git a/drivers/of/fdt.c b/drivers/of/fdt.c
index c9db49c..2487356 100644
--- a/drivers/of/fdt.c
+++ b/drivers/of/fdt.c
@@ -142,14 +142,14 @@ static void *unflatten_dt_alloc(unsigned long *mem, unsigned long size,
  * @mem: Memory chunk to use for allocating device nodes and properties
  * @p: pointer to node in flat tree
  * @dad: Parent struct device_node
- * @allnextpp: pointer to ->allnext from last allocated device_node
+ * @rootp: tree's root node pointer
  * @fpsize: Size of the node path up at the current depth.
  */
 static unsigned long unflatten_dt_node(struct boot_param_header *blob,
 				unsigned long mem,
 				unsigned long *p,
 				struct device_node *dad,
-				struct device_node ***allnextpp,
+				struct device_node **rootp,
 				unsigned long fpsize)
 {
 	struct device_node *np;
@@ -196,7 +196,7 @@ static unsigned long unflatten_dt_node(struct boot_param_header *blob,
 
 	np = unflatten_dt_alloc(&mem, sizeof(struct device_node) + allocl,
 				__alignof__(struct device_node));
-	if (allnextpp) {
+	if (rootp) {
 		memset(np, 0, sizeof(*np));
 		np->full_name = ((char *)np) + sizeof(struct device_node);
 		if (new_format) {
@@ -218,17 +218,7 @@ static unsigned long unflatten_dt_node(struct boot_param_header *blob,
 		} else
 			memcpy(np->full_name, pathp, l);
 		prev_pp = &np->properties;
-		**allnextpp = np;
-		*allnextpp = &np->allnext;
-		if (dad != NULL) {
-			np->parent = dad;
-			/* we temporarily use the next field as `last_child'*/
-			if (dad->next == NULL)
-				dad->child = np;
-			else
-				dad->next->sibling = np;
-			dad->next = np;
-		}
+		np->parent = dad;
 		kref_init(&np->kref);
 	}
 	/* process properties */
@@ -260,7 +250,7 @@ static unsigned long unflatten_dt_node(struct boot_param_header *blob,
 		l = strlen(pname) + 1;
 		pp = unflatten_dt_alloc(&mem, sizeof(struct property),
 					__alignof__(struct property));
-		if (allnextpp) {
+		if (rootp) {
 			/* We accept flattened tree phandles either in
 			 * ePAPR-style "phandle" properties, or the
 			 * legacy "linux,phandle" properties.  If both
@@ -303,7 +293,7 @@ static unsigned long unflatten_dt_node(struct boot_param_header *blob,
 		sz = (pa - ps) + 1;
 		pp = unflatten_dt_alloc(&mem, sizeof(struct property) + sz,
 					__alignof__(struct property));
-		if (allnextpp) {
+		if (rootp) {
 			pp->name = "name";
 			pp->length = sz;
 			pp->value = pp + 1;
@@ -315,7 +305,7 @@ static unsigned long unflatten_dt_node(struct boot_param_header *blob,
 				(char *)pp->value);
 		}
 	}
-	if (allnextpp) {
+	if (rootp) {
 		*prev_pp = NULL;
 		np->name = of_get_property(np, "name", NULL);
 		np->type = of_get_property(np, "device_type", NULL);
@@ -324,12 +314,17 @@ static unsigned long unflatten_dt_node(struct boot_param_header *blob,
 			np->name = "<NULL>";
 		if (!np->type)
 			np->type = "<NULL>";
+		of_attach_node(np);
+
+		/* if no parent, then we're looking at the root node */
+		if (!np->parent)
+			*rootp = np;
 	}
 	while (tag == OF_DT_BEGIN_NODE || tag == OF_DT_NOP) {
 		if (tag == OF_DT_NOP)
 			*p += 4;
 		else
-			mem = unflatten_dt_node(blob, mem, p, np, allnextpp,
+			mem = unflatten_dt_node(blob, mem, p, np, rootp,
 						fpsize);
 		tag = be32_to_cpup((__be32 *)(*p));
 	}
@@ -358,7 +353,6 @@ static void __unflatten_device_tree(struct boot_param_header *blob,
 			     void * (*dt_alloc)(u64 size, u64 align))
 {
 	unsigned long start, mem, size;
-	struct device_node **allnextp = mynodes;
 
 	pr_debug(" -> unflatten_device_tree()\n");
 
@@ -396,13 +390,12 @@ static void __unflatten_device_tree(struct boot_param_header *blob,
 	/* Second pass, do actual unflattening */
 	start = ((unsigned long)blob) +
 		be32_to_cpu(blob->off_dt_struct);
-	unflatten_dt_node(blob, mem, &start, NULL, &allnextp, 0);
+	unflatten_dt_node(blob, mem, &start, NULL, mynodes, 0);
 	if (be32_to_cpup((__be32 *)start) != OF_DT_END)
 		pr_warning("Weird tag at end of tree: %08x\n", *((u32 *)start));
 	if (be32_to_cpu(((__be32 *)mem)[size / 4]) != 0xdeadbeef)
 		pr_warning("End of tree marker overwritten: %08x\n",
 			   be32_to_cpu(((__be32 *)mem)[size / 4]));
-	*allnextp = NULL;
 
 	pr_debug(" <- unflatten_device_tree()\n");
 }
diff --git a/include/linux/of.h b/include/linux/of.h
index f398ecd..58ef067 100644
--- a/include/linux/of.h
+++ b/include/linux/of.h
@@ -51,7 +51,6 @@ struct device_node {
 	struct	device_node *child;
 	struct	device_node *last_child; /* last to be added to a tree level*/
 	struct	device_node *sibling;
-	struct	device_node *next;	/* next device of same type */
 	struct	device_node *allnext;	/* next in list of all nodes */
 	struct	proc_dir_entry *pde;	/* this node's proc directory */
 	struct	kref kref;
-- 
1.7.2.3

Re: [PATCH 0/4] switch DT creation to using of_attach_node (v2)

[Grant Likely]

On Thu, Mar 17, 2011 at 05:32:32PM -0700, Andres Salomon wrote:
> This is attempt #2 to make OF core use of_attach_node for both promtree
> and flattree building.  This reworks of_attach_node quite a bit to conform
> with our expectations of how the DT should look in memory.
> 
> It's different in many ways from the original patches, so it's worth
> reviewing each in their entirety.

Thanks Andres,

Ping me on this stuff after the merge window.  I don't have time to
look at it now, but I'll do so right all the stuff for .39 is taken
care of.

g.

Re: [PATCH 3/4] of/flattree: minor cleanups

[Grant Likely]

On Thu, Mar 17, 2011 at 05:32:35PM -0700, Andres Salomon wrote:
>  - static-ize some functions
>  - add some additional comments
> 
> Signed-off-by: Andres Salomon <dilinger@queued.net>

Merged, thanks.  I'll look at the rest after the merge window.

g.

> ---
>  drivers/of/fdt.c |    6 ++++--
>  1 files changed, 4 insertions(+), 2 deletions(-)
> 
> diff --git a/drivers/of/fdt.c b/drivers/of/fdt.c
> index af824e7..c9db49c 100644
> --- a/drivers/of/fdt.c
> +++ b/drivers/of/fdt.c
> @@ -139,12 +139,13 @@ static void *unflatten_dt_alloc(unsigned long *mem, unsigned long size,
>  /**
>   * unflatten_dt_node - Alloc and populate a device_node from the flat tree
>   * @blob: The parent device tree blob
> + * @mem: Memory chunk to use for allocating device nodes and properties
>   * @p: pointer to node in flat tree
>   * @dad: Parent struct device_node
>   * @allnextpp: pointer to ->allnext from last allocated device_node
>   * @fpsize: Size of the node path up at the current depth.
>   */
> -unsigned long unflatten_dt_node(struct boot_param_header *blob,
> +static unsigned long unflatten_dt_node(struct boot_param_header *blob,
>  				unsigned long mem,
>  				unsigned long *p,
>  				struct device_node *dad,
> @@ -230,6 +231,7 @@ unsigned long unflatten_dt_node(struct boot_param_header *blob,
>  		}
>  		kref_init(&np->kref);
>  	}
> +	/* process properties */
>  	while (1) {
>  		u32 sz, noff;
>  		char *pname;
> @@ -351,7 +353,7 @@ unsigned long unflatten_dt_node(struct boot_param_header *blob,
>   * @dt_alloc: An allocator that provides a virtual address to memory
>   * for the resulting tree
>   */
> -void __unflatten_device_tree(struct boot_param_header *blob,
> +static void __unflatten_device_tree(struct boot_param_header *blob,
>  			     struct device_node **mynodes,
>  			     void * (*dt_alloc)(u64 size, u64 align))
>  {
> -- 
> 1.7.2.3
> 

Re: [PATCH 1/4] of: rework of_attach_node, removing CONFIG_OF_DYNAMIC

[Grant Likely]

On Thu, Mar 17, 2011 at 05:32:33PM -0700, Andres Salomon wrote:
> Remove the OF_DYNAMIC config option, which makes of_attach_node/of_detach_node
> available without a specific config option.  CONFIG_OF_DYNAMIC wasn't actually
> being used by anything, as the drivers which made use of of_attach_node
> weren't depending upon or selecting it.
> 
> This also reworks of_attach_node to honor node ordering by time, rather than
> creating the allnext/sibling list in reverse order.  This has a number of
> ramifications worth mentioning:
> 
>  - 'last_child' is added to the device_node struct, and used to figure out
>    where a node should be added in the tree.  This will take the place of
>    the 'next' field.
>  - 'allnodes' is no longer used.  It is assumed that the parent node is already
>    attached to the tree.  What this really means is a simple assignment of
>    "allnodes = root_node;" prior to calling of_attach_node(root_node).
>  - The sibling list is guaranteed to retain order by insertion (later
>    insertions showing up later in the list).
>  - There are no similar guarantees for the allnext list with respect to
>    parents, their children, and their siblings.  While siblings are
>    guaranteed to be ordered by time, children may come before a sibling,
>    or after.  That is, one ordering of the allnext list may be: "/", "/pci",
>    "/isa", "/pci/foo", "/pci/bar".  Another perfectly valid ordering (and
>    this *will* happen depending upon how insertions are done) is: "/",
>    "/pci", "/pci/foo", "/pci/bar", "/isa".  The only thing that is
>    guaranteed is that the sibling list will be "/pci", "/isa" (if "/isa"
>    is added later), and that "/pci" will come before "/isa" in the allnext
>    list.
> 
> Signed-off-by: Andres Salomon <dilinger@queued.net>

Hi Andres, comment below.

> ---
>  drivers/of/Kconfig |    4 ----
>  drivers/of/base.c  |   47 ++++++++++++++++++++++++++++++++---------------
>  include/linux/of.h |    5 ++---
>  3 files changed, 34 insertions(+), 22 deletions(-)
> 
> diff --git a/drivers/of/Kconfig b/drivers/of/Kconfig
> index d06a637..ba90122 100644
> --- a/drivers/of/Kconfig
> +++ b/drivers/of/Kconfig
> @@ -26,10 +26,6 @@ config OF_EARLY_FLATTREE
>  config OF_PROMTREE
>  	bool
>  
> -config OF_DYNAMIC
> -	def_bool y
> -	depends on PPC_OF
> -
>  config OF_ADDRESS
>  	def_bool y
>  	depends on !SPARC
> diff --git a/drivers/of/base.c b/drivers/of/base.c
> index 710b53b..9e94267 100644
> --- a/drivers/of/base.c
> +++ b/drivers/of/base.c
> @@ -849,27 +849,46 @@ int prom_update_property(struct device_node *np,
>  	return 0;
>  }
>  
> -#if defined(CONFIG_OF_DYNAMIC)
> -/*
> - * Support for dynamic device trees.
> - *
> - * On some platforms, the device tree can be manipulated at runtime.
> - * The routines in this section support adding, removing and changing
> - * device tree nodes.
> - */
> -
>  /**
>   * of_attach_node - Plug a device node into the tree and global list.
>   */
>  void of_attach_node(struct device_node *np)
>  {
> +	struct device_node *parent;
>  	unsigned long flags;
>  
> +	parent = np->parent;
> +	if (!parent)
> +		return;
> +
>  	write_lock_irqsave(&devtree_lock, flags);
> -	np->sibling = np->parent->child;
> -	np->allnext = allnodes;
> -	np->parent->child = np;
> -	allnodes = np;
> +	if (parent->child) {
> +		/*
> +		 * We have at least 1 sibling, and last_child points to the
> +		 * last one that we've inserted.
> +		 *
> +		 * After insertion, the current node will be the last sibling
> +		 * in the sibling list (maintaining tree order), but will come
> +		 * before any siblings' children in the allnext list.  That
> +		 * holds true so long as the device tree is generated in a
> +		 * depth-first fashion.  Children added later may screw with
> +		 * the allnext ordering, but siblings are always guaranteed to
> +		 * remain in the order in which they were added.
> +		 */
> +		parent->last_child->sibling = np;
> +		np->allnext = parent->last_child->allnext;
> +		parent->last_child->allnext = np;
> +
> +	} else {
> +		/*
> +		 * This node is an only child.  Allnext descends into the
> +		 * child nodes from the parent.
> +		 */
> +		parent->child = np;
> +		np->allnext = parent->allnext;
> +		parent->allnext = np;
> +	}
> +	parent->last_child = np;

Hmmm... this screams to me that it shouldn't be open-coded.  Instead,
it really should be using list_head.  Unfortunately, that is a more
complex change, but I don't think I want to open code a new list
implementation.

blech.  I need to think about that more.

g.