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 #ifndef _FDT_HH_ 34 #define _FDT_HH_ 35 #include <unordered_map> 36 #include <unordered_set> 37 #include <memory> 38 #include <string> 39 40 #include "util.hh" 41 #include "string.hh" 42 43 namespace dtc 44 { 45 46 namespace dtb 47 { 48 struct output_writer; 49 class string_table; 50 } 51 52 namespace fdt 53 { 54 class property; 55 class node; 56 /** 57 * Type for (owned) pointers to properties. 58 */ 59 typedef std::shared_ptr<property> property_ptr; 60 /** 61 * Owning pointer to a node. 62 */ 63 typedef std::unique_ptr<node> node_ptr; 64 /** 65 * Map from macros to property pointers. 66 */ 67 typedef std::unordered_map<string, property_ptr> define_map; 68 /** 69 * Properties may contain a number of different value, each with a different 70 * label. This class encapsulates a single value. 71 */ 72 struct property_value 73 { 74 /** 75 * The label for this data. This is usually empty. 76 */ 77 string label; 78 /** 79 * If this value is a string, or something resolved from a string (a 80 * reference) then this contains the source string. 81 */ 82 string string_data; 83 /** 84 * The data that should be written to the final output. 85 */ 86 byte_buffer byte_data; 87 /** 88 * Enumeration describing the possible types of a value. Note that 89 * property-coded arrays will appear simply as binary (or possibly 90 * string, if they happen to be nul-terminated and printable), and must 91 * be checked separately. 92 */ 93 enum value_type 94 { 95 /** 96 * This is a list of strings. When read from source, string 97 * lists become one property value for each string, however 98 * when read from binary we have a single property value 99 * incorporating the entire text, with nul bytes separating the 100 * strings. 101 */ 102 STRING_LIST, 103 /** 104 * This property contains a single string. 105 */ 106 STRING, 107 /** 108 * This is a binary value. Check the size of byte_data to 109 * determine how many bytes this contains. 110 */ 111 BINARY, 112 /** This contains a short-form address that should be replaced 113 * by a fully-qualified version. This will only appear when 114 * the input is a device tree source. When parsed from a 115 * device tree blob, the cross reference will have already been 116 * resolved and the property value will be a string containing 117 * the full path of the target node. */ 118 CROSS_REFERENCE, 119 /** 120 * This is a phandle reference. When parsed from source, the 121 * string_data will contain the node label for the target and, 122 * after cross references have been resolved, the binary data 123 * will contain a 32-bit integer that should match the phandle 124 * property of the target node. 125 */ 126 PHANDLE, 127 /** 128 * An empty property value. This will never appear on a real 129 * property value, it is used by checkers to indicate that no 130 * property values should exist for a property. 131 */ 132 EMPTY, 133 /** 134 * The type of this property has not yet been determined. 135 */ 136 UNKNOWN 137 }; 138 /** 139 * The type of this property. 140 */ 141 value_type type; 142 /** 143 * Returns true if this value is a cross reference, false otherwise. 144 */ 145 inline bool is_cross_reference() 146 { 147 return is_type(CROSS_REFERENCE); 148 } 149 /** 150 * Returns true if this value is a phandle reference, false otherwise. 151 */ 152 inline bool is_phandle() 153 { 154 return is_type(PHANDLE); 155 } 156 /** 157 * Returns true if this value is a string, false otherwise. 158 */ 159 inline bool is_string() 160 { 161 return is_type(STRING); 162 } 163 /** 164 * Returns true if this value is a string list (a nul-separated 165 * sequence of strings), false otherwise. 166 */ 167 inline bool is_string_list() 168 { 169 return is_type(STRING_LIST); 170 } 171 /** 172 * Returns true if this value is binary, false otherwise. 173 */ 174 inline bool is_binary() 175 { 176 return is_type(BINARY); 177 } 178 /** 179 * Returns this property value as a 32-bit integer. Returns 0 if this 180 * property value is not 32 bits long. The bytes in the property value 181 * are assumed to be in big-endian format, but the return value is in 182 * the host native endian. 183 */ 184 uint32_t get_as_uint32(); 185 /** 186 * Default constructor, specifying the label of the value. 187 */ 188 property_value(string l=string()) : label(l), type(UNKNOWN) {} 189 /** 190 * Writes the data for this value into an output buffer. 191 */ 192 void push_to_buffer(byte_buffer &buffer); 193 194 /** 195 * Writes the property value to the standard output. This uses the 196 * following heuristics for deciding how to print the output: 197 * 198 * - If the value is nul-terminated and only contains printable 199 * characters, it is written as a string. 200 * - If it is a multiple of 4 bytes long, then it is printed as cells. 201 * - Otherwise, it is printed as a byte buffer. 202 */ 203 void write_dts(FILE *file); 204 /** 205 * Tries to merge adjacent property values, returns true if it succeeds and 206 * false otherwise. 207 */ 208 bool try_to_merge(property_value &other); 209 private: 210 /** 211 * Returns whether the value is of the specified type. If the type of 212 * the value has not yet been determined, then this calculates it. 213 */ 214 inline bool is_type(value_type v) 215 { 216 if (type == UNKNOWN) 217 { 218 resolve_type(); 219 } 220 return type == v; 221 } 222 /** 223 * Determines the type of the value based on its contents. 224 */ 225 void resolve_type(); 226 /** 227 * Writes the property value to the specified file as a quoted string. 228 * This is used when generating DTS. 229 */ 230 void write_as_string(FILE *file); 231 /** 232 * Writes the property value to the specified file as a sequence of 233 * 32-bit big-endian cells. This is used when generating DTS. 234 */ 235 void write_as_cells(FILE *file); 236 /** 237 * Writes the property value to the specified file as a sequence of 238 * bytes. This is used when generating DTS. 239 */ 240 void write_as_bytes(FILE *file); 241 }; 242 243 /** 244 * A value encapsulating a single property. This contains a key, optionally a 245 * label, and optionally one or more values. 246 */ 247 class property 248 { 249 /** 250 * The name of this property. 251 */ 252 string key; 253 /** 254 * An optional label. 255 */ 256 string label; 257 /** 258 * The values in this property. 259 */ 260 std::vector<property_value> values; 261 /** 262 * Value indicating that this is a valid property. If a parse error 263 * occurs, then this value is false. 264 */ 265 bool valid; 266 /** 267 * Parses a string property value, i.e. a value enclosed in double quotes. 268 */ 269 void parse_string(input_buffer &input); 270 /** 271 * Parses one or more 32-bit values enclosed in angle brackets. 272 */ 273 void parse_cells(input_buffer &input, int cell_size); 274 /** 275 * Parses an array of bytes, contained within square brackets. 276 */ 277 void parse_bytes(input_buffer &input); 278 /** 279 * Parses a reference. This is a node label preceded by an ampersand 280 * symbol, which should expand to the full path to that node. 281 * 282 * Note: The specification says that the target of such a reference is 283 * a node name, however dtc assumes that it is a label, and so we 284 * follow their interpretation for compatibility. 285 */ 286 void parse_reference(input_buffer &input); 287 /** 288 * Parse a predefined macro definition for a property. 289 */ 290 void parse_define(input_buffer &input, define_map *defines); 291 /** 292 * Constructs a new property from two input buffers, pointing to the 293 * struct and strings tables in the device tree blob, respectively. 294 * The structs input buffer is assumed to have just consumed the 295 * FDT_PROP token. 296 */ 297 property(input_buffer &structs, input_buffer &strings); 298 /** 299 * Parses a new property from the input buffer. 300 */ 301 property(input_buffer &input, 302 string k, 303 string l, 304 bool terminated, 305 define_map *defines); 306 public: 307 /** 308 * Creates an empty property. 309 */ 310 property(string k, string l=string()) : key(k), label(l), valid(true) 311 {} 312 /** 313 * Copy constructor. 314 */ 315 property(property &p) : key(p.key), label(p.label), values(p.values), 316 valid(p.valid) {} 317 /** 318 * Factory method for constructing a new property. Attempts to parse a 319 * property from the input, and returns it on success. On any parse 320 * error, this will return 0. 321 */ 322 static property_ptr parse_dtb(input_buffer &structs, 323 input_buffer &strings); 324 /** 325 * Factory method for constructing a new property. Attempts to parse a 326 * property from the input, and returns it on success. On any parse 327 * error, this will return 0. 328 */ 329 static property_ptr parse(input_buffer &input, 330 string key, 331 string label=string(), 332 bool semicolonTerminated=true, 333 define_map *defines=0); 334 /** 335 * Iterator type used for accessing the values of a property. 336 */ 337 typedef std::vector<property_value>::iterator value_iterator; 338 /** 339 * Returns an iterator referring to the first value in this property. 340 */ 341 inline value_iterator begin() 342 { 343 return values.begin(); 344 } 345 /** 346 * Returns an iterator referring to the last value in this property. 347 */ 348 inline value_iterator end() 349 { 350 return values.end(); 351 } 352 /** 353 * Adds a new value to an existing property. 354 */ 355 inline void add_value(property_value v) 356 { 357 values.push_back(v); 358 } 359 /** 360 * Returns the key for this property. 361 */ 362 inline string get_key() 363 { 364 return key; 365 } 366 /** 367 * Writes the property to the specified writer. The property name is a 368 * reference into the strings table. 369 */ 370 void write(dtb::output_writer &writer, dtb::string_table &strings); 371 /** 372 * Writes in DTS format to the specified file, at the given indent 373 * level. This will begin the line with the number of tabs specified 374 * as the indent level and then write the property in the most 375 * applicable way that it can determine. 376 */ 377 void write_dts(FILE *file, int indent); 378 }; 379 380 /** 381 * Class encapsulating a device tree node. Nodes may contain properties and 382 * other nodes. 383 */ 384 class node 385 { 386 public: 387 /** 388 * The label for this node, if any. Node labels are used as the 389 * targets for cross references. 390 */ 391 string label; 392 /** 393 * The name of the node. 394 */ 395 string name; 396 /** 397 * The unit address of the node, which is optionally written after the 398 * name followed by an at symbol. 399 */ 400 string unit_address; 401 /** 402 * The type for the property vector. 403 */ 404 typedef std::vector<property_ptr> property_vector; 405 private: 406 /** 407 * The properties contained within this node. 408 */ 409 property_vector properties; 410 /** 411 * The children of this node. 412 */ 413 std::vector<node_ptr> children; 414 /** 415 * A flag indicating whether this node is valid. This is set to false 416 * if an error occurs during parsing. 417 */ 418 bool valid; 419 /** 420 * Parses a name inside a node, writing the string passed as the last 421 * argument as an error if it fails. 422 */ 423 string parse_name(input_buffer &input, 424 bool &is_property, 425 const char *error); 426 /** 427 * Constructs a new node from two input buffers, pointing to the struct 428 * and strings tables in the device tree blob, respectively. 429 */ 430 node(input_buffer &structs, input_buffer &strings); 431 /** 432 * Parses a new node from the specified input buffer. This is called 433 * when the input cursor is on the open brace for the start of the 434 * node. The name, and optionally label and unit address, should have 435 * already been parsed. 436 */ 437 node(input_buffer &input, string n, string l, string a, define_map*); 438 /** 439 * Comparison function for properties, used when sorting the properties 440 * vector. Orders the properties based on their names. 441 */ 442 static inline bool cmp_properties(property_ptr &p1, property_ptr &p2); 443 /* 444 { 445 return p1->get_key() < p2->get_key(); 446 } 447 */ 448 /** 449 * Comparison function for nodes, used when sorting the children 450 * vector. Orders the nodes based on their names or, if the names are 451 * the same, by the unit addresses. 452 */ 453 static inline bool cmp_children(node_ptr &c1, node_ptr &c2); 454 public: 455 /** 456 * Sorts the node's properties and children into alphabetical order and 457 * recursively sorts the children. 458 */ 459 void sort(); 460 /** 461 * Iterator type for child nodes. 462 */ 463 typedef std::vector<node_ptr>::iterator child_iterator; 464 /** 465 * Returns an iterator for the first child of this node. 466 */ 467 inline child_iterator child_begin() 468 { 469 return children.begin(); 470 } 471 /** 472 * Returns an iterator after the last child of this node. 473 */ 474 inline child_iterator child_end() 475 { 476 return children.end(); 477 } 478 /** 479 * Returns an iterator after the last property of this node. 480 */ 481 inline property_vector::iterator property_begin() 482 { 483 return properties.begin(); 484 } 485 /** 486 * Returns an iterator for the first property of this node. 487 */ 488 inline property_vector::iterator property_end() 489 { 490 return properties.end(); 491 } 492 /** 493 * Factory method for constructing a new node. Attempts to parse a 494 * node in DTS format from the input, and returns it on success. On 495 * any parse error, this will return 0. This should be called with the 496 * cursor on the open brace of the property, after the name and so on 497 * have been parsed. 498 */ 499 static node_ptr parse(input_buffer &input, 500 string name, 501 string label=string(), 502 string address=string(), 503 define_map *defines=0); 504 /** 505 * Factory method for constructing a new node. Attempts to parse a 506 * node in DTB format from the input, and returns it on success. On 507 * any parse error, this will return 0. This should be called with the 508 * cursor on the open brace of the property, after the name and so on 509 * have been parsed. 510 */ 511 static node_ptr parse_dtb(input_buffer &structs, input_buffer &strings); 512 /** 513 * Returns a property corresponding to the specified key, or 0 if this 514 * node does not contain a property of that name. 515 */ 516 property_ptr get_property(string key); 517 /** 518 * Adds a new property to this node. 519 */ 520 inline void add_property(property_ptr &p) 521 { 522 properties.push_back(p); 523 } 524 /** 525 * Merges a node into this one. Any properties present in both are 526 * overridden, any properties present in only one are preserved. 527 */ 528 void merge_node(node_ptr other); 529 /** 530 * Write this node to the specified output. Although nodes do not 531 * refer to a string table directly, their properties do. The string 532 * table passed as the second argument is used for the names of 533 * properties within this node and its children. 534 */ 535 void write(dtb::output_writer &writer, dtb::string_table &strings); 536 /** 537 * Writes the current node as DTS to the specified file. The second 538 * parameter is the indent level. This function will start every line 539 * with this number of tabs. 540 */ 541 void write_dts(FILE *file, int indent); 542 }; 543 544 /** 545 * Class encapsulating the entire parsed FDT. This is the top-level class, 546 * which parses the entire DTS representation and write out the finished 547 * version. 548 */ 549 class device_tree 550 { 551 public: 552 /** 553 * Type used for node paths. A node path is sequence of names and unit 554 * addresses. 555 */ 556 typedef std::vector<std::pair<string,string> > node_path; 557 /** 558 * Name that we should use for phandle nodes. 559 */ 560 enum phandle_format 561 { 562 /** linux,phandle */ 563 LINUX, 564 /** phandle */ 565 EPAPR, 566 /** Create both nodes. */ 567 BOTH 568 }; 569 private: 570 /** 571 * The format that we should use for writing phandles. 572 */ 573 phandle_format phandle_node_name; 574 /** 575 * Flag indicating that this tree is valid. This will be set to false 576 * on parse errors. 577 */ 578 bool valid; 579 /** 580 * Type used for memory reservations. A reservation is two 64-bit 581 * values indicating a base address and length in memory that the 582 * kernel should not use. The high 32 bits are ignored on 32-bit 583 * platforms. 584 */ 585 typedef std::pair<uint64_t, uint64_t> reservation; 586 /** 587 * The memory reserves table. 588 */ 589 std::vector<reservation> reservations; 590 /** 591 * Root node. All other nodes are children of this node. 592 */ 593 node_ptr root; 594 /** 595 * Mapping from names to nodes. Only unambiguous names are recorded, 596 * duplicate names are stored as (node*)-1. 597 */ 598 std::unordered_map<string, node*> node_names; 599 /** 600 * A map from labels to node paths. When resolving cross references, 601 * we look up referenced nodes in this and replace the cross reference 602 * with the full path to its target. 603 */ 604 std::unordered_map<string, node_path> node_paths; 605 /** 606 * A collection of property values that are references to other nodes. 607 * These should be expanded to the full path of their targets. 608 */ 609 std::vector<property_value*> cross_references; 610 /** 611 * A collection of property values that refer to phandles. These will 612 * be replaced by the value of the phandle property in their 613 * destination. 614 */ 615 std::vector<property_value*> phandles; 616 /** 617 * The names of nodes that target phandles. 618 */ 619 std::unordered_set<string> phandle_targets; 620 /** 621 * A collection of input buffers that we are using. These input 622 * buffers are the ones that own their memory, and so we must preserve 623 * them for the lifetime of the device tree. 624 */ 625 std::vector<std::unique_ptr<input_buffer>> buffers; 626 /** 627 * A map of used phandle values to nodes. All phandles must be unique, 628 * so we keep a set of ones that the user explicitly provides in the 629 * input to ensure that we don't reuse them. 630 * 631 * This is a map, rather than a set, because we also want to be able to 632 * find phandles that were provided by the user explicitly when we are 633 * doing checking. 634 */ 635 std::unordered_map<uint32_t, node*> used_phandles; 636 /** 637 * Paths to search for include files. This contains a set of 638 * nul-terminated strings, which are not owned by this class and so 639 * must be freed separately. 640 */ 641 std::vector<std::string> include_paths; 642 /** 643 * Dictionary of predefined macros provided on the command line. 644 */ 645 define_map defines; 646 /** 647 * The default boot CPU, specified in the device tree header. 648 */ 649 uint32_t boot_cpu; 650 /** 651 * The number of empty reserve map entries to generate in the blob. 652 */ 653 uint32_t spare_reserve_map_entries; 654 /** 655 * The minimum size in bytes of the blob. 656 */ 657 uint32_t minimum_blob_size; 658 /** 659 * The number of bytes of padding to add to the end of the blob. 660 */ 661 uint32_t blob_padding; 662 /** 663 * Visit all of the nodes recursively, and if they have labels then add 664 * them to the node_paths and node_names vectors so that they can be 665 * used in resolving cross references. Also collects phandle 666 * properties that have been explicitly added. 667 */ 668 void collect_names_recursive(node_ptr &n, node_path &path); 669 /** 670 * Assign phandle properties to all nodes that have been referenced and 671 * require one. This method will recursively visit the tree starting at 672 * the node that it is passed. 673 */ 674 void assign_phandles(node_ptr &n, uint32_t &next); 675 /** 676 * Calls the recursive version of this method on every root node. 677 */ 678 void collect_names(); 679 /** 680 * Resolves all cross references. Any properties that refer to another 681 * node must have their values replaced by either the node path or 682 * phandle value. 683 */ 684 void resolve_cross_references(); 685 /** 686 * Parses a dts file in the given buffer and adds the roots to the parsed 687 * set. The `read_header` argument indicates whether the header has 688 * already been read. Some dts files place the header in an include, 689 * rather than in the top-level file. 690 */ 691 void parse_file(input_buffer &input, 692 const std::string &dir, 693 std::vector<node_ptr> &roots, 694 FILE *depfile, 695 bool &read_header); 696 /** 697 * Allocates a new mmap()'d input buffer for use in parsing. This 698 * object then keeps a reference to it, ensuring that it is not 699 * deallocated until the device tree is destroyed. 700 */ 701 input_buffer *buffer_for_file(const char *path); 702 /** 703 * Template function that writes a dtb blob using the specified writer. 704 * The writer defines the output format (assembly, blob). 705 */ 706 template<class writer> 707 void write(int fd); 708 public: 709 /** 710 * Returns the node referenced by the property. If this is a tree that 711 * is in source form, then we have a string that we can use to index 712 * the cross_references array and so we can just look that up. 713 */ 714 node *referenced_node(property_value &v); 715 /** 716 * Writes this FDT as a DTB to the specified output. 717 */ 718 void write_binary(int fd); 719 /** 720 * Writes this FDT as an assembly representation of the DTB to the 721 * specified output. The result can then be assembled and linked into 722 * a program. 723 */ 724 void write_asm(int fd); 725 /** 726 * Writes the tree in DTS (source) format. 727 */ 728 void write_dts(int fd); 729 /** 730 * Default constructor. Creates a valid, but empty FDT. 731 */ 732 device_tree() : phandle_node_name(EPAPR), valid(true), 733 boot_cpu(0), spare_reserve_map_entries(0), 734 minimum_blob_size(0), blob_padding(0) {} 735 /** 736 * Constructs a device tree from the specified file name, referring to 737 * a file that contains a device tree blob. 738 */ 739 void parse_dtb(const char *fn, FILE *depfile); 740 /** 741 * Constructs a device tree from the specified file name, referring to 742 * a file that contains device tree source. 743 */ 744 void parse_dts(const char *fn, FILE *depfile); 745 /** 746 * Returns whether this tree is valid. 747 */ 748 inline bool is_valid() 749 { 750 return valid; 751 } 752 /** 753 * Sets the format for writing phandle properties. 754 */ 755 inline void set_phandle_format(phandle_format f) 756 { 757 phandle_node_name = f; 758 } 759 /** 760 * Returns a pointer to the root node of this tree. No ownership 761 * transfer. 762 */ 763 inline const node_ptr &get_root() const 764 { 765 return root; 766 } 767 /** 768 * Sets the physical boot CPU. 769 */ 770 void set_boot_cpu(uint32_t cpu) 771 { 772 boot_cpu = cpu; 773 } 774 /** 775 * Sorts the tree. Useful for debugging device trees. 776 */ 777 void sort() 778 { 779 root->sort(); 780 } 781 /** 782 * Adds a path to search for include files. The argument must be a 783 * nul-terminated string representing the path. The device tree keeps 784 * a pointer to this string, but does not own it: the caller is 785 * responsible for freeing it if required. 786 */ 787 void add_include_path(const char *path) 788 { 789 std::string p(path); 790 include_paths.push_back(std::move(p)); 791 } 792 /** 793 * Sets the number of empty reserve map entries to add. 794 */ 795 void set_empty_reserve_map_entries(uint32_t e) 796 { 797 spare_reserve_map_entries = e; 798 } 799 /** 800 * Sets the minimum size, in bytes, of the blob. 801 */ 802 void set_blob_minimum_size(uint32_t s) 803 { 804 minimum_blob_size = s; 805 } 806 /** 807 * Sets the amount of padding to add to the blob. 808 */ 809 void set_blob_padding(uint32_t p) 810 { 811 blob_padding = p; 812 } 813 /** 814 * Parses a predefined macro value. 815 */ 816 bool parse_define(const char *def); 817 }; 818 819 } // namespace fdt 820 821 } // namespace dtc 822 823 #endif // !_FDT_HH_ 824