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