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