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