Index: head/usr.bin/dtc/Makefile =================================================================== --- head/usr.bin/dtc/Makefile (revision 292875) +++ head/usr.bin/dtc/Makefile (revision 292876) @@ -1,13 +1,13 @@ # $FreeBSD$ PROG_CXX=dtc SRCS= dtc.cc input_buffer.cc string.cc dtb.cc fdt.cc checking.cc MAN= dtc.1 WARNS?= 3 -CXXFLAGS+= -std=c++11 +CXXFLAGS+= -std=c++11 -fno-rtti -fno-exceptions NO_SHARED?=NO .include Index: head/usr.bin/dtc/checking.cc =================================================================== --- head/usr.bin/dtc/checking.cc (revision 292875) +++ head/usr.bin/dtc/checking.cc (revision 292876) @@ -1,259 +1,259 @@ /*- * Copyright (c) 2013 David Chisnall * All rights reserved. * * This software was developed by SRI International and the University of * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237) * ("CTSRD"), as part of the DARPA CRASH research programme. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * $FreeBSD$ */ #include "checking.hh" #include namespace dtc { namespace fdt { namespace checking { namespace { /** * Checker that verifies that every node that has children has * #address-cells and #size-cells properties. */ struct address_cells_checker : public checker { address_cells_checker(const char *name) : checker(name) {} - virtual bool check_node(device_tree *tree, const node_ptr &n) + virtual bool check_node(device_tree *, const node_ptr &n) { // If this has no children, it trivially meets the // conditions. if (n->child_begin() == n->child_end()) { return true; } bool found_address = false; bool found_size = false; for (auto i=n->property_begin(), e=n->property_end() ; i!=e ; ++i) { if (!found_address) { found_address = ((*i)->get_key() == "#address-cells"); } if (!found_size) { found_size = ((*i)->get_key() == "#size-cells"); } if (found_size && found_address) { break; } } if (!found_address) { report_error("Missing #address-cells property"); } if (!found_size) { report_error("Missing #size-cells property"); } return found_address && found_size; } }; } // anonymous namespace bool checker::visit_node(device_tree *tree, const node_ptr &n) { path.push_back(std::make_pair(n->name, n->unit_address)); // Check this node if (!check_node(tree, n)) { return false; } // Now check its properties for (auto i=n->property_begin(), e=n->property_end() ; i!=e ; ++i) { if (!check_property(tree, n, *i)) { return false; } } // And then recursively check the children for (node::child_iterator i=n->child_begin(), e=n->child_end() ; i!=e ; ++i) { if (!visit_node(tree, *i)) { return false; } } path.pop_back(); return true; } void checker::report_error(const char *errmsg) { fprintf(stderr, "Error: %s, while checking node: ", errmsg); for (auto &p : path) { putc('/', stderr); p.first.dump(); if (!(p.second.empty())) { putc('@', stderr); p.second.dump(); } } fprintf(stderr, " [-W%s]\n", checker_name); } bool property_checker::check_property(device_tree *tree, const node_ptr &n, property_ptr p) { if (p->get_key() == key) { if (!check(tree, n, p)) { report_error("property check failed"); return false; } } return true; } bool -property_size_checker::check(device_tree *tree, const node_ptr &n, property_ptr p) +property_size_checker::check(device_tree *, const node_ptr &, property_ptr p) { uint32_t psize = 0; for (property::value_iterator i=p->begin(),e=p->end() ; i!=e ; ++i) { if (!i->is_binary()) { return false; } psize += i->byte_data.size(); } return psize == size; } template void check_manager::add_property_type_checker(const char *name, string prop) { checkers.insert(std::make_pair(string(name), new property_type_checker(name, prop))); } void check_manager::add_property_size_checker(const char *name, string prop, uint32_t size) { checkers.insert(std::make_pair(string(name), new property_size_checker(name, prop, size))); } check_manager::~check_manager() { while (checkers.begin() != checkers.end()) { delete checkers.begin()->second; checkers.erase(checkers.begin()); } while (disabled_checkers.begin() != disabled_checkers.end()) { delete disabled_checkers.begin()->second; disabled_checkers.erase(disabled_checkers.begin()); } } check_manager::check_manager() { // NOTE: All checks listed here MUST have a corresponding line // in the man page! add_property_type_checker( "type-compatible", string("compatible")); add_property_type_checker( "type-model", string("model")); add_property_size_checker("type-phandle", string("phandle"), 4); disabled_checkers.insert(std::make_pair(string("cells-attributes"), new address_cells_checker("cells-attributes"))); } bool check_manager::run_checks(device_tree *tree, bool keep_going) { bool success = true; for (auto &i : checkers) { success &= i.second->check_tree(tree); if (!(success || keep_going)) { break; } } return success; } bool check_manager::disable_checker(string name) { auto checker = checkers.find(name); if (checker != checkers.end()) { disabled_checkers.insert(std::make_pair(name, checker->second)); checkers.erase(checker); return true; } return false; } bool check_manager::enable_checker(string name) { auto checker = disabled_checkers.find(name); if (checker != disabled_checkers.end()) { checkers.insert(std::make_pair(name, checker->second)); disabled_checkers.erase(checker); return true; } return false; } } // namespace checking } // namespace fdt } // namespace dtc Index: head/usr.bin/dtc/checking.hh =================================================================== --- head/usr.bin/dtc/checking.hh (revision 292875) +++ head/usr.bin/dtc/checking.hh (revision 292876) @@ -1,308 +1,308 @@ /*- * Copyright (c) 2013 David Chisnall * All rights reserved. * * This software was developed by SRI International and the University of * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237) * ("CTSRD"), as part of the DARPA CRASH research programme. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * $FreeBSD$ */ #ifndef _CHECKING_HH_ #define _CHECKING_HH_ #include "string.hh" #include "fdt.hh" namespace dtc { namespace fdt { namespace checking { /** * Base class for all checkers. This will visit the entire tree and perform * semantic checks defined in subclasses. Note that device trees are generally * small (a few dozen nodes at most) and so we optimise for flexibility and * extensibility here, not for performance. Each checker will visit the entire * tree. */ class checker { /** * The path to the current node being checked. This is used for * printing error messages. */ device_tree::node_path path; /** * The name of the checker. This is used for printing error messages * and for enabling / disabling specific checkers from the command * line. */ const char *checker_name; /** * Visits each node, calling the checker functions on properties and * nodes. */ bool visit_node(device_tree *tree, const node_ptr &n); protected: /** * Prints the error message, along with the path to the node that * caused the error and the name of the checker. */ void report_error(const char *errmsg); public: /** * Constructor. Takes the name of this checker, which is which is used * when reporting errors. */ checker(const char *name) : checker_name(name) {} /** * Virtual destructor in case any subclasses need to do cleanup. */ virtual ~checker() {} /** * Method for checking that a node is valid. The root class version * does nothing, subclasses should override this. */ - virtual bool check_node(device_tree *tree, const node_ptr &n) + virtual bool check_node(device_tree *, const node_ptr &) { return true; } /** * Method for checking that a property is valid. The root class * version does nothing, subclasses should override this. */ - virtual bool check_property(device_tree *tree, const node_ptr &n, property_ptr p) + virtual bool check_property(device_tree *, const node_ptr &, property_ptr ) { return true; } /** * Runs the checker on the specified device tree. */ bool check_tree(fdt::device_tree *tree) { return visit_node(tree, tree->get_root()); } }; /** * Abstract base class for simple property checks. This class defines a check * method for subclasses, which is invoked only when it finds a property with * the matching name. To define simple property checkers, just subclass this * and override the check() method. */ class property_checker : public checker { /** * The name of the property that this checker is looking for. */ string key; public: /** * Implementation of the generic property-checking method that checks * for a property with the name specified in the constructor */ virtual bool check_property(device_tree *tree, const node_ptr &n, property_ptr p); /** * Constructor. Takes the name of the checker and the name of the * property to check. */ property_checker(const char* name, string property_name) : checker(name), key(property_name) {} /** * The check method, which subclasses should implement. */ virtual bool check(device_tree *tree, const node_ptr &n, property_ptr p) = 0; }; /** * Property type checker. */ template struct property_type_checker : public property_checker { /** * Constructor, takes the name of the checker and the name of the * property to check as arguments. */ property_type_checker(const char* name, string property_name) : property_checker(name, property_name) {} virtual bool check(device_tree *tree, const node_ptr &n, property_ptr p) = 0; }; /** * Empty property checker. This checks that the property has no value. */ template<> struct property_type_checker : public property_checker { property_type_checker(const char* name, string property_name) : property_checker(name, property_name) {} - virtual bool check(device_tree *tree, const node_ptr &n, property_ptr p) + virtual bool check(device_tree *, const node_ptr &, property_ptr p) { return p->begin() == p->end(); } }; /** * String property checker. This checks that the property has exactly one * value, which is a string. */ template<> struct property_type_checker : public property_checker { property_type_checker(const char* name, string property_name) : property_checker(name, property_name) {} - virtual bool check(device_tree *tree, const node_ptr &n, property_ptr p) + virtual bool check(device_tree *, const node_ptr &, property_ptr p) { return (p->begin() + 1 == p->end()) && p->begin()->is_string(); } }; /** * String list property checker. This checks that the property has at least * one value, all of which are strings. */ template<> struct property_type_checker : public property_checker { property_type_checker(const char* name, string property_name) : property_checker(name, property_name) {} - virtual bool check(device_tree *tree, const node_ptr &n, property_ptr p) + virtual bool check(device_tree *, const node_ptr &, property_ptr p) { for (property::value_iterator i=p->begin(),e=p->end() ; i!=e ; ++i) { if (!(i->is_string() || i->is_string_list())) { return false; } } return p->begin() != p->end(); } }; /** * Phandle property checker. This checks that the property has exactly one * value, which is a valid phandle. */ template<> struct property_type_checker : public property_checker { property_type_checker(const char* name, string property_name) : property_checker(name, property_name) {} - virtual bool check(device_tree *tree, const node_ptr &n, property_ptr p) + virtual bool check(device_tree *tree, const node_ptr &, property_ptr p) { return (p->begin() + 1 == p->end()) && (tree->referenced_node(*p->begin()) != 0); } }; /** * Check that a property has the correct size. */ struct property_size_checker : public property_checker { /** * The expected size of the property. */ uint32_t size; public: /** * Constructor, takes the name of the checker, the name of the property * to check, and its expected size as arguments. */ property_size_checker(const char* name, string property_name, uint32_t bytes) : property_checker(name, property_name), size(bytes) {} /** * Check, validates that the property has the correct size. */ virtual bool check(device_tree *tree, const node_ptr &n, property_ptr p); }; /** * The check manager is the interface to running the checks. This allows * default checks to be enabled, non-default checks to be enabled, and so on. */ class check_manager { /** * The enabled checkers, indexed by their names. The name is used when * disabling checkers from the command line. When this manager runs, * it will only run the checkers from this map. */ std::unordered_map checkers; /** * The disabled checkers. Moving checkers to this list disables them, * but allows them to be easily moved back. */ std::unordered_map disabled_checkers; /** * Helper function for adding a property value checker. */ template void add_property_type_checker(const char *name, string prop); /** * Helper function for adding a simple type checker. */ void add_property_type_checker(const char *name, string prop); /** * Helper function for adding a property value checker. */ void add_property_size_checker(const char *name, string prop, uint32_t size); public: /** * Delete all of the checkers that are part of this checker manager. */ ~check_manager(); /** * Default constructor, creates check manager containing all of the * default checks. */ check_manager(); /** * Run all of the checks on the specified tree. */ bool run_checks(device_tree *tree, bool keep_going); /** * Disables the named checker. */ bool disable_checker(string name); /** * Enables the named checker. */ bool enable_checker(string name); }; } // namespace checking } // namespace fdt } // namespace dtc #endif // !_CHECKING_HH_ Index: head/usr.bin/dtc/dtb.hh =================================================================== --- head/usr.bin/dtc/dtb.hh (revision 292875) +++ head/usr.bin/dtc/dtb.hh (revision 292876) @@ -1,365 +1,365 @@ /*- * Copyright (c) 2013 David Chisnall * All rights reserved. * * This software was developed by SRI International and the University of * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237) * ("CTSRD"), as part of the DARPA CRASH research programme. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * $FreeBSD$ */ #ifndef _DTB_HH_ #define _DTB_HH_ #include #include "string.hh" #include namespace dtc { /** * The dtb namespace contains code related to the generation of device tree * blobs, the binary representation of flattened device trees. The abstract * tree representation calls into this code to generate the output. */ namespace dtb { /** The token types in the DTB, as defined by ยง7.4.1 of the ePAPR * specification. All of these values are written in big-endian format in the * output. */ enum token_type { /** * Marker indicating the start of a node in the tree. This is followed * by the nul-terminated name. If a unit address is specified, then * the name also contains the address, with an @ symbol between the end * of the name and the start of the address. * * The name is then padded such that the next token begins on a 4-byte * boundary. The node may contain properties, other nodes, both, or be * empty. */ FDT_BEGIN_NODE = 0x00000001, /** * Marker indicating the end of a node. */ FDT_END_NODE = 0x00000002, /** * The start of a property. This is followed by two 32-bit big-endian * values. The first indicates the length of the property value, the * second its index in the strings table. It is then followed by the * property value, if the value is of non-zero length. */ FDT_PROP = 0x00000003, /** * Ignored token. May be used for padding inside DTB nodes. */ FDT_NOP = 0x00000004, /** * Marker indicating the end of the tree. */ FDT_END = 0x00000009 }; /** * Returns the token as a string. This is used for debugging and for printing * human-friendly error messages about malformed DTB input. */ inline const char *token_type_name(token_type t) { switch(t) { case FDT_BEGIN_NODE: return "FDT_BEGIN_NODE"; case FDT_END_NODE: return "FDT_END_NODE"; case FDT_PROP: return "FDT_PROP"; case FDT_NOP: return "FDT_NOP"; case FDT_END: return "FDT_END"; } assert(0); } /** * Abstract class for writing a section of the output. We create one * of these for each section that needs to be written. It is intended to build * a temporary buffer of the output in memory and then write it to a file * stream. The size can be returned after all of the data has been written * into the internal buffer, so the sizes of the three tables can be calculated * before storing them in the buffer. */ struct output_writer { /** * Writes a label into the output stream. This is only applicable for * assembly output, where the labels become symbols that can be * resolved at link time. */ virtual void write_label(string name) = 0; /** * Writes a comment into the output stream. Useful only when debugging * the output. */ virtual void write_comment(string name) = 0; /** * Writes a string. A nul terminator is implicitly added. */ virtual void write_string(string name) = 0; /** * Writes a single 8-bit value. */ virtual void write_data(uint8_t) = 0; /** * Writes a single 32-bit value. The value is written in big-endian * format, but should be passed in the host's native endian. */ virtual void write_data(uint32_t) = 0; /** * Writes a single 64-bit value. The value is written in big-endian * format, but should be passed in the host's native endian. */ virtual void write_data(uint64_t) = 0; /** * Writes the collected output to the specified file descriptor. */ virtual void write_to_file(int fd) = 0; /** * Returns the number of bytes. */ virtual uint32_t size() = 0; /** * Helper for writing tokens to the output stream. This writes a * comment above the token describing its value, for easier debugging * of the output. */ inline void write_token(token_type t) { write_comment(token_type_name(t)); write_data((uint32_t)t); } /** * Helper function that writes a byte buffer to the output, one byte at * a time. */ void write_data(byte_buffer b); }; /** * Binary file writer. This class is responsible for writing the DTB output * directly in blob format. */ class binary_writer : public output_writer { /** * The internal buffer used to store the blob while it is being * constructed. */ byte_buffer buffer; public: /** * The binary format does not support labels, so this method * does nothing. */ - virtual void write_label(string name) {} + virtual void write_label(string) {} /** * Comments are ignored by the binary writer. */ - virtual void write_comment(string name) {} + virtual void write_comment(string) {} virtual void write_string(string name); virtual void write_data(uint8_t v); virtual void write_data(uint32_t v); virtual void write_data(uint64_t v); virtual void write_to_file(int fd); virtual uint32_t size(); }; /** * Assembly writer. This class is responsible for writing the output in an * assembly format that is suitable for linking into a kernel, loader, and so * on. */ class asm_writer : public output_writer { /** * The internal buffer for temporary values. Note that this actually * contains ASCII text, but it is a byte buffer so that we can just * copy strings across as-is. */ byte_buffer buffer; /** * The number of bytes written to the current line. This is used to * allow line wrapping, where we aim to write four .byte directives to * make the alignment clearer. */ int byte_count; /** * The current number of bytes written. This is the number in binary * format, not the number of bytes in the buffer. */ uint32_t bytes_written; /** * Writes a C string directly to the output as-is. This is mainly used * for writing directives. */ void write_string(const char *c); /** * Writes the string, starting on a new line. */ void write_line(const char *c); /** * Writes a byte in binary format. This will emit a single .byte * directive, with up to four per line. */ void write_byte(uint8_t b); public: asm_writer() : byte_count(0), bytes_written(0) {} virtual void write_label(string name); virtual void write_comment(string name); virtual void write_string(string name); virtual void write_data(uint8_t v); virtual void write_data(uint32_t v); virtual void write_data(uint64_t v); virtual void write_to_file(int fd); virtual uint32_t size(); }; /** * Class encapsulating the device tree blob header. This class stores all of * the values found in the header and is responsible for writing them to the * output. */ struct header { /** * Magic value, used to validate that this really is a device tree * blob. Should always be set to 0xd00dfeed. */ uint32_t magic; /** * The total size of the blob, including header, reservations, strings * table, and padding. */ uint32_t totalsize; /** * The offset from the start of the blob of the struct table (i.e. the * part of the blob containing the entire device tree). */ uint32_t off_dt_struct; /** * The offset from the start of the blob of the strings table. */ uint32_t off_dt_strings; /** * The offset of the reservation map from the start of the blob. */ uint32_t off_mem_rsvmap; /** * The version of the blob. This should always be 17. */ uint32_t version; /** * The earliest version of the DTB specification with which this blob * is backwards compatible. This should always be 16. */ uint32_t last_comp_version; /** * The ID of the CPU where this boots. */ uint32_t boot_cpuid_phys; /** * The size of the strings table. */ uint32_t size_dt_strings; /** * The size of the struct table. */ uint32_t size_dt_struct; /** * Writes the entire header to the specified output buffer. */ void write(output_writer &out); /** * Reads the header from bits binary representation in a blob. */ bool read_dtb(input_buffer &input); /** * Default constructor. Initialises the values that have sensible * defaults, leaves the others blank. */ header() : magic(0xd00dfeed), version(17), last_comp_version(16), boot_cpuid_phys(0) {} }; /** * Class encapsulating the string table. FDT strings are stored in a string * section. This maintains a map from strings to their offsets in the strings * section. * * Note: We don't currently do suffix matching, which may save a small amount * of space. */ class string_table { /** * Map from strings to their offset. */ std::map string_offsets; /** * The strings, in the order in which they should be written to the * output. The order must be stable - adding another string must not * change the offset of any that we have already referenced - and so we * simply write the strings in the order that they are passed. */ std::vector strings; /** * The current size of the strings section. */ uint32_t size; public: /** * Default constructor, creates an empty strings table. */ string_table() : size(0) {} /** * Adds a string to the table, returning the offset from the start * where it will be written. If the string is already present, this * will return its existing offset, otherwise it will return a new * offset. */ uint32_t add_string(string str); /** * Writes the strings table to the specified output. */ void write(dtb::output_writer &writer); }; } // namespace dtb } // namespace dtc #endif // !_DTB_HH_ Index: head/usr.bin/dtc/fdt.cc =================================================================== --- head/usr.bin/dtc/fdt.cc (revision 292875) +++ head/usr.bin/dtc/fdt.cc (revision 292876) @@ -1,1588 +1,1616 @@ /*- * Copyright (c) 2013 David Chisnall * All rights reserved. * * This software was developed by SRI International and the University of * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237) * ("CTSRD"), as part of the DARPA CRASH research programme. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * $FreeBSD$ */ #define __STDC_LIMIT_MACROS 1 #include "fdt.hh" #include "dtb.hh" #include #include #include #include #include #include #include #include #include #include #include namespace dtc { namespace fdt { uint32_t property_value::get_as_uint32() { if (byte_data.size() != 4) { return 0; } uint32_t v = 0; v &= byte_data[0] << 24; v &= byte_data[1] << 16; v &= byte_data[2] << 8; v &= byte_data[3] << 0; return v; } void property_value::push_to_buffer(byte_buffer &buffer) { if (!byte_data.empty()) { buffer.insert(buffer.end(), byte_data.begin(), byte_data.end()); } else { string_data.push_to_buffer(buffer, true); // Trailing nul buffer.push_back(0); } } void property_value::write_dts(FILE *file) { resolve_type(); switch (type) { default: assert(0 && "Invalid type"); case STRING: case STRING_LIST: case CROSS_REFERENCE: write_as_string(file); break; case PHANDLE: write_as_cells(file); break; case BINARY: if (byte_data.size() % 4 == 0) { write_as_cells(file); break; } write_as_bytes(file); break; } } void property_value::resolve_type() { if (type != UNKNOWN) { return; } if (byte_data.empty()) { type = STRING; return; } if (byte_data.back() == 0) { bool is_all_printable = true; int nuls = 0; int bytes = 0; bool lastWasNull = false; for (auto i : byte_data) { bytes++; is_all_printable &= (i == '\0') || isprint(i); if (i == '\0') { // If there are two nulls in a row, then we're probably binary. if (lastWasNull) { type = BINARY; return; } nuls++; lastWasNull = true; } else { lastWasNull = false; } if (!is_all_printable) { break; } } if ((is_all_printable && (bytes > nuls)) || bytes == 0) { type = STRING; if (nuls > 1) { type = STRING_LIST; } return; } } type = BINARY; } void property_value::write_as_string(FILE *file) { putc('"', file); if (byte_data.empty()) { string_data.print(file); } else { bool hasNull = (byte_data.back() == '\0'); // Remove trailing null bytes from the string before printing as dts. if (hasNull) { byte_data.pop_back(); } for (auto i : byte_data) { // FIXME Escape tabs, newlines, and so on. if (i == '\0') { fputs("\", \"", file); continue; } putc(i, file); } if (hasNull) { byte_data.push_back('\0'); } } putc('"', file); } void property_value::write_as_cells(FILE *file) { putc('<', file); assert((byte_data.size() % 4) == 0); for (auto i=byte_data.begin(), e=byte_data.end(); i!=e ; ++i) { uint32_t v = 0; v = (v << 8) | *i; ++i; v = (v << 8) | *i; ++i; v = (v << 8) | *i; ++i; v = (v << 8) | *i; fprintf(file, "0x%" PRIx32, v); if (i+1 != e) { putc(' ', file); } } putc('>', file); } void property_value::write_as_bytes(FILE *file) { putc('[', file); for (auto i=byte_data.begin(), e=byte_data.end(); i!=e ; i++) { fprintf(file, "%02hhx", *i); if (i+1 != e) { putc(' ', file); } } putc(']', file); } void property::parse_string(input_buffer &input) { property_value v; assert(input[0] == '"'); ++input; const char *start = (const char*)input; int length = 0; while (char c = input[0]) { if (c == '"' && input[-1] != '\\') { input.consume('"'); break; } ++input; ++length; } v.string_data = string(start, length); values.push_back(v); } void property::parse_cells(input_buffer &input, int cell_size) { - unsigned long long cell_max; - switch (cell_size) - { - case 8: - cell_max = UINT8_MAX; - break; - case 16: - cell_max = UINT16_MAX; - break; - case 32: - cell_max = UINT32_MAX; - break; - case 64: - cell_max = UINT64_MAX; - break; - default: - assert(0 && "Invalid cell size!"); - } assert(input[0] == '<'); ++input; property_value v; input.next_token(); while (!input.consume('>')) { input.next_token(); // If this is a phandle then we need to get the name of the // referenced node if (input.consume('&')) { if (cell_size != 32) { input.parse_error("reference only permitted in 32-bit arrays"); valid = false; return; } input.next_token(); // FIXME: We should support full paths here, but we // don't. string referenced = string::parse_node_name(input); if (referenced.empty()) { input.parse_error("Expected node name"); valid = false; return; } input.next_token(); // If we already have some bytes, make the phandle a // separate component. if (!v.byte_data.empty()) { values.push_back(v); v = property_value(); } v.string_data = referenced; v.type = property_value::PHANDLE; values.push_back(v); v = property_value(); } else { //FIXME: We should support labels in the middle //of these, but we don't. unsigned long long val; - if (!input.consume_integer(val)) + if (!input.consume_integer_expression(val)) { input.parse_error("Expected numbers in array of cells"); valid = false; return; } - if (val > cell_max) - { - fprintf(stderr, "%lld > %lld\n", val, cell_max); - input.parse_error("Value out of range"); - valid = false; - return; - } switch (cell_size) { case 8: v.byte_data.push_back(val); break; case 16: push_big_endian(v.byte_data, (uint16_t)val); break; case 32: push_big_endian(v.byte_data, (uint32_t)val); break; case 64: push_big_endian(v.byte_data, (uint64_t)val); break; default: assert(0 && "Invalid cell size!"); } input.next_token(); } } // Don't store an empty string value here. if (v.byte_data.size() > 0) { values.push_back(v); } } void property::parse_bytes(input_buffer &input) { assert(input[0] == '['); ++input; property_value v; input.next_token(); while (!input.consume(']')) { { //FIXME: We should support //labels in the middle of //these, but we don't. uint8_t val; if (!input.consume_hex_byte(val)) { input.parse_error("Expected hex bytes in array of bytes"); valid = false; return; } v.byte_data.push_back(val); input.next_token(); } } values.push_back(v); } void property::parse_reference(input_buffer &input) { assert(input[0] == '&'); ++input; input.next_token(); property_value v; v.string_data = string::parse_node_name(input); if (v.string_data.empty()) { input.parse_error("Expected node name"); valid = false; return; } v.type = property_value::CROSS_REFERENCE; values.push_back(v); } property::property(input_buffer &structs, input_buffer &strings) { uint32_t name_offset; uint32_t length; valid = structs.consume_binary(length) && structs.consume_binary(name_offset); if (!valid) { fprintf(stderr, "Failed to read property\n"); return; } // Find the name input_buffer name_buffer = strings.buffer_from_offset(name_offset); if (name_buffer.empty()) { fprintf(stderr, "Property name offset %" PRIu32 " is past the end of the strings table\n", name_offset); valid = false; return; } key = string(name_buffer); // If we're empty, do not push anything as value. if (!length) return; // Read the value uint8_t byte; property_value v; for (uint32_t i=0 ; ifind(name)) == defines->end())) { input.parse_error("Undefined property name\n"); valid = false; return; } values.push_back((*found).second->values[0]); } property::property(input_buffer &input, string k, string l, bool semicolonTerminated, define_map *defines) : key(k), label(l), valid(true) { do { input.next_token(); switch (input[0]) { case '$': { parse_define(input, defines); if (valid) { break; } } default: input.parse_error("Invalid property value."); valid = false; return; case '/': { unsigned long long bits = 0; valid = input.consume("/bits/"); input.next_token(); valid &= input.consume_integer(bits); if ((bits != 8) && (bits != 16) && (bits != 32) && (bits != 64)) { input.parse_error("Invalid size for elements"); valid = false; } if (!valid) return; input.next_token(); if (input[0] != '<') { input.parse_error("/bits/ directive is only valid on arrays"); valid = false; return; } parse_cells(input, bits); break; } case '"': parse_string(input); break; case '<': parse_cells(input, 32); break; case '[': parse_bytes(input); break; case '&': parse_reference(input); break; case ';': { break; } } input.next_token(); } while (input.consume(',')); if (semicolonTerminated && !input.consume(';')) { input.parse_error("Expected ; at end of property"); valid = false; } } property_ptr property::parse_dtb(input_buffer &structs, input_buffer &strings) { property_ptr p(new property(structs, strings)); if (!p->valid) { p = nullptr; } return p; } property_ptr property::parse(input_buffer &input, string key, string label, bool semicolonTerminated, define_map *defines) { property_ptr p(new property(input, key, label, semicolonTerminated, defines)); if (!p->valid) { p = nullptr; } return p; } void property::write(dtb::output_writer &writer, dtb::string_table &strings) { writer.write_token(dtb::FDT_PROP); byte_buffer value_buffer; for (value_iterator i=begin(), e=end() ; i!=e ; ++i) { i->push_to_buffer(value_buffer); } writer.write_data((uint32_t)value_buffer.size()); writer.write_comment(key); writer.write_data(strings.add_string(key)); writer.write_data(value_buffer); } bool property_value::try_to_merge(property_value &other) { resolve_type(); switch (type) { case UNKNOWN: __builtin_unreachable(); assert(0); return false; case EMPTY: *this = other; case STRING: case STRING_LIST: case CROSS_REFERENCE: return false; case PHANDLE: case BINARY: if (other.type == PHANDLE || other.type == BINARY) { type = BINARY; byte_data.insert(byte_data.end(), other.byte_data.begin(), other.byte_data.end()); return true; } } return false; } void property::write_dts(FILE *file, int indent) { for (int i=0 ; i *vals = &values; std::vector v; // If we've got multiple values then try to merge them all together. if (values.size() > 1) { vals = &v; v.push_back(values.front()); for (auto i=(++begin()), e=end() ; i!=e ; ++i) { if (!v.back().try_to_merge(*i)) { v.push_back(*i); } } } fputs(" = ", file); for (auto i=vals->begin(), e=vals->end() ; i!=e ; ++i) { i->write_dts(file); if (i+1 != e) { putc(',', file); putc(' ', file); } } } fputs(";\n", file); } string node::parse_name(input_buffer &input, bool &is_property, const char *error) { if (!valid) { return string(); } input.next_token(); if (is_property) { return string::parse_property_name(input); } string n = string::parse_node_or_property_name(input, is_property); if (n.empty()) { if (n.empty()) { input.parse_error(error); valid = false; } } return n; } +void +node::visit(std::function fn) +{ + fn(*this); + for (auto &&c : children) + { + c->visit(fn); + } +} + node::node(input_buffer &structs, input_buffer &strings) : valid(true) { const char *name_start = (const char*)structs; int name_length = 0; while (structs[0] != '\0' && structs[0] != '@') { name_length++; ++structs; } name = string(name_start, name_length); if (structs[0] == '@') { ++structs; name_start = (const char*)structs; name_length = 0; while (structs[0] != '\0') { name_length++; ++structs; } unit_address = string(name_start, name_length); } ++structs; uint32_t token; while (structs.consume_binary(token)) { switch (token) { default: fprintf(stderr, "Unexpected token 0x%" PRIx32 " while parsing node.\n", token); valid = false; return; // Child node, parse it. case dtb::FDT_BEGIN_NODE: { node_ptr child = node::parse_dtb(structs, strings); if (child == 0) { valid = false; return; } children.push_back(std::move(child)); break; } // End of this node, no errors. case dtb::FDT_END_NODE: return; // Property, parse it. case dtb::FDT_PROP: { property_ptr prop = property::parse_dtb(structs, strings); if (prop == 0) { valid = false; return; } - properties.push_back(prop); + props.push_back(prop); break; } break; // End of structs table. Should appear after // the end of the last node. case dtb::FDT_END: fprintf(stderr, "Unexpected FDT_END token while parsing node.\n"); valid = false; return; // NOPs are padding. Ignore them. case dtb::FDT_NOP: break; } } fprintf(stderr, "Failed to read token from structs table while parsing node.\n"); valid = false; return; } node::node(input_buffer &input, string n, string l, string a, define_map *defines) : label(l), name(n), unit_address(a), valid(true) { if (!input.consume('{')) { input.parse_error("Expected { to start new device tree node.\n"); } input.next_token(); while (valid && !input.consume('}')) { // flag set if we find any characters that are only in // the property name character set, not the node bool is_property = false; string child_name, child_label, child_address; child_name = parse_name(input, is_property, "Expected property or node name"); if (input.consume(':')) { // Node labels can contain any characters? The // spec doesn't say, so we guess so... is_property = false; child_label = child_name; child_name = parse_name(input, is_property, "Expected property or node name"); } if (input.consume('@')) { child_address = parse_name(input, is_property, "Expected unit address"); } if (!valid) { return; } input.next_token(); // If we're parsing a property, then we must actually do that. if (input.consume('=')) { property_ptr p = property::parse(input, child_name, child_label, true, defines); if (p == 0) { valid = false; } else { - properties.push_back(p); + props.push_back(p); } } else if (!is_property && input[0] == ('{')) { node_ptr child = node::parse(input, child_name, child_label, child_address, defines); if (child) { children.push_back(std::move(child)); } else { valid = false; } } else if (input.consume(';')) { - properties.push_back(property_ptr(new property(child_name, child_label))); + props.push_back(property_ptr(new property(child_name, child_label))); } else { input.parse_error("Error parsing property."); valid = false; } input.next_token(); } input.consume(';'); } bool node::cmp_properties(property_ptr &p1, property_ptr &p2) { return p1->get_key() < p2->get_key(); } bool node::cmp_children(node_ptr &c1, node_ptr &c2) { if (c1->name == c2->name) { return c1->unit_address < c2->unit_address; } return c1->name < c2->name; } void node::sort() { std::sort(property_begin(), property_end(), cmp_properties); std::sort(child_begin(), child_end(), cmp_children); - for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i) + for (auto &c : child_nodes()) { - (*i)->sort(); + c->sort(); } } node_ptr node::parse(input_buffer &input, string name, string label, string address, define_map *defines) { node_ptr n(new node(input, name, label, address, defines)); if (!n->valid) { n = 0; } return n; } node_ptr node::parse_dtb(input_buffer &structs, input_buffer &strings) { node_ptr n(new node(structs, strings)); if (!n->valid) { n = 0; } return n; } property_ptr node::get_property(string key) { - for (auto &i : properties) + for (auto &i : props) { if (i->get_key() == key) { return i; } } return 0; } void node::merge_node(node_ptr other) { if (!other->label.empty()) { label = other->label; } // Note: this is an O(n*m) operation. It might be sensible to // optimise this if we find that there are nodes with very // large numbers of properties, but for typical usage the // entire vector will fit (easily) into cache, so iterating // over it repeatedly isn't that expensive. - for (auto &p : other->properties) + for (auto &p : other->properties()) { bool found = false; - for (auto i=property_begin(), e=property_end() ; i!=e ; ++i) + for (auto &mp : properties()) { - if ((*i)->get_key() == p->get_key()) + if (mp->get_key() == p->get_key()) { - *i = p; + mp = p; found = true; break; } } if (!found) { add_property(p); } } for (auto &c : other->children) { bool found = false; for (auto &i : children) { if (i->name == c->name && i->unit_address == c->unit_address) { i->merge_node(std::move(c)); found = true; break; } } if (!found) { children.push_back(std::move(c)); } } } void node::write(dtb::output_writer &writer, dtb::string_table &strings) { writer.write_token(dtb::FDT_BEGIN_NODE); byte_buffer name_buffer; name.push_to_buffer(name_buffer); if (unit_address != string()) { name_buffer.push_back('@'); unit_address.push_to_buffer(name_buffer); } writer.write_comment(name); writer.write_data(name_buffer); writer.write_data((uint8_t)0); - for (auto i=property_begin(), e=property_end() ; i!=e ; ++i) + for (auto p : properties()) { - (*i)->write(writer, strings); + p->write(writer, strings); } - for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i) + for (auto &c : child_nodes()) { - (*i)->write(writer, strings); + c->write(writer, strings); } writer.write_token(dtb::FDT_END_NODE); } void node::write_dts(FILE *file, int indent) { for (int i=0 ; iwrite_dts(file, indent+1); + p->write_dts(file, indent+1); } - for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i) + for (auto &c : child_nodes()) { - (*i)->write_dts(file, indent+1); + c->write_dts(file, indent+1); } for (int i=0 ; ilabel; path.push_back(std::make_pair(n->name, n->unit_address)); if (name != string()) { if (node_names.find(name) == node_names.end()) { node_names.insert(std::make_pair(name, n.get())); node_paths.insert(std::make_pair(name, path)); } else { node_names[name] = (node*)-1; auto i = node_paths.find(name); if (i != node_paths.end()) { node_paths.erase(name); } fprintf(stderr, "Label not unique: "); name.dump(); fprintf(stderr, ". References to this label will not be resolved."); } } - for (node::child_iterator i=n->child_begin(), e=n->child_end() ; i!=e ; ++i) + for (auto &c : n->child_nodes()) { - collect_names_recursive(*i, path); + collect_names_recursive(c, path); } path.pop_back(); // Now we collect the phandles and properties that reference // other nodes. - for (auto i=n->property_begin(), e=n->property_end() ; i!=e ; ++i) + for (auto &p : n->properties()) { - for (property::value_iterator p=(*i)->begin(),pe=(*i)->end() ; p!=pe ; ++p) + for (auto &v : *p) { - if (p->is_phandle()) + if (v.is_phandle()) { - phandles.push_back(&*p); + phandles.push_back(&v); } - if (p->is_cross_reference()) + if (v.is_cross_reference()) { - cross_references.push_back(&*p); + cross_references.push_back(&v); } } - if ((*i)->get_key() == string("phandle") || - (*i)->get_key() == string("linux,phandle")) + if (p->get_key() == string("phandle") || + p->get_key() == string("linux,phandle")) { - if ((*i)->begin()->byte_data.size() != 4) + if (p->begin()->byte_data.size() != 4) { fprintf(stderr, "Invalid phandle value for node "); n->name.dump(); fprintf(stderr, ". Should be a 4-byte value.\n"); valid = false; } else { - uint32_t phandle = (*i)->begin()->get_as_uint32(); + uint32_t phandle = p->begin()->get_as_uint32(); used_phandles.insert(std::make_pair(phandle, n.get())); } } } } void device_tree::collect_names() { node_path p; node_names.clear(); node_paths.clear(); cross_references.clear(); phandles.clear(); collect_names_recursive(root, p); } void device_tree::resolve_cross_references() { for (auto *pv : cross_references) { node_path path = node_paths[pv->string_data]; // Skip the first name in the path. It's always "", and implicitly / for (auto p=path.begin()+1, pe=path.end() ; p!=pe ; ++p) { pv->byte_data.push_back('/'); p->first.push_to_buffer(pv->byte_data); if (!(p->second.empty())) { pv->byte_data.push_back('@'); p->second.push_to_buffer(pv->byte_data); + pv->byte_data.push_back(0); } } } - uint32_t phandle = 1; + std::unordered_set phandle_set; for (auto &i : phandles) { + phandle_set.insert(i); + } + std::vector sorted_phandles; + root->visit([&](node &n) { + for (auto &p : n.properties()) + { + for (auto &v : *p) + { + if (phandle_set.count(&v)) + { + sorted_phandles.push_back(&v); + } + } + } + }); + assert(sorted_phandles.size() == phandles.size()); + + uint32_t phandle = 1; + for (auto &i : sorted_phandles) + { string target_name = i->string_data; node *target = node_names[target_name]; if (target == 0) { fprintf(stderr, "Failed to find node with label: "); target_name.dump(); fprintf(stderr, "\n"); valid = 0; return; } // If there is an existing phandle, use it property_ptr p = target->get_property("phandle"); if (p == 0) { p = target->get_property("linux,phandle"); } if (p == 0) { // Otherwise insert a new phandle node property_value v; while (used_phandles.find(phandle) != used_phandles.end()) { // Note that we only don't need to // store this phandle in the set, // because we are monotonically // increasing the value of phandle and // so will only ever revisit this value // if we have used 2^32 phandles, at // which point our blob won't fit in // any 32-bit system and we've done // something badly wrong elsewhere // already. phandle++; } push_big_endian(v.byte_data, phandle++); if (phandle_node_name == BOTH || phandle_node_name == LINUX) { p.reset(new property(string("linux,phandle"))); p->add_value(v); target->add_property(p); } if (phandle_node_name == BOTH || phandle_node_name == EPAPR) { p.reset(new property(string("phandle"))); p->add_value(v); target->add_property(p); } } p->begin()->push_to_buffer(i->byte_data); assert(i->byte_data.size() == 4); } } -void -device_tree::parse_file(input_buffer &input, +bool +device_tree::parse_include(input_buffer &input, const std::string &dir, std::vector &roots, FILE *depfile, bool &read_header) { - input.next_token(); - // Read the header - if (input.consume("/dts-v1/;")) + if (!input.consume("/include/")) { - read_header = true; + return false; } - input.next_token(); - while(input.consume("/include/")) + bool reallyInclude = true; + if (input.consume("if ")) { - bool reallyInclude = true; - if (input.consume("if ")) - { - input.next_token(); - string name = string::parse_property_name(input); - // XXX: Error handling - if (defines.find(name) == defines.end()) - { - reallyInclude = false; - } - input.consume('/'); - } input.next_token(); - if (!input.consume('"')) + string name = string::parse_property_name(input); + // XXX: Error handling + if (defines.find(name) == defines.end()) { - input.parse_error("Expected quoted filename"); - valid = false; - return; + reallyInclude = false; } - int length = 0; - while (input[length] != '"') length++; + input.consume('/'); + } + input.next_token(); + if (!input.consume('"')) + { + input.parse_error("Expected quoted filename"); + valid = false; + return false; + } + int length = 0; + while (input[length] != '"') length++; - std::string file((const char*)input, length); - std::string include_file = dir + '/' + file; - assert(input.consume(file.c_str())); + std::string file((const char*)input, length); + std::string include_file = dir + '/' + file; + input.consume(file.c_str()); + if (!reallyInclude) + { input.consume('"'); input.next_token(); - if (!reallyInclude) - { - continue; - } + return true; + } - input_buffer *include_buffer = buffer_for_file(include_file.c_str()); + input_buffer *include_buffer = buffer_for_file(include_file.c_str(), false); - if (include_buffer == 0) + if (include_buffer == 0) + { + for (auto i : include_paths) { - for (auto i : include_paths) + include_file = i + '/' + file; + include_buffer = buffer_for_file(include_file.c_str()); + if (include_buffer != 0) { - include_file = i + '/' + file; - include_buffer = buffer_for_file(include_file.c_str()); - if (include_buffer != 0) - { - break; - } + break; } } - if (depfile != 0) - { - putc(' ', depfile); - fputs(include_file.c_str(), depfile); - } - if (include_buffer == 0) - { - valid = false; - return; - } - parse_file(*include_buffer, dir, roots, depfile, read_header); } + if (depfile != 0) + { + putc(' ', depfile); + fputs(include_file.c_str(), depfile); + } + if (include_buffer == 0) + { + input.parse_error("Unable to locate input file"); + input.consume('"'); + input.next_token(); + valid = false; + return true; + } + input.consume('"'); input.next_token(); + parse_file(*include_buffer, dir, roots, depfile, read_header); + return true; +} + +void +device_tree::parse_file(input_buffer &input, + const std::string &dir, + std::vector &roots, + FILE *depfile, + bool &read_header) +{ + input.next_token(); + // Read the header + if (input.consume("/dts-v1/;")) + { + read_header = true; + } + input.next_token(); + input.next_token(); if (!read_header) { input.parse_error("Expected /dts-v1/; version string"); } + while(parse_include(input, dir, roots, depfile, read_header)) {} // Read any memory reservations while(input.consume("/memreserve/")) { unsigned long long start, len; input.next_token(); // Read the start and length. - if (!(input.consume_integer(start) && + if (!(input.consume_integer_expression(start) && (input.next_token(), - input.consume_integer(len)))) + input.consume_integer_expression(len)))) { input.parse_error("Expected size on /memreserve/ node."); } input.next_token(); input.consume(';'); reservations.push_back(reservation(start, len)); } input.next_token(); + while(parse_include(input, dir, roots, depfile, read_header)) {} while (valid && !input.finished()) { node_ptr n; if (input.consume('/')) { input.next_token(); n = node::parse(input, string(), string(), string(), &defines); } else if (input.consume('&')) { input.next_token(); string name = string::parse_node_name(input); input.next_token(); n = node::parse(input, name, string(), string(), &defines); } else { input.parse_error("Failed to find root node /."); } if (n) { roots.push_back(std::move(n)); } else { valid = false; } input.next_token(); + while(parse_include(input, dir, roots, depfile, read_header)) {} } } input_buffer* -device_tree::buffer_for_file(const char *path) +device_tree::buffer_for_file(const char *path, bool warn) { if (string(path) == string("-")) { input_buffer *b = new stream_input_buffer(); if (b) { std::unique_ptr ptr(b); buffers.push_back(std::move(ptr)); } return b; } int source = open(path, O_RDONLY); if (source == -1) { - fprintf(stderr, "Unable to open file '%s'. %s\n", path, strerror(errno)); + if (warn) + { + fprintf(stderr, "Unable to open file '%s'. %s\n", path, strerror(errno)); + } return 0; } struct stat st; if (fstat(source, &st) == 0 && S_ISDIR(st.st_mode)) { fprintf(stderr, "File %s is a directory\n", path); close(source); return 0; } input_buffer *b = new mmap_input_buffer(source); // Keep the buffer that owns the memory around for the lifetime // of this FDT. Ones simply referring to it may have shorter // lifetimes. if (b) { std::unique_ptr ptr(b); buffers.push_back(std::move(ptr)); } close(source); return b; } template void device_tree::write(int fd) { dtb::string_table st; dtb::header head; writer head_writer; writer reservation_writer; writer struct_writer; writer strings_writer; // Build the reservation table reservation_writer.write_comment(string("Memory reservations")); reservation_writer.write_label(string("dt_reserve_map")); for (auto &i : reservations) { reservation_writer.write_comment(string("Reservation start")); reservation_writer.write_data(i.first); reservation_writer.write_comment(string("Reservation length")); reservation_writer.write_data(i.first); } // Write n spare reserve map entries, plus the trailing 0. for (uint32_t i=0 ; i<=spare_reserve_map_entries ; i++) { reservation_writer.write_data((uint64_t)0); reservation_writer.write_data((uint64_t)0); } struct_writer.write_comment(string("Device tree")); struct_writer.write_label(string("dt_struct_start")); root->write(struct_writer, st); struct_writer.write_token(dtb::FDT_END); struct_writer.write_label(string("dt_struct_end")); st.write(strings_writer); // Find the strings size before we stick padding on the end. // Note: We should possibly use a new writer for the padding. head.size_dt_strings = strings_writer.size(); // Stick the padding in the strings writer, but after the // marker indicating that it's the end. // Note: We probably should add a padding call to the writer so // that the asm back end can write padding directives instead // of a load of 0 bytes. for (uint32_t i=0 ; i(fd); } void device_tree::write_asm(int fd) { write(fd); } void device_tree::write_dts(int fd) { FILE *file = fdopen(fd, "w"); fputs("/dts-v1/;\n\n", file); if (!reservations.empty()) { const char msg[] = "/memreserve/"; fwrite(msg, sizeof(msg), 1, file); for (auto &i : reservations) { fprintf(file, " %" PRIx64 " %" PRIx64, i.first, i.second); } fputs(";\n\n", file); } putc('/', file); putc(' ', file); root->write_dts(file, 0); fclose(file); } void -device_tree::parse_dtb(const char *fn, FILE *depfile) +device_tree::parse_dtb(const char *fn, FILE *) { input_buffer *in = buffer_for_file(fn); if (in == 0) { valid = false; return; } input_buffer &input = *in; dtb::header h; valid = h.read_dtb(input); boot_cpu = h.boot_cpuid_phys; if (h.last_comp_version > 17) { fprintf(stderr, "Don't know how to read this version of the device tree blob"); valid = false; } if (!valid) { return; } input_buffer reservation_map = input.buffer_from_offset(h.off_mem_rsvmap, 0); uint64_t start, length; do { if (!(reservation_map.consume_binary(start) && reservation_map.consume_binary(length))) { fprintf(stderr, "Failed to read memory reservation table\n"); valid = false; return; } } while (!((start == 0) && (length == 0))); input_buffer struct_table = input.buffer_from_offset(h.off_dt_struct, h.size_dt_struct); input_buffer strings_table = input.buffer_from_offset(h.off_dt_strings, h.size_dt_strings); uint32_t token; if (!(struct_table.consume_binary(token) && (token == dtb::FDT_BEGIN_NODE))) { fprintf(stderr, "Expected FDT_BEGIN_NODE token.\n"); valid = false; return; } root = node::parse_dtb(struct_table, strings_table); if (!(struct_table.consume_binary(token) && (token == dtb::FDT_END))) { fprintf(stderr, "Expected FDT_END token after parsing root node.\n"); valid = false; return; } valid = (root != 0); } void device_tree::parse_dts(const char *fn, FILE *depfile) { input_buffer *in = buffer_for_file(fn); std::string dir(dirname((char*)fn)); if (in == 0) { valid = false; return; } std::vector roots; input_buffer &input = *in; bool read_header = false; parse_file(input, dir, roots, depfile, read_header); switch (roots.size()) { case 0: valid = false; input.parse_error("Failed to find root node /."); return; case 1: root = std::move(roots[0]); break; default: { root = std::move(roots[0]); for (auto i=++(roots.begin()), e=roots.end() ; i!=e ; ++i) { auto &node = *i; string name = node->name; if (name == string()) { root->merge_node(std::move(node)); } else { auto existing = node_names.find(name); if (existing == node_names.end()) { collect_names(); existing = node_names.find(name); } if (existing == node_names.end()) { fprintf(stderr, "Unable to merge node: "); name.dump(); fprintf(stderr, "\n"); } existing->second->merge_node(std::move(node)); } } } } collect_names(); resolve_cross_references(); } bool device_tree::parse_define(const char *def) { char *val = strchr(def, '='); if (!val) { if (strlen(def) != 0) { string name(def); defines[name]; return true; } return false; } string name(def, val-def); val++; input_buffer in = input_buffer(val, strlen(val)); property_ptr p = property::parse(in, name, string(), false); if (p) defines[name] = p; return (bool)p; } } // namespace fdt } // namespace dtc Index: head/usr.bin/dtc/fdt.hh =================================================================== --- head/usr.bin/dtc/fdt.hh (revision 292875) +++ head/usr.bin/dtc/fdt.hh (revision 292876) @@ -1,823 +1,866 @@ /*- * Copyright (c) 2013 David Chisnall * All rights reserved. * * This software was developed by SRI International and the University of * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237) * ("CTSRD"), as part of the DARPA CRASH research programme. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * $FreeBSD$ */ #ifndef _FDT_HH_ #define _FDT_HH_ #include #include #include #include +#include #include "util.hh" #include "string.hh" namespace dtc { namespace dtb { struct output_writer; class string_table; } namespace fdt { class property; class node; /** * Type for (owned) pointers to properties. */ typedef std::shared_ptr property_ptr; /** * Owning pointer to a node. */ typedef std::unique_ptr node_ptr; /** * Map from macros to property pointers. */ typedef std::unordered_map define_map; /** * Properties may contain a number of different value, each with a different * label. This class encapsulates a single value. */ struct property_value { /** * The label for this data. This is usually empty. */ string label; /** * If this value is a string, or something resolved from a string (a * reference) then this contains the source string. */ string string_data; /** * The data that should be written to the final output. */ byte_buffer byte_data; /** * Enumeration describing the possible types of a value. Note that * property-coded arrays will appear simply as binary (or possibly * string, if they happen to be nul-terminated and printable), and must * be checked separately. */ enum value_type { /** * This is a list of strings. When read from source, string * lists become one property value for each string, however * when read from binary we have a single property value * incorporating the entire text, with nul bytes separating the * strings. */ STRING_LIST, /** * This property contains a single string. */ STRING, /** * This is a binary value. Check the size of byte_data to * determine how many bytes this contains. */ BINARY, /** This contains a short-form address that should be replaced * by a fully-qualified version. This will only appear when * the input is a device tree source. When parsed from a * device tree blob, the cross reference will have already been * resolved and the property value will be a string containing * the full path of the target node. */ CROSS_REFERENCE, /** * This is a phandle reference. When parsed from source, the * string_data will contain the node label for the target and, * after cross references have been resolved, the binary data * will contain a 32-bit integer that should match the phandle * property of the target node. */ PHANDLE, /** * An empty property value. This will never appear on a real * property value, it is used by checkers to indicate that no * property values should exist for a property. */ EMPTY, /** * The type of this property has not yet been determined. */ UNKNOWN }; /** * The type of this property. */ value_type type; /** * Returns true if this value is a cross reference, false otherwise. */ inline bool is_cross_reference() { return is_type(CROSS_REFERENCE); } /** * Returns true if this value is a phandle reference, false otherwise. */ inline bool is_phandle() { return is_type(PHANDLE); } /** * Returns true if this value is a string, false otherwise. */ inline bool is_string() { return is_type(STRING); } /** * Returns true if this value is a string list (a nul-separated * sequence of strings), false otherwise. */ inline bool is_string_list() { return is_type(STRING_LIST); } /** * Returns true if this value is binary, false otherwise. */ inline bool is_binary() { return is_type(BINARY); } /** * Returns this property value as a 32-bit integer. Returns 0 if this * property value is not 32 bits long. The bytes in the property value * are assumed to be in big-endian format, but the return value is in * the host native endian. */ uint32_t get_as_uint32(); /** * Default constructor, specifying the label of the value. */ property_value(string l=string()) : label(l), type(UNKNOWN) {} /** * Writes the data for this value into an output buffer. */ void push_to_buffer(byte_buffer &buffer); /** * Writes the property value to the standard output. This uses the * following heuristics for deciding how to print the output: * * - If the value is nul-terminated and only contains printable * characters, it is written as a string. * - If it is a multiple of 4 bytes long, then it is printed as cells. * - Otherwise, it is printed as a byte buffer. */ void write_dts(FILE *file); /** * Tries to merge adjacent property values, returns true if it succeeds and * false otherwise. */ bool try_to_merge(property_value &other); private: /** * Returns whether the value is of the specified type. If the type of * the value has not yet been determined, then this calculates it. */ inline bool is_type(value_type v) { if (type == UNKNOWN) { resolve_type(); } return type == v; } /** * Determines the type of the value based on its contents. */ void resolve_type(); /** * Writes the property value to the specified file as a quoted string. * This is used when generating DTS. */ void write_as_string(FILE *file); /** * Writes the property value to the specified file as a sequence of * 32-bit big-endian cells. This is used when generating DTS. */ void write_as_cells(FILE *file); /** * Writes the property value to the specified file as a sequence of * bytes. This is used when generating DTS. */ void write_as_bytes(FILE *file); }; /** * A value encapsulating a single property. This contains a key, optionally a * label, and optionally one or more values. */ class property { /** * The name of this property. */ string key; /** * An optional label. */ string label; /** * The values in this property. */ std::vector values; /** * Value indicating that this is a valid property. If a parse error * occurs, then this value is false. */ bool valid; /** * Parses a string property value, i.e. a value enclosed in double quotes. */ void parse_string(input_buffer &input); /** * Parses one or more 32-bit values enclosed in angle brackets. */ void parse_cells(input_buffer &input, int cell_size); /** * Parses an array of bytes, contained within square brackets. */ void parse_bytes(input_buffer &input); /** * Parses a reference. This is a node label preceded by an ampersand * symbol, which should expand to the full path to that node. * * Note: The specification says that the target of such a reference is * a node name, however dtc assumes that it is a label, and so we * follow their interpretation for compatibility. */ void parse_reference(input_buffer &input); /** * Parse a predefined macro definition for a property. */ void parse_define(input_buffer &input, define_map *defines); /** * Constructs a new property from two input buffers, pointing to the * struct and strings tables in the device tree blob, respectively. * The structs input buffer is assumed to have just consumed the * FDT_PROP token. */ property(input_buffer &structs, input_buffer &strings); /** * Parses a new property from the input buffer. */ property(input_buffer &input, string k, string l, bool terminated, define_map *defines); public: /** * Creates an empty property. */ property(string k, string l=string()) : key(k), label(l), valid(true) {} /** * Copy constructor. */ property(property &p) : key(p.key), label(p.label), values(p.values), valid(p.valid) {} /** * Factory method for constructing a new property. Attempts to parse a * property from the input, and returns it on success. On any parse * error, this will return 0. */ static property_ptr parse_dtb(input_buffer &structs, input_buffer &strings); /** * Factory method for constructing a new property. Attempts to parse a * property from the input, and returns it on success. On any parse * error, this will return 0. */ static property_ptr parse(input_buffer &input, string key, string label=string(), bool semicolonTerminated=true, define_map *defines=0); /** * Iterator type used for accessing the values of a property. */ typedef std::vector::iterator value_iterator; /** * Returns an iterator referring to the first value in this property. */ inline value_iterator begin() { return values.begin(); } /** * Returns an iterator referring to the last value in this property. */ inline value_iterator end() { return values.end(); } /** * Adds a new value to an existing property. */ inline void add_value(property_value v) { values.push_back(v); } /** * Returns the key for this property. */ inline string get_key() { return key; } /** * Writes the property to the specified writer. The property name is a * reference into the strings table. */ void write(dtb::output_writer &writer, dtb::string_table &strings); /** * Writes in DTS format to the specified file, at the given indent * level. This will begin the line with the number of tabs specified * as the indent level and then write the property in the most * applicable way that it can determine. */ void write_dts(FILE *file, int indent); }; /** * Class encapsulating a device tree node. Nodes may contain properties and * other nodes. */ class node { public: /** * The label for this node, if any. Node labels are used as the * targets for cross references. */ string label; /** * The name of the node. */ string name; /** * The unit address of the node, which is optionally written after the * name followed by an at symbol. */ string unit_address; /** * The type for the property vector. */ typedef std::vector property_vector; + /** + * Iterator type for child nodes. + */ + typedef std::vector::iterator child_iterator; private: /** + * Adaptor to use children in range-based for loops. + */ + struct child_range + { + child_range(node &nd) : n(nd) {} + child_iterator begin() { return n.child_begin(); } + child_iterator end() { return n.child_end(); } + private: + node &n; + }; + /** + * Adaptor to use properties in range-based for loops. + */ + struct property_range + { + property_range(node &nd) : n(nd) {} + property_vector::iterator begin() { return n.property_begin(); } + property_vector::iterator end() { return n.property_end(); } + private: + node &n; + }; + /** * The properties contained within this node. */ - property_vector properties; + property_vector props; /** * The children of this node. */ std::vector children; /** * A flag indicating whether this node is valid. This is set to false * if an error occurs during parsing. */ bool valid; /** * Parses a name inside a node, writing the string passed as the last * argument as an error if it fails. */ string parse_name(input_buffer &input, bool &is_property, const char *error); /** * Constructs a new node from two input buffers, pointing to the struct * and strings tables in the device tree blob, respectively. */ node(input_buffer &structs, input_buffer &strings); /** * Parses a new node from the specified input buffer. This is called * when the input cursor is on the open brace for the start of the * node. The name, and optionally label and unit address, should have * already been parsed. */ node(input_buffer &input, string n, string l, string a, define_map*); /** * Comparison function for properties, used when sorting the properties * vector. Orders the properties based on their names. */ static inline bool cmp_properties(property_ptr &p1, property_ptr &p2); /* { return p1->get_key() < p2->get_key(); } */ /** * Comparison function for nodes, used when sorting the children * vector. Orders the nodes based on their names or, if the names are * the same, by the unit addresses. */ static inline bool cmp_children(node_ptr &c1, node_ptr &c2); public: /** * Sorts the node's properties and children into alphabetical order and * recursively sorts the children. */ void sort(); /** - * Iterator type for child nodes. - */ - typedef std::vector::iterator child_iterator; - /** * Returns an iterator for the first child of this node. */ inline child_iterator child_begin() { return children.begin(); } /** * Returns an iterator after the last child of this node. */ inline child_iterator child_end() { return children.end(); } + inline child_range child_nodes() + { + return child_range(*this); + } + inline property_range properties() + { + return property_range(*this); + } /** * Returns an iterator after the last property of this node. */ inline property_vector::iterator property_begin() { - return properties.begin(); + return props.begin(); } /** * Returns an iterator for the first property of this node. */ inline property_vector::iterator property_end() { - return properties.end(); + return props.end(); } /** * Factory method for constructing a new node. Attempts to parse a * node in DTS format from the input, and returns it on success. On * any parse error, this will return 0. This should be called with the * cursor on the open brace of the property, after the name and so on * have been parsed. */ static node_ptr parse(input_buffer &input, string name, string label=string(), string address=string(), define_map *defines=0); /** * Factory method for constructing a new node. Attempts to parse a * node in DTB format from the input, and returns it on success. On * any parse error, this will return 0. This should be called with the * cursor on the open brace of the property, after the name and so on * have been parsed. */ static node_ptr parse_dtb(input_buffer &structs, input_buffer &strings); /** * Returns a property corresponding to the specified key, or 0 if this * node does not contain a property of that name. */ property_ptr get_property(string key); /** * Adds a new property to this node. */ inline void add_property(property_ptr &p) { - properties.push_back(p); + props.push_back(p); } /** * Merges a node into this one. Any properties present in both are * overridden, any properties present in only one are preserved. */ void merge_node(node_ptr other); /** * Write this node to the specified output. Although nodes do not * refer to a string table directly, their properties do. The string * table passed as the second argument is used for the names of * properties within this node and its children. */ void write(dtb::output_writer &writer, dtb::string_table &strings); /** * Writes the current node as DTS to the specified file. The second * parameter is the indent level. This function will start every line * with this number of tabs. */ void write_dts(FILE *file, int indent); + /** + * Recursively visit this node and then its children. + */ + void visit(std::function); }; /** * Class encapsulating the entire parsed FDT. This is the top-level class, * which parses the entire DTS representation and write out the finished * version. */ class device_tree { public: /** * Type used for node paths. A node path is sequence of names and unit * addresses. */ typedef std::vector > node_path; /** * Name that we should use for phandle nodes. */ enum phandle_format { /** linux,phandle */ LINUX, /** phandle */ EPAPR, /** Create both nodes. */ BOTH }; private: /** * The format that we should use for writing phandles. */ phandle_format phandle_node_name; /** * Flag indicating that this tree is valid. This will be set to false * on parse errors. */ bool valid; /** * Type used for memory reservations. A reservation is two 64-bit * values indicating a base address and length in memory that the * kernel should not use. The high 32 bits are ignored on 32-bit * platforms. */ typedef std::pair reservation; /** * The memory reserves table. */ std::vector reservations; /** * Root node. All other nodes are children of this node. */ node_ptr root; /** * Mapping from names to nodes. Only unambiguous names are recorded, * duplicate names are stored as (node*)-1. */ std::unordered_map node_names; /** * A map from labels to node paths. When resolving cross references, * we look up referenced nodes in this and replace the cross reference * with the full path to its target. */ std::unordered_map node_paths; /** * A collection of property values that are references to other nodes. * These should be expanded to the full path of their targets. */ std::vector cross_references; /** * A collection of property values that refer to phandles. These will * be replaced by the value of the phandle property in their * destination. */ std::vector phandles; /** * The names of nodes that target phandles. */ std::unordered_set phandle_targets; /** * A collection of input buffers that we are using. These input * buffers are the ones that own their memory, and so we must preserve * them for the lifetime of the device tree. */ std::vector> buffers; /** * A map of used phandle values to nodes. All phandles must be unique, * so we keep a set of ones that the user explicitly provides in the * input to ensure that we don't reuse them. * * This is a map, rather than a set, because we also want to be able to * find phandles that were provided by the user explicitly when we are * doing checking. */ std::unordered_map used_phandles; /** * Paths to search for include files. This contains a set of * nul-terminated strings, which are not owned by this class and so * must be freed separately. */ std::vector include_paths; /** * Dictionary of predefined macros provided on the command line. */ define_map defines; /** * The default boot CPU, specified in the device tree header. */ uint32_t boot_cpu; /** * The number of empty reserve map entries to generate in the blob. */ uint32_t spare_reserve_map_entries; /** * The minimum size in bytes of the blob. */ uint32_t minimum_blob_size; /** * The number of bytes of padding to add to the end of the blob. */ uint32_t blob_padding; /** * Visit all of the nodes recursively, and if they have labels then add * them to the node_paths and node_names vectors so that they can be * used in resolving cross references. Also collects phandle * properties that have been explicitly added. */ void collect_names_recursive(node_ptr &n, node_path &path); /** * Assign phandle properties to all nodes that have been referenced and * require one. This method will recursively visit the tree starting at * the node that it is passed. */ void assign_phandles(node_ptr &n, uint32_t &next); /** * Calls the recursive version of this method on every root node. */ void collect_names(); /** * Resolves all cross references. Any properties that refer to another * node must have their values replaced by either the node path or * phandle value. */ void resolve_cross_references(); /** + * Parse a top-level include directive. + */ + bool parse_include(input_buffer &input, + const std::string &dir, + std::vector &roots, + FILE *depfile, + bool &read_header); + /** * Parses a dts file in the given buffer and adds the roots to the parsed * set. The `read_header` argument indicates whether the header has * already been read. Some dts files place the header in an include, * rather than in the top-level file. */ void parse_file(input_buffer &input, const std::string &dir, std::vector &roots, FILE *depfile, bool &read_header); /** * Allocates a new mmap()'d input buffer for use in parsing. This * object then keeps a reference to it, ensuring that it is not * deallocated until the device tree is destroyed. */ - input_buffer *buffer_for_file(const char *path); + input_buffer *buffer_for_file(const char *path, bool warn=true); /** * Template function that writes a dtb blob using the specified writer. * The writer defines the output format (assembly, blob). */ template void write(int fd); public: /** * Returns the node referenced by the property. If this is a tree that * is in source form, then we have a string that we can use to index * the cross_references array and so we can just look that up. */ node *referenced_node(property_value &v); /** * Writes this FDT as a DTB to the specified output. */ void write_binary(int fd); /** * Writes this FDT as an assembly representation of the DTB to the * specified output. The result can then be assembled and linked into * a program. */ void write_asm(int fd); /** * Writes the tree in DTS (source) format. */ void write_dts(int fd); /** * Default constructor. Creates a valid, but empty FDT. */ device_tree() : phandle_node_name(EPAPR), valid(true), boot_cpu(0), spare_reserve_map_entries(0), minimum_blob_size(0), blob_padding(0) {} /** * Constructs a device tree from the specified file name, referring to * a file that contains a device tree blob. */ void parse_dtb(const char *fn, FILE *depfile); /** * Constructs a device tree from the specified file name, referring to * a file that contains device tree source. */ void parse_dts(const char *fn, FILE *depfile); /** * Returns whether this tree is valid. */ inline bool is_valid() { return valid; } /** * Sets the format for writing phandle properties. */ inline void set_phandle_format(phandle_format f) { phandle_node_name = f; } /** * Returns a pointer to the root node of this tree. No ownership * transfer. */ inline const node_ptr &get_root() const { return root; } /** * Sets the physical boot CPU. */ void set_boot_cpu(uint32_t cpu) { boot_cpu = cpu; } /** * Sorts the tree. Useful for debugging device trees. */ void sort() { root->sort(); } /** * Adds a path to search for include files. The argument must be a * nul-terminated string representing the path. The device tree keeps * a pointer to this string, but does not own it: the caller is * responsible for freeing it if required. */ void add_include_path(const char *path) { std::string p(path); include_paths.push_back(std::move(p)); } /** * Sets the number of empty reserve map entries to add. */ void set_empty_reserve_map_entries(uint32_t e) { spare_reserve_map_entries = e; } /** * Sets the minimum size, in bytes, of the blob. */ void set_blob_minimum_size(uint32_t s) { minimum_blob_size = s; } /** * Sets the amount of padding to add to the blob. */ void set_blob_padding(uint32_t p) { blob_padding = p; } /** * Parses a predefined macro value. */ bool parse_define(const char *def); }; } // namespace fdt } // namespace dtc #endif // !_FDT_HH_ Index: head/usr.bin/dtc/input_buffer.cc =================================================================== --- head/usr.bin/dtc/input_buffer.cc (revision 292875) +++ head/usr.bin/dtc/input_buffer.cc (revision 292876) @@ -1,269 +1,831 @@ /*- * Copyright (c) 2013 David Chisnall * All rights reserved. * * This software was developed by SRI International and the University of * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237) * ("CTSRD"), as part of the DARPA CRASH research programme. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * $FreeBSD$ */ #include "input_buffer.hh" #include #include #include #include #include #include +#include +#ifndef NDEBUG +#include +#endif #include #include #include #ifndef MAP_PREFAULT_READ #define MAP_PREFAULT_READ 0 #endif namespace dtc { - void input_buffer::skip_spaces() { if (cursor >= size) { return; } if (cursor < 0) { return; } char c = buffer[cursor]; while ((c == ' ') || (c == '\t') || (c == '\n') || (c == '\f') || (c == '\v') || (c == '\r')) { cursor++; if (cursor > size) { c = '\0'; } else { c = buffer[cursor]; } } } input_buffer input_buffer::buffer_from_offset(int offset, int s) { if (s == 0) { s = size - offset; } if (offset > size) { return input_buffer(); } if (s > (size-offset)) { return input_buffer(); } return input_buffer(&buffer[offset], s); } bool input_buffer::consume(const char *str) { int len = strlen(str); if (len > size - cursor) { return false; } else { for (int i=0 ; idump(); + std::cerr << ") "; + } +#endif +}; + +/** + * Template class for unary operators. The `OpChar` template parameter is + * solely for debugging and makes it easy to print the expression. The `Op` + * template parameter is a function object that implements the operator that + * this class provides. Most of these are provided by the `` + * header. + */ +template +class unary_operator : public expression +{ + /** + * The subexpression for this unary operator. + */ + expression_ptr subexpr; + valty operator()() override + { + Op op; + return op((*subexpr)()); + } + /** + * All unary operators have the same precedence. They are all evaluated + * before binary expressions, but after parentheses. + */ + int precedence() override + { + return 3; + } + public: + unary_operator(expression_ptr p) : subexpr(std::move(p)) {} +#ifndef NDEBUG + void dump_impl() override + { + std::cerr << OpChar; + subexpr->dump(); + } +#endif +}; + +/** + * Abstract base class for binary operators. Allows the tree to be modified + * without knowing what the operations actually are. + */ +struct binary_operator_base : public expression +{ + /** + * The left side of the expression. + */ + expression_ptr lhs; + /** + * The right side of the expression. + */ + expression_ptr rhs; + /** + * Insert a node somewhere down the path of left children, until it would + * be preempting something that should execute first. + */ + void insert_left(binary_operator_base *new_left) + { + if (lhs->precedence() < new_left->precedence()) + { + new_left->rhs = std::move(lhs); + lhs.reset(new_left); + } + else + { + static_cast(lhs.get())->insert_left(new_left); + } + } +}; + +/** + * Template class for binary operators. The precedence and the operation are + * provided as template parameters. + */ +template +struct binary_operator : public binary_operator_base +{ + valty operator()() override + { + Op op; + return op((*lhs)(), (*rhs)()); + } + int precedence() override + { + return Precedence; + } +#ifdef NDEBUG + /** + * Constructor. Takes the name of the operator as an argument, for + * debugging. Only stores it in debug mode. + */ + binary_operator(const char *) {} +#else + const char *opName; + binary_operator(const char *o) : opName(o) {} + void dump_impl() override + { + lhs->dump(); + std::cerr << opName; + rhs->dump(); + } +#endif +}; + +/** + * Ternary conditional operators (`cond ? true : false`) are a special case - + * there are no other ternary operators. + */ +class ternary_conditional_operator : public expression +{ + /** + * The condition for the clause. + */ + expression_ptr cond; + /** + * The expression that this evaluates to if the condition is true. + */ + expression_ptr lhs; + /** + * The expression that this evaluates to if the condition is false. + */ + expression_ptr rhs; + valty operator()() override + { + return (*cond)() ? (*lhs)() : (*rhs)(); + } + int precedence() override + { + // The actual precedence of a ternary conditional operator is 15, but + // its associativity is the opposite way around to the other operators, + // so we fudge it slightly. + return 3; + } +#ifndef NDEBUG + void dump_impl() override + { + cond->dump(); + std::cerr << " ? "; + lhs->dump(); + std::cerr << " : "; + rhs->dump(); + } +#endif + public: + ternary_conditional_operator(expression_ptr c, + expression_ptr l, + expression_ptr r) : + cond(std::move(c)), lhs(std::move(l)), rhs(std::move(r)) {} +}; + +template +struct lshift +{ + constexpr T operator()(const T &lhs, const T &rhs) const + { + return lhs << rhs; + } +}; +template +struct rshift +{ + constexpr T operator()(const T &lhs, const T &rhs) const + { + return lhs >> rhs; + } +}; +template +struct unary_plus +{ + constexpr T operator()(const T &val) const + { + return +val; + } +}; +// TODO: Replace with std::bit_not once we can guarantee C++14 as a baseline. +template +struct bit_not +{ + constexpr T operator()(const T &val) const + { + return ~val; + } +}; + +} // anonymous namespace + + +expression_ptr input_buffer::parse_binary_expression(expression_ptr lhs) +{ + next_token(); + binary_operator_base *expr = nullptr; + char op = ((*this)[0]); + switch (op) + { + default: + return lhs; + case '+': + expr = new binary_operator<6, std::plus>("+"); + break; + case '-': + expr = new binary_operator<6, std::minus>("-"); + break; + case '%': + expr = new binary_operator<5, std::modulus>("%"); + break; + case '*': + expr = new binary_operator<5, std::multiplies>("*"); + break; + case '/': + expr = new binary_operator<5, std::divides>("/"); + break; + case '<': + cursor++; + switch ((*this)[0]) + { + default: + parse_error("Invalid operator"); + return nullptr; + case ' ': + case '(': + case '0'...'9': + cursor--; + expr = new binary_operator<8, std::less>("<"); + break; + case '=': + expr = new binary_operator<8, std::less_equal>("<="); + break; + case '<': + expr = new binary_operator<7, lshift>("<<"); + break; + } + break; + case '>': + cursor++; + switch ((*this)[0]) + { + default: + parse_error("Invalid operator"); + return nullptr; + case '(': + case ' ': + case '0'...'9': + cursor--; + expr = new binary_operator<8, std::greater>(">"); + break; + case '=': + expr = new binary_operator<8, std::greater_equal>(">="); + break; + case '>': + expr = new binary_operator<7, rshift>(">>"); + break; + return lhs; + } + break; + case '=': + if ((*this)[1] != '=') + { + parse_error("Invalid operator"); + return nullptr; + } + consume('='); + expr = new binary_operator<9, std::equal_to>("=="); + break; + case '!': + if ((*this)[1] != '=') + { + parse_error("Invalid operator"); + return nullptr; + } + cursor++; + expr = new binary_operator<9, std::not_equal_to>("!="); + break; + case '&': + if ((*this)[1] == '&') + { + expr = new binary_operator<13, std::logical_and>("&&"); + } + else + { + expr = new binary_operator<10, std::bit_and>("&"); + } + break; + case '|': + if ((*this)[1] == '|') + { + expr = new binary_operator<12, std::logical_or>("||"); + } + else + { + expr = new binary_operator<14, std::bit_or>("|"); + } + break; + case '?': + { + consume('?'); + expression_ptr true_case = parse_expression(); + next_token(); + if (!true_case || !consume(':')) + { + parse_error("Expected : in ternary conditional operator"); + return nullptr; + } + expression_ptr false_case = parse_expression(); + if (!false_case) + { + parse_error("Expected false condition for ternary operator"); + return nullptr; + } + return expression_ptr(new ternary_conditional_operator(std::move(lhs), + std::move(true_case), std::move(false_case))); + } + } + cursor++; + next_token(); + expression_ptr e(expr); + expression_ptr rhs(parse_expression()); + if (!rhs) + { + return nullptr; + } + expr->lhs = std::move(lhs); + if (rhs->precedence() < expr->precedence()) + { + expr->rhs = std::move(rhs); + } + else + { + // If we're a normal left-to-right expression, then we need to insert + // this as the far-left child node of the rhs expression + binary_operator_base *rhs_op = + static_cast(rhs.get()); + rhs_op->insert_left(expr); + e.release(); + return rhs; + } + return e; +} + +expression_ptr input_buffer::parse_expression(bool stopAtParen) +{ + next_token(); + unsigned long long leftVal; + expression_ptr lhs; + switch ((*this)[0]) + { + case '0'...'9': + if (!consume_integer(leftVal)) + { + return nullptr; + } + lhs.reset(new terminal_expr(leftVal)); + break; + case '(': + { + consume('('); + expression_ptr &&subexpr = parse_expression(); + if (!subexpr) + { + return nullptr; + } + lhs.reset(new paren_expression(std::move(subexpr))); + if (!consume(')')) + { + return nullptr; + } + if (stopAtParen) + { + return lhs; + } + break; + } + case '+': + { + consume('+'); + expression_ptr &&subexpr = parse_expression(); + if (!subexpr) + { + return nullptr; + } + lhs.reset(new unary_operator<'+', unary_plus>(std::move(subexpr))); + break; + } + case '-': + { + consume('-'); + expression_ptr &&subexpr = parse_expression(); + if (!subexpr) + { + return nullptr; + } + lhs.reset(new unary_operator<'-', std::negate>(std::move(subexpr))); + break; + } + case '!': + { + consume('!'); + expression_ptr &&subexpr = parse_expression(); + if (!subexpr) + { + return nullptr; + } + lhs.reset(new unary_operator<'!', std::logical_not>(std::move(subexpr))); + break; + } + case '~': + { + consume('~'); + expression_ptr &&subexpr = parse_expression(); + if (!subexpr) + { + return nullptr; + } + lhs.reset(new unary_operator<'~', bit_not>(std::move(subexpr))); + break; + } + } + if (!lhs) + { + return nullptr; + } + return parse_binary_expression(std::move(lhs)); +} + bool +input_buffer::consume_integer_expression(unsigned long long &outInt) +{ + switch ((*this)[0]) + { + case '(': + { + expression_ptr e(parse_expression(true)); + if (!e) + { + return false; + } + outInt = (*e)(); + return true; + } + case '0'...'9': + return consume_integer(outInt); + default: + return false; + } +} + +bool input_buffer::consume_hex_byte(uint8_t &outByte) { if (!ishexdigit((*this)[0]) && !ishexdigit((*this)[1])) { return false; } outByte = (digittoint((*this)[0]) << 4) | digittoint((*this)[1]); cursor += 2; return true; } input_buffer& input_buffer::next_token() { int start; do { start = cursor; skip_spaces(); // Parse /* comments if ((*this)[0] == '/' && (*this)[1] == '*') { // eat the start of the comment ++(*this); ++(*this); do { // Find the ending * of */ while ((**this != '\0') && (**this != '*')) { ++(*this); } // Eat the * ++(*this); } while ((**this != '\0') && (**this != '/')); // Eat the / ++(*this); } // Parse // comments if (((*this)[0] == '/' && (*this)[1] == '/')) { // eat the start of the comment ++(*this); ++(*this); // Find the ending of the line while (**this != '\n') { ++(*this); } // Eat the \n ++(*this); } } while (start != cursor); return *this; } void input_buffer::parse_error(const char *msg) { int line_count = 1; int line_start = 0; int line_end = cursor; for (int i=cursor ; i>0 ; --i) { if (buffer[i] == '\n') { line_count++; if (line_start == 0) { line_start = i+1; } } } for (int i=cursor+1 ; i namespace dtc { +namespace { +struct expression; +typedef std::unique_ptr expression_ptr; +} + /** * Class encapsulating the input file. Can be used as a const char*, but has * range checking. Attempting to access anything out of range will return a 0 * byte. The input buffer can be cheaply copied, without copying the * underlying memory, however it is the user's responsibility to ensure that * such copies do not persist beyond the lifetime of the underlying memory. * * This also contains methods for reporting errors and for consuming the token * stream. */ class input_buffer { protected: /** * The buffer. This class doesn't own the buffer, but the * mmap_input_buffer subclass does. */ const char* buffer; /** * The size of the buffer. */ int size; private: /** + * Parse an expression. If `stopAtParen` is set, then only parse a number + * or a parenthetical expression, otherwise assume that either is the + * left-hand side of a binary expression and try to parse the right-hand + * side. + */ + expression_ptr parse_expression(bool stopAtParen=false); + /** + * Parse a binary expression, having already parsed the right-hand side. + */ + expression_ptr parse_binary_expression(expression_ptr lhs); + /** * The current place in the buffer where we are reading. This class * keeps a separate size, pointer, and cursor so that we can move * forwards and backwards and still have checks that we haven't fallen * off either end. */ int cursor; /** * Private constructor. This is used to create input buffers that * refer to the same memory, but have different cursors. */ input_buffer(const char* b, int s, int c) : buffer(b), size(s), cursor(c) {} /** * Reads forward past any spaces. The DTS format is not whitespace * sensitive and so we want to scan past whitespace when reading it. */ void skip_spaces(); public: /** * Return whether all input has been consumed. */ bool finished() { return cursor >= size; } /** * Virtual destructor. Does nothing, but exists so that subclasses * that own the memory can run cleanup code for deallocating it. */ virtual ~input_buffer() {}; /** * Constructs an empty buffer. */ input_buffer() : buffer(0), size(0), cursor(0) {} /** * Constructs a new buffer with a specified memory region and size. */ input_buffer(const char* b, int s) : buffer(b), size(s), cursor(0){} /** * Returns a new input buffer referring into this input, clamped to the * specified size. If the requested buffer would fall outside the * range of this one, then it returns an empty buffer. * * The returned buffer shares the same underlying storage as the * original. This is intended to be used for splitting up the various * sections of a device tree blob. Requesting a size of 0 will give a * buffer that extends to the end of the available memory. */ input_buffer buffer_from_offset(int offset, int s=0); /** * Returns true if this buffer has no unconsumed space in it. */ inline bool empty() { return cursor >= size; } /** * Dereferencing operator, allows the buffer to be treated as a char* * and dereferenced to give a character. This returns a null byte if * the cursor is out of range. */ inline char operator*() { if (cursor >= size) { return '\0'; } if (cursor < 0) { return '\0'; } return buffer[cursor]; } /** * Array subscripting operator, returns a character at the specified * index offset from the current cursor. The offset may be negative, * to reread characters that have already been read. If the current * cursor plus offset is outside of the range, this returns a nul * byte. */ inline char operator[](int offset) { if (cursor + offset >= size) { return '\0'; } if (cursor + offset < 0) { return '\0'; } return buffer[cursor + offset]; } /** * Increments the cursor, iterating forward in the buffer. */ inline input_buffer &operator++() { cursor++; return *this; } /** * Cast to char* operator. Returns a pointer into the buffer that can * be used for constructing strings. */ inline operator const char*() { if (cursor >= size) { return 0; } if (cursor < 0) { return 0; } return &buffer[cursor]; } /** * Consumes a character. Moves the cursor one character forward if the * next character matches the argument, returning true. If the current * character does not match the argument, returns false. */ inline bool consume(char c) { if ((*this)[0] == c) { ++(*this); return true; } return false; } /** * Consumes a string. If the (null-terminated) string passed as the * argument appears in the input, advances the cursor to the end and * returns true. Returns false if the string does not appear at the * current point in the input. */ bool consume(const char *str); /** * Reads an integer in base 8, 10, or 16. Returns true and advances * the cursor to the end of the integer if the cursor points to an * integer, returns false and does not move the cursor otherwise. * * The parsed value is returned via the argument. */ bool consume_integer(unsigned long long &outInt); /** + * Reads an arithmetic expression (containing any of the normal C + * operators), evaluates it, and returns the result. + */ + bool consume_integer_expression(unsigned long long &outInt); + /** * Template function that consumes a binary value in big-endian format * from the input stream. Returns true and advances the cursor if * there is a value of the correct size. This function assumes that * all values must be natively aligned, and so advances the cursor to * the correct alignment before reading. */ template bool consume_binary(T &out) { int align = 0; int type_size = sizeof(T); if (cursor % type_size != 0) { align = type_size - (cursor % type_size); } if (size < cursor + align + type_size) { return false; } cursor += align; assert(cursor % type_size == 0); out = 0; for (int i=0 ; i inline bool input_buffer::consume_binary(uint8_t &out) { if (size < cursor + 1) { return false; } out = buffer[cursor++]; return true; } /** * Subclass of input_buffer that mmap()s a file and owns the resulting memory. * When this object is destroyed, the memory is unmapped. */ struct mmap_input_buffer : public input_buffer { /** * Constructs a new buffer from the file passed in as a file * descriptor. */ mmap_input_buffer(int fd); /** * Unmaps the buffer, if one exists. */ virtual ~mmap_input_buffer(); }; /** * Input buffer read from standard input. This is used for reading device tree * blobs and source from standard input. It reads the entire input into * malloc'd memory, so will be very slow for large inputs. DTS and DTB files * are very rarely more than 10KB though, so this is probably not a problem. */ struct stream_input_buffer : public input_buffer { /** * The buffer that will store the data read from the standard input. */ std::vector b; /** * Constructs a new buffer from the standard input. */ stream_input_buffer(); }; } // namespace dtc #endif // !_INPUT_BUFFER_HH_