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 #define __STDC_LIMIT_MACROS 1
  34
  35 #include "fdt.hh"
  36 #include "dtb.hh"
  37
  38 #include <algorithm>
  39 #include <sstream>
  40
  41 #include <ctype.h>
  42 #include <fcntl.h>
  43 #include <inttypes.h>
  44 #include <libgen.h>
  45 #include <stdio.h>
  46 #include <stdlib.h>
  47 #include <unistd.h>
  48 #include <sys/types.h>
  49 #include <sys/stat.h>
  50 #include <errno.h>
  51
  52 using std::string;
  53
  54 namespace dtc
  55 {
  56
  57 namespace fdt
  58 {
  59
  60 uint32_t
  61 property_value::get_as_uint32()
  62 {
  63         if (byte_data.size() != 4)
  64         {
  65                 return 0;
  66         }
  67         uint32_t v = 0;
  68         v &= byte_data[0] << 24;
  69         v &= byte_data[1] << 16;
  70         v &= byte_data[2] << 8;
  71         v &= byte_data[3] << 0;
  72         return v;
  73 }
  74
  75 void
  76 property_value::push_to_buffer(byte_buffer &buffer)
  77 {
  78         if (!byte_data.empty())
  79         {
  80                 buffer.insert(buffer.end(), byte_data.begin(), byte_data.end());
  81         }
  82         else
  83         {
  84                 push_string(buffer, string_data, true);
  85                 // Trailing nul
  86                 buffer.push_back(0);
  87         }
  88 }
  89
  90 void
  91 property_value::write_dts(FILE *file)
  92 {
  93         resolve_type();
  94         switch (type)
  95         {
  96                 default:
  97                         assert(0 && "Invalid type");
  98                 case STRING:
  99                 case STRING_LIST:
 100                 case CROSS_REFERENCE:
 101                         write_as_string(file);
 102                         break;
 103                 case PHANDLE:
 104                         write_as_cells(file);
 105                         break;
 106                 case BINARY:
 107                         if (byte_data.size() % 4 == 0)
 108                         {
 109                                 write_as_cells(file);
 110                                 break;
 111                         }
 112                         write_as_bytes(file);
 113                         break;
 114         }
 115 }
 116
 117 void
 118 property_value::resolve_type()
 119 {
 120         if (type != UNKNOWN)
 121         {
 122                 return;
 123         }
 124         if (byte_data.empty())
 125         {
 126                 type = STRING;
 127                 return;
 128         }
 129         if (byte_data.back() == 0)
 130         {
 131                 bool is_all_printable = true;
 132                 int nuls = 0;
 133                 int bytes = 0;
 134                 bool lastWasNull = false;
 135                 for (auto i : byte_data)
 136                 {
 137                         bytes++;
 138                         is_all_printable &= (i == '\0') || isprint(i);
 139                         if (i == '\0')
 140                         {
 141                                 // If there are two nulls in a row, then we're probably binary.
 142                                 if (lastWasNull)
 143                                 {
 144                                         type = BINARY;
 145                                         return;
 146                                 }
 147                                 nuls++;
 148                                 lastWasNull = true;
 149                         }
 150                         else
 151                         {
 152                                 lastWasNull = false;
 153                         }
 154                         if (!is_all_printable)
 155                         {
 156                                 break;
 157                         }
 158                 }
 159                 if ((is_all_printable && (bytes > nuls)) || bytes == 0)
 160                 {
 161                         type = STRING;
 162                         if (nuls > 1)
 163                         {
 164                                 type = STRING_LIST;
 165                         }
 166                         return;
 167                 }
 168         }
 169         type = BINARY;
 170 }
 171
 172 size_t
 173 property_value::size()
 174 {
 175         if (!byte_data.empty())
 176         {
 177                 return byte_data.size();
 178         }
 179         return string_data.size() + 1;
 180 }
 181
 182 void
 183 property_value::write_as_string(FILE *file)
 184 {
 185         putc('"', file);
 186         if (byte_data.empty())
 187         {
 188                 fputs(string_data.c_str(), file);
 189         }
 190         else
 191         {
 192                 bool hasNull = (byte_data.back() == '\0');
 193                 // Remove trailing null bytes from the string before printing as dts.
 194                 if (hasNull)
 195                 {
 196                         byte_data.pop_back();
 197                 }
 198                 for (auto i : byte_data)
 199                 {
 200                         // FIXME Escape tabs, newlines, and so on.
 201                         if (i == '\0')
 202                         {
 203                                 fputs("\", \"", file);
 204                                 continue;
 205                         }
 206                         putc(i, file);
 207                 }
 208                 if (hasNull)
 209                 {
 210                         byte_data.push_back('\0');
 211                 }
 212         }
 213         putc('"', file);
 214 }
 215
 216 void
 217 property_value::write_as_cells(FILE *file)
 218 {
 219         putc('<', file);
 220         assert((byte_data.size() % 4) == 0);
 221         for (auto i=byte_data.begin(), e=byte_data.end(); i!=e ; ++i)
 222         {
 223                 uint32_t v = 0;
 224                 v = (v << 8) | *i;
 225                 ++i;
 226                 v = (v << 8) | *i;
 227                 ++i;
 228                 v = (v << 8) | *i;
 229                 ++i;
 230                 v = (v << 8) | *i;
 231                 fprintf(file, "0x%" PRIx32, v);
 232                 if (i+1 != e)
 233                 {
 234                         putc(' ', file);
 235                 }
 236         }
 237         putc('>', file);
 238 }
 239
 240 void
 241 property_value::write_as_bytes(FILE *file)
 242 {
 243         putc('[', file);
 244         for (auto i=byte_data.begin(), e=byte_data.end(); i!=e ; i++)
 245         {
 246                 fprintf(file, "%02hhx", *i);
 247                 if (i+1 != e)
 248                 {
 249                         putc(' ', file);
 250                 }
 251         }
 252         putc(']', file);
 253 }
 254
 255 void
 256 property::parse_string(text_input_buffer &input)
 257 {
 258         property_value v;
 259         assert(*input == '"');
 260         ++input;
 261         std::vector<char> bytes;
 262         bool isEscaped = false;
 263         while (char c = *input)
 264         {
 265                 if (c == '"' && !isEscaped)
 266                 {
 267                         input.consume('"');
 268                         break;
 269                 }
 270                 isEscaped = (c == '\\');
 271                 bytes.push_back(c);
 272                 ++input;
 273         }
 274         v.string_data = string(bytes.begin(), bytes.end());
 275         values.push_back(v);
 276 }
 277
 278 void
 279 property::parse_cells(text_input_buffer &input, int cell_size)
 280 {
 281         assert(*input == '<');
 282         ++input;
 283         property_value v;
 284         input.next_token();
 285         while (!input.consume('>'))
 286         {
 287                 input.next_token();
 288                 // If this is a phandle then we need to get the name of the
 289                 // referenced node
 290                 if (input.consume('&'))
 291                 {
 292                         if (cell_size != 32)
 293                         {
 294                                 input.parse_error("reference only permitted in 32-bit arrays");
 295                                 valid = false;
 296                                 return;
 297                         }
 298                         input.next_token();
 299                         string referenced;
 300                         if (!input.consume('{'))
 301                         {
 302                                 referenced = input.parse_node_name();
 303                         }
 304                         else
 305                         {
 306                                 referenced = input.parse_to('}');
 307                                 input.consume('}');
 308                         }
 309                         if (referenced.empty())
 310                         {
 311                                 input.parse_error("Expected node name");
 312                                 valid = false;
 313                                 return;
 314                         }
 315                         input.next_token();
 316                         // If we already have some bytes, make the phandle a
 317                         // separate component.
 318                         if (!v.byte_data.empty())
 319                         {
 320                                 values.push_back(v);
 321                                 v = property_value();
 322                         }
 323                         v.string_data = referenced;
 324                         v.type = property_value::PHANDLE;
 325                         values.push_back(v);
 326                         v = property_value();
 327                 }
 328                 else
 329                 {
 330                         //FIXME: We should support labels in the middle
 331                         //of these, but we don't.
 332                         unsigned long long val;
 333                         if (!input.consume_integer_expression(val))
 334                         {
 335                                 input.parse_error("Expected numbers in array of cells");
 336                                 valid = false;
 337                                 return;
 338                         }
 339                         switch (cell_size)
 340                         {
 341                                 case 8:
 342                                         v.byte_data.push_back(val);
 343                                         break;
 344                                 case 16:
 345                                         push_big_endian(v.byte_data, (uint16_t)val);
 346                                         break;
 347                                 case 32:
 348                                         push_big_endian(v.byte_data, (uint32_t)val);
 349                                         break;
 350                                 case 64:
 351                                         push_big_endian(v.byte_data, (uint64_t)val);
 352                                         break;
 353                                 default:
 354                                         assert(0 && "Invalid cell size!");
 355                         }
 356                         input.next_token();
 357                 }
 358         }
 359         // Don't store an empty string value here.
 360         if (v.byte_data.size() > 0)
 361         {
 362                 values.push_back(v);
 363         }
 364 }
 365
 366 void
 367 property::parse_bytes(text_input_buffer &input)
 368 {
 369         assert(*input == '[');
 370         ++input;
 371         property_value v;
 372         input.next_token();
 373         while (!input.consume(']'))
 374         {
 375                 {
 376                         //FIXME: We should support
 377                         //labels in the middle of
 378                         //these, but we don't.
 379                         uint8_t val;
 380                         if (!input.consume_hex_byte(val))
 381                         {
 382                                 input.parse_error("Expected hex bytes in array of bytes");
 383                                 valid = false;
 384                                 return;
 385                         }
 386                         v.byte_data.push_back(val);
 387                         input.next_token();
 388                 }
 389         }
 390         values.push_back(v);
 391 }
 392
 393 void
 394 property::parse_reference(text_input_buffer &input)
 395 {
 396         assert(*input == '&');
 397         ++input;
 398         input.next_token();
 399         property_value v;
 400         v.string_data = input.parse_node_name();
 401         if (v.string_data.empty())
 402         {
 403                 input.parse_error("Expected node name");
 404                 valid = false;
 405                 return;
 406         }
 407         v.type = property_value::CROSS_REFERENCE;
 408         values.push_back(v);
 409 }
 410
 411 property::property(input_buffer &structs, input_buffer &strings)
 412 {
 413         uint32_t name_offset;
 414         uint32_t length;
 415         valid = structs.consume_binary(length) &&
 416                 structs.consume_binary(name_offset);
 417         if (!valid)
 418         {
 419                 fprintf(stderr, "Failed to read property\n");
 420                 return;
 421         }
 422         // Find the name
 423         input_buffer name_buffer = strings.buffer_from_offset(name_offset);
 424         if (name_buffer.finished())
 425         {
 426                 fprintf(stderr, "Property name offset %" PRIu32
 427                         " is past the end of the strings table\n",
 428                         name_offset);
 429                 valid = false;
 430                 return;
 431         }
 432         key = name_buffer.parse_to(0);
 433
 434         // If we're empty, do not push anything as value.
 435         if (!length)
 436                 return;
 437
 438         // Read the value
 439         uint8_t byte;
 440         property_value v;
 441         for (uint32_t i=0 ; i<length ; i++)
 442         {
 443                 if (!(valid = structs.consume_binary(byte)))
 444                 {
 445                         fprintf(stderr, "Failed to read property value\n");
 446                         return;
 447                 }
 448                 v.byte_data.push_back(byte);
 449         }
 450         values.push_back(v);
 451 }
 452
 453 void property::parse_define(text_input_buffer &input, define_map *defines)
 454 {
 455         input.consume('$');
 456         if (!defines)
 457         {
 458                 input.parse_error("No predefined properties to match name\n");
 459                 valid = false;
 460                 return;
 461         }
 462         string name = input.parse_property_name();
 463         define_map::iterator found;
 464         if ((name == string()) ||
 465             ((found = defines->find(name)) == defines->end()))
 466         {
 467                 input.parse_error("Undefined property name\n");
 468                 valid = false;
 469                 return;
 470         }
 471         values.push_back((*found).second->values[0]);
 472 }
 473
 474 property::property(text_input_buffer &input,
 475                    string &&k,
 476                    string_set &&l,
 477                    bool semicolonTerminated,
 478                    define_map *defines) : key(k), labels(l), valid(true)
 479 {
 480         do {
 481                 input.next_token();
 482                 switch (*input)
 483                 {
 484                         case '$':
 485                         {
 486                                 parse_define(input, defines);
 487                                 if (valid)
 488                                 {
 489                                         break;
 490                                 }
 491                         }
 492                         default:
 493                                 input.parse_error("Invalid property value.");
 494                                 valid = false;
 495                                 return;
 496                         case '/':
 497                         {
 498                                 unsigned long long bits = 0;
 499                                 valid = input.consume("/bits/");
 500                                 input.next_token();
 501                                 valid &= input.consume_integer(bits);
 502                                 if ((bits != 8) &&
 503                                     (bits != 16) &&
 504                                     (bits != 32) &&
 505                                     (bits != 64)) {
 506                                         input.parse_error("Invalid size for elements");
 507                                         valid = false;
 508                                 }
 509                                 if (!valid) return;
 510                                 input.next_token();
 511                                 if (*input != '<')
 512                                 {
 513                                         input.parse_error("/bits/ directive is only valid on arrays");
 514                                         valid = false;
 515                                         return;
 516                                 }
 517                                 parse_cells(input, bits);
 518                                 break;
 519                         }
 520                         case '"':
 521                                 parse_string(input);
 522                                 break;
 523                         case '<':
 524                                 parse_cells(input, 32);
 525                                 break;
 526                         case '[':
 527                                 parse_bytes(input);
 528                                 break;
 529                         case '&':
 530                                 parse_reference(input);
 531                                 break;
 532                         case ';':
 533                         {
 534                                 break;
 535                         }
 536                 }
 537                 input.next_token();
 538         } while (input.consume(','));
 539         if (semicolonTerminated && !input.consume(';'))
 540         {
 541                 input.parse_error("Expected ; at end of property");
 542                 valid = false;
 543         }
 544 }
 545
 546 property_ptr
 547 property::parse_dtb(input_buffer &structs, input_buffer &strings)
 548 {
 549         property_ptr p(new property(structs, strings));
 550         if (!p->valid)
 551         {
 552                 p = nullptr;
 553         }
 554         return p;
 555 }
 556
 557 property_ptr
 558 property::parse(text_input_buffer &input, string &&key, string_set &&label,
 559                 bool semicolonTerminated, define_map *defines)
 560 {
 561         property_ptr p(new property(input,
 562                                     std::move(key),
 563                                     std::move(label),
 564                                     semicolonTerminated,
 565                                     defines));
 566         if (!p->valid)
 567         {
 568                 p = nullptr;
 569         }
 570         return p;
 571 }
 572
 573 void
 574 property::write(dtb::output_writer &writer, dtb::string_table &strings)
 575 {
 576         writer.write_token(dtb::FDT_PROP);
 577         byte_buffer value_buffer;
 578         for (value_iterator i=begin(), e=end() ; i!=e ; ++i)
 579         {
 580                 i->push_to_buffer(value_buffer);
 581         }
 582         writer.write_data((uint32_t)value_buffer.size());
 583         writer.write_comment(key);
 584         writer.write_data(strings.add_string(key));
 585         writer.write_data(value_buffer);
 586 }
 587
 588 bool
 589 property_value::try_to_merge(property_value &other)
 590 {
 591         resolve_type();
 592         switch (type)
 593         {
 594                 case UNKNOWN:
 595                         __builtin_unreachable();
 596                         assert(0);
 597                         return false;
 598                 case EMPTY:
 599                         *this = other;
 600                 case STRING:
 601                 case STRING_LIST:
 602                 case CROSS_REFERENCE:
 603                         return false;
 604                 case PHANDLE:
 605                 case BINARY:
 606                         if (other.type == PHANDLE || other.type == BINARY)
 607                         {
 608                                 type = BINARY;
 609                                 byte_data.insert(byte_data.end(), other.byte_data.begin(),
 610                                                  other.byte_data.end());
 611                                 return true;
 612                         }
 613         }
 614         return false;
 615 }
 616
 617 void
 618 property::write_dts(FILE *file, int indent)
 619 {
 620         for (int i=0 ; i<indent ; i++)
 621         {
 622                 putc('\t', file);
 623         }
 624 #ifdef PRINT_LABELS
 625         for (auto &l : labels)
 626         {
 627                 fputs(l.c_str(), file);
 628                 fputs(": ", file);
 629         }
 630 #endif
 631         if (key != string())
 632         {
 633                 fputs(key.c_str(), file);
 634         }
 635         if (!values.empty())
 636         {
 637                 std::vector<property_value> *vals = &values;
 638                 std::vector<property_value> v;
 639                 // If we've got multiple values then try to merge them all together.
 640                 if (values.size() > 1)
 641                 {
 642                         vals = &v;
 643                         v.push_back(values.front());
 644                         for (auto i=(++begin()), e=end() ; i!=e ; ++i)
 645                         {
 646                                 if (!v.back().try_to_merge(*i))
 647                                 {
 648                                         v.push_back(*i);
 649                                 }
 650                         }
 651                 }
 652                 fputs(" = ", file);
 653                 for (auto i=vals->begin(), e=vals->end() ; i!=e ; ++i)
 654                 {
 655                         i->write_dts(file);
 656                         if (i+1 != e)
 657                         {
 658                                 putc(',', file);
 659                                 putc(' ', file);
 660                         }
 661                 }
 662         }
 663         fputs(";\n", file);
 664 }
 665
 666 size_t
 667 property::offset_of_value(property_value &val)
 668 {
 669         size_t off = 0;
 670         for (auto &v : values)
 671         {
 672                 if (&v == &val)
 673                 {
 674                         return off;
 675                 }
 676                 off += v.size();
 677         }
 678         return -1;
 679 }
 680
 681 string
 682 node::parse_name(text_input_buffer &input, bool &is_property, const char *error)
 683 {
 684         if (!valid)
 685         {
 686                 return string();
 687         }
 688         input.next_token();
 689         if (is_property)
 690         {
 691                 return input.parse_property_name();
 692         }
 693         string n = input.parse_node_or_property_name(is_property);
 694         if (n.empty())
 695         {
 696                 if (n.empty())
 697                 {
 698                         input.parse_error(error);
 699                         valid = false;
 700                 }
 701         }
 702         return n;
 703 }
 704
 705 void
 706 node::visit(std::function<void(node&)> fn)
 707 {
 708         fn(*this);
 709         for (auto &&c : children)
 710         {
 711                 c->visit(fn);
 712         }
 713 }
 714
 715 node::node(input_buffer &structs, input_buffer &strings) : valid(true)
 716 {
 717         std::vector<char> bytes;
 718         while (structs[0] != '\0' && structs[0] != '@')
 719         {
 720                 bytes.push_back(structs[0]);
 721                 ++structs;
 722         }
 723         name = string(bytes.begin(), bytes.end());
 724         bytes.clear();
 725         if (structs[0] == '@')
 726         {
 727                 ++structs;
 728                 while (structs[0] != '\0')
 729                 {
 730                         bytes.push_back(structs[0]);
 731                         ++structs;
 732                 }
 733                 unit_address = string(bytes.begin(), bytes.end());
 734         }
 735         ++structs;
 736         uint32_t token;
 737         while (structs.consume_binary(token))
 738         {
 739                 switch (token)
 740                 {
 741                         default:
 742                                 fprintf(stderr, "Unexpected token 0x%" PRIx32
 743                                         " while parsing node.\n", token);
 744                                 valid = false;
 745                                 return;
 746                         // Child node, parse it.
 747                         case dtb::FDT_BEGIN_NODE:
 748                         {
 749                                 node_ptr child = node::parse_dtb(structs, strings);
 750                                 if (child == 0)
 751                                 {
 752                                         valid = false;
 753                                         return;
 754                                 }
 755                                 children.push_back(std::move(child));
 756                                 break;
 757                         }
 758                         // End of this node, no errors.
 759                         case dtb::FDT_END_NODE:
 760                                 return;
 761                         // Property, parse it.
 762                         case dtb::FDT_PROP:
 763                         {
 764                                 property_ptr prop = property::parse_dtb(structs, strings);
 765                                 if (prop == 0)
 766                                 {
 767                                         valid = false;
 768                                         return;
 769                                 }
 770                                 props.push_back(prop);
 771                                 break;
 772                         }
 773                                 break;
 774                         // End of structs table.  Should appear after
 775                         // the end of the last node.
 776                         case dtb::FDT_END:
 777                                 fprintf(stderr, "Unexpected FDT_END token while parsing node.\n");
 778                                 valid = false;
 779                                 return;
 780                         // NOPs are padding.  Ignore them.
 781                         case dtb::FDT_NOP:
 782                                 break;
 783                 }
 784         }
 785         fprintf(stderr, "Failed to read token from structs table while parsing node.\n");
 786         valid = false;
 787         return;
 788 }
 789
 790
 791 node::node(const string &n,
 792            const std::vector<property_ptr> &p)
 793         : name(n)
 794 {
 795         props.insert(props.begin(), p.begin(), p.end());
 796 }
 797
 798 node_ptr node::create_special_node(const string &name,
 799                                    const std::vector<property_ptr> &props)
 800 {
 801         node_ptr n(new node(name, props));
 802         return n;
 803 }
 804
 805 node::node(text_input_buffer &input,
 806            string &&n,
 807            std::unordered_set<string> &&l,
 808            string &&a,
 809            define_map *defines)
 810         : labels(l), name(n), unit_address(a), valid(true)
 811 {
 812         if (!input.consume('{'))
 813         {
 814                 input.parse_error("Expected { to start new device tree node.\n");
 815         }
 816         input.next_token();
 817         while (valid && !input.consume('}'))
 818         {
 819                 // flag set if we find any characters that are only in
 820                 // the property name character set, not the node
 821                 bool is_property = false;
 822                 string child_name, child_address;
 823                 std::unordered_set<string> child_labels;
 824                 auto parse_delete = [&](const char *expected, bool at)
 825                 {
 826                         if (child_name == string())
 827                         {
 828                                 input.parse_error(expected);
 829                                 valid = false;
 830                                 return;
 831                         }
 832                         input.next_token();
 833                         if (at && input.consume('@'))
 834                         {
 835                                 child_name += '@';
 836                                 child_name += parse_name(input, is_property, "Expected unit address");
 837                         }
 838                         if (!input.consume(';'))
 839                         {
 840                                 input.parse_error("Expected semicolon");
 841                                 valid = false;
 842                                 return;
 843                         }
 844                         input.next_token();
 845                 };
 846                 if (input.consume("/delete-node/"))
 847                 {
 848                         input.next_token();
 849                         child_name = input.parse_node_name();
 850                         parse_delete("Expected node name", true);
 851                         if (valid)
 852                         {
 853                                 deleted_children.insert(child_name);
 854                         }
 855                         continue;
 856                 }
 857                 if (input.consume("/delete-property/"))
 858                 {
 859                         input.next_token();
 860                         child_name = input.parse_property_name();
 861                         parse_delete("Expected property name", false);
 862                         if (valid)
 863                         {
 864                                 deleted_props.insert(child_name);
 865                         }
 866                         continue;
 867                 }
 868                 child_name = parse_name(input, is_property,
 869                                 "Expected property or node name");
 870                 while (input.consume(':'))
 871                 {
 872                         // Node labels can contain any characters?  The
 873                         // spec doesn't say, so we guess so...
 874                         is_property = false;
 875                         child_labels.insert(std::move(child_name));
 876                         child_name = parse_name(input, is_property, "Expected property or node name");
 877                 }
 878                 if (input.consume('@'))
 879                 {
 880                         child_address = parse_name(input, is_property, "Expected unit address");
 881                 }
 882                 if (!valid)
 883                 {
 884                         return;
 885                 }
 886                 input.next_token();
 887                 // If we're parsing a property, then we must actually do that.
 888                 if (input.consume('='))
 889                 {
 890                         property_ptr p = property::parse(input, std::move(child_name),
 891                                         std::move(child_labels), true, defines);
 892                         if (p == 0)
 893                         {
 894                                 valid = false;
 895                         }
 896                         else
 897                         {
 898                                 props.push_back(p);
 899                         }
 900                 }
 901                 else if (!is_property && *input == ('{'))
 902                 {
 903                         node_ptr child = node::parse(input, std::move(child_name),
 904                                         std::move(child_labels), std::move(child_address), defines);
 905                         if (child)
 906                         {
 907                                 children.push_back(std::move(child));
 908                         }
 909                         else
 910                         {
 911                                 valid = false;
 912                         }
 913                 }
 914                 else if (input.consume(';'))
 915                 {
 916                         props.push_back(property_ptr(new property(std::move(child_name), std::move(child_labels))));
 917                 }
 918                 else
 919                 {
 920                         input.parse_error("Error parsing property.  Expected property value");
 921                         valid = false;
 922                 }
 923                 input.next_token();
 924         }
 925         input.next_token();
 926         input.consume(';');
 927 }
 928
 929 bool
 930 node::cmp_properties(property_ptr &p1, property_ptr &p2)
 931 {
 932         return p1->get_key() < p2->get_key();
 933 }
 934
 935 bool
 936 node::cmp_children(node_ptr &c1, node_ptr &c2)
 937 {
 938         if (c1->name == c2->name)
 939         {
 940                 return c1->unit_address < c2->unit_address;
 941         }
 942         return c1->name < c2->name;
 943 }
 944
 945 void
 946 node::sort()
 947 {
 948         std::sort(property_begin(), property_end(), cmp_properties);
 949         std::sort(child_begin(), child_end(), cmp_children);
 950         for (auto &c : child_nodes())
 951         {
 952                 c->sort();
 953         }
 954 }
 955
 956 node_ptr
 957 node::parse(text_input_buffer &input,
 958             string &&name,
 959             string_set &&label,
 960             string &&address,
 961             define_map *defines)
 962 {
 963         node_ptr n(new node(input,
 964                             std::move(name),
 965                             std::move(label),
 966                             std::move(address),
 967                             defines));
 968         if (!n->valid)
 969         {
 970                 n = 0;
 971         }
 972         return n;
 973 }
 974
 975 node_ptr
 976 node::parse_dtb(input_buffer &structs, input_buffer &strings)
 977 {
 978         node_ptr n(new node(structs, strings));
 979         if (!n->valid)
 980         {
 981                 n = 0;
 982         }
 983         return n;
 984 }
 985
 986 property_ptr
 987 node::get_property(const string &key)
 988 {
 989         for (auto &i : props)
 990         {
 991                 if (i->get_key() == key)
 992                 {
 993                         return i;
 994                 }
 995         }
 996         return 0;
 997 }
 998
 999 void
1000 node::merge_node(node_ptr other)
1001 {
1002         for (auto &l : other->labels)
1003         {
1004                 labels.insert(l);
1005         }
1006         // Note: this is an O(n*m) operation.  It might be sensible to
1007         // optimise this if we find that there are nodes with very
1008         // large numbers of properties, but for typical usage the
1009         // entire vector will fit (easily) into cache, so iterating
1010         // over it repeatedly isn't that expensive.
1011         for (auto &p : other->properties())
1012         {
1013                 bool found = false;
1014                 for (auto &mp : properties())
1015                 {
1016                         if (mp->get_key() == p->get_key())
1017                         {
1018                                 mp = p;
1019                                 found = true;
1020                                 break;
1021                         }
1022                 }
1023                 if (!found)
1024                 {
1025                         add_property(p);
1026                 }
1027         }
1028         for (auto &c : other->children)
1029         {
1030                 bool found = false;
1031                 for (auto &i : children)
1032                 {
1033                         if (i->name == c->name && i->unit_address == c->unit_address)
1034                         {
1035                                 i->merge_node(std::move(c));
1036                                 found = true;
1037                                 break;
1038                         }
1039                 }
1040                 if (!found)
1041                 {
1042                         children.push_back(std::move(c));
1043                 }
1044         }
1045         children.erase(std::remove_if(children.begin(), children.end(),
1046                         [&](const node_ptr &p) {
1047                                 string full_name = p->name;
1048                                 if (p->unit_address != string())
1049                                 {
1050                                         full_name += '@';
1051                                         full_name += p->unit_address;
1052                                 }
1053                                 if (other->deleted_children.count(full_name) > 0)
1054                                 {
1055                                         other->deleted_children.erase(full_name);
1056                                         return true;
1057                                 }
1058                                 return false;
1059                         }), children.end());
1060         props.erase(std::remove_if(props.begin(), props.end(),
1061                         [&](const property_ptr &p) {
1062                                 if (other->deleted_props.count(p->get_key()) > 0)
1063                                 {
1064                                         other->deleted_props.erase(p->get_key());
1065                                         return true;
1066                                 }
1067                                 return false;
1068                         }), props.end());
1069 }
1070
1071 void
1072 node::write(dtb::output_writer &writer, dtb::string_table &strings)
1073 {
1074         writer.write_token(dtb::FDT_BEGIN_NODE);
1075         byte_buffer name_buffer;
1076         push_string(name_buffer, name);
1077         if (unit_address != string())
1078         {
1079                 name_buffer.push_back('@');
1080                 push_string(name_buffer, unit_address);
1081         }
1082         writer.write_comment(name);
1083         writer.write_data(name_buffer);
1084         writer.write_data((uint8_t)0);
1085         for (auto p : properties())
1086         {
1087                 p->write(writer, strings);
1088         }
1089         for (auto &c : child_nodes())
1090         {
1091                 c->write(writer, strings);
1092         }
1093         writer.write_token(dtb::FDT_END_NODE);
1094 }
1095
1096 void
1097 node::write_dts(FILE *file, int indent)
1098 {
1099         for (int i=0 ; i<indent ; i++)
1100         {
1101                 putc('\t', file);
1102         }
1103 #ifdef PRINT_LABELS
1104         for (auto &label : labels)
1105         {
1106                 fprintf(file, "%s: ", label.c_str());
1107         }
1108 #endif
1109         if (name != string())
1110         {
1111                 fputs(name.c_str(), file);
1112         }
1113         if (unit_address != string())
1114         {
1115                 putc('@', file);
1116                 fputs(unit_address.c_str(), file);
1117         }
1118         fputs(" {\n\n", file);
1119         for (auto p : properties())
1120         {
1121                 p->write_dts(file, indent+1);
1122         }
1123         for (auto &c : child_nodes())
1124         {
1125                 c->write_dts(file, indent+1);
1126         }
1127         for (int i=0 ; i<indent ; i++)
1128         {
1129                 putc('\t', file);
1130         }
1131         fputs("};\n", file);
1132 }
1133
1134 void
1135 device_tree::collect_names_recursive(node_ptr &n, node_path &path)
1136 {
1137         path.push_back(std::make_pair(n->name, n->unit_address));
1138         for (const string &name : n->labels)
1139         {
1140                 if (name != string())
1141                 {
1142                         auto iter = node_names.find(name);
1143                         if (iter == node_names.end())
1144                         {
1145                                 node_names.insert(std::make_pair(name, n.get()));
1146                                 node_paths.insert(std::make_pair(name, path));
1147                         }
1148                         else
1149                         {
1150                                 node_names.erase(iter);
1151                                 auto i = node_paths.find(name);
1152                                 if (i != node_paths.end())
1153                                 {
1154                                         node_paths.erase(name);
1155                                 }
1156                                 fprintf(stderr, "Label not unique: %s.  References to this label will not be resolved.\n", name.c_str());
1157                         }
1158                 }
1159         }
1160         for (auto &c : n->child_nodes())
1161         {
1162                 collect_names_recursive(c, path);
1163         }
1164         // Now we collect the phandles and properties that reference
1165         // other nodes.
1166         for (auto &p : n->properties())
1167         {
1168                 for (auto &v : *p)
1169                 {
1170                         if (v.is_phandle())
1171                         {
1172                                 fixups.push_back({path, p, v});
1173                         }
1174                         if (v.is_cross_reference())
1175                         {
1176                                 cross_references.push_back(&v);
1177                         }
1178                 }
1179                 if ((p->get_key() == "phandle") ||
1180                     (p->get_key() == "linux,phandle"))
1181                 {
1182                         if (p->begin()->byte_data.size() != 4)
1183                         {
1184                                 fprintf(stderr, "Invalid phandle value for node %s.  Should be a 4-byte value.\n", n->name.c_str());
1185                                 valid = false;
1186                         }
1187                         else
1188                         {
1189                                 uint32_t phandle = p->begin()->get_as_uint32();
1190                                 used_phandles.insert(std::make_pair(phandle, n.get()));
1191                         }
1192                 }
1193         }
1194         path.pop_back();
1195 }
1196
1197 void
1198 device_tree::collect_names()
1199 {
1200         node_path p;
1201         node_names.clear();
1202         node_paths.clear();
1203         cross_references.clear();
1204         fixups.clear();
1205         collect_names_recursive(root, p);
1206 }
1207
1208 void
1209 device_tree::resolve_cross_references()
1210 {
1211         for (auto *pv : cross_references)
1212         {
1213                 node_path path = node_paths[pv->string_data];
1214                 auto p = path.begin();
1215                 auto pe = path.end();
1216                 if (p != pe)
1217                 {
1218                         // Skip the first name in the path.  It's always "", and implicitly /
1219                         for (++p ; p!=pe ; ++p)
1220                         {
1221                                 pv->byte_data.push_back('/');
1222                                 push_string(pv->byte_data, p->first);
1223                                 if (!(p->second.empty()))
1224                                 {
1225                                         pv->byte_data.push_back('@');
1226                                         push_string(pv->byte_data, p->second);
1227                                         pv->byte_data.push_back(0);
1228                                 }
1229                         }
1230                 }
1231         }
1232         std::unordered_map<property_value*, fixup&> phandle_set;
1233         for (auto &i : fixups)
1234         {
1235                 phandle_set.insert({&i.val, i});
1236         }
1237         std::vector<std::reference_wrapper<fixup>> sorted_phandles;
1238         root->visit([&](node &n) {
1239                 for (auto &p : n.properties())
1240                 {
1241                         for (auto &v : *p)
1242                         {
1243                                 auto i = phandle_set.find(&v);
1244                                 if (i != phandle_set.end())
1245                                 {
1246                                         sorted_phandles.push_back(i->second);
1247                                 }
1248                         }
1249                 }
1250         });
1251         assert(sorted_phandles.size() == fixups.size());
1252
1253         uint32_t phandle = 1;
1254         for (auto &i : sorted_phandles)
1255         {
1256                 string target_name = i.get().val.string_data;
1257                 node *target = nullptr;
1258                 string possible;
1259                 // If the node name is a path, then look it up by following the path,
1260                 // otherwise jump directly to the named node.
1261                 if (target_name[0] == '/')
1262                 {
1263                         string path;
1264                         target = root.get();
1265                         std::istringstream ss(target_name);
1266                         string path_element;
1267                         // Read the leading /
1268                         std::getline(ss, path_element, '/');
1269                         // Iterate over path elements
1270                         while (!ss.eof())
1271                         {
1272                                 path += '/';
1273                                 std::getline(ss, path_element, '/');
1274                                 std::istringstream nss(path_element);
1275                                 string node_name, node_address;
1276                                 std::getline(nss, node_name, '@');
1277                                 std::getline(nss, node_address, '@');
1278                                 node *next = nullptr;
1279                                 for (auto &c : target->child_nodes())
1280                                 {
1281                                         if (c->name == node_name)
1282                                         {
1283                                                 if (c->unit_address == node_address)
1284                                                 {
1285                                                         next = c.get();
1286                                                         break;
1287                                                 }
1288                                                 else
1289                                                 {
1290                                                         possible = path + c->name;
1291                                                         if (c->unit_address != string())
1292                                                         {
1293                                                                 possible += '@';
1294                                                                 possible += c->unit_address;
1295                                                         }
1296                                                 }
1297                                         }
1298                                 }
1299                                 path += node_name;
1300                                 if (node_address != string())
1301                                 {
1302                                         path += '@';
1303                                         path += node_address;
1304                                 }
1305                                 target = next;
1306                                 if (target == nullptr)
1307                                 {
1308                                         break;
1309                                 }
1310                         }
1311                 }
1312                 else
1313                 {
1314                         target = node_names[target_name];
1315                 }
1316                 if (target == nullptr)
1317                 {
1318                         if (is_plugin)
1319                         {
1320                                 unresolved_fixups.push_back(i);
1321                                 continue;
1322                         }
1323                         else
1324                         {
1325                                 fprintf(stderr, "Failed to find node with label: %s\n", target_name.c_str());
1326                                 if (possible != string())
1327                                 {
1328                                         fprintf(stderr, "Possible intended match: %s\n", possible.c_str());
1329                                 }
1330                                 valid = 0;
1331                                 return;
1332                         }
1333                 }
1334                 // If there is an existing phandle, use it
1335                 property_ptr p = target->get_property("phandle");
1336                 if (p == 0)
1337                 {
1338                         p = target->get_property("linux,phandle");
1339                 }
1340                 if (p == 0)
1341                 {
1342                         // Otherwise insert a new phandle node
1343                         property_value v;
1344                         while (used_phandles.find(phandle) != used_phandles.end())
1345                         {
1346                                 // Note that we only don't need to
1347                                 // store this phandle in the set,
1348                                 // because we are monotonically
1349                                 // increasing the value of phandle and
1350                                 // so will only ever revisit this value
1351                                 // if we have used 2^32 phandles, at
1352                                 // which point our blob won't fit in
1353                                 // any 32-bit system and we've done
1354                                 // something badly wrong elsewhere
1355                                 // already.
1356                                 phandle++;
1357                         }
1358                         push_big_endian(v.byte_data, phandle++);
1359                         if (phandle_node_name == BOTH || phandle_node_name == LINUX)
1360                         {
1361                                 p.reset(new property("linux,phandle"));
1362                                 p->add_value(v);
1363                                 target->add_property(p);
1364                         }
1365                         if (phandle_node_name == BOTH || phandle_node_name == EPAPR)
1366                         {
1367                                 p.reset(new property("phandle"));
1368                                 p->add_value(v);
1369                                 target->add_property(p);
1370                         }
1371                 }
1372                 p->begin()->push_to_buffer(i.get().val.byte_data);
1373                 assert(i.get().val.byte_data.size() == 4);
1374         }
1375 }
1376
1377
1378 void
1379 device_tree::parse_file(text_input_buffer &input,
1380                         std::vector<node_ptr> &roots,
1381                         bool &read_header)
1382 {
1383         input.next_token();
1384         // Read the header
1385         if (input.consume("/dts-v1/;"))
1386         {
1387                 read_header = true;
1388         }
1389         input.next_token();
1390         if (input.consume("/plugin/;"))
1391         {
1392                 is_plugin = true;
1393         }
1394         input.next_token();
1395         if (!read_header)
1396         {
1397                 input.parse_error("Expected /dts-v1/; version string");
1398         }
1399         // Read any memory reservations
1400         while (input.consume("/memreserve/"))
1401         {
1402                 unsigned long long start, len;
1403                 input.next_token();
1404                 // Read the start and length.
1405                 if (!(input.consume_integer_expression(start) &&
1406                     (input.next_token(),
1407                     input.consume_integer_expression(len))))
1408                 {
1409                         input.parse_error("Expected size on /memreserve/ node.");
1410                 }
1411                 input.next_token();
1412                 input.consume(';');
1413                 reservations.push_back(reservation(start, len));
1414                 input.next_token();
1415         }
1416         while (valid && !input.finished())
1417         {
1418                 node_ptr n;
1419                 if (input.consume('/'))
1420                 {
1421                         input.next_token();
1422                         n = node::parse(input, string(), string_set(), string(), &defines);
1423                 }
1424                 else if (input.consume('&'))
1425                 {
1426                         input.next_token();
1427                         string name = input.parse_node_name();
1428                         input.next_token();
1429                         n = node::parse(input, std::move(name), string_set(), string(), &defines);
1430                 }
1431                 else
1432                 {
1433                         input.parse_error("Failed to find root node /.");
1434                 }
1435                 if (n)
1436                 {
1437                         roots.push_back(std::move(n));
1438                 }
1439                 else
1440                 {
1441                         valid = false;
1442                 }
1443                 input.next_token();
1444         }
1445 }
1446
1447 template<class writer> void
1448 device_tree::write(int fd)
1449 {
1450         dtb::string_table st;
1451         dtb::header head;
1452         writer head_writer;
1453         writer reservation_writer;
1454         writer struct_writer;
1455         writer strings_writer;
1456
1457         // Build the reservation table
1458         reservation_writer.write_comment(string("Memory reservations"));
1459         reservation_writer.write_label(string("dt_reserve_map"));
1460         for (auto &i : reservations)
1461         {
1462                 reservation_writer.write_comment(string("Reservation start"));
1463                 reservation_writer.write_data(i.first);
1464                 reservation_writer.write_comment(string("Reservation length"));
1465                 reservation_writer.write_data(i.first);
1466         }
1467         // Write n spare reserve map entries, plus the trailing 0.
1468         for (uint32_t i=0 ; i<=spare_reserve_map_entries ; i++)
1469         {
1470                 reservation_writer.write_data((uint64_t)0);
1471                 reservation_writer.write_data((uint64_t)0);
1472         }
1473
1474
1475         struct_writer.write_comment(string("Device tree"));
1476         struct_writer.write_label(string("dt_struct_start"));
1477         root->write(struct_writer, st);
1478         struct_writer.write_token(dtb::FDT_END);
1479         struct_writer.write_label(string("dt_struct_end"));
1480
1481         st.write(strings_writer);
1482         // Find the strings size before we stick padding on the end.
1483         // Note: We should possibly use a new writer for the padding.
1484         head.size_dt_strings = strings_writer.size();
1485
1486         // Stick the padding in the strings writer, but after the
1487         // marker indicating that it's the end.
1488         // Note: We probably should add a padding call to the writer so
1489         // that the asm back end can write padding directives instead
1490         // of a load of 0 bytes.
1491         for (uint32_t i=0 ; i<blob_padding ; i++)
1492         {
1493                 strings_writer.write_data((uint8_t)0);
1494         }
1495         head.totalsize = sizeof(head) + strings_writer.size() +
1496                 struct_writer.size() + reservation_writer.size();
1497         while (head.totalsize < minimum_blob_size)
1498         {
1499                 head.totalsize++;
1500                 strings_writer.write_data((uint8_t)0);
1501         }
1502         head.off_dt_struct = sizeof(head) + reservation_writer.size();;
1503         head.off_dt_strings = head.off_dt_struct + struct_writer.size();
1504         head.off_mem_rsvmap = sizeof(head);
1505         head.boot_cpuid_phys = boot_cpu;
1506         head.size_dt_struct = struct_writer.size();
1507         head.write(head_writer);
1508
1509         head_writer.write_to_file(fd);
1510         reservation_writer.write_to_file(fd);
1511         struct_writer.write_to_file(fd);
1512         strings_writer.write_label(string("dt_blob_end"));
1513         strings_writer.write_to_file(fd);
1514 }
1515
1516 node*
1517 device_tree::referenced_node(property_value &v)
1518 {
1519         if (v.is_phandle())
1520         {
1521                 return node_names[v.string_data];
1522         }
1523         if (v.is_binary())
1524         {
1525                 return used_phandles[v.get_as_uint32()];
1526         }
1527         return 0;
1528 }
1529
1530 void
1531 device_tree::write_binary(int fd)
1532 {
1533         write<dtb::binary_writer>(fd);
1534 }
1535
1536 void
1537 device_tree::write_asm(int fd)
1538 {
1539         write<dtb::asm_writer>(fd);
1540 }
1541
1542 void
1543 device_tree::write_dts(int fd)
1544 {
1545         FILE *file = fdopen(fd, "w");
1546         fputs("/dts-v1/;\n\n", file);
1547
1548         if (!reservations.empty())
1549         {
1550                 const char msg[] = "/memreserve/";
1551                 fwrite(msg, sizeof(msg), 1, file);
1552                 for (auto &i : reservations)
1553                 {
1554                         fprintf(file, " %" PRIx64 " %" PRIx64, i.first, i.second);
1555                 }
1556                 fputs(";\n\n", file);
1557         }
1558         putc('/', file);
1559         putc(' ', file);
1560         root->write_dts(file, 0);
1561         fclose(file);
1562 }
1563
1564 void
1565 device_tree::parse_dtb(const string &fn, FILE *)
1566 {
1567         auto in = input_buffer::buffer_for_file(fn);
1568         if (in == 0)
1569         {
1570                 valid = false;
1571                 return;
1572         }
1573         input_buffer &input = *in;
1574         dtb::header h;
1575         valid = h.read_dtb(input);
1576         boot_cpu = h.boot_cpuid_phys;
1577         if (h.last_comp_version > 17)
1578         {
1579                 fprintf(stderr, "Don't know how to read this version of the device tree blob");
1580                 valid = false;
1581         }
1582         if (!valid)
1583         {
1584                 return;
1585         }
1586         input_buffer reservation_map =
1587                 input.buffer_from_offset(h.off_mem_rsvmap, 0);
1588         uint64_t start, length;
1589         do
1590         {
1591                 if (!(reservation_map.consume_binary(start) &&
1592                       reservation_map.consume_binary(length)))
1593                 {
1594                         fprintf(stderr, "Failed to read memory reservation table\n");
1595                         valid = false;
1596                         return;
1597                 }
1598         } while (!((start == 0) && (length == 0)));
1599         input_buffer struct_table =
1600                 input.buffer_from_offset(h.off_dt_struct, h.size_dt_struct);
1601         input_buffer strings_table =
1602                 input.buffer_from_offset(h.off_dt_strings, h.size_dt_strings);
1603         uint32_t token;
1604         if (!(struct_table.consume_binary(token) &&
1605                 (token == dtb::FDT_BEGIN_NODE)))
1606         {
1607                 fprintf(stderr, "Expected FDT_BEGIN_NODE token.\n");
1608                 valid = false;
1609                 return;
1610         }
1611         root = node::parse_dtb(struct_table, strings_table);
1612         if (!(struct_table.consume_binary(token) && (token == dtb::FDT_END)))
1613         {
1614                 fprintf(stderr, "Expected FDT_END token after parsing root node.\n");
1615                 valid = false;
1616                 return;
1617         }
1618         valid = (root != 0);
1619 }
1620
1621 string
1622 device_tree::node_path::to_string() const
1623 {
1624         string path;
1625         auto p = begin();
1626         auto pe = end();
1627         if ((p == pe) || (p+1 == pe))
1628         {
1629                 return string("/");
1630         }
1631         // Skip the first name in the path.  It's always "", and implicitly /
1632         for (++p ; p!=pe ; ++p)
1633         {
1634                 path += '/';
1635                 path += p->first;
1636                 if (!(p->second.empty()))
1637                 {
1638                         path += '@';
1639                         path += p->second;
1640                 }
1641         }
1642         return path;
1643 }
1644
1645 void
1646 device_tree::parse_dts(const string &fn, FILE *depfile)
1647 {
1648         auto in = input_buffer::buffer_for_file(fn);
1649         if (!in)
1650         {
1651                 valid = false;
1652                 return;
1653         }
1654         std::vector<node_ptr> roots;
1655         std::unordered_set<string> defnames;
1656         for (auto &i : defines)
1657         {
1658                 defnames.insert(i.first);
1659         }
1660         text_input_buffer input(std::move(in),
1661                                 std::move(defnames),
1662                                 std::vector<string>(include_paths),
1663                                 dirname(fn),
1664                                 depfile);
1665         bool read_header = false;
1666         parse_file(input, roots, read_header);
1667         switch (roots.size())
1668         {
1669                 case 0:
1670                         valid = false;
1671                         input.parse_error("Failed to find root node /.");
1672                         return;
1673                 case 1:
1674                         root = std::move(roots[0]);
1675                         break;
1676                 default:
1677                 {
1678                         root = std::move(roots[0]);
1679                         for (auto i=++(roots.begin()), e=roots.end() ; i!=e ; ++i)
1680                         {
1681                                 auto &node = *i;
1682                                 string name = node->name;
1683                                 if (name == string())
1684                                 {
1685                                         root->merge_node(std::move(node));
1686                                 }
1687                                 else
1688                                 {
1689                                         auto existing = node_names.find(name);
1690                                         if (existing == node_names.end())
1691                                         {
1692                                                 collect_names();
1693                                                 existing = node_names.find(name);
1694                                         }
1695                                         if (existing == node_names.end())
1696                                         {
1697                                                 fprintf(stderr, "Unable to merge node: %s\n", name.c_str());
1698                                         }
1699                                         else
1700                                         {
1701                                                 existing->second->merge_node(std::move(node));
1702                                         }
1703                                 }
1704                         }
1705                 }
1706         }
1707         collect_names();
1708         resolve_cross_references();
1709         if (write_symbols)
1710         {
1711                 std::vector<property_ptr> symbols;
1712                 // Create a symbol table.  Each label  in this device tree may be
1713                 // referenced by other plugins, so we create a __symbols__ node inside
1714                 // the root that contains mappings (properties) from label names to
1715                 // paths.
1716                 for (auto &s : node_paths)
1717                 {
1718                         property_value v;
1719                         v.string_data = s.second.to_string();
1720                         v.type = property_value::STRING;
1721                         string name = s.first;
1722                         auto prop = std::make_shared<property>(std::move(name));
1723                         prop->add_value(v);
1724                         symbols.push_back(prop);
1725                 }
1726                 root->add_child(node::create_special_node("__symbols__", symbols));
1727                 // If this is a plugin, then we also need to create two extra nodes.
1728                 // Internal phandles will need to be renumbered to avoid conflicts with
1729                 // already-loaded nodes and external references will need to be
1730                 // resolved.
1731                 if (is_plugin)
1732                 {
1733                         // Create the fixups entry.  This is of the form:
1734                         // {target} = {path}:{property name}:{offset}
1735                         auto create_fixup_entry = [&](fixup &i, string target)
1736                                 {
1737                                         string value = i.path.to_string();
1738                                         value += ':';
1739                                         value += i.prop->get_key();
1740                                         value += ':';
1741                                         value += std::to_string(i.prop->offset_of_value(i.val));
1742                                         property_value v;
1743                                         v.string_data = value;
1744                                         v.type = property_value::STRING;
1745                                         auto prop = std::make_shared<property>(std::move(target));
1746                                         prop->add_value(v);
1747                                         return prop;
1748                                 };
1749                         // If we have any unresolved phandle references in this plugin,
1750                         // then we must update them to 0xdeadbeef and leave a property in
1751                         // the /__fixups__ node whose key is the label and whose value is
1752                         // as described above.
1753                         if (!unresolved_fixups.empty())
1754                         {
1755                                 symbols.clear();
1756                                 for (auto &i : unresolved_fixups)
1757                                 {
1758                                         auto &val = i.get().val;
1759                                         symbols.push_back(create_fixup_entry(i, val.string_data));
1760                                         val.byte_data.push_back(0xde);
1761                                         val.byte_data.push_back(0xad);
1762                                         val.byte_data.push_back(0xbe);
1763                                         val.byte_data.push_back(0xef);
1764                                         val.type = property_value::BINARY;
1765                                 }
1766                                 root->add_child(node::create_special_node("__fixups__", symbols));
1767                         }
1768                         symbols.clear();
1769                         // If we have any resolved phandle references in this plugin, then
1770                         // we must leave a property in the /__local_fixups__ node whose key
1771                         // is 'fixup' and whose value is as described above.
1772                         for (auto &i : fixups)
1773                         {
1774                                 if (!i.val.is_phandle())
1775                                 {
1776                                         continue;
1777                                 }
1778                                 symbols.push_back(create_fixup_entry(i, "fixup"));
1779                         }
1780                         // We've iterated over all fixups, but only emit the
1781                         // __local_fixups__ if we found some that were resolved internally.
1782                         if (!symbols.empty())
1783                         {
1784                                 root->add_child(node::create_special_node("__local_fixups__", symbols));
1785                         }
1786                 }
1787         }
1788 }
1789
1790 bool device_tree::parse_define(const char *def)
1791 {
1792         const char *val = strchr(def, '=');
1793         if (!val)
1794         {
1795                 if (strlen(def) != 0)
1796                 {
1797                         string name(def);
1798                         defines[name];
1799                         return true;
1800                 }
1801                 return false;
1802         }
1803         string name(def, val-def);
1804         string name_copy = name;
1805         val++;
1806         std::unique_ptr<input_buffer> raw(new input_buffer(val, strlen(val)));
1807         text_input_buffer in(std::move(raw),
1808                              std::unordered_set<string>(),
1809                              std::vector<string>(),
1810                              string(),
1811                              nullptr);
1812         property_ptr p = property::parse(in, std::move(name_copy), string_set(), false);
1813         if (p)
1814                 defines[name] = p;
1815         return (bool)p;
1816 }
1817
1818 } // namespace fdt
1819
1820 } // namespace dtc
1821