Merge branch 'next-devicetree' of git://git.secretlab.ca/git/linux-2.6

* 'next-devicetree' of git://git.secretlab.ca/git/linux-2.6: (29 commits)
  of/flattree: forward declare struct device_node in of_fdt.h
  ipmi: explicitly include of_address.h and of_irq.h
  sparc: explicitly cast negative phandle checks to s32
  powerpc/405: Fix missing #{address,size}-cells in i2c node
  powerpc/5200: dts: refactor dts files
  powerpc/5200: dts: Change combatible strings on localbus
  powerpc/5200: dts: remove unused properties
  powerpc/5200: dts: rename nodes to prepare for refactoring dts files
  of/flattree: Update dtc to current mainline.
  of/device: Don't register disabled devices
  powerpc/dts: fix syntax bugs in bluestone.dts
  of: Fixes for OF probing on little endian systems
  of: make drivers depend on CONFIG_OF instead of CONFIG_PPC_OF
  of/flattree: Add of_flat_dt_match() helper function
  of_serial: explicitly include of_irq.h
  of/flattree: Refactor unflatten_device_tree and add fdt_unflatten_tree
  of/flattree: Reorder unflatten_dt_node
  of/flattree: Refactor unflatten_dt_node
  of/flattree: Add non-boottime device tree functions
  of/flattree: Add Kconfig for EARLY_FLATTREE
  ...

Fix up trivial conflict in arch/sparc/prom/tree_32.c as per Grant.

1 files changed, 323 insertions, 22 deletions

diff --git a/scripts/dtc/livetree.c b/scripts/dtc/livetree.c
index 0ca3de550b3f..c9209d5c999e 100644
--- a/scripts/dtc/livetree.c
+++ b/scripts/dtc/livetree.c
@@ -24,17 +24,30 @@
  * Tree building functions
  */
 
-struct property *build_property(char *name, struct data val, char *label)
+void add_label(struct label **labels, char *label)
+{
+	struct label *new;
+
+	/* Make sure the label isn't already there */
+	for_each_label(*labels, new)
+		if (streq(new->label, label))
+			return;
+
+	new = xmalloc(sizeof(*new));
+	new->label = label;
+	new->next = *labels;
+	*labels = new;
+}
+
+struct property *build_property(char *name, struct data val)
 {
 	struct property *new = xmalloc(sizeof(*new));
 
+	memset(new, 0, sizeof(*new));
+
 	new->name = name;
 	new->val = val;
 
-	new->next = NULL;
-
-	new->label = label;
-
 	return new;
 }
 
@@ -78,17 +91,82 @@ struct node *build_node(struct property *proplist, struct node *children)
 	return new;
 }
 
-struct node *name_node(struct node *node, char *name, char * label)
+struct node *name_node(struct node *node, char *name)
 {
 	assert(node->name == NULL);
 
 	node->name = name;
 
-	node->label = label;
-
 	return node;
 }
 
+struct node *merge_nodes(struct node *old_node, struct node *new_node)
+{
+	struct property *new_prop, *old_prop;
+	struct node *new_child, *old_child;
+	struct label *l;
+
+	/* Add new node labels to old node */
+	for_each_label(new_node->labels, l)
+		add_label(&old_node->labels, l->label);
+
+	/* Move properties from the new node to the old node.  If there
+	 * is a collision, replace the old value with the new */
+	while (new_node->proplist) {
+		/* Pop the property off the list */
+		new_prop = new_node->proplist;
+		new_node->proplist = new_prop->next;
+		new_prop->next = NULL;
+
+		/* Look for a collision, set new value if there is */
+		for_each_property(old_node, old_prop) {
+			if (streq(old_prop->name, new_prop->name)) {
+				/* Add new labels to old property */
+				for_each_label(new_prop->labels, l)
+					add_label(&old_prop->labels, l->label);
+
+				old_prop->val = new_prop->val;
+				free(new_prop);
+				new_prop = NULL;
+				break;
+			}
+		}
+
+		/* if no collision occurred, add property to the old node. */
+		if (new_prop)
+			add_property(old_node, new_prop);
+	}
+
+	/* Move the override child nodes into the primary node.  If
+	 * there is a collision, then merge the nodes. */
+	while (new_node->children) {
+		/* Pop the child node off the list */
+		new_child = new_node->children;
+		new_node->children = new_child->next_sibling;
+		new_child->parent = NULL;
+		new_child->next_sibling = NULL;
+
+		/* Search for a collision.  Merge if there is */
+		for_each_child(old_node, old_child) {
+			if (streq(old_child->name, new_child->name)) {
+				merge_nodes(old_child, new_child);
+				new_child = NULL;
+				break;
+			}
+		}
+
+		/* if no collision occured, add child to the old node. */
+		if (new_child)
+			add_child(old_node, new_child);
+	}
+
+	/* The new node contents are now merged into the old node.  Free
+	 * the new node. */
+	free(new_node);
+
+	return old_node;
+}
+
 struct node *chain_node(struct node *first, struct node *list)
 {
 	assert(first->next_sibling == NULL);
@@ -124,18 +202,15 @@ void add_child(struct node *parent, struct node *child)
 	*p = child;
 }
 
-struct reserve_info *build_reserve_entry(uint64_t address, uint64_t size,
-					 char *label)
+struct reserve_info *build_reserve_entry(uint64_t address, uint64_t size)
 {
 	struct reserve_info *new = xmalloc(sizeof(*new));
 
+	memset(new, 0, sizeof(*new));
+
 	new->re.address = address;
 	new->re.size = size;
 
-	new->next = NULL;
-
-	new->label = label;
-
 	return new;
 }
 
@@ -208,6 +283,60 @@ cell_t propval_cell(struct property *prop)
 	return fdt32_to_cpu(*((cell_t *)prop->val.val));
 }
 
+struct property *get_property_by_label(struct node *tree, const char *label,
+				       struct node **node)
+{
+	struct property *prop;
+	struct node *c;
+
+	*node = tree;
+
+	for_each_property(tree, prop) {
+		struct label *l;
+
+		for_each_label(prop->labels, l)
+			if (streq(l->label, label))
+				return prop;
+	}
+
+	for_each_child(tree, c) {
+		prop = get_property_by_label(c, label, node);
+		if (prop)
+			return prop;
+	}
+
+	*node = NULL;
+	return NULL;
+}
+
+struct marker *get_marker_label(struct node *tree, const char *label,
+				struct node **node, struct property **prop)
+{
+	struct marker *m;
+	struct property *p;
+	struct node *c;
+
+	*node = tree;
+
+	for_each_property(tree, p) {
+		*prop = p;
+		m = p->val.markers;
+		for_each_marker_of_type(m, LABEL)
+			if (streq(m->ref, label))
+				return m;
+	}
+
+	for_each_child(tree, c) {
+		m = get_marker_label(c, label, node, prop);
+		if (m)
+			return m;
+	}
+
+	*prop = NULL;
+	*node = NULL;
+	return NULL;
+}
+
 struct node *get_subnode(struct node *node, const char *nodename)
 {
 	struct node *child;
@@ -245,11 +374,13 @@ struct node *get_node_by_path(struct node *tree, const char *path)
 struct node *get_node_by_label(struct node *tree, const char *label)
 {
 	struct node *child, *node;
+	struct label *l;
 
 	assert(label && (strlen(label) > 0));
 
-	if (tree->label && streq(tree->label, label))
-		return tree;
+	for_each_label(tree->labels, l)
+		if (streq(l->label, label))
+			return tree;
 
 	for_each_child(tree, child) {
 		node = get_node_by_label(child, label);
@@ -293,16 +424,186 @@ cell_t get_node_phandle(struct node *root, struct node *node)
 	if ((node->phandle != 0) && (node->phandle != -1))
 		return node->phandle;
 
-	assert(! get_property(node, "linux,phandle"));
-
 	while (get_node_by_phandle(root, phandle))
 		phandle++;
 
 	node->phandle = phandle;
-	add_property(node,
-		     build_property("linux,phandle",
-				    data_append_cell(empty_data, phandle),
-				    NULL));
+
+	if (!get_property(node, "linux,phandle")
+	    && (phandle_format & PHANDLE_LEGACY))
+		add_property(node,
+			     build_property("linux,phandle",
+					    data_append_cell(empty_data, phandle)));
+
+	if (!get_property(node, "phandle")
+	    && (phandle_format & PHANDLE_EPAPR))
+		add_property(node,
+			     build_property("phandle",
+					    data_append_cell(empty_data, phandle)));
+
+	/* If the node *does* have a phandle property, we must
+	 * be dealing with a self-referencing phandle, which will be
+	 * fixed up momentarily in the caller */
 
 	return node->phandle;
 }
+
+uint32_t guess_boot_cpuid(struct node *tree)
+{
+	struct node *cpus, *bootcpu;
+	struct property *reg;
+
+	cpus = get_node_by_path(tree, "/cpus");
+	if (!cpus)
+		return 0;
+
+
+	bootcpu = cpus->children;
+	if (!bootcpu)
+		return 0;
+
+	reg = get_property(bootcpu, "reg");
+	if (!reg || (reg->val.len != sizeof(uint32_t)))
+		return 0;
+
+	/* FIXME: Sanity check node? */
+
+	return propval_cell(reg);
+}
+
+static int cmp_reserve_info(const void *ax, const void *bx)
+{
+	const struct reserve_info *a, *b;
+
+	a = *((const struct reserve_info * const *)ax);
+	b = *((const struct reserve_info * const *)bx);
+
+	if (a->re.address < b->re.address)
+		return -1;
+	else if (a->re.address > b->re.address)
+		return 1;
+	else if (a->re.size < b->re.size)
+		return -1;
+	else if (a->re.size > b->re.size)
+		return 1;
+	else
+		return 0;
+}
+
+static void sort_reserve_entries(struct boot_info *bi)
+{
+	struct reserve_info *ri, **tbl;
+	int n = 0, i = 0;
+
+	for (ri = bi->reservelist;
+	     ri;
+	     ri = ri->next)
+		n++;
+
+	if (n == 0)
+		return;
+
+	tbl = xmalloc(n * sizeof(*tbl));
+
+	for (ri = bi->reservelist;
+	     ri;
+	     ri = ri->next)
+		tbl[i++] = ri;
+
+	qsort(tbl, n, sizeof(*tbl), cmp_reserve_info);
+
+	bi->reservelist = tbl[0];
+	for (i = 0; i < (n-1); i++)
+		tbl[i]->next = tbl[i+1];
+	tbl[n-1]->next = NULL;
+
+	free(tbl);
+}
+
+static int cmp_prop(const void *ax, const void *bx)
+{
+	const struct property *a, *b;
+
+	a = *((const struct property * const *)ax);
+	b = *((const struct property * const *)bx);
+
+	return strcmp(a->name, b->name);
+}
+
+static void sort_properties(struct node *node)
+{
+	int n = 0, i = 0;
+	struct property *prop, **tbl;
+
+	for_each_property(node, prop)
+		n++;
+
+	if (n == 0)
+		return;
+
+	tbl = xmalloc(n * sizeof(*tbl));
+
+	for_each_property(node, prop)
+		tbl[i++] = prop;
+
+	qsort(tbl, n, sizeof(*tbl), cmp_prop);
+
+	node->proplist = tbl[0];
+	for (i = 0; i < (n-1); i++)
+		tbl[i]->next = tbl[i+1];
+	tbl[n-1]->next = NULL;
+
+	free(tbl);
+}
+
+static int cmp_subnode(const void *ax, const void *bx)
+{
+	const struct node *a, *b;
+
+	a = *((const struct node * const *)ax);
+	b = *((const struct node * const *)bx);
+
+	return strcmp(a->name, b->name);
+}
+
+static void sort_subnodes(struct node *node)
+{
+	int n = 0, i = 0;
+	struct node *subnode, **tbl;
+
+	for_each_child(node, subnode)
+		n++;
+
+	if (n == 0)
+		return;
+
+	tbl = xmalloc(n * sizeof(*tbl));
+
+	for_each_child(node, subnode)
+		tbl[i++] = subnode;
+
+	qsort(tbl, n, sizeof(*tbl), cmp_subnode);
+
+	node->children = tbl[0];
+	for (i = 0; i < (n-1); i++)
+		tbl[i]->next_sibling = tbl[i+1];
+	tbl[n-1]->next_sibling = NULL;
+
+	free(tbl);
+}
+
+static void sort_node(struct node *node)
+{
+	struct node *c;
+
+	sort_properties(node);
+	sort_subnodes(node);
+	for_each_child(node, c)
+		sort_node(c);
+}
+
+void sort_tree(struct boot_info *bi)
+{
+	sort_reserve_entries(bi);
+	sort_node(bi->dt);
+}