Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
livetree.c
Go to the documentation of this file.
1 /*
2  * (C) Copyright David Gibson <[email protected]>, 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 
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 
78 {
79  assert(first->next == NULL);
80 
81  first->next = list;
82  return first;
83 }
84 
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 
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 
312  struct reserve_info *list)
313 {
314  assert(first->next == NULL);
315 
316  first->next = list;
317  return first;
318 }
319 
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 
340 {
341  struct boot_info *bi;
342 
343  bi = xmalloc(sizeof(*bi));
344  bi->reservelist = reservelist;
345  bi->dt = tree;
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 
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;
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 
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 (ref[0] == '/')
515  return get_node_by_path(tree, ref);
516  else
517  return get_node_by_label(tree, ref);
518 }
519 
520 cell_t get_node_phandle(struct node *root, struct node *node)
521 {
522  static cell_t phandle = 1; /* FIXME: ick, static local */
523 
524  if ((node->phandle != 0) && (node->phandle != -1))
525  return node->phandle;
526 
527  while (get_node_by_phandle(root, phandle))
528  phandle++;
529 
530  node->phandle = phandle;
531 
532  if (!get_property(node, "linux,phandle")
534  add_property(node,
535  build_property("linux,phandle",
536  data_append_cell(empty_data, phandle)));
537 
538  if (!get_property(node, "phandle")
540  add_property(node,
541  build_property("phandle",
542  data_append_cell(empty_data, phandle)));
543 
544  /* If the node *does* have a phandle property, we must
545  * be dealing with a self-referencing phandle, which will be
546  * fixed up momentarily in the caller */
547 
548  return node->phandle;
549 }
550 
552 {
553  struct node *cpus, *bootcpu;
554  struct property *reg;
555 
556  cpus = get_node_by_path(tree, "/cpus");
557  if (!cpus)
558  return 0;
559 
560 
561  bootcpu = cpus->children;
562  if (!bootcpu)
563  return 0;
564 
565  reg = get_property(bootcpu, "reg");
566  if (!reg || (reg->val.len != sizeof(uint32_t)))
567  return 0;
568 
569  /* FIXME: Sanity check node? */
570 
571  return propval_cell(reg);
572 }
573 
574 static int cmp_reserve_info(const void *ax, const void *bx)
575 {
576  const struct reserve_info *a, *b;
577 
578  a = *((const struct reserve_info * const *)ax);
579  b = *((const struct reserve_info * const *)bx);
580 
581  if (a->re.address < b->re.address)
582  return -1;
583  else if (a->re.address > b->re.address)
584  return 1;
585  else if (a->re.size < b->re.size)
586  return -1;
587  else if (a->re.size > b->re.size)
588  return 1;
589  else
590  return 0;
591 }
592 
593 static void sort_reserve_entries(struct boot_info *bi)
594 {
595  struct reserve_info *ri, **tbl;
596  int n = 0, i = 0;
597 
598  for (ri = bi->reservelist;
599  ri;
600  ri = ri->next)
601  n++;
602 
603  if (n == 0)
604  return;
605 
606  tbl = xmalloc(n * sizeof(*tbl));
607 
608  for (ri = bi->reservelist;
609  ri;
610  ri = ri->next)
611  tbl[i++] = ri;
612 
613  qsort(tbl, n, sizeof(*tbl), cmp_reserve_info);
614 
615  bi->reservelist = tbl[0];
616  for (i = 0; i < (n-1); i++)
617  tbl[i]->next = tbl[i+1];
618  tbl[n-1]->next = NULL;
619 
620  free(tbl);
621 }
622 
623 static int cmp_prop(const void *ax, const void *bx)
624 {
625  const struct property *a, *b;
626 
627  a = *((const struct property * const *)ax);
628  b = *((const struct property * const *)bx);
629 
630  return strcmp(a->name, b->name);
631 }
632 
633 static void sort_properties(struct node *node)
634 {
635  int n = 0, i = 0;
636  struct property *prop, **tbl;
637 
638  for_each_property_withdel(node, prop)
639  n++;
640 
641  if (n == 0)
642  return;
643 
644  tbl = xmalloc(n * sizeof(*tbl));
645 
646  for_each_property_withdel(node, prop)
647  tbl[i++] = prop;
648 
649  qsort(tbl, n, sizeof(*tbl), cmp_prop);
650 
651  node->proplist = tbl[0];
652  for (i = 0; i < (n-1); i++)
653  tbl[i]->next = tbl[i+1];
654  tbl[n-1]->next = NULL;
655 
656  free(tbl);
657 }
658 
659 static int cmp_subnode(const void *ax, const void *bx)
660 {
661  const struct node *a, *b;
662 
663  a = *((const struct node * const *)ax);
664  b = *((const struct node * const *)bx);
665 
666  return strcmp(a->name, b->name);
667 }
668 
669 static void sort_subnodes(struct node *node)
670 {
671  int n = 0, i = 0;
672  struct node *subnode, **tbl;
673 
674  for_each_child_withdel(node, subnode)
675  n++;
676 
677  if (n == 0)
678  return;
679 
680  tbl = xmalloc(n * sizeof(*tbl));
681 
682  for_each_child_withdel(node, subnode)
683  tbl[i++] = subnode;
684 
685  qsort(tbl, n, sizeof(*tbl), cmp_subnode);
686 
687  node->children = tbl[0];
688  for (i = 0; i < (n-1); i++)
689  tbl[i]->next_sibling = tbl[i+1];
690  tbl[n-1]->next_sibling = NULL;
691 
692  free(tbl);
693 }
694 
695 static void sort_node(struct node *node)
696 {
697  struct node *c;
698 
699  sort_properties(node);
700  sort_subnodes(node);
701  for_each_child_withdel(node, c)
702  sort_node(c);
703 }
704 
706 {
707  sort_reserve_entries(bi);
708  sort_node(bi->dt);
709 }