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 | ||
6f05afcb | 207 | /* if no collision occurred, 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 | ||
9130ba88 | 219 | struct node * add_orphan_node(struct node *dt, struct node *new_node, char *ref) |
4201d057 RH |
220 | { |
221 | static unsigned int next_orphan_fragment = 0; | |
222 | struct node *node; | |
223 | struct property *p; | |
224 | struct data d = empty_data; | |
225 | char *name; | |
226 | ||
227 | d = data_add_marker(d, REF_PHANDLE, ref); | |
228 | d = data_append_integer(d, 0xffffffff, 32); | |
229 | ||
230 | p = build_property("target", d); | |
231 | ||
232 | xasprintf(&name, "fragment@%u", | |
233 | next_orphan_fragment++); | |
234 | name_node(new_node, "__overlay__"); | |
235 | node = build_node(p, new_node); | |
236 | name_node(node, name); | |
237 | ||
238 | add_child(dt, node); | |
9130ba88 | 239 | return dt; |
4201d057 RH |
240 | } |
241 | ||
a4da2e3e DG |
242 | struct node *chain_node(struct node *first, struct node *list) |
243 | { | |
244 | assert(first->next_sibling == NULL); | |
245 | ||
246 | first->next_sibling = list; | |
247 | return first; | |
248 | } | |
249 | ||
250 | void add_property(struct node *node, struct property *prop) | |
251 | { | |
252 | struct property **p; | |
253 | ||
254 | prop->next = NULL; | |
255 | ||
256 | p = &node->proplist; | |
257 | while (*p) | |
258 | p = &((*p)->next); | |
259 | ||
260 | *p = prop; | |
261 | } | |
262 | ||
cd296721 SW |
263 | void delete_property_by_name(struct node *node, char *name) |
264 | { | |
265 | struct property *prop = node->proplist; | |
266 | ||
267 | while (prop) { | |
89d12310 | 268 | if (streq(prop->name, name)) { |
cd296721 SW |
269 | delete_property(prop); |
270 | return; | |
271 | } | |
272 | prop = prop->next; | |
273 | } | |
274 | } | |
275 | ||
276 | void delete_property(struct property *prop) | |
277 | { | |
278 | prop->deleted = 1; | |
279 | delete_labels(&prop->labels); | |
280 | } | |
281 | ||
a4da2e3e DG |
282 | void add_child(struct node *parent, struct node *child) |
283 | { | |
284 | struct node **p; | |
285 | ||
286 | child->next_sibling = NULL; | |
ed95d745 | 287 | child->parent = parent; |
a4da2e3e DG |
288 | |
289 | p = &parent->children; | |
290 | while (*p) | |
291 | p = &((*p)->next_sibling); | |
292 | ||
293 | *p = child; | |
294 | } | |
295 | ||
cd296721 SW |
296 | void delete_node_by_name(struct node *parent, char *name) |
297 | { | |
298 | struct node *node = parent->children; | |
299 | ||
300 | while (node) { | |
89d12310 | 301 | if (streq(node->name, name)) { |
cd296721 SW |
302 | delete_node(node); |
303 | return; | |
304 | } | |
305 | node = node->next_sibling; | |
306 | } | |
307 | } | |
308 | ||
309 | void delete_node(struct node *node) | |
310 | { | |
311 | struct property *prop; | |
312 | struct node *child; | |
313 | ||
314 | node->deleted = 1; | |
315 | for_each_child(node, child) | |
316 | delete_node(child); | |
317 | for_each_property(node, prop) | |
318 | delete_property(prop); | |
319 | delete_labels(&node->labels); | |
320 | } | |
321 | ||
6f05afcb RH |
322 | void append_to_property(struct node *node, |
323 | char *name, const void *data, int len) | |
324 | { | |
325 | struct data d; | |
326 | struct property *p; | |
327 | ||
328 | p = get_property(node, name); | |
329 | if (p) { | |
330 | d = data_append_data(p->val, data, len); | |
331 | p->val = d; | |
332 | } else { | |
333 | d = data_append_data(empty_data, data, len); | |
334 | p = build_property(name, d); | |
335 | add_property(node, p); | |
336 | } | |
337 | } | |
338 | ||
658f29a5 | 339 | struct reserve_info *build_reserve_entry(uint64_t address, uint64_t size) |
a4da2e3e DG |
340 | { |
341 | struct reserve_info *new = xmalloc(sizeof(*new)); | |
342 | ||
658f29a5 JB |
343 | memset(new, 0, sizeof(*new)); |
344 | ||
89d12310 RH |
345 | new->address = address; |
346 | new->size = size; | |
a4da2e3e | 347 | |
a4da2e3e DG |
348 | return new; |
349 | } | |
350 | ||
351 | struct reserve_info *chain_reserve_entry(struct reserve_info *first, | |
352 | struct reserve_info *list) | |
353 | { | |
354 | assert(first->next == NULL); | |
355 | ||
356 | first->next = list; | |
357 | return first; | |
358 | } | |
359 | ||
360 | struct reserve_info *add_reserve_entry(struct reserve_info *list, | |
361 | struct reserve_info *new) | |
362 | { | |
363 | struct reserve_info *last; | |
364 | ||
365 | new->next = NULL; | |
366 | ||
367 | if (! list) | |
368 | return new; | |
369 | ||
370 | for (last = list; last->next; last = last->next) | |
371 | ; | |
372 | ||
373 | last->next = new; | |
374 | ||
375 | return list; | |
376 | } | |
377 | ||
6f05afcb RH |
378 | struct dt_info *build_dt_info(unsigned int dtsflags, |
379 | struct reserve_info *reservelist, | |
380 | struct node *tree, uint32_t boot_cpuid_phys) | |
a4da2e3e | 381 | { |
6f05afcb | 382 | struct dt_info *dti; |
a4da2e3e | 383 | |
6f05afcb RH |
384 | dti = xmalloc(sizeof(*dti)); |
385 | dti->dtsflags = dtsflags; | |
386 | dti->reservelist = reservelist; | |
387 | dti->dt = tree; | |
388 | dti->boot_cpuid_phys = boot_cpuid_phys; | |
a4da2e3e | 389 | |
6f05afcb | 390 | return dti; |
a4da2e3e DG |
391 | } |
392 | ||
393 | /* | |
394 | * Tree accessor functions | |
395 | */ | |
396 | ||
397 | const char *get_unitname(struct node *node) | |
398 | { | |
399 | if (node->name[node->basenamelen] == '\0') | |
400 | return ""; | |
401 | else | |
402 | return node->name + node->basenamelen + 1; | |
403 | } | |
404 | ||
405 | struct property *get_property(struct node *node, const char *propname) | |
406 | { | |
407 | struct property *prop; | |
408 | ||
409 | for_each_property(node, prop) | |
410 | if (streq(prop->name, propname)) | |
411 | return prop; | |
412 | ||
413 | return NULL; | |
414 | } | |
415 | ||
416 | cell_t propval_cell(struct property *prop) | |
417 | { | |
418 | assert(prop->val.len == sizeof(cell_t)); | |
89d12310 | 419 | return fdt32_to_cpu(*((fdt32_t *)prop->val.val)); |
a4da2e3e DG |
420 | } |
421 | ||
4201d057 RH |
422 | cell_t propval_cell_n(struct property *prop, int n) |
423 | { | |
424 | assert(prop->val.len / sizeof(cell_t) >= n); | |
425 | return fdt32_to_cpu(*((fdt32_t *)prop->val.val + n)); | |
426 | } | |
427 | ||
658f29a5 JB |
428 | struct property *get_property_by_label(struct node *tree, const char *label, |
429 | struct node **node) | |
430 | { | |
431 | struct property *prop; | |
432 | struct node *c; | |
433 | ||
434 | *node = tree; | |
435 | ||
436 | for_each_property(tree, prop) { | |
437 | struct label *l; | |
438 | ||
439 | for_each_label(prop->labels, l) | |
440 | if (streq(l->label, label)) | |
441 | return prop; | |
442 | } | |
443 | ||
444 | for_each_child(tree, c) { | |
445 | prop = get_property_by_label(c, label, node); | |
446 | if (prop) | |
447 | return prop; | |
448 | } | |
449 | ||
450 | *node = NULL; | |
451 | return NULL; | |
452 | } | |
453 | ||
454 | struct marker *get_marker_label(struct node *tree, const char *label, | |
455 | struct node **node, struct property **prop) | |
456 | { | |
457 | struct marker *m; | |
458 | struct property *p; | |
459 | struct node *c; | |
460 | ||
461 | *node = tree; | |
462 | ||
463 | for_each_property(tree, p) { | |
464 | *prop = p; | |
465 | m = p->val.markers; | |
466 | for_each_marker_of_type(m, LABEL) | |
467 | if (streq(m->ref, label)) | |
468 | return m; | |
469 | } | |
470 | ||
471 | for_each_child(tree, c) { | |
472 | m = get_marker_label(c, label, node, prop); | |
473 | if (m) | |
474 | return m; | |
475 | } | |
476 | ||
477 | *prop = NULL; | |
478 | *node = NULL; | |
479 | return NULL; | |
480 | } | |
481 | ||
a4da2e3e DG |
482 | struct node *get_subnode(struct node *node, const char *nodename) |
483 | { | |
484 | struct node *child; | |
485 | ||
486 | for_each_child(node, child) | |
487 | if (streq(child->name, nodename)) | |
488 | return child; | |
489 | ||
490 | return NULL; | |
491 | } | |
492 | ||
493 | struct node *get_node_by_path(struct node *tree, const char *path) | |
494 | { | |
495 | const char *p; | |
496 | struct node *child; | |
497 | ||
cd296721 SW |
498 | if (!path || ! (*path)) { |
499 | if (tree->deleted) | |
500 | return NULL; | |
a4da2e3e | 501 | return tree; |
cd296721 | 502 | } |
a4da2e3e DG |
503 | |
504 | while (path[0] == '/') | |
505 | path++; | |
506 | ||
507 | p = strchr(path, '/'); | |
508 | ||
509 | for_each_child(tree, child) { | |
4201d057 | 510 | if (p && (strlen(child->name) == p-path) && |
9130ba88 | 511 | strprefixeq(path, p - path, child->name)) |
a4da2e3e DG |
512 | return get_node_by_path(child, p+1); |
513 | else if (!p && streq(path, child->name)) | |
514 | return child; | |
515 | } | |
516 | ||
517 | return NULL; | |
518 | } | |
519 | ||
520 | struct node *get_node_by_label(struct node *tree, const char *label) | |
521 | { | |
522 | struct node *child, *node; | |
658f29a5 | 523 | struct label *l; |
a4da2e3e DG |
524 | |
525 | assert(label && (strlen(label) > 0)); | |
526 | ||
658f29a5 JB |
527 | for_each_label(tree->labels, l) |
528 | if (streq(l->label, label)) | |
529 | return tree; | |
a4da2e3e DG |
530 | |
531 | for_each_child(tree, child) { | |
532 | node = get_node_by_label(child, label); | |
533 | if (node) | |
534 | return node; | |
535 | } | |
536 | ||
537 | return NULL; | |
538 | } | |
539 | ||
540 | struct node *get_node_by_phandle(struct node *tree, cell_t phandle) | |
541 | { | |
542 | struct node *child, *node; | |
543 | ||
9130ba88 RH |
544 | if ((phandle == 0) || (phandle == -1)) { |
545 | assert(generate_fixups); | |
546 | return NULL; | |
547 | } | |
a4da2e3e | 548 | |
cd296721 SW |
549 | if (tree->phandle == phandle) { |
550 | if (tree->deleted) | |
551 | return NULL; | |
a4da2e3e | 552 | return tree; |
cd296721 | 553 | } |
a4da2e3e DG |
554 | |
555 | for_each_child(tree, child) { | |
556 | node = get_node_by_phandle(child, phandle); | |
557 | if (node) | |
558 | return node; | |
559 | } | |
560 | ||
561 | return NULL; | |
562 | } | |
563 | ||
564 | struct node *get_node_by_ref(struct node *tree, const char *ref) | |
565 | { | |
47605971 RH |
566 | if (streq(ref, "/")) |
567 | return tree; | |
568 | else if (ref[0] == '/') | |
a4da2e3e DG |
569 | return get_node_by_path(tree, ref); |
570 | else | |
571 | return get_node_by_label(tree, ref); | |
572 | } | |
573 | ||
574 | cell_t get_node_phandle(struct node *root, struct node *node) | |
575 | { | |
576 | static cell_t phandle = 1; /* FIXME: ick, static local */ | |
577 | ||
578 | if ((node->phandle != 0) && (node->phandle != -1)) | |
579 | return node->phandle; | |
580 | ||
a4da2e3e DG |
581 | while (get_node_by_phandle(root, phandle)) |
582 | phandle++; | |
583 | ||
584 | node->phandle = phandle; | |
658f29a5 JB |
585 | |
586 | if (!get_property(node, "linux,phandle") | |
587 | && (phandle_format & PHANDLE_LEGACY)) | |
588 | add_property(node, | |
589 | build_property("linux,phandle", | |
590 | data_append_cell(empty_data, phandle))); | |
591 | ||
592 | if (!get_property(node, "phandle") | |
593 | && (phandle_format & PHANDLE_EPAPR)) | |
594 | add_property(node, | |
595 | build_property("phandle", | |
596 | data_append_cell(empty_data, phandle))); | |
597 | ||
598 | /* If the node *does* have a phandle property, we must | |
599 | * be dealing with a self-referencing phandle, which will be | |
600 | * fixed up momentarily in the caller */ | |
a4da2e3e DG |
601 | |
602 | return node->phandle; | |
603 | } | |
658f29a5 JB |
604 | |
605 | uint32_t guess_boot_cpuid(struct node *tree) | |
606 | { | |
607 | struct node *cpus, *bootcpu; | |
608 | struct property *reg; | |
609 | ||
610 | cpus = get_node_by_path(tree, "/cpus"); | |
611 | if (!cpus) | |
612 | return 0; | |
613 | ||
614 | ||
615 | bootcpu = cpus->children; | |
616 | if (!bootcpu) | |
617 | return 0; | |
618 | ||
619 | reg = get_property(bootcpu, "reg"); | |
620 | if (!reg || (reg->val.len != sizeof(uint32_t))) | |
621 | return 0; | |
622 | ||
623 | /* FIXME: Sanity check node? */ | |
624 | ||
625 | return propval_cell(reg); | |
626 | } | |
627 | ||
628 | static int cmp_reserve_info(const void *ax, const void *bx) | |
629 | { | |
630 | const struct reserve_info *a, *b; | |
631 | ||
632 | a = *((const struct reserve_info * const *)ax); | |
633 | b = *((const struct reserve_info * const *)bx); | |
634 | ||
89d12310 | 635 | if (a->address < b->address) |
658f29a5 | 636 | return -1; |
89d12310 | 637 | else if (a->address > b->address) |
658f29a5 | 638 | return 1; |
89d12310 | 639 | else if (a->size < b->size) |
658f29a5 | 640 | return -1; |
89d12310 | 641 | else if (a->size > b->size) |
658f29a5 JB |
642 | return 1; |
643 | else | |
644 | return 0; | |
645 | } | |
646 | ||
6f05afcb | 647 | static void sort_reserve_entries(struct dt_info *dti) |
658f29a5 JB |
648 | { |
649 | struct reserve_info *ri, **tbl; | |
650 | int n = 0, i = 0; | |
651 | ||
6f05afcb | 652 | for (ri = dti->reservelist; |
658f29a5 JB |
653 | ri; |
654 | ri = ri->next) | |
655 | n++; | |
656 | ||
657 | if (n == 0) | |
658 | return; | |
659 | ||
660 | tbl = xmalloc(n * sizeof(*tbl)); | |
661 | ||
6f05afcb | 662 | for (ri = dti->reservelist; |
658f29a5 JB |
663 | ri; |
664 | ri = ri->next) | |
665 | tbl[i++] = ri; | |
666 | ||
667 | qsort(tbl, n, sizeof(*tbl), cmp_reserve_info); | |
668 | ||
6f05afcb | 669 | dti->reservelist = tbl[0]; |
658f29a5 JB |
670 | for (i = 0; i < (n-1); i++) |
671 | tbl[i]->next = tbl[i+1]; | |
672 | tbl[n-1]->next = NULL; | |
673 | ||
674 | free(tbl); | |
675 | } | |
676 | ||
677 | static int cmp_prop(const void *ax, const void *bx) | |
678 | { | |
679 | const struct property *a, *b; | |
680 | ||
681 | a = *((const struct property * const *)ax); | |
682 | b = *((const struct property * const *)bx); | |
683 | ||
684 | return strcmp(a->name, b->name); | |
685 | } | |
686 | ||
687 | static void sort_properties(struct node *node) | |
688 | { | |
689 | int n = 0, i = 0; | |
690 | struct property *prop, **tbl; | |
691 | ||
cd296721 | 692 | for_each_property_withdel(node, prop) |
658f29a5 JB |
693 | n++; |
694 | ||
695 | if (n == 0) | |
696 | return; | |
697 | ||
698 | tbl = xmalloc(n * sizeof(*tbl)); | |
699 | ||
cd296721 | 700 | for_each_property_withdel(node, prop) |
658f29a5 JB |
701 | tbl[i++] = prop; |
702 | ||
703 | qsort(tbl, n, sizeof(*tbl), cmp_prop); | |
704 | ||
705 | node->proplist = tbl[0]; | |
706 | for (i = 0; i < (n-1); i++) | |
707 | tbl[i]->next = tbl[i+1]; | |
708 | tbl[n-1]->next = NULL; | |
709 | ||
710 | free(tbl); | |
711 | } | |
712 | ||
713 | static int cmp_subnode(const void *ax, const void *bx) | |
714 | { | |
715 | const struct node *a, *b; | |
716 | ||
717 | a = *((const struct node * const *)ax); | |
718 | b = *((const struct node * const *)bx); | |
719 | ||
720 | return strcmp(a->name, b->name); | |
721 | } | |
722 | ||
723 | static void sort_subnodes(struct node *node) | |
724 | { | |
725 | int n = 0, i = 0; | |
726 | struct node *subnode, **tbl; | |
727 | ||
cd296721 | 728 | for_each_child_withdel(node, subnode) |
658f29a5 JB |
729 | n++; |
730 | ||
731 | if (n == 0) | |
732 | return; | |
733 | ||
734 | tbl = xmalloc(n * sizeof(*tbl)); | |
735 | ||
cd296721 | 736 | for_each_child_withdel(node, subnode) |
658f29a5 JB |
737 | tbl[i++] = subnode; |
738 | ||
739 | qsort(tbl, n, sizeof(*tbl), cmp_subnode); | |
740 | ||
741 | node->children = tbl[0]; | |
742 | for (i = 0; i < (n-1); i++) | |
743 | tbl[i]->next_sibling = tbl[i+1]; | |
744 | tbl[n-1]->next_sibling = NULL; | |
745 | ||
746 | free(tbl); | |
747 | } | |
748 | ||
749 | static void sort_node(struct node *node) | |
750 | { | |
751 | struct node *c; | |
752 | ||
753 | sort_properties(node); | |
754 | sort_subnodes(node); | |
cd296721 | 755 | for_each_child_withdel(node, c) |
658f29a5 JB |
756 | sort_node(c); |
757 | } | |
758 | ||
6f05afcb RH |
759 | void sort_tree(struct dt_info *dti) |
760 | { | |
761 | sort_reserve_entries(dti); | |
762 | sort_node(dti->dt); | |
763 | } | |
764 | ||
765 | /* utility helper to avoid code duplication */ | |
766 | static struct node *build_and_name_child_node(struct node *parent, char *name) | |
767 | { | |
768 | struct node *node; | |
769 | ||
770 | node = build_node(NULL, NULL); | |
771 | name_node(node, xstrdup(name)); | |
772 | add_child(parent, node); | |
773 | ||
774 | return node; | |
775 | } | |
776 | ||
777 | static struct node *build_root_node(struct node *dt, char *name) | |
778 | { | |
779 | struct node *an; | |
780 | ||
781 | an = get_subnode(dt, name); | |
782 | if (!an) | |
783 | an = build_and_name_child_node(dt, name); | |
784 | ||
785 | if (!an) | |
786 | die("Could not build root node /%s\n", name); | |
787 | ||
788 | return an; | |
789 | } | |
790 | ||
791 | static bool any_label_tree(struct dt_info *dti, struct node *node) | |
792 | { | |
793 | struct node *c; | |
794 | ||
795 | if (node->labels) | |
796 | return true; | |
797 | ||
798 | for_each_child(node, c) | |
799 | if (any_label_tree(dti, c)) | |
800 | return true; | |
801 | ||
802 | return false; | |
803 | } | |
804 | ||
805 | static void generate_label_tree_internal(struct dt_info *dti, | |
806 | struct node *an, struct node *node, | |
807 | bool allocph) | |
808 | { | |
809 | struct node *dt = dti->dt; | |
810 | struct node *c; | |
811 | struct property *p; | |
812 | struct label *l; | |
813 | ||
814 | /* if there are labels */ | |
815 | if (node->labels) { | |
816 | ||
817 | /* now add the label in the node */ | |
818 | for_each_label(node->labels, l) { | |
819 | ||
820 | /* check whether the label already exists */ | |
821 | p = get_property(an, l->label); | |
822 | if (p) { | |
823 | fprintf(stderr, "WARNING: label %s already" | |
824 | " exists in /%s", l->label, | |
825 | an->name); | |
826 | continue; | |
827 | } | |
828 | ||
829 | /* insert it */ | |
830 | p = build_property(l->label, | |
831 | data_copy_mem(node->fullpath, | |
832 | strlen(node->fullpath) + 1)); | |
833 | add_property(an, p); | |
834 | } | |
835 | ||
836 | /* force allocation of a phandle for this node */ | |
837 | if (allocph) | |
838 | (void)get_node_phandle(dt, node); | |
839 | } | |
840 | ||
841 | for_each_child(node, c) | |
842 | generate_label_tree_internal(dti, an, c, allocph); | |
843 | } | |
844 | ||
845 | static bool any_fixup_tree(struct dt_info *dti, struct node *node) | |
846 | { | |
847 | struct node *c; | |
848 | struct property *prop; | |
849 | struct marker *m; | |
850 | ||
851 | for_each_property(node, prop) { | |
852 | m = prop->val.markers; | |
853 | for_each_marker_of_type(m, REF_PHANDLE) { | |
854 | if (!get_node_by_ref(dti->dt, m->ref)) | |
855 | return true; | |
856 | } | |
857 | } | |
858 | ||
859 | for_each_child(node, c) { | |
860 | if (any_fixup_tree(dti, c)) | |
861 | return true; | |
862 | } | |
863 | ||
864 | return false; | |
865 | } | |
866 | ||
867 | static void add_fixup_entry(struct dt_info *dti, struct node *fn, | |
868 | struct node *node, struct property *prop, | |
869 | struct marker *m) | |
658f29a5 | 870 | { |
6f05afcb RH |
871 | char *entry; |
872 | ||
873 | /* m->ref can only be a REF_PHANDLE, but check anyway */ | |
874 | assert(m->type == REF_PHANDLE); | |
875 | ||
876 | /* there shouldn't be any ':' in the arguments */ | |
877 | if (strchr(node->fullpath, ':') || strchr(prop->name, ':')) | |
878 | die("arguments should not contain ':'\n"); | |
879 | ||
880 | xasprintf(&entry, "%s:%s:%u", | |
881 | node->fullpath, prop->name, m->offset); | |
882 | append_to_property(fn, m->ref, entry, strlen(entry) + 1); | |
89d12310 RH |
883 | |
884 | free(entry); | |
6f05afcb RH |
885 | } |
886 | ||
887 | static void generate_fixups_tree_internal(struct dt_info *dti, | |
888 | struct node *fn, | |
889 | struct node *node) | |
890 | { | |
891 | struct node *dt = dti->dt; | |
892 | struct node *c; | |
893 | struct property *prop; | |
894 | struct marker *m; | |
895 | struct node *refnode; | |
896 | ||
897 | for_each_property(node, prop) { | |
898 | m = prop->val.markers; | |
899 | for_each_marker_of_type(m, REF_PHANDLE) { | |
900 | refnode = get_node_by_ref(dt, m->ref); | |
901 | if (!refnode) | |
902 | add_fixup_entry(dti, fn, node, prop, m); | |
903 | } | |
904 | } | |
905 | ||
906 | for_each_child(node, c) | |
907 | generate_fixups_tree_internal(dti, fn, c); | |
908 | } | |
909 | ||
910 | static bool any_local_fixup_tree(struct dt_info *dti, struct node *node) | |
911 | { | |
912 | struct node *c; | |
913 | struct property *prop; | |
914 | struct marker *m; | |
915 | ||
916 | for_each_property(node, prop) { | |
917 | m = prop->val.markers; | |
918 | for_each_marker_of_type(m, REF_PHANDLE) { | |
919 | if (get_node_by_ref(dti->dt, m->ref)) | |
920 | return true; | |
921 | } | |
922 | } | |
923 | ||
924 | for_each_child(node, c) { | |
925 | if (any_local_fixup_tree(dti, c)) | |
926 | return true; | |
927 | } | |
928 | ||
929 | return false; | |
930 | } | |
931 | ||
932 | static void add_local_fixup_entry(struct dt_info *dti, | |
933 | struct node *lfn, struct node *node, | |
934 | struct property *prop, struct marker *m, | |
935 | struct node *refnode) | |
936 | { | |
937 | struct node *wn, *nwn; /* local fixup node, walk node, new */ | |
89d12310 | 938 | fdt32_t value_32; |
6f05afcb RH |
939 | char **compp; |
940 | int i, depth; | |
941 | ||
942 | /* walk back retreiving depth */ | |
943 | depth = 0; | |
944 | for (wn = node; wn; wn = wn->parent) | |
945 | depth++; | |
946 | ||
947 | /* allocate name array */ | |
948 | compp = xmalloc(sizeof(*compp) * depth); | |
949 | ||
950 | /* store names in the array */ | |
951 | for (wn = node, i = depth - 1; wn; wn = wn->parent, i--) | |
952 | compp[i] = wn->name; | |
953 | ||
954 | /* walk the path components creating nodes if they don't exist */ | |
955 | for (wn = lfn, i = 1; i < depth; i++, wn = nwn) { | |
956 | /* if no node exists, create it */ | |
957 | nwn = get_subnode(wn, compp[i]); | |
958 | if (!nwn) | |
959 | nwn = build_and_name_child_node(wn, compp[i]); | |
960 | } | |
961 | ||
962 | free(compp); | |
963 | ||
964 | value_32 = cpu_to_fdt32(m->offset); | |
965 | append_to_property(wn, prop->name, &value_32, sizeof(value_32)); | |
966 | } | |
967 | ||
968 | static void generate_local_fixups_tree_internal(struct dt_info *dti, | |
969 | struct node *lfn, | |
970 | struct node *node) | |
971 | { | |
972 | struct node *dt = dti->dt; | |
973 | struct node *c; | |
974 | struct property *prop; | |
975 | struct marker *m; | |
976 | struct node *refnode; | |
977 | ||
978 | for_each_property(node, prop) { | |
979 | m = prop->val.markers; | |
980 | for_each_marker_of_type(m, REF_PHANDLE) { | |
981 | refnode = get_node_by_ref(dt, m->ref); | |
982 | if (refnode) | |
983 | add_local_fixup_entry(dti, lfn, node, prop, m, refnode); | |
984 | } | |
985 | } | |
986 | ||
987 | for_each_child(node, c) | |
988 | generate_local_fixups_tree_internal(dti, lfn, c); | |
989 | } | |
990 | ||
991 | void generate_label_tree(struct dt_info *dti, char *name, bool allocph) | |
992 | { | |
993 | if (!any_label_tree(dti, dti->dt)) | |
994 | return; | |
995 | generate_label_tree_internal(dti, build_root_node(dti->dt, name), | |
996 | dti->dt, allocph); | |
997 | } | |
998 | ||
999 | void generate_fixups_tree(struct dt_info *dti, char *name) | |
1000 | { | |
1001 | if (!any_fixup_tree(dti, dti->dt)) | |
1002 | return; | |
1003 | generate_fixups_tree_internal(dti, build_root_node(dti->dt, name), | |
1004 | dti->dt); | |
1005 | } | |
1006 | ||
1007 | void generate_local_fixups_tree(struct dt_info *dti, char *name) | |
1008 | { | |
1009 | if (!any_local_fixup_tree(dti, dti->dt)) | |
1010 | return; | |
1011 | generate_local_fixups_tree_internal(dti, build_root_node(dti->dt, name), | |
1012 | dti->dt); | |
658f29a5 | 1013 | } |