Commit | Line | Data |
---|---|---|
12869ecd | 1 | // SPDX-License-Identifier: GPL-2.0-or-later |
a4da2e3e DG |
2 | /* |
3 | * (C) Copyright David Gibson <dwg@au1.ibm.com>, IBM Corporation. 2005. | |
a4da2e3e DG |
4 | */ |
5 | ||
6 | #include "dtc.h" | |
c2e7075c | 7 | #include "srcpos.h" |
a4da2e3e DG |
8 | |
9 | /* | |
10 | * Tree building functions | |
11 | */ | |
12 | ||
658f29a5 JB |
13 | void add_label(struct label **labels, char *label) |
14 | { | |
15 | struct label *new; | |
16 | ||
17 | /* Make sure the label isn't already there */ | |
cd296721 SW |
18 | for_each_label_withdel(*labels, new) |
19 | if (streq(new->label, label)) { | |
20 | new->deleted = 0; | |
658f29a5 | 21 | return; |
cd296721 | 22 | } |
658f29a5 JB |
23 | |
24 | new = xmalloc(sizeof(*new)); | |
cd296721 | 25 | memset(new, 0, sizeof(*new)); |
658f29a5 JB |
26 | new->label = label; |
27 | new->next = *labels; | |
28 | *labels = new; | |
29 | } | |
30 | ||
cd296721 SW |
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 | ||
c2e7075c RH |
39 | struct property *build_property(char *name, struct data val, |
40 | struct srcpos *srcpos) | |
a4da2e3e DG |
41 | { |
42 | struct property *new = xmalloc(sizeof(*new)); | |
43 | ||
658f29a5 JB |
44 | memset(new, 0, sizeof(*new)); |
45 | ||
a4da2e3e DG |
46 | new->name = name; |
47 | new->val = val; | |
c2e7075c | 48 | new->srcpos = srcpos_copy(srcpos); |
a4da2e3e | 49 | |
a4da2e3e DG |
50 | return new; |
51 | } | |
52 | ||
cd296721 SW |
53 | struct property *build_property_delete(char *name) |
54 | { | |
55 | struct property *new = xmalloc(sizeof(*new)); | |
56 | ||
57 | memset(new, 0, sizeof(*new)); | |
58 | ||
59 | new->name = name; | |
60 | new->deleted = 1; | |
61 | ||
62 | return new; | |
63 | } | |
64 | ||
a4da2e3e DG |
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 | ||
c2e7075c RH |
88 | struct node *build_node(struct property *proplist, struct node *children, |
89 | struct srcpos *srcpos) | |
a4da2e3e DG |
90 | { |
91 | struct node *new = xmalloc(sizeof(*new)); | |
92 | struct node *child; | |
93 | ||
94 | memset(new, 0, sizeof(*new)); | |
95 | ||
96 | new->proplist = reverse_properties(proplist); | |
97 | new->children = children; | |
c2e7075c | 98 | new->srcpos = srcpos_copy(srcpos); |
a4da2e3e DG |
99 | |
100 | for_each_child(new, child) { | |
101 | child->parent = new; | |
102 | } | |
103 | ||
104 | return new; | |
105 | } | |
106 | ||
c2e7075c | 107 | struct node *build_node_delete(struct srcpos *srcpos) |
cd296721 SW |
108 | { |
109 | struct node *new = xmalloc(sizeof(*new)); | |
110 | ||
111 | memset(new, 0, sizeof(*new)); | |
112 | ||
113 | new->deleted = 1; | |
c2e7075c | 114 | new->srcpos = srcpos_copy(srcpos); |
cd296721 SW |
115 | |
116 | return new; | |
117 | } | |
118 | ||
658f29a5 | 119 | struct node *name_node(struct node *node, char *name) |
a4da2e3e DG |
120 | { |
121 | assert(node->name == NULL); | |
122 | ||
123 | node->name = name; | |
124 | ||
a4da2e3e DG |
125 | return node; |
126 | } | |
127 | ||
50aafd60 RH |
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 | ||
658f29a5 JB |
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 | ||
cd296721 SW |
148 | old_node->deleted = 0; |
149 | ||
658f29a5 | 150 | /* Add new node labels to old node */ |
cd296721 | 151 | for_each_label_withdel(new_node->labels, l) |
658f29a5 JB |
152 | add_label(&old_node->labels, 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 | ||
cd296721 SW |
162 | if (new_prop->deleted) { |
163 | delete_property_by_name(old_node, new_prop->name); | |
164 | free(new_prop); | |
165 | continue; | |
166 | } | |
167 | ||
658f29a5 | 168 | /* Look for a collision, set new value if there is */ |
cd296721 | 169 | for_each_property_withdel(old_node, old_prop) { |
658f29a5 JB |
170 | if (streq(old_prop->name, new_prop->name)) { |
171 | /* Add new labels to old property */ | |
cd296721 | 172 | for_each_label_withdel(new_prop->labels, l) |
658f29a5 JB |
173 | add_label(&old_prop->labels, l->label); |
174 | ||
175 | old_prop->val = new_prop->val; | |
cd296721 | 176 | old_prop->deleted = 0; |
c2e7075c RH |
177 | free(old_prop->srcpos); |
178 | old_prop->srcpos = new_prop->srcpos; | |
658f29a5 JB |
179 | free(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(old_node, 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 | ||
cd296721 SW |
199 | if (new_child->deleted) { |
200 | delete_node_by_name(old_node, new_child->name); | |
201 | free(new_child); | |
202 | continue; | |
203 | } | |
204 | ||
658f29a5 | 205 | /* Search for a collision. Merge if there is */ |
cd296721 | 206 | for_each_child_withdel(old_node, old_child) { |
658f29a5 JB |
207 | if (streq(old_child->name, new_child->name)) { |
208 | merge_nodes(old_child, new_child); | |
209 | new_child = NULL; | |
210 | break; | |
211 | } | |
212 | } | |
213 | ||
6f05afcb | 214 | /* if no collision occurred, add child to the old node. */ |
658f29a5 JB |
215 | if (new_child) |
216 | add_child(old_node, new_child); | |
217 | } | |
218 | ||
c2e7075c RH |
219 | old_node->srcpos = srcpos_extend(old_node->srcpos, new_node->srcpos); |
220 | ||
658f29a5 JB |
221 | /* The new node contents are now merged into the old node. Free |
222 | * the new node. */ | |
223 | free(new_node); | |
224 | ||
225 | return old_node; | |
226 | } | |
227 | ||
9130ba88 | 228 | struct node * add_orphan_node(struct node *dt, struct node *new_node, char *ref) |
4201d057 RH |
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 | ||
50aafd60 | 236 | if (ref[0] == '/') { |
9bb9c6a1 | 237 | d = data_add_marker(d, TYPE_STRING, ref); |
50aafd60 RH |
238 | d = data_append_data(d, ref, strlen(ref) + 1); |
239 | ||
c2e7075c | 240 | p = build_property("target-path", d, NULL); |
50aafd60 RH |
241 | } else { |
242 | d = data_add_marker(d, REF_PHANDLE, ref); | |
243 | d = data_append_integer(d, 0xffffffff, 32); | |
4201d057 | 244 | |
c2e7075c | 245 | p = build_property("target", d, NULL); |
50aafd60 | 246 | } |
4201d057 RH |
247 | |
248 | xasprintf(&name, "fragment@%u", | |
249 | next_orphan_fragment++); | |
250 | name_node(new_node, "__overlay__"); | |
c2e7075c | 251 | node = build_node(p, new_node, NULL); |
4201d057 RH |
252 | name_node(node, name); |
253 | ||
254 | add_child(dt, node); | |
9130ba88 | 255 | return dt; |
4201d057 RH |
256 | } |
257 | ||
a4da2e3e DG |
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 | ||
cd296721 SW |
279 | void delete_property_by_name(struct node *node, char *name) |
280 | { | |
281 | struct property *prop = node->proplist; | |
282 | ||
283 | while (prop) { | |
89d12310 | 284 | if (streq(prop->name, name)) { |
cd296721 SW |
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(&prop->labels); | |
296 | } | |
297 | ||
a4da2e3e DG |
298 | void add_child(struct node *parent, struct node *child) |
299 | { | |
300 | struct node **p; | |
301 | ||
302 | child->next_sibling = NULL; | |
ed95d745 | 303 | child->parent = parent; |
a4da2e3e DG |
304 | |
305 | p = &parent->children; | |
306 | while (*p) | |
307 | p = &((*p)->next_sibling); | |
308 | ||
309 | *p = child; | |
310 | } | |
311 | ||
cd296721 SW |
312 | void delete_node_by_name(struct node *parent, char *name) |
313 | { | |
314 | struct node *node = parent->children; | |
315 | ||
316 | while (node) { | |
89d12310 | 317 | if (streq(node->name, name)) { |
cd296721 SW |
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(child); | |
333 | for_each_property(node, prop) | |
334 | delete_property(prop); | |
335 | delete_labels(&node->labels); | |
336 | } | |
337 | ||
6f05afcb | 338 | void append_to_property(struct node *node, |
9bb9c6a1 RH |
339 | char *name, const void *data, int len, |
340 | enum markertype type) | |
6f05afcb RH |
341 | { |
342 | struct data d; | |
343 | struct property *p; | |
344 | ||
345 | p = get_property(node, name); | |
346 | if (p) { | |
9bb9c6a1 RH |
347 | d = data_add_marker(p->val, type, name); |
348 | d = data_append_data(d, data, len); | |
6f05afcb RH |
349 | p->val = d; |
350 | } else { | |
9bb9c6a1 RH |
351 | d = data_add_marker(empty_data, type, name); |
352 | d = data_append_data(d, data, len); | |
c2e7075c | 353 | p = build_property(name, d, NULL); |
6f05afcb RH |
354 | add_property(node, p); |
355 | } | |
356 | } | |
357 | ||
658f29a5 | 358 | struct reserve_info *build_reserve_entry(uint64_t address, uint64_t size) |
a4da2e3e DG |
359 | { |
360 | struct reserve_info *new = xmalloc(sizeof(*new)); | |
361 | ||
658f29a5 JB |
362 | memset(new, 0, sizeof(*new)); |
363 | ||
89d12310 RH |
364 | new->address = address; |
365 | new->size = size; | |
a4da2e3e | 366 | |
a4da2e3e DG |
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 | ||
6f05afcb RH |
397 | struct dt_info *build_dt_info(unsigned int dtsflags, |
398 | struct reserve_info *reservelist, | |
399 | struct node *tree, uint32_t boot_cpuid_phys) | |
a4da2e3e | 400 | { |
6f05afcb | 401 | struct dt_info *dti; |
a4da2e3e | 402 | |
6f05afcb RH |
403 | dti = xmalloc(sizeof(*dti)); |
404 | dti->dtsflags = dtsflags; | |
405 | dti->reservelist = reservelist; | |
406 | dti->dt = tree; | |
407 | dti->boot_cpuid_phys = boot_cpuid_phys; | |
a4da2e3e | 408 | |
6f05afcb | 409 | return dti; |
a4da2e3e DG |
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)); | |
89d12310 | 438 | return fdt32_to_cpu(*((fdt32_t *)prop->val.val)); |
a4da2e3e DG |
439 | } |
440 | ||
79edff12 | 441 | cell_t propval_cell_n(struct property *prop, unsigned int n) |
4201d057 RH |
442 | { |
443 | assert(prop->val.len / sizeof(cell_t) >= n); | |
444 | return fdt32_to_cpu(*((fdt32_t *)prop->val.val + n)); | |
445 | } | |
446 | ||
658f29a5 JB |
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(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(c, label, node, prop); | |
492 | if (m) | |
493 | return m; | |
494 | } | |
495 | ||
496 | *prop = NULL; | |
497 | *node = NULL; | |
498 | return NULL; | |
499 | } | |
500 | ||
a4da2e3e DG |
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 | ||
cd296721 SW |
517 | if (!path || ! (*path)) { |
518 | if (tree->deleted) | |
519 | return NULL; | |
a4da2e3e | 520 | return tree; |
cd296721 | 521 | } |
a4da2e3e DG |
522 | |
523 | while (path[0] == '/') | |
524 | path++; | |
525 | ||
526 | p = strchr(path, '/'); | |
527 | ||
528 | for_each_child(tree, child) { | |
0cec114e | 529 | if (p && strprefixeq(path, p - path, child->name)) |
a4da2e3e DG |
530 | return get_node_by_path(child, 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; | |
658f29a5 | 541 | struct label *l; |
a4da2e3e DG |
542 | |
543 | assert(label && (strlen(label) > 0)); | |
544 | ||
658f29a5 JB |
545 | for_each_label(tree->labels, l) |
546 | if (streq(l->label, label)) | |
547 | return tree; | |
a4da2e3e DG |
548 | |
549 | for_each_child(tree, child) { | |
550 | node = get_node_by_label(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 | ||
9130ba88 RH |
562 | if ((phandle == 0) || (phandle == -1)) { |
563 | assert(generate_fixups); | |
564 | return NULL; | |
565 | } | |
a4da2e3e | 566 | |
cd296721 SW |
567 | if (tree->phandle == phandle) { |
568 | if (tree->deleted) | |
569 | return NULL; | |
a4da2e3e | 570 | return tree; |
cd296721 | 571 | } |
a4da2e3e DG |
572 | |
573 | for_each_child(tree, child) { | |
574 | node = get_node_by_phandle(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 | { | |
47605971 RH |
584 | if (streq(ref, "/")) |
585 | return tree; | |
586 | else if (ref[0] == '/') | |
a4da2e3e DG |
587 | return get_node_by_path(tree, ref); |
588 | else | |
589 | return get_node_by_label(tree, ref); | |
590 | } | |
591 | ||
592 | cell_t get_node_phandle(struct node *root, struct node *node) | |
593 | { | |
594 | static cell_t phandle = 1; /* FIXME: ick, static local */ | |
f858927f | 595 | struct data d = empty_data; |
a4da2e3e DG |
596 | |
597 | if ((node->phandle != 0) && (node->phandle != -1)) | |
598 | return node->phandle; | |
599 | ||
a4da2e3e DG |
600 | while (get_node_by_phandle(root, phandle)) |
601 | phandle++; | |
602 | ||
603 | node->phandle = phandle; | |
658f29a5 | 604 | |
f858927f RH |
605 | d = data_add_marker(d, TYPE_UINT32, NULL); |
606 | d = data_append_cell(d, phandle); | |
607 | ||
658f29a5 JB |
608 | if (!get_property(node, "linux,phandle") |
609 | && (phandle_format & PHANDLE_LEGACY)) | |
c2e7075c | 610 | add_property(node, build_property("linux,phandle", d, NULL)); |
658f29a5 JB |
611 | |
612 | if (!get_property(node, "phandle") | |
613 | && (phandle_format & PHANDLE_EPAPR)) | |
c2e7075c | 614 | add_property(node, build_property("phandle", d, NULL)); |
658f29a5 JB |
615 | |
616 | /* If the node *does* have a phandle property, we must | |
617 | * be dealing with a self-referencing phandle, which will be | |
618 | * fixed up momentarily in the caller */ | |
a4da2e3e DG |
619 | |
620 | return node->phandle; | |
621 | } | |
658f29a5 JB |
622 | |
623 | uint32_t guess_boot_cpuid(struct node *tree) | |
624 | { | |
625 | struct node *cpus, *bootcpu; | |
626 | struct property *reg; | |
627 | ||
628 | cpus = get_node_by_path(tree, "/cpus"); | |
629 | if (!cpus) | |
630 | return 0; | |
631 | ||
632 | ||
633 | bootcpu = cpus->children; | |
634 | if (!bootcpu) | |
635 | return 0; | |
636 | ||
637 | reg = get_property(bootcpu, "reg"); | |
638 | if (!reg || (reg->val.len != sizeof(uint32_t))) | |
639 | return 0; | |
640 | ||
641 | /* FIXME: Sanity check node? */ | |
642 | ||
643 | return propval_cell(reg); | |
644 | } | |
645 | ||
646 | static int cmp_reserve_info(const void *ax, const void *bx) | |
647 | { | |
648 | const struct reserve_info *a, *b; | |
649 | ||
650 | a = *((const struct reserve_info * const *)ax); | |
651 | b = *((const struct reserve_info * const *)bx); | |
652 | ||
89d12310 | 653 | if (a->address < b->address) |
658f29a5 | 654 | return -1; |
89d12310 | 655 | else if (a->address > b->address) |
658f29a5 | 656 | return 1; |
89d12310 | 657 | else if (a->size < b->size) |
658f29a5 | 658 | return -1; |
89d12310 | 659 | else if (a->size > b->size) |
658f29a5 JB |
660 | return 1; |
661 | else | |
662 | return 0; | |
663 | } | |
664 | ||
6f05afcb | 665 | static void sort_reserve_entries(struct dt_info *dti) |
658f29a5 JB |
666 | { |
667 | struct reserve_info *ri, **tbl; | |
668 | int n = 0, i = 0; | |
669 | ||
6f05afcb | 670 | for (ri = dti->reservelist; |
658f29a5 JB |
671 | ri; |
672 | ri = ri->next) | |
673 | n++; | |
674 | ||
675 | if (n == 0) | |
676 | return; | |
677 | ||
678 | tbl = xmalloc(n * sizeof(*tbl)); | |
679 | ||
6f05afcb | 680 | for (ri = dti->reservelist; |
658f29a5 JB |
681 | ri; |
682 | ri = ri->next) | |
683 | tbl[i++] = ri; | |
684 | ||
685 | qsort(tbl, n, sizeof(*tbl), cmp_reserve_info); | |
686 | ||
6f05afcb | 687 | dti->reservelist = tbl[0]; |
658f29a5 JB |
688 | for (i = 0; i < (n-1); i++) |
689 | tbl[i]->next = tbl[i+1]; | |
690 | tbl[n-1]->next = NULL; | |
691 | ||
692 | free(tbl); | |
693 | } | |
694 | ||
695 | static int cmp_prop(const void *ax, const void *bx) | |
696 | { | |
697 | const struct property *a, *b; | |
698 | ||
699 | a = *((const struct property * const *)ax); | |
700 | b = *((const struct property * const *)bx); | |
701 | ||
702 | return strcmp(a->name, b->name); | |
703 | } | |
704 | ||
705 | static void sort_properties(struct node *node) | |
706 | { | |
707 | int n = 0, i = 0; | |
708 | struct property *prop, **tbl; | |
709 | ||
cd296721 | 710 | for_each_property_withdel(node, prop) |
658f29a5 JB |
711 | n++; |
712 | ||
713 | if (n == 0) | |
714 | return; | |
715 | ||
716 | tbl = xmalloc(n * sizeof(*tbl)); | |
717 | ||
cd296721 | 718 | for_each_property_withdel(node, prop) |
658f29a5 JB |
719 | tbl[i++] = prop; |
720 | ||
721 | qsort(tbl, n, sizeof(*tbl), cmp_prop); | |
722 | ||
723 | node->proplist = tbl[0]; | |
724 | for (i = 0; i < (n-1); i++) | |
725 | tbl[i]->next = tbl[i+1]; | |
726 | tbl[n-1]->next = NULL; | |
727 | ||
728 | free(tbl); | |
729 | } | |
730 | ||
731 | static int cmp_subnode(const void *ax, const void *bx) | |
732 | { | |
733 | const struct node *a, *b; | |
734 | ||
735 | a = *((const struct node * const *)ax); | |
736 | b = *((const struct node * const *)bx); | |
737 | ||
738 | return strcmp(a->name, b->name); | |
739 | } | |
740 | ||
741 | static void sort_subnodes(struct node *node) | |
742 | { | |
743 | int n = 0, i = 0; | |
744 | struct node *subnode, **tbl; | |
745 | ||
cd296721 | 746 | for_each_child_withdel(node, subnode) |
658f29a5 JB |
747 | n++; |
748 | ||
749 | if (n == 0) | |
750 | return; | |
751 | ||
752 | tbl = xmalloc(n * sizeof(*tbl)); | |
753 | ||
cd296721 | 754 | for_each_child_withdel(node, subnode) |
658f29a5 JB |
755 | tbl[i++] = subnode; |
756 | ||
757 | qsort(tbl, n, sizeof(*tbl), cmp_subnode); | |
758 | ||
759 | node->children = tbl[0]; | |
760 | for (i = 0; i < (n-1); i++) | |
761 | tbl[i]->next_sibling = tbl[i+1]; | |
762 | tbl[n-1]->next_sibling = NULL; | |
763 | ||
764 | free(tbl); | |
765 | } | |
766 | ||
767 | static void sort_node(struct node *node) | |
768 | { | |
769 | struct node *c; | |
770 | ||
771 | sort_properties(node); | |
772 | sort_subnodes(node); | |
cd296721 | 773 | for_each_child_withdel(node, c) |
658f29a5 JB |
774 | sort_node(c); |
775 | } | |
776 | ||
6f05afcb RH |
777 | void sort_tree(struct dt_info *dti) |
778 | { | |
779 | sort_reserve_entries(dti); | |
780 | sort_node(dti->dt); | |
781 | } | |
782 | ||
783 | /* utility helper to avoid code duplication */ | |
784 | static struct node *build_and_name_child_node(struct node *parent, char *name) | |
785 | { | |
786 | struct node *node; | |
787 | ||
c2e7075c | 788 | node = build_node(NULL, NULL, NULL); |
6f05afcb RH |
789 | name_node(node, xstrdup(name)); |
790 | add_child(parent, node); | |
791 | ||
792 | return node; | |
793 | } | |
794 | ||
795 | static struct node *build_root_node(struct node *dt, char *name) | |
796 | { | |
797 | struct node *an; | |
798 | ||
799 | an = get_subnode(dt, name); | |
800 | if (!an) | |
801 | an = build_and_name_child_node(dt, name); | |
802 | ||
803 | if (!an) | |
804 | die("Could not build root node /%s\n", name); | |
805 | ||
806 | return an; | |
807 | } | |
808 | ||
809 | static bool any_label_tree(struct dt_info *dti, struct node *node) | |
810 | { | |
811 | struct node *c; | |
812 | ||
813 | if (node->labels) | |
814 | return true; | |
815 | ||
816 | for_each_child(node, c) | |
817 | if (any_label_tree(dti, c)) | |
818 | return true; | |
819 | ||
820 | return false; | |
821 | } | |
822 | ||
823 | static void generate_label_tree_internal(struct dt_info *dti, | |
824 | struct node *an, struct node *node, | |
825 | bool allocph) | |
826 | { | |
827 | struct node *dt = dti->dt; | |
828 | struct node *c; | |
829 | struct property *p; | |
830 | struct label *l; | |
831 | ||
832 | /* if there are labels */ | |
833 | if (node->labels) { | |
834 | ||
835 | /* now add the label in the node */ | |
836 | for_each_label(node->labels, l) { | |
837 | ||
838 | /* check whether the label already exists */ | |
839 | p = get_property(an, l->label); | |
840 | if (p) { | |
841 | fprintf(stderr, "WARNING: label %s already" | |
842 | " exists in /%s", l->label, | |
843 | an->name); | |
844 | continue; | |
845 | } | |
846 | ||
847 | /* insert it */ | |
848 | p = build_property(l->label, | |
9bb9c6a1 RH |
849 | data_copy_escape_string(node->fullpath, |
850 | strlen(node->fullpath)), | |
c2e7075c | 851 | NULL); |
6f05afcb RH |
852 | add_property(an, p); |
853 | } | |
854 | ||
855 | /* force allocation of a phandle for this node */ | |
856 | if (allocph) | |
857 | (void)get_node_phandle(dt, node); | |
858 | } | |
859 | ||
860 | for_each_child(node, c) | |
861 | generate_label_tree_internal(dti, an, c, allocph); | |
862 | } | |
863 | ||
864 | static bool any_fixup_tree(struct dt_info *dti, struct node *node) | |
865 | { | |
866 | struct node *c; | |
867 | struct property *prop; | |
868 | struct marker *m; | |
869 | ||
870 | for_each_property(node, prop) { | |
871 | m = prop->val.markers; | |
872 | for_each_marker_of_type(m, REF_PHANDLE) { | |
873 | if (!get_node_by_ref(dti->dt, m->ref)) | |
874 | return true; | |
875 | } | |
876 | } | |
877 | ||
878 | for_each_child(node, c) { | |
879 | if (any_fixup_tree(dti, c)) | |
880 | return true; | |
881 | } | |
882 | ||
883 | return false; | |
884 | } | |
885 | ||
886 | static void add_fixup_entry(struct dt_info *dti, struct node *fn, | |
887 | struct node *node, struct property *prop, | |
888 | struct marker *m) | |
658f29a5 | 889 | { |
6f05afcb RH |
890 | char *entry; |
891 | ||
892 | /* m->ref can only be a REF_PHANDLE, but check anyway */ | |
893 | assert(m->type == REF_PHANDLE); | |
894 | ||
895 | /* there shouldn't be any ':' in the arguments */ | |
896 | if (strchr(node->fullpath, ':') || strchr(prop->name, ':')) | |
897 | die("arguments should not contain ':'\n"); | |
898 | ||
899 | xasprintf(&entry, "%s:%s:%u", | |
900 | node->fullpath, prop->name, m->offset); | |
9bb9c6a1 | 901 | append_to_property(fn, m->ref, entry, strlen(entry) + 1, TYPE_STRING); |
89d12310 RH |
902 | |
903 | free(entry); | |
6f05afcb RH |
904 | } |
905 | ||
906 | static void generate_fixups_tree_internal(struct dt_info *dti, | |
907 | struct node *fn, | |
908 | struct node *node) | |
909 | { | |
910 | struct node *dt = dti->dt; | |
911 | struct node *c; | |
912 | struct property *prop; | |
913 | struct marker *m; | |
914 | struct node *refnode; | |
915 | ||
916 | for_each_property(node, prop) { | |
917 | m = prop->val.markers; | |
918 | for_each_marker_of_type(m, REF_PHANDLE) { | |
919 | refnode = get_node_by_ref(dt, m->ref); | |
920 | if (!refnode) | |
921 | add_fixup_entry(dti, fn, node, prop, m); | |
922 | } | |
923 | } | |
924 | ||
925 | for_each_child(node, c) | |
926 | generate_fixups_tree_internal(dti, fn, c); | |
927 | } | |
928 | ||
929 | static bool any_local_fixup_tree(struct dt_info *dti, struct node *node) | |
930 | { | |
931 | struct node *c; | |
932 | struct property *prop; | |
933 | struct marker *m; | |
934 | ||
935 | for_each_property(node, prop) { | |
936 | m = prop->val.markers; | |
937 | for_each_marker_of_type(m, REF_PHANDLE) { | |
938 | if (get_node_by_ref(dti->dt, m->ref)) | |
939 | return true; | |
940 | } | |
941 | } | |
942 | ||
943 | for_each_child(node, c) { | |
944 | if (any_local_fixup_tree(dti, c)) | |
945 | return true; | |
946 | } | |
947 | ||
948 | return false; | |
949 | } | |
950 | ||
951 | static void add_local_fixup_entry(struct dt_info *dti, | |
952 | struct node *lfn, struct node *node, | |
953 | struct property *prop, struct marker *m, | |
954 | struct node *refnode) | |
955 | { | |
956 | struct node *wn, *nwn; /* local fixup node, walk node, new */ | |
89d12310 | 957 | fdt32_t value_32; |
6f05afcb RH |
958 | char **compp; |
959 | int i, depth; | |
960 | ||
9bb9c6a1 | 961 | /* walk back retrieving depth */ |
6f05afcb RH |
962 | depth = 0; |
963 | for (wn = node; wn; wn = wn->parent) | |
964 | depth++; | |
965 | ||
966 | /* allocate name array */ | |
967 | compp = xmalloc(sizeof(*compp) * depth); | |
968 | ||
969 | /* store names in the array */ | |
970 | for (wn = node, i = depth - 1; wn; wn = wn->parent, i--) | |
971 | compp[i] = wn->name; | |
972 | ||
973 | /* walk the path components creating nodes if they don't exist */ | |
974 | for (wn = lfn, i = 1; i < depth; i++, wn = nwn) { | |
975 | /* if no node exists, create it */ | |
976 | nwn = get_subnode(wn, compp[i]); | |
977 | if (!nwn) | |
978 | nwn = build_and_name_child_node(wn, compp[i]); | |
979 | } | |
980 | ||
981 | free(compp); | |
982 | ||
983 | value_32 = cpu_to_fdt32(m->offset); | |
9bb9c6a1 | 984 | append_to_property(wn, prop->name, &value_32, sizeof(value_32), TYPE_UINT32); |
6f05afcb RH |
985 | } |
986 | ||
987 | static void generate_local_fixups_tree_internal(struct dt_info *dti, | |
988 | struct node *lfn, | |
989 | struct node *node) | |
990 | { | |
991 | struct node *dt = dti->dt; | |
992 | struct node *c; | |
993 | struct property *prop; | |
994 | struct marker *m; | |
995 | struct node *refnode; | |
996 | ||
997 | for_each_property(node, prop) { | |
998 | m = prop->val.markers; | |
999 | for_each_marker_of_type(m, REF_PHANDLE) { | |
1000 | refnode = get_node_by_ref(dt, m->ref); | |
1001 | if (refnode) | |
1002 | add_local_fixup_entry(dti, lfn, node, prop, m, refnode); | |
1003 | } | |
1004 | } | |
1005 | ||
1006 | for_each_child(node, c) | |
1007 | generate_local_fixups_tree_internal(dti, lfn, c); | |
1008 | } | |
1009 | ||
1010 | void generate_label_tree(struct dt_info *dti, char *name, bool allocph) | |
1011 | { | |
1012 | if (!any_label_tree(dti, dti->dt)) | |
1013 | return; | |
1014 | generate_label_tree_internal(dti, build_root_node(dti->dt, name), | |
1015 | dti->dt, allocph); | |
1016 | } | |
1017 | ||
1018 | void generate_fixups_tree(struct dt_info *dti, char *name) | |
1019 | { | |
1020 | if (!any_fixup_tree(dti, dti->dt)) | |
1021 | return; | |
1022 | generate_fixups_tree_internal(dti, build_root_node(dti->dt, name), | |
1023 | dti->dt); | |
1024 | } | |
1025 | ||
1026 | void generate_local_fixups_tree(struct dt_info *dti, char *name) | |
1027 | { | |
1028 | if (!any_local_fixup_tree(dti, dti->dt)) | |
1029 | return; | |
1030 | generate_local_fixups_tree_internal(dti, build_root_node(dti->dt, name), | |
1031 | dti->dt); | |
658f29a5 | 1032 | } |