usr.bin/dtc/fdt.cc

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