1 | // SPDX-License-Identifier: GPL-2.0-or-later |
2 | /* |
3 | * (C) Copyright David Gibson <dwg@au1.ibm.com>, IBM Corporation. 2005. |
4 | */ |
5 | |
6 | #include "dtc.h" |
7 | #include "srcpos.h" |
8 | |
9 | /* |
10 | * Tree building functions |
11 | */ |
12 | |
13 | void add_label(struct label **labels, char *label) |
14 | { |
15 | struct label *new; |
16 | |
17 | /* Make sure the label isn't already there */ |
18 | for_each_label_withdel(*labels, new) |
19 | if (streq(new->label, label)) { |
20 | new->deleted = 0; |
21 | return; |
22 | } |
23 | |
24 | new = xmalloc(len: sizeof(*new)); |
25 | memset(s: new, c: 0, n: sizeof(*new)); |
26 | new->label = label; |
27 | new->next = *labels; |
28 | *labels = new; |
29 | } |
30 | |
31 | void delete_labels(struct label **labels) |
32 | { |
33 | struct label *label; |
34 | |
35 | for_each_label(*labels, label) |
36 | label->deleted = 1; |
37 | } |
38 | |
39 | struct property *build_property(char *name, struct data val, |
40 | struct srcpos *srcpos) |
41 | { |
42 | struct property *new = xmalloc(len: sizeof(*new)); |
43 | |
44 | memset(s: new, c: 0, n: sizeof(*new)); |
45 | |
46 | new->name = name; |
47 | new->val = val; |
48 | new->srcpos = srcpos_copy(pos: srcpos); |
49 | |
50 | return new; |
51 | } |
52 | |
53 | struct property *build_property_delete(char *name) |
54 | { |
55 | struct property *new = xmalloc(len: sizeof(*new)); |
56 | |
57 | memset(s: new, c: 0, n: sizeof(*new)); |
58 | |
59 | new->name = name; |
60 | new->deleted = 1; |
61 | |
62 | return new; |
63 | } |
64 | |
65 | struct property *chain_property(struct property *first, struct property *list) |
66 | { |
67 | assert(first->next == NULL); |
68 | |
69 | first->next = list; |
70 | return first; |
71 | } |
72 | |
73 | struct property *reverse_properties(struct property *first) |
74 | { |
75 | struct property *p = first; |
76 | struct property *head = NULL; |
77 | struct property *next; |
78 | |
79 | while (p) { |
80 | next = p->next; |
81 | p->next = head; |
82 | head = p; |
83 | p = next; |
84 | } |
85 | return head; |
86 | } |
87 | |
88 | struct node *build_node(struct property *proplist, struct node *children, |
89 | struct srcpos *srcpos) |
90 | { |
91 | struct node *new = xmalloc(len: sizeof(*new)); |
92 | struct node *child; |
93 | |
94 | memset(s: new, c: 0, n: sizeof(*new)); |
95 | |
96 | new->proplist = reverse_properties(first: proplist); |
97 | new->children = children; |
98 | new->srcpos = srcpos_copy(pos: srcpos); |
99 | |
100 | for_each_child(new, child) { |
101 | child->parent = new; |
102 | } |
103 | |
104 | return new; |
105 | } |
106 | |
107 | struct node *build_node_delete(struct srcpos *srcpos) |
108 | { |
109 | struct node *new = xmalloc(len: sizeof(*new)); |
110 | |
111 | memset(s: new, c: 0, n: sizeof(*new)); |
112 | |
113 | new->deleted = 1; |
114 | new->srcpos = srcpos_copy(pos: srcpos); |
115 | |
116 | return new; |
117 | } |
118 | |
119 | struct node *name_node(struct node *node, char *name) |
120 | { |
121 | assert(node->name == NULL); |
122 | |
123 | node->name = name; |
124 | |
125 | return node; |
126 | } |
127 | |
128 | struct node *omit_node_if_unused(struct node *node) |
129 | { |
130 | node->omit_if_unused = 1; |
131 | |
132 | return node; |
133 | } |
134 | |
135 | struct node *reference_node(struct node *node) |
136 | { |
137 | node->is_referenced = 1; |
138 | |
139 | return node; |
140 | } |
141 | |
142 | struct node *merge_nodes(struct node *old_node, struct node *new_node) |
143 | { |
144 | struct property *new_prop, *old_prop; |
145 | struct node *new_child, *old_child; |
146 | struct label *l; |
147 | |
148 | old_node->deleted = 0; |
149 | |
150 | /* Add new node labels to old node */ |
151 | for_each_label_withdel(new_node->labels, l) |
152 | add_label(labels: &old_node->labels, label: l->label); |
153 | |
154 | /* Move properties from the new node to the old node. If there |
155 | * is a collision, replace the old value with the new */ |
156 | while (new_node->proplist) { |
157 | /* Pop the property off the list */ |
158 | new_prop = new_node->proplist; |
159 | new_node->proplist = new_prop->next; |
160 | new_prop->next = NULL; |
161 | |
162 | if (new_prop->deleted) { |
163 | delete_property_by_name(node: old_node, name: new_prop->name); |
164 | free(ptr: new_prop); |
165 | continue; |
166 | } |
167 | |
168 | /* Look for a collision, set new value if there is */ |
169 | for_each_property_withdel(old_node, old_prop) { |
170 | if (streq(old_prop->name, new_prop->name)) { |
171 | /* Add new labels to old property */ |
172 | for_each_label_withdel(new_prop->labels, l) |
173 | add_label(labels: &old_prop->labels, label: l->label); |
174 | |
175 | old_prop->val = new_prop->val; |
176 | old_prop->deleted = 0; |
177 | free(ptr: old_prop->srcpos); |
178 | old_prop->srcpos = new_prop->srcpos; |
179 | free(ptr: new_prop); |
180 | new_prop = NULL; |
181 | break; |
182 | } |
183 | } |
184 | |
185 | /* if no collision occurred, add property to the old node. */ |
186 | if (new_prop) |
187 | add_property(node: old_node, prop: new_prop); |
188 | } |
189 | |
190 | /* Move the override child nodes into the primary node. If |
191 | * there is a collision, then merge the nodes. */ |
192 | while (new_node->children) { |
193 | /* Pop the child node off the list */ |
194 | new_child = new_node->children; |
195 | new_node->children = new_child->next_sibling; |
196 | new_child->parent = NULL; |
197 | new_child->next_sibling = NULL; |
198 | |
199 | if (new_child->deleted) { |
200 | delete_node_by_name(parent: old_node, name: new_child->name); |
201 | free(ptr: new_child); |
202 | continue; |
203 | } |
204 | |
205 | /* Search for a collision. Merge if there is */ |
206 | for_each_child_withdel(old_node, old_child) { |
207 | if (streq(old_child->name, new_child->name)) { |
208 | merge_nodes(old_node: old_child, new_node: new_child); |
209 | new_child = NULL; |
210 | break; |
211 | } |
212 | } |
213 | |
214 | /* if no collision occurred, add child to the old node. */ |
215 | if (new_child) |
216 | add_child(parent: old_node, child: new_child); |
217 | } |
218 | |
219 | old_node->srcpos = srcpos_extend(new_srcpos: old_node->srcpos, old_srcpos: new_node->srcpos); |
220 | |
221 | /* The new node contents are now merged into the old node. Free |
222 | * the new node. */ |
223 | free(ptr: new_node); |
224 | |
225 | return old_node; |
226 | } |
227 | |
228 | struct node * add_orphan_node(struct node *dt, struct node *new_node, char *ref) |
229 | { |
230 | static unsigned int next_orphan_fragment = 0; |
231 | struct node *node; |
232 | struct property *p; |
233 | struct data d = empty_data; |
234 | char *name; |
235 | |
236 | if (ref[0] == '/') { |
237 | d = data_add_marker(d, type: TYPE_STRING, ref); |
238 | d = data_append_data(d, p: ref, len: strlen(s: ref) + 1); |
239 | |
240 | p = build_property(name: "target-path" , val: d, NULL); |
241 | } else { |
242 | d = data_add_marker(d, type: REF_PHANDLE, ref); |
243 | d = data_append_integer(d, word: 0xffffffff, bits: 32); |
244 | |
245 | p = build_property(name: "target" , val: d, NULL); |
246 | } |
247 | |
248 | xasprintf(strp: &name, fmt: "fragment@%u" , |
249 | next_orphan_fragment++); |
250 | name_node(node: new_node, name: "__overlay__" ); |
251 | node = build_node(proplist: p, children: new_node, NULL); |
252 | name_node(node, name); |
253 | |
254 | add_child(parent: dt, child: node); |
255 | return dt; |
256 | } |
257 | |
258 | struct node *chain_node(struct node *first, struct node *list) |
259 | { |
260 | assert(first->next_sibling == NULL); |
261 | |
262 | first->next_sibling = list; |
263 | return first; |
264 | } |
265 | |
266 | void add_property(struct node *node, struct property *prop) |
267 | { |
268 | struct property **p; |
269 | |
270 | prop->next = NULL; |
271 | |
272 | p = &node->proplist; |
273 | while (*p) |
274 | p = &((*p)->next); |
275 | |
276 | *p = prop; |
277 | } |
278 | |
279 | void delete_property_by_name(struct node *node, char *name) |
280 | { |
281 | struct property *prop = node->proplist; |
282 | |
283 | while (prop) { |
284 | if (streq(prop->name, name)) { |
285 | delete_property(prop); |
286 | return; |
287 | } |
288 | prop = prop->next; |
289 | } |
290 | } |
291 | |
292 | void delete_property(struct property *prop) |
293 | { |
294 | prop->deleted = 1; |
295 | delete_labels(labels: &prop->labels); |
296 | } |
297 | |
298 | void add_child(struct node *parent, struct node *child) |
299 | { |
300 | struct node **p; |
301 | |
302 | child->next_sibling = NULL; |
303 | child->parent = parent; |
304 | |
305 | p = &parent->children; |
306 | while (*p) |
307 | p = &((*p)->next_sibling); |
308 | |
309 | *p = child; |
310 | } |
311 | |
312 | void delete_node_by_name(struct node *parent, char *name) |
313 | { |
314 | struct node *node = parent->children; |
315 | |
316 | while (node) { |
317 | if (streq(node->name, name)) { |
318 | delete_node(node); |
319 | return; |
320 | } |
321 | node = node->next_sibling; |
322 | } |
323 | } |
324 | |
325 | void delete_node(struct node *node) |
326 | { |
327 | struct property *prop; |
328 | struct node *child; |
329 | |
330 | node->deleted = 1; |
331 | for_each_child(node, child) |
332 | delete_node(node: child); |
333 | for_each_property(node, prop) |
334 | delete_property(prop); |
335 | delete_labels(labels: &node->labels); |
336 | } |
337 | |
338 | void append_to_property(struct node *node, |
339 | char *name, const void *data, int len, |
340 | enum markertype type) |
341 | { |
342 | struct data d; |
343 | struct property *p; |
344 | |
345 | p = get_property(node, propname: name); |
346 | if (p) { |
347 | d = data_add_marker(d: p->val, type, ref: name); |
348 | d = data_append_data(d, p: data, len); |
349 | p->val = d; |
350 | } else { |
351 | d = data_add_marker(empty_data, type, ref: name); |
352 | d = data_append_data(d, data, len); |
353 | p = build_property(name, d, NULL); |
354 | add_property(node, p); |
355 | } |
356 | } |
357 | |
358 | struct reserve_info *build_reserve_entry(uint64_t address, uint64_t size) |
359 | { |
360 | struct reserve_info *new = xmalloc(len: sizeof(*new)); |
361 | |
362 | memset(s: new, c: 0, n: sizeof(*new)); |
363 | |
364 | new->address = address; |
365 | new->size = size; |
366 | |
367 | return new; |
368 | } |
369 | |
370 | struct reserve_info *chain_reserve_entry(struct reserve_info *first, |
371 | struct reserve_info *list) |
372 | { |
373 | assert(first->next == NULL); |
374 | |
375 | first->next = list; |
376 | return first; |
377 | } |
378 | |
379 | struct reserve_info *add_reserve_entry(struct reserve_info *list, |
380 | struct reserve_info *new) |
381 | { |
382 | struct reserve_info *last; |
383 | |
384 | new->next = NULL; |
385 | |
386 | if (! list) |
387 | return new; |
388 | |
389 | for (last = list; last->next; last = last->next) |
390 | ; |
391 | |
392 | last->next = new; |
393 | |
394 | return list; |
395 | } |
396 | |
397 | struct dt_info *build_dt_info(unsigned int dtsflags, |
398 | struct reserve_info *reservelist, |
399 | struct node *tree, uint32_t boot_cpuid_phys) |
400 | { |
401 | struct dt_info *dti; |
402 | |
403 | dti = xmalloc(len: sizeof(*dti)); |
404 | dti->dtsflags = dtsflags; |
405 | dti->reservelist = reservelist; |
406 | dti->dt = tree; |
407 | dti->boot_cpuid_phys = boot_cpuid_phys; |
408 | |
409 | return dti; |
410 | } |
411 | |
412 | /* |
413 | * Tree accessor functions |
414 | */ |
415 | |
416 | const char *get_unitname(struct node *node) |
417 | { |
418 | if (node->name[node->basenamelen] == '\0') |
419 | return "" ; |
420 | else |
421 | return node->name + node->basenamelen + 1; |
422 | } |
423 | |
424 | struct property *get_property(struct node *node, const char *propname) |
425 | { |
426 | struct property *prop; |
427 | |
428 | for_each_property(node, prop) |
429 | if (streq(prop->name, propname)) |
430 | return prop; |
431 | |
432 | return NULL; |
433 | } |
434 | |
435 | cell_t propval_cell(struct property *prop) |
436 | { |
437 | assert(prop->val.len == sizeof(cell_t)); |
438 | return fdt32_to_cpu(*((fdt32_t *)prop->val.val)); |
439 | } |
440 | |
441 | cell_t propval_cell_n(struct property *prop, unsigned int n) |
442 | { |
443 | assert(prop->val.len / sizeof(cell_t) >= n); |
444 | return fdt32_to_cpu(*((fdt32_t *)prop->val.val + n)); |
445 | } |
446 | |
447 | struct property *get_property_by_label(struct node *tree, const char *label, |
448 | struct node **node) |
449 | { |
450 | struct property *prop; |
451 | struct node *c; |
452 | |
453 | *node = tree; |
454 | |
455 | for_each_property(tree, prop) { |
456 | struct label *l; |
457 | |
458 | for_each_label(prop->labels, l) |
459 | if (streq(l->label, label)) |
460 | return prop; |
461 | } |
462 | |
463 | for_each_child(tree, c) { |
464 | prop = get_property_by_label(tree: c, label, node); |
465 | if (prop) |
466 | return prop; |
467 | } |
468 | |
469 | *node = NULL; |
470 | return NULL; |
471 | } |
472 | |
473 | struct marker *get_marker_label(struct node *tree, const char *label, |
474 | struct node **node, struct property **prop) |
475 | { |
476 | struct marker *m; |
477 | struct property *p; |
478 | struct node *c; |
479 | |
480 | *node = tree; |
481 | |
482 | for_each_property(tree, p) { |
483 | *prop = p; |
484 | m = p->val.markers; |
485 | for_each_marker_of_type(m, LABEL) |
486 | if (streq(m->ref, label)) |
487 | return m; |
488 | } |
489 | |
490 | for_each_child(tree, c) { |
491 | m = get_marker_label(tree: c, label, node, prop); |
492 | if (m) |
493 | return m; |
494 | } |
495 | |
496 | *prop = NULL; |
497 | *node = NULL; |
498 | return NULL; |
499 | } |
500 | |
501 | struct node *get_subnode(struct node *node, const char *nodename) |
502 | { |
503 | struct node *child; |
504 | |
505 | for_each_child(node, child) |
506 | if (streq(child->name, nodename)) |
507 | return child; |
508 | |
509 | return NULL; |
510 | } |
511 | |
512 | struct node *get_node_by_path(struct node *tree, const char *path) |
513 | { |
514 | const char *p; |
515 | struct node *child; |
516 | |
517 | if (!path || ! (*path)) { |
518 | if (tree->deleted) |
519 | return NULL; |
520 | return tree; |
521 | } |
522 | |
523 | while (path[0] == '/') |
524 | path++; |
525 | |
526 | p = strchr(s: path, c: '/'); |
527 | |
528 | for_each_child(tree, child) { |
529 | if (p && strprefixeq(path, (size_t)(p - path), child->name)) |
530 | return get_node_by_path(tree: child, path: p+1); |
531 | else if (!p && streq(path, child->name)) |
532 | return child; |
533 | } |
534 | |
535 | return NULL; |
536 | } |
537 | |
538 | struct node *get_node_by_label(struct node *tree, const char *label) |
539 | { |
540 | struct node *child, *node; |
541 | struct label *l; |
542 | |
543 | assert(label && (strlen(label) > 0)); |
544 | |
545 | for_each_label(tree->labels, l) |
546 | if (streq(l->label, label)) |
547 | return tree; |
548 | |
549 | for_each_child(tree, child) { |
550 | node = get_node_by_label(tree: child, label); |
551 | if (node) |
552 | return node; |
553 | } |
554 | |
555 | return NULL; |
556 | } |
557 | |
558 | struct node *get_node_by_phandle(struct node *tree, cell_t phandle) |
559 | { |
560 | struct node *child, *node; |
561 | |
562 | if (!phandle_is_valid(phandle)) { |
563 | assert(generate_fixups); |
564 | return NULL; |
565 | } |
566 | |
567 | if (tree->phandle == phandle) { |
568 | if (tree->deleted) |
569 | return NULL; |
570 | return tree; |
571 | } |
572 | |
573 | for_each_child(tree, child) { |
574 | node = get_node_by_phandle(tree: child, phandle); |
575 | if (node) |
576 | return node; |
577 | } |
578 | |
579 | return NULL; |
580 | } |
581 | |
582 | struct node *get_node_by_ref(struct node *tree, const char *ref) |
583 | { |
584 | struct node *target = tree; |
585 | const char *label = NULL, *path = NULL; |
586 | |
587 | if (streq(ref, "/" )) |
588 | return tree; |
589 | |
590 | if (ref[0] == '/') |
591 | path = ref; |
592 | else |
593 | label = ref; |
594 | |
595 | if (label) { |
596 | const char *slash = strchr(s: label, c: '/'); |
597 | char *buf = NULL; |
598 | |
599 | if (slash) { |
600 | buf = xstrndup(s: label, len: slash - label); |
601 | label = buf; |
602 | path = slash + 1; |
603 | } |
604 | |
605 | target = get_node_by_label(tree, label); |
606 | |
607 | free(ptr: buf); |
608 | |
609 | if (!target) |
610 | return NULL; |
611 | } |
612 | |
613 | if (path) |
614 | target = get_node_by_path(tree: target, path); |
615 | |
616 | return target; |
617 | } |
618 | |
619 | cell_t get_node_phandle(struct node *root, struct node *node) |
620 | { |
621 | static cell_t phandle = 1; /* FIXME: ick, static local */ |
622 | struct data d = empty_data; |
623 | |
624 | if (phandle_is_valid(phandle: node->phandle)) |
625 | return node->phandle; |
626 | |
627 | while (get_node_by_phandle(tree: root, phandle)) |
628 | phandle++; |
629 | |
630 | node->phandle = phandle; |
631 | |
632 | d = data_add_marker(d, type: TYPE_UINT32, NULL); |
633 | d = data_append_cell(d, word: phandle); |
634 | |
635 | if (!get_property(node, propname: "linux,phandle" ) |
636 | && (phandle_format & PHANDLE_LEGACY)) |
637 | add_property(node, prop: build_property(name: "linux,phandle" , val: d, NULL)); |
638 | |
639 | if (!get_property(node, propname: "phandle" ) |
640 | && (phandle_format & PHANDLE_EPAPR)) |
641 | add_property(node, prop: build_property(name: "phandle" , val: d, NULL)); |
642 | |
643 | /* If the node *does* have a phandle property, we must |
644 | * be dealing with a self-referencing phandle, which will be |
645 | * fixed up momentarily in the caller */ |
646 | |
647 | return node->phandle; |
648 | } |
649 | |
650 | uint32_t guess_boot_cpuid(struct node *tree) |
651 | { |
652 | struct node *cpus, *bootcpu; |
653 | struct property *reg; |
654 | |
655 | cpus = get_node_by_path(tree, path: "/cpus" ); |
656 | if (!cpus) |
657 | return 0; |
658 | |
659 | |
660 | bootcpu = cpus->children; |
661 | if (!bootcpu) |
662 | return 0; |
663 | |
664 | reg = get_property(node: bootcpu, propname: "reg" ); |
665 | if (!reg || (reg->val.len != sizeof(uint32_t))) |
666 | return 0; |
667 | |
668 | /* FIXME: Sanity check node? */ |
669 | |
670 | return propval_cell(prop: reg); |
671 | } |
672 | |
673 | static int cmp_reserve_info(const void *ax, const void *bx) |
674 | { |
675 | const struct reserve_info *a, *b; |
676 | |
677 | a = *((const struct reserve_info * const *)ax); |
678 | b = *((const struct reserve_info * const *)bx); |
679 | |
680 | if (a->address < b->address) |
681 | return -1; |
682 | else if (a->address > b->address) |
683 | return 1; |
684 | else if (a->size < b->size) |
685 | return -1; |
686 | else if (a->size > b->size) |
687 | return 1; |
688 | else |
689 | return 0; |
690 | } |
691 | |
692 | static void sort_reserve_entries(struct dt_info *dti) |
693 | { |
694 | struct reserve_info *ri, **tbl; |
695 | int n = 0, i = 0; |
696 | |
697 | for (ri = dti->reservelist; |
698 | ri; |
699 | ri = ri->next) |
700 | n++; |
701 | |
702 | if (n == 0) |
703 | return; |
704 | |
705 | tbl = xmalloc(len: n * sizeof(*tbl)); |
706 | |
707 | for (ri = dti->reservelist; |
708 | ri; |
709 | ri = ri->next) |
710 | tbl[i++] = ri; |
711 | |
712 | qsort(base: tbl, nmemb: n, size: sizeof(*tbl), compar: cmp_reserve_info); |
713 | |
714 | dti->reservelist = tbl[0]; |
715 | for (i = 0; i < (n-1); i++) |
716 | tbl[i]->next = tbl[i+1]; |
717 | tbl[n-1]->next = NULL; |
718 | |
719 | free(ptr: tbl); |
720 | } |
721 | |
722 | static int cmp_prop(const void *ax, const void *bx) |
723 | { |
724 | const struct property *a, *b; |
725 | |
726 | a = *((const struct property * const *)ax); |
727 | b = *((const struct property * const *)bx); |
728 | |
729 | return strcmp(s1: a->name, s2: b->name); |
730 | } |
731 | |
732 | static void sort_properties(struct node *node) |
733 | { |
734 | int n = 0, i = 0; |
735 | struct property *prop, **tbl; |
736 | |
737 | for_each_property_withdel(node, prop) |
738 | n++; |
739 | |
740 | if (n == 0) |
741 | return; |
742 | |
743 | tbl = xmalloc(len: n * sizeof(*tbl)); |
744 | |
745 | for_each_property_withdel(node, prop) |
746 | tbl[i++] = prop; |
747 | |
748 | qsort(base: tbl, nmemb: n, size: sizeof(*tbl), compar: cmp_prop); |
749 | |
750 | node->proplist = tbl[0]; |
751 | for (i = 0; i < (n-1); i++) |
752 | tbl[i]->next = tbl[i+1]; |
753 | tbl[n-1]->next = NULL; |
754 | |
755 | free(ptr: tbl); |
756 | } |
757 | |
758 | static int cmp_subnode(const void *ax, const void *bx) |
759 | { |
760 | const struct node *a, *b; |
761 | |
762 | a = *((const struct node * const *)ax); |
763 | b = *((const struct node * const *)bx); |
764 | |
765 | return strcmp(s1: a->name, s2: b->name); |
766 | } |
767 | |
768 | static void sort_subnodes(struct node *node) |
769 | { |
770 | int n = 0, i = 0; |
771 | struct node *subnode, **tbl; |
772 | |
773 | for_each_child_withdel(node, subnode) |
774 | n++; |
775 | |
776 | if (n == 0) |
777 | return; |
778 | |
779 | tbl = xmalloc(len: n * sizeof(*tbl)); |
780 | |
781 | for_each_child_withdel(node, subnode) |
782 | tbl[i++] = subnode; |
783 | |
784 | qsort(base: tbl, nmemb: n, size: sizeof(*tbl), compar: cmp_subnode); |
785 | |
786 | node->children = tbl[0]; |
787 | for (i = 0; i < (n-1); i++) |
788 | tbl[i]->next_sibling = tbl[i+1]; |
789 | tbl[n-1]->next_sibling = NULL; |
790 | |
791 | free(ptr: tbl); |
792 | } |
793 | |
794 | static void sort_node(struct node *node) |
795 | { |
796 | struct node *c; |
797 | |
798 | sort_properties(node); |
799 | sort_subnodes(node); |
800 | for_each_child_withdel(node, c) |
801 | sort_node(node: c); |
802 | } |
803 | |
804 | void sort_tree(struct dt_info *dti) |
805 | { |
806 | sort_reserve_entries(dti); |
807 | sort_node(node: dti->dt); |
808 | } |
809 | |
810 | /* utility helper to avoid code duplication */ |
811 | static struct node *build_and_name_child_node(struct node *parent, char *name) |
812 | { |
813 | struct node *node; |
814 | |
815 | node = build_node(NULL, NULL, NULL); |
816 | name_node(node, name: xstrdup(s: name)); |
817 | add_child(parent, child: node); |
818 | |
819 | return node; |
820 | } |
821 | |
822 | static struct node *build_root_node(struct node *dt, char *name) |
823 | { |
824 | struct node *an; |
825 | |
826 | an = get_subnode(node: dt, nodename: name); |
827 | if (!an) |
828 | an = build_and_name_child_node(parent: dt, name); |
829 | |
830 | if (!an) |
831 | die(str: "Could not build root node /%s\n" , name); |
832 | |
833 | return an; |
834 | } |
835 | |
836 | static bool any_label_tree(struct dt_info *dti, struct node *node) |
837 | { |
838 | struct node *c; |
839 | |
840 | if (node->labels) |
841 | return true; |
842 | |
843 | for_each_child(node, c) |
844 | if (any_label_tree(dti, node: c)) |
845 | return true; |
846 | |
847 | return false; |
848 | } |
849 | |
850 | static void generate_label_tree_internal(struct dt_info *dti, |
851 | struct node *an, struct node *node, |
852 | bool allocph) |
853 | { |
854 | struct node *dt = dti->dt; |
855 | struct node *c; |
856 | struct property *p; |
857 | struct label *l; |
858 | |
859 | /* if there are labels */ |
860 | if (node->labels) { |
861 | |
862 | /* now add the label in the node */ |
863 | for_each_label(node->labels, l) { |
864 | |
865 | /* check whether the label already exists */ |
866 | p = get_property(node: an, propname: l->label); |
867 | if (p) { |
868 | fprintf(stderr, format: "WARNING: label %s already" |
869 | " exists in /%s" , l->label, |
870 | an->name); |
871 | continue; |
872 | } |
873 | |
874 | /* insert it */ |
875 | p = build_property(name: l->label, |
876 | val: data_copy_escape_string(s: node->fullpath, |
877 | len: strlen(s: node->fullpath)), |
878 | NULL); |
879 | add_property(node: an, prop: p); |
880 | } |
881 | |
882 | /* force allocation of a phandle for this node */ |
883 | if (allocph) |
884 | (void)get_node_phandle(root: dt, node); |
885 | } |
886 | |
887 | for_each_child(node, c) |
888 | generate_label_tree_internal(dti, an, node: c, allocph); |
889 | } |
890 | |
891 | static bool any_fixup_tree(struct dt_info *dti, struct node *node) |
892 | { |
893 | struct node *c; |
894 | struct property *prop; |
895 | struct marker *m; |
896 | |
897 | for_each_property(node, prop) { |
898 | m = prop->val.markers; |
899 | for_each_marker_of_type(m, REF_PHANDLE) { |
900 | if (!get_node_by_ref(tree: dti->dt, ref: m->ref)) |
901 | return true; |
902 | } |
903 | } |
904 | |
905 | for_each_child(node, c) { |
906 | if (any_fixup_tree(dti, node: c)) |
907 | return true; |
908 | } |
909 | |
910 | return false; |
911 | } |
912 | |
913 | static void add_fixup_entry(struct dt_info *dti, struct node *fn, |
914 | struct node *node, struct property *prop, |
915 | struct marker *m) |
916 | { |
917 | char *entry; |
918 | |
919 | /* m->ref can only be a REF_PHANDLE, but check anyway */ |
920 | assert(m->type == REF_PHANDLE); |
921 | |
922 | /* The format only permits fixups for references to label, not |
923 | * references to path */ |
924 | if (strchr(s: m->ref, c: '/')) |
925 | die(str: "Can't generate fixup for reference to path &{%s}\n" , |
926 | m->ref); |
927 | |
928 | /* there shouldn't be any ':' in the arguments */ |
929 | if (strchr(s: node->fullpath, c: ':') || strchr(s: prop->name, c: ':')) |
930 | die(str: "arguments should not contain ':'\n" ); |
931 | |
932 | xasprintf(strp: &entry, fmt: "%s:%s:%u" , |
933 | node->fullpath, prop->name, m->offset); |
934 | append_to_property(node: fn, name: m->ref, data: entry, len: strlen(s: entry) + 1, type: TYPE_STRING); |
935 | |
936 | free(ptr: entry); |
937 | } |
938 | |
939 | static void generate_fixups_tree_internal(struct dt_info *dti, |
940 | struct node *fn, |
941 | struct node *node) |
942 | { |
943 | struct node *dt = dti->dt; |
944 | struct node *c; |
945 | struct property *prop; |
946 | struct marker *m; |
947 | struct node *refnode; |
948 | |
949 | for_each_property(node, prop) { |
950 | m = prop->val.markers; |
951 | for_each_marker_of_type(m, REF_PHANDLE) { |
952 | refnode = get_node_by_ref(tree: dt, ref: m->ref); |
953 | if (!refnode) |
954 | add_fixup_entry(dti, fn, node, prop, m); |
955 | } |
956 | } |
957 | |
958 | for_each_child(node, c) |
959 | generate_fixups_tree_internal(dti, fn, node: c); |
960 | } |
961 | |
962 | static bool any_local_fixup_tree(struct dt_info *dti, struct node *node) |
963 | { |
964 | struct node *c; |
965 | struct property *prop; |
966 | struct marker *m; |
967 | |
968 | for_each_property(node, prop) { |
969 | m = prop->val.markers; |
970 | for_each_marker_of_type(m, REF_PHANDLE) { |
971 | if (get_node_by_ref(tree: dti->dt, ref: m->ref)) |
972 | return true; |
973 | } |
974 | } |
975 | |
976 | for_each_child(node, c) { |
977 | if (any_local_fixup_tree(dti, node: c)) |
978 | return true; |
979 | } |
980 | |
981 | return false; |
982 | } |
983 | |
984 | static void add_local_fixup_entry(struct dt_info *dti, |
985 | struct node *lfn, struct node *node, |
986 | struct property *prop, struct marker *m, |
987 | struct node *refnode) |
988 | { |
989 | struct node *wn, *nwn; /* local fixup node, walk node, new */ |
990 | fdt32_t value_32; |
991 | char **compp; |
992 | int i, depth; |
993 | |
994 | /* walk back retrieving depth */ |
995 | depth = 0; |
996 | for (wn = node; wn; wn = wn->parent) |
997 | depth++; |
998 | |
999 | /* allocate name array */ |
1000 | compp = xmalloc(len: sizeof(*compp) * depth); |
1001 | |
1002 | /* store names in the array */ |
1003 | for (wn = node, i = depth - 1; wn; wn = wn->parent, i--) |
1004 | compp[i] = wn->name; |
1005 | |
1006 | /* walk the path components creating nodes if they don't exist */ |
1007 | for (wn = lfn, i = 1; i < depth; i++, wn = nwn) { |
1008 | /* if no node exists, create it */ |
1009 | nwn = get_subnode(node: wn, nodename: compp[i]); |
1010 | if (!nwn) |
1011 | nwn = build_and_name_child_node(parent: wn, name: compp[i]); |
1012 | } |
1013 | |
1014 | free(ptr: compp); |
1015 | |
1016 | value_32 = cpu_to_fdt32(m->offset); |
1017 | append_to_property(node: wn, name: prop->name, data: &value_32, len: sizeof(value_32), type: TYPE_UINT32); |
1018 | } |
1019 | |
1020 | static void generate_local_fixups_tree_internal(struct dt_info *dti, |
1021 | struct node *lfn, |
1022 | struct node *node) |
1023 | { |
1024 | struct node *dt = dti->dt; |
1025 | struct node *c; |
1026 | struct property *prop; |
1027 | struct marker *m; |
1028 | struct node *refnode; |
1029 | |
1030 | for_each_property(node, prop) { |
1031 | m = prop->val.markers; |
1032 | for_each_marker_of_type(m, REF_PHANDLE) { |
1033 | refnode = get_node_by_ref(tree: dt, ref: m->ref); |
1034 | if (refnode) |
1035 | add_local_fixup_entry(dti, lfn, node, prop, m, refnode); |
1036 | } |
1037 | } |
1038 | |
1039 | for_each_child(node, c) |
1040 | generate_local_fixups_tree_internal(dti, lfn, node: c); |
1041 | } |
1042 | |
1043 | void generate_label_tree(struct dt_info *dti, char *name, bool allocph) |
1044 | { |
1045 | if (!any_label_tree(dti, node: dti->dt)) |
1046 | return; |
1047 | generate_label_tree_internal(dti, an: build_root_node(dt: dti->dt, name), |
1048 | node: dti->dt, allocph); |
1049 | } |
1050 | |
1051 | void generate_fixups_tree(struct dt_info *dti, char *name) |
1052 | { |
1053 | if (!any_fixup_tree(dti, node: dti->dt)) |
1054 | return; |
1055 | generate_fixups_tree_internal(dti, fn: build_root_node(dt: dti->dt, name), |
1056 | node: dti->dt); |
1057 | } |
1058 | |
1059 | void generate_local_fixups_tree(struct dt_info *dti, char *name) |
1060 | { |
1061 | if (!any_local_fixup_tree(dti, node: dti->dt)) |
1062 | return; |
1063 | generate_local_fixups_tree_internal(dti, lfn: build_root_node(dt: dti->dt, name), |
1064 | node: dti->dt); |
1065 | } |
1066 | |