usr.bin/dtc/fdt.cc

   1 /*-
   2  * Copyright (c) 2013 David Chisnall
   3  * All rights reserved.
   4  *
   5  * This software was developed by SRI International and the University of
   6  * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237)
   7  * ("CTSRD"), as part of the DARPA CRASH research programme.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  19  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  21  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  22  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  23  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  24  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  25  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  26  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  27  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  28  * SUCH DAMAGE.
  29  *
  30  * $FreeBSD$
  31  */
  32
  33 #include "fdt.hh"
  34
  35 #include <algorithm>
  36 #include <ctype.h>
  37 #include <fcntl.h>
  38 #include <inttypes.h>
  39 #include <libgen.h>
  40 #include <stdio.h>
  41 #include <stdlib.h>
  42 #include <unistd.h>
  43 #include "dtb.hh"
  44
  45 namespace dtc
  46 {
  47
  48 namespace fdt
  49 {
  50
  51 uint32_t
  52 property_value::get_as_uint32()
  53 {
  54         if (byte_data.size() != 4)
  55         {
  56                 return 0;
  57         }
  58         uint32_t v = 0;
  59         v &= byte_data[0] << 24;
  60         v &= byte_data[1] << 16;
  61         v &= byte_data[2] << 8;
  62         v &= byte_data[3] << 0;
  63         return v;
  64 }
  65
  66 void
  67 property_value::push_to_buffer(byte_buffer &buffer)
  68 {
  69         if (!byte_data.empty())
  70         {
  71                 buffer.insert(buffer.end(), byte_data.begin(), byte_data.end());
  72         }
  73         else
  74         {
  75                 string_data.push_to_buffer(buffer, true);
  76                 // Trailing nul
  77                 buffer.push_back(0);
  78         }
  79 }
  80
  81 void
  82 property_value::write_dts(FILE *file)
  83 {
  84         resolve_type();
  85         switch (type)
  86         {
  87                 default:
  88                         assert(0 && "Invalid type");
  89                 case STRING:
  90                 case STRING_LIST:
  91                 case CROSS_REFERENCE:
  92                         write_as_string(file);
  93                         break;
  94                 case PHANDLE:
  95                         write_as_cells(file);
  96                         break;
  97                 case BINARY:
  98                         if (byte_data.size() % 4 == 0)
  99                         {
 100                                 write_as_cells(file);
 101                                 break;
 102                         }
 103                         write_as_bytes(file);
 104                         break;
 105         }
 106 }
 107
 108 void
 109 property_value::resolve_type()
 110 {
 111         if (type != UNKNOWN)
 112         {
 113                 return;
 114         }
 115         if (byte_data.empty())
 116         {
 117                 type = STRING;
 118                 return;
 119         }
 120         if (byte_data.back() == 0)
 121         {
 122                 bool is_all_printable = true;
 123                 int nuls = 0;
 124                 int bytes = 0;
 125                 for (byte_buffer::iterator i=byte_data.begin(), e=byte_data.end()-1; i<e ; i++)
 126                 {
 127                         bytes++;
 128                         is_all_printable &= (*i == '\0') || isprint(*i);
 129                         if (*i == '\0')
 130                         {
 131                                 nuls++;
 132                         }
 133                         if (!is_all_printable)
 134                         {
 135                                 break;
 136                         }
 137                 }
 138                 if (is_all_printable && (bytes > nuls))
 139                 {
 140                         type = STRING;
 141                         if (nuls > 0)
 142                         {
 143                                 type = STRING_LIST;
 144                         }
 145                         return;
 146                 }
 147         }
 148         type = BINARY;
 149 }
 150
 151 void
 152 property_value::write_as_string(FILE *file)
 153 {
 154         putc('"', file);
 155         if (byte_data.empty())
 156         {
 157                 string_data.print(file);
 158         }
 159         else
 160         {
 161                 for (byte_buffer::iterator i=byte_data.begin(), e=byte_data.end()-1; i!=e ; ++i)
 162                 {
 163                         // FIXME Escape tabs, newlines, and so on.
 164                         if (*i == '\0')
 165                         {
 166                                 fputs("\", \"", file);
 167                                 continue;
 168                         }
 169                         putc(*i, file);
 170                 }
 171         }
 172         putc('"', file);
 173 }
 174
 175 void
 176 property_value::write_as_cells(FILE *file)
 177 {
 178         putc('<', file);
 179         assert((byte_data.size() % 4) == 0);
 180         for (byte_buffer::iterator i=byte_data.begin(), e=byte_data.end(); i!=e ; ++i)
 181         {
 182                 uint32_t v = 0;
 183                 v = (v << 8) | *i;
 184                 ++i;
 185                 v = (v << 8) | *i;
 186                 ++i;
 187                 v = (v << 8) | *i;
 188                 ++i;
 189                 v = (v << 8) | *i;
 190                 fprintf(file, "0x%" PRIx32, v);
 191                 if (i+1 != e)
 192                 {
 193                         putc(' ', file);
 194                 }
 195         }
 196         putc('>', file);
 197 }
 198
 199 void
 200 property_value::write_as_bytes(FILE *file)
 201 {
 202         putc('[', file);
 203         for (byte_buffer::iterator i=byte_data.begin(), e=byte_data.end(); i!=e ; i++)
 204         {
 205                 fprintf(file, "%hhx", *i);
 206                 if (i+1 != e)
 207                 {
 208                         putc(' ', file);
 209                 }
 210         }
 211         putc(']', file);
 212 }
 213
 214 void
 215 property::parse_string(input_buffer &input)
 216 {
 217         property_value v;
 218         assert(input[0] == '"');
 219         ++input;
 220         const char *start = (const char*)input;
 221         int length = 0;
 222         while (char c = input[0])
 223         {
 224                 if (c == '"' && input[-1] != '\\')
 225                 {
 226                         input.consume('"');
 227                         break;
 228                 }
 229                 ++input;
 230                 ++length;
 231         }
 232         v.string_data = string(start, length);
 233         values.push_back(v);
 234 }
 235
 236 void
 237 property::parse_cells(input_buffer &input)
 238 {
 239         assert(input[0] == '<');
 240         ++input;
 241         property_value v;
 242         input.next_token();
 243         while (!input.consume('>'))
 244         {
 245                 input.next_token();
 246                 // If this is a phandle then we need to get the name of the
 247                 // referenced node
 248                 if (input.consume('&'))
 249                 {
 250                         input.next_token();
 251                         // FIXME: We should support full paths here, but we
 252                         // don't.
 253                         string referenced = string::parse_node_name(input);
 254                         if (referenced.empty())
 255                         {
 256                                 input.parse_error("Expected node name");
 257                                 valid = false;
 258                                 return;
 259                         }
 260                         input.next_token();
 261                         // If we already have some bytes, make the phandle a
 262                         // separate component.
 263                         if (!v.byte_data.empty())
 264                         {
 265                                 values.push_back(v);
 266                                 v = property_value();
 267                         }
 268                         v.string_data = referenced;
 269                         v.type = property_value::PHANDLE;
 270                         values.push_back(v);
 271                         v = property_value();
 272                 }
 273                 else
 274                 {
 275                         //FIXME: We should support labels in the middle
 276                         //of these, but we don't.
 277                         long long val;
 278                         if (!input.consume_integer(val))
 279                         {
 280                                 input.parse_error("Expected numbers in array of cells");
 281                                 valid = false;
 282                                 return;
 283                         }
 284                         push_big_endian(v.byte_data, (uint32_t)val);
 285                         input.next_token();
 286                 }
 287         }
 288         // Don't store an empty string value here.
 289         if (v.byte_data.size() > 0)
 290         {
 291                 values.push_back(v);
 292         }
 293 }
 294
 295 void
 296 property::parse_bytes(input_buffer &input)
 297 {
 298         assert(input[0] == '[');
 299         ++input;
 300         property_value v;
 301         input.next_token();
 302         while (!input.consume(']'))
 303         {
 304                 {
 305                         //FIXME: We should support
 306                         //labels in the middle of
 307                         //these, but we don't.
 308                         uint8_t val;
 309                         if (!input.consume_hex_byte(val))
 310                         {
 311                                 input.parse_error("Expected hex bytes in array of bytes");
 312                                 valid = false;
 313                                 return;
 314                         }
 315                         v.byte_data.push_back(val);
 316                         input.next_token();
 317                 }
 318         }
 319         values.push_back(v);
 320 }
 321
 322 void
 323 property::parse_reference(input_buffer &input)
 324 {
 325         assert(input[0] == '&');
 326         ++input;
 327         input.next_token();
 328         property_value v;
 329         v.string_data = string::parse_node_name(input);
 330         if (v.string_data.empty())
 331         {
 332                 input.parse_error("Expected node name");
 333                 valid = false;
 334                 return;
 335         }
 336         v.type = property_value::CROSS_REFERENCE;
 337         values.push_back(v);
 338 }
 339
 340 property::property(input_buffer &structs, input_buffer &strings)
 341 {
 342         uint32_t name_offset;
 343         uint32_t length;
 344         valid = structs.consume_binary(length) &&
 345                 structs.consume_binary(name_offset);
 346         if (!valid)
 347         {
 348                 fprintf(stderr, "Failed to read property\n");
 349                 return;
 350         }
 351         // Find the name
 352         input_buffer name_buffer = strings.buffer_from_offset(name_offset);
 353         if (name_buffer.empty())
 354         {
 355                 fprintf(stderr, "Property name offset %" PRIu32
 356                         " is past the end of the strings table\n",
 357                         name_offset);
 358                 valid = false;
 359                 return;
 360         }
 361         key = string(name_buffer);
 362         // Read the value
 363         uint8_t byte;
 364         property_value v;
 365         for (uint32_t i=0 ; i<length ; i++)
 366         {
 367                 if (!(valid = structs.consume_binary(byte)))
 368                 {
 369                         fprintf(stderr, "Failed to read property value\n");
 370                         return;
 371                 }
 372                 v.byte_data.push_back(byte);
 373         }
 374         values.push_back(v);
 375 }
 376
 377 property::property(input_buffer &input, string k, string l) : key(k), label(l),
 378         valid(true)
 379 {
 380         do {
 381                 input.next_token();
 382                 switch (input[0])
 383                 {
 384                         default:
 385                                 input.parse_error("Invalid property value.");
 386                                 valid = false;
 387                                 return;
 388                         case '"':
 389                                 parse_string(input);
 390                                 break;
 391                         case '<':
 392                                 parse_cells(input);
 393                                 break;
 394                         case '[':
 395                                 parse_bytes(input);
 396                                 break;
 397                         case '&':
 398                                 parse_reference(input);
 399                                 break;
 400                         case ';':
 401                         {
 402                                 break;
 403                         }
 404                 }
 405                 input.next_token();
 406         } while (input.consume(','));
 407         if (!input.consume(';'))
 408         {
 409                 input.parse_error("Expected ; at end of property");
 410                 valid = false;
 411         }
 412 }
 413
 414 property*
 415 property::parse_dtb(input_buffer &structs, input_buffer &strings)
 416 {
 417         property *p = new property(structs, strings);
 418         if (!p->valid)
 419         {
 420                 delete p;
 421                 p = 0;
 422         }
 423         return p;
 424 }
 425
 426 property*
 427 property::parse(input_buffer &input, string key, string label)
 428 {
 429         property *p = new property(input, key, label);
 430         if (!p->valid)
 431         {
 432                 delete p;
 433                 p = 0;
 434         }
 435         return p;
 436 }
 437
 438 void
 439 property::write(dtb::output_writer &writer, dtb::string_table &strings)
 440 {
 441         writer.write_token(dtb::FDT_PROP);
 442         byte_buffer value_buffer;
 443         for (value_iterator i=begin(), e=end() ; i!=e ; ++i)
 444         {
 445                 i->push_to_buffer(value_buffer);
 446         }
 447         writer.write_data((uint32_t)value_buffer.size());
 448         writer.write_comment(key);
 449         writer.write_data(strings.add_string(key));
 450         writer.write_data(value_buffer);
 451 }
 452
 453 void
 454 property::write_dts(FILE *file, int indent)
 455 {
 456         for (int i=0 ; i<indent ; i++)
 457         {
 458                 putc('\t', file);
 459         }
 460         if (label != string())
 461         {
 462                 label.print(file);
 463                 fputs(": ", file);
 464         }
 465         if (key != string())
 466         {
 467                 key.print(file);
 468         }
 469         if (!values.empty())
 470         {
 471                 fputs(" = ", file);
 472                 for (value_iterator i=begin(), e=end() ; i!=e ; ++i)
 473                 {
 474                         i->write_dts(file);
 475                         if (i+1 != e)
 476                         {
 477                                 putc(',', file);
 478                                 putc(' ', file);
 479                         }
 480                 }
 481         }
 482         fputs(";\n", file);
 483 }
 484
 485 string
 486 node::parse_name(input_buffer &input, bool &is_property, const char *error)
 487 {
 488         if (!valid)
 489         {
 490                 return string();
 491         }
 492         input.next_token();
 493         if (is_property)
 494         {
 495                 return string::parse_property_name(input);
 496         }
 497         string n = string::parse_node_or_property_name(input, is_property);
 498         if (n.empty())
 499         {
 500                 if (n.empty())
 501                 {
 502                         input.parse_error(error);
 503                         valid = false;
 504                 }
 505         }
 506         return n;
 507 }
 508
 509 node::node(input_buffer &structs, input_buffer &strings) : valid(true)
 510 {
 511         const char *name_start = (const char*)structs;
 512         int name_length = 0;
 513         while (structs[0] != '\0' && structs[0] != '@')
 514         {
 515                 name_length++;
 516                 ++structs;
 517         }
 518         name = string(name_start, name_length);
 519         if (structs[0] == '@')
 520         {
 521                 ++structs;
 522                 name_start = (const char*)structs;
 523                 name_length = 0;
 524                 while (structs[0] != '\0')
 525                 {
 526                         name_length++;
 527                         ++structs;
 528                 }
 529                 unit_address = string(name_start, name_length);
 530         }
 531         ++structs;
 532         uint32_t token;
 533         while (structs.consume_binary(token))
 534         {
 535                 switch (token)
 536                 {
 537                         default:
 538                                 fprintf(stderr, "Unexpected token 0x%" PRIx32
 539                                         " while parsing node.\n", token);
 540                                 valid = false;
 541                                 return;
 542                         // Child node, parse it.
 543                         case dtb::FDT_BEGIN_NODE:
 544                         {
 545                                 node *child = node::parse_dtb(structs, strings);
 546                                 if (child == 0)
 547                                 {
 548                                         valid = false;
 549                                         return;
 550                                 }
 551                                 children.push_back(child);
 552                                 break;
 553                         }
 554                         // End of this node, no errors.
 555                         case dtb::FDT_END_NODE:
 556                                 return;
 557                         // Property, parse it.
 558                         case dtb::FDT_PROP:
 559                         {
 560                                 property *prop = property::parse_dtb(structs, strings);
 561                                 if (prop == 0)
 562                                 {
 563                                         valid = false;
 564                                         return;
 565                                 }
 566                                 properties.push_back(prop);
 567                                 break;
 568                         }
 569                                 break;
 570                         // End of structs table.  Should appear after
 571                         // the end of the last node.
 572                         case dtb::FDT_END:
 573                                 fprintf(stderr, "Unexpected FDT_END token while parsing node.\n");
 574                                 valid = false;
 575                                 return;
 576                         // NOPs are padding.  Ignore them.
 577                         case dtb::FDT_NOP:
 578                                 break;
 579                 }
 580         }
 581         fprintf(stderr, "Failed to read token from structs table while parsing node.\n");
 582         valid = false;
 583         return;
 584 }
 585
 586 node::node(input_buffer &input, string n, string l, string a) :
 587         label(l), name(n), unit_address(a), valid(true)
 588 {
 589         if (!input.consume('{'))
 590         {
 591                 input.parse_error("Expected { to start new device tree node.\n");
 592         }
 593         input.next_token();
 594         while (valid && !input.consume('}'))
 595         {
 596                 // flag set if we find any characters that are only in
 597                 // the property name character set, not the node
 598                 bool is_property = false;
 599                 string child_name, child_label, child_address;
 600                 child_name = parse_name(input, is_property,
 601                                 "Expected property or node name");
 602                 if (input.consume(':'))
 603                 {
 604                         // Node labels can contain any characters?  The
 605                         // spec doesn't say, so we guess so...
 606                         is_property = false;
 607                         child_label = child_name;
 608                         child_name = parse_name(input, is_property, "Expected property or node name");
 609                 }
 610                 if (input.consume('@'))
 611                 {
 612                         child_address = parse_name(input, is_property, "Expected unit address");
 613                 }
 614                 if (!valid)
 615                 {
 616                         return;
 617                 }
 618                 input.next_token();
 619                 // If we're parsing a property, then we must actually do that.
 620                 if (input.consume('='))
 621                 {
 622                         property *p= property::parse(input, child_name,
 623                                         child_label);
 624                         if (p == 0)
 625                         {
 626                                 valid = false;
 627                         }
 628                         else
 629                         {
 630                                 properties.push_back(p);
 631                         }
 632                 }
 633                 else if (!is_property && input[0] == ('{'))
 634                 {
 635                         node *child = node::parse(input, child_name,
 636                                         child_label, child_address);
 637                         if (child)
 638                         {
 639                                 children.push_back(child);
 640                         }
 641                         else
 642                         {
 643                                 valid = false;
 644                         }
 645                 }
 646                 else if (input.consume(';'))
 647                 {
 648                         properties.push_back(new property(child_name, child_label));
 649                 }
 650                 else
 651                 {
 652                         input.parse_error("Error parsing property.");
 653                         valid = false;
 654                 }
 655                 input.next_token();
 656         }
 657         input.consume(';');
 658 }
 659
 660 bool
 661 node::cmp_properties(property *p1, property *p2)
 662 {
 663         return p1->get_key() < p2->get_key();
 664 }
 665
 666 bool
 667 node::cmp_children(node *c1, node *c2)
 668 {
 669         if (c1->name == c2->name)
 670         {
 671                 return c1->unit_address < c2->unit_address;
 672         }
 673         return c1->name < c2->name;
 674 }
 675
 676 void
 677 node::sort()
 678 {
 679         std::sort(property_begin(), property_end(), cmp_properties);
 680         std::sort(child_begin(), child_end(), cmp_children);
 681         for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i)
 682         {
 683                 (*i)->sort();
 684         }
 685 }
 686
 687 node*
 688 node::parse(input_buffer &input, string name, string label, string address)
 689 {
 690         node *n = new node(input, name, label, address);
 691         if (!n->valid)
 692         {
 693                 delete n;
 694                 n = 0;
 695         }
 696         return n;
 697 }
 698
 699 node*
 700 node::parse_dtb(input_buffer &structs, input_buffer &strings)
 701 {
 702         node *n = new node(structs, strings);
 703         if (!n->valid)
 704         {
 705                 delete n;
 706                 n = 0;
 707         }
 708         return n;
 709 }
 710
 711 node::~node()
 712 {
 713         while (!children.empty())
 714         {
 715                 delete children.back();
 716                 children.pop_back();
 717         }
 718         while (!properties.empty())
 719         {
 720                 delete properties.back();
 721                 properties.pop_back();
 722         }
 723 }
 724
 725 property*
 726 node::get_property(string key)
 727 {
 728         for (property_iterator i=property_begin(), e=property_end() ; i!=e ; ++i)
 729         {
 730                 if ((*i)->get_key() == key)
 731                 {
 732                         return *i;
 733                 }
 734         }
 735         return 0;
 736 }
 737
 738 void
 739 node::merge_node(node *other)
 740 {
 741         if (!other->label.empty())
 742         {
 743                 label = other->label;
 744         }
 745         // Note: this is an O(n*m) operation.  It might be sensible to
 746         // optimise this if we find that there are nodes with very
 747         // large numbers of properties, but for typical usage the
 748         // entire vector will fit (easily) into cache, so iterating
 749         // over it repeatedly isn't that expensive.
 750         while (!other->properties.empty())
 751         {
 752                 property *p = other->properties.front();
 753                 for (property_iterator i=property_begin(), e=property_end() ; i!=e ; ++i)
 754                 {
 755                         if ((*i)->get_key() == p->get_key())
 756                         {
 757                                 delete *i;
 758                                 properties.erase(i);
 759                                 break;
 760                         }
 761                 }
 762                 add_property(p);
 763                 other->properties.erase(other->properties.begin());
 764         }
 765         while (!other->children.empty())
 766         {
 767                 node *c = other->children.front();
 768                 bool found = false;
 769                 for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i)
 770                 {
 771                         if ((*i)->name == c->name && (*i)->unit_address == c->unit_address)
 772                         {
 773                                 (*i)->merge_node(c);
 774                                 delete c;
 775                                 found = true;
 776                                 break;
 777                         }
 778                 }
 779                 if (!found)
 780                 {
 781                         children.push_back(c);
 782                 }
 783                 other->children.erase(other->children.begin());
 784         }
 785 }
 786
 787 void
 788 node::write(dtb::output_writer &writer, dtb::string_table &strings)
 789 {
 790         writer.write_token(dtb::FDT_BEGIN_NODE);
 791         byte_buffer name_buffer;
 792         name.push_to_buffer(name_buffer);
 793         if (unit_address != string())
 794         {
 795                 name_buffer.push_back('@');
 796                 unit_address.push_to_buffer(name_buffer);
 797         }
 798         writer.write_comment(name);
 799         writer.write_data(name_buffer);
 800         writer.write_data((uint8_t)0);
 801         for (property_iterator i=property_begin(), e=property_end() ; i!=e ; ++i)
 802         {
 803                 (*i)->write(writer, strings);
 804         }
 805         for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i)
 806         {
 807                 (*i)->write(writer, strings);
 808         }
 809         writer.write_token(dtb::FDT_END_NODE);
 810 }
 811
 812 void
 813 node::write_dts(FILE *file, int indent)
 814 {
 815         for (int i=0 ; i<indent ; i++)
 816         {
 817                 putc('\t', file);
 818         }
 819         if (label != string())
 820         {
 821                 label.print(file);
 822                 fputs(": ", file);
 823         }
 824         if (name != string())
 825         {
 826                 name.print(file);
 827         }
 828         if (unit_address != string())
 829         {
 830                 putc('@', file);
 831                 unit_address.print(file);
 832         }
 833         fputs(" {\n\n", file);
 834         for (property_iterator i=property_begin(), e=property_end() ; i!=e ; ++i)
 835         {
 836                 (*i)->write_dts(file, indent+1);
 837         }
 838         for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i)
 839         {
 840                 (*i)->write_dts(file, indent+1);
 841         }
 842         for (int i=0 ; i<indent ; i++)
 843         {
 844                 putc('\t', file);
 845         }
 846         fputs("};\n", file);
 847 }
 848
 849 void
 850 device_tree::collect_names_recursive(node* n, node_path &path)
 851 {
 852         string name = n->label;
 853         path.push_back(std::make_pair(n->name, n->unit_address));
 854         if (name != string())
 855         {
 856                 if (node_names.find(name) == node_names.end())
 857                 {
 858                         node_names.insert(std::make_pair(name, n));
 859                         node_paths.insert(std::make_pair(name, path));
 860                 }
 861                 else
 862                 {
 863                         node_names[name] = (node*)-1;
 864                         std::map<string, node_path>::iterator i = node_paths.find(name);
 865                         if (i != node_paths.end())
 866                         {
 867                                 node_paths.erase(name);
 868                         }
 869                         fprintf(stderr, "Label not unique: ");
 870                         name.dump();
 871                         fprintf(stderr, ".  References to this label will not be resolved.");
 872                 }
 873         }
 874         for (node::child_iterator i=n->child_begin(), e=n->child_end() ; i!=e ; ++i)
 875         {
 876                 collect_names_recursive(*i, path);
 877         }
 878         path.pop_back();
 879         // Now we collect the phandles and properties that reference
 880         // other nodes.
 881         for (node::property_iterator i=n->property_begin(), e=n->property_end() ; i!=e ; ++i)
 882         {
 883                 for (property::value_iterator p=(*i)->begin(),pe=(*i)->end() ; p!=pe ; ++p)
 884                 {
 885                         if (p->is_phandle())
 886                         {
 887                                 phandles.push_back(&*p);
 888                         }
 889                         if (p->is_cross_reference())
 890                         {
 891                                 cross_references.push_back(&*p);
 892                         }
 893                 }
 894                 if ((*i)->get_key() == string("phandle") ||
 895                     (*i)->get_key() == string("linux,phandle"))
 896                 {
 897                         if ((*i)->begin()->byte_data.size() != 4)
 898                         {
 899                                 fprintf(stderr, "Invalid phandle value for node ");
 900                                 n->name.dump();
 901                                 fprintf(stderr, ".  Should be a 4-byte value.\n");
 902                                 valid = false;
 903                         }
 904                         else
 905                         {
 906                                 uint32_t phandle = (*i)->begin()->get_as_uint32();
 907                                 used_phandles.insert(std::make_pair(phandle, n));
 908                         }
 909                 }
 910         }
 911 }
 912
 913 void
 914 device_tree::collect_names()
 915 {
 916         node_path p;
 917         collect_names_recursive(root, p);
 918 }
 919
 920 void
 921 device_tree::resolve_cross_references()
 922 {
 923         for (std::vector<property_value*>::iterator i=cross_references.begin(), e=cross_references.end() ; i!=e ; ++i)
 924         {
 925                 property_value* pv = *i;
 926                 node_path path = node_paths[pv->string_data];
 927                 // Skip the first name in the path.  It's always "", and implicitly /
 928                 for (node_path::iterator p=path.begin()+1, pe=path.end() ; p!=pe ; ++p)
 929                 {
 930                         pv->byte_data.push_back('/');
 931                         p->first.push_to_buffer(pv->byte_data);
 932                         if (!(p->second.empty()))
 933                         {
 934                                 pv->byte_data.push_back('@');
 935                                 p->second.push_to_buffer(pv->byte_data);
 936                         }
 937                 }
 938                 pv->byte_data.push_back(0);
 939         }
 940         uint32_t phandle = 1;
 941         for (std::vector<property_value*>::iterator i=phandles.begin(), e=phandles.end() ; i!=e ; ++i)
 942         {
 943                 string target_name = (*i)->string_data;
 944                 node *target = node_names[target_name];
 945                 if (target == 0)
 946                 {
 947                         fprintf(stderr, "Failed to find node with label:");
 948                         target_name.dump();
 949                         fprintf(stderr, "\n");
 950                         valid = 0;
 951                         return;
 952                 }
 953                 // If there is an existing phandle, use it
 954                 property *p = target->get_property("phandle");
 955                 if (p == 0)
 956                 {
 957                         p = target->get_property("linux,phandle");
 958                 }
 959                 if (p == 0)
 960                 {
 961                         // Otherwise insert a new phandle node
 962                         property_value v;
 963                         while (used_phandles.find(phandle) != used_phandles.end())
 964                         {
 965                                 // Note that we only don't need to
 966                                 // store this phandle in the set,
 967                                 // because we are monotonically
 968                                 // increasing the value of phandle and
 969                                 // so will only ever revisit this value
 970                                 // if we have used 2^32 phandles, at
 971                                 // which point our blob won't fit in
 972                                 // any 32-bit system and we've done
 973                                 // something badly wrong elsewhere
 974                                 // already.
 975                                 phandle++;
 976                         }
 977                         push_big_endian(v.byte_data, phandle++);
 978                         if (phandle_node_name == BOTH || phandle_node_name == LINUX)
 979                         {
 980                                 p = new property(string("linux,phandle"));
 981                                 p->add_value(v);
 982                                 target->add_property(p);
 983                         }
 984                         if (phandle_node_name == BOTH || phandle_node_name == EPAPR)
 985                         {
 986                                 p = new property(string("phandle"));
 987                                 p->add_value(v);
 988                                 target->add_property(p);
 989                         }
 990                 }
 991                 p->begin()->push_to_buffer((*i)->byte_data);
 992                 assert((*i)->byte_data.size() == 4);
 993         }
 994 }
 995
 996 void
 997 device_tree::parse_roots(input_buffer &input, std::vector<node*> &roots)
 998 {
 999         input.next_token();
1000         while (valid && input.consume('/'))
1001         {
1002                 input.next_token();
1003                 node *n = node::parse(input, string("", 1));
1004                 if (n)
1005                 {
1006                         roots.push_back(n);
1007                 }
1008                 else
1009                 {
1010                         valid = false;
1011                 }
1012         }
1013 }
1014
1015 input_buffer*
1016 device_tree::buffer_for_file(const char *path)
1017 {
1018         if (string(path) == string("-"))
1019         {
1020                 input_buffer *b = new stream_input_buffer();
1021                 buffers.push_back(b);
1022                 return b;
1023         }
1024         int source = open(path, O_RDONLY);
1025         if (source == -1)
1026         {
1027                 fprintf(stderr, "Unable to open file %s\n", path);
1028                 return 0;
1029         }
1030         input_buffer *b = new mmap_input_buffer(source);
1031         // Keep the buffer that owns the memory around for the lifetime
1032         // of this FDT.  Ones simply referring to it may have shorter
1033         // lifetimes.
1034         buffers.push_back(b);
1035         close(source);
1036         return b;
1037 }
1038
1039 template<class writer> void
1040 device_tree::write(int fd)
1041 {
1042         dtb::string_table st;
1043         dtb::header head;
1044         writer head_writer;
1045         writer reservation_writer;
1046         writer struct_writer;
1047         writer strings_writer;
1048
1049         // Build the reservation table
1050         reservation_writer.write_comment(string("Memory reservations"));
1051         reservation_writer.write_label(string("dt_reserve_map"));
1052         for (std::vector<reservation>::iterator i=reservations.begin(),
1053              e=reservations.end() ; i!=e ; ++i)
1054         {
1055                 reservation_writer.write_comment(string("Reservation start"));
1056                 reservation_writer.write_data(i->first);
1057                 reservation_writer.write_comment(string("Reservation length"));
1058                 reservation_writer.write_data(i->first);
1059         }
1060         // Write n spare reserve map entries, plus the trailing 0.
1061         for (uint32_t i=0 ; i<=spare_reserve_map_entries ; i++)
1062         {
1063                 reservation_writer.write_data((uint64_t)0);
1064                 reservation_writer.write_data((uint64_t)0);
1065         }
1066
1067
1068         struct_writer.write_comment(string("Device tree"));
1069         struct_writer.write_label(string("dt_struct_start"));
1070         root->write(struct_writer, st);
1071         struct_writer.write_token(dtb::FDT_END);
1072         struct_writer.write_label(string("dt_struct_end"));
1073
1074         st.write(strings_writer);
1075         // Find the strings size before we stick padding on the end.
1076         // Note: We should possibly use a new writer for the padding.
1077         head.size_dt_strings = strings_writer.size();
1078
1079         // Stick the padding in the strings writer, but after the
1080         // marker indicating that it's the end.
1081         // Note: We probably should add a padding call to the writer so
1082         // that the asm back end can write padding directives instead
1083         // of a load of 0 bytes.
1084         for (uint32_t i=0 ; i<blob_padding ; i++)
1085         {
1086                 strings_writer.write_data((uint8_t)0);
1087         }
1088         head.totalsize = sizeof(head) + strings_writer.size() +
1089                 struct_writer.size() + reservation_writer.size();
1090         while (head.totalsize < minimum_blob_size)
1091         {
1092                 head.totalsize++;
1093                 strings_writer.write_data((uint8_t)0);
1094         }
1095         head.off_dt_struct = sizeof(head) + reservation_writer.size();;
1096         head.off_dt_strings = head.off_dt_struct + struct_writer.size();
1097         head.off_mem_rsvmap = sizeof(head);
1098         head.boot_cpuid_phys = boot_cpu;
1099         head.size_dt_struct = struct_writer.size();
1100         head.write(head_writer);
1101
1102         head_writer.write_to_file(fd);
1103         reservation_writer.write_to_file(fd);
1104         struct_writer.write_to_file(fd);
1105         strings_writer.write_label(string("dt_blob_end"));
1106         strings_writer.write_to_file(fd);
1107 }
1108
1109 node*
1110 device_tree::referenced_node(property_value &v)
1111 {
1112         if (v.is_phandle())
1113         {
1114                 return node_names[v.string_data];
1115         }
1116         if (v.is_binary())
1117         {
1118                 return used_phandles[v.get_as_uint32()];
1119         }
1120         return 0;
1121 }
1122
1123 void
1124 device_tree::write_binary(int fd)
1125 {
1126         write<dtb::binary_writer>(fd);
1127 }
1128
1129 void
1130 device_tree::write_asm(int fd)
1131 {
1132         write<dtb::asm_writer>(fd);
1133 }
1134
1135 void
1136 device_tree::write_dts(int fd)
1137 {
1138         FILE *file = fdopen(fd, "w");
1139         fputs("/dtc-v1/;\n\n", file);
1140
1141         if (!reservations.empty())
1142         {
1143                 const char msg[] = "/memreserve/";
1144                 fwrite(msg, sizeof(msg), 1, file);
1145                 for (std::vector<reservation>::iterator i=reservations.begin(),
1146                      e=reservations.end() ; i!=e ; ++i)
1147                 {
1148                         fprintf(stderr, " %" PRIx64 " %" PRIx64, i->first, i->second);
1149                 }
1150                 fputs(";\n\n", file);
1151         }
1152         putc('/', file);
1153         putc(' ', file);
1154         root->write_dts(file, 0);
1155         fclose(file);
1156 }
1157
1158 void
1159 device_tree::parse_dtb(const char *fn, FILE *depfile)
1160 {
1161         input_buffer *in = buffer_for_file(fn);
1162         if (in == 0)
1163         {
1164                 valid = false;
1165                 return;
1166         }
1167         input_buffer &input = *in;
1168         dtb::header h;
1169         valid = h.read_dtb(input);
1170         boot_cpu = h.boot_cpuid_phys;
1171         if (h.last_comp_version > 17)
1172         {
1173                 fprintf(stderr, "Don't know how to read this version of the device tree blob");
1174                 valid = false;
1175         }
1176         if (!valid)
1177         {
1178                 return;
1179         }
1180         input_buffer reservation_map =
1181                 input.buffer_from_offset(h.off_mem_rsvmap, 0);
1182         uint64_t start, length;
1183         do
1184         {
1185                 if (!(reservation_map.consume_binary(start) &&
1186                       reservation_map.consume_binary(length)))
1187                 {
1188                         fprintf(stderr, "Failed to read memory reservation table\n");
1189                         valid = false;
1190                         return;
1191                 }
1192         } while (!((start == 0) && (length == 0)));
1193         input_buffer struct_table =
1194                 input.buffer_from_offset(h.off_dt_struct, h.size_dt_struct);
1195         input_buffer strings_table =
1196                 input.buffer_from_offset(h.off_dt_strings, h.size_dt_strings);
1197         uint32_t token;
1198         if (!(struct_table.consume_binary(token) &&
1199                 (token == dtb::FDT_BEGIN_NODE)))
1200         {
1201                 fprintf(stderr, "Expected FDT_BEGIN_NODE token.\n");
1202                 valid = false;
1203                 return;
1204         }
1205         root = node::parse_dtb(struct_table, strings_table);
1206         if (!(struct_table.consume_binary(token) && (token == dtb::FDT_END)))
1207         {
1208                 fprintf(stderr, "Expected FDT_END token after parsing root node.\n");
1209                 valid = false;
1210                 return;
1211         }
1212         valid = (root != 0);
1213 }
1214
1215 void
1216 device_tree::parse_dts(const char *fn, FILE *depfile)
1217 {
1218         input_buffer *in = buffer_for_file(fn);
1219         if (in == 0)
1220         {
1221                 valid = false;
1222                 return;
1223         }
1224         std::vector<node*> roots;
1225         input_buffer &input = *in;
1226         input.next_token();
1227         bool read_header = false;
1228         // Read the header
1229         if (input.consume("/dts-v1/;"))
1230         {
1231                 read_header = true;
1232         }
1233         input.next_token();
1234         while(input.consume("/include/"))
1235         {
1236                 input.next_token();
1237                 if (!input.consume('"'))
1238                 {
1239                         input.parse_error("Expected quoted filename");
1240                         valid = false;
1241                         return;
1242                 }
1243                 int length = 0;
1244                 while (input[length] != '"') length++;
1245
1246                 const char *file = (const char*)input;
1247                 const char *dir = dirname(fn);
1248                 int dir_length = strlen(dir);
1249                 char *include_file = (char*)malloc(strlen(dir) + length + 2);
1250                 memcpy(include_file, dir, dir_length);
1251                 include_file[dir_length] = '/';
1252                 memcpy(include_file+dir_length+1, file, length);
1253                 include_file[dir_length+length+1] = 0;
1254                 input_buffer *include_buffer = buffer_for_file(include_file);
1255
1256                 if (include_buffer == 0)
1257                 {
1258                         for (std::vector<const char*>::iterator i=include_paths.begin(), e=include_paths.end() ; e!=i ; ++i)
1259                         {
1260                                 free(include_file);
1261                                 dir = *i;
1262                                 dir_length = strlen(dir);
1263                                 include_file = (char*)malloc(strlen(dir) +
1264                                                 length + 2);
1265                                 memcpy(include_file, dir, dir_length);
1266                                 include_file[dir_length] = '/';
1267                                 memcpy(include_file+dir_length+1, file, length);
1268                                 include_file[dir_length+length+1] = 0;
1269                                 include_buffer = buffer_for_file(include_file);
1270                                 if (include_buffer != 0)
1271                                 {
1272                                         break;
1273                                 }
1274                         }
1275                 }
1276                 if (depfile != 0)
1277                 {
1278                         putc(' ', depfile);
1279                         fputs(include_file, depfile);
1280                 }
1281                 if (include_buffer == 0)
1282                 {
1283                         valid = false;
1284                         return;
1285                 }
1286                 input_buffer &include = *include_buffer;
1287                 input.consume(include_file+dir_length+1);
1288                 input.consume('"');
1289                 free((void*)include_file);
1290
1291                 if (!read_header)
1292                 {
1293                         include.next_token();
1294                         read_header = include.consume("/dts-v1/;");
1295                 }
1296                 parse_roots(include, roots);
1297         }
1298         input.next_token();
1299         if (!read_header)
1300         {
1301                 input.parse_error("Expected /dts-v1/; version string");
1302         }
1303         // Read any memory reservations
1304         while(input.consume("/memreserve/"))
1305         {
1306                 long long start, len;
1307                 input.next_token();
1308                 // Read the start and length.
1309                 if (!(input.consume_integer(start) &&
1310                     (input.next_token(),
1311                     input.consume_integer(len))))
1312                 {
1313                         input.parse_error("Expected /dts-v1/; version string");
1314                 }
1315                 input.next_token();
1316                 input.consume(';');
1317                 reservations.push_back(reservation(start, len));
1318         }
1319         parse_roots(input, roots);
1320         switch (roots.size())
1321         {
1322                 case 0:
1323                         valid = false;
1324                         input.parse_error("Failed to find root node /.");
1325                         return;
1326                 case 1:
1327                         root = roots[0];
1328                         break;
1329                 default:
1330                 {
1331                         root = roots[0];
1332                         for (std::vector<node*>::iterator i=roots.begin()+1,
1333                              e=roots.end() ; i!=e ; ++i)
1334                         {
1335                                 root->merge_node(*i);
1336                                 delete *i;
1337                         }
1338                         roots.resize(1);
1339                 }
1340         }
1341         collect_names();
1342         resolve_cross_references();
1343 }
1344
1345 device_tree::~device_tree()
1346 {
1347         if (root != 0)
1348         {
1349                 delete root;
1350         }
1351         while (!buffers.empty())
1352         {
1353                 delete buffers.back();
1354                 buffers.pop_back();
1355         }
1356 }
1357
1358 } // namespace fdt
1359
1360 } // namespace dtc
1361