[PATCH] Patch to improve device tree structure

[PATCH] Patch to improve device tree structure

[Gaurav Minocha]

This patch improves the implementation of device tree structure.

Traditional child and sibling linked list in device tree structure
is removed and is replaced by list_head (i.e. circular doubly linked
 list) already available in Linux kernel.

Signed-off-by: Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
---
 drivers/of/base.c     |  36 ++++++++++----
 drivers/of/dynamic.c  |  18 ++-----
 drivers/of/fdt.c      |   7 ++-
 drivers/of/selftest.c | 130 +++++++++++++++++++++++---------------------------
 include/linux/of.h    |   4 +-
 5 files changed, 97 insertions(+), 98 deletions(-)

diff --git a/drivers/of/base.c b/drivers/of/base.c
index 2305dc0..7acaeca 100644
--- a/drivers/of/base.c
+++ b/drivers/of/base.c
@@ -603,16 +603,25 @@ EXPORT_SYMBOL(of_get_next_parent);
 static struct device_node *__of_get_next_child(const struct device_node *node,
 						struct device_node *prev)
 {
-	struct device_node *next;
+	struct device_node *next = NULL, *np;
+	struct list_head *pos;
+	int found = 0;
 
 	if (!node)
 		return NULL;
 
-	next = prev ? prev->sibling : node->child;
-	for (; next; next = next->sibling)
-		if (of_node_get(next))
-			break;
+	// move through the children list, and find the next node
+	list_for_each(pos, &node->children) {
+		np = list_entry(pos, struct device_node, siblings);
+		if ((!prev || (found == 1)) && of_node_get(np)) {
+				next = np;
+				break;
+		}
+		if (prev && strcmp(np->full_name, prev->full_name) == 0)
+			found = 1;
+	}
 	of_node_put(prev);
+
 	return next;
 }
 #define __for_each_child_of_node(parent, child) \
@@ -651,22 +660,29 @@ EXPORT_SYMBOL(of_get_next_child);
 struct device_node *of_get_next_available_child(const struct device_node *node,
 	struct device_node *prev)
 {
-	struct device_node *next;
+	struct device_node *next = NULL, *np;
+	struct list_head *pos;
 	unsigned long flags;
+	int found = 0;
 
 	if (!node)
 		return NULL;
 
 	raw_spin_lock_irqsave(&devtree_lock, flags);
-	next = prev ? prev->sibling : node->child;
-	for (; next; next = next->sibling) {
-		if (!__of_device_is_available(next))
+	list_for_each(pos, &node->children) {
+		np = list_entry(pos, struct device_node, siblings);
+		if (!__of_device_is_available(np))
 			continue;
-		if (of_node_get(next))
+		if ((!prev || (found == 1)) && of_node_get(np)) {
+			next = np;
 			break;
+		}
+		if (prev && strcmp(np->full_name, prev->full_name) == 0)
+			found = 1;
 	}
 	of_node_put(prev);
 	raw_spin_unlock_irqrestore(&devtree_lock, flags);
+
 	return next;
 }
 EXPORT_SYMBOL(of_get_next_available_child);
diff --git a/drivers/of/dynamic.c b/drivers/of/dynamic.c
index f297891..3ffc726 100644
--- a/drivers/of/dynamic.c
+++ b/drivers/of/dynamic.c
@@ -115,11 +115,12 @@ void __of_attach_node(struct device_node *np)
 		phandle = __of_get_property(np, "ibm,phandle", &sz);
 	np->phandle = (phandle && (sz >= 4)) ? be32_to_cpup(phandle) : 0;
 
-	np->child = NULL;
-	np->sibling = np->parent->child;
+	INIT_LIST_HEAD(&np->siblings);
+	INIT_LIST_HEAD(&np->children);
+	list_add_tail(&(np->siblings), &(np->parent->children));
+
 	np->allnext = np->parent->allnext;
 	np->parent->allnext = np;
-	np->parent->child = np;
 	of_node_clear_flag(np, OF_DETACHED);
 }
 
@@ -165,16 +166,7 @@ void __of_detach_node(struct device_node *np)
 		prev->allnext = np->allnext;
 	}
 
-	if (parent->child == np)
-		parent->child = np->sibling;
-	else {
-		struct device_node *prevsib;
-		for (prevsib = np->parent->child;
-		     prevsib->sibling != np;
-		     prevsib = prevsib->sibling)
-			;
-		prevsib->sibling = np->sibling;
-	}
+	list_del(&np->siblings);
 
 	of_node_set_flag(np, OF_DETACHED);
 }
diff --git a/drivers/of/fdt.c b/drivers/of/fdt.c
index d1ffca8..4cf2356 100644
--- a/drivers/of/fdt.c
+++ b/drivers/of/fdt.c
@@ -224,13 +224,12 @@ static void * unflatten_dt_node(void *blob,
 		prev_pp = &np->properties;
 		**allnextpp = np;
 		*allnextpp = &np->allnext;
+		INIT_LIST_HEAD(&np->siblings);
+		INIT_LIST_HEAD(&np->children);
 		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;
+			list_add_tail(&(np->siblings), &(dad->children));
 			dad->next = np;
 		}
 	}
diff --git a/drivers/of/selftest.c b/drivers/of/selftest.c
index 7800127..8ec8a22 100644
--- a/drivers/of/selftest.c
+++ b/drivers/of/selftest.c
@@ -25,10 +25,11 @@ static struct selftest_results {
 	int failed;
 } selftest_results;
 
-#define NO_OF_NODES 3
-static struct device_node *nodes[NO_OF_NODES];
-static int last_node_index;
+#define MAX_NODES 50
+
+static int no_of_nodes;
 static bool selftest_live_tree;
+static struct device_node* nodes[MAX_NODES];
 
 #define selftest(result, fmt, ...) { \
 	if (!(result)) { \
@@ -417,7 +418,6 @@ static void __init of_selftest_changeset(void)
 	n1->parent = parent;
 	n2->parent = parent;
 	n21->parent = n2;
-	n2->child = n21;
 	ppremove = of_find_property(parent, "prop-remove", NULL);
 	selftest(ppremove, "failed to find removal prop");
 
@@ -713,44 +713,34 @@ static void update_node_properties(struct device_node *np,
 		child->parent = dup;
 }
 
-/**
- *	attach_node_and_children - attaches nodes
- *	and its children to live tree
- *
- *	@np:	Node to attach to live tree
- */
-static int attach_node_and_children(struct device_node *np)
-{
-	struct device_node *next, *root = np, *dup;
 
-	/* skip root node */
-	np = np->child;
-	/* storing a copy in temporary node */
-	dup = np;
+static void populate_node_list(struct device_node *np)
+{
+	struct list_head *pos;
 
-	while (dup) {
-		if (WARN_ON(last_node_index >= NO_OF_NODES))
-			return -EINVAL;
-		nodes[last_node_index++] = dup;
-		dup = dup->sibling;
+	list_for_each(pos, &np->children) {
+		nodes[no_of_nodes] = list_entry(pos, struct device_node, siblings);
+		populate_node_list(nodes[no_of_nodes++]);
 	}
-	dup = NULL;
+}
 
-	while (np) {
-		next = np->allnext;
-		dup = of_find_node_by_path(np->full_name);
+static void attach_node_and_children(struct device_node *np)
+{
+	struct device_node *root = np, *dup, *temp;
+	int i;
+
+	populate_node_list(np);
+
+	for (i = 0; i < no_of_nodes && nodes[i]; i++) {
+		temp = nodes[i];
+		if (temp->parent == root)
+			temp->parent = of_allnodes;
+		dup = of_find_node_by_path(temp->full_name);
 		if (dup)
-			update_node_properties(np, dup);
-		else {
-			np->child = NULL;
-			if (np->parent == root)
-				np->parent = of_allnodes;
-			of_attach_node(np);
-		}
-		np = next;
+			update_node_properties(temp, dup);
+		else
+			of_attach_node(temp);
 	}
-
-	return 0;
 }
 
 /**
@@ -764,7 +754,8 @@ static int __init selftest_data_add(void)
 	extern uint8_t __dtb_testcases_begin[];
 	extern uint8_t __dtb_testcases_end[];
 	const int size = __dtb_testcases_end - __dtb_testcases_begin;
-	int rc;
+	struct list_head *pos;
+	int rc, i = 0;
 
 	if (!size) {
 		pr_warn("%s: No testcase data to attach; not running tests\n",
@@ -796,65 +787,66 @@ static int __init selftest_data_add(void)
 		/* enabling flag for removing nodes */
 		selftest_live_tree = true;
 		of_allnodes = selftest_data_node;
+		populate_node_list(selftest_data_node);
+
+		// attach the root node
+		__of_attach_node_sysfs(selftest_data_node);
+
+		while (i < no_of_nodes && nodes[i])
+			__of_attach_node_sysfs(nodes[i++]);
 
-		for_each_of_allnodes(np)
-			__of_attach_node_sysfs(np);
 		of_aliases = of_find_node_by_path("/aliases");
 		of_chosen = of_find_node_by_path("/chosen");
 		return 0;
 	}
 
+	list_for_each(pos, &selftest_data_node->children) {
+		np = list_entry(pos, struct device_node, siblings);
+		np->parent = of_allnodes;
+	}
+
+
 	/* attach the sub-tree to live tree */
-	return attach_node_and_children(selftest_data_node);
-}
+	attach_node_and_children(selftest_data_node);
 
-/**
- *	detach_node_and_children - detaches node
- *	and its children from live tree
- *
- *	@np:	Node to detach from live tree
- */
-static void detach_node_and_children(struct device_node *np)
-{
-	while (np->child)
-		detach_node_and_children(np->child);
-	of_detach_node(np);
+	return 0;
 }
 
-/**
- *	selftest_data_remove - removes the selftest data
- *	nodes from the live tree
- */
 static void selftest_data_remove(void)
 {
-	struct device_node *np;
 	struct property *prop;
+	struct device_node *np, *temp;
+	int i = no_of_nodes;
 
 	if (selftest_live_tree) {
 		of_node_put(of_aliases);
 		of_node_put(of_chosen);
 		of_aliases = NULL;
 		of_chosen = NULL;
-		for_each_child_of_node(of_allnodes, np)
-			detach_node_and_children(np);
+		while (i >= 0) {
+			temp = nodes[i--];
+			if (temp)
+				of_detach_node(temp);
+		}
 		__of_detach_node_sysfs(of_allnodes);
 		of_allnodes = NULL;
 		return;
 	}
 
-	while (last_node_index >= 0) {
-		if (nodes[last_node_index]) {
-			np = of_find_node_by_path(nodes[last_node_index]->full_name);
-			if (strcmp(np->full_name, "/aliases") != 0) {
-				detach_node_and_children(np);
-			} else {
-				for_each_property_of_node(np, prop) {
-					if (strcmp(prop->name, "testcase-alias") == 0)
+	while (i >= 0) {
+		temp = nodes[i--];
+		if (temp) {
+			if (strcmp(temp->full_name, "/aliases") == 0) {
+				for_each_property_of_node(temp, prop) {
+					if (strcmp(prop->name, "testcase-alias") == 0) {
+						np = of_find_node_by_path(temp->full_name);
 						of_remove_property(np, prop);
+					}
 				}
 			}
+			else
+				of_detach_node(temp);
 		}
-		last_node_index--;
 	}
 }
 
@@ -865,6 +857,7 @@ static int __init of_selftest(void)
 
 	/* adding data for selftest */
 	res = selftest_data_add();
+
 	if (res)
 		return res;
 
@@ -891,7 +884,6 @@ static int __init of_selftest(void)
 
 	/* removing selftest data from live tree */
 	selftest_data_remove();
-
 	/* Double check linkage after removing testcase data */
 	of_selftest_check_tree_linkage();
 
diff --git a/include/linux/of.h b/include/linux/of.h
index 6545e7a..84c708c 100644
--- a/include/linux/of.h
+++ b/include/linux/of.h
@@ -53,10 +53,10 @@ struct device_node {
 	struct	property *properties;
 	struct	property *deadprops;	/* removed properties */
 	struct	device_node *parent;
-	struct	device_node *child;
-	struct	device_node *sibling;
 	struct	device_node *next;	/* next device of same type */
 	struct	device_node *allnext;	/* next in list of all nodes */
+	struct	list_head children;
+	struct	list_head siblings;
 	struct	kobject kobj;
 	unsigned long _flags;
 	void	*data;
-- 
1.9.1

--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] Patch to improve device tree structure

[Frank Rowand]

On 11/16/2014 8:52 PM, Gaurav Minocha wrote:
> This patch improves the implementation of device tree structure.

Could you add a brief reason of why this is an improvement?


> Traditional child and sibling linked list in device tree structure
> is removed and is replaced by list_head (i.e. circular doubly linked
>  list) already available in Linux kernel.
> 
> Signed-off-by: Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
> ---

< snip >

Thanks,

-Frank

--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] Patch to improve device tree structure

[Grant Likely]

On Sun, 16 Nov 2014 20:52:56 -0800
, Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
 wrote:
> This patch improves the implementation of device tree structure.
> 
> Traditional child and sibling linked list in device tree structure
> is removed and is replaced by list_head (i.e. circular doubly linked
>  list) already available in Linux kernel.
> 
> Signed-off-by: Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>

Hi Gaurav,

So, after you've done this work, I need to you rebase it (and of course
it is non-trivial) onto linux-next. I've already got a patch queued up
which gets rid of the of_allnodes/allnext list which will have conflicts
with this patch.

I'll make comments below where still relevant.

> ---
>  drivers/of/base.c     |  36 ++++++++++----
>  drivers/of/dynamic.c  |  18 ++-----
>  drivers/of/fdt.c      |   7 ++-
>  drivers/of/selftest.c | 130 +++++++++++++++++++++++---------------------------
>  include/linux/of.h    |   4 +-
>  5 files changed, 97 insertions(+), 98 deletions(-)
> 
> diff --git a/drivers/of/base.c b/drivers/of/base.c
> index 2305dc0..7acaeca 100644
> --- a/drivers/of/base.c
> +++ b/drivers/of/base.c
> @@ -603,16 +603,25 @@ EXPORT_SYMBOL(of_get_next_parent);
>  static struct device_node *__of_get_next_child(const struct device_node *node,
>  						struct device_node *prev)
>  {
> -	struct device_node *next;
> +	struct device_node *next = NULL, *np;
> +	struct list_head *pos;
> +	int found = 0;
>  
>  	if (!node)
>  		return NULL;
>  
> -	next = prev ? prev->sibling : node->child;
> -	for (; next; next = next->sibling)
> -		if (of_node_get(next))
> -			break;
> +	// move through the children list, and find the next node
> +	list_for_each(pos, &node->children) {
> +		np = list_entry(pos, struct device_node, siblings);
> +		if ((!prev || (found == 1)) && of_node_get(np)) {
> +				next = np;
> +				break;
> +		}
> +		if (prev && strcmp(np->full_name, prev->full_name) == 0)
> +			found = 1;

What is this 'found' stuff about? Why is this in the loop?

> +	}
>  	of_node_put(prev);

Most of this code can be eliminated by using list_for_each_entry().
Actually, the use of a loop here in the original code is a little bit
goofy simply because it never actually loops. It always exits on the
first iteration, but it does conveniently calculate the next entry in
the list. The thing to do here is take inspiration from the
list_for_each_entry() implementation and do the following:

	if (!prev) {
		next = list_first_entry_or_null(&node->children, struct device_node, siblings);
	} else if (prev->siblings.next != &node->children)
		next = list_next_entry(prev, siblings);
	} else {
		next = NULL;
	}

> +
>  	return next;
>  }
>  #define __for_each_child_of_node(parent, child) \
> @@ -651,22 +660,29 @@ EXPORT_SYMBOL(of_get_next_child);
>  struct device_node *of_get_next_available_child(const struct device_node *node,
>  	struct device_node *prev)
>  {
> -	struct device_node *next;
> +	struct device_node *next = NULL, *np;
> +	struct list_head *pos;
>  	unsigned long flags;
> +	int found = 0;
>  
>  	if (!node)
>  		return NULL;
>  
>  	raw_spin_lock_irqsave(&devtree_lock, flags);
> -	next = prev ? prev->sibling : node->child;
> -	for (; next; next = next->sibling) {
> -		if (!__of_device_is_available(next))
> +	list_for_each(pos, &node->children) {

Use list_for_each_entry_continue(), but there will be a bit of fiddling
to make sure the first entry in the list is handled correctly. You can
handle this by using list_entry on the &node->children list, but be
careful to never actually dereference that pointer.

> +		np = list_entry(pos, struct device_node, siblings);
> +		if (!__of_device_is_available(np))
>  			continue;
> -		if (of_node_get(next))
> +		if ((!prev || (found == 1)) && of_node_get(np)) {
> +			next = np;
>  			break;
> +		}
> +		if (prev && strcmp(np->full_name, prev->full_name) == 0)
> +			found = 1;
>  	}
>  	of_node_put(prev);
>  	raw_spin_unlock_irqrestore(&devtree_lock, flags);
> +
>  	return next;
>  }
>  EXPORT_SYMBOL(of_get_next_available_child);
> diff --git a/drivers/of/dynamic.c b/drivers/of/dynamic.c
> index f297891..3ffc726 100644
> --- a/drivers/of/dynamic.c
> +++ b/drivers/of/dynamic.c
> @@ -115,11 +115,12 @@ void __of_attach_node(struct device_node *np)
>  		phandle = __of_get_property(np, "ibm,phandle", &sz);
>  	np->phandle = (phandle && (sz >= 4)) ? be32_to_cpup(phandle) : 0;
>  
> -	np->child = NULL;
> -	np->sibling = np->parent->child;
> +	INIT_LIST_HEAD(&np->siblings);
> +	INIT_LIST_HEAD(&np->children);
> +	list_add_tail(&(np->siblings), &(np->parent->children));
> +
>  	np->allnext = np->parent->allnext;
>  	np->parent->allnext = np;
> -	np->parent->child = np;
>  	of_node_clear_flag(np, OF_DETACHED);
>  }
>  
> @@ -165,16 +166,7 @@ void __of_detach_node(struct device_node *np)
>  		prev->allnext = np->allnext;
>  	}
>  
> -	if (parent->child == np)
> -		parent->child = np->sibling;
> -	else {
> -		struct device_node *prevsib;
> -		for (prevsib = np->parent->child;
> -		     prevsib->sibling != np;
> -		     prevsib = prevsib->sibling)
> -			;
> -		prevsib->sibling = np->sibling;
> -	}
> +	list_del(&np->siblings);
>  
>  	of_node_set_flag(np, OF_DETACHED);
>  }
> diff --git a/drivers/of/fdt.c b/drivers/of/fdt.c
> index d1ffca8..4cf2356 100644
> --- a/drivers/of/fdt.c
> +++ b/drivers/of/fdt.c
> @@ -224,13 +224,12 @@ static void * unflatten_dt_node(void *blob,
>  		prev_pp = &np->properties;
>  		**allnextpp = np;
>  		*allnextpp = &np->allnext;
> +		INIT_LIST_HEAD(&np->siblings);
> +		INIT_LIST_HEAD(&np->children);
>  		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;
> +			list_add_tail(&(np->siblings), &(dad->children));
>  			dad->next = np;
>  		}
>  	}
> diff --git a/drivers/of/selftest.c b/drivers/of/selftest.c
> index 7800127..8ec8a22 100644
> --- a/drivers/of/selftest.c
> +++ b/drivers/of/selftest.c
> @@ -25,10 +25,11 @@ static struct selftest_results {
>  	int failed;
>  } selftest_results;
>  
> -#define NO_OF_NODES 3
> -static struct device_node *nodes[NO_OF_NODES];
> -static int last_node_index;
> +#define MAX_NODES 50
> +
> +static int no_of_nodes;
>  static bool selftest_live_tree;
> +static struct device_node* nodes[MAX_NODES];

I think it's time to rework this structure. Instead of a static list,
the code should figure out how many entries it needs and then kzalloc()
the region.

>  
>  #define selftest(result, fmt, ...) { \
>  	if (!(result)) { \
> @@ -417,7 +418,6 @@ static void __init of_selftest_changeset(void)
>  	n1->parent = parent;
>  	n2->parent = parent;
>  	n21->parent = n2;
> -	n2->child = n21;
>  	ppremove = of_find_property(parent, "prop-remove", NULL);
>  	selftest(ppremove, "failed to find removal prop");
>  
> @@ -713,44 +713,34 @@ static void update_node_properties(struct device_node *np,
>  		child->parent = dup;
>  }
>  
> -/**
> - *	attach_node_and_children - attaches nodes
> - *	and its children to live tree
> - *
> - *	@np:	Node to attach to live tree
> - */
> -static int attach_node_and_children(struct device_node *np)
> -{
> -	struct device_node *next, *root = np, *dup;
>  
> -	/* skip root node */
> -	np = np->child;
> -	/* storing a copy in temporary node */
> -	dup = np;
> +static void populate_node_list(struct device_node *np)
> +{
> +	struct list_head *pos;
>  
> -	while (dup) {
> -		if (WARN_ON(last_node_index >= NO_OF_NODES))
> -			return -EINVAL;
> -		nodes[last_node_index++] = dup;
> -		dup = dup->sibling;
> +	list_for_each(pos, &np->children) {
> +		nodes[no_of_nodes] = list_entry(pos, struct device_node, siblings);
> +		populate_node_list(nodes[no_of_nodes++]);
>  	}
> -	dup = NULL;
> +}
>  
> -	while (np) {
> -		next = np->allnext;
> -		dup = of_find_node_by_path(np->full_name);
> +static void attach_node_and_children(struct device_node *np)
> +{
> +	struct device_node *root = np, *dup, *temp;
> +	int i;
> +
> +	populate_node_list(np);
> +
> +	for (i = 0; i < no_of_nodes && nodes[i]; i++) {
> +		temp = nodes[i];
> +		if (temp->parent == root)
> +			temp->parent = of_allnodes;
> +		dup = of_find_node_by_path(temp->full_name);
>  		if (dup)
> -			update_node_properties(np, dup);
> -		else {
> -			np->child = NULL;
> -			if (np->parent == root)
> -				np->parent = of_allnodes;
> -			of_attach_node(np);
> -		}
> -		np = next;
> +			update_node_properties(temp, dup);
> +		else
> +			of_attach_node(temp);
>  	}
> -
> -	return 0;
>  }
>  
>  /**
> @@ -764,7 +754,8 @@ static int __init selftest_data_add(void)
>  	extern uint8_t __dtb_testcases_begin[];
>  	extern uint8_t __dtb_testcases_end[];
>  	const int size = __dtb_testcases_end - __dtb_testcases_begin;
> -	int rc;
> +	struct list_head *pos;
> +	int rc, i = 0;
>  
>  	if (!size) {
>  		pr_warn("%s: No testcase data to attach; not running tests\n",
> @@ -796,65 +787,66 @@ static int __init selftest_data_add(void)
>  		/* enabling flag for removing nodes */
>  		selftest_live_tree = true;
>  		of_allnodes = selftest_data_node;
> +		populate_node_list(selftest_data_node);
> +
> +		// attach the root node
> +		__of_attach_node_sysfs(selftest_data_node);
> +
> +		while (i < no_of_nodes && nodes[i])
> +			__of_attach_node_sysfs(nodes[i++]);
>  
> -		for_each_of_allnodes(np)
> -			__of_attach_node_sysfs(np);
>  		of_aliases = of_find_node_by_path("/aliases");
>  		of_chosen = of_find_node_by_path("/chosen");
>  		return 0;
>  	}
>  
> +	list_for_each(pos, &selftest_data_node->children) {
> +		np = list_entry(pos, struct device_node, siblings);
> +		np->parent = of_allnodes;
> +	}
> +
> +
>  	/* attach the sub-tree to live tree */
> -	return attach_node_and_children(selftest_data_node);
> -}
> +	attach_node_and_children(selftest_data_node);
>  
> -/**
> - *	detach_node_and_children - detaches node
> - *	and its children from live tree
> - *
> - *	@np:	Node to detach from live tree
> - */
> -static void detach_node_and_children(struct device_node *np)
> -{
> -	while (np->child)
> -		detach_node_and_children(np->child);
> -	of_detach_node(np);
> +	return 0;
>  }
>  
> -/**
> - *	selftest_data_remove - removes the selftest data
> - *	nodes from the live tree
> - */
>  static void selftest_data_remove(void)
>  {
> -	struct device_node *np;
>  	struct property *prop;
> +	struct device_node *np, *temp;
> +	int i = no_of_nodes;
>  
>  	if (selftest_live_tree) {
>  		of_node_put(of_aliases);
>  		of_node_put(of_chosen);
>  		of_aliases = NULL;
>  		of_chosen = NULL;
> -		for_each_child_of_node(of_allnodes, np)
> -			detach_node_and_children(np);
> +		while (i >= 0) {
> +			temp = nodes[i--];
> +			if (temp)
> +				of_detach_node(temp);
> +		}
>  		__of_detach_node_sysfs(of_allnodes);
>  		of_allnodes = NULL;
>  		return;
>  	}
>  
> -	while (last_node_index >= 0) {
> -		if (nodes[last_node_index]) {
> -			np = of_find_node_by_path(nodes[last_node_index]->full_name);
> -			if (strcmp(np->full_name, "/aliases") != 0) {
> -				detach_node_and_children(np);
> -			} else {
> -				for_each_property_of_node(np, prop) {
> -					if (strcmp(prop->name, "testcase-alias") == 0)
> +	while (i >= 0) {
> +		temp = nodes[i--];
> +		if (temp) {
> +			if (strcmp(temp->full_name, "/aliases") == 0) {
> +				for_each_property_of_node(temp, prop) {
> +					if (strcmp(prop->name, "testcase-alias") == 0) {
> +						np = of_find_node_by_path(temp->full_name);
>  						of_remove_property(np, prop);
> +					}
>  				}
>  			}
> +			else
> +				of_detach_node(temp);
>  		}
> -		last_node_index--;
>  	}
>  }
>  
> @@ -865,6 +857,7 @@ static int __init of_selftest(void)
>  
>  	/* adding data for selftest */
>  	res = selftest_data_add();
> +
>  	if (res)
>  		return res;
>  
> @@ -891,7 +884,6 @@ static int __init of_selftest(void)
>  
>  	/* removing selftest data from live tree */
>  	selftest_data_remove();
> -
>  	/* Double check linkage after removing testcase data */
>  	of_selftest_check_tree_linkage();
>  
> diff --git a/include/linux/of.h b/include/linux/of.h
> index 6545e7a..84c708c 100644
> --- a/include/linux/of.h
> +++ b/include/linux/of.h
> @@ -53,10 +53,10 @@ struct device_node {
>  	struct	property *properties;
>  	struct	property *deadprops;	/* removed properties */
>  	struct	device_node *parent;
> -	struct	device_node *child;
> -	struct	device_node *sibling;
>  	struct	device_node *next;	/* next device of same type */
>  	struct	device_node *allnext;	/* next in list of all nodes */
> +	struct	list_head children;
> +	struct	list_head siblings;
>  	struct	kobject kobj;
>  	unsigned long _flags;
>  	void	*data;
> -- 
> 1.9.1
> 

--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] Patch to improve device tree structure

[Frank Rowand]

On 11/18/2014 7:10 AM, Grant Likely wrote:
> On Sun, 16 Nov 2014 20:52:56 -0800
> , Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>  wrote:
>> This patch improves the implementation of device tree structure.
>>
>> Traditional child and sibling linked list in device tree structure
>> is removed and is replaced by list_head (i.e. circular doubly linked
>>  list) already available in Linux kernel.
>>
>> Signed-off-by: Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
> 
> Hi Gaurav,
> 
> So, after you've done this work, I need to you rebase it (and of course
> it is non-trivial) onto linux-next. I've already got a patch queued up
> which gets rid of the of_allnodes/allnext list which will have conflicts
> with this patch.
> 
> I'll make comments below where still relevant.

Grant,

My first reaction to this patch was that moving to using struct list_head
made the code less readable plus increased the size of struct device_node.

I reworked the changes to drivers/of/base.c to see if I could make
it a little more readable.  And I see below that you also have some
suggestions that make it more readable.

Even after that, I'm still feeling that the gain of moving to a more
standard list data type might not be greater than the downsides in
terms of readability and space.  The current list implementation does
seem like a decent fit to the problem space.

</ opinion, take it for what it is worth >

-Frank


< snip - original patch, plus Grant's comments >

--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] Patch to improve device tree structure

[Grant Likely]

On Wed, Nov 19, 2014 at 1:37 AM, Frank Rowand <frowand.list-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
> On 11/18/2014 7:10 AM, Grant Likely wrote:
>> On Sun, 16 Nov 2014 20:52:56 -0800
>> , Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>>  wrote:
>>> This patch improves the implementation of device tree structure.
>>>
>>> Traditional child and sibling linked list in device tree structure
>>> is removed and is replaced by list_head (i.e. circular doubly linked
>>>  list) already available in Linux kernel.
>>>
>>> Signed-off-by: Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>>
>> Hi Gaurav,
>>
>> So, after you've done this work, I need to you rebase it (and of course
>> it is non-trivial) onto linux-next. I've already got a patch queued up
>> which gets rid of the of_allnodes/allnext list which will have conflicts
>> with this patch.
>>
>> I'll make comments below where still relevant.
>
> Grant,
>
> My first reaction to this patch was that moving to using struct list_head
> made the code less readable plus increased the size of struct device_node.
>
> I reworked the changes to drivers/of/base.c to see if I could make
> it a little more readable.  And I see below that you also have some
> suggestions that make it more readable.
>
> Even after that, I'm still feeling that the gain of moving to a more
> standard list data type might not be greater than the downsides in
> terms of readability and space.  The current list implementation does
> seem like a decent fit to the problem space.

Moving to list_head has a couple of nice benefits. The prime
motification is that using a standard list_head means that the OF code
can be migrated to use the standard rcu operations and get rid of manual
of_node_{get,put} management in the majority of code paths.

A second reason to do this is it becomes easy to add nodes to the end of
the list instead of the beginning. It's a small thing, but it makes
unflattening simpler.

I've also considered switching to a hlist_head/hlist_node to keep the
footprint the same.* With an hlist_head the cost is a wash, but looses
the ability to do O(1) addition to the end of the list.

* Gaurav's patch removes the *child and *sibling pointers, but doesn't
  remove the *next pointer which can also be dropped. So, three pointers
  get dropped from the structure. Using list_head adds 4 pointers (Net
  +1). hlist_head adds 3 (Net 0).

g.
--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] Patch to improve device tree structure

[Frank Rowand]

On 11/19/2014 5:56 AM, Grant Likely wrote:
> On Wed, Nov 19, 2014 at 1:37 AM, Frank Rowand <frowand.list-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
>> On 11/18/2014 7:10 AM, Grant Likely wrote:
>>> On Sun, 16 Nov 2014 20:52:56 -0800
>>> , Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>>>  wrote:
>>>> This patch improves the implementation of device tree structure.
>>>>
>>>> Traditional child and sibling linked list in device tree structure
>>>> is removed and is replaced by list_head (i.e. circular doubly linked
>>>>  list) already available in Linux kernel.
>>>>
>>>> Signed-off-by: Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>>>
>>> Hi Gaurav,
>>>
>>> So, after you've done this work, I need to you rebase it (and of course
>>> it is non-trivial) onto linux-next. I've already got a patch queued up
>>> which gets rid of the of_allnodes/allnext list which will have conflicts
>>> with this patch.
>>>
>>> I'll make comments below where still relevant.
>>
>> Grant,
>>
>> My first reaction to this patch was that moving to using struct list_head
>> made the code less readable plus increased the size of struct device_node.
>>
>> I reworked the changes to drivers/of/base.c to see if I could make
>> it a little more readable.  And I see below that you also have some
>> suggestions that make it more readable.
>>
>> Even after that, I'm still feeling that the gain of moving to a more
>> standard list data type might not be greater than the downsides in
>> terms of readability and space.  The current list implementation does
>> seem like a decent fit to the problem space.
> 
> Moving to list_head has a couple of nice benefits. The prime
> motification is that using a standard list_head means that the OF code
> can be migrated to use the standard rcu operations and get rid of manual
> of_node_{get,put} management in the majority of code paths.

Oh yeah, I remember you mentioning that before.  That is what was missing
from Gaurav's patch header, explaining the value of the change.  If this
is the end goal, then I think it would be valuable to add a second patch
to the series that shows what the actual changes for rcu will be so that
the cost vs benefit of the end result can be evaluated.


> A second reason to do this is it becomes easy to add nodes to the end of
> the list instead of the beginning. It's a small thing, but it makes
> unflattening simpler.

Not a big change.  In the unflatten_dt_node() part of the patch, the
result was 4 lines deleted, 3 lines added.  With my attached patch to
remove the next field, it would have been 8 lines deleted, 3 lines
added -- thus list_head is an even greater simplification.  But still
tiny.


> I've also considered switching to a hlist_head/hlist_node to keep the
> footprint the same.* With an hlist_head the cost is a wash, but looses
> the ability to do O(1) addition to the end of the list.
> 
> * Gaurav's patch removes the *child and *sibling pointers, but doesn't
>   remove the *next pointer which can also be dropped. So, three pointers
>   get dropped from the structure. Using list_head adds 4 pointers (Net
>   +1). hlist_head adds 3 (Net 0).

I include a patch below to also drop the *next pointer.  Not to actually
propose submitting the patch, but to suggest that Gaurav's patch should be
counted as a net of +2 pointers.  I expect that you will accept either a
list_head of an hlist_head patch, but if you do not then I will submit the
below patch to remove *next or a patch to rename *next to match the actual
usage of the field.

I still do not have a strong opinion, but I am still feeling that the gain
probably does not outweigh the cost.

-Frank

> 
> g.
> 

From: Frank Rowand <frank.rowand-/MT0OVThwyLZJqsBc5GL+g@public.gmane.org>

Decrease size of struct device_node by one pointer.
The pointer is only used during the unflattening of the
device tree at boot.

The cost of removing the pointer is chasing through the
sibling list to add new nodes instead of using the
cached 'last_child'.  The cost is expected to be in the
noise level.

Signed-off-by: Frank Rowand <frank.rowand-/MT0OVThwyLZJqsBc5GL+g@public.gmane.org>
---
 drivers/of/fdt.c   |   14 +++++++++-----
 include/linux/of.h |    1 -
 2 files changed, 9 insertions(+), 6 deletions(-)

Index: b/include/linux/of.h
===================================================================
--- a/include/linux/of.h
+++ b/include/linux/of.h
@@ -55,7 +55,6 @@ struct device_node {
 	struct	device_node *parent;
 	struct	device_node *child;
 	struct	device_node *sibling;
-	struct	device_node *next;	/* next device of same type */
 	struct	device_node *allnext;	/* next in list of all nodes */
 	struct	kobject kobj;
 	unsigned long _flags;
Index: b/drivers/of/fdt.c
===================================================================
--- a/drivers/of/fdt.c
+++ b/drivers/of/fdt.c
@@ -226,12 +226,16 @@ static void * unflatten_dt_node(void *bl
 		*allnextpp = &np->allnext;
 		if (dad != NULL) {
 			np->parent = dad;
-			/* we temporarily use the next field as `last_child'*/
-			if (dad->next == NULL)
+			if (dad->child == NULL)
 				dad->child = np;
-			else
-				dad->next->sibling = np;
-			dad->next = np;
+			else {
+				struct device_node *next;
+
+				next = dad->child;
+				while (next->sibling)
+					next = next->sibling;
+				next->sibling = np;
+			}
 		}
 	}
 	/* process properties */
--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] Patch to improve device tree structure

[Frank Rowand]

On 11/19/2014 11:30 AM, Frank Rowand wrote:
> On 11/19/2014 5:56 AM, Grant Likely wrote:
>> On Wed, Nov 19, 2014 at 1:37 AM, Frank Rowand <frowand.list-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:

< snip >

> I include a patch below to also drop the *next pointer.  Not to actually
> propose submitting the patch, but to suggest that Gaurav's patch should be
> counted as a net of +2 pointers.  I expect that you will accept either a
> list_head of an hlist_head patch, but if you do not then I will submit the

  list_head _or_ and hlist_head

stupid typos...

> below patch to remove *next or a patch to rename *next to match the actual
> usage of the field.
> 
> I still do not have a strong opinion, but I am still feeling that the gain
> probably does not outweigh the cost.
> 
> -Frank

--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] Patch to improve device tree structure

[Frank Rowand]

On 11/19/2014 12:03 PM, Frank Rowand wrote:
> On 11/19/2014 11:30 AM, Frank Rowand wrote:
>> On 11/19/2014 5:56 AM, Grant Likely wrote:
>>> On Wed, Nov 19, 2014 at 1:37 AM, Frank Rowand <frowand.list-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
> 
> < snip >
> 
>> I include a patch below to also drop the *next pointer.  Not to actually
>> propose submitting the patch, but to suggest that Gaurav's patch should be
>> counted as a net of +2 pointers.  I expect that you will accept either a
>> list_head of an hlist_head patch, but if you do not then I will submit the
> 
>   list_head _or_ and hlist_head

    list_head _or_ an hlist_head

darn it!

> 
> stupid typos...
> 
>> below patch to remove *next or a patch to rename *next to match the actual
>> usage of the field.
>>
>> I still do not have a strong opinion, but I am still feeling that the gain
>> probably does not outweigh the cost.
>>
>> -Frank
> 

--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] Patch to improve device tree structure

[Gaurav Minocha]

On Tue, Nov 18, 2014 at 7:10 AM, Grant Likely <grant.likely-QSEj5FYQhm4dnm+yROfE0A@public.gmane.org> wrote:
> On Sun, 16 Nov 2014 20:52:56 -0800
> , Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>  wrote:
>> This patch improves the implementation of device tree structure.
>>
>> Traditional child and sibling linked list in device tree structure
>> is removed and is replaced by list_head (i.e. circular doubly linked
>>  list) already available in Linux kernel.
>>
>> Signed-off-by: Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>
> Hi Gaurav,
>
> So, after you've done this work, I need to you rebase it (and of course
> it is non-trivial) onto linux-next. I've already got a patch queued up
> which gets rid of the of_allnodes/allnext list which will have conflicts
> with this patch.
>

I am using http://git.kernel.org/pub/scm/linux/kernel/git/glikely/linux.git
There is no branch linux-next in it. Also, I believe http://git.secretlab.ca/
is not up yet. Please correct.

> I'll make comments below where still relevant.
>
>> ---
>>  drivers/of/base.c     |  36 ++++++++++----
>>  drivers/of/dynamic.c  |  18 ++-----
>>  drivers/of/fdt.c      |   7 ++-
>>  drivers/of/selftest.c | 130 +++++++++++++++++++++++---------------------------
>>  include/linux/of.h    |   4 +-
>>  5 files changed, 97 insertions(+), 98 deletions(-)
>>
>> diff --git a/drivers/of/base.c b/drivers/of/base.c
>> index 2305dc0..7acaeca 100644
>> --- a/drivers/of/base.c
>> +++ b/drivers/of/base.c
>> @@ -603,16 +603,25 @@ EXPORT_SYMBOL(of_get_next_parent);
>>  static struct device_node *__of_get_next_child(const struct device_node *node,
>>                                               struct device_node *prev)
>>  {
>> -     struct device_node *next;
>> +     struct device_node *next = NULL, *np;
>> +     struct list_head *pos;
>> +     int found = 0;
>>
>>       if (!node)
>>               return NULL;
>>
>> -     next = prev ? prev->sibling : node->child;
>> -     for (; next; next = next->sibling)
>> -             if (of_node_get(next))
>> -                     break;
>> +     // move through the children list, and find the next node
>> +     list_for_each(pos, &node->children) {
>> +             np = list_entry(pos, struct device_node, siblings);
>> +             if ((!prev || (found == 1)) && of_node_get(np)) {
>> +                             next = np;
>> +                             break;
>> +             }
>> +             if (prev && strcmp(np->full_name, prev->full_name) == 0)
>> +                     found = 1;
>
> What is this 'found' stuff about? Why is this in the loop?

I think with your suggestions below, it will definitely change.

Considering the fact that it is a doubly linked list. First, I try to locate
the pre node in the list. If found, then only I call of_node_get() on the next
node, and if successful I break. I used found in the loop so that I do not
have to manually check the next node is head or not.

I can follow another approach, by directly getting the next entry and
failing it if it is the head node.

>
>> +     }
>>       of_node_put(prev);
>
> Most of this code can be eliminated by using list_for_each_entry().
> Actually, the use of a loop here in the original code is a little bit
> goofy simply because it never actually loops. It always exits on the
> first iteration, but it does conveniently calculate the next entry in
> the list. The thing to do here is take inspiration from the
> list_for_each_entry() implementation and do the following:
>
>         if (!prev) {
>                 next = list_first_entry_or_null(&node->children, struct device_node, siblings);
>         } else if (prev->siblings.next != &node->children)
>                 next = list_next_entry(prev, siblings);
>         } else {
>                 next = NULL;
>         }
>
>> +
>>       return next;
>>  }
>>  #define __for_each_child_of_node(parent, child) \
>> @@ -651,22 +660,29 @@ EXPORT_SYMBOL(of_get_next_child);
>>  struct device_node *of_get_next_available_child(const struct device_node *node,
>>       struct device_node *prev)
>>  {
>> -     struct device_node *next;
>> +     struct device_node *next = NULL, *np;
>> +     struct list_head *pos;
>>       unsigned long flags;
>> +     int found = 0;
>>
>>       if (!node)
>>               return NULL;
>>
>>       raw_spin_lock_irqsave(&devtree_lock, flags);
>> -     next = prev ? prev->sibling : node->child;
>> -     for (; next; next = next->sibling) {
>> -             if (!__of_device_is_available(next))
>> +     list_for_each(pos, &node->children) {
>
> Use list_for_each_entry_continue(), but there will be a bit of fiddling
> to make sure the first entry in the list is handled correctly. You can
> handle this by using list_entry on the &node->children list, but be
> careful to never actually dereference that pointer.
>
>> +             np = list_entry(pos, struct device_node, siblings);
>> +             if (!__of_device_is_available(np))
>>                       continue;
>> -             if (of_node_get(next))
>> +             if ((!prev || (found == 1)) && of_node_get(np)) {
>> +                     next = np;
>>                       break;
>> +             }
>> +             if (prev && strcmp(np->full_name, prev->full_name) == 0)
>> +                     found = 1;
>>       }
>>       of_node_put(prev);
>>       raw_spin_unlock_irqrestore(&devtree_lock, flags);
>> +
>>       return next;
>>  }
>>  EXPORT_SYMBOL(of_get_next_available_child);
>> diff --git a/drivers/of/dynamic.c b/drivers/of/dynamic.c
>> index f297891..3ffc726 100644
>> --- a/drivers/of/dynamic.c
>> +++ b/drivers/of/dynamic.c
>> @@ -115,11 +115,12 @@ void __of_attach_node(struct device_node *np)
>>               phandle = __of_get_property(np, "ibm,phandle", &sz);
>>       np->phandle = (phandle && (sz >= 4)) ? be32_to_cpup(phandle) : 0;
>>
>> -     np->child = NULL;
>> -     np->sibling = np->parent->child;
>> +     INIT_LIST_HEAD(&np->siblings);
>> +     INIT_LIST_HEAD(&np->children);
>> +     list_add_tail(&(np->siblings), &(np->parent->children));
>> +
>>       np->allnext = np->parent->allnext;
>>       np->parent->allnext = np;
>> -     np->parent->child = np;
>>       of_node_clear_flag(np, OF_DETACHED);
>>  }
>>
>> @@ -165,16 +166,7 @@ void __of_detach_node(struct device_node *np)
>>               prev->allnext = np->allnext;
>>       }
>>
>> -     if (parent->child == np)
>> -             parent->child = np->sibling;
>> -     else {
>> -             struct device_node *prevsib;
>> -             for (prevsib = np->parent->child;
>> -                  prevsib->sibling != np;
>> -                  prevsib = prevsib->sibling)
>> -                     ;
>> -             prevsib->sibling = np->sibling;
>> -     }
>> +     list_del(&np->siblings);
>>
>>       of_node_set_flag(np, OF_DETACHED);
>>  }
>> diff --git a/drivers/of/fdt.c b/drivers/of/fdt.c
>> index d1ffca8..4cf2356 100644
>> --- a/drivers/of/fdt.c
>> +++ b/drivers/of/fdt.c
>> @@ -224,13 +224,12 @@ static void * unflatten_dt_node(void *blob,
>>               prev_pp = &np->properties;
>>               **allnextpp = np;
>>               *allnextpp = &np->allnext;
>> +             INIT_LIST_HEAD(&np->siblings);
>> +             INIT_LIST_HEAD(&np->children);
>>               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;
>> +                     list_add_tail(&(np->siblings), &(dad->children));
>>                       dad->next = np;
>>               }
>>       }
>> diff --git a/drivers/of/selftest.c b/drivers/of/selftest.c
>> index 7800127..8ec8a22 100644
>> --- a/drivers/of/selftest.c
>> +++ b/drivers/of/selftest.c
>> @@ -25,10 +25,11 @@ static struct selftest_results {
>>       int failed;
>>  } selftest_results;
>>
>> -#define NO_OF_NODES 3
>> -static struct device_node *nodes[NO_OF_NODES];
>> -static int last_node_index;
>> +#define MAX_NODES 50
>> +
>> +static int no_of_nodes;
>>  static bool selftest_live_tree;
>> +static struct device_node* nodes[MAX_NODES];
>
> I think it's time to rework this structure. Instead of a static list,
> the code should figure out how many entries it needs and then kzalloc()
> the region.

Ok.

>
>>
>>  #define selftest(result, fmt, ...) { \
>>       if (!(result)) { \
>> @@ -417,7 +418,6 @@ static void __init of_selftest_changeset(void)
>>       n1->parent = parent;
>>       n2->parent = parent;
>>       n21->parent = n2;
>> -     n2->child = n21;
>>       ppremove = of_find_property(parent, "prop-remove", NULL);
>>       selftest(ppremove, "failed to find removal prop");
>>
>> @@ -713,44 +713,34 @@ static void update_node_properties(struct device_node *np,
>>               child->parent = dup;
>>  }
>>
>> -/**
>> - *   attach_node_and_children - attaches nodes
>> - *   and its children to live tree
>> - *
>> - *   @np:    Node to attach to live tree
>> - */
>> -static int attach_node_and_children(struct device_node *np)
>> -{
>> -     struct device_node *next, *root = np, *dup;
>>
>> -     /* skip root node */
>> -     np = np->child;
>> -     /* storing a copy in temporary node */
>> -     dup = np;
>> +static void populate_node_list(struct device_node *np)
>> +{
>> +     struct list_head *pos;
>>
>> -     while (dup) {
>> -             if (WARN_ON(last_node_index >= NO_OF_NODES))
>> -                     return -EINVAL;
>> -             nodes[last_node_index++] = dup;
>> -             dup = dup->sibling;
>> +     list_for_each(pos, &np->children) {
>> +             nodes[no_of_nodes] = list_entry(pos, struct device_node, siblings);
>> +             populate_node_list(nodes[no_of_nodes++]);
>>       }
>> -     dup = NULL;
>> +}
>>
>> -     while (np) {
>> -             next = np->allnext;
>> -             dup = of_find_node_by_path(np->full_name);
>> +static void attach_node_and_children(struct device_node *np)
>> +{
>> +     struct device_node *root = np, *dup, *temp;
>> +     int i;
>> +
>> +     populate_node_list(np);
>> +
>> +     for (i = 0; i < no_of_nodes && nodes[i]; i++) {
>> +             temp = nodes[i];
>> +             if (temp->parent == root)
>> +                     temp->parent = of_allnodes;
>> +             dup = of_find_node_by_path(temp->full_name);
>>               if (dup)
>> -                     update_node_properties(np, dup);
>> -             else {
>> -                     np->child = NULL;
>> -                     if (np->parent == root)
>> -                             np->parent = of_allnodes;
>> -                     of_attach_node(np);
>> -             }
>> -             np = next;
>> +                     update_node_properties(temp, dup);
>> +             else
>> +                     of_attach_node(temp);
>>       }
>> -
>> -     return 0;
>>  }
>>
>>  /**
>> @@ -764,7 +754,8 @@ static int __init selftest_data_add(void)
>>       extern uint8_t __dtb_testcases_begin[];
>>       extern uint8_t __dtb_testcases_end[];
>>       const int size = __dtb_testcases_end - __dtb_testcases_begin;
>> -     int rc;
>> +     struct list_head *pos;
>> +     int rc, i = 0;
>>
>>       if (!size) {
>>               pr_warn("%s: No testcase data to attach; not running tests\n",
>> @@ -796,65 +787,66 @@ static int __init selftest_data_add(void)
>>               /* enabling flag for removing nodes */
>>               selftest_live_tree = true;
>>               of_allnodes = selftest_data_node;
>> +             populate_node_list(selftest_data_node);
>> +
>> +             // attach the root node
>> +             __of_attach_node_sysfs(selftest_data_node);
>> +
>> +             while (i < no_of_nodes && nodes[i])
>> +                     __of_attach_node_sysfs(nodes[i++]);
>>
>> -             for_each_of_allnodes(np)
>> -                     __of_attach_node_sysfs(np);
>>               of_aliases = of_find_node_by_path("/aliases");
>>               of_chosen = of_find_node_by_path("/chosen");
>>               return 0;
>>       }
>>
>> +     list_for_each(pos, &selftest_data_node->children) {
>> +             np = list_entry(pos, struct device_node, siblings);
>> +             np->parent = of_allnodes;
>> +     }
>> +
>> +
>>       /* attach the sub-tree to live tree */
>> -     return attach_node_and_children(selftest_data_node);
>> -}
>> +     attach_node_and_children(selftest_data_node);
>>
>> -/**
>> - *   detach_node_and_children - detaches node
>> - *   and its children from live tree
>> - *
>> - *   @np:    Node to detach from live tree
>> - */
>> -static void detach_node_and_children(struct device_node *np)
>> -{
>> -     while (np->child)
>> -             detach_node_and_children(np->child);
>> -     of_detach_node(np);
>> +     return 0;
>>  }
>>
>> -/**
>> - *   selftest_data_remove - removes the selftest data
>> - *   nodes from the live tree
>> - */
>>  static void selftest_data_remove(void)
>>  {
>> -     struct device_node *np;
>>       struct property *prop;
>> +     struct device_node *np, *temp;
>> +     int i = no_of_nodes;
>>
>>       if (selftest_live_tree) {
>>               of_node_put(of_aliases);
>>               of_node_put(of_chosen);
>>               of_aliases = NULL;
>>               of_chosen = NULL;
>> -             for_each_child_of_node(of_allnodes, np)
>> -                     detach_node_and_children(np);
>> +             while (i >= 0) {
>> +                     temp = nodes[i--];
>> +                     if (temp)
>> +                             of_detach_node(temp);
>> +             }
>>               __of_detach_node_sysfs(of_allnodes);
>>               of_allnodes = NULL;
>>               return;
>>       }
>>
>> -     while (last_node_index >= 0) {
>> -             if (nodes[last_node_index]) {
>> -                     np = of_find_node_by_path(nodes[last_node_index]->full_name);
>> -                     if (strcmp(np->full_name, "/aliases") != 0) {
>> -                             detach_node_and_children(np);
>> -                     } else {
>> -                             for_each_property_of_node(np, prop) {
>> -                                     if (strcmp(prop->name, "testcase-alias") == 0)
>> +     while (i >= 0) {
>> +             temp = nodes[i--];
>> +             if (temp) {
>> +                     if (strcmp(temp->full_name, "/aliases") == 0) {
>> +                             for_each_property_of_node(temp, prop) {
>> +                                     if (strcmp(prop->name, "testcase-alias") == 0) {
>> +                                             np = of_find_node_by_path(temp->full_name);
>>                                               of_remove_property(np, prop);
>> +                                     }
>>                               }
>>                       }
>> +                     else
>> +                             of_detach_node(temp);
>>               }
>> -             last_node_index--;
>>       }
>>  }
>>
>> @@ -865,6 +857,7 @@ static int __init of_selftest(void)
>>
>>       /* adding data for selftest */
>>       res = selftest_data_add();
>> +
>>       if (res)
>>               return res;
>>
>> @@ -891,7 +884,6 @@ static int __init of_selftest(void)
>>
>>       /* removing selftest data from live tree */
>>       selftest_data_remove();
>> -
>>       /* Double check linkage after removing testcase data */
>>       of_selftest_check_tree_linkage();
>>
>> diff --git a/include/linux/of.h b/include/linux/of.h
>> index 6545e7a..84c708c 100644
>> --- a/include/linux/of.h
>> +++ b/include/linux/of.h
>> @@ -53,10 +53,10 @@ struct device_node {
>>       struct  property *properties;
>>       struct  property *deadprops;    /* removed properties */
>>       struct  device_node *parent;
>> -     struct  device_node *child;
>> -     struct  device_node *sibling;
>>       struct  device_node *next;      /* next device of same type */
>>       struct  device_node *allnext;   /* next in list of all nodes */
>> +     struct  list_head children;
>> +     struct  list_head siblings;
>>       struct  kobject kobj;
>>       unsigned long _flags;
>>       void    *data;
>> --
>> 1.9.1
>>
>
--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] Patch to improve device tree structure

[Gaurav Minocha]

On Sun, Nov 23, 2014 at 5:22 PM, Gaurav Minocha
<gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
> On Tue, Nov 18, 2014 at 7:10 AM, Grant Likely <grant.likely-QSEj5FYQhm4dnm+yROfE0A@public.gmane.org> wrote:
>> On Sun, 16 Nov 2014 20:52:56 -0800
>> , Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>>  wrote:
>>> This patch improves the implementation of device tree structure.
>>>
>>> Traditional child and sibling linked list in device tree structure
>>> is removed and is replaced by list_head (i.e. circular doubly linked
>>>  list) already available in Linux kernel.
>>>
>>> Signed-off-by: Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>>
>> Hi Gaurav,
>>
>> So, after you've done this work, I need to you rebase it (and of course
>> it is non-trivial) onto linux-next. I've already got a patch queued up
>> which gets rid of the of_allnodes/allnext list which will have conflicts
>> with this patch.
>>
>
> I am using http://git.kernel.org/pub/scm/linux/kernel/git/glikely/linux.git
> There is no branch linux-next in it. Also, I believe http://git.secretlab.ca/
> is not up yet. Please correct.
>

My bad! I can see your commits present in the next branch. I will send you a
revised patch soon. Thanks!

>> I'll make comments below where still relevant.
>>
>>> ---
>>>  drivers/of/base.c     |  36 ++++++++++----
>>>  drivers/of/dynamic.c  |  18 ++-----
>>>  drivers/of/fdt.c      |   7 ++-
>>>  drivers/of/selftest.c | 130 +++++++++++++++++++++++---------------------------
>>>  include/linux/of.h    |   4 +-
>>>  5 files changed, 97 insertions(+), 98 deletions(-)
>>>
>>> diff --git a/drivers/of/base.c b/drivers/of/base.c
>>> index 2305dc0..7acaeca 100644
>>> --- a/drivers/of/base.c
>>> +++ b/drivers/of/base.c
>>> @@ -603,16 +603,25 @@ EXPORT_SYMBOL(of_get_next_parent);
>>>  static struct device_node *__of_get_next_child(const struct device_node *node,
>>>                                               struct device_node *prev)
>>>  {
>>> -     struct device_node *next;
>>> +     struct device_node *next = NULL, *np;
>>> +     struct list_head *pos;
>>> +     int found = 0;
>>>
>>>       if (!node)
>>>               return NULL;
>>>
>>> -     next = prev ? prev->sibling : node->child;
>>> -     for (; next; next = next->sibling)
>>> -             if (of_node_get(next))
>>> -                     break;
>>> +     // move through the children list, and find the next node
>>> +     list_for_each(pos, &node->children) {
>>> +             np = list_entry(pos, struct device_node, siblings);
>>> +             if ((!prev || (found == 1)) && of_node_get(np)) {
>>> +                             next = np;
>>> +                             break;
>>> +             }
>>> +             if (prev && strcmp(np->full_name, prev->full_name) == 0)
>>> +                     found = 1;
>>
>> What is this 'found' stuff about? Why is this in the loop?
>
> I think with your suggestions below, it will definitely change.
>
> Considering the fact that it is a doubly linked list. First, I try to locate
> the pre node in the list. If found, then only I call of_node_get() on the next
> node, and if successful I break. I used found in the loop so that I do not
> have to manually check the next node is head or not.
>
> I can follow another approach, by directly getting the next entry and
> failing it if it is the head node.
>
>>
>>> +     }
>>>       of_node_put(prev);
>>
>> Most of this code can be eliminated by using list_for_each_entry().
>> Actually, the use of a loop here in the original code is a little bit
>> goofy simply because it never actually loops. It always exits on the
>> first iteration, but it does conveniently calculate the next entry in
>> the list. The thing to do here is take inspiration from the
>> list_for_each_entry() implementation and do the following:
>>
>>         if (!prev) {
>>                 next = list_first_entry_or_null(&node->children, struct device_node, siblings);
>>         } else if (prev->siblings.next != &node->children)
>>                 next = list_next_entry(prev, siblings);
>>         } else {
>>                 next = NULL;
>>         }
>>
>>> +
>>>       return next;
>>>  }
>>>  #define __for_each_child_of_node(parent, child) \
>>> @@ -651,22 +660,29 @@ EXPORT_SYMBOL(of_get_next_child);
>>>  struct device_node *of_get_next_available_child(const struct device_node *node,
>>>       struct device_node *prev)
>>>  {
>>> -     struct device_node *next;
>>> +     struct device_node *next = NULL, *np;
>>> +     struct list_head *pos;
>>>       unsigned long flags;
>>> +     int found = 0;
>>>
>>>       if (!node)
>>>               return NULL;
>>>
>>>       raw_spin_lock_irqsave(&devtree_lock, flags);
>>> -     next = prev ? prev->sibling : node->child;
>>> -     for (; next; next = next->sibling) {
>>> -             if (!__of_device_is_available(next))
>>> +     list_for_each(pos, &node->children) {
>>
>> Use list_for_each_entry_continue(), but there will be a bit of fiddling
>> to make sure the first entry in the list is handled correctly. You can
>> handle this by using list_entry on the &node->children list, but be
>> careful to never actually dereference that pointer.
>>
>>> +             np = list_entry(pos, struct device_node, siblings);
>>> +             if (!__of_device_is_available(np))
>>>                       continue;
>>> -             if (of_node_get(next))
>>> +             if ((!prev || (found == 1)) && of_node_get(np)) {
>>> +                     next = np;
>>>                       break;
>>> +             }
>>> +             if (prev && strcmp(np->full_name, prev->full_name) == 0)
>>> +                     found = 1;
>>>       }
>>>       of_node_put(prev);
>>>       raw_spin_unlock_irqrestore(&devtree_lock, flags);
>>> +
>>>       return next;
>>>  }
>>>  EXPORT_SYMBOL(of_get_next_available_child);
>>> diff --git a/drivers/of/dynamic.c b/drivers/of/dynamic.c
>>> index f297891..3ffc726 100644
>>> --- a/drivers/of/dynamic.c
>>> +++ b/drivers/of/dynamic.c
>>> @@ -115,11 +115,12 @@ void __of_attach_node(struct device_node *np)
>>>               phandle = __of_get_property(np, "ibm,phandle", &sz);
>>>       np->phandle = (phandle && (sz >= 4)) ? be32_to_cpup(phandle) : 0;
>>>
>>> -     np->child = NULL;
>>> -     np->sibling = np->parent->child;
>>> +     INIT_LIST_HEAD(&np->siblings);
>>> +     INIT_LIST_HEAD(&np->children);
>>> +     list_add_tail(&(np->siblings), &(np->parent->children));
>>> +
>>>       np->allnext = np->parent->allnext;
>>>       np->parent->allnext = np;
>>> -     np->parent->child = np;
>>>       of_node_clear_flag(np, OF_DETACHED);
>>>  }
>>>
>>> @@ -165,16 +166,7 @@ void __of_detach_node(struct device_node *np)
>>>               prev->allnext = np->allnext;
>>>       }
>>>
>>> -     if (parent->child == np)
>>> -             parent->child = np->sibling;
>>> -     else {
>>> -             struct device_node *prevsib;
>>> -             for (prevsib = np->parent->child;
>>> -                  prevsib->sibling != np;
>>> -                  prevsib = prevsib->sibling)
>>> -                     ;
>>> -             prevsib->sibling = np->sibling;
>>> -     }
>>> +     list_del(&np->siblings);
>>>
>>>       of_node_set_flag(np, OF_DETACHED);
>>>  }
>>> diff --git a/drivers/of/fdt.c b/drivers/of/fdt.c
>>> index d1ffca8..4cf2356 100644
>>> --- a/drivers/of/fdt.c
>>> +++ b/drivers/of/fdt.c
>>> @@ -224,13 +224,12 @@ static void * unflatten_dt_node(void *blob,
>>>               prev_pp = &np->properties;
>>>               **allnextpp = np;
>>>               *allnextpp = &np->allnext;
>>> +             INIT_LIST_HEAD(&np->siblings);
>>> +             INIT_LIST_HEAD(&np->children);
>>>               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;
>>> +                     list_add_tail(&(np->siblings), &(dad->children));
>>>                       dad->next = np;
>>>               }
>>>       }
>>> diff --git a/drivers/of/selftest.c b/drivers/of/selftest.c
>>> index 7800127..8ec8a22 100644
>>> --- a/drivers/of/selftest.c
>>> +++ b/drivers/of/selftest.c
>>> @@ -25,10 +25,11 @@ static struct selftest_results {
>>>       int failed;
>>>  } selftest_results;
>>>
>>> -#define NO_OF_NODES 3
>>> -static struct device_node *nodes[NO_OF_NODES];
>>> -static int last_node_index;
>>> +#define MAX_NODES 50
>>> +
>>> +static int no_of_nodes;
>>>  static bool selftest_live_tree;
>>> +static struct device_node* nodes[MAX_NODES];
>>
>> I think it's time to rework this structure. Instead of a static list,
>> the code should figure out how many entries it needs and then kzalloc()
>> the region.
>
> Ok.
>
>>
>>>
>>>  #define selftest(result, fmt, ...) { \
>>>       if (!(result)) { \
>>> @@ -417,7 +418,6 @@ static void __init of_selftest_changeset(void)
>>>       n1->parent = parent;
>>>       n2->parent = parent;
>>>       n21->parent = n2;
>>> -     n2->child = n21;
>>>       ppremove = of_find_property(parent, "prop-remove", NULL);
>>>       selftest(ppremove, "failed to find removal prop");
>>>
>>> @@ -713,44 +713,34 @@ static void update_node_properties(struct device_node *np,
>>>               child->parent = dup;
>>>  }
>>>
>>> -/**
>>> - *   attach_node_and_children - attaches nodes
>>> - *   and its children to live tree
>>> - *
>>> - *   @np:    Node to attach to live tree
>>> - */
>>> -static int attach_node_and_children(struct device_node *np)
>>> -{
>>> -     struct device_node *next, *root = np, *dup;
>>>
>>> -     /* skip root node */
>>> -     np = np->child;
>>> -     /* storing a copy in temporary node */
>>> -     dup = np;
>>> +static void populate_node_list(struct device_node *np)
>>> +{
>>> +     struct list_head *pos;
>>>
>>> -     while (dup) {
>>> -             if (WARN_ON(last_node_index >= NO_OF_NODES))
>>> -                     return -EINVAL;
>>> -             nodes[last_node_index++] = dup;
>>> -             dup = dup->sibling;
>>> +     list_for_each(pos, &np->children) {
>>> +             nodes[no_of_nodes] = list_entry(pos, struct device_node, siblings);
>>> +             populate_node_list(nodes[no_of_nodes++]);
>>>       }
>>> -     dup = NULL;
>>> +}
>>>
>>> -     while (np) {
>>> -             next = np->allnext;
>>> -             dup = of_find_node_by_path(np->full_name);
>>> +static void attach_node_and_children(struct device_node *np)
>>> +{
>>> +     struct device_node *root = np, *dup, *temp;
>>> +     int i;
>>> +
>>> +     populate_node_list(np);
>>> +
>>> +     for (i = 0; i < no_of_nodes && nodes[i]; i++) {
>>> +             temp = nodes[i];
>>> +             if (temp->parent == root)
>>> +                     temp->parent = of_allnodes;
>>> +             dup = of_find_node_by_path(temp->full_name);
>>>               if (dup)
>>> -                     update_node_properties(np, dup);
>>> -             else {
>>> -                     np->child = NULL;
>>> -                     if (np->parent == root)
>>> -                             np->parent = of_allnodes;
>>> -                     of_attach_node(np);
>>> -             }
>>> -             np = next;
>>> +                     update_node_properties(temp, dup);
>>> +             else
>>> +                     of_attach_node(temp);
>>>       }
>>> -
>>> -     return 0;
>>>  }
>>>
>>>  /**
>>> @@ -764,7 +754,8 @@ static int __init selftest_data_add(void)
>>>       extern uint8_t __dtb_testcases_begin[];
>>>       extern uint8_t __dtb_testcases_end[];
>>>       const int size = __dtb_testcases_end - __dtb_testcases_begin;
>>> -     int rc;
>>> +     struct list_head *pos;
>>> +     int rc, i = 0;
>>>
>>>       if (!size) {
>>>               pr_warn("%s: No testcase data to attach; not running tests\n",
>>> @@ -796,65 +787,66 @@ static int __init selftest_data_add(void)
>>>               /* enabling flag for removing nodes */
>>>               selftest_live_tree = true;
>>>               of_allnodes = selftest_data_node;
>>> +             populate_node_list(selftest_data_node);
>>> +
>>> +             // attach the root node
>>> +             __of_attach_node_sysfs(selftest_data_node);
>>> +
>>> +             while (i < no_of_nodes && nodes[i])
>>> +                     __of_attach_node_sysfs(nodes[i++]);
>>>
>>> -             for_each_of_allnodes(np)
>>> -                     __of_attach_node_sysfs(np);
>>>               of_aliases = of_find_node_by_path("/aliases");
>>>               of_chosen = of_find_node_by_path("/chosen");
>>>               return 0;
>>>       }
>>>
>>> +     list_for_each(pos, &selftest_data_node->children) {
>>> +             np = list_entry(pos, struct device_node, siblings);
>>> +             np->parent = of_allnodes;
>>> +     }
>>> +
>>> +
>>>       /* attach the sub-tree to live tree */
>>> -     return attach_node_and_children(selftest_data_node);
>>> -}
>>> +     attach_node_and_children(selftest_data_node);
>>>
>>> -/**
>>> - *   detach_node_and_children - detaches node
>>> - *   and its children from live tree
>>> - *
>>> - *   @np:    Node to detach from live tree
>>> - */
>>> -static void detach_node_and_children(struct device_node *np)
>>> -{
>>> -     while (np->child)
>>> -             detach_node_and_children(np->child);
>>> -     of_detach_node(np);
>>> +     return 0;
>>>  }
>>>
>>> -/**
>>> - *   selftest_data_remove - removes the selftest data
>>> - *   nodes from the live tree
>>> - */
>>>  static void selftest_data_remove(void)
>>>  {
>>> -     struct device_node *np;
>>>       struct property *prop;
>>> +     struct device_node *np, *temp;
>>> +     int i = no_of_nodes;
>>>
>>>       if (selftest_live_tree) {
>>>               of_node_put(of_aliases);
>>>               of_node_put(of_chosen);
>>>               of_aliases = NULL;
>>>               of_chosen = NULL;
>>> -             for_each_child_of_node(of_allnodes, np)
>>> -                     detach_node_and_children(np);
>>> +             while (i >= 0) {
>>> +                     temp = nodes[i--];
>>> +                     if (temp)
>>> +                             of_detach_node(temp);
>>> +             }
>>>               __of_detach_node_sysfs(of_allnodes);
>>>               of_allnodes = NULL;
>>>               return;
>>>       }
>>>
>>> -     while (last_node_index >= 0) {
>>> -             if (nodes[last_node_index]) {
>>> -                     np = of_find_node_by_path(nodes[last_node_index]->full_name);
>>> -                     if (strcmp(np->full_name, "/aliases") != 0) {
>>> -                             detach_node_and_children(np);
>>> -                     } else {
>>> -                             for_each_property_of_node(np, prop) {
>>> -                                     if (strcmp(prop->name, "testcase-alias") == 0)
>>> +     while (i >= 0) {
>>> +             temp = nodes[i--];
>>> +             if (temp) {
>>> +                     if (strcmp(temp->full_name, "/aliases") == 0) {
>>> +                             for_each_property_of_node(temp, prop) {
>>> +                                     if (strcmp(prop->name, "testcase-alias") == 0) {
>>> +                                             np = of_find_node_by_path(temp->full_name);
>>>                                               of_remove_property(np, prop);
>>> +                                     }
>>>                               }
>>>                       }
>>> +                     else
>>> +                             of_detach_node(temp);
>>>               }
>>> -             last_node_index--;
>>>       }
>>>  }
>>>
>>> @@ -865,6 +857,7 @@ static int __init of_selftest(void)
>>>
>>>       /* adding data for selftest */
>>>       res = selftest_data_add();
>>> +
>>>       if (res)
>>>               return res;
>>>
>>> @@ -891,7 +884,6 @@ static int __init of_selftest(void)
>>>
>>>       /* removing selftest data from live tree */
>>>       selftest_data_remove();
>>> -
>>>       /* Double check linkage after removing testcase data */
>>>       of_selftest_check_tree_linkage();
>>>
>>> diff --git a/include/linux/of.h b/include/linux/of.h
>>> index 6545e7a..84c708c 100644
>>> --- a/include/linux/of.h
>>> +++ b/include/linux/of.h
>>> @@ -53,10 +53,10 @@ struct device_node {
>>>       struct  property *properties;
>>>       struct  property *deadprops;    /* removed properties */
>>>       struct  device_node *parent;
>>> -     struct  device_node *child;
>>> -     struct  device_node *sibling;
>>>       struct  device_node *next;      /* next device of same type */
>>>       struct  device_node *allnext;   /* next in list of all nodes */
>>> +     struct  list_head children;
>>> +     struct  list_head siblings;
>>>       struct  kobject kobj;
>>>       unsigned long _flags;
>>>       void    *data;
>>> --
>>> 1.9.1
>>>
>>
--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] Patch to improve device tree structure

[Grant Likely]

On Sun, 23 Nov 2014 17:22:22 -0800
, Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
 wrote:
> On Tue, Nov 18, 2014 at 7:10 AM, Grant Likely <grant.likely-QSEj5FYQhm4dnm+yROfE0A@public.gmane.org> wrote:
> > On Sun, 16 Nov 2014 20:52:56 -0800
> > , Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
> >  wrote:
> >> This patch improves the implementation of device tree structure.
> >>
> >> Traditional child and sibling linked list in device tree structure
> >> is removed and is replaced by list_head (i.e. circular doubly linked
> >>  list) already available in Linux kernel.
> >>
> >> Signed-off-by: Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
> >
> > Hi Gaurav,
> >
> > So, after you've done this work, I need to you rebase it (and of course
> > it is non-trivial) onto linux-next. I've already got a patch queued up
> > which gets rid of the of_allnodes/allnext list which will have conflicts
> > with this patch.
> >
> 
> I am using http://git.kernel.org/pub/scm/linux/kernel/git/glikely/linux.git
> There is no branch linux-next in it. Also, I believe http://git.secretlab.ca/
> is not up yet. Please correct.

The branch is devicetree/next. That is the branch that gets pulled into
linux-next every day.

git.secretlab.ca is now gone. I'm not going to resurrect it.

> >> -#define NO_OF_NODES 3
> >> -static struct device_node *nodes[NO_OF_NODES];
> >> -static int last_node_index;
> >> +#define MAX_NODES 50
> >> +
> >> +static int no_of_nodes;
> >>  static bool selftest_live_tree;
> >> +static struct device_node* nodes[MAX_NODES];
> >
> > I think it's time to rework this structure. Instead of a static list,
> > the code should figure out how many entries it needs and then kzalloc()
> > the region.
> 
> Ok.

For now I would like to you focus on this change and on making the
unittests independent of OF_DYNAMIC. Frank had some good comments. I'd
like to think on it some more before proceeding. The only time that the
single linked list is a problem is when unflattening the tree, but even
that can be mitigated by reordering it after unflatting has completed
instead of trying to keep it in order all the time.

The biggest question is whether or not we can switch to RCU operations.
It isn't necessary to use list_head to switch to RCU, but RCU is a lot
better understood when list_head is used.

So, work on OF_DYNAMIC for now and we'll revisit list_head later.

g.
--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] Patch to improve device tree structure

[Grant Likely]

On Wed, 19 Nov 2014 11:30:12 -0800
, Frank Rowand <frowand.list-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
 wrote:
> On 11/19/2014 5:56 AM, Grant Likely wrote:
> > On Wed, Nov 19, 2014 at 1:37 AM, Frank Rowand <frowand.list-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
> >> On 11/18/2014 7:10 AM, Grant Likely wrote:
> >>> On Sun, 16 Nov 2014 20:52:56 -0800
> >>> , Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
> >>>  wrote:
> >>>> This patch improves the implementation of device tree structure.
> >>>>
> >>>> Traditional child and sibling linked list in device tree structure
> >>>> is removed and is replaced by list_head (i.e. circular doubly linked
> >>>>  list) already available in Linux kernel.
> >>>>
> >>>> Signed-off-by: Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
> >>>
> >>> Hi Gaurav,
> >>>
> >>> So, after you've done this work, I need to you rebase it (and of course
> >>> it is non-trivial) onto linux-next. I've already got a patch queued up
> >>> which gets rid of the of_allnodes/allnext list which will have conflicts
> >>> with this patch.
> >>>
> >>> I'll make comments below where still relevant.
> >>
> >> Grant,
> >>
> >> My first reaction to this patch was that moving to using struct list_head
> >> made the code less readable plus increased the size of struct device_node.
> >>
> >> I reworked the changes to drivers/of/base.c to see if I could make
> >> it a little more readable.  And I see below that you also have some
> >> suggestions that make it more readable.
> >>
> >> Even after that, I'm still feeling that the gain of moving to a more
> >> standard list data type might not be greater than the downsides in
> >> terms of readability and space.  The current list implementation does
> >> seem like a decent fit to the problem space.
> > 
> > Moving to list_head has a couple of nice benefits. The prime
> > motification is that using a standard list_head means that the OF code
> > can be migrated to use the standard rcu operations and get rid of manual
> > of_node_{get,put} management in the majority of code paths.
> 
> Oh yeah, I remember you mentioning that before.  That is what was missing
> from Gaurav's patch header, explaining the value of the change.  If this
> is the end goal, then I think it would be valuable to add a second patch
> to the series that shows what the actual changes for rcu will be so that
> the cost vs benefit of the end result can be evaluated.
> 
> 
> > A second reason to do this is it becomes easy to add nodes to the end of
> > the list instead of the beginning. It's a small thing, but it makes
> > unflattening simpler.
> 
> Not a big change.  In the unflatten_dt_node() part of the patch, the
> result was 4 lines deleted, 3 lines added.  With my attached patch to
> remove the next field, it would have been 8 lines deleted, 3 lines
> added -- thus list_head is an even greater simplification.  But still
> tiny.
> 
> 
> > I've also considered switching to a hlist_head/hlist_node to keep the
> > footprint the same.* With an hlist_head the cost is a wash, but looses
> > the ability to do O(1) addition to the end of the list.
> > 
> > * Gaurav's patch removes the *child and *sibling pointers, but doesn't
> >   remove the *next pointer which can also be dropped. So, three pointers
> >   get dropped from the structure. Using list_head adds 4 pointers (Net
> >   +1). hlist_head adds 3 (Net 0).
> 
> I include a patch below to also drop the *next pointer.  Not to actually
> propose submitting the patch, but to suggest that Gaurav's patch should be
> counted as a net of +2 pointers.  I expect that you will accept either a
> list_head of an hlist_head patch, but if you do not then I will submit the
> below patch to remove *next or a patch to rename *next to match the actual
> usage of the field.
> 
> I still do not have a strong opinion, but I am still feeling that the gain
> probably does not outweigh the cost.
> 
> -Frank
> 
> > 
> > g.
> > 
> 
> From: Frank Rowand <frank.rowand-/MT0OVThwyLZJqsBc5GL+g@public.gmane.org>
> 
> Decrease size of struct device_node by one pointer.
> The pointer is only used during the unflattening of the
> device tree at boot.
> 
> The cost of removing the pointer is chasing through the
> sibling list to add new nodes instead of using the
> cached 'last_child'.  The cost is expected to be in the
> noise level.
> 
> Signed-off-by: Frank Rowand <frank.rowand-/MT0OVThwyLZJqsBc5GL+g@public.gmane.org>
> ---
>  drivers/of/fdt.c   |   14 +++++++++-----
>  include/linux/of.h |    1 -
>  2 files changed, 9 insertions(+), 6 deletions(-)
> 
> Index: b/include/linux/of.h
> ===================================================================
> --- a/include/linux/of.h
> +++ b/include/linux/of.h
> @@ -55,7 +55,6 @@ struct device_node {
>  	struct	device_node *parent;
>  	struct	device_node *child;
>  	struct	device_node *sibling;
> -	struct	device_node *next;	/* next device of same type */
>  	struct	device_node *allnext;	/* next in list of all nodes */
>  	struct	kobject kobj;
>  	unsigned long _flags;
> Index: b/drivers/of/fdt.c
> ===================================================================
> --- a/drivers/of/fdt.c
> +++ b/drivers/of/fdt.c
> @@ -226,12 +226,16 @@ static void * unflatten_dt_node(void *bl
>  		*allnextpp = &np->allnext;
>  		if (dad != NULL) {
>  			np->parent = dad;
> -			/* we temporarily use the next field as `last_child'*/
> -			if (dad->next == NULL)
> +			if (dad->child == NULL)
>  				dad->child = np;
> -			else
> -				dad->next->sibling = np;
> -			dad->next = np;
> +			else {
> +				struct device_node *next;
> +
> +				next = dad->child;
> +				while (next->sibling)
> +					next = next->sibling;
> +				next->sibling = np;
> +			}
>  		}
>  	}
>  	/* process properties */

Instead of keeping it always in order, what about reordering the whole
list after all the nodes at a given level are unflattened? That would
avoid traversing the entire sibling list on every node addition. Like
this:

g.

>From de46de766eb4d2240208bf83fdae955361069352 Mon Sep 17 00:00:00 2001
From: Grant Likely <grant.likely-QSEj5FYQhm4dnm+yROfE0A@public.gmane.org>
Date: Fri, 28 Nov 2014 16:03:33 +0000
Subject: [PATCH] of: Drop ->next pointer from struct device_node

The ->next pointer in struct device_node is a hanger-on from when it was
used to iterate over the whole tree by a particular device_type property
value. Those days are long over, but the fdt unflattening code still
uses it to put nodes in the unflattened tree into the same order as node
in the flat tree. By reworking the unflattening code to reverse the list
after unflattening all the children of a node, the pointer can be
dropped which gives a small amount of memory savings.

Signed-off-by: Grant Likely <grant.likely-QSEj5FYQhm4dnm+yROfE0A@public.gmane.org>
Cc: Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
Cc: Frank Rowand <frowand.list-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
---
 drivers/of/fdt.c   | 24 ++++++++++++++++++------
 include/linux/of.h |  1 -
 2 files changed, 18 insertions(+), 7 deletions(-)

diff --git a/drivers/of/fdt.c b/drivers/of/fdt.c
index 7f6ee31d5650..a41f9fdb1aa0 100644
--- a/drivers/of/fdt.c
+++ b/drivers/of/fdt.c
@@ -226,12 +226,8 @@ static void * unflatten_dt_node(void *blob,
 		prev_pp = &np->properties;
 		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->sibling = dad->child;
+			dad->child = np;
 		}
 	}
 	/* process properties */
@@ -329,6 +325,22 @@ static void * unflatten_dt_node(void *blob,
 
 	if (*poffset < 0 && *poffset != -FDT_ERR_NOTFOUND)
 		pr_err("unflatten: error %d processing FDT\n", *poffset);
+
+	/*
+	 * Reverse the child list. Some drivers assumes node order matches .dts
+	 * node order
+	 */
+	if (!dryrun && np->child) {
+		struct device_node *child = np->child;
+		np->child = NULL;
+		while (child) {
+			struct device_node *next = child->sibling;
+			child->sibling = np->child;
+			np->child = child;
+			child = next;
+		}
+	}
+
 	if (nodepp)
 		*nodepp = np;
 
diff --git a/include/linux/of.h b/include/linux/of.h
index 8b021db3e16e..3f0f0ffbd5e5 100644
--- a/include/linux/of.h
+++ b/include/linux/of.h
@@ -56,7 +56,6 @@ struct device_node {
 	struct	device_node *parent;
 	struct	device_node *child;
 	struct	device_node *sibling;
-	struct	device_node *next;	/* next device of same type */
 	struct	kobject kobj;
 	unsigned long _flags;
 	void	*data;
-- 
1.9.1

--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] Patch to improve device tree structure

[Frank Rowand]

On 11/28/2014 8:48 AM, Grant Likely wrote:
> On Wed, 19 Nov 2014 11:30:12 -0800
> , Frank Rowand <frowand.list-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>  wrote:
>> On 11/19/2014 5:56 AM, Grant Likely wrote:
>>> On Wed, Nov 19, 2014 at 1:37 AM, Frank Rowand <frowand.list-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
>>>> On 11/18/2014 7:10 AM, Grant Likely wrote:
>>>>> On Sun, 16 Nov 2014 20:52:56 -0800
>>>>> , Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>>>>>  wrote:
>>>>>> This patch improves the implementation of device tree structure.
>>>>>>
>>>>>> Traditional child and sibling linked list in device tree structure
>>>>>> is removed and is replaced by list_head (i.e. circular doubly linked
>>>>>>  list) already available in Linux kernel.
>>>>>>
>>>>>> Signed-off-by: Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>>>>>
>>>>> Hi Gaurav,
>>>>>
>>>>> So, after you've done this work, I need to you rebase it (and of course
>>>>> it is non-trivial) onto linux-next. I've already got a patch queued up
>>>>> which gets rid of the of_allnodes/allnext list which will have conflicts
>>>>> with this patch.
>>>>>
>>>>> I'll make comments below where still relevant.
>>>>
>>>> Grant,
>>>>
>>>> My first reaction to this patch was that moving to using struct list_head
>>>> made the code less readable plus increased the size of struct device_node.
>>>>
>>>> I reworked the changes to drivers/of/base.c to see if I could make
>>>> it a little more readable.  And I see below that you also have some
>>>> suggestions that make it more readable.
>>>>
>>>> Even after that, I'm still feeling that the gain of moving to a more
>>>> standard list data type might not be greater than the downsides in
>>>> terms of readability and space.  The current list implementation does
>>>> seem like a decent fit to the problem space.
>>>
>>> Moving to list_head has a couple of nice benefits. The prime
>>> motification is that using a standard list_head means that the OF code
>>> can be migrated to use the standard rcu operations and get rid of manual
>>> of_node_{get,put} management in the majority of code paths.
>>
>> Oh yeah, I remember you mentioning that before.  That is what was missing
>> from Gaurav's patch header, explaining the value of the change.  If this
>> is the end goal, then I think it would be valuable to add a second patch
>> to the series that shows what the actual changes for rcu will be so that
>> the cost vs benefit of the end result can be evaluated.
>>
>>
>>> A second reason to do this is it becomes easy to add nodes to the end of
>>> the list instead of the beginning. It's a small thing, but it makes
>>> unflattening simpler.
>>
>> Not a big change.  In the unflatten_dt_node() part of the patch, the
>> result was 4 lines deleted, 3 lines added.  With my attached patch to
>> remove the next field, it would have been 8 lines deleted, 3 lines
>> added -- thus list_head is an even greater simplification.  But still
>> tiny.
>>
>>
>>> I've also considered switching to a hlist_head/hlist_node to keep the
>>> footprint the same.* With an hlist_head the cost is a wash, but looses
>>> the ability to do O(1) addition to the end of the list.
>>>
>>> * Gaurav's patch removes the *child and *sibling pointers, but doesn't
>>>   remove the *next pointer which can also be dropped. So, three pointers
>>>   get dropped from the structure. Using list_head adds 4 pointers (Net
>>>   +1). hlist_head adds 3 (Net 0).
>>
>> I include a patch below to also drop the *next pointer.  Not to actually
>> propose submitting the patch, but to suggest that Gaurav's patch should be
>> counted as a net of +2 pointers.  I expect that you will accept either a
>> list_head of an hlist_head patch, but if you do not then I will submit the
>> below patch to remove *next or a patch to rename *next to match the actual
>> usage of the field.
>>
>> I still do not have a strong opinion, but I am still feeling that the gain
>> probably does not outweigh the cost.
>>
>> -Frank
>>
>>>
>>> g.
>>>
>>
>> From: Frank Rowand <frank.rowand-/MT0OVThwyLZJqsBc5GL+g@public.gmane.org>
>>
>> Decrease size of struct device_node by one pointer.
>> The pointer is only used during the unflattening of the
>> device tree at boot.
>>
>> The cost of removing the pointer is chasing through the
>> sibling list to add new nodes instead of using the
>> cached 'last_child'.  The cost is expected to be in the
>> noise level.
>>
>> Signed-off-by: Frank Rowand <frank.rowand-/MT0OVThwyLZJqsBc5GL+g@public.gmane.org>
>> ---
>>  drivers/of/fdt.c   |   14 +++++++++-----
>>  include/linux/of.h |    1 -
>>  2 files changed, 9 insertions(+), 6 deletions(-)
>>
>> Index: b/include/linux/of.h
>> ===================================================================
>> --- a/include/linux/of.h
>> +++ b/include/linux/of.h
>> @@ -55,7 +55,6 @@ struct device_node {
>>  	struct	device_node *parent;
>>  	struct	device_node *child;
>>  	struct	device_node *sibling;
>> -	struct	device_node *next;	/* next device of same type */
>>  	struct	device_node *allnext;	/* next in list of all nodes */
>>  	struct	kobject kobj;
>>  	unsigned long _flags;
>> Index: b/drivers/of/fdt.c
>> ===================================================================
>> --- a/drivers/of/fdt.c
>> +++ b/drivers/of/fdt.c
>> @@ -226,12 +226,16 @@ static void * unflatten_dt_node(void *bl
>>  		*allnextpp = &np->allnext;
>>  		if (dad != NULL) {
>>  			np->parent = dad;
>> -			/* we temporarily use the next field as `last_child'*/
>> -			if (dad->next == NULL)
>> +			if (dad->child == NULL)
>>  				dad->child = np;
>> -			else
>> -				dad->next->sibling = np;
>> -			dad->next = np;
>> +			else {
>> +				struct device_node *next;
>> +
>> +				next = dad->child;
>> +				while (next->sibling)
>> +					next = next->sibling;
>> +				next->sibling = np;
>> +			}
>>  		}
>>  	}
>>  	/* process properties */
> 
> Instead of keeping it always in order, what about reordering the whole
> list after all the nodes at a given level are unflattened? That would
> avoid traversing the entire sibling list on every node addition. Like
> this:

Seems pretty close to a wash to me.  Either one would work.  Though
mine would benefit from the comment you added in yours.

-Frank

> 
> g.
> 
>>From de46de766eb4d2240208bf83fdae955361069352 Mon Sep 17 00:00:00 2001
> From: Grant Likely <grant.likely-QSEj5FYQhm4dnm+yROfE0A@public.gmane.org>
> Date: Fri, 28 Nov 2014 16:03:33 +0000
> Subject: [PATCH] of: Drop ->next pointer from struct device_node
> 
> The ->next pointer in struct device_node is a hanger-on from when it was
> used to iterate over the whole tree by a particular device_type property
> value. Those days are long over, but the fdt unflattening code still
> uses it to put nodes in the unflattened tree into the same order as node
> in the flat tree. By reworking the unflattening code to reverse the list
> after unflattening all the children of a node, the pointer can be
> dropped which gives a small amount of memory savings.
> 
> Signed-off-by: Grant Likely <grant.likely-QSEj5FYQhm4dnm+yROfE0A@public.gmane.org>
> Cc: Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
> Cc: Frank Rowand <frowand.list-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
> ---
>  drivers/of/fdt.c   | 24 ++++++++++++++++++------
>  include/linux/of.h |  1 -
>  2 files changed, 18 insertions(+), 7 deletions(-)
> 
> diff --git a/drivers/of/fdt.c b/drivers/of/fdt.c
> index 7f6ee31d5650..a41f9fdb1aa0 100644
> --- a/drivers/of/fdt.c
> +++ b/drivers/of/fdt.c
> @@ -226,12 +226,8 @@ static void * unflatten_dt_node(void *blob,
>  		prev_pp = &np->properties;
>  		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->sibling = dad->child;
> +			dad->child = np;
>  		}
>  	}
>  	/* process properties */
> @@ -329,6 +325,22 @@ static void * unflatten_dt_node(void *blob,
>  
>  	if (*poffset < 0 && *poffset != -FDT_ERR_NOTFOUND)
>  		pr_err("unflatten: error %d processing FDT\n", *poffset);
> +
> +	/*
> +	 * Reverse the child list. Some drivers assumes node order matches .dts
> +	 * node order
> +	 */
> +	if (!dryrun && np->child) {
> +		struct device_node *child = np->child;
> +		np->child = NULL;
> +		while (child) {
> +			struct device_node *next = child->sibling;
> +			child->sibling = np->child;
> +			np->child = child;
> +			child = next;
> +		}
> +	}
> +
>  	if (nodepp)
>  		*nodepp = np;
>  
> diff --git a/include/linux/of.h b/include/linux/of.h
> index 8b021db3e16e..3f0f0ffbd5e5 100644
> --- a/include/linux/of.h
> +++ b/include/linux/of.h
> @@ -56,7 +56,6 @@ struct device_node {
>  	struct	device_node *parent;
>  	struct	device_node *child;
>  	struct	device_node *sibling;
> -	struct	device_node *next;	/* next device of same type */
>  	struct	kobject kobj;
>  	unsigned long _flags;
>  	void	*data;
> 

--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] Patch to improve device tree structure

[Grant Likely]

On Wed, Dec 3, 2014 at 3:39 AM, Frank Rowand <frowand.list-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
> On 11/28/2014 8:48 AM, Grant Likely wrote:
>> On Wed, 19 Nov 2014 11:30:12 -0800
>> , Frank Rowand <frowand.list-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>>  wrote:
>>> On 11/19/2014 5:56 AM, Grant Likely wrote:
>>>> On Wed, Nov 19, 2014 at 1:37 AM, Frank Rowand <frowand.list-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
>>>>> On 11/18/2014 7:10 AM, Grant Likely wrote:
>>>>>> On Sun, 16 Nov 2014 20:52:56 -0800
>>>>>> , Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>>>>>>  wrote:
>>>>>>> This patch improves the implementation of device tree structure.
>>>>>>>
>>>>>>> Traditional child and sibling linked list in device tree structure
>>>>>>> is removed and is replaced by list_head (i.e. circular doubly linked
>>>>>>>  list) already available in Linux kernel.
>>>>>>>
>>>>>>> Signed-off-by: Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>>>>>>
>>>>>> Hi Gaurav,
>>>>>>
>>>>>> So, after you've done this work, I need to you rebase it (and of course
>>>>>> it is non-trivial) onto linux-next. I've already got a patch queued up
>>>>>> which gets rid of the of_allnodes/allnext list which will have conflicts
>>>>>> with this patch.
>>>>>>
>>>>>> I'll make comments below where still relevant.
>>>>>
>>>>> Grant,
>>>>>
>>>>> My first reaction to this patch was that moving to using struct list_head
>>>>> made the code less readable plus increased the size of struct device_node.
>>>>>
>>>>> I reworked the changes to drivers/of/base.c to see if I could make
>>>>> it a little more readable.  And I see below that you also have some
>>>>> suggestions that make it more readable.
>>>>>
>>>>> Even after that, I'm still feeling that the gain of moving to a more
>>>>> standard list data type might not be greater than the downsides in
>>>>> terms of readability and space.  The current list implementation does
>>>>> seem like a decent fit to the problem space.
>>>>
>>>> Moving to list_head has a couple of nice benefits. The prime
>>>> motification is that using a standard list_head means that the OF code
>>>> can be migrated to use the standard rcu operations and get rid of manual
>>>> of_node_{get,put} management in the majority of code paths.
>>>
>>> Oh yeah, I remember you mentioning that before.  That is what was missing
>>> from Gaurav's patch header, explaining the value of the change.  If this
>>> is the end goal, then I think it would be valuable to add a second patch
>>> to the series that shows what the actual changes for rcu will be so that
>>> the cost vs benefit of the end result can be evaluated.
>>>
>>>
>>>> A second reason to do this is it becomes easy to add nodes to the end of
>>>> the list instead of the beginning. It's a small thing, but it makes
>>>> unflattening simpler.
>>>
>>> Not a big change.  In the unflatten_dt_node() part of the patch, the
>>> result was 4 lines deleted, 3 lines added.  With my attached patch to
>>> remove the next field, it would have been 8 lines deleted, 3 lines
>>> added -- thus list_head is an even greater simplification.  But still
>>> tiny.
>>>
>>>
>>>> I've also considered switching to a hlist_head/hlist_node to keep the
>>>> footprint the same.* With an hlist_head the cost is a wash, but looses
>>>> the ability to do O(1) addition to the end of the list.
>>>>
>>>> * Gaurav's patch removes the *child and *sibling pointers, but doesn't
>>>>   remove the *next pointer which can also be dropped. So, three pointers
>>>>   get dropped from the structure. Using list_head adds 4 pointers (Net
>>>>   +1). hlist_head adds 3 (Net 0).
>>>
>>> I include a patch below to also drop the *next pointer.  Not to actually
>>> propose submitting the patch, but to suggest that Gaurav's patch should be
>>> counted as a net of +2 pointers.  I expect that you will accept either a
>>> list_head of an hlist_head patch, but if you do not then I will submit the
>>> below patch to remove *next or a patch to rename *next to match the actual
>>> usage of the field.
>>>
>>> I still do not have a strong opinion, but I am still feeling that the gain
>>> probably does not outweigh the cost.
>>>
>>> -Frank
>>>
>>>>
>>>> g.
>>>>
>>>
>>> From: Frank Rowand <frank.rowand-/MT0OVThwyLZJqsBc5GL+g@public.gmane.org>
>>>
>>> Decrease size of struct device_node by one pointer.
>>> The pointer is only used during the unflattening of the
>>> device tree at boot.
>>>
>>> The cost of removing the pointer is chasing through the
>>> sibling list to add new nodes instead of using the
>>> cached 'last_child'.  The cost is expected to be in the
>>> noise level.
>>>
>>> Signed-off-by: Frank Rowand <frank.rowand-/MT0OVThwyLZJqsBc5GL+g@public.gmane.org>
>>> ---
>>>  drivers/of/fdt.c   |   14 +++++++++-----
>>>  include/linux/of.h |    1 -
>>>  2 files changed, 9 insertions(+), 6 deletions(-)
>>>
>>> Index: b/include/linux/of.h
>>> ===================================================================
>>> --- a/include/linux/of.h
>>> +++ b/include/linux/of.h
>>> @@ -55,7 +55,6 @@ struct device_node {
>>>      struct  device_node *parent;
>>>      struct  device_node *child;
>>>      struct  device_node *sibling;
>>> -    struct  device_node *next;      /* next device of same type */
>>>      struct  device_node *allnext;   /* next in list of all nodes */
>>>      struct  kobject kobj;
>>>      unsigned long _flags;
>>> Index: b/drivers/of/fdt.c
>>> ===================================================================
>>> --- a/drivers/of/fdt.c
>>> +++ b/drivers/of/fdt.c
>>> @@ -226,12 +226,16 @@ static void * unflatten_dt_node(void *bl
>>>              *allnextpp = &np->allnext;
>>>              if (dad != NULL) {
>>>                      np->parent = dad;
>>> -                    /* we temporarily use the next field as `last_child'*/
>>> -                    if (dad->next == NULL)
>>> +                    if (dad->child == NULL)
>>>                              dad->child = np;
>>> -                    else
>>> -                            dad->next->sibling = np;
>>> -                    dad->next = np;
>>> +                    else {
>>> +                            struct device_node *next;
>>> +
>>> +                            next = dad->child;
>>> +                            while (next->sibling)
>>> +                                    next = next->sibling;
>>> +                            next->sibling = np;
>>> +                    }
>>>              }
>>>      }
>>>      /* process properties */
>>
>> Instead of keeping it always in order, what about reordering the whole
>> list after all the nodes at a given level are unflattened? That would
>> avoid traversing the entire sibling list on every node addition. Like
>> this:
>
> Seems pretty close to a wash to me.  Either one would work.  Though
> mine would benefit from the comment you added in yours.
>
> -Frank

Okay, if I can take that as an 'acked-by' from you then I'll merge my
version of the patch. I prefer doing the post processing to sort the
list because it is theoretically less costly.

g.

>>
>> g.
>>
>>>From de46de766eb4d2240208bf83fdae955361069352 Mon Sep 17 00:00:00 2001
>> From: Grant Likely <grant.likely-QSEj5FYQhm4dnm+yROfE0A@public.gmane.org>
>> Date: Fri, 28 Nov 2014 16:03:33 +0000
>> Subject: [PATCH] of: Drop ->next pointer from struct device_node
>>
>> The ->next pointer in struct device_node is a hanger-on from when it was
>> used to iterate over the whole tree by a particular device_type property
>> value. Those days are long over, but the fdt unflattening code still
>> uses it to put nodes in the unflattened tree into the same order as node
>> in the flat tree. By reworking the unflattening code to reverse the list
>> after unflattening all the children of a node, the pointer can be
>> dropped which gives a small amount of memory savings.
>>
>> Signed-off-by: Grant Likely <grant.likely-QSEj5FYQhm4dnm+yROfE0A@public.gmane.org>
>> Cc: Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>> Cc: Frank Rowand <frowand.list-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>> ---
>>  drivers/of/fdt.c   | 24 ++++++++++++++++++------
>>  include/linux/of.h |  1 -
>>  2 files changed, 18 insertions(+), 7 deletions(-)
>>
>> diff --git a/drivers/of/fdt.c b/drivers/of/fdt.c
>> index 7f6ee31d5650..a41f9fdb1aa0 100644
>> --- a/drivers/of/fdt.c
>> +++ b/drivers/of/fdt.c
>> @@ -226,12 +226,8 @@ static void * unflatten_dt_node(void *blob,
>>               prev_pp = &np->properties;
>>               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->sibling = dad->child;
>> +                     dad->child = np;
>>               }
>>       }
>>       /* process properties */
>> @@ -329,6 +325,22 @@ static void * unflatten_dt_node(void *blob,
>>
>>       if (*poffset < 0 && *poffset != -FDT_ERR_NOTFOUND)
>>               pr_err("unflatten: error %d processing FDT\n", *poffset);
>> +
>> +     /*
>> +      * Reverse the child list. Some drivers assumes node order matches .dts
>> +      * node order
>> +      */
>> +     if (!dryrun && np->child) {
>> +             struct device_node *child = np->child;
>> +             np->child = NULL;
>> +             while (child) {
>> +                     struct device_node *next = child->sibling;
>> +                     child->sibling = np->child;
>> +                     np->child = child;
>> +                     child = next;
>> +             }
>> +     }
>> +
>>       if (nodepp)
>>               *nodepp = np;
>>
>> diff --git a/include/linux/of.h b/include/linux/of.h
>> index 8b021db3e16e..3f0f0ffbd5e5 100644
>> --- a/include/linux/of.h
>> +++ b/include/linux/of.h
>> @@ -56,7 +56,6 @@ struct device_node {
>>       struct  device_node *parent;
>>       struct  device_node *child;
>>       struct  device_node *sibling;
>> -     struct  device_node *next;      /* next device of same type */
>>       struct  kobject kobj;
>>       unsigned long _flags;
>>       void    *data;
>>
>
--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] Patch to improve device tree structure

[Frank Rowand]

On 12/3/2014 7:09 AM, Grant Likely wrote:
> On Wed, Dec 3, 2014 at 3:39 AM, Frank Rowand <frowand.list-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
>> On 11/28/2014 8:48 AM, Grant Likely wrote:

< snip >

>>> Instead of keeping it always in order, what about reordering the whole
>>> list after all the nodes at a given level are unflattened? That would
>>> avoid traversing the entire sibling list on every node addition. Like
>>> this:
>>
>> Seems pretty close to a wash to me.  Either one would work.  Though
>> mine would benefit from the comment you added in yours.
>>
>> -Frank
> 
> Okay, if I can take that as an 'acked-by' from you then I'll merge my
> version of the patch. I prefer doing the post processing to sort the
> list because it is theoretically less costly.

Yes, that would be fine.

Acked-by:  Frank Rowand <frank.rowand-/MT0OVThwyLZJqsBc5GL+g@public.gmane.org>

> 
> g.
> 
>>>
>>> g.
>>>
>>> >From de46de766eb4d2240208bf83fdae955361069352 Mon Sep 17 00:00:00 2001
>>> From: Grant Likely <grant.likely-QSEj5FYQhm4dnm+yROfE0A@public.gmane.org>
>>> Date: Fri, 28 Nov 2014 16:03:33 +0000
>>> Subject: [PATCH] of: Drop ->next pointer from struct device_node
>>>
>>> The ->next pointer in struct device_node is a hanger-on from when it was
>>> used to iterate over the whole tree by a particular device_type property
>>> value. Those days are long over, but the fdt unflattening code still
>>> uses it to put nodes in the unflattened tree into the same order as node
>>> in the flat tree. By reworking the unflattening code to reverse the list
>>> after unflattening all the children of a node, the pointer can be
>>> dropped which gives a small amount of memory savings.
>>>
>>> Signed-off-by: Grant Likely <grant.likely-QSEj5FYQhm4dnm+yROfE0A@public.gmane.org>
>>> Cc: Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>>> Cc: Frank Rowand <frowand.list-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>>> ---
>>>  drivers/of/fdt.c   | 24 ++++++++++++++++++------
>>>  include/linux/of.h |  1 -
>>>  2 files changed, 18 insertions(+), 7 deletions(-)
>>>
>>> diff --git a/drivers/of/fdt.c b/drivers/of/fdt.c
>>> index 7f6ee31d5650..a41f9fdb1aa0 100644
>>> --- a/drivers/of/fdt.c
>>> +++ b/drivers/of/fdt.c
>>> @@ -226,12 +226,8 @@ static void * unflatten_dt_node(void *blob,
>>>               prev_pp = &np->properties;
>>>               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->sibling = dad->child;
>>> +                     dad->child = np;
>>>               }
>>>       }
>>>       /* process properties */
>>> @@ -329,6 +325,22 @@ static void * unflatten_dt_node(void *blob,
>>>
>>>       if (*poffset < 0 && *poffset != -FDT_ERR_NOTFOUND)
>>>               pr_err("unflatten: error %d processing FDT\n", *poffset);
>>> +
>>> +     /*
>>> +      * Reverse the child list. Some drivers assumes node order matches .dts
>>> +      * node order
>>> +      */
>>> +     if (!dryrun && np->child) {
>>> +             struct device_node *child = np->child;
>>> +             np->child = NULL;
>>> +             while (child) {
>>> +                     struct device_node *next = child->sibling;
>>> +                     child->sibling = np->child;
>>> +                     np->child = child;
>>> +                     child = next;
>>> +             }
>>> +     }
>>> +
>>>       if (nodepp)
>>>               *nodepp = np;
>>>
>>> diff --git a/include/linux/of.h b/include/linux/of.h
>>> index 8b021db3e16e..3f0f0ffbd5e5 100644
>>> --- a/include/linux/of.h
>>> +++ b/include/linux/of.h
>>> @@ -56,7 +56,6 @@ struct device_node {
>>>       struct  device_node *parent;
>>>       struct  device_node *child;
>>>       struct  device_node *sibling;
>>> -     struct  device_node *next;      /* next device of same type */
>>>       struct  kobject kobj;
>>>       unsigned long _flags;
>>>       void    *data;
>>>
>>
> 

--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html