xref: /openbmc/linux/scripts/dtc/livetree.c (revision 3821a065)
1  /*
2   * (C) Copyright David Gibson <dwg@au1.ibm.com>, IBM Corporation.  2005.
3   *
4   *
5   * This program is free software; you can redistribute it and/or
6   * modify it under the terms of the GNU General Public License as
7   * published by the Free Software Foundation; either version 2 of the
8   * License, or (at your option) any later version.
9   *
10   *  This program is distributed in the hope that it will be useful,
11   *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12   *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13   *  General Public License for more details.
14   *
15   *  You should have received a copy of the GNU General Public License
16   *  along with this program; if not, write to the Free Software
17   *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307
18   *                                                                   USA
19   */
20  
21  #include "dtc.h"
22  
23  /*
24   * Tree building functions
25   */
26  
27  void add_label(struct label **labels, char *label)
28  {
29  	struct label *new;
30  
31  	/* Make sure the label isn't already there */
32  	for_each_label_withdel(*labels, new)
33  		if (streq(new->label, label)) {
34  			new->deleted = 0;
35  			return;
36  		}
37  
38  	new = xmalloc(sizeof(*new));
39  	memset(new, 0, sizeof(*new));
40  	new->label = label;
41  	new->next = *labels;
42  	*labels = new;
43  }
44  
45  void delete_labels(struct label **labels)
46  {
47  	struct label *label;
48  
49  	for_each_label(*labels, label)
50  		label->deleted = 1;
51  }
52  
53  struct property *build_property(char *name, struct data val)
54  {
55  	struct property *new = xmalloc(sizeof(*new));
56  
57  	memset(new, 0, sizeof(*new));
58  
59  	new->name = name;
60  	new->val = val;
61  
62  	return new;
63  }
64  
65  struct property *build_property_delete(char *name)
66  {
67  	struct property *new = xmalloc(sizeof(*new));
68  
69  	memset(new, 0, sizeof(*new));
70  
71  	new->name = name;
72  	new->deleted = 1;
73  
74  	return new;
75  }
76  
77  struct property *chain_property(struct property *first, struct property *list)
78  {
79  	assert(first->next == NULL);
80  
81  	first->next = list;
82  	return first;
83  }
84  
85  struct property *reverse_properties(struct property *first)
86  {
87  	struct property *p = first;
88  	struct property *head = NULL;
89  	struct property *next;
90  
91  	while (p) {
92  		next = p->next;
93  		p->next = head;
94  		head = p;
95  		p = next;
96  	}
97  	return head;
98  }
99  
100  struct node *build_node(struct property *proplist, struct node *children)
101  {
102  	struct node *new = xmalloc(sizeof(*new));
103  	struct node *child;
104  
105  	memset(new, 0, sizeof(*new));
106  
107  	new->proplist = reverse_properties(proplist);
108  	new->children = children;
109  
110  	for_each_child(new, child) {
111  		child->parent = new;
112  	}
113  
114  	return new;
115  }
116  
117  struct node *build_node_delete(void)
118  {
119  	struct node *new = xmalloc(sizeof(*new));
120  
121  	memset(new, 0, sizeof(*new));
122  
123  	new->deleted = 1;
124  
125  	return new;
126  }
127  
128  struct node *name_node(struct node *node, char *name)
129  {
130  	assert(node->name == NULL);
131  
132  	node->name = name;
133  
134  	return node;
135  }
136  
137  struct node *merge_nodes(struct node *old_node, struct node *new_node)
138  {
139  	struct property *new_prop, *old_prop;
140  	struct node *new_child, *old_child;
141  	struct label *l;
142  
143  	old_node->deleted = 0;
144  
145  	/* Add new node labels to old node */
146  	for_each_label_withdel(new_node->labels, l)
147  		add_label(&old_node->labels, l->label);
148  
149  	/* Move properties from the new node to the old node.  If there
150  	 * is a collision, replace the old value with the new */
151  	while (new_node->proplist) {
152  		/* Pop the property off the list */
153  		new_prop = new_node->proplist;
154  		new_node->proplist = new_prop->next;
155  		new_prop->next = NULL;
156  
157  		if (new_prop->deleted) {
158  			delete_property_by_name(old_node, new_prop->name);
159  			free(new_prop);
160  			continue;
161  		}
162  
163  		/* Look for a collision, set new value if there is */
164  		for_each_property_withdel(old_node, old_prop) {
165  			if (streq(old_prop->name, new_prop->name)) {
166  				/* Add new labels to old property */
167  				for_each_label_withdel(new_prop->labels, l)
168  					add_label(&old_prop->labels, l->label);
169  
170  				old_prop->val = new_prop->val;
171  				old_prop->deleted = 0;
172  				free(new_prop);
173  				new_prop = NULL;
174  				break;
175  			}
176  		}
177  
178  		/* if no collision occurred, add property to the old node. */
179  		if (new_prop)
180  			add_property(old_node, new_prop);
181  	}
182  
183  	/* Move the override child nodes into the primary node.  If
184  	 * there is a collision, then merge the nodes. */
185  	while (new_node->children) {
186  		/* Pop the child node off the list */
187  		new_child = new_node->children;
188  		new_node->children = new_child->next_sibling;
189  		new_child->parent = NULL;
190  		new_child->next_sibling = NULL;
191  
192  		if (new_child->deleted) {
193  			delete_node_by_name(old_node, new_child->name);
194  			free(new_child);
195  			continue;
196  		}
197  
198  		/* Search for a collision.  Merge if there is */
199  		for_each_child_withdel(old_node, old_child) {
200  			if (streq(old_child->name, new_child->name)) {
201  				merge_nodes(old_child, new_child);
202  				new_child = NULL;
203  				break;
204  			}
205  		}
206  
207  		/* if no collision occured, add child to the old node. */
208  		if (new_child)
209  			add_child(old_node, new_child);
210  	}
211  
212  	/* The new node contents are now merged into the old node.  Free
213  	 * the new node. */
214  	free(new_node);
215  
216  	return old_node;
217  }
218  
219  struct node *chain_node(struct node *first, struct node *list)
220  {
221  	assert(first->next_sibling == NULL);
222  
223  	first->next_sibling = list;
224  	return first;
225  }
226  
227  void add_property(struct node *node, struct property *prop)
228  {
229  	struct property **p;
230  
231  	prop->next = NULL;
232  
233  	p = &node->proplist;
234  	while (*p)
235  		p = &((*p)->next);
236  
237  	*p = prop;
238  }
239  
240  void delete_property_by_name(struct node *node, char *name)
241  {
242  	struct property *prop = node->proplist;
243  
244  	while (prop) {
245  		if (!strcmp(prop->name, name)) {
246  			delete_property(prop);
247  			return;
248  		}
249  		prop = prop->next;
250  	}
251  }
252  
253  void delete_property(struct property *prop)
254  {
255  	prop->deleted = 1;
256  	delete_labels(&prop->labels);
257  }
258  
259  void add_child(struct node *parent, struct node *child)
260  {
261  	struct node **p;
262  
263  	child->next_sibling = NULL;
264  	child->parent = parent;
265  
266  	p = &parent->children;
267  	while (*p)
268  		p = &((*p)->next_sibling);
269  
270  	*p = child;
271  }
272  
273  void delete_node_by_name(struct node *parent, char *name)
274  {
275  	struct node *node = parent->children;
276  
277  	while (node) {
278  		if (!strcmp(node->name, name)) {
279  			delete_node(node);
280  			return;
281  		}
282  		node = node->next_sibling;
283  	}
284  }
285  
286  void delete_node(struct node *node)
287  {
288  	struct property *prop;
289  	struct node *child;
290  
291  	node->deleted = 1;
292  	for_each_child(node, child)
293  		delete_node(child);
294  	for_each_property(node, prop)
295  		delete_property(prop);
296  	delete_labels(&node->labels);
297  }
298  
299  struct reserve_info *build_reserve_entry(uint64_t address, uint64_t size)
300  {
301  	struct reserve_info *new = xmalloc(sizeof(*new));
302  
303  	memset(new, 0, sizeof(*new));
304  
305  	new->re.address = address;
306  	new->re.size = size;
307  
308  	return new;
309  }
310  
311  struct reserve_info *chain_reserve_entry(struct reserve_info *first,
312  					struct reserve_info *list)
313  {
314  	assert(first->next == NULL);
315  
316  	first->next = list;
317  	return first;
318  }
319  
320  struct reserve_info *add_reserve_entry(struct reserve_info *list,
321  				      struct reserve_info *new)
322  {
323  	struct reserve_info *last;
324  
325  	new->next = NULL;
326  
327  	if (! list)
328  		return new;
329  
330  	for (last = list; last->next; last = last->next)
331  		;
332  
333  	last->next = new;
334  
335  	return list;
336  }
337  
338  struct boot_info *build_boot_info(struct reserve_info *reservelist,
339  				  struct node *tree, uint32_t boot_cpuid_phys)
340  {
341  	struct boot_info *bi;
342  
343  	bi = xmalloc(sizeof(*bi));
344  	bi->reservelist = reservelist;
345  	bi->dt = tree;
346  	bi->boot_cpuid_phys = boot_cpuid_phys;
347  
348  	return bi;
349  }
350  
351  /*
352   * Tree accessor functions
353   */
354  
355  const char *get_unitname(struct node *node)
356  {
357  	if (node->name[node->basenamelen] == '\0')
358  		return "";
359  	else
360  		return node->name + node->basenamelen + 1;
361  }
362  
363  struct property *get_property(struct node *node, const char *propname)
364  {
365  	struct property *prop;
366  
367  	for_each_property(node, prop)
368  		if (streq(prop->name, propname))
369  			return prop;
370  
371  	return NULL;
372  }
373  
374  cell_t propval_cell(struct property *prop)
375  {
376  	assert(prop->val.len == sizeof(cell_t));
377  	return fdt32_to_cpu(*((cell_t *)prop->val.val));
378  }
379  
380  struct property *get_property_by_label(struct node *tree, const char *label,
381  				       struct node **node)
382  {
383  	struct property *prop;
384  	struct node *c;
385  
386  	*node = tree;
387  
388  	for_each_property(tree, prop) {
389  		struct label *l;
390  
391  		for_each_label(prop->labels, l)
392  			if (streq(l->label, label))
393  				return prop;
394  	}
395  
396  	for_each_child(tree, c) {
397  		prop = get_property_by_label(c, label, node);
398  		if (prop)
399  			return prop;
400  	}
401  
402  	*node = NULL;
403  	return NULL;
404  }
405  
406  struct marker *get_marker_label(struct node *tree, const char *label,
407  				struct node **node, struct property **prop)
408  {
409  	struct marker *m;
410  	struct property *p;
411  	struct node *c;
412  
413  	*node = tree;
414  
415  	for_each_property(tree, p) {
416  		*prop = p;
417  		m = p->val.markers;
418  		for_each_marker_of_type(m, LABEL)
419  			if (streq(m->ref, label))
420  				return m;
421  	}
422  
423  	for_each_child(tree, c) {
424  		m = get_marker_label(c, label, node, prop);
425  		if (m)
426  			return m;
427  	}
428  
429  	*prop = NULL;
430  	*node = NULL;
431  	return NULL;
432  }
433  
434  struct node *get_subnode(struct node *node, const char *nodename)
435  {
436  	struct node *child;
437  
438  	for_each_child(node, child)
439  		if (streq(child->name, nodename))
440  			return child;
441  
442  	return NULL;
443  }
444  
445  struct node *get_node_by_path(struct node *tree, const char *path)
446  {
447  	const char *p;
448  	struct node *child;
449  
450  	if (!path || ! (*path)) {
451  		if (tree->deleted)
452  			return NULL;
453  		return tree;
454  	}
455  
456  	while (path[0] == '/')
457  		path++;
458  
459  	p = strchr(path, '/');
460  
461  	for_each_child(tree, child) {
462  		if (p && strneq(path, child->name, p-path))
463  			return get_node_by_path(child, p+1);
464  		else if (!p && streq(path, child->name))
465  			return child;
466  	}
467  
468  	return NULL;
469  }
470  
471  struct node *get_node_by_label(struct node *tree, const char *label)
472  {
473  	struct node *child, *node;
474  	struct label *l;
475  
476  	assert(label && (strlen(label) > 0));
477  
478  	for_each_label(tree->labels, l)
479  		if (streq(l->label, label))
480  			return tree;
481  
482  	for_each_child(tree, child) {
483  		node = get_node_by_label(child, label);
484  		if (node)
485  			return node;
486  	}
487  
488  	return NULL;
489  }
490  
491  struct node *get_node_by_phandle(struct node *tree, cell_t phandle)
492  {
493  	struct node *child, *node;
494  
495  	assert((phandle != 0) && (phandle != -1));
496  
497  	if (tree->phandle == phandle) {
498  		if (tree->deleted)
499  			return NULL;
500  		return tree;
501  	}
502  
503  	for_each_child(tree, child) {
504  		node = get_node_by_phandle(child, phandle);
505  		if (node)
506  			return node;
507  	}
508  
509  	return NULL;
510  }
511  
512  struct node *get_node_by_ref(struct node *tree, const char *ref)
513  {
514  	if (streq(ref, "/"))
515  		return tree;
516  	else if (ref[0] == '/')
517  		return get_node_by_path(tree, ref);
518  	else
519  		return get_node_by_label(tree, ref);
520  }
521  
522  cell_t get_node_phandle(struct node *root, struct node *node)
523  {
524  	static cell_t phandle = 1; /* FIXME: ick, static local */
525  
526  	if ((node->phandle != 0) && (node->phandle != -1))
527  		return node->phandle;
528  
529  	while (get_node_by_phandle(root, phandle))
530  		phandle++;
531  
532  	node->phandle = phandle;
533  
534  	if (!get_property(node, "linux,phandle")
535  	    && (phandle_format & PHANDLE_LEGACY))
536  		add_property(node,
537  			     build_property("linux,phandle",
538  					    data_append_cell(empty_data, phandle)));
539  
540  	if (!get_property(node, "phandle")
541  	    && (phandle_format & PHANDLE_EPAPR))
542  		add_property(node,
543  			     build_property("phandle",
544  					    data_append_cell(empty_data, phandle)));
545  
546  	/* If the node *does* have a phandle property, we must
547  	 * be dealing with a self-referencing phandle, which will be
548  	 * fixed up momentarily in the caller */
549  
550  	return node->phandle;
551  }
552  
553  uint32_t guess_boot_cpuid(struct node *tree)
554  {
555  	struct node *cpus, *bootcpu;
556  	struct property *reg;
557  
558  	cpus = get_node_by_path(tree, "/cpus");
559  	if (!cpus)
560  		return 0;
561  
562  
563  	bootcpu = cpus->children;
564  	if (!bootcpu)
565  		return 0;
566  
567  	reg = get_property(bootcpu, "reg");
568  	if (!reg || (reg->val.len != sizeof(uint32_t)))
569  		return 0;
570  
571  	/* FIXME: Sanity check node? */
572  
573  	return propval_cell(reg);
574  }
575  
576  static int cmp_reserve_info(const void *ax, const void *bx)
577  {
578  	const struct reserve_info *a, *b;
579  
580  	a = *((const struct reserve_info * const *)ax);
581  	b = *((const struct reserve_info * const *)bx);
582  
583  	if (a->re.address < b->re.address)
584  		return -1;
585  	else if (a->re.address > b->re.address)
586  		return 1;
587  	else if (a->re.size < b->re.size)
588  		return -1;
589  	else if (a->re.size > b->re.size)
590  		return 1;
591  	else
592  		return 0;
593  }
594  
595  static void sort_reserve_entries(struct boot_info *bi)
596  {
597  	struct reserve_info *ri, **tbl;
598  	int n = 0, i = 0;
599  
600  	for (ri = bi->reservelist;
601  	     ri;
602  	     ri = ri->next)
603  		n++;
604  
605  	if (n == 0)
606  		return;
607  
608  	tbl = xmalloc(n * sizeof(*tbl));
609  
610  	for (ri = bi->reservelist;
611  	     ri;
612  	     ri = ri->next)
613  		tbl[i++] = ri;
614  
615  	qsort(tbl, n, sizeof(*tbl), cmp_reserve_info);
616  
617  	bi->reservelist = tbl[0];
618  	for (i = 0; i < (n-1); i++)
619  		tbl[i]->next = tbl[i+1];
620  	tbl[n-1]->next = NULL;
621  
622  	free(tbl);
623  }
624  
625  static int cmp_prop(const void *ax, const void *bx)
626  {
627  	const struct property *a, *b;
628  
629  	a = *((const struct property * const *)ax);
630  	b = *((const struct property * const *)bx);
631  
632  	return strcmp(a->name, b->name);
633  }
634  
635  static void sort_properties(struct node *node)
636  {
637  	int n = 0, i = 0;
638  	struct property *prop, **tbl;
639  
640  	for_each_property_withdel(node, prop)
641  		n++;
642  
643  	if (n == 0)
644  		return;
645  
646  	tbl = xmalloc(n * sizeof(*tbl));
647  
648  	for_each_property_withdel(node, prop)
649  		tbl[i++] = prop;
650  
651  	qsort(tbl, n, sizeof(*tbl), cmp_prop);
652  
653  	node->proplist = tbl[0];
654  	for (i = 0; i < (n-1); i++)
655  		tbl[i]->next = tbl[i+1];
656  	tbl[n-1]->next = NULL;
657  
658  	free(tbl);
659  }
660  
661  static int cmp_subnode(const void *ax, const void *bx)
662  {
663  	const struct node *a, *b;
664  
665  	a = *((const struct node * const *)ax);
666  	b = *((const struct node * const *)bx);
667  
668  	return strcmp(a->name, b->name);
669  }
670  
671  static void sort_subnodes(struct node *node)
672  {
673  	int n = 0, i = 0;
674  	struct node *subnode, **tbl;
675  
676  	for_each_child_withdel(node, subnode)
677  		n++;
678  
679  	if (n == 0)
680  		return;
681  
682  	tbl = xmalloc(n * sizeof(*tbl));
683  
684  	for_each_child_withdel(node, subnode)
685  		tbl[i++] = subnode;
686  
687  	qsort(tbl, n, sizeof(*tbl), cmp_subnode);
688  
689  	node->children = tbl[0];
690  	for (i = 0; i < (n-1); i++)
691  		tbl[i]->next_sibling = tbl[i+1];
692  	tbl[n-1]->next_sibling = NULL;
693  
694  	free(tbl);
695  }
696  
697  static void sort_node(struct node *node)
698  {
699  	struct node *c;
700  
701  	sort_properties(node);
702  	sort_subnodes(node);
703  	for_each_child_withdel(node, c)
704  		sort_node(c);
705  }
706  
707  void sort_tree(struct boot_info *bi)
708  {
709  	sort_reserve_entries(bi);
710  	sort_node(bi->dt);
711  }
712