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