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 */ 32261215Simp for_each_label_withdel(*labels, new) 33261215Simp if (streq(new->label, label)) { 34261215Simp new->deleted = 0; 35238742Simp return; 36261215Simp } 37238742Simp 38238742Simp new = xmalloc(sizeof(*new)); 39261215Simp memset(new, 0, sizeof(*new)); 40238742Simp new->label = label; 41238742Simp new->next = *labels; 42238742Simp *labels = new; 43238742Simp} 44238742Simp 45261215Simpvoid delete_labels(struct label **labels) 46261215Simp{ 47261215Simp struct label *label; 48261215Simp 49261215Simp for_each_label(*labels, label) 50261215Simp label->deleted = 1; 51261215Simp} 52261215Simp 53238742Simpstruct property *build_property(char *name, struct data val) 54238742Simp{ 55204431Sraj struct property *new = xmalloc(sizeof(*new)); 56204431Sraj 57238742Simp memset(new, 0, sizeof(*new)); 58238742Simp 59204431Sraj new->name = name; 60204431Sraj new->val = val; 61204431Sraj 62204431Sraj return new; 63204431Sraj} 64204431Sraj 65261215Simpstruct property *build_property_delete(char *name) 66261215Simp{ 67261215Simp struct property *new = xmalloc(sizeof(*new)); 68261215Simp 69261215Simp memset(new, 0, sizeof(*new)); 70261215Simp 71261215Simp new->name = name; 72261215Simp new->deleted = 1; 73261215Simp 74261215Simp return new; 75261215Simp} 76261215Simp 77204431Srajstruct property *chain_property(struct property *first, struct property *list) 78204431Sraj{ 79204431Sraj assert(first->next == NULL); 80204431Sraj 81204431Sraj first->next = list; 82204431Sraj return first; 83204431Sraj} 84204431Sraj 85204431Srajstruct property *reverse_properties(struct property *first) 86204431Sraj{ 87204431Sraj struct property *p = first; 88204431Sraj struct property *head = NULL; 89204431Sraj struct property *next; 90204431Sraj 91204431Sraj while (p) { 92204431Sraj next = p->next; 93204431Sraj p->next = head; 94204431Sraj head = p; 95204431Sraj p = next; 96204431Sraj } 97204431Sraj return head; 98204431Sraj} 99204431Sraj 100204431Srajstruct node *build_node(struct property *proplist, struct node *children) 101204431Sraj{ 102204431Sraj struct node *new = xmalloc(sizeof(*new)); 103204431Sraj struct node *child; 104204431Sraj 105204431Sraj memset(new, 0, sizeof(*new)); 106204431Sraj 107204431Sraj new->proplist = reverse_properties(proplist); 108204431Sraj new->children = children; 109204431Sraj 110204431Sraj for_each_child(new, child) { 111204431Sraj child->parent = new; 112204431Sraj } 113204431Sraj 114204431Sraj return new; 115204431Sraj} 116204431Sraj 117261215Simpstruct node *build_node_delete(void) 118261215Simp{ 119261215Simp struct node *new = xmalloc(sizeof(*new)); 120261215Simp 121261215Simp memset(new, 0, sizeof(*new)); 122261215Simp 123261215Simp new->deleted = 1; 124261215Simp 125261215Simp return new; 126261215Simp} 127261215Simp 128238742Simpstruct node *name_node(struct node *node, char *name) 129204431Sraj{ 130204431Sraj assert(node->name == NULL); 131204431Sraj 132204431Sraj node->name = name; 133204431Sraj 134204431Sraj return node; 135204431Sraj} 136204431Sraj 137238742Simpstruct node *merge_nodes(struct node *old_node, struct node *new_node) 138238742Simp{ 139238742Simp struct property *new_prop, *old_prop; 140238742Simp struct node *new_child, *old_child; 141238742Simp struct label *l; 142238742Simp 143261215Simp old_node->deleted = 0; 144261215Simp 145238742Simp /* Add new node labels to old node */ 146261215Simp for_each_label_withdel(new_node->labels, l) 147238742Simp add_label(&old_node->labels, l->label); 148238742Simp 149238742Simp /* Move properties from the new node to the old node. If there 150238742Simp * is a collision, replace the old value with the new */ 151238742Simp while (new_node->proplist) { 152238742Simp /* Pop the property off the list */ 153238742Simp new_prop = new_node->proplist; 154238742Simp new_node->proplist = new_prop->next; 155238742Simp new_prop->next = NULL; 156238742Simp 157261215Simp if (new_prop->deleted) { 158261215Simp delete_property_by_name(old_node, new_prop->name); 159261215Simp free(new_prop); 160261215Simp continue; 161261215Simp } 162261215Simp 163238742Simp /* Look for a collision, set new value if there is */ 164261215Simp for_each_property_withdel(old_node, old_prop) { 165238742Simp if (streq(old_prop->name, new_prop->name)) { 166238742Simp /* Add new labels to old property */ 167261215Simp for_each_label_withdel(new_prop->labels, l) 168238742Simp add_label(&old_prop->labels, l->label); 169238742Simp 170238742Simp old_prop->val = new_prop->val; 171261215Simp old_prop->deleted = 0; 172238742Simp free(new_prop); 173238742Simp new_prop = NULL; 174238742Simp break; 175238742Simp } 176238742Simp } 177238742Simp 178238742Simp /* if no collision occurred, add property to the old node. */ 179238742Simp if (new_prop) 180238742Simp add_property(old_node, new_prop); 181238742Simp } 182238742Simp 183238742Simp /* Move the override child nodes into the primary node. If 184238742Simp * there is a collision, then merge the nodes. */ 185238742Simp while (new_node->children) { 186238742Simp /* Pop the child node off the list */ 187238742Simp new_child = new_node->children; 188238742Simp new_node->children = new_child->next_sibling; 189238742Simp new_child->parent = NULL; 190238742Simp new_child->next_sibling = NULL; 191238742Simp 192261215Simp if (new_child->deleted) { 193261215Simp delete_node_by_name(old_node, new_child->name); 194261215Simp free(new_child); 195261215Simp continue; 196261215Simp } 197261215Simp 198238742Simp /* Search for a collision. Merge if there is */ 199261215Simp for_each_child_withdel(old_node, old_child) { 200238742Simp if (streq(old_child->name, new_child->name)) { 201238742Simp merge_nodes(old_child, new_child); 202238742Simp new_child = NULL; 203238742Simp break; 204238742Simp } 205238742Simp } 206238742Simp 207318102Sgonzo /* if no collision occurred, add child to the old node. */ 208238742Simp if (new_child) 209238742Simp add_child(old_node, new_child); 210238742Simp } 211238742Simp 212238742Simp /* The new node contents are now merged into the old node. Free 213238742Simp * the new node. */ 214238742Simp free(new_node); 215238742Simp 216238742Simp return old_node; 217238742Simp} 218238742Simp 219204431Srajstruct node *chain_node(struct node *first, struct node *list) 220204431Sraj{ 221204431Sraj assert(first->next_sibling == NULL); 222204431Sraj 223204431Sraj first->next_sibling = list; 224204431Sraj return first; 225204431Sraj} 226204431Sraj 227204431Srajvoid add_property(struct node *node, struct property *prop) 228204431Sraj{ 229204431Sraj struct property **p; 230204431Sraj 231204431Sraj prop->next = NULL; 232204431Sraj 233204431Sraj p = &node->proplist; 234204431Sraj while (*p) 235204431Sraj p = &((*p)->next); 236204431Sraj 237204431Sraj *p = prop; 238204431Sraj} 239204431Sraj 240261215Simpvoid delete_property_by_name(struct node *node, char *name) 241261215Simp{ 242261215Simp struct property *prop = node->proplist; 243261215Simp 244261215Simp while (prop) { 245318102Sgonzo if (streq(prop->name, name)) { 246261215Simp delete_property(prop); 247261215Simp return; 248261215Simp } 249261215Simp prop = prop->next; 250261215Simp } 251261215Simp} 252261215Simp 253261215Simpvoid delete_property(struct property *prop) 254261215Simp{ 255261215Simp prop->deleted = 1; 256261215Simp delete_labels(&prop->labels); 257261215Simp} 258261215Simp 259204431Srajvoid add_child(struct node *parent, struct node *child) 260204431Sraj{ 261204431Sraj struct node **p; 262204431Sraj 263204431Sraj child->next_sibling = NULL; 264204431Sraj child->parent = parent; 265204431Sraj 266204431Sraj p = &parent->children; 267204431Sraj while (*p) 268204431Sraj p = &((*p)->next_sibling); 269204431Sraj 270204431Sraj *p = child; 271204431Sraj} 272204431Sraj 273261215Simpvoid delete_node_by_name(struct node *parent, char *name) 274261215Simp{ 275261215Simp struct node *node = parent->children; 276261215Simp 277261215Simp while (node) { 278318102Sgonzo if (streq(node->name, name)) { 279261215Simp delete_node(node); 280261215Simp return; 281261215Simp } 282261215Simp node = node->next_sibling; 283261215Simp } 284261215Simp} 285261215Simp 286261215Simpvoid delete_node(struct node *node) 287261215Simp{ 288261215Simp struct property *prop; 289261215Simp struct node *child; 290261215Simp 291261215Simp node->deleted = 1; 292261215Simp for_each_child(node, child) 293261215Simp delete_node(child); 294261215Simp for_each_property(node, prop) 295261215Simp delete_property(prop); 296261215Simp delete_labels(&node->labels); 297261215Simp} 298261215Simp 299318102Sgonzovoid append_to_property(struct node *node, 300318102Sgonzo char *name, const void *data, int len) 301318102Sgonzo{ 302318102Sgonzo struct data d; 303318102Sgonzo struct property *p; 304318102Sgonzo 305318102Sgonzo p = get_property(node, name); 306318102Sgonzo if (p) { 307318102Sgonzo d = data_append_data(p->val, data, len); 308318102Sgonzo p->val = d; 309318102Sgonzo } else { 310318102Sgonzo d = data_append_data(empty_data, data, len); 311318102Sgonzo p = build_property(name, d); 312318102Sgonzo add_property(node, p); 313318102Sgonzo } 314318102Sgonzo} 315318102Sgonzo 316238742Simpstruct reserve_info *build_reserve_entry(uint64_t address, uint64_t size) 317204431Sraj{ 318204431Sraj struct reserve_info *new = xmalloc(sizeof(*new)); 319204431Sraj 320238742Simp memset(new, 0, sizeof(*new)); 321238742Simp 322204431Sraj new->re.address = address; 323204431Sraj new->re.size = size; 324204431Sraj 325204431Sraj return new; 326204431Sraj} 327204431Sraj 328204431Srajstruct reserve_info *chain_reserve_entry(struct reserve_info *first, 329204431Sraj struct reserve_info *list) 330204431Sraj{ 331204431Sraj assert(first->next == NULL); 332204431Sraj 333204431Sraj first->next = list; 334204431Sraj return first; 335204431Sraj} 336204431Sraj 337204431Srajstruct reserve_info *add_reserve_entry(struct reserve_info *list, 338204431Sraj struct reserve_info *new) 339204431Sraj{ 340204431Sraj struct reserve_info *last; 341204431Sraj 342204431Sraj new->next = NULL; 343204431Sraj 344204431Sraj if (! list) 345204431Sraj return new; 346204431Sraj 347204431Sraj for (last = list; last->next; last = last->next) 348204431Sraj ; 349204431Sraj 350204431Sraj last->next = new; 351204431Sraj 352204431Sraj return list; 353204431Sraj} 354204431Sraj 355318102Sgonzostruct dt_info *build_dt_info(unsigned int dtsflags, 356318102Sgonzo struct reserve_info *reservelist, 357318102Sgonzo struct node *tree, uint32_t boot_cpuid_phys) 358204431Sraj{ 359318102Sgonzo struct dt_info *dti; 360204431Sraj 361318102Sgonzo dti = xmalloc(sizeof(*dti)); 362318102Sgonzo dti->dtsflags = dtsflags; 363318102Sgonzo dti->reservelist = reservelist; 364318102Sgonzo dti->dt = tree; 365318102Sgonzo dti->boot_cpuid_phys = boot_cpuid_phys; 366204431Sraj 367318102Sgonzo return dti; 368204431Sraj} 369204431Sraj 370204431Sraj/* 371204431Sraj * Tree accessor functions 372204431Sraj */ 373204431Sraj 374204431Srajconst char *get_unitname(struct node *node) 375204431Sraj{ 376204431Sraj if (node->name[node->basenamelen] == '\0') 377204431Sraj return ""; 378204431Sraj else 379204431Sraj return node->name + node->basenamelen + 1; 380204431Sraj} 381204431Sraj 382204431Srajstruct property *get_property(struct node *node, const char *propname) 383204431Sraj{ 384204431Sraj struct property *prop; 385204431Sraj 386204431Sraj for_each_property(node, prop) 387204431Sraj if (streq(prop->name, propname)) 388204431Sraj return prop; 389204431Sraj 390204431Sraj return NULL; 391204431Sraj} 392204431Sraj 393204431Srajcell_t propval_cell(struct property *prop) 394204431Sraj{ 395204431Sraj assert(prop->val.len == sizeof(cell_t)); 396204431Sraj return fdt32_to_cpu(*((cell_t *)prop->val.val)); 397204431Sraj} 398204431Sraj 399238742Simpstruct property *get_property_by_label(struct node *tree, const char *label, 400238742Simp struct node **node) 401238742Simp{ 402238742Simp struct property *prop; 403238742Simp struct node *c; 404238742Simp 405238742Simp *node = tree; 406238742Simp 407238742Simp for_each_property(tree, prop) { 408238742Simp struct label *l; 409238742Simp 410238742Simp for_each_label(prop->labels, l) 411238742Simp if (streq(l->label, label)) 412238742Simp return prop; 413238742Simp } 414238742Simp 415238742Simp for_each_child(tree, c) { 416238742Simp prop = get_property_by_label(c, label, node); 417238742Simp if (prop) 418238742Simp return prop; 419238742Simp } 420238742Simp 421238742Simp *node = NULL; 422238742Simp return NULL; 423238742Simp} 424238742Simp 425238742Simpstruct marker *get_marker_label(struct node *tree, const char *label, 426238742Simp struct node **node, struct property **prop) 427238742Simp{ 428238742Simp struct marker *m; 429238742Simp struct property *p; 430238742Simp struct node *c; 431238742Simp 432238742Simp *node = tree; 433238742Simp 434238742Simp for_each_property(tree, p) { 435238742Simp *prop = p; 436238742Simp m = p->val.markers; 437238742Simp for_each_marker_of_type(m, LABEL) 438238742Simp if (streq(m->ref, label)) 439238742Simp return m; 440238742Simp } 441238742Simp 442238742Simp for_each_child(tree, c) { 443238742Simp m = get_marker_label(c, label, node, prop); 444238742Simp if (m) 445238742Simp return m; 446238742Simp } 447238742Simp 448238742Simp *prop = NULL; 449238742Simp *node = NULL; 450238742Simp return NULL; 451238742Simp} 452238742Simp 453204431Srajstruct node *get_subnode(struct node *node, const char *nodename) 454204431Sraj{ 455204431Sraj struct node *child; 456204431Sraj 457204431Sraj for_each_child(node, child) 458204431Sraj if (streq(child->name, nodename)) 459204431Sraj return child; 460204431Sraj 461204431Sraj return NULL; 462204431Sraj} 463204431Sraj 464204431Srajstruct node *get_node_by_path(struct node *tree, const char *path) 465204431Sraj{ 466204431Sraj const char *p; 467204431Sraj struct node *child; 468204431Sraj 469261215Simp if (!path || ! (*path)) { 470261215Simp if (tree->deleted) 471261215Simp return NULL; 472204431Sraj return tree; 473261215Simp } 474204431Sraj 475204431Sraj while (path[0] == '/') 476204431Sraj path++; 477204431Sraj 478204431Sraj p = strchr(path, '/'); 479204431Sraj 480204431Sraj for_each_child(tree, child) { 481204431Sraj if (p && strneq(path, child->name, p-path)) 482204431Sraj return get_node_by_path(child, p+1); 483204431Sraj else if (!p && streq(path, child->name)) 484204431Sraj return child; 485204431Sraj } 486204431Sraj 487204431Sraj return NULL; 488204431Sraj} 489204431Sraj 490204431Srajstruct node *get_node_by_label(struct node *tree, const char *label) 491204431Sraj{ 492204431Sraj struct node *child, *node; 493238742Simp struct label *l; 494204431Sraj 495204431Sraj assert(label && (strlen(label) > 0)); 496204431Sraj 497238742Simp for_each_label(tree->labels, l) 498238742Simp if (streq(l->label, label)) 499238742Simp return tree; 500204431Sraj 501204431Sraj for_each_child(tree, child) { 502204431Sraj node = get_node_by_label(child, label); 503204431Sraj if (node) 504204431Sraj return node; 505204431Sraj } 506204431Sraj 507204431Sraj return NULL; 508204431Sraj} 509204431Sraj 510204431Srajstruct node *get_node_by_phandle(struct node *tree, cell_t phandle) 511204431Sraj{ 512204431Sraj struct node *child, *node; 513204431Sraj 514204431Sraj assert((phandle != 0) && (phandle != -1)); 515204431Sraj 516261215Simp if (tree->phandle == phandle) { 517261215Simp if (tree->deleted) 518261215Simp return NULL; 519204431Sraj return tree; 520261215Simp } 521204431Sraj 522204431Sraj for_each_child(tree, child) { 523204431Sraj node = get_node_by_phandle(child, phandle); 524204431Sraj if (node) 525204431Sraj return node; 526204431Sraj } 527204431Sraj 528204431Sraj return NULL; 529204431Sraj} 530204431Sraj 531204431Srajstruct node *get_node_by_ref(struct node *tree, const char *ref) 532204431Sraj{ 533318102Sgonzo if (streq(ref, "/")) 534318102Sgonzo return tree; 535318102Sgonzo else if (ref[0] == '/') 536204431Sraj return get_node_by_path(tree, ref); 537204431Sraj else 538204431Sraj return get_node_by_label(tree, ref); 539204431Sraj} 540204431Sraj 541204431Srajcell_t get_node_phandle(struct node *root, struct node *node) 542204431Sraj{ 543204431Sraj static cell_t phandle = 1; /* FIXME: ick, static local */ 544204431Sraj 545204431Sraj if ((node->phandle != 0) && (node->phandle != -1)) 546204431Sraj return node->phandle; 547204431Sraj 548204431Sraj while (get_node_by_phandle(root, phandle)) 549204431Sraj phandle++; 550204431Sraj 551204431Sraj node->phandle = phandle; 552204431Sraj 553204433Sraj if (!get_property(node, "linux,phandle") 554204433Sraj && (phandle_format & PHANDLE_LEGACY)) 555204433Sraj add_property(node, 556204433Sraj build_property("linux,phandle", 557238742Simp data_append_cell(empty_data, phandle))); 558204433Sraj 559204433Sraj if (!get_property(node, "phandle") 560204433Sraj && (phandle_format & PHANDLE_EPAPR)) 561204433Sraj add_property(node, 562204433Sraj build_property("phandle", 563238742Simp data_append_cell(empty_data, phandle))); 564204433Sraj 565204433Sraj /* If the node *does* have a phandle property, we must 566204433Sraj * be dealing with a self-referencing phandle, which will be 567204433Sraj * fixed up momentarily in the caller */ 568204433Sraj 569204431Sraj return node->phandle; 570204431Sraj} 571238742Simp 572238742Simpuint32_t guess_boot_cpuid(struct node *tree) 573238742Simp{ 574238742Simp struct node *cpus, *bootcpu; 575238742Simp struct property *reg; 576238742Simp 577238742Simp cpus = get_node_by_path(tree, "/cpus"); 578238742Simp if (!cpus) 579238742Simp return 0; 580238742Simp 581238742Simp 582238742Simp bootcpu = cpus->children; 583238742Simp if (!bootcpu) 584238742Simp return 0; 585238742Simp 586238742Simp reg = get_property(bootcpu, "reg"); 587238742Simp if (!reg || (reg->val.len != sizeof(uint32_t))) 588238742Simp return 0; 589238742Simp 590238742Simp /* FIXME: Sanity check node? */ 591238742Simp 592238742Simp return propval_cell(reg); 593238742Simp} 594238742Simp 595238742Simpstatic int cmp_reserve_info(const void *ax, const void *bx) 596238742Simp{ 597238742Simp const struct reserve_info *a, *b; 598238742Simp 599238742Simp a = *((const struct reserve_info * const *)ax); 600238742Simp b = *((const struct reserve_info * const *)bx); 601238742Simp 602238742Simp if (a->re.address < b->re.address) 603238742Simp return -1; 604238742Simp else if (a->re.address > b->re.address) 605238742Simp return 1; 606238742Simp else if (a->re.size < b->re.size) 607238742Simp return -1; 608238742Simp else if (a->re.size > b->re.size) 609238742Simp return 1; 610238742Simp else 611238742Simp return 0; 612238742Simp} 613238742Simp 614318102Sgonzostatic void sort_reserve_entries(struct dt_info *dti) 615238742Simp{ 616238742Simp struct reserve_info *ri, **tbl; 617238742Simp int n = 0, i = 0; 618238742Simp 619318102Sgonzo for (ri = dti->reservelist; 620238742Simp ri; 621238742Simp ri = ri->next) 622238742Simp n++; 623238742Simp 624238742Simp if (n == 0) 625238742Simp return; 626238742Simp 627238742Simp tbl = xmalloc(n * sizeof(*tbl)); 628238742Simp 629318102Sgonzo for (ri = dti->reservelist; 630238742Simp ri; 631238742Simp ri = ri->next) 632238742Simp tbl[i++] = ri; 633238742Simp 634238742Simp qsort(tbl, n, sizeof(*tbl), cmp_reserve_info); 635238742Simp 636318102Sgonzo dti->reservelist = tbl[0]; 637238742Simp for (i = 0; i < (n-1); i++) 638238742Simp tbl[i]->next = tbl[i+1]; 639238742Simp tbl[n-1]->next = NULL; 640238742Simp 641238742Simp free(tbl); 642238742Simp} 643238742Simp 644238742Simpstatic int cmp_prop(const void *ax, const void *bx) 645238742Simp{ 646238742Simp const struct property *a, *b; 647238742Simp 648238742Simp a = *((const struct property * const *)ax); 649238742Simp b = *((const struct property * const *)bx); 650238742Simp 651238742Simp return strcmp(a->name, b->name); 652238742Simp} 653238742Simp 654238742Simpstatic void sort_properties(struct node *node) 655238742Simp{ 656238742Simp int n = 0, i = 0; 657238742Simp struct property *prop, **tbl; 658238742Simp 659261215Simp for_each_property_withdel(node, prop) 660238742Simp n++; 661238742Simp 662238742Simp if (n == 0) 663238742Simp return; 664238742Simp 665238742Simp tbl = xmalloc(n * sizeof(*tbl)); 666238742Simp 667261215Simp for_each_property_withdel(node, prop) 668238742Simp tbl[i++] = prop; 669238742Simp 670238742Simp qsort(tbl, n, sizeof(*tbl), cmp_prop); 671238742Simp 672238742Simp node->proplist = tbl[0]; 673238742Simp for (i = 0; i < (n-1); i++) 674238742Simp tbl[i]->next = tbl[i+1]; 675238742Simp tbl[n-1]->next = NULL; 676238742Simp 677238742Simp free(tbl); 678238742Simp} 679238742Simp 680238742Simpstatic int cmp_subnode(const void *ax, const void *bx) 681238742Simp{ 682238742Simp const struct node *a, *b; 683238742Simp 684238742Simp a = *((const struct node * const *)ax); 685238742Simp b = *((const struct node * const *)bx); 686238742Simp 687238742Simp return strcmp(a->name, b->name); 688238742Simp} 689238742Simp 690238742Simpstatic void sort_subnodes(struct node *node) 691238742Simp{ 692238742Simp int n = 0, i = 0; 693238742Simp struct node *subnode, **tbl; 694238742Simp 695261215Simp for_each_child_withdel(node, subnode) 696238742Simp n++; 697238742Simp 698238742Simp if (n == 0) 699238742Simp return; 700238742Simp 701238742Simp tbl = xmalloc(n * sizeof(*tbl)); 702238742Simp 703261215Simp for_each_child_withdel(node, subnode) 704238742Simp tbl[i++] = subnode; 705238742Simp 706238742Simp qsort(tbl, n, sizeof(*tbl), cmp_subnode); 707238742Simp 708238742Simp node->children = tbl[0]; 709238742Simp for (i = 0; i < (n-1); i++) 710238742Simp tbl[i]->next_sibling = tbl[i+1]; 711238742Simp tbl[n-1]->next_sibling = NULL; 712238742Simp 713238742Simp free(tbl); 714238742Simp} 715238742Simp 716238742Simpstatic void sort_node(struct node *node) 717238742Simp{ 718238742Simp struct node *c; 719238742Simp 720238742Simp sort_properties(node); 721238742Simp sort_subnodes(node); 722261215Simp for_each_child_withdel(node, c) 723238742Simp sort_node(c); 724238742Simp} 725238742Simp 726318102Sgonzovoid sort_tree(struct dt_info *dti) 727238742Simp{ 728318102Sgonzo sort_reserve_entries(dti); 729318102Sgonzo sort_node(dti->dt); 730238742Simp} 731318102Sgonzo 732318102Sgonzo/* utility helper to avoid code duplication */ 733318102Sgonzostatic struct node *build_and_name_child_node(struct node *parent, char *name) 734318102Sgonzo{ 735318102Sgonzo struct node *node; 736318102Sgonzo 737318102Sgonzo node = build_node(NULL, NULL); 738318102Sgonzo name_node(node, xstrdup(name)); 739318102Sgonzo add_child(parent, node); 740318102Sgonzo 741318102Sgonzo return node; 742318102Sgonzo} 743318102Sgonzo 744318102Sgonzostatic struct node *build_root_node(struct node *dt, char *name) 745318102Sgonzo{ 746318102Sgonzo struct node *an; 747318102Sgonzo 748318102Sgonzo an = get_subnode(dt, name); 749318102Sgonzo if (!an) 750318102Sgonzo an = build_and_name_child_node(dt, name); 751318102Sgonzo 752318102Sgonzo if (!an) 753318102Sgonzo die("Could not build root node /%s\n", name); 754318102Sgonzo 755318102Sgonzo return an; 756318102Sgonzo} 757318102Sgonzo 758318102Sgonzostatic bool any_label_tree(struct dt_info *dti, struct node *node) 759318102Sgonzo{ 760318102Sgonzo struct node *c; 761318102Sgonzo 762318102Sgonzo if (node->labels) 763318102Sgonzo return true; 764318102Sgonzo 765318102Sgonzo for_each_child(node, c) 766318102Sgonzo if (any_label_tree(dti, c)) 767318102Sgonzo return true; 768318102Sgonzo 769318102Sgonzo return false; 770318102Sgonzo} 771318102Sgonzo 772318102Sgonzostatic void generate_label_tree_internal(struct dt_info *dti, 773318102Sgonzo struct node *an, struct node *node, 774318102Sgonzo bool allocph) 775318102Sgonzo{ 776318102Sgonzo struct node *dt = dti->dt; 777318102Sgonzo struct node *c; 778318102Sgonzo struct property *p; 779318102Sgonzo struct label *l; 780318102Sgonzo 781318102Sgonzo /* if there are labels */ 782318102Sgonzo if (node->labels) { 783318102Sgonzo 784318102Sgonzo /* now add the label in the node */ 785318102Sgonzo for_each_label(node->labels, l) { 786318102Sgonzo 787318102Sgonzo /* check whether the label already exists */ 788318102Sgonzo p = get_property(an, l->label); 789318102Sgonzo if (p) { 790318102Sgonzo fprintf(stderr, "WARNING: label %s already" 791318102Sgonzo " exists in /%s", l->label, 792318102Sgonzo an->name); 793318102Sgonzo continue; 794318102Sgonzo } 795318102Sgonzo 796318102Sgonzo /* insert it */ 797318102Sgonzo p = build_property(l->label, 798318102Sgonzo data_copy_mem(node->fullpath, 799318102Sgonzo strlen(node->fullpath) + 1)); 800318102Sgonzo add_property(an, p); 801318102Sgonzo } 802318102Sgonzo 803318102Sgonzo /* force allocation of a phandle for this node */ 804318102Sgonzo if (allocph) 805318102Sgonzo (void)get_node_phandle(dt, node); 806318102Sgonzo } 807318102Sgonzo 808318102Sgonzo for_each_child(node, c) 809318102Sgonzo generate_label_tree_internal(dti, an, c, allocph); 810318102Sgonzo} 811318102Sgonzo 812318102Sgonzostatic bool any_fixup_tree(struct dt_info *dti, struct node *node) 813318102Sgonzo{ 814318102Sgonzo struct node *c; 815318102Sgonzo struct property *prop; 816318102Sgonzo struct marker *m; 817318102Sgonzo 818318102Sgonzo for_each_property(node, prop) { 819318102Sgonzo m = prop->val.markers; 820318102Sgonzo for_each_marker_of_type(m, REF_PHANDLE) { 821318102Sgonzo if (!get_node_by_ref(dti->dt, m->ref)) 822318102Sgonzo return true; 823318102Sgonzo } 824318102Sgonzo } 825318102Sgonzo 826318102Sgonzo for_each_child(node, c) { 827318102Sgonzo if (any_fixup_tree(dti, c)) 828318102Sgonzo return true; 829318102Sgonzo } 830318102Sgonzo 831318102Sgonzo return false; 832318102Sgonzo} 833318102Sgonzo 834318102Sgonzostatic void add_fixup_entry(struct dt_info *dti, struct node *fn, 835318102Sgonzo struct node *node, struct property *prop, 836318102Sgonzo struct marker *m) 837318102Sgonzo{ 838318102Sgonzo char *entry; 839318102Sgonzo 840318102Sgonzo /* m->ref can only be a REF_PHANDLE, but check anyway */ 841318102Sgonzo assert(m->type == REF_PHANDLE); 842318102Sgonzo 843318102Sgonzo /* there shouldn't be any ':' in the arguments */ 844318102Sgonzo if (strchr(node->fullpath, ':') || strchr(prop->name, ':')) 845318102Sgonzo die("arguments should not contain ':'\n"); 846318102Sgonzo 847318102Sgonzo xasprintf(&entry, "%s:%s:%u", 848318102Sgonzo node->fullpath, prop->name, m->offset); 849318102Sgonzo append_to_property(fn, m->ref, entry, strlen(entry) + 1); 850318102Sgonzo 851318102Sgonzo free(entry); 852318102Sgonzo} 853318102Sgonzo 854318102Sgonzostatic void generate_fixups_tree_internal(struct dt_info *dti, 855318102Sgonzo struct node *fn, 856318102Sgonzo struct node *node) 857318102Sgonzo{ 858318102Sgonzo struct node *dt = dti->dt; 859318102Sgonzo struct node *c; 860318102Sgonzo struct property *prop; 861318102Sgonzo struct marker *m; 862318102Sgonzo struct node *refnode; 863318102Sgonzo 864318102Sgonzo for_each_property(node, prop) { 865318102Sgonzo m = prop->val.markers; 866318102Sgonzo for_each_marker_of_type(m, REF_PHANDLE) { 867318102Sgonzo refnode = get_node_by_ref(dt, m->ref); 868318102Sgonzo if (!refnode) 869318102Sgonzo add_fixup_entry(dti, fn, node, prop, m); 870318102Sgonzo } 871318102Sgonzo } 872318102Sgonzo 873318102Sgonzo for_each_child(node, c) 874318102Sgonzo generate_fixups_tree_internal(dti, fn, c); 875318102Sgonzo} 876318102Sgonzo 877318102Sgonzostatic bool any_local_fixup_tree(struct dt_info *dti, struct node *node) 878318102Sgonzo{ 879318102Sgonzo struct node *c; 880318102Sgonzo struct property *prop; 881318102Sgonzo struct marker *m; 882318102Sgonzo 883318102Sgonzo for_each_property(node, prop) { 884318102Sgonzo m = prop->val.markers; 885318102Sgonzo for_each_marker_of_type(m, REF_PHANDLE) { 886318102Sgonzo if (get_node_by_ref(dti->dt, m->ref)) 887318102Sgonzo return true; 888318102Sgonzo } 889318102Sgonzo } 890318102Sgonzo 891318102Sgonzo for_each_child(node, c) { 892318102Sgonzo if (any_local_fixup_tree(dti, c)) 893318102Sgonzo return true; 894318102Sgonzo } 895318102Sgonzo 896318102Sgonzo return false; 897318102Sgonzo} 898318102Sgonzo 899318102Sgonzostatic void add_local_fixup_entry(struct dt_info *dti, 900318102Sgonzo struct node *lfn, struct node *node, 901318102Sgonzo struct property *prop, struct marker *m, 902318102Sgonzo struct node *refnode) 903318102Sgonzo{ 904318102Sgonzo struct node *wn, *nwn; /* local fixup node, walk node, new */ 905318102Sgonzo uint32_t value_32; 906318102Sgonzo char **compp; 907318102Sgonzo int i, depth; 908318102Sgonzo 909318102Sgonzo /* walk back retreiving depth */ 910318102Sgonzo depth = 0; 911318102Sgonzo for (wn = node; wn; wn = wn->parent) 912318102Sgonzo depth++; 913318102Sgonzo 914318102Sgonzo /* allocate name array */ 915318102Sgonzo compp = xmalloc(sizeof(*compp) * depth); 916318102Sgonzo 917318102Sgonzo /* store names in the array */ 918318102Sgonzo for (wn = node, i = depth - 1; wn; wn = wn->parent, i--) 919318102Sgonzo compp[i] = wn->name; 920318102Sgonzo 921318102Sgonzo /* walk the path components creating nodes if they don't exist */ 922318102Sgonzo for (wn = lfn, i = 1; i < depth; i++, wn = nwn) { 923318102Sgonzo /* if no node exists, create it */ 924318102Sgonzo nwn = get_subnode(wn, compp[i]); 925318102Sgonzo if (!nwn) 926318102Sgonzo nwn = build_and_name_child_node(wn, compp[i]); 927318102Sgonzo } 928318102Sgonzo 929318102Sgonzo free(compp); 930318102Sgonzo 931318102Sgonzo value_32 = cpu_to_fdt32(m->offset); 932318102Sgonzo append_to_property(wn, prop->name, &value_32, sizeof(value_32)); 933318102Sgonzo} 934318102Sgonzo 935318102Sgonzostatic void generate_local_fixups_tree_internal(struct dt_info *dti, 936318102Sgonzo struct node *lfn, 937318102Sgonzo struct node *node) 938318102Sgonzo{ 939318102Sgonzo struct node *dt = dti->dt; 940318102Sgonzo struct node *c; 941318102Sgonzo struct property *prop; 942318102Sgonzo struct marker *m; 943318102Sgonzo struct node *refnode; 944318102Sgonzo 945318102Sgonzo for_each_property(node, prop) { 946318102Sgonzo m = prop->val.markers; 947318102Sgonzo for_each_marker_of_type(m, REF_PHANDLE) { 948318102Sgonzo refnode = get_node_by_ref(dt, m->ref); 949318102Sgonzo if (refnode) 950318102Sgonzo add_local_fixup_entry(dti, lfn, node, prop, m, refnode); 951318102Sgonzo } 952318102Sgonzo } 953318102Sgonzo 954318102Sgonzo for_each_child(node, c) 955318102Sgonzo generate_local_fixups_tree_internal(dti, lfn, c); 956318102Sgonzo} 957318102Sgonzo 958318102Sgonzovoid generate_label_tree(struct dt_info *dti, char *name, bool allocph) 959318102Sgonzo{ 960318102Sgonzo if (!any_label_tree(dti, dti->dt)) 961318102Sgonzo return; 962318102Sgonzo generate_label_tree_internal(dti, build_root_node(dti->dt, name), 963318102Sgonzo dti->dt, allocph); 964318102Sgonzo} 965318102Sgonzo 966318102Sgonzovoid generate_fixups_tree(struct dt_info *dti, char *name) 967318102Sgonzo{ 968318102Sgonzo if (!any_fixup_tree(dti, dti->dt)) 969318102Sgonzo return; 970318102Sgonzo generate_fixups_tree_internal(dti, build_root_node(dti->dt, name), 971318102Sgonzo dti->dt); 972318102Sgonzo} 973318102Sgonzo 974318102Sgonzovoid generate_local_fixups_tree(struct dt_info *dti, char *name) 975318102Sgonzo{ 976318102Sgonzo if (!any_local_fixup_tree(dti, dti->dt)) 977318102Sgonzo return; 978318102Sgonzo generate_local_fixups_tree_internal(dti, build_root_node(dti->dt, name), 979318102Sgonzo dti->dt); 980318102Sgonzo} 981