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