2 * Copyright (c) 2013 David Chisnall
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.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
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.
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
35 #include <unordered_map>
36 #include <unordered_set>
42 #include "input_buffer.hh"
58 * Type for (owned) pointers to properties.
60 typedef std::shared_ptr<property> property_ptr;
62 * Owning pointer to a node.
64 typedef std::unique_ptr<node> node_ptr;
66 * Map from macros to property pointers.
68 typedef std::unordered_map<std::string, property_ptr> define_map;
70 * Set of strings used for label names.
72 typedef std::unordered_set<std::string> string_set;
74 * Properties may contain a number of different value, each with a different
75 * label. This class encapsulates a single value.
80 * The label for this data. This is usually empty.
84 * If this value is a string, or something resolved from a string (a
85 * reference) then this contains the source string.
87 std::string string_data;
89 * The data that should be written to the final output.
91 byte_buffer byte_data;
93 * Enumeration describing the possible types of a value. Note that
94 * property-coded arrays will appear simply as binary (or possibly
95 * string, if they happen to be nul-terminated and printable), and must
96 * be checked separately.
101 * This is a list of strings. When read from source, string
102 * lists become one property value for each string, however
103 * when read from binary we have a single property value
104 * incorporating the entire text, with nul bytes separating the
109 * This property contains a single string.
113 * This is a binary value. Check the size of byte_data to
114 * determine how many bytes this contains.
117 /** This contains a short-form address that should be replaced
118 * by a fully-qualified version. This will only appear when
119 * the input is a device tree source. When parsed from a
120 * device tree blob, the cross reference will have already been
121 * resolved and the property value will be a string containing
122 * the full path of the target node. */
125 * This is a phandle reference. When parsed from source, the
126 * string_data will contain the node label for the target and,
127 * after cross references have been resolved, the binary data
128 * will contain a 32-bit integer that should match the phandle
129 * property of the target node.
133 * An empty property value. This will never appear on a real
134 * property value, it is used by checkers to indicate that no
135 * property values should exist for a property.
139 * The type of this property has not yet been determined.
144 * The type of this property.
148 * Returns true if this value is a cross reference, false otherwise.
150 inline bool is_cross_reference()
152 return is_type(CROSS_REFERENCE);
155 * Returns true if this value is a phandle reference, false otherwise.
157 inline bool is_phandle()
159 return is_type(PHANDLE);
162 * Returns true if this value is a string, false otherwise.
164 inline bool is_string()
166 return is_type(STRING);
169 * Returns true if this value is a string list (a nul-separated
170 * sequence of strings), false otherwise.
172 inline bool is_string_list()
174 return is_type(STRING_LIST);
177 * Returns true if this value is binary, false otherwise.
179 inline bool is_binary()
181 return is_type(BINARY);
184 * Returns this property value as a 32-bit integer. Returns 0 if this
185 * property value is not 32 bits long. The bytes in the property value
186 * are assumed to be in big-endian format, but the return value is in
187 * the host native endian.
189 uint32_t get_as_uint32();
191 * Default constructor, specifying the label of the value.
193 property_value(std::string l=std::string()) : label(l), type(UNKNOWN) {}
195 * Writes the data for this value into an output buffer.
197 void push_to_buffer(byte_buffer &buffer);
200 * Writes the property value to the standard output. This uses the
201 * following heuristics for deciding how to print the output:
203 * - If the value is nul-terminated and only contains printable
204 * characters, it is written as a string.
205 * - If it is a multiple of 4 bytes long, then it is printed as cells.
206 * - Otherwise, it is printed as a byte buffer.
208 void write_dts(FILE *file);
210 * Tries to merge adjacent property values, returns true if it succeeds and
213 bool try_to_merge(property_value &other);
216 * Returns whether the value is of the specified type. If the type of
217 * the value has not yet been determined, then this calculates it.
219 inline bool is_type(value_type v)
228 * Determines the type of the value based on its contents.
232 * Writes the property value to the specified file as a quoted string.
233 * This is used when generating DTS.
235 void write_as_string(FILE *file);
237 * Writes the property value to the specified file as a sequence of
238 * 32-bit big-endian cells. This is used when generating DTS.
240 void write_as_cells(FILE *file);
242 * Writes the property value to the specified file as a sequence of
243 * bytes. This is used when generating DTS.
245 void write_as_bytes(FILE *file);
249 * A value encapsulating a single property. This contains a key, optionally a
250 * label, and optionally one or more values.
255 * The name of this property.
259 * Zero or more labels.
263 * The values in this property.
265 std::vector<property_value> values;
267 * Value indicating that this is a valid property. If a parse error
268 * occurs, then this value is false.
272 * Parses a string property value, i.e. a value enclosed in double quotes.
274 void parse_string(text_input_buffer &input);
276 * Parses one or more 32-bit values enclosed in angle brackets.
278 void parse_cells(text_input_buffer &input, int cell_size);
280 * Parses an array of bytes, contained within square brackets.
282 void parse_bytes(text_input_buffer &input);
284 * Parses a reference. This is a node label preceded by an ampersand
285 * symbol, which should expand to the full path to that node.
287 * Note: The specification says that the target of such a reference is
288 * a node name, however dtc assumes that it is a label, and so we
289 * follow their interpretation for compatibility.
291 void parse_reference(text_input_buffer &input);
293 * Parse a predefined macro definition for a property.
295 void parse_define(text_input_buffer &input, define_map *defines);
297 * Constructs a new property from two input buffers, pointing to the
298 * struct and strings tables in the device tree blob, respectively.
299 * The structs input buffer is assumed to have just consumed the
302 property(input_buffer &structs, input_buffer &strings);
304 * Parses a new property from the input buffer.
306 property(text_input_buffer &input,
310 define_map *defines);
313 * Creates an empty property.
315 property(std::string &&k, string_set &&l=string_set())
316 : key(k), labels(l), valid(true) {}
320 property(property &p) : key(p.key), labels(p.labels), values(p.values),
323 * Factory method for constructing a new property. Attempts to parse a
324 * property from the input, and returns it on success. On any parse
325 * error, this will return 0.
327 static property_ptr parse_dtb(input_buffer &structs,
328 input_buffer &strings);
330 * Factory method for constructing a new property. Attempts to parse a
331 * property from the input, and returns it on success. On any parse
332 * error, this will return 0.
334 static property_ptr parse(text_input_buffer &input,
336 string_set &&labels=string_set(),
337 bool semicolonTerminated=true,
338 define_map *defines=0);
340 * Iterator type used for accessing the values of a property.
342 typedef std::vector<property_value>::iterator value_iterator;
344 * Returns an iterator referring to the first value in this property.
346 inline value_iterator begin()
348 return values.begin();
351 * Returns an iterator referring to the last value in this property.
353 inline value_iterator end()
358 * Adds a new value to an existing property.
360 inline void add_value(property_value v)
365 * Returns the key for this property.
367 inline std::string get_key()
372 * Writes the property to the specified writer. The property name is a
373 * reference into the strings table.
375 void write(dtb::output_writer &writer, dtb::string_table &strings);
377 * Writes in DTS format to the specified file, at the given indent
378 * level. This will begin the line with the number of tabs specified
379 * as the indent level and then write the property in the most
380 * applicable way that it can determine.
382 void write_dts(FILE *file, int indent);
386 * Class encapsulating a device tree node. Nodes may contain properties and
393 * The labels for this node, if any. Node labels are used as the
394 * targets for cross references.
396 std::unordered_set<std::string> labels;
398 * The name of the node.
402 * The unit address of the node, which is optionally written after the
403 * name followed by an at symbol.
405 std::string unit_address;
407 * The type for the property vector.
409 typedef std::vector<property_ptr> property_vector;
411 * Iterator type for child nodes.
413 typedef std::vector<node_ptr>::iterator child_iterator;
416 * Adaptor to use children in range-based for loops.
420 child_range(node &nd) : n(nd) {}
421 child_iterator begin() { return n.child_begin(); }
422 child_iterator end() { return n.child_end(); }
427 * Adaptor to use properties in range-based for loops.
429 struct property_range
431 property_range(node &nd) : n(nd) {}
432 property_vector::iterator begin() { return n.property_begin(); }
433 property_vector::iterator end() { return n.property_end(); }
438 * The properties contained within this node.
440 property_vector props;
442 * The children of this node.
444 std::vector<node_ptr> children;
446 * Children that should be deleted from this node when merging.
448 std::unordered_set<std::string> deleted_children;
450 * Properties that should be deleted from this node when merging.
452 std::unordered_set<std::string> deleted_props;
454 * A flag indicating whether this node is valid. This is set to false
455 * if an error occurs during parsing.
459 * Parses a name inside a node, writing the string passed as the last
460 * argument as an error if it fails.
462 std::string parse_name(text_input_buffer &input,
466 * Constructs a new node from two input buffers, pointing to the struct
467 * and strings tables in the device tree blob, respectively.
469 node(input_buffer &structs, input_buffer &strings);
471 * Parses a new node from the specified input buffer. This is called
472 * when the input cursor is on the open brace for the start of the
473 * node. The name, and optionally label and unit address, should have
474 * already been parsed.
476 node(text_input_buffer &input,
478 std::unordered_set<std::string> &&l,
482 * Comparison function for properties, used when sorting the properties
483 * vector. Orders the properties based on their names.
485 static inline bool cmp_properties(property_ptr &p1, property_ptr &p2);
488 return p1->get_key() < p2->get_key();
492 * Comparison function for nodes, used when sorting the children
493 * vector. Orders the nodes based on their names or, if the names are
494 * the same, by the unit addresses.
496 static inline bool cmp_children(node_ptr &c1, node_ptr &c2);
499 * Sorts the node's properties and children into alphabetical order and
500 * recursively sorts the children.
504 * Returns an iterator for the first child of this node.
506 inline child_iterator child_begin()
508 return children.begin();
511 * Returns an iterator after the last child of this node.
513 inline child_iterator child_end()
515 return children.end();
518 * Returns a range suitable for use in a range-based for loop describing
519 * the children of this node.
521 inline child_range child_nodes()
523 return child_range(*this);
526 * Accessor for the deleted children.
528 inline const std::unordered_set<std::string> &deleted_child_nodes()
530 return deleted_children;
533 * Accessor for the deleted properties
535 inline const std::unordered_set<std::string> &deleted_properties()
537 return deleted_props;
540 * Returns a range suitable for use in a range-based for loop describing
541 * the properties of this node.
543 inline property_range properties()
545 return property_range(*this);
548 * Returns an iterator after the last property of this node.
550 inline property_vector::iterator property_begin()
552 return props.begin();
555 * Returns an iterator for the first property of this node.
557 inline property_vector::iterator property_end()
562 * Factory method for constructing a new node. Attempts to parse a
563 * node in DTS format from the input, and returns it on success. On
564 * any parse error, this will return 0. This should be called with the
565 * cursor on the open brace of the property, after the name and so on
568 static node_ptr parse(text_input_buffer &input,
570 std::unordered_set<std::string> &&label=std::unordered_set<std::string>(),
571 std::string &&address=std::string(),
572 define_map *defines=0);
574 * Factory method for constructing a new node. Attempts to parse a
575 * node in DTB format from the input, and returns it on success. On
576 * any parse error, this will return 0. This should be called with the
577 * cursor on the open brace of the property, after the name and so on
580 static node_ptr parse_dtb(input_buffer &structs, input_buffer &strings);
582 * Returns a property corresponding to the specified key, or 0 if this
583 * node does not contain a property of that name.
585 property_ptr get_property(const std::string &key);
587 * Adds a new property to this node.
589 inline void add_property(property_ptr &p)
594 * Merges a node into this one. Any properties present in both are
595 * overridden, any properties present in only one are preserved.
597 void merge_node(node_ptr other);
599 * Write this node to the specified output. Although nodes do not
600 * refer to a string table directly, their properties do. The string
601 * table passed as the second argument is used for the names of
602 * properties within this node and its children.
604 void write(dtb::output_writer &writer, dtb::string_table &strings);
606 * Writes the current node as DTS to the specified file. The second
607 * parameter is the indent level. This function will start every line
608 * with this number of tabs.
610 void write_dts(FILE *file, int indent);
612 * Recursively visit this node and then its children.
614 void visit(std::function<void(node&)>);
618 * Class encapsulating the entire parsed FDT. This is the top-level class,
619 * which parses the entire DTS representation and write out the finished
626 * Type used for node paths. A node path is sequence of names and unit
629 typedef std::vector<std::pair<std::string,std::string> > node_path;
631 * Name that we should use for phandle nodes.
639 /** Create both nodes. */
644 * The format that we should use for writing phandles.
646 phandle_format phandle_node_name;
648 * Flag indicating that this tree is valid. This will be set to false
653 * Type used for memory reservations. A reservation is two 64-bit
654 * values indicating a base address and length in memory that the
655 * kernel should not use. The high 32 bits are ignored on 32-bit
658 typedef std::pair<uint64_t, uint64_t> reservation;
660 * The memory reserves table.
662 std::vector<reservation> reservations;
664 * Root node. All other nodes are children of this node.
668 * Mapping from names to nodes. Only unambiguous names are recorded,
669 * duplicate names are stored as (node*)-1.
671 std::unordered_map<std::string, node*> node_names;
673 * A map from labels to node paths. When resolving cross references,
674 * we look up referenced nodes in this and replace the cross reference
675 * with the full path to its target.
677 std::unordered_map<std::string, node_path> node_paths;
679 * A collection of property values that are references to other nodes.
680 * These should be expanded to the full path of their targets.
682 std::vector<property_value*> cross_references;
684 * A collection of property values that refer to phandles. These will
685 * be replaced by the value of the phandle property in their
688 std::vector<property_value*> phandles;
690 * The names of nodes that target phandles.
692 std::unordered_set<std::string> phandle_targets;
694 * A collection of input buffers that we are using. These input
695 * buffers are the ones that own their memory, and so we must preserve
696 * them for the lifetime of the device tree.
698 std::vector<std::unique_ptr<input_buffer>> buffers;
700 * A map of used phandle values to nodes. All phandles must be unique,
701 * so we keep a set of ones that the user explicitly provides in the
702 * input to ensure that we don't reuse them.
704 * This is a map, rather than a set, because we also want to be able to
705 * find phandles that were provided by the user explicitly when we are
708 std::unordered_map<uint32_t, node*> used_phandles;
710 * Paths to search for include files. This contains a set of
711 * nul-terminated strings, which are not owned by this class and so
712 * must be freed separately.
714 std::vector<std::string> include_paths;
716 * Dictionary of predefined macros provided on the command line.
720 * The default boot CPU, specified in the device tree header.
724 * The number of empty reserve map entries to generate in the blob.
726 uint32_t spare_reserve_map_entries;
728 * The minimum size in bytes of the blob.
730 uint32_t minimum_blob_size;
732 * The number of bytes of padding to add to the end of the blob.
734 uint32_t blob_padding;
736 * Visit all of the nodes recursively, and if they have labels then add
737 * them to the node_paths and node_names vectors so that they can be
738 * used in resolving cross references. Also collects phandle
739 * properties that have been explicitly added.
741 void collect_names_recursive(node_ptr &n, node_path &path);
743 * Assign phandle properties to all nodes that have been referenced and
744 * require one. This method will recursively visit the tree starting at
745 * the node that it is passed.
747 void assign_phandles(node_ptr &n, uint32_t &next);
749 * Calls the recursive version of this method on every root node.
751 void collect_names();
753 * Resolves all cross references. Any properties that refer to another
754 * node must have their values replaced by either the node path or
757 void resolve_cross_references();
759 * Parses a dts file in the given buffer and adds the roots to the parsed
760 * set. The `read_header` argument indicates whether the header has
761 * already been read. Some dts files place the header in an include,
762 * rather than in the top-level file.
764 void parse_file(text_input_buffer &input,
765 std::vector<node_ptr> &roots,
768 * Template function that writes a dtb blob using the specified writer.
769 * The writer defines the output format (assembly, blob).
771 template<class writer>
775 * Returns the node referenced by the property. If this is a tree that
776 * is in source form, then we have a string that we can use to index
777 * the cross_references array and so we can just look that up.
779 node *referenced_node(property_value &v);
781 * Writes this FDT as a DTB to the specified output.
783 void write_binary(int fd);
785 * Writes this FDT as an assembly representation of the DTB to the
786 * specified output. The result can then be assembled and linked into
789 void write_asm(int fd);
791 * Writes the tree in DTS (source) format.
793 void write_dts(int fd);
795 * Default constructor. Creates a valid, but empty FDT.
797 device_tree() : phandle_node_name(EPAPR), valid(true),
798 boot_cpu(0), spare_reserve_map_entries(0),
799 minimum_blob_size(0), blob_padding(0) {}
801 * Constructs a device tree from the specified file name, referring to
802 * a file that contains a device tree blob.
804 void parse_dtb(const std::string &fn, FILE *depfile);
806 * Constructs a device tree from the specified file name, referring to
807 * a file that contains device tree source.
809 void parse_dts(const std::string &fn, FILE *depfile);
811 * Returns whether this tree is valid.
813 inline bool is_valid()
818 * Sets the format for writing phandle properties.
820 inline void set_phandle_format(phandle_format f)
822 phandle_node_name = f;
825 * Returns a pointer to the root node of this tree. No ownership
828 inline const node_ptr &get_root() const
833 * Sets the physical boot CPU.
835 void set_boot_cpu(uint32_t cpu)
840 * Sorts the tree. Useful for debugging device trees.
847 * Adds a path to search for include files. The argument must be a
848 * nul-terminated string representing the path. The device tree keeps
849 * a pointer to this string, but does not own it: the caller is
850 * responsible for freeing it if required.
852 void add_include_path(const char *path)
855 include_paths.push_back(std::move(p));
858 * Sets the number of empty reserve map entries to add.
860 void set_empty_reserve_map_entries(uint32_t e)
862 spare_reserve_map_entries = e;
865 * Sets the minimum size, in bytes, of the blob.
867 void set_blob_minimum_size(uint32_t s)
869 minimum_blob_size = s;
872 * Sets the amount of padding to add to the blob.
874 void set_blob_padding(uint32_t p)
879 * Parses a predefined macro value.
881 bool parse_define(const char *def);