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 if (input.consume("/dts-v1/;")) 1567 { 1568 read_header = true; 1569 } 1570 input.next_token(); 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 input.next_token(); 1593 input.consume(';'); 1594 reservations.push_back(reservation(start, len)); 1595 input.next_token(); 1596 } 1597 while (valid && !input.finished()) 1598 { 1599 node_ptr n; 1600 if (input.consume('/')) 1601 { 1602 input.next_token(); 1603 n = node::parse(input, *this, string(), string_set(), string(), &defines); 1604 } 1605 else if (input.consume('&')) 1606 { 1607 input.next_token(); 1608 string name; 1609 bool name_is_path_reference = false; 1610 // This is to deal with names intended as path references, e.g. &{/path}. 1611 // While it may make sense in a non-plugin context, we don't support such 1612 // usage at this time. 1613 if (input.consume('{') && is_plugin) 1614 { 1615 name = input.parse_to('}'); 1616 input.consume('}'); 1617 name_is_path_reference = true; 1618 } 1619 else 1620 { 1621 name = input.parse_node_name(); 1622 } 1623 input.next_token(); 1624 n = node::parse(input, *this, std::move(name), string_set(), string(), &defines); 1625 n->name_is_path_reference = name_is_path_reference; 1626 } 1627 else 1628 { 1629 input.parse_error("Failed to find root node /."); 1630 } 1631 if (n) 1632 { 1633 roots.push_back(std::move(n)); 1634 } 1635 else 1636 { 1637 valid = false; 1638 } 1639 input.next_token(); 1640 } 1641 } 1642 1643 template<class writer> void 1644 device_tree::write(int fd) 1645 { 1646 dtb::string_table st; 1647 dtb::header head; 1648 writer head_writer; 1649 writer reservation_writer; 1650 writer struct_writer; 1651 writer strings_writer; 1652 1653 // Build the reservation table 1654 reservation_writer.write_comment(string("Memory reservations")); 1655 reservation_writer.write_label(string("dt_reserve_map")); 1656 for (auto &i : reservations) 1657 { 1658 reservation_writer.write_comment(string("Reservation start")); 1659 reservation_writer.write_data(i.first); 1660 reservation_writer.write_comment(string("Reservation length")); 1661 reservation_writer.write_data(i.first); 1662 } 1663 // Write n spare reserve map entries, plus the trailing 0. 1664 for (uint32_t i=0 ; i<=spare_reserve_map_entries ; i++) 1665 { 1666 reservation_writer.write_data((uint64_t)0); 1667 reservation_writer.write_data((uint64_t)0); 1668 } 1669 1670 1671 struct_writer.write_comment(string("Device tree")); 1672 struct_writer.write_label(string("dt_struct_start")); 1673 root->write(struct_writer, st); 1674 struct_writer.write_token(dtb::FDT_END); 1675 struct_writer.write_label(string("dt_struct_end")); 1676 1677 st.write(strings_writer); 1678 // Find the strings size before we stick padding on the end. 1679 // Note: We should possibly use a new writer for the padding. 1680 head.size_dt_strings = strings_writer.size(); 1681 1682 // Stick the padding in the strings writer, but after the 1683 // marker indicating that it's the end. 1684 // Note: We probably should add a padding call to the writer so 1685 // that the asm back end can write padding directives instead 1686 // of a load of 0 bytes. 1687 for (uint32_t i=0 ; i<blob_padding ; i++) 1688 { 1689 strings_writer.write_data((uint8_t)0); 1690 } 1691 head.totalsize = sizeof(head) + strings_writer.size() + 1692 struct_writer.size() + reservation_writer.size(); 1693 while (head.totalsize < minimum_blob_size) 1694 { 1695 head.totalsize++; 1696 strings_writer.write_data((uint8_t)0); 1697 } 1698 head.off_dt_struct = sizeof(head) + reservation_writer.size();; 1699 head.off_dt_strings = head.off_dt_struct + struct_writer.size(); 1700 head.off_mem_rsvmap = sizeof(head); 1701 head.boot_cpuid_phys = boot_cpu; 1702 head.size_dt_struct = struct_writer.size(); 1703 head.write(head_writer); 1704 1705 head_writer.write_to_file(fd); 1706 reservation_writer.write_to_file(fd); 1707 struct_writer.write_to_file(fd); 1708 strings_writer.write_label(string("dt_blob_end")); 1709 strings_writer.write_to_file(fd); 1710 } 1711 1712 node* 1713 device_tree::referenced_node(property_value &v) 1714 { 1715 if (v.is_phandle()) 1716 { 1717 return node_names[v.string_data]; 1718 } 1719 if (v.is_binary()) 1720 { 1721 return used_phandles[v.get_as_uint32()]; 1722 } 1723 return 0; 1724 } 1725 1726 void 1727 device_tree::write_binary(int fd) 1728 { 1729 write<dtb::binary_writer>(fd); 1730 } 1731 1732 void 1733 device_tree::write_asm(int fd) 1734 { 1735 write<dtb::asm_writer>(fd); 1736 } 1737 1738 void 1739 device_tree::write_dts(int fd) 1740 { 1741 FILE *file = fdopen(fd, "w"); 1742 fputs("/dts-v1/;\n\n", file); 1743 1744 if (!reservations.empty()) 1745 { 1746 const char msg[] = "/memreserve/"; 1747 fwrite(msg, sizeof(msg), 1, file); 1748 for (auto &i : reservations) 1749 { 1750 fprintf(file, " %" PRIx64 " %" PRIx64, i.first, i.second); 1751 } 1752 fputs(";\n\n", file); 1753 } 1754 putc('/', file); 1755 putc(' ', file); 1756 root->write_dts(file, 0); 1757 fclose(file); 1758 } 1759 1760 void 1761 device_tree::parse_dtb(const string &fn, FILE *) 1762 { 1763 auto in = input_buffer::buffer_for_file(fn); 1764 if (in == 0) 1765 { 1766 valid = false; 1767 return; 1768 } 1769 input_buffer &input = *in; 1770 dtb::header h; 1771 valid = h.read_dtb(input); 1772 boot_cpu = h.boot_cpuid_phys; 1773 if (h.last_comp_version > 17) 1774 { 1775 fprintf(stderr, "Don't know how to read this version of the device tree blob"); 1776 valid = false; 1777 } 1778 if (!valid) 1779 { 1780 return; 1781 } 1782 input_buffer reservation_map = 1783 input.buffer_from_offset(h.off_mem_rsvmap, 0); 1784 uint64_t start, length; 1785 do 1786 { 1787 if (!(reservation_map.consume_binary(start) && 1788 reservation_map.consume_binary(length))) 1789 { 1790 fprintf(stderr, "Failed to read memory reservation table\n"); 1791 valid = false; 1792 return; 1793 } 1794 } while (!((start == 0) && (length == 0))); 1795 input_buffer struct_table = 1796 input.buffer_from_offset(h.off_dt_struct, h.size_dt_struct); 1797 input_buffer strings_table = 1798 input.buffer_from_offset(h.off_dt_strings, h.size_dt_strings); 1799 uint32_t token; 1800 if (!(struct_table.consume_binary(token) && 1801 (token == dtb::FDT_BEGIN_NODE))) 1802 { 1803 fprintf(stderr, "Expected FDT_BEGIN_NODE token.\n"); 1804 valid = false; 1805 return; 1806 } 1807 root = node::parse_dtb(struct_table, strings_table); 1808 if (!(struct_table.consume_binary(token) && (token == dtb::FDT_END))) 1809 { 1810 fprintf(stderr, "Expected FDT_END token after parsing root node.\n"); 1811 valid = false; 1812 return; 1813 } 1814 valid = (root != 0); 1815 } 1816 1817 string 1818 device_tree::node_path::to_string() const 1819 { 1820 string path; 1821 auto p = begin(); 1822 auto pe = end(); 1823 if ((p == pe) || (p+1 == pe)) 1824 { 1825 return string("/"); 1826 } 1827 // Skip the first name in the path. It's always "", and implicitly / 1828 for (++p ; p!=pe ; ++p) 1829 { 1830 path += '/'; 1831 path += p->first; 1832 if (!(p->second.empty())) 1833 { 1834 path += '@'; 1835 path += p->second; 1836 } 1837 } 1838 return path; 1839 } 1840 1841 node_ptr 1842 device_tree::create_fragment_wrapper(node_ptr &node, int &fragnum) 1843 { 1844 // In a plugin, we can massage these non-/ root nodes into into a fragment 1845 std::string fragment_address = "fragment@" + std::to_string(fragnum); 1846 ++fragnum; 1847 1848 std::vector<property_ptr> symbols; 1849 1850 // Intentionally left empty 1851 node_ptr newroot = node::create_special_node("", symbols); 1852 node_ptr wrapper = node::create_special_node("__overlay__", symbols); 1853 1854 // Generate the fragment with $propname = <&name> 1855 property_value v; 1856 std::string propname; 1857 v.string_data = node->name; 1858 if (!node->name_is_path_reference) 1859 { 1860 propname = "target"; 1861 v.type = property_value::PHANDLE; 1862 } 1863 else 1864 { 1865 propname = "target-path"; 1866 v.type = property_value::STRING; 1867 } 1868 auto prop = std::make_shared<property>(std::string(propname)); 1869 prop->add_value(v); 1870 symbols.push_back(prop); 1871 1872 node_ptr fragment = node::create_special_node(fragment_address, symbols); 1873 1874 wrapper->merge_node(node); 1875 fragment->add_child(std::move(wrapper)); 1876 newroot->add_child(std::move(fragment)); 1877 return newroot; 1878 } 1879 1880 node_ptr 1881 device_tree::generate_root(node_ptr &node, int &fragnum) 1882 { 1883 1884 string name = node->name; 1885 if (name == string()) 1886 { 1887 return std::move(node); 1888 } 1889 else if (!is_plugin) 1890 { 1891 return nullptr; 1892 } 1893 1894 return create_fragment_wrapper(node, fragnum); 1895 } 1896 1897 void 1898 device_tree::reassign_fragment_numbers(node_ptr &node, int &delta) 1899 { 1900 1901 for (auto &c : node->child_nodes()) 1902 { 1903 if (c->name == std::string("fragment")) 1904 { 1905 int current_address = std::stoi(c->unit_address, nullptr, 16); 1906 std::ostringstream new_address; 1907 current_address += delta; 1908 // It's possible that we hopped more than one somewhere, so just reset 1909 // delta to the next in sequence. 1910 delta = current_address + 1; 1911 new_address << std::hex << current_address; 1912 c->unit_address = new_address.str(); 1913 } 1914 } 1915 } 1916 1917 void 1918 device_tree::parse_dts(const string &fn, FILE *depfile) 1919 { 1920 auto in = input_buffer::buffer_for_file(fn); 1921 if (!in) 1922 { 1923 valid = false; 1924 return; 1925 } 1926 std::vector<node_ptr> roots; 1927 std::unordered_set<string> defnames; 1928 for (auto &i : defines) 1929 { 1930 defnames.insert(i.first); 1931 } 1932 text_input_buffer input(std::move(in), 1933 std::move(defnames), 1934 std::vector<string>(include_paths), 1935 dirname(fn), 1936 depfile); 1937 bool read_header = false; 1938 int fragnum = 0; 1939 parse_file(input, roots, read_header); 1940 switch (roots.size()) 1941 { 1942 case 0: 1943 valid = false; 1944 input.parse_error("Failed to find root node /."); 1945 return; 1946 case 1: 1947 root = generate_root(roots[0], fragnum); 1948 if (!root) 1949 { 1950 valid = false; 1951 input.parse_error("Failed to find root node /."); 1952 return; 1953 } 1954 break; 1955 default: 1956 { 1957 root = generate_root(roots[0], fragnum); 1958 if (!root) 1959 { 1960 valid = false; 1961 input.parse_error("Failed to find root node /."); 1962 return; 1963 } 1964 for (auto i=++(roots.begin()), e=roots.end() ; i!=e ; ++i) 1965 { 1966 auto &node = *i; 1967 string name = node->name; 1968 if (name == string()) 1969 { 1970 if (is_plugin) 1971 { 1972 // Re-assign any fragment numbers based on a delta of 1973 // fragnum before we merge it 1974 reassign_fragment_numbers(node, fragnum); 1975 } 1976 root->merge_node(node); 1977 } 1978 else 1979 { 1980 auto existing = node_names.find(name); 1981 if (existing == node_names.end()) 1982 { 1983 collect_names(); 1984 existing = node_names.find(name); 1985 } 1986 if (existing == node_names.end()) 1987 { 1988 if (is_plugin) 1989 { 1990 auto fragment = create_fragment_wrapper(node, fragnum); 1991 root->merge_node(fragment); 1992 } 1993 else 1994 { 1995 fprintf(stderr, "Unable to merge node: %s\n", name.c_str()); 1996 } 1997 } 1998 else 1999 { 2000 existing->second->merge_node(node); 2001 } 2002 } 2003 } 2004 } 2005 } 2006 collect_names(); 2007 // Return value indicates whether we've dirtied the tree or not and need to 2008 // recollect names 2009 if (garbage_collect && garbage_collect_marked_nodes()) 2010 { 2011 collect_names(); 2012 } 2013 uint32_t phandle = 1; 2014 // If we're writing symbols, go ahead and assign phandles to the entire 2015 // tree. We'll do this before we resolve cross references, just to keep 2016 // order semi-predictable and stable. 2017 if (write_symbols) 2018 { 2019 assign_phandles(root, phandle); 2020 } 2021 resolve_cross_references(phandle); 2022 if (write_symbols) 2023 { 2024 std::vector<property_ptr> symbols; 2025 // Create a symbol table. Each label in this device tree may be 2026 // referenced by other plugins, so we create a __symbols__ node inside 2027 // the root that contains mappings (properties) from label names to 2028 // paths. 2029 for (auto i=ordered_node_paths.rbegin(), e=ordered_node_paths.rend() ; i!=e ; ++i) 2030 { 2031 auto &s = *i; 2032 if (node_paths.find(s.first) == node_paths.end()) 2033 { 2034 // Erased node, skip it. 2035 continue; 2036 } 2037 property_value v; 2038 v.string_data = s.second.to_string(); 2039 v.type = property_value::STRING; 2040 string name = s.first; 2041 auto prop = std::make_shared<property>(std::move(name)); 2042 prop->add_value(v); 2043 symbols.push_back(prop); 2044 } 2045 root->add_child(node::create_special_node("__symbols__", symbols)); 2046 } 2047 // If this is a plugin, then we also need to create two extra nodes. 2048 // Internal phandles will need to be renumbered to avoid conflicts with 2049 // already-loaded nodes and external references will need to be 2050 // resolved. 2051 if (is_plugin) 2052 { 2053 std::vector<property_ptr> symbols; 2054 // Create the fixups entry. This is of the form: 2055 // {target} = {path}:{property name}:{offset} 2056 auto create_fixup_entry = [&](fixup &i, string target) 2057 { 2058 string value = i.path.to_string(); 2059 value += ':'; 2060 value += i.prop->get_key(); 2061 value += ':'; 2062 value += std::to_string(i.prop->offset_of_value(i.val)); 2063 property_value v; 2064 v.string_data = value; 2065 v.type = property_value::STRING; 2066 auto prop = std::make_shared<property>(std::move(target)); 2067 prop->add_value(v); 2068 return prop; 2069 }; 2070 // If we have any unresolved phandle references in this plugin, 2071 // then we must update them to 0xdeadbeef and leave a property in 2072 // the /__fixups__ node whose key is the label and whose value is 2073 // as described above. 2074 if (!unresolved_fixups.empty()) 2075 { 2076 for (auto &i : unresolved_fixups) 2077 { 2078 auto &val = i.get().val; 2079 symbols.push_back(create_fixup_entry(i, val.string_data)); 2080 val.byte_data.push_back(0xde); 2081 val.byte_data.push_back(0xad); 2082 val.byte_data.push_back(0xbe); 2083 val.byte_data.push_back(0xef); 2084 val.type = property_value::BINARY; 2085 } 2086 root->add_child(node::create_special_node("__fixups__", symbols)); 2087 } 2088 symbols.clear(); 2089 // If we have any resolved phandle references in this plugin, then 2090 // we must create a child in the __local_fixups__ node whose path 2091 // matches the node path from the root and whose value contains the 2092 // location of the reference within a property. 2093 2094 // Create a local_fixups node that is initially empty. 2095 node_ptr local_fixups = node::create_special_node("__local_fixups__", symbols); 2096 for (auto &i : fixups) 2097 { 2098 if (!i.val.is_phandle()) 2099 { 2100 continue; 2101 } 2102 node *n = local_fixups.get(); 2103 for (auto &p : i.path) 2104 { 2105 // Skip the implicit root 2106 if (p.first.empty()) 2107 { 2108 continue; 2109 } 2110 bool found = false; 2111 for (auto &c : n->child_nodes()) 2112 { 2113 if (c->name == p.first) 2114 { 2115 if (c->unit_address == p.second) 2116 { 2117 n = c.get(); 2118 found = true; 2119 break; 2120 } 2121 } 2122 } 2123 if (!found) 2124 { 2125 string path = p.first; 2126 if (!(p.second.empty())) 2127 { 2128 path += '@'; 2129 path += p.second; 2130 } 2131 n->add_child(node::create_special_node(path, symbols)); 2132 n = (--n->child_end())->get(); 2133 } 2134 } 2135 assert(n); 2136 property_value pv; 2137 push_big_endian(pv.byte_data, static_cast<uint32_t>(i.prop->offset_of_value(i.val))); 2138 pv.type = property_value::BINARY; 2139 auto key = i.prop->get_key(); 2140 property_ptr prop = n->get_property(key); 2141 // If we don't have an existing property then create one and 2142 // use this property value 2143 if (!prop) 2144 { 2145 prop = std::make_shared<property>(std::move(key)); 2146 n->add_property(prop); 2147 prop->add_value(pv); 2148 } 2149 else 2150 { 2151 // If we do have an existing property value, try to append 2152 // this value. 2153 property_value &old_val = *(--prop->end()); 2154 if (!old_val.try_to_merge(pv)) 2155 { 2156 prop->add_value(pv); 2157 } 2158 } 2159 } 2160 // We've iterated over all fixups, but only emit the 2161 // __local_fixups__ if we found some that were resolved internally. 2162 if (local_fixups->child_begin() != local_fixups->child_end()) 2163 { 2164 root->add_child(std::move(local_fixups)); 2165 } 2166 } 2167 } 2168 2169 bool device_tree::parse_define(const char *def) 2170 { 2171 const char *val = strchr(def, '='); 2172 if (!val) 2173 { 2174 if (strlen(def) != 0) 2175 { 2176 string name(def); 2177 defines[name]; 2178 return true; 2179 } 2180 return false; 2181 } 2182 string name(def, val-def); 2183 string name_copy = name; 2184 val++; 2185 std::unique_ptr<input_buffer> raw(new input_buffer(val, strlen(val))); 2186 text_input_buffer in(std::move(raw), 2187 std::unordered_set<string>(), 2188 std::vector<string>(), 2189 string(), 2190 nullptr); 2191 property_ptr p = property::parse(in, std::move(name_copy), string_set(), false); 2192 if (p) 2193 defines[name] = p; 2194 return (bool)p; 2195 } 2196 2197 } // namespace fdt 2198 2199 } // namespace dtc 2200 2201