linux/scripts/dtc/livetree.c
<<
>>
Prefs
   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
  27void 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
  42struct 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
  54struct 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
  62struct 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
  77struct 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
  94struct 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
 103struct 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
 170struct 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
 178void 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
 191void 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
 205struct 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
 217struct 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
 226struct 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
 244struct 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
 261const 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
 269struct 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
 280cell_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
 286struct 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
 312struct 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
 340struct 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
 351struct 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
 374struct 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
 394struct 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
 412struct 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
 420cell_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
 451uint32_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
 474static 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
 493static 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
 523static 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
 533static 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
 559static 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
 569static 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
 595static 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
 605void sort_tree(struct boot_info *bi)
 606{
 607        sort_reserve_entries(bi);
 608        sort_node(bi->dt);
 609}
 610
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.