usr.bin/dtc/fdt.cc

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