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