usr.bin/dtc/fdt.cc

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