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