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 */ | |
32 | for_each_label(*labels, new) | |
33 | if (streq(new->label, label)) | |
34 | return; | |
35 | ||
36 | new = xmalloc(sizeof(*new)); | |
37 | new->label = label; | |
38 | new->next = *labels; | |
39 | *labels = new; | |
40 | } | |
41 | ||
42 | struct property *build_property(char *name, struct data val) | |
a4da2e3e DG |
43 | { |
44 | struct property *new = xmalloc(sizeof(*new)); | |
45 | ||
658f29a5 JB |
46 | memset(new, 0, sizeof(*new)); |
47 | ||
a4da2e3e DG |
48 | new->name = name; |
49 | new->val = val; | |
50 | ||
a4da2e3e DG |
51 | return new; |
52 | } | |
53 | ||
54 | struct property *chain_property(struct property *first, struct property *list) | |
55 | { | |
56 | assert(first->next == NULL); | |
57 | ||
58 | first->next = list; | |
59 | return first; | |
60 | } | |
61 | ||
62 | struct property *reverse_properties(struct property *first) | |
63 | { | |
64 | struct property *p = first; | |
65 | struct property *head = NULL; | |
66 | struct property *next; | |
67 | ||
68 | while (p) { | |
69 | next = p->next; | |
70 | p->next = head; | |
71 | head = p; | |
72 | p = next; | |
73 | } | |
74 | return head; | |
75 | } | |
76 | ||
77 | struct node *build_node(struct property *proplist, struct node *children) | |
78 | { | |
79 | struct node *new = xmalloc(sizeof(*new)); | |
80 | struct node *child; | |
81 | ||
82 | memset(new, 0, sizeof(*new)); | |
83 | ||
84 | new->proplist = reverse_properties(proplist); | |
85 | new->children = children; | |
86 | ||
87 | for_each_child(new, child) { | |
88 | child->parent = new; | |
89 | } | |
90 | ||
91 | return new; | |
92 | } | |
93 | ||
658f29a5 | 94 | struct node *name_node(struct node *node, char *name) |
a4da2e3e DG |
95 | { |
96 | assert(node->name == NULL); | |
97 | ||
98 | node->name = name; | |
99 | ||
a4da2e3e DG |
100 | return node; |
101 | } | |
102 | ||
658f29a5 JB |
103 | struct node *merge_nodes(struct node *old_node, struct node *new_node) |
104 | { | |
105 | struct property *new_prop, *old_prop; | |
106 | struct node *new_child, *old_child; | |
107 | struct label *l; | |
108 | ||
109 | /* Add new node labels to old node */ | |
110 | for_each_label(new_node->labels, l) | |
111 | add_label(&old_node->labels, l->label); | |
112 | ||
113 | /* Move properties from the new node to the old node. If there | |
114 | * is a collision, replace the old value with the new */ | |
115 | while (new_node->proplist) { | |
116 | /* Pop the property off the list */ | |
117 | new_prop = new_node->proplist; | |
118 | new_node->proplist = new_prop->next; | |
119 | new_prop->next = NULL; | |
120 | ||
121 | /* Look for a collision, set new value if there is */ | |
122 | for_each_property(old_node, old_prop) { | |
123 | if (streq(old_prop->name, new_prop->name)) { | |
124 | /* Add new labels to old property */ | |
125 | for_each_label(new_prop->labels, l) | |
126 | add_label(&old_prop->labels, l->label); | |
127 | ||
128 | old_prop->val = new_prop->val; | |
129 | free(new_prop); | |
130 | new_prop = NULL; | |
131 | break; | |
132 | } | |
133 | } | |
134 | ||
135 | /* if no collision occurred, add property to the old node. */ | |
136 | if (new_prop) | |
137 | add_property(old_node, new_prop); | |
138 | } | |
139 | ||
140 | /* Move the override child nodes into the primary node. If | |
141 | * there is a collision, then merge the nodes. */ | |
142 | while (new_node->children) { | |
143 | /* Pop the child node off the list */ | |
144 | new_child = new_node->children; | |
145 | new_node->children = new_child->next_sibling; | |
146 | new_child->parent = NULL; | |
147 | new_child->next_sibling = NULL; | |
148 | ||
149 | /* Search for a collision. Merge if there is */ | |
150 | for_each_child(old_node, old_child) { | |
151 | if (streq(old_child->name, new_child->name)) { | |
152 | merge_nodes(old_child, new_child); | |
153 | new_child = NULL; | |
154 | break; | |
155 | } | |
156 | } | |
157 | ||
25985edc | 158 | /* if no collision occurred, add child to the old node. */ |
658f29a5 JB |
159 | if (new_child) |
160 | add_child(old_node, new_child); | |
161 | } | |
162 | ||
163 | /* The new node contents are now merged into the old node. Free | |
164 | * the new node. */ | |
165 | free(new_node); | |
166 | ||
167 | return old_node; | |
168 | } | |
169 | ||
a4da2e3e DG |
170 | struct node *chain_node(struct node *first, struct node *list) |
171 | { | |
172 | assert(first->next_sibling == NULL); | |
173 | ||
174 | first->next_sibling = list; | |
175 | return first; | |
176 | } | |
177 | ||
178 | void add_property(struct node *node, struct property *prop) | |
179 | { | |
180 | struct property **p; | |
181 | ||
182 | prop->next = NULL; | |
183 | ||
184 | p = &node->proplist; | |
185 | while (*p) | |
186 | p = &((*p)->next); | |
187 | ||
188 | *p = prop; | |
189 | } | |
190 | ||
191 | void add_child(struct node *parent, struct node *child) | |
192 | { | |
193 | struct node **p; | |
194 | ||
195 | child->next_sibling = NULL; | |
ed95d745 | 196 | child->parent = parent; |
a4da2e3e DG |
197 | |
198 | p = &parent->children; | |
199 | while (*p) | |
200 | p = &((*p)->next_sibling); | |
201 | ||
202 | *p = child; | |
203 | } | |
204 | ||
658f29a5 | 205 | struct reserve_info *build_reserve_entry(uint64_t address, uint64_t size) |
a4da2e3e DG |
206 | { |
207 | struct reserve_info *new = xmalloc(sizeof(*new)); | |
208 | ||
658f29a5 JB |
209 | memset(new, 0, sizeof(*new)); |
210 | ||
a4da2e3e DG |
211 | new->re.address = address; |
212 | new->re.size = size; | |
213 | ||
a4da2e3e DG |
214 | return new; |
215 | } | |
216 | ||
217 | struct reserve_info *chain_reserve_entry(struct reserve_info *first, | |
218 | struct reserve_info *list) | |
219 | { | |
220 | assert(first->next == NULL); | |
221 | ||
222 | first->next = list; | |
223 | return first; | |
224 | } | |
225 | ||
226 | struct reserve_info *add_reserve_entry(struct reserve_info *list, | |
227 | struct reserve_info *new) | |
228 | { | |
229 | struct reserve_info *last; | |
230 | ||
231 | new->next = NULL; | |
232 | ||
233 | if (! list) | |
234 | return new; | |
235 | ||
236 | for (last = list; last->next; last = last->next) | |
237 | ; | |
238 | ||
239 | last->next = new; | |
240 | ||
241 | return list; | |
242 | } | |
243 | ||
244 | struct boot_info *build_boot_info(struct reserve_info *reservelist, | |
ed95d745 | 245 | struct node *tree, uint32_t boot_cpuid_phys) |
a4da2e3e DG |
246 | { |
247 | struct boot_info *bi; | |
248 | ||
249 | bi = xmalloc(sizeof(*bi)); | |
250 | bi->reservelist = reservelist; | |
251 | bi->dt = tree; | |
ed95d745 | 252 | bi->boot_cpuid_phys = boot_cpuid_phys; |
a4da2e3e DG |
253 | |
254 | return bi; | |
255 | } | |
256 | ||
257 | /* | |
258 | * Tree accessor functions | |
259 | */ | |
260 | ||
261 | const char *get_unitname(struct node *node) | |
262 | { | |
263 | if (node->name[node->basenamelen] == '\0') | |
264 | return ""; | |
265 | else | |
266 | return node->name + node->basenamelen + 1; | |
267 | } | |
268 | ||
269 | struct property *get_property(struct node *node, const char *propname) | |
270 | { | |
271 | struct property *prop; | |
272 | ||
273 | for_each_property(node, prop) | |
274 | if (streq(prop->name, propname)) | |
275 | return prop; | |
276 | ||
277 | return NULL; | |
278 | } | |
279 | ||
280 | cell_t propval_cell(struct property *prop) | |
281 | { | |
282 | assert(prop->val.len == sizeof(cell_t)); | |
ed95d745 | 283 | return fdt32_to_cpu(*((cell_t *)prop->val.val)); |
a4da2e3e DG |
284 | } |
285 | ||
658f29a5 JB |
286 | struct property *get_property_by_label(struct node *tree, const char *label, |
287 | struct node **node) | |
288 | { | |
289 | struct property *prop; | |
290 | struct node *c; | |
291 | ||
292 | *node = tree; | |
293 | ||
294 | for_each_property(tree, prop) { | |
295 | struct label *l; | |
296 | ||
297 | for_each_label(prop->labels, l) | |
298 | if (streq(l->label, label)) | |
299 | return prop; | |
300 | } | |
301 | ||
302 | for_each_child(tree, c) { | |
303 | prop = get_property_by_label(c, label, node); | |
304 | if (prop) | |
305 | return prop; | |
306 | } | |
307 | ||
308 | *node = NULL; | |
309 | return NULL; | |
310 | } | |
311 | ||
312 | struct marker *get_marker_label(struct node *tree, const char *label, | |
313 | struct node **node, struct property **prop) | |
314 | { | |
315 | struct marker *m; | |
316 | struct property *p; | |
317 | struct node *c; | |
318 | ||
319 | *node = tree; | |
320 | ||
321 | for_each_property(tree, p) { | |
322 | *prop = p; | |
323 | m = p->val.markers; | |
324 | for_each_marker_of_type(m, LABEL) | |
325 | if (streq(m->ref, label)) | |
326 | return m; | |
327 | } | |
328 | ||
329 | for_each_child(tree, c) { | |
330 | m = get_marker_label(c, label, node, prop); | |
331 | if (m) | |
332 | return m; | |
333 | } | |
334 | ||
335 | *prop = NULL; | |
336 | *node = NULL; | |
337 | return NULL; | |
338 | } | |
339 | ||
a4da2e3e DG |
340 | struct node *get_subnode(struct node *node, const char *nodename) |
341 | { | |
342 | struct node *child; | |
343 | ||
344 | for_each_child(node, child) | |
345 | if (streq(child->name, nodename)) | |
346 | return child; | |
347 | ||
348 | return NULL; | |
349 | } | |
350 | ||
351 | struct node *get_node_by_path(struct node *tree, const char *path) | |
352 | { | |
353 | const char *p; | |
354 | struct node *child; | |
355 | ||
356 | if (!path || ! (*path)) | |
357 | return tree; | |
358 | ||
359 | while (path[0] == '/') | |
360 | path++; | |
361 | ||
362 | p = strchr(path, '/'); | |
363 | ||
364 | for_each_child(tree, child) { | |
365 | if (p && strneq(path, child->name, p-path)) | |
366 | return get_node_by_path(child, p+1); | |
367 | else if (!p && streq(path, child->name)) | |
368 | return child; | |
369 | } | |
370 | ||
371 | return NULL; | |
372 | } | |
373 | ||
374 | struct node *get_node_by_label(struct node *tree, const char *label) | |
375 | { | |
376 | struct node *child, *node; | |
658f29a5 | 377 | struct label *l; |
a4da2e3e DG |
378 | |
379 | assert(label && (strlen(label) > 0)); | |
380 | ||
658f29a5 JB |
381 | for_each_label(tree->labels, l) |
382 | if (streq(l->label, label)) | |
383 | return tree; | |
a4da2e3e DG |
384 | |
385 | for_each_child(tree, child) { | |
386 | node = get_node_by_label(child, label); | |
387 | if (node) | |
388 | return node; | |
389 | } | |
390 | ||
391 | return NULL; | |
392 | } | |
393 | ||
394 | struct node *get_node_by_phandle(struct node *tree, cell_t phandle) | |
395 | { | |
396 | struct node *child, *node; | |
397 | ||
398 | assert((phandle != 0) && (phandle != -1)); | |
399 | ||
400 | if (tree->phandle == phandle) | |
401 | return tree; | |
402 | ||
403 | for_each_child(tree, child) { | |
404 | node = get_node_by_phandle(child, phandle); | |
405 | if (node) | |
406 | return node; | |
407 | } | |
408 | ||
409 | return NULL; | |
410 | } | |
411 | ||
412 | struct node *get_node_by_ref(struct node *tree, const char *ref) | |
413 | { | |
414 | if (ref[0] == '/') | |
415 | return get_node_by_path(tree, ref); | |
416 | else | |
417 | return get_node_by_label(tree, ref); | |
418 | } | |
419 | ||
420 | cell_t get_node_phandle(struct node *root, struct node *node) | |
421 | { | |
422 | static cell_t phandle = 1; /* FIXME: ick, static local */ | |
423 | ||
424 | if ((node->phandle != 0) && (node->phandle != -1)) | |
425 | return node->phandle; | |
426 | ||
a4da2e3e DG |
427 | while (get_node_by_phandle(root, phandle)) |
428 | phandle++; | |
429 | ||
430 | node->phandle = phandle; | |
658f29a5 JB |
431 | |
432 | if (!get_property(node, "linux,phandle") | |
433 | && (phandle_format & PHANDLE_LEGACY)) | |
434 | add_property(node, | |
435 | build_property("linux,phandle", | |
436 | data_append_cell(empty_data, phandle))); | |
437 | ||
438 | if (!get_property(node, "phandle") | |
439 | && (phandle_format & PHANDLE_EPAPR)) | |
440 | add_property(node, | |
441 | build_property("phandle", | |
442 | data_append_cell(empty_data, phandle))); | |
443 | ||
444 | /* If the node *does* have a phandle property, we must | |
445 | * be dealing with a self-referencing phandle, which will be | |
446 | * fixed up momentarily in the caller */ | |
a4da2e3e DG |
447 | |
448 | return node->phandle; | |
449 | } | |
658f29a5 JB |
450 | |
451 | uint32_t guess_boot_cpuid(struct node *tree) | |
452 | { | |
453 | struct node *cpus, *bootcpu; | |
454 | struct property *reg; | |
455 | ||
456 | cpus = get_node_by_path(tree, "/cpus"); | |
457 | if (!cpus) | |
458 | return 0; | |
459 | ||
460 | ||
461 | bootcpu = cpus->children; | |
462 | if (!bootcpu) | |
463 | return 0; | |
464 | ||
465 | reg = get_property(bootcpu, "reg"); | |
466 | if (!reg || (reg->val.len != sizeof(uint32_t))) | |
467 | return 0; | |
468 | ||
469 | /* FIXME: Sanity check node? */ | |
470 | ||
471 | return propval_cell(reg); | |
472 | } | |
473 | ||
474 | static int cmp_reserve_info(const void *ax, const void *bx) | |
475 | { | |
476 | const struct reserve_info *a, *b; | |
477 | ||
478 | a = *((const struct reserve_info * const *)ax); | |
479 | b = *((const struct reserve_info * const *)bx); | |
480 | ||
481 | if (a->re.address < b->re.address) | |
482 | return -1; | |
483 | else if (a->re.address > b->re.address) | |
484 | return 1; | |
485 | else if (a->re.size < b->re.size) | |
486 | return -1; | |
487 | else if (a->re.size > b->re.size) | |
488 | return 1; | |
489 | else | |
490 | return 0; | |
491 | } | |
492 | ||
493 | static void sort_reserve_entries(struct boot_info *bi) | |
494 | { | |
495 | struct reserve_info *ri, **tbl; | |
496 | int n = 0, i = 0; | |
497 | ||
498 | for (ri = bi->reservelist; | |
499 | ri; | |
500 | ri = ri->next) | |
501 | n++; | |
502 | ||
503 | if (n == 0) | |
504 | return; | |
505 | ||
506 | tbl = xmalloc(n * sizeof(*tbl)); | |
507 | ||
508 | for (ri = bi->reservelist; | |
509 | ri; | |
510 | ri = ri->next) | |
511 | tbl[i++] = ri; | |
512 | ||
513 | qsort(tbl, n, sizeof(*tbl), cmp_reserve_info); | |
514 | ||
515 | bi->reservelist = tbl[0]; | |
516 | for (i = 0; i < (n-1); i++) | |
517 | tbl[i]->next = tbl[i+1]; | |
518 | tbl[n-1]->next = NULL; | |
519 | ||
520 | free(tbl); | |
521 | } | |
522 | ||
523 | static int cmp_prop(const void *ax, const void *bx) | |
524 | { | |
525 | const struct property *a, *b; | |
526 | ||
527 | a = *((const struct property * const *)ax); | |
528 | b = *((const struct property * const *)bx); | |
529 | ||
530 | return strcmp(a->name, b->name); | |
531 | } | |
532 | ||
533 | static void sort_properties(struct node *node) | |
534 | { | |
535 | int n = 0, i = 0; | |
536 | struct property *prop, **tbl; | |
537 | ||
538 | for_each_property(node, prop) | |
539 | n++; | |
540 | ||
541 | if (n == 0) | |
542 | return; | |
543 | ||
544 | tbl = xmalloc(n * sizeof(*tbl)); | |
545 | ||
546 | for_each_property(node, prop) | |
547 | tbl[i++] = prop; | |
548 | ||
549 | qsort(tbl, n, sizeof(*tbl), cmp_prop); | |
550 | ||
551 | node->proplist = tbl[0]; | |
552 | for (i = 0; i < (n-1); i++) | |
553 | tbl[i]->next = tbl[i+1]; | |
554 | tbl[n-1]->next = NULL; | |
555 | ||
556 | free(tbl); | |
557 | } | |
558 | ||
559 | static int cmp_subnode(const void *ax, const void *bx) | |
560 | { | |
561 | const struct node *a, *b; | |
562 | ||
563 | a = *((const struct node * const *)ax); | |
564 | b = *((const struct node * const *)bx); | |
565 | ||
566 | return strcmp(a->name, b->name); | |
567 | } | |
568 | ||
569 | static void sort_subnodes(struct node *node) | |
570 | { | |
571 | int n = 0, i = 0; | |
572 | struct node *subnode, **tbl; | |
573 | ||
574 | for_each_child(node, subnode) | |
575 | n++; | |
576 | ||
577 | if (n == 0) | |
578 | return; | |
579 | ||
580 | tbl = xmalloc(n * sizeof(*tbl)); | |
581 | ||
582 | for_each_child(node, subnode) | |
583 | tbl[i++] = subnode; | |
584 | ||
585 | qsort(tbl, n, sizeof(*tbl), cmp_subnode); | |
586 | ||
587 | node->children = tbl[0]; | |
588 | for (i = 0; i < (n-1); i++) | |
589 | tbl[i]->next_sibling = tbl[i+1]; | |
590 | tbl[n-1]->next_sibling = NULL; | |
591 | ||
592 | free(tbl); | |
593 | } | |
594 | ||
595 | static void sort_node(struct node *node) | |
596 | { | |
597 | struct node *c; | |
598 | ||
599 | sort_properties(node); | |
600 | sort_subnodes(node); | |
601 | for_each_child(node, c) | |
602 | sort_node(c); | |
603 | } | |
604 | ||
605 | void sort_tree(struct boot_info *bi) | |
606 | { | |
607 | sort_reserve_entries(bi); | |
608 | sort_node(bi->dt); | |
609 | } |