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