usr.bin/dtc/fdt.cc

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