usr.bin/dtc/fdt.cc

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause
   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
  33 #define __STDC_LIMIT_MACROS 1
  34
  35 #include "fdt.hh"
  36 #include "dtb.hh"
  37
  38 #include <algorithm>
  39 #include <limits>
  40 #include <sstream>
  41
  42 #include <ctype.h>
  43 #include <fcntl.h>
  44 #include <inttypes.h>
  45 #include <libgen.h>
  46 #include <stdio.h>
  47 #include <stdlib.h>
  48 #include <string.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                                 // FIXME: Distinguish invalid syntax from a
 338                                 // number that cannot be represented in an
 339                                 // unsigned long long.
 340                                 input.parse_error("Expected numbers in array of cells");
 341                                 valid = false;
 342                                 return;
 343                         }
 344                         // FIXME: No sign information available, so cannot
 345                         // distinguish small negative values from large
 346                         // positive ones, and thus we have to conservatively
 347                         // permit anything that looks like a sign-extended
 348                         // negative integer.
 349                         if (cell_size < 64 && val >= (1ull << cell_size) &&
 350                             (val | ((1ull << (cell_size - 1)) - 1)) !=
 351                             std::numeric_limits<unsigned long long>::max())
 352                         {
 353                                 std::string msg = "Value does not fit in a " +
 354                                         std::to_string(cell_size) + "-bit cell";
 355                                 input.parse_error(msg.c_str());
 356                                 valid = false;
 357                                 return;
 358                         }
 359                         switch (cell_size)
 360                         {
 361                                 case 8:
 362                                         v.byte_data.push_back(val);
 363                                         break;
 364                                 case 16:
 365                                         push_big_endian(v.byte_data, (uint16_t)val);
 366                                         break;
 367                                 case 32:
 368                                         push_big_endian(v.byte_data, (uint32_t)val);
 369                                         break;
 370                                 case 64:
 371                                         push_big_endian(v.byte_data, (uint64_t)val);
 372                                         break;
 373                                 default:
 374                                         assert(0 && "Invalid cell size!");
 375                         }
 376                         input.next_token();
 377                 }
 378         }
 379         // Don't store an empty string value here.
 380         if (v.byte_data.size() > 0)
 381         {
 382                 values.push_back(v);
 383         }
 384 }
 385
 386 void
 387 property::parse_bytes(text_input_buffer &input)
 388 {
 389         assert(*input == '[');
 390         ++input;
 391         property_value v;
 392         input.next_token();
 393         while (!input.consume(']'))
 394         {
 395                 {
 396                         //FIXME: We should support
 397                         //labels in the middle of
 398                         //these, but we don't.
 399                         uint8_t val;
 400                         if (!input.consume_hex_byte(val))
 401                         {
 402                                 input.parse_error("Expected hex bytes in array of bytes");
 403                                 valid = false;
 404                                 return;
 405                         }
 406                         v.byte_data.push_back(val);
 407                         input.next_token();
 408                 }
 409         }
 410         values.push_back(v);
 411 }
 412
 413 void
 414 property::parse_reference(text_input_buffer &input)
 415 {
 416         assert(*input == '&');
 417         ++input;
 418         input.next_token();
 419         property_value v;
 420         v.string_data = input.parse_node_name();
 421         if (v.string_data.empty())
 422         {
 423                 input.parse_error("Expected node name");
 424                 valid = false;
 425                 return;
 426         }
 427         v.type = property_value::CROSS_REFERENCE;
 428         values.push_back(v);
 429 }
 430
 431 property::property(input_buffer &structs, input_buffer &strings)
 432 {
 433         uint32_t name_offset;
 434         uint32_t length;
 435         valid = structs.consume_binary(length) &&
 436                 structs.consume_binary(name_offset);
 437         if (!valid)
 438         {
 439                 fprintf(stderr, "Failed to read property\n");
 440                 return;
 441         }
 442         // Find the name
 443         input_buffer name_buffer = strings.buffer_from_offset(name_offset);
 444         if (name_buffer.finished())
 445         {
 446                 fprintf(stderr, "Property name offset %" PRIu32
 447                         " is past the end of the strings table\n",
 448                         name_offset);
 449                 valid = false;
 450                 return;
 451         }
 452         key = name_buffer.parse_to(0);
 453
 454         // If we're empty, do not push anything as value.
 455         if (!length)
 456                 return;
 457
 458         // Read the value
 459         uint8_t byte;
 460         property_value v;
 461         for (uint32_t i=0 ; i<length ; i++)
 462         {
 463                 if (!(valid = structs.consume_binary(byte)))
 464                 {
 465                         fprintf(stderr, "Failed to read property value\n");
 466                         return;
 467                 }
 468                 v.byte_data.push_back(byte);
 469         }
 470         values.push_back(v);
 471 }
 472
 473 void property::parse_define(text_input_buffer &input, define_map *defines)
 474 {
 475         input.consume('$');
 476         if (!defines)
 477         {
 478                 input.parse_error("No predefined properties to match name\n");
 479                 valid = false;
 480                 return;
 481         }
 482         string name = input.parse_property_name();
 483         define_map::iterator found;
 484         if ((name == string()) ||
 485             ((found = defines->find(name)) == defines->end()))
 486         {
 487                 input.parse_error("Undefined property name\n");
 488                 valid = false;
 489                 return;
 490         }
 491         values.push_back((*found).second->values[0]);
 492 }
 493
 494 property::property(text_input_buffer &input,
 495                    string &&k,
 496                    string_set &&l,
 497                    bool semicolonTerminated,
 498                    define_map *defines) : key(k), labels(l), valid(true)
 499 {
 500         do {
 501                 input.next_token();
 502                 switch (*input)
 503                 {
 504                         case '$':
 505                         {
 506                                 parse_define(input, defines);
 507                                 if (valid)
 508                                 {
 509                                         break;
 510                                 }
 511                         }
 512                         [[fallthrough]];
 513                         default:
 514                                 input.parse_error("Invalid property value.");
 515                                 valid = false;
 516                                 return;
 517                         case '/':
 518                         {
 519                                 if (input.consume("/incbin/(\""))
 520                                 {
 521                                         auto loc = input.location();
 522                                         std::string filename = input.parse_to('"');
 523                                         if (!(valid = input.consume('"')))
 524                                         {
 525                                                 loc.report_error("Syntax error, expected '\"' to terminate /incbin/(");
 526                                                 return;
 527                                         }
 528                                         property_value v;
 529                                         if (!(valid = input.read_binary_file(filename, v.byte_data)))
 530                                         {
 531                                                 input.parse_error("Cannot open binary include file");
 532                                                 return;
 533                                         }
 534                                         if (!(valid &= input.consume(')')))
 535                                         {
 536                                                 input.parse_error("Syntax error, expected ')' to terminate /incbin/(");
 537                                                 return;
 538                                         }
 539                                         values.push_back(v);
 540                                         break;
 541                                 }
 542                                 unsigned long long bits = 0;
 543                                 valid = input.consume("/bits/");
 544                                 input.next_token();
 545                                 valid &= input.consume_integer(bits);
 546                                 if ((bits != 8) &&
 547                                     (bits != 16) &&
 548                                     (bits != 32) &&
 549                                     (bits != 64)) {
 550                                         input.parse_error("Invalid size for elements");
 551                                         valid = false;
 552                                 }
 553                                 if (!valid) return;
 554                                 input.next_token();
 555                                 if (*input != '<')
 556                                 {
 557                                         input.parse_error("/bits/ directive is only valid on arrays");
 558                                         valid = false;
 559                                         return;
 560                                 }
 561                                 parse_cells(input, bits);
 562                                 break;
 563                         }
 564                         case '"':
 565                                 parse_string(input);
 566                                 break;
 567                         case '<':
 568                                 parse_cells(input, 32);
 569                                 break;
 570                         case '[':
 571                                 parse_bytes(input);
 572                                 break;
 573                         case '&':
 574                                 parse_reference(input);
 575                                 break;
 576                         case ';':
 577                         {
 578                                 break;
 579                         }
 580                 }
 581                 input.next_token();
 582         } while (input.consume(','));
 583         if (semicolonTerminated && !input.consume(';'))
 584         {
 585                 input.parse_error("Expected ; at end of property");
 586                 valid = false;
 587         }
 588 }
 589
 590 property_ptr
 591 property::parse_dtb(input_buffer &structs, input_buffer &strings)
 592 {
 593         property_ptr p(new property(structs, strings));
 594         if (!p->valid)
 595         {
 596                 p = nullptr;
 597         }
 598         return p;
 599 }
 600
 601 property_ptr
 602 property::parse(text_input_buffer &input, string &&key, string_set &&label,
 603                 bool semicolonTerminated, define_map *defines)
 604 {
 605         property_ptr p(new property(input,
 606                                     std::move(key),
 607                                     std::move(label),
 608                                     semicolonTerminated,
 609                                     defines));
 610         if (!p->valid)
 611         {
 612                 p = nullptr;
 613         }
 614         return p;
 615 }
 616
 617 void
 618 property::write(dtb::output_writer &writer, dtb::string_table &strings)
 619 {
 620         writer.write_token(dtb::FDT_PROP);
 621         byte_buffer value_buffer;
 622         for (value_iterator i=begin(), e=end() ; i!=e ; ++i)
 623         {
 624                 i->push_to_buffer(value_buffer);
 625         }
 626         writer.write_data((uint32_t)value_buffer.size());
 627         writer.write_comment(key);
 628         writer.write_data(strings.add_string(key));
 629         writer.write_data(value_buffer);
 630 }
 631
 632 bool
 633 property_value::try_to_merge(property_value &other)
 634 {
 635         resolve_type();
 636         switch (type)
 637         {
 638                 case UNKNOWN:
 639                         __builtin_unreachable();
 640                         assert(0);
 641                         return false;
 642                 case EMPTY:
 643                         *this = other;
 644                         [[fallthrough]];
 645                 case STRING:
 646                 case STRING_LIST:
 647                 case CROSS_REFERENCE:
 648                         return false;
 649                 case PHANDLE:
 650                 case BINARY:
 651                         if (other.type == PHANDLE || other.type == BINARY)
 652                         {
 653                                 type = BINARY;
 654                                 byte_data.insert(byte_data.end(), other.byte_data.begin(),
 655                                                  other.byte_data.end());
 656                                 return true;
 657                         }
 658         }
 659         return false;
 660 }
 661
 662 void
 663 property::write_dts(FILE *file, int indent)
 664 {
 665         for (int i=0 ; i<indent ; i++)
 666         {
 667                 putc('\t', file);
 668         }
 669 #ifdef PRINT_LABELS
 670         for (auto &l : labels)
 671         {
 672                 fputs(l.c_str(), file);
 673                 fputs(": ", file);
 674         }
 675 #endif
 676         if (key != string())
 677         {
 678                 fputs(key.c_str(), file);
 679         }
 680         if (!values.empty())
 681         {
 682                 std::vector<property_value> *vals = &values;
 683                 std::vector<property_value> v;
 684                 // If we've got multiple values then try to merge them all together.
 685                 if (values.size() > 1)
 686                 {
 687                         vals = &v;
 688                         v.push_back(values.front());
 689                         for (auto i=(++begin()), e=end() ; i!=e ; ++i)
 690                         {
 691                                 if (!v.back().try_to_merge(*i))
 692                                 {
 693                                         v.push_back(*i);
 694                                 }
 695                         }
 696                 }
 697                 fputs(" = ", file);
 698                 for (auto i=vals->begin(), e=vals->end() ; i!=e ; ++i)
 699                 {
 700                         i->write_dts(file);
 701                         if (i+1 != e)
 702                         {
 703                                 putc(',', file);
 704                                 putc(' ', file);
 705                         }
 706                 }
 707         }
 708         fputs(";\n", file);
 709 }
 710
 711 size_t
 712 property::offset_of_value(property_value &val)
 713 {
 714         size_t off = 0;
 715         for (auto &v : values)
 716         {
 717                 if (&v == &val)
 718                 {
 719                         return off;
 720                 }
 721                 off += v.size();
 722         }
 723         return -1;
 724 }
 725
 726 string
 727 node::parse_name(text_input_buffer &input, bool &is_property, const char *error)
 728 {
 729         if (!valid)
 730         {
 731                 return string();
 732         }
 733         input.next_token();
 734         if (is_property)
 735         {
 736                 return input.parse_property_name();
 737         }
 738         string n = input.parse_node_or_property_name(is_property);
 739         if (n.empty())
 740         {
 741                 if (n.empty())
 742                 {
 743                         input.parse_error(error);
 744                         valid = false;
 745                 }
 746         }
 747         return n;
 748 }
 749
 750 node::visit_behavior
 751 node::visit(std::function<visit_behavior(node&, node*)> fn, node *parent)
 752 {
 753         visit_behavior behavior;
 754         behavior = fn(*this, parent);
 755         if (behavior == VISIT_BREAK)
 756         {
 757                 return VISIT_BREAK;
 758         }
 759         else if (behavior != VISIT_CONTINUE)
 760         {
 761                 for (auto &&c : children)
 762                 {
 763                         behavior = c->visit(fn, this);
 764                         // Any status other than VISIT_RECURSE stops our execution and
 765                         // bubbles up to our caller.  The caller may then either continue
 766                         // visiting nodes that are siblings to this one or completely halt
 767                         // visiting.
 768                         if (behavior != VISIT_RECURSE)
 769                         {
 770                                 return behavior;
 771                         }
 772                 }
 773         }
 774         // Continue recursion by default
 775         return VISIT_RECURSE;
 776 }
 777
 778 node::node(input_buffer &structs, input_buffer &strings) : valid(true)
 779 {
 780         std::vector<char> bytes;
 781         while (structs[0] != '\0' && structs[0] != '@')
 782         {
 783                 bytes.push_back(structs[0]);
 784                 ++structs;
 785         }
 786         name = string(bytes.begin(), bytes.end());
 787         bytes.clear();
 788         if (structs[0] == '@')
 789         {
 790                 ++structs;
 791                 while (structs[0] != '\0')
 792                 {
 793                         bytes.push_back(structs[0]);
 794                         ++structs;
 795                 }
 796                 unit_address = string(bytes.begin(), bytes.end());
 797         }
 798         ++structs;
 799         uint32_t token;
 800         while (structs.consume_binary(token))
 801         {
 802                 switch (token)
 803                 {
 804                         default:
 805                                 fprintf(stderr, "Unexpected token 0x%" PRIx32
 806                                         " while parsing node.\n", token);
 807                                 valid = false;
 808                                 return;
 809                         // Child node, parse it.
 810                         case dtb::FDT_BEGIN_NODE:
 811                         {
 812                                 node_ptr child = node::parse_dtb(structs, strings);
 813                                 if (child == 0)
 814                                 {
 815                                         valid = false;
 816                                         return;
 817                                 }
 818                                 children.push_back(std::move(child));
 819                                 break;
 820                         }
 821                         // End of this node, no errors.
 822                         case dtb::FDT_END_NODE:
 823                                 return;
 824                         // Property, parse it.
 825                         case dtb::FDT_PROP:
 826                         {
 827                                 property_ptr prop = property::parse_dtb(structs, strings);
 828                                 if (prop == 0)
 829                                 {
 830                                         valid = false;
 831                                         return;
 832                                 }
 833                                 props.push_back(prop);
 834                                 break;
 835                         }
 836                                 break;
 837                         // End of structs table.  Should appear after
 838                         // the end of the last node.
 839                         case dtb::FDT_END:
 840                                 fprintf(stderr, "Unexpected FDT_END token while parsing node.\n");
 841                                 valid = false;
 842                                 return;
 843                         // NOPs are padding.  Ignore them.
 844                         case dtb::FDT_NOP:
 845                                 break;
 846                 }
 847         }
 848         fprintf(stderr, "Failed to read token from structs table while parsing node.\n");
 849         valid = false;
 850         return;
 851 }
 852
 853
 854 node::node(const string &n,
 855            const std::vector<property_ptr> &p)
 856         : name(n)
 857 {
 858         props.insert(props.begin(), p.begin(), p.end());
 859 }
 860
 861 node_ptr node::create_special_node(const string &name,
 862                                    const std::vector<property_ptr> &props)
 863 {
 864         // Work around for the fact that we can't call make_shared on something
 865         // with a private constructor.  Instead create a subclass with a public
 866         // constructor that is visible only in this function and construct that
 867         // instead.
 868         struct constructable_node : public node
 869         {
 870                 constructable_node(const string &n, const std::vector<property_ptr> &p) : node(n, p) {}
 871         };
 872         node_ptr n{std::make_shared<constructable_node>(name, props)};
 873         return n;
 874 }
 875
 876 node::node(text_input_buffer &input,
 877            device_tree &tree,
 878            string &&n,
 879            std::unordered_set<string> &&l,
 880            string &&a,
 881            define_map *defines)
 882         : labels(l), name(n), unit_address(a), valid(true)
 883 {
 884         if (!input.consume('{'))
 885         {
 886                 input.parse_error("Expected { to start new device tree node.\n");
 887         }
 888         input.next_token();
 889         while (valid && !input.consume('}'))
 890         {
 891                 // flag set if we find any characters that are only in
 892                 // the property name character set, not the node
 893                 bool is_property = false;
 894                 // flag set if our node is marked as /omit-if-no-ref/ to be
 895                 // garbage collected later if nothing references it
 896                 bool marked_omit_if_no_ref = false;
 897                 string child_name, child_address;
 898                 std::unordered_set<string> child_labels;
 899                 auto parse_delete = [&](const char *expected, bool at)
 900                 {
 901                         if (child_name == string())
 902                         {
 903                                 input.parse_error(expected);
 904                                 valid = false;
 905                                 return;
 906                         }
 907                         input.next_token();
 908                         if (at && input.consume('@'))
 909                         {
 910                                 child_name += '@';
 911                                 child_name += parse_name(input, is_property, "Expected unit address");
 912                         }
 913                         if (!input.consume(';'))
 914                         {
 915                                 input.parse_error("Expected semicolon");
 916                                 valid = false;
 917                                 return;
 918                         }
 919                         input.next_token();
 920                 };
 921                 if (input.consume("/delete-node/"))
 922                 {
 923                         input.next_token();
 924                         child_name = input.parse_node_name();
 925                         parse_delete("Expected node name", true);
 926                         if (valid)
 927                         {
 928                                 deleted_children.insert(child_name);
 929                         }
 930                         continue;
 931                 }
 932                 if (input.consume("/delete-property/"))
 933                 {
 934                         input.next_token();
 935                         child_name = input.parse_property_name();
 936                         parse_delete("Expected property name", false);
 937                         if (valid)
 938                         {
 939                                 deleted_props.insert(child_name);
 940                         }
 941                         continue;
 942                 }
 943                 if (input.consume("/omit-if-no-ref/"))
 944                 {
 945                         input.next_token();
 946                         marked_omit_if_no_ref = true;
 947                         tree.set_needs_garbage_collection();
 948                 }
 949                 child_name = parse_name(input, is_property,
 950                                 "Expected property or node name");
 951                 while (input.consume(':'))
 952                 {
 953                         // Node labels can contain any characters?  The
 954                         // spec doesn't say, so we guess so...
 955                         is_property = false;
 956                         child_labels.insert(std::move(child_name));
 957                         child_name = parse_name(input, is_property, "Expected property or node name");
 958                 }
 959                 if (input.consume('@'))
 960                 {
 961                         child_address = parse_name(input, is_property, "Expected unit address");
 962                 }
 963                 if (!valid)
 964                 {
 965                         return;
 966                 }
 967                 input.next_token();
 968                 // If we're parsing a property, then we must actually do that.
 969                 if (input.consume('='))
 970                 {
 971                         property_ptr p = property::parse(input, std::move(child_name),
 972                                         std::move(child_labels), true, defines);
 973                         if (p == 0)
 974                         {
 975                                 valid = false;
 976                         }
 977                         else
 978                         {
 979                                 props.push_back(p);
 980                         }
 981                 }
 982                 else if (!is_property && *input == ('{'))
 983                 {
 984                         node_ptr child = node::parse(input, tree, std::move(child_name),
 985                                         std::move(child_labels), std::move(child_address), defines);
 986                         if (child)
 987                         {
 988                                 child->omit_if_no_ref = marked_omit_if_no_ref;
 989                                 children.push_back(std::move(child));
 990                         }
 991                         else
 992                         {
 993                                 valid = false;
 994                         }
 995                 }
 996                 else if (input.consume(';'))
 997                 {
 998                         props.push_back(property_ptr(new property(std::move(child_name), std::move(child_labels))));
 999                 }
1000                 else
1001                 {
1002                         input.parse_error("Error parsing property.  Expected property value");
1003                         valid = false;
1004                 }
1005                 input.next_token();
1006         }
1007         input.next_token();
1008         input.consume(';');
1009 }
1010
1011 bool
1012 node::cmp_properties(property_ptr &p1, property_ptr &p2)
1013 {
1014         return p1->get_key() < p2->get_key();
1015 }
1016
1017 bool
1018 node::cmp_children(node_ptr &c1, node_ptr &c2)
1019 {
1020         if (c1->name == c2->name)
1021         {
1022                 return c1->unit_address < c2->unit_address;
1023         }
1024         return c1->name < c2->name;
1025 }
1026
1027 void
1028 node::sort()
1029 {
1030         std::sort(property_begin(), property_end(), cmp_properties);
1031         std::sort(child_begin(), child_end(), cmp_children);
1032         for (auto &c : child_nodes())
1033         {
1034                 c->sort();
1035         }
1036 }
1037
1038 node_ptr
1039 node::parse(text_input_buffer &input,
1040             device_tree &tree,
1041             string &&name,
1042             string_set &&label,
1043             string &&address,
1044             define_map *defines)
1045 {
1046         // Work around for the fact that we can't call make_shared on something
1047         // with a private constructor.  Instead create a subclass with a public
1048         // constructor that is visible only in this function and construct that
1049         // instead.
1050         struct constructable_node : public node
1051         {
1052                 constructable_node(text_input_buffer &input,
1053                                device_tree &tree,
1054                                std::string &&n,
1055                                std::unordered_set<std::string> &&l,
1056                                std::string &&a,
1057                                define_map*m) : node(input,
1058                                                     tree,
1059                                                     std::move(n),
1060                                                     std::move(l),
1061                                                     std::move(a),
1062                                                     m)
1063                 {}
1064         };
1065         node_ptr n{std::make_shared<constructable_node>(input,
1066                                                         tree,
1067                                                         std::move(name),
1068                                                         std::move(label),
1069                                                         std::move(address),
1070                                                         defines)};
1071         if (!n->valid)
1072         {
1073                 n = 0;
1074         }
1075         return n;
1076 }
1077
1078 node_ptr
1079 node::parse_dtb(input_buffer &structs, input_buffer &strings)
1080 {
1081         node_ptr n(new node(structs, strings));
1082         if (!n->valid)
1083         {
1084                 n = 0;
1085         }
1086         return n;
1087 }
1088
1089 property_ptr
1090 node::get_property(const string &key)
1091 {
1092         for (auto &i : props)
1093         {
1094                 if (i->get_key() == key)
1095                 {
1096                         return i;
1097                 }
1098         }
1099         return 0;
1100 }
1101
1102 void
1103 node::merge_node(node_ptr &other)
1104 {
1105         for (auto &l : other->labels)
1106         {
1107                 labels.insert(l);
1108         }
1109         children.erase(std::remove_if(children.begin(), children.end(),
1110                         [&](const node_ptr &p) {
1111                                 string full_name = p->name;
1112                                 if (p->unit_address != string())
1113                                 {
1114                                         full_name += '@';
1115                                         full_name += p->unit_address;
1116                                 }
1117                                 if (other->deleted_children.count(full_name) > 0)
1118                                 {
1119                                         other->deleted_children.erase(full_name);
1120                                         return true;
1121                                 }
1122                                 return false;
1123                         }), children.end());
1124         props.erase(std::remove_if(props.begin(), props.end(),
1125                         [&](const property_ptr &p) {
1126                                 if (other->deleted_props.count(p->get_key()) > 0)
1127                                 {
1128                                         other->deleted_props.erase(p->get_key());
1129                                         return true;
1130                                 }
1131                                 return false;
1132                         }), props.end());
1133         // Note: this is an O(n*m) operation.  It might be sensible to
1134         // optimise this if we find that there are nodes with very
1135         // large numbers of properties, but for typical usage the
1136         // entire vector will fit (easily) into cache, so iterating
1137         // over it repeatedly isn't that expensive.
1138         for (auto &p : other->properties())
1139         {
1140                 bool found = false;
1141                 for (auto &mp : properties())
1142                 {
1143                         if (mp->get_key() == p->get_key())
1144                         {
1145                                 mp = p;
1146                                 found = true;
1147                                 break;
1148                         }
1149                 }
1150                 if (!found)
1151                 {
1152                         add_property(p);
1153                 }
1154         }
1155         for (auto &c : other->children)
1156         {
1157                 bool found = false;
1158                 for (auto &i : children)
1159                 {
1160                         if (i->name == c->name && i->unit_address == c->unit_address)
1161                         {
1162                                 i->merge_node(c);
1163                                 found = true;
1164                                 break;
1165                         }
1166                 }
1167                 if (!found)
1168                 {
1169                         children.push_back(std::move(c));
1170                 }
1171         }
1172 }
1173
1174 void
1175 node::write(dtb::output_writer &writer, dtb::string_table &strings)
1176 {
1177         writer.write_token(dtb::FDT_BEGIN_NODE);
1178         byte_buffer name_buffer;
1179         push_string(name_buffer, name);
1180         if (unit_address != string())
1181         {
1182                 name_buffer.push_back('@');
1183                 push_string(name_buffer, unit_address);
1184         }
1185         writer.write_comment(name);
1186         writer.write_data(name_buffer);
1187         writer.write_data((uint8_t)0);
1188         for (auto p : properties())
1189         {
1190                 p->write(writer, strings);
1191         }
1192         for (auto &c : child_nodes())
1193         {
1194                 c->write(writer, strings);
1195         }
1196         writer.write_token(dtb::FDT_END_NODE);
1197 }
1198
1199 void
1200 node::write_dts(FILE *file, int indent)
1201 {
1202         for (int i=0 ; i<indent ; i++)
1203         {
1204                 putc('\t', file);
1205         }
1206 #ifdef PRINT_LABELS
1207         for (auto &label : labels)
1208         {
1209                 fprintf(file, "%s: ", label.c_str());
1210         }
1211 #endif
1212         if (name != string())
1213         {
1214                 fputs(name.c_str(), file);
1215         }
1216         if (unit_address != string())
1217         {
1218                 putc('@', file);
1219                 fputs(unit_address.c_str(), file);
1220         }
1221         fputs(" {\n\n", file);
1222         for (auto p : properties())
1223         {
1224                 p->write_dts(file, indent+1);
1225         }
1226         for (auto &c : child_nodes())
1227         {
1228                 c->write_dts(file, indent+1);
1229         }
1230         for (int i=0 ; i<indent ; i++)
1231         {
1232                 putc('\t', file);
1233         }
1234         fputs("};\n", file);
1235 }
1236
1237 void
1238 device_tree::collect_names_recursive(node_ptr parent, node_ptr n, node_path &path)
1239 {
1240         path.push_back(std::make_pair(n->name, n->unit_address));
1241         for (const string &name : n->labels)
1242         {
1243                 if (name != string())
1244                 {
1245                         auto iter = node_names.find(name);
1246                         if (iter == node_names.end())
1247                         {
1248                                 node_names.insert(std::make_pair(name, n));
1249                                 node_paths.insert(std::make_pair(name, path));
1250                                 ordered_node_paths.push_back({name, path});
1251                                 if (parent)
1252                                 {
1253                                         node_name_parents.insert({name, parent});
1254                                 }
1255                         }
1256                         else
1257                         {
1258                                 node_names.erase(iter);
1259                                 auto i = node_paths.find(name);
1260                                 if (i != node_paths.end())
1261                                 {
1262                                         node_paths.erase(name);
1263                                 }
1264                                 fprintf(stderr, "Label not unique: %s.  References to this label will not be resolved.\n", name.c_str());
1265                         }
1266                 }
1267         }
1268         for (auto &c : n->child_nodes())
1269         {
1270                 collect_names_recursive(n, c, path);
1271         }
1272         // Now we collect the phandles and properties that reference
1273         // other nodes.
1274         for (auto &p : n->properties())
1275         {
1276                 for (auto &v : *p)
1277                 {
1278                         if (v.is_phandle())
1279                         {
1280                                 fixups.push_back({path, p, v});
1281                         }
1282                         if (v.is_cross_reference())
1283                         {
1284                                 cross_references.push_back(&v);
1285                         }
1286                 }
1287                 if ((p->get_key() == "phandle") ||
1288                     (p->get_key() == "linux,phandle"))
1289                 {
1290                         if (p->begin()->byte_data.size() != 4)
1291                         {
1292                                 fprintf(stderr, "Invalid phandle value for node %s.  Should be a 4-byte value.\n", n->name.c_str());
1293                                 valid = false;
1294                         }
1295                         else
1296                         {
1297                                 uint32_t phandle = p->begin()->get_as_uint32();
1298                                 used_phandles.insert(std::make_pair(phandle, n));
1299                         }
1300                 }
1301         }
1302         path.pop_back();
1303 }
1304
1305 void
1306 device_tree::collect_names()
1307 {
1308         node_path p;
1309         node_names.clear();
1310         node_paths.clear();
1311         ordered_node_paths.clear();
1312         cross_references.clear();
1313         fixups.clear();
1314         collect_names_recursive(nullptr, root, p);
1315 }
1316
1317 property_ptr
1318 device_tree::assign_phandle(node_ptr n, uint32_t &phandle)
1319 {
1320         // If there is an existing phandle, use it
1321         property_ptr p = n->get_property("phandle");
1322         if (p == 0)
1323         {
1324                 p = n->get_property("linux,phandle");
1325         }
1326         if (p == 0)
1327         {
1328                 // Otherwise insert a new phandle node
1329                 property_value v;
1330                 while (used_phandles.find(phandle) != used_phandles.end())
1331                 {
1332                         // Note that we only don't need to
1333                         // store this phandle in the set,
1334                         // because we are monotonically
1335                         // increasing the value of phandle and
1336                         // so will only ever revisit this value
1337                         // if we have used 2^32 phandles, at
1338                         // which point our blob won't fit in
1339                         // any 32-bit system and we've done
1340                         // something badly wrong elsewhere
1341                         // already.
1342                         phandle++;
1343                 }
1344                 push_big_endian(v.byte_data, phandle++);
1345                 if (phandle_node_name == BOTH || phandle_node_name == LINUX)
1346                 {
1347                         p.reset(new property("linux,phandle"));
1348                         p->add_value(v);
1349                         n->add_property(p);
1350                 }
1351                 if (phandle_node_name == BOTH || phandle_node_name == EPAPR)
1352                 {
1353                         p.reset(new property("phandle"));
1354                         p->add_value(v);
1355                         n->add_property(p);
1356                 }
1357         }
1358
1359         return (p);
1360 }
1361
1362 void
1363 device_tree::assign_phandles(node_ptr n, uint32_t &next)
1364 {
1365         if (!n->labels.empty())
1366         {
1367                 assign_phandle(n, next);
1368         }
1369
1370         for (auto &c : n->child_nodes())
1371         {
1372                 assign_phandles(c, next);
1373         }
1374 }
1375
1376 void
1377 device_tree::resolve_cross_references(uint32_t &phandle)
1378 {
1379         for (auto *pv : cross_references)
1380         {
1381                 node_path path = node_paths[pv->string_data];
1382                 auto p = path.begin();
1383                 auto pe = path.end();
1384                 if (p != pe)
1385                 {
1386                         // Skip the first name in the path.  It's always "", and implicitly /
1387                         for (++p ; p!=pe ; ++p)
1388                         {
1389                                 pv->byte_data.push_back('/');
1390                                 push_string(pv->byte_data, p->first);
1391                                 if (!(p->second.empty()))
1392                                 {
1393                                         pv->byte_data.push_back('@');
1394                                         push_string(pv->byte_data, p->second);
1395                                 }
1396                         }
1397                         pv->byte_data.push_back(0);
1398                 }
1399         }
1400         std::unordered_map<property_value*, fixup&> phandle_set;
1401         for (auto &i : fixups)
1402         {
1403                 phandle_set.insert({&i.val, i});
1404         }
1405         std::vector<std::reference_wrapper<fixup>> sorted_phandles;
1406         root->visit([&](node &n, node *) {
1407                 for (auto &p : n.properties())
1408                 {
1409                         for (auto &v : *p)
1410                         {
1411                                 auto i = phandle_set.find(&v);
1412                                 if (i != phandle_set.end())
1413                                 {
1414                                         sorted_phandles.push_back(i->second);
1415                                 }
1416                         }
1417                 }
1418                 // Allow recursion
1419                 return node::VISIT_RECURSE;
1420         }, nullptr);
1421         assert(sorted_phandles.size() == fixups.size());
1422         for (auto &i : sorted_phandles)
1423         {
1424                 string target_name = i.get().val.string_data;
1425                 node_ptr target;
1426                 string possible;
1427                 // If the node name is a path, then look it up by following the path,
1428                 // otherwise jump directly to the named node.
1429                 if (target_name[0] == '/')
1430                 {
1431                         string path;
1432                         target = root;
1433                         std::istringstream ss(target_name);
1434                         string path_element;
1435                         // Read the leading /
1436                         std::getline(ss, path_element, '/');
1437                         // Iterate over path elements
1438                         while (!ss.eof())
1439                         {
1440                                 path += '/';
1441                                 std::getline(ss, path_element, '/');
1442                                 std::istringstream nss(path_element);
1443                                 string node_name, node_address;
1444                                 std::getline(nss, node_name, '@');
1445                                 std::getline(nss, node_address, '@');
1446                                 node_ptr next;
1447                                 for (auto &c : target->child_nodes())
1448                                 {
1449                                         if (c->name == node_name)
1450                                         {
1451                                                 if (c->unit_address == node_address)
1452                                                 {
1453                                                         next = c;
1454                                                         break;
1455                                                 }
1456                                                 else
1457                                                 {
1458                                                         possible = path + c->name;
1459                                                         if (c->unit_address != string())
1460                                                         {
1461                                                                 possible += '@';
1462                                                                 possible += c->unit_address;
1463                                                         }
1464                                                 }
1465                                         }
1466                                 }
1467                                 path += node_name;
1468                                 if (node_address != string())
1469                                 {
1470                                         path += '@';
1471                                         path += node_address;
1472                                 }
1473                                 target = next;
1474                                 if (target == nullptr)
1475                                 {
1476                                         break;
1477                                 }
1478                         }
1479                 }
1480                 else
1481                 {
1482                         target = node_names[target_name];
1483                 }
1484                 if (target == nullptr)
1485                 {
1486                         if (is_plugin)
1487                         {
1488                                 unresolved_fixups.push_back(i);
1489                                 continue;
1490                         }
1491                         else
1492                         {
1493                                 fprintf(stderr, "Failed to find node with label: %s\n", target_name.c_str());
1494                                 if (possible != string())
1495                                 {
1496                                         fprintf(stderr, "Possible intended match: %s\n", possible.c_str());
1497                                 }
1498                                 valid = 0;
1499                                 return;
1500                         }
1501                 }
1502                 // If there is an existing phandle, use it
1503                 property_ptr p = assign_phandle(target, phandle);
1504                 p->begin()->push_to_buffer(i.get().val.byte_data);
1505                 assert(i.get().val.byte_data.size() == 4);
1506         }
1507 }
1508
1509 bool
1510 device_tree::garbage_collect_marked_nodes()
1511 {
1512         std::unordered_set<node_ptr> previously_referenced_nodes;
1513         std::unordered_set<node_ptr> newly_referenced_nodes;
1514
1515         auto mark_referenced_nodes_used = [&](node &n)
1516         {
1517                 for (auto &p : n.properties())
1518                 {
1519                         for (auto &v : *p)
1520                         {
1521                                 if (v.is_phandle())
1522                                 {
1523                                         node_ptr nx = node_names[v.string_data];
1524                                         if (nx == nullptr)
1525                                         {
1526                                                 // Try it again, but as a path
1527                                                 for (auto &s : node_paths)
1528                                                 {
1529                                                         if (v.string_data == s.second.to_string())
1530                                                         {
1531                                                                 nx = node_names[s.first];
1532                                                                 break;
1533                                                         }
1534                                                 }
1535                                         }
1536                                         if (nx == nullptr)
1537                                         {
1538                                                 // Couldn't resolve this one?
1539                                                 continue;
1540                                         }
1541                                         // Only mark those currently unmarked
1542                                         if (!nx->used)
1543                                         {
1544                                                         nx->used = 1;
1545                                                         newly_referenced_nodes.insert(nx);
1546                                         }
1547                                 }
1548                         }
1549                 }
1550         };
1551
1552         // Seed our referenced nodes with those that have been seen by a node that
1553         // either will not be omitted if it's unreferenced or has a symbol.
1554         // Nodes with symbols are explicitly not garbage collected because they may
1555         // be expected for referencing by an overlay, and we do not want surprises
1556         // there.
1557         root->visit([&](node &n, node *) {
1558                 if (!n.omit_if_no_ref || (write_symbols && !n.labels.empty()))
1559                 {
1560                         mark_referenced_nodes_used(n);
1561                 }
1562                 // Recurse as normal
1563                 return node::VISIT_RECURSE;
1564         }, nullptr);
1565
1566         while (!newly_referenced_nodes.empty())
1567         {
1568                         previously_referenced_nodes = newly_referenced_nodes;
1569                         newly_referenced_nodes.clear();
1570                         for (auto &n : previously_referenced_nodes)
1571                         {
1572                                 mark_referenced_nodes_used(*n);
1573                         }
1574         }
1575
1576         previously_referenced_nodes.clear();
1577         bool children_deleted = false;
1578
1579         // Delete
1580         root->visit([&](node &n, node *) {
1581                 bool gc_children = false;
1582
1583                 for (auto &cn : n.child_nodes())
1584                 {
1585                                 if (cn->omit_if_no_ref && !cn->used)
1586                                 {
1587                                         gc_children = true;
1588                                         break;
1589                                 }
1590                 }
1591
1592                 if (gc_children)
1593                 {
1594                         children_deleted = true;
1595                         n.delete_children_if([](node_ptr &nx) {
1596                                 return (nx->omit_if_no_ref && !nx->used);
1597                         });
1598
1599                         return node::VISIT_CONTINUE;
1600                 }
1601
1602                 return node::VISIT_RECURSE;
1603         }, nullptr);
1604
1605         return children_deleted;
1606 }
1607
1608 void
1609 device_tree::parse_file(text_input_buffer &input,
1610                         std::vector<node_ptr> &roots,
1611                         bool &read_header)
1612 {
1613         input.next_token();
1614         // Read the header
1615         while (input.consume("/dts-v1/;"))
1616         {
1617                 read_header = true;
1618                 input.next_token();
1619         }
1620         if (input.consume("/plugin/;"))
1621         {
1622                 is_plugin = true;
1623         }
1624         input.next_token();
1625         if (!read_header)
1626         {
1627                 input.parse_error("Expected /dts-v1/; version string");
1628         }
1629         // Read any memory reservations
1630         while (input.consume("/memreserve/"))
1631         {
1632                 unsigned long long start, len;
1633                 input.next_token();
1634                 // Read the start and length.
1635                 if (!(input.consume_integer_expression(start) &&
1636                     (input.next_token(),
1637                     input.consume_integer_expression(len))))
1638                 {
1639                         input.parse_error("Expected size on /memreserve/ node.");
1640                 }
1641                 else
1642                 {
1643                         reservations.push_back(reservation(start, len));
1644                 }
1645                 input.next_token();
1646                 input.consume(';');
1647                 input.next_token();
1648         }
1649         while (valid && !input.finished())
1650         {
1651                 node_ptr n;
1652                 if (input.consume("/delete-node/"))
1653                 {
1654                         // Top-level /delete-node/ directives refer to references that must
1655                         // be deleted later.
1656                         input.next_token();
1657                         auto expect = [&](auto token, const char *msg)
1658                         {
1659                                 if (!input.consume(token))
1660                                 {
1661                                         input.parse_error(msg);
1662                                         valid = false;
1663                                 }
1664                                 input.next_token();
1665                                 return valid;
1666                         };
1667                         if (expect('&', "Expected reference after top-level /delete-node/."))
1668                         {
1669                                 string ref = input.parse_node_name();
1670                                 if (ref == string())
1671                                 {
1672                                         input.parse_error("Expected label name for top-level /delete-node/.");
1673                                         valid = false;
1674                                 }
1675                                 else
1676                                 {
1677                                         deletions.push_back(std::move(ref));
1678                                 }
1679                                 expect(';', "Missing semicolon.");
1680                         }
1681                         continue;
1682                 }
1683                 else if (input.consume('/'))
1684                 {
1685                         input.next_token();
1686                         n = node::parse(input, *this, string(), string_set(), string(), &defines);
1687                 }
1688                 else if (input.consume('&'))
1689                 {
1690                         input.next_token();
1691                         string name;
1692                         bool name_is_path_reference = false;
1693                         // This is to deal with names intended as path references, e.g. &{/path}.
1694                         // While it may make sense in a non-plugin context, we don't support such
1695                         // usage at this time.
1696                         if (input.consume('{') && is_plugin)
1697                         {
1698                                 name = input.parse_to('}');
1699                                 input.consume('}');
1700                                 name_is_path_reference = true;
1701                         }
1702                         else
1703                         {
1704                                 name = input.parse_node_name();
1705                         }
1706                         input.next_token();
1707                         n = node::parse(input, *this, std::move(name), string_set(), string(), &defines);
1708                         if (n)
1709                         {
1710                                 n->name_is_path_reference = name_is_path_reference;
1711                         }
1712                 }
1713                 else
1714                 {
1715                         input.parse_error("Failed to find root node /.");
1716                 }
1717                 if (n)
1718                 {
1719                         roots.push_back(std::move(n));
1720                 }
1721                 else
1722                 {
1723                         valid = false;
1724                 }
1725                 input.next_token();
1726         }
1727 }
1728
1729 template<class writer> void
1730 device_tree::write(int fd)
1731 {
1732         dtb::string_table st;
1733         dtb::header head;
1734         writer head_writer;
1735         writer reservation_writer;
1736         writer struct_writer;
1737         writer strings_writer;
1738
1739         // Build the reservation table
1740         reservation_writer.write_comment(string("Memory reservations"));
1741         reservation_writer.write_label(string("dt_reserve_map"));
1742         for (auto &i : reservations)
1743         {
1744                 reservation_writer.write_comment(string("Reservation start"));
1745                 reservation_writer.write_data(i.first);
1746                 reservation_writer.write_comment(string("Reservation length"));
1747                 reservation_writer.write_data(i.second);
1748         }
1749         // Write n spare reserve map entries, plus the trailing 0.
1750         for (uint32_t i=0 ; i<=spare_reserve_map_entries ; i++)
1751         {
1752                 reservation_writer.write_data((uint64_t)0);
1753                 reservation_writer.write_data((uint64_t)0);
1754         }
1755
1756
1757         struct_writer.write_comment(string("Device tree"));
1758         struct_writer.write_label(string("dt_struct_start"));
1759         root->write(struct_writer, st);
1760         struct_writer.write_token(dtb::FDT_END);
1761         struct_writer.write_label(string("dt_struct_end"));
1762
1763         st.write(strings_writer);
1764         // Find the strings size before we stick padding on the end.
1765         // Note: We should possibly use a new writer for the padding.
1766         head.size_dt_strings = strings_writer.size();
1767
1768         // Stick the padding in the strings writer, but after the
1769         // marker indicating that it's the end.
1770         // Note: We probably should add a padding call to the writer so
1771         // that the asm back end can write padding directives instead
1772         // of a load of 0 bytes.
1773         for (uint32_t i=0 ; i<blob_padding ; i++)
1774         {
1775                 strings_writer.write_data((uint8_t)0);
1776         }
1777         head.totalsize = sizeof(head) + strings_writer.size() +
1778                 struct_writer.size() + reservation_writer.size();
1779         while (head.totalsize < minimum_blob_size)
1780         {
1781                 head.totalsize++;
1782                 strings_writer.write_data((uint8_t)0);
1783         }
1784         head.off_dt_struct = sizeof(head) + reservation_writer.size();;
1785         head.off_dt_strings = head.off_dt_struct + struct_writer.size();
1786         head.off_mem_rsvmap = sizeof(head);
1787         head.boot_cpuid_phys = boot_cpu;
1788         head.size_dt_struct = struct_writer.size();
1789         head.write(head_writer);
1790
1791         head_writer.write_to_file(fd);
1792         reservation_writer.write_to_file(fd);
1793         struct_writer.write_to_file(fd);
1794         strings_writer.write_label(string("dt_blob_end"));
1795         strings_writer.write_to_file(fd);
1796 }
1797
1798 node_ptr
1799 device_tree::referenced_node(property_value &v)
1800 {
1801         if (v.is_phandle())
1802         {
1803                 return node_names[v.string_data];
1804         }
1805         if (v.is_binary())
1806         {
1807                 return used_phandles[v.get_as_uint32()];
1808         }
1809         return 0;
1810 }
1811
1812 void
1813 device_tree::write_binary(int fd)
1814 {
1815         write<dtb::binary_writer>(fd);
1816 }
1817
1818 void
1819 device_tree::write_asm(int fd)
1820 {
1821         write<dtb::asm_writer>(fd);
1822 }
1823
1824 void
1825 device_tree::write_dts(int fd)
1826 {
1827         FILE *file = fdopen(fd, "w");
1828         fputs("/dts-v1/;\n\n", file);
1829
1830         if (!reservations.empty())
1831         {
1832                 const char msg[] = "/memreserve/";
1833                 // Exclude the null byte when we're writing it out to the file.
1834                 fwrite(msg, sizeof(msg) - 1, 1, file);
1835                 for (auto &i : reservations)
1836                 {
1837                         fprintf(file, " 0x%" PRIx64 " 0x%" PRIx64, i.first, i.second);
1838                 }
1839                 fputs(";\n\n", file);
1840         }
1841         putc('/', file);
1842         putc(' ', file);
1843         root->write_dts(file, 0);
1844         fclose(file);
1845 }
1846
1847 void
1848 device_tree::parse_dtb(const string &fn, FILE *)
1849 {
1850         auto in = input_buffer::buffer_for_file(fn);
1851         if (in == 0)
1852         {
1853                 valid = false;
1854                 return;
1855         }
1856         input_buffer &input = *in;
1857         dtb::header h;
1858         valid = h.read_dtb(input);
1859         boot_cpu = h.boot_cpuid_phys;
1860         if (h.last_comp_version > 17)
1861         {
1862                 fprintf(stderr, "Don't know how to read this version of the device tree blob");
1863                 valid = false;
1864         }
1865         if (!valid)
1866         {
1867                 return;
1868         }
1869         input_buffer reservation_map =
1870                 input.buffer_from_offset(h.off_mem_rsvmap, 0);
1871         uint64_t start, length;
1872         do
1873         {
1874                 if (!(reservation_map.consume_binary(start) &&
1875                       reservation_map.consume_binary(length)))
1876                 {
1877                         fprintf(stderr, "Failed to read memory reservation table\n");
1878                         valid = false;
1879                         return;
1880                 }
1881                 if (start != 0 || length != 0)
1882                 {
1883                         reservations.push_back(reservation(start, length));
1884                 }
1885         } while (!((start == 0) && (length == 0)));
1886         input_buffer struct_table =
1887                 input.buffer_from_offset(h.off_dt_struct, h.size_dt_struct);
1888         input_buffer strings_table =
1889                 input.buffer_from_offset(h.off_dt_strings, h.size_dt_strings);
1890         uint32_t token;
1891         if (!(struct_table.consume_binary(token) &&
1892                 (token == dtb::FDT_BEGIN_NODE)))
1893         {
1894                 fprintf(stderr, "Expected FDT_BEGIN_NODE token.\n");
1895                 valid = false;
1896                 return;
1897         }
1898         root = node::parse_dtb(struct_table, strings_table);
1899         if (!(struct_table.consume_binary(token) && (token == dtb::FDT_END)))
1900         {
1901                 fprintf(stderr, "Expected FDT_END token after parsing root node.\n");
1902                 valid = false;
1903                 return;
1904         }
1905         valid = (root != 0);
1906 }
1907
1908 string
1909 device_tree::node_path::to_string() const
1910 {
1911         string path;
1912         auto p = begin();
1913         auto pe = end();
1914         if ((p == pe) || (p+1 == pe))
1915         {
1916                 return string("/");
1917         }
1918         // Skip the first name in the path.  It's always "", and implicitly /
1919         for (++p ; p!=pe ; ++p)
1920         {
1921                 path += '/';
1922                 path += p->first;
1923                 if (!(p->second.empty()))
1924                 {
1925                         path += '@';
1926                         path += p->second;
1927                 }
1928         }
1929         return path;
1930 }
1931
1932 node_ptr
1933 device_tree::create_fragment_wrapper(node_ptr &node, int &fragnum)
1934 {
1935         // In a plugin, we can massage these non-/ root nodes into into a fragment
1936         std::string fragment_address = "fragment@" + std::to_string(fragnum);
1937         ++fragnum;
1938
1939         std::vector<property_ptr> symbols;
1940
1941         // Intentionally left empty
1942         node_ptr newroot = node::create_special_node("", symbols);
1943         node_ptr wrapper = node::create_special_node("__overlay__", symbols);
1944
1945         // Generate the fragment with $propname = <&name>
1946         property_value v;
1947         std::string propname;
1948         v.string_data = node->name;
1949         if (!node->name_is_path_reference)
1950         {
1951                 propname = "target";
1952                 v.type = property_value::PHANDLE;
1953         }
1954         else
1955         {
1956                 propname = "target-path";
1957                 v.type = property_value::STRING;
1958         }
1959         auto prop = std::make_shared<property>(std::string(propname));
1960         prop->add_value(v);
1961         symbols.push_back(prop);
1962
1963         node_ptr fragment = node::create_special_node(fragment_address, symbols);
1964
1965         wrapper->merge_node(node);
1966         fragment->add_child(std::move(wrapper));
1967         newroot->add_child(std::move(fragment));
1968         return newroot;
1969 }
1970
1971 node_ptr
1972 device_tree::generate_root(node_ptr &node, int &fragnum)
1973 {
1974
1975         string name = node->name;
1976         if (name == string())
1977         {
1978                 return std::move(node);
1979         }
1980         else if (!is_plugin)
1981         {
1982                 return nullptr;
1983         }
1984
1985         return create_fragment_wrapper(node, fragnum);
1986 }
1987
1988 void
1989 device_tree::reassign_fragment_numbers(node_ptr &node, int &delta)
1990 {
1991
1992         for (auto &c : node->child_nodes())
1993         {
1994                 if (c->name == std::string("fragment"))
1995                 {
1996                         int current_address = std::stoi(c->unit_address, nullptr, 16);
1997                         std::ostringstream new_address;
1998                         current_address += delta;
1999                         // It's possible that we hopped more than one somewhere, so just reset
2000                         // delta to the next in sequence.
2001                         delta = current_address + 1;
2002                         new_address << std::hex << current_address;
2003                         c->unit_address = new_address.str();
2004                 }
2005         }
2006 }
2007
2008 void
2009 device_tree::parse_dts(const string &fn, FILE *depfile)
2010 {
2011         auto in = input_buffer::buffer_for_file(fn);
2012         if (!in)
2013         {
2014                 valid = false;
2015                 return;
2016         }
2017         std::vector<node_ptr> roots;
2018         std::unordered_set<string> defnames;
2019         for (auto &i : defines)
2020         {
2021                 defnames.insert(i.first);
2022         }
2023         text_input_buffer input(std::move(in),
2024                                 std::move(defnames),
2025                                 std::vector<string>(include_paths),
2026                                 dirname(fn),
2027                                 depfile);
2028         bool read_header = false;
2029         int fragnum = 0;
2030         parse_file(input, roots, read_header);
2031         switch (roots.size())
2032         {
2033                 case 0:
2034                         valid = false;
2035                         input.parse_error("Failed to find root node /.");
2036                         return;
2037                 case 1:
2038                         root = generate_root(roots[0], fragnum);
2039                         if (!root)
2040                         {
2041                                 valid = false;
2042                                 input.parse_error("Failed to find root node /.");
2043                                 return;
2044                         }
2045                         break;
2046                 default:
2047                 {
2048                         root = generate_root(roots[0], fragnum);
2049                         if (!root)
2050                         {
2051                                 valid = false;
2052                                 input.parse_error("Failed to find root node /.");
2053                                 return;
2054                         }
2055                         for (auto i=++(roots.begin()), e=roots.end() ; i!=e ; ++i)
2056                         {
2057                                 auto &node = *i;
2058                                 string name = node->name;
2059                                 if (name == string())
2060                                 {
2061                                         if (is_plugin)
2062                                         {
2063                                                 // Re-assign any fragment numbers based on a delta of
2064                                                 // fragnum before we merge it
2065                                                 reassign_fragment_numbers(node, fragnum);
2066                                         }
2067                                         root->merge_node(node);
2068                                 }
2069                                 else
2070                                 {
2071                                         auto existing = node_names.find(name);
2072                                         if (existing == node_names.end())
2073                                         {
2074                                                 collect_names();
2075                                                 existing = node_names.find(name);
2076                                         }
2077                                         if (existing == node_names.end())
2078                                         {
2079                                                 if (is_plugin)
2080                                                 {
2081                                                         auto fragment = create_fragment_wrapper(node, fragnum);
2082                                                         root->merge_node(fragment);
2083                                                 }
2084                                                 else
2085                                                 {
2086                                                         fprintf(stderr, "Unable to merge node: %s\n", name.c_str());
2087                                                 }
2088                                         }
2089                                         else
2090                                         {
2091                                                 existing->second->merge_node(node);
2092                                         }
2093                                 }
2094                         }
2095                 }
2096         }
2097         collect_names();
2098         for (auto &ref : deletions)
2099         {
2100                 auto parent = node_name_parents[ref];
2101                 auto node = node_names[ref];
2102                 if (!parent)
2103                 {
2104                         fprintf(stderr, "Top-level /delete-node/ directive refers to label %s, which is not found.\n", ref.c_str());
2105                 }
2106                 else
2107                 {
2108                         parent->delete_children_if([&](node_ptr &child) { return child == node; });
2109                 }
2110         }
2111         // Return value indicates whether we've dirtied the tree or not and need to
2112         // recollect names
2113         if (garbage_collect && garbage_collect_marked_nodes())
2114         {
2115                 collect_names();
2116         }
2117         uint32_t phandle = 1;
2118         // If we're writing symbols, go ahead and assign phandles to the entire
2119         // tree. We'll do this before we resolve cross references, just to keep
2120         // order semi-predictable and stable.
2121         if (write_symbols)
2122         {
2123                 assign_phandles(root, phandle);
2124         }
2125         resolve_cross_references(phandle);
2126         if (write_symbols)
2127         {
2128                 std::vector<property_ptr> symbols;
2129                 // Create a symbol table.  Each label  in this device tree may be
2130                 // referenced by other plugins, so we create a __symbols__ node inside
2131                 // the root that contains mappings (properties) from label names to
2132                 // paths.
2133                 for (auto i=ordered_node_paths.rbegin(), e=ordered_node_paths.rend() ; i!=e ; ++i)
2134                 {
2135                         auto &s = *i;
2136                         if (node_paths.find(s.first) == node_paths.end())
2137                         {
2138                                 // Erased node, skip it.
2139                                 continue;
2140                         }
2141                         property_value v;
2142                         v.string_data = s.second.to_string();
2143                         v.type = property_value::STRING;
2144                         string name = s.first;
2145                         auto prop = std::make_shared<property>(std::move(name));
2146                         prop->add_value(v);
2147                         symbols.push_back(prop);
2148                 }
2149                 root->add_child(node::create_special_node("__symbols__", symbols));
2150         }
2151         // If this is a plugin, then we also need to create two extra nodes.
2152         // Internal phandles will need to be renumbered to avoid conflicts with
2153         // already-loaded nodes and external references will need to be
2154         // resolved.
2155         if (is_plugin)
2156         {
2157                 std::vector<property_ptr> symbols;
2158                 // Create the fixups entry.  This is of the form:
2159                 // {target} = {path}:{property name}:{offset}
2160                 auto create_fixup_entry = [&](fixup &i, string target)
2161                         {
2162                                 string value = i.path.to_string();
2163                                 value += ':';
2164                                 value += i.prop->get_key();
2165                                 value += ':';
2166                                 value += std::to_string(i.prop->offset_of_value(i.val));
2167                                 property_value v;
2168                                 v.string_data = value;
2169                                 v.type = property_value::STRING;
2170                                 auto prop = std::make_shared<property>(std::move(target));
2171                                 prop->add_value(v);
2172                                 return prop;
2173                         };
2174                 // If we have any unresolved phandle references in this plugin,
2175                 // then we must update them to 0xdeadbeef and leave a property in
2176                 // the /__fixups__ node whose key is the label and whose value is
2177                 // as described above.
2178                 if (!unresolved_fixups.empty())
2179                 {
2180                         for (auto &i : unresolved_fixups)
2181                         {
2182                                 auto &val = i.get().val;
2183                                 symbols.push_back(create_fixup_entry(i, val.string_data));
2184                                 val.byte_data.push_back(0xde);
2185                                 val.byte_data.push_back(0xad);
2186                                 val.byte_data.push_back(0xbe);
2187                                 val.byte_data.push_back(0xef);
2188                                 val.type = property_value::BINARY;
2189                         }
2190                         root->add_child(node::create_special_node("__fixups__", symbols));
2191                 }
2192                 symbols.clear();
2193                 // If we have any resolved phandle references in this plugin, then
2194                 // we must create a child in the __local_fixups__ node whose path
2195                 // matches the node path from the root and whose value contains the
2196                 // location of the reference within a property.
2197
2198                 // Create a local_fixups node that is initially empty.
2199                 node_ptr local_fixups = node::create_special_node("__local_fixups__", symbols);
2200                 for (auto &i : fixups)
2201                 {
2202                         if (!i.val.is_phandle())
2203                         {
2204                                 continue;
2205                         }
2206                         node_ptr n = local_fixups;
2207                         for (auto &p : i.path)
2208                         {
2209                                 // Skip the implicit root
2210                                 if (p.first.empty())
2211                                 {
2212                                         continue;
2213                                 }
2214                                 bool found = false;
2215                                 for (auto &c : n->child_nodes())
2216                                 {
2217                                         if (c->name == p.first)
2218                                         {
2219                                                 if (c->unit_address == p.second)
2220                                                 {
2221                                                         n = c;
2222                                                         found = true;
2223                                                         break;
2224                                                 }
2225                                         }
2226                                 }
2227                                 if (!found)
2228                                 {
2229                                         string path = p.first;
2230                                         if (!(p.second.empty()))
2231                                         {
2232                                                 path += '@';
2233                                                 path += p.second;
2234                                         }
2235                                         n->add_child(node::create_special_node(path, symbols));
2236                                         n = *(--(n->child_end()));
2237                                 }
2238                         }
2239                         assert(n);
2240                         property_value pv;
2241                         push_big_endian(pv.byte_data, static_cast<uint32_t>(i.prop->offset_of_value(i.val)));
2242                         pv.type = property_value::BINARY;
2243                         auto key = i.prop->get_key();
2244                         property_ptr prop = n->get_property(key);
2245                         // If we don't have an existing property then create one and
2246                         // use this property value
2247                         if (!prop)
2248                         {
2249                                 prop = std::make_shared<property>(std::move(key));
2250                                 n->add_property(prop);
2251                                 prop->add_value(pv);
2252                         }
2253                         else
2254                         {
2255                                 // If we do have an existing property value, try to append
2256                                 // this value.
2257                                 property_value &old_val = *(--prop->end());
2258                                 if (!old_val.try_to_merge(pv))
2259                                 {
2260                                         prop->add_value(pv);
2261                                 }
2262                         }
2263                 }
2264                 // We've iterated over all fixups, but only emit the
2265                 // __local_fixups__ if we found some that were resolved internally.
2266                 if (local_fixups->child_begin() != local_fixups->child_end())
2267                 {
2268                         root->add_child(std::move(local_fixups));
2269                 }
2270         }
2271 }
2272
2273 bool device_tree::parse_define(const char *def)
2274 {
2275         const char *val = strchr(def, '=');
2276         if (!val)
2277         {
2278                 if (strlen(def) != 0)
2279                 {
2280                         string name(def);
2281                         defines[name];
2282                         return true;
2283                 }
2284                 return false;
2285         }
2286         string name(def, val-def);
2287         string name_copy = name;
2288         val++;
2289         std::unique_ptr<input_buffer> raw(new input_buffer(val, strlen(val)));
2290         text_input_buffer in(std::move(raw),
2291                              std::unordered_set<string>(),
2292                              std::vector<string>(),
2293                              string(),
2294                              nullptr);
2295         property_ptr p = property::parse(in, std::move(name_copy), string_set(), false);
2296         if (p)
2297                 defines[name] = p;
2298         return (bool)p;
2299 }
2300
2301 } // namespace fdt
2302
2303 } // namespace dtc
2304