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