1204431Sraj/* 2204431Sraj * (C) Copyright David Gibson <dwg@au1.ibm.com>, IBM Corporation. 2005. 3204431Sraj * 4204431Sraj * 5204431Sraj * This program is free software; you can redistribute it and/or 6204431Sraj * modify it under the terms of the GNU General Public License as 7204431Sraj * published by the Free Software Foundation; either version 2 of the 8204431Sraj * License, or (at your option) any later version. 9204431Sraj * 10204431Sraj * This program is distributed in the hope that it will be useful, 11204431Sraj * but WITHOUT ANY WARRANTY; without even the implied warranty of 12204431Sraj * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13204431Sraj * General Public License for more details. 14204431Sraj * 15204431Sraj * You should have received a copy of the GNU General Public License 16204431Sraj * along with this program; if not, write to the Free Software 17204431Sraj * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 18204431Sraj * USA 19204431Sraj */ 20204431Sraj 21204431Sraj#include "dtc.h" 22204431Sraj 23204431Sraj/* 24204431Sraj * Tree building functions 25204431Sraj */ 26204431Sraj 27238742Simpvoid add_label(struct label **labels, char *label) 28204431Sraj{ 29238742Simp struct label *new; 30238742Simp 31238742Simp /* Make sure the label isn't already there */ 32238742Simp for_each_label(*labels, new) 33238742Simp if (streq(new->label, label)) 34238742Simp return; 35238742Simp 36238742Simp new = xmalloc(sizeof(*new)); 37238742Simp new->label = label; 38238742Simp new->next = *labels; 39238742Simp *labels = new; 40238742Simp} 41238742Simp 42238742Simpstruct property *build_property(char *name, struct data val) 43238742Simp{ 44204431Sraj struct property *new = xmalloc(sizeof(*new)); 45204431Sraj 46238742Simp memset(new, 0, sizeof(*new)); 47238742Simp 48204431Sraj new->name = name; 49204431Sraj new->val = val; 50204431Sraj 51204431Sraj return new; 52204431Sraj} 53204431Sraj 54204431Srajstruct property *chain_property(struct property *first, struct property *list) 55204431Sraj{ 56204431Sraj assert(first->next == NULL); 57204431Sraj 58204431Sraj first->next = list; 59204431Sraj return first; 60204431Sraj} 61204431Sraj 62204431Srajstruct property *reverse_properties(struct property *first) 63204431Sraj{ 64204431Sraj struct property *p = first; 65204431Sraj struct property *head = NULL; 66204431Sraj struct property *next; 67204431Sraj 68204431Sraj while (p) { 69204431Sraj next = p->next; 70204431Sraj p->next = head; 71204431Sraj head = p; 72204431Sraj p = next; 73204431Sraj } 74204431Sraj return head; 75204431Sraj} 76204431Sraj 77204431Srajstruct node *build_node(struct property *proplist, struct node *children) 78204431Sraj{ 79204431Sraj struct node *new = xmalloc(sizeof(*new)); 80204431Sraj struct node *child; 81204431Sraj 82204431Sraj memset(new, 0, sizeof(*new)); 83204431Sraj 84204431Sraj new->proplist = reverse_properties(proplist); 85204431Sraj new->children = children; 86204431Sraj 87204431Sraj for_each_child(new, child) { 88204431Sraj child->parent = new; 89204431Sraj } 90204431Sraj 91204431Sraj return new; 92204431Sraj} 93204431Sraj 94238742Simpstruct node *name_node(struct node *node, char *name) 95204431Sraj{ 96204431Sraj assert(node->name == NULL); 97204431Sraj 98204431Sraj node->name = name; 99204431Sraj 100204431Sraj return node; 101204431Sraj} 102204431Sraj 103238742Simpstruct node *merge_nodes(struct node *old_node, struct node *new_node) 104238742Simp{ 105238742Simp struct property *new_prop, *old_prop; 106238742Simp struct node *new_child, *old_child; 107238742Simp struct label *l; 108238742Simp 109238742Simp /* Add new node labels to old node */ 110238742Simp for_each_label(new_node->labels, l) 111238742Simp add_label(&old_node->labels, l->label); 112238742Simp 113238742Simp /* Move properties from the new node to the old node. If there 114238742Simp * is a collision, replace the old value with the new */ 115238742Simp while (new_node->proplist) { 116238742Simp /* Pop the property off the list */ 117238742Simp new_prop = new_node->proplist; 118238742Simp new_node->proplist = new_prop->next; 119238742Simp new_prop->next = NULL; 120238742Simp 121238742Simp /* Look for a collision, set new value if there is */ 122238742Simp for_each_property(old_node, old_prop) { 123238742Simp if (streq(old_prop->name, new_prop->name)) { 124238742Simp /* Add new labels to old property */ 125238742Simp for_each_label(new_prop->labels, l) 126238742Simp add_label(&old_prop->labels, l->label); 127238742Simp 128238742Simp old_prop->val = new_prop->val; 129238742Simp free(new_prop); 130238742Simp new_prop = NULL; 131238742Simp break; 132238742Simp } 133238742Simp } 134238742Simp 135238742Simp /* if no collision occurred, add property to the old node. */ 136238742Simp if (new_prop) 137238742Simp add_property(old_node, new_prop); 138238742Simp } 139238742Simp 140238742Simp /* Move the override child nodes into the primary node. If 141238742Simp * there is a collision, then merge the nodes. */ 142238742Simp while (new_node->children) { 143238742Simp /* Pop the child node off the list */ 144238742Simp new_child = new_node->children; 145238742Simp new_node->children = new_child->next_sibling; 146238742Simp new_child->parent = NULL; 147238742Simp new_child->next_sibling = NULL; 148238742Simp 149238742Simp /* Search for a collision. Merge if there is */ 150238742Simp for_each_child(old_node, old_child) { 151238742Simp if (streq(old_child->name, new_child->name)) { 152238742Simp merge_nodes(old_child, new_child); 153238742Simp new_child = NULL; 154238742Simp break; 155238742Simp } 156238742Simp } 157238742Simp 158238742Simp /* if no collision occured, add child to the old node. */ 159238742Simp if (new_child) 160238742Simp add_child(old_node, new_child); 161238742Simp } 162238742Simp 163238742Simp /* The new node contents are now merged into the old node. Free 164238742Simp * the new node. */ 165238742Simp free(new_node); 166238742Simp 167238742Simp return old_node; 168238742Simp} 169238742Simp 170204431Srajstruct node *chain_node(struct node *first, struct node *list) 171204431Sraj{ 172204431Sraj assert(first->next_sibling == NULL); 173204431Sraj 174204431Sraj first->next_sibling = list; 175204431Sraj return first; 176204431Sraj} 177204431Sraj 178204431Srajvoid add_property(struct node *node, struct property *prop) 179204431Sraj{ 180204431Sraj struct property **p; 181204431Sraj 182204431Sraj prop->next = NULL; 183204431Sraj 184204431Sraj p = &node->proplist; 185204431Sraj while (*p) 186204431Sraj p = &((*p)->next); 187204431Sraj 188204431Sraj *p = prop; 189204431Sraj} 190204431Sraj 191204431Srajvoid add_child(struct node *parent, struct node *child) 192204431Sraj{ 193204431Sraj struct node **p; 194204431Sraj 195204431Sraj child->next_sibling = NULL; 196204431Sraj child->parent = parent; 197204431Sraj 198204431Sraj p = &parent->children; 199204431Sraj while (*p) 200204431Sraj p = &((*p)->next_sibling); 201204431Sraj 202204431Sraj *p = child; 203204431Sraj} 204204431Sraj 205238742Simpstruct reserve_info *build_reserve_entry(uint64_t address, uint64_t size) 206204431Sraj{ 207204431Sraj struct reserve_info *new = xmalloc(sizeof(*new)); 208204431Sraj 209238742Simp memset(new, 0, sizeof(*new)); 210238742Simp 211204431Sraj new->re.address = address; 212204431Sraj new->re.size = size; 213204431Sraj 214204431Sraj return new; 215204431Sraj} 216204431Sraj 217204431Srajstruct reserve_info *chain_reserve_entry(struct reserve_info *first, 218204431Sraj struct reserve_info *list) 219204431Sraj{ 220204431Sraj assert(first->next == NULL); 221204431Sraj 222204431Sraj first->next = list; 223204431Sraj return first; 224204431Sraj} 225204431Sraj 226204431Srajstruct reserve_info *add_reserve_entry(struct reserve_info *list, 227204431Sraj struct reserve_info *new) 228204431Sraj{ 229204431Sraj struct reserve_info *last; 230204431Sraj 231204431Sraj new->next = NULL; 232204431Sraj 233204431Sraj if (! list) 234204431Sraj return new; 235204431Sraj 236204431Sraj for (last = list; last->next; last = last->next) 237204431Sraj ; 238204431Sraj 239204431Sraj last->next = new; 240204431Sraj 241204431Sraj return list; 242204431Sraj} 243204431Sraj 244204431Srajstruct boot_info *build_boot_info(struct reserve_info *reservelist, 245204431Sraj struct node *tree, uint32_t boot_cpuid_phys) 246204431Sraj{ 247204431Sraj struct boot_info *bi; 248204431Sraj 249204431Sraj bi = xmalloc(sizeof(*bi)); 250204431Sraj bi->reservelist = reservelist; 251204431Sraj bi->dt = tree; 252204431Sraj bi->boot_cpuid_phys = boot_cpuid_phys; 253204431Sraj 254204431Sraj return bi; 255204431Sraj} 256204431Sraj 257204431Sraj/* 258204431Sraj * Tree accessor functions 259204431Sraj */ 260204431Sraj 261204431Srajconst char *get_unitname(struct node *node) 262204431Sraj{ 263204431Sraj if (node->name[node->basenamelen] == '\0') 264204431Sraj return ""; 265204431Sraj else 266204431Sraj return node->name + node->basenamelen + 1; 267204431Sraj} 268204431Sraj 269204431Srajstruct property *get_property(struct node *node, const char *propname) 270204431Sraj{ 271204431Sraj struct property *prop; 272204431Sraj 273204431Sraj for_each_property(node, prop) 274204431Sraj if (streq(prop->name, propname)) 275204431Sraj return prop; 276204431Sraj 277204431Sraj return NULL; 278204431Sraj} 279204431Sraj 280204431Srajcell_t propval_cell(struct property *prop) 281204431Sraj{ 282204431Sraj assert(prop->val.len == sizeof(cell_t)); 283204431Sraj return fdt32_to_cpu(*((cell_t *)prop->val.val)); 284204431Sraj} 285204431Sraj 286238742Simpstruct property *get_property_by_label(struct node *tree, const char *label, 287238742Simp struct node **node) 288238742Simp{ 289238742Simp struct property *prop; 290238742Simp struct node *c; 291238742Simp 292238742Simp *node = tree; 293238742Simp 294238742Simp for_each_property(tree, prop) { 295238742Simp struct label *l; 296238742Simp 297238742Simp for_each_label(prop->labels, l) 298238742Simp if (streq(l->label, label)) 299238742Simp return prop; 300238742Simp } 301238742Simp 302238742Simp for_each_child(tree, c) { 303238742Simp prop = get_property_by_label(c, label, node); 304238742Simp if (prop) 305238742Simp return prop; 306238742Simp } 307238742Simp 308238742Simp *node = NULL; 309238742Simp return NULL; 310238742Simp} 311238742Simp 312238742Simpstruct marker *get_marker_label(struct node *tree, const char *label, 313238742Simp struct node **node, struct property **prop) 314238742Simp{ 315238742Simp struct marker *m; 316238742Simp struct property *p; 317238742Simp struct node *c; 318238742Simp 319238742Simp *node = tree; 320238742Simp 321238742Simp for_each_property(tree, p) { 322238742Simp *prop = p; 323238742Simp m = p->val.markers; 324238742Simp for_each_marker_of_type(m, LABEL) 325238742Simp if (streq(m->ref, label)) 326238742Simp return m; 327238742Simp } 328238742Simp 329238742Simp for_each_child(tree, c) { 330238742Simp m = get_marker_label(c, label, node, prop); 331238742Simp if (m) 332238742Simp return m; 333238742Simp } 334238742Simp 335238742Simp *prop = NULL; 336238742Simp *node = NULL; 337238742Simp return NULL; 338238742Simp} 339238742Simp 340204431Srajstruct node *get_subnode(struct node *node, const char *nodename) 341204431Sraj{ 342204431Sraj struct node *child; 343204431Sraj 344204431Sraj for_each_child(node, child) 345204431Sraj if (streq(child->name, nodename)) 346204431Sraj return child; 347204431Sraj 348204431Sraj return NULL; 349204431Sraj} 350204431Sraj 351204431Srajstruct node *get_node_by_path(struct node *tree, const char *path) 352204431Sraj{ 353204431Sraj const char *p; 354204431Sraj struct node *child; 355204431Sraj 356204431Sraj if (!path || ! (*path)) 357204431Sraj return tree; 358204431Sraj 359204431Sraj while (path[0] == '/') 360204431Sraj path++; 361204431Sraj 362204431Sraj p = strchr(path, '/'); 363204431Sraj 364204431Sraj for_each_child(tree, child) { 365204431Sraj if (p && strneq(path, child->name, p-path)) 366204431Sraj return get_node_by_path(child, p+1); 367204431Sraj else if (!p && streq(path, child->name)) 368204431Sraj return child; 369204431Sraj } 370204431Sraj 371204431Sraj return NULL; 372204431Sraj} 373204431Sraj 374204431Srajstruct node *get_node_by_label(struct node *tree, const char *label) 375204431Sraj{ 376204431Sraj struct node *child, *node; 377238742Simp struct label *l; 378204431Sraj 379204431Sraj assert(label && (strlen(label) > 0)); 380204431Sraj 381238742Simp for_each_label(tree->labels, l) 382238742Simp if (streq(l->label, label)) 383238742Simp return tree; 384204431Sraj 385204431Sraj for_each_child(tree, child) { 386204431Sraj node = get_node_by_label(child, label); 387204431Sraj if (node) 388204431Sraj return node; 389204431Sraj } 390204431Sraj 391204431Sraj return NULL; 392204431Sraj} 393204431Sraj 394204431Srajstruct node *get_node_by_phandle(struct node *tree, cell_t phandle) 395204431Sraj{ 396204431Sraj struct node *child, *node; 397204431Sraj 398204431Sraj assert((phandle != 0) && (phandle != -1)); 399204431Sraj 400204431Sraj if (tree->phandle == phandle) 401204431Sraj return tree; 402204431Sraj 403204431Sraj for_each_child(tree, child) { 404204431Sraj node = get_node_by_phandle(child, phandle); 405204431Sraj if (node) 406204431Sraj return node; 407204431Sraj } 408204431Sraj 409204431Sraj return NULL; 410204431Sraj} 411204431Sraj 412204431Srajstruct node *get_node_by_ref(struct node *tree, const char *ref) 413204431Sraj{ 414204431Sraj if (ref[0] == '/') 415204431Sraj return get_node_by_path(tree, ref); 416204431Sraj else 417204431Sraj return get_node_by_label(tree, ref); 418204431Sraj} 419204431Sraj 420204431Srajcell_t get_node_phandle(struct node *root, struct node *node) 421204431Sraj{ 422204431Sraj static cell_t phandle = 1; /* FIXME: ick, static local */ 423204431Sraj 424204431Sraj if ((node->phandle != 0) && (node->phandle != -1)) 425204431Sraj return node->phandle; 426204431Sraj 427204431Sraj while (get_node_by_phandle(root, phandle)) 428204431Sraj phandle++; 429204431Sraj 430204431Sraj node->phandle = phandle; 431204431Sraj 432204433Sraj if (!get_property(node, "linux,phandle") 433204433Sraj && (phandle_format & PHANDLE_LEGACY)) 434204433Sraj add_property(node, 435204433Sraj build_property("linux,phandle", 436238742Simp data_append_cell(empty_data, phandle))); 437204433Sraj 438204433Sraj if (!get_property(node, "phandle") 439204433Sraj && (phandle_format & PHANDLE_EPAPR)) 440204433Sraj add_property(node, 441204433Sraj build_property("phandle", 442238742Simp data_append_cell(empty_data, phandle))); 443204433Sraj 444204433Sraj /* If the node *does* have a phandle property, we must 445204433Sraj * be dealing with a self-referencing phandle, which will be 446204433Sraj * fixed up momentarily in the caller */ 447204433Sraj 448204431Sraj return node->phandle; 449204431Sraj} 450238742Simp 451238742Simpuint32_t guess_boot_cpuid(struct node *tree) 452238742Simp{ 453238742Simp struct node *cpus, *bootcpu; 454238742Simp struct property *reg; 455238742Simp 456238742Simp cpus = get_node_by_path(tree, "/cpus"); 457238742Simp if (!cpus) 458238742Simp return 0; 459238742Simp 460238742Simp 461238742Simp bootcpu = cpus->children; 462238742Simp if (!bootcpu) 463238742Simp return 0; 464238742Simp 465238742Simp reg = get_property(bootcpu, "reg"); 466238742Simp if (!reg || (reg->val.len != sizeof(uint32_t))) 467238742Simp return 0; 468238742Simp 469238742Simp /* FIXME: Sanity check node? */ 470238742Simp 471238742Simp return propval_cell(reg); 472238742Simp} 473238742Simp 474238742Simpstatic int cmp_reserve_info(const void *ax, const void *bx) 475238742Simp{ 476238742Simp const struct reserve_info *a, *b; 477238742Simp 478238742Simp a = *((const struct reserve_info * const *)ax); 479238742Simp b = *((const struct reserve_info * const *)bx); 480238742Simp 481238742Simp if (a->re.address < b->re.address) 482238742Simp return -1; 483238742Simp else if (a->re.address > b->re.address) 484238742Simp return 1; 485238742Simp else if (a->re.size < b->re.size) 486238742Simp return -1; 487238742Simp else if (a->re.size > b->re.size) 488238742Simp return 1; 489238742Simp else 490238742Simp return 0; 491238742Simp} 492238742Simp 493238742Simpstatic void sort_reserve_entries(struct boot_info *bi) 494238742Simp{ 495238742Simp struct reserve_info *ri, **tbl; 496238742Simp int n = 0, i = 0; 497238742Simp 498238742Simp for (ri = bi->reservelist; 499238742Simp ri; 500238742Simp ri = ri->next) 501238742Simp n++; 502238742Simp 503238742Simp if (n == 0) 504238742Simp return; 505238742Simp 506238742Simp tbl = xmalloc(n * sizeof(*tbl)); 507238742Simp 508238742Simp for (ri = bi->reservelist; 509238742Simp ri; 510238742Simp ri = ri->next) 511238742Simp tbl[i++] = ri; 512238742Simp 513238742Simp qsort(tbl, n, sizeof(*tbl), cmp_reserve_info); 514238742Simp 515238742Simp bi->reservelist = tbl[0]; 516238742Simp for (i = 0; i < (n-1); i++) 517238742Simp tbl[i]->next = tbl[i+1]; 518238742Simp tbl[n-1]->next = NULL; 519238742Simp 520238742Simp free(tbl); 521238742Simp} 522238742Simp 523238742Simpstatic int cmp_prop(const void *ax, const void *bx) 524238742Simp{ 525238742Simp const struct property *a, *b; 526238742Simp 527238742Simp a = *((const struct property * const *)ax); 528238742Simp b = *((const struct property * const *)bx); 529238742Simp 530238742Simp return strcmp(a->name, b->name); 531238742Simp} 532238742Simp 533238742Simpstatic void sort_properties(struct node *node) 534238742Simp{ 535238742Simp int n = 0, i = 0; 536238742Simp struct property *prop, **tbl; 537238742Simp 538238742Simp for_each_property(node, prop) 539238742Simp n++; 540238742Simp 541238742Simp if (n == 0) 542238742Simp return; 543238742Simp 544238742Simp tbl = xmalloc(n * sizeof(*tbl)); 545238742Simp 546238742Simp for_each_property(node, prop) 547238742Simp tbl[i++] = prop; 548238742Simp 549238742Simp qsort(tbl, n, sizeof(*tbl), cmp_prop); 550238742Simp 551238742Simp node->proplist = tbl[0]; 552238742Simp for (i = 0; i < (n-1); i++) 553238742Simp tbl[i]->next = tbl[i+1]; 554238742Simp tbl[n-1]->next = NULL; 555238742Simp 556238742Simp free(tbl); 557238742Simp} 558238742Simp 559238742Simpstatic int cmp_subnode(const void *ax, const void *bx) 560238742Simp{ 561238742Simp const struct node *a, *b; 562238742Simp 563238742Simp a = *((const struct node * const *)ax); 564238742Simp b = *((const struct node * const *)bx); 565238742Simp 566238742Simp return strcmp(a->name, b->name); 567238742Simp} 568238742Simp 569238742Simpstatic void sort_subnodes(struct node *node) 570238742Simp{ 571238742Simp int n = 0, i = 0; 572238742Simp struct node *subnode, **tbl; 573238742Simp 574238742Simp for_each_child(node, subnode) 575238742Simp n++; 576238742Simp 577238742Simp if (n == 0) 578238742Simp return; 579238742Simp 580238742Simp tbl = xmalloc(n * sizeof(*tbl)); 581238742Simp 582238742Simp for_each_child(node, subnode) 583238742Simp tbl[i++] = subnode; 584238742Simp 585238742Simp qsort(tbl, n, sizeof(*tbl), cmp_subnode); 586238742Simp 587238742Simp node->children = tbl[0]; 588238742Simp for (i = 0; i < (n-1); i++) 589238742Simp tbl[i]->next_sibling = tbl[i+1]; 590238742Simp tbl[n-1]->next_sibling = NULL; 591238742Simp 592238742Simp free(tbl); 593238742Simp} 594238742Simp 595238742Simpstatic void sort_node(struct node *node) 596238742Simp{ 597238742Simp struct node *c; 598238742Simp 599238742Simp sort_properties(node); 600238742Simp sort_subnodes(node); 601238742Simp for_each_child(node, c) 602238742Simp sort_node(c); 603238742Simp} 604238742Simp 605238742Simpvoid sort_tree(struct boot_info *bi) 606238742Simp{ 607238742Simp sort_reserve_entries(bi); 608238742Simp sort_node(bi->dt); 609238742Simp} 610