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