Commit | Line | Data |
---|---|---|
a4da2e3e DG |
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 | ||
658f29a5 JB |
27 | void add_label(struct label **labels, char *label) |
28 | { | |
29 | struct label *new; | |
30 | ||
31 | /* Make sure the label isn't already there */ | |
cd296721 SW |
32 | for_each_label_withdel(*labels, new) |
33 | if (streq(new->label, label)) { | |
34 | new->deleted = 0; | |
658f29a5 | 35 | return; |
cd296721 | 36 | } |
658f29a5 JB |
37 | |
38 | new = xmalloc(sizeof(*new)); | |
cd296721 | 39 | memset(new, 0, sizeof(*new)); |
658f29a5 JB |
40 | new->label = label; |
41 | new->next = *labels; | |
42 | *labels = new; | |
43 | } | |
44 | ||
cd296721 SW |
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 | ||
658f29a5 | 53 | struct property *build_property(char *name, struct data val) |
a4da2e3e DG |
54 | { |
55 | struct property *new = xmalloc(sizeof(*new)); | |
56 | ||
658f29a5 JB |
57 | memset(new, 0, sizeof(*new)); |
58 | ||
a4da2e3e DG |
59 | new->name = name; |
60 | new->val = val; | |
61 | ||
a4da2e3e DG |
62 | return new; |
63 | } | |
64 | ||
cd296721 SW |
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 | ||
a4da2e3e DG |
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 | ||
cd296721 SW |
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 | ||
658f29a5 | 128 | struct node *name_node(struct node *node, char *name) |
a4da2e3e DG |
129 | { |
130 | assert(node->name == NULL); | |
131 | ||
132 | node->name = name; | |
133 | ||
a4da2e3e DG |
134 | return node; |
135 | } | |
136 | ||
658f29a5 JB |
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 | ||
cd296721 SW |
143 | old_node->deleted = 0; |
144 | ||
658f29a5 | 145 | /* Add new node labels to old node */ |
cd296721 | 146 | for_each_label_withdel(new_node->labels, l) |
658f29a5 JB |
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 | ||
cd296721 SW |
157 | if (new_prop->deleted) { |
158 | delete_property_by_name(old_node, new_prop->name); | |
159 | free(new_prop); | |
160 | continue; | |
161 | } | |
162 | ||
658f29a5 | 163 | /* Look for a collision, set new value if there is */ |
cd296721 | 164 | for_each_property_withdel(old_node, old_prop) { |
658f29a5 JB |
165 | if (streq(old_prop->name, new_prop->name)) { |
166 | /* Add new labels to old property */ | |
cd296721 | 167 | for_each_label_withdel(new_prop->labels, l) |
658f29a5 JB |
168 | add_label(&old_prop->labels, l->label); |
169 | ||
170 | old_prop->val = new_prop->val; | |
cd296721 | 171 | old_prop->deleted = 0; |
658f29a5 JB |
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 | ||
cd296721 SW |
192 | if (new_child->deleted) { |
193 | delete_node_by_name(old_node, new_child->name); | |
194 | free(new_child); | |
195 | continue; | |
196 | } | |
197 | ||
658f29a5 | 198 | /* Search for a collision. Merge if there is */ |
cd296721 | 199 | for_each_child_withdel(old_node, old_child) { |
658f29a5 JB |
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 | ||
cd296721 | 207 | /* if no collision occured, add child to the old node. */ |
658f29a5 JB |
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 | ||
a4da2e3e DG |
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 | ||
cd296721 SW |
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 | ||
a4da2e3e DG |
259 | void add_child(struct node *parent, struct node *child) |
260 | { | |
261 | struct node **p; | |
262 | ||
263 | child->next_sibling = NULL; | |
ed95d745 | 264 | child->parent = parent; |
a4da2e3e DG |
265 | |
266 | p = &parent->children; | |
267 | while (*p) | |
268 | p = &((*p)->next_sibling); | |
269 | ||
270 | *p = child; | |
271 | } | |
272 | ||
cd296721 SW |
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 | ||
658f29a5 | 299 | struct reserve_info *build_reserve_entry(uint64_t address, uint64_t size) |
a4da2e3e DG |
300 | { |
301 | struct reserve_info *new = xmalloc(sizeof(*new)); | |
302 | ||
658f29a5 JB |
303 | memset(new, 0, sizeof(*new)); |
304 | ||
a4da2e3e DG |
305 | new->re.address = address; |
306 | new->re.size = size; | |
307 | ||
a4da2e3e DG |
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, | |
ed95d745 | 339 | struct node *tree, uint32_t boot_cpuid_phys) |
a4da2e3e DG |
340 | { |
341 | struct boot_info *bi; | |
342 | ||
343 | bi = xmalloc(sizeof(*bi)); | |
344 | bi->reservelist = reservelist; | |
345 | bi->dt = tree; | |
ed95d745 | 346 | bi->boot_cpuid_phys = boot_cpuid_phys; |
a4da2e3e DG |
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)); | |
ed95d745 | 377 | return fdt32_to_cpu(*((cell_t *)prop->val.val)); |
a4da2e3e DG |
378 | } |
379 | ||
658f29a5 JB |
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 | ||
a4da2e3e DG |
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 | ||
cd296721 SW |
450 | if (!path || ! (*path)) { |
451 | if (tree->deleted) | |
452 | return NULL; | |
a4da2e3e | 453 | return tree; |
cd296721 | 454 | } |
a4da2e3e DG |
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; | |
658f29a5 | 474 | struct label *l; |
a4da2e3e DG |
475 | |
476 | assert(label && (strlen(label) > 0)); | |
477 | ||
658f29a5 JB |
478 | for_each_label(tree->labels, l) |
479 | if (streq(l->label, label)) | |
480 | return tree; | |
a4da2e3e DG |
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 | ||
cd296721 SW |
497 | if (tree->phandle == phandle) { |
498 | if (tree->deleted) | |
499 | return NULL; | |
a4da2e3e | 500 | return tree; |
cd296721 | 501 | } |
a4da2e3e DG |
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 | ||
a4da2e3e DG |
527 | while (get_node_by_phandle(root, phandle)) |
528 | phandle++; | |
529 | ||
530 | node->phandle = phandle; | |
658f29a5 JB |
531 | |
532 | if (!get_property(node, "linux,phandle") | |
533 | && (phandle_format & PHANDLE_LEGACY)) | |
534 | add_property(node, | |
535 | build_property("linux,phandle", | |
536 | data_append_cell(empty_data, phandle))); | |
537 | ||
538 | if (!get_property(node, "phandle") | |
539 | && (phandle_format & PHANDLE_EPAPR)) | |
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 */ | |
a4da2e3e DG |
547 | |
548 | return node->phandle; | |
549 | } | |
658f29a5 JB |
550 | |
551 | uint32_t guess_boot_cpuid(struct node *tree) | |
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 | ||
cd296721 | 638 | for_each_property_withdel(node, prop) |
658f29a5 JB |
639 | n++; |
640 | ||
641 | if (n == 0) | |
642 | return; | |
643 | ||
644 | tbl = xmalloc(n * sizeof(*tbl)); | |
645 | ||
cd296721 | 646 | for_each_property_withdel(node, prop) |
658f29a5 JB |
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 | ||
cd296721 | 674 | for_each_child_withdel(node, subnode) |
658f29a5 JB |
675 | n++; |
676 | ||
677 | if (n == 0) | |
678 | return; | |
679 | ||
680 | tbl = xmalloc(n * sizeof(*tbl)); | |
681 | ||
cd296721 | 682 | for_each_child_withdel(node, subnode) |
658f29a5 JB |
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); | |
cd296721 | 701 | for_each_child_withdel(node, c) |
658f29a5 JB |
702 | sort_node(c); |
703 | } | |
704 | ||
705 | void sort_tree(struct boot_info *bi) | |
706 | { | |
707 | sort_reserve_entries(bi); | |
708 | sort_node(bi->dt); | |
709 | } |