From a0706eb4574932a57e425505e9a3027cd45fce4c Mon Sep 17 00:00:00 2001 From: David Chisnall Date: Sun, 25 Oct 2015 14:52:16 +0000 Subject: Lots of improvements to the BSD-licensed dtc - Various fixes to includes (including recursive includes) - Lots of testing that the output exactly matches GPL'd dtc - Lots of bug fixes to merging - Fix incorrect mmap usage - Ad-hoc memory management replaced with C++11 unique_ptr and similar Patrick Wildt has successfully run many (all?) of the GPL dtc test suite. --- usr.bin/dtc/checking.cc | 33 +-- usr.bin/dtc/checking.hh | 26 +- usr.bin/dtc/dtb.cc | 11 +- usr.bin/dtc/dtc.cc | 2 +- usr.bin/dtc/fdt.cc | 612 ++++++++++++++++++++++++++------------------ usr.bin/dtc/fdt.hh | 138 +++++----- usr.bin/dtc/input_buffer.cc | 16 +- usr.bin/dtc/input_buffer.hh | 6 +- usr.bin/dtc/string.hh | 17 ++ 9 files changed, 509 insertions(+), 352 deletions(-) (limited to 'usr.bin/dtc') diff --git a/usr.bin/dtc/checking.cc b/usr.bin/dtc/checking.cc index 9c7f43c01dc5..70731ce7155f 100644 --- a/usr.bin/dtc/checking.cc +++ b/usr.bin/dtc/checking.cc @@ -51,7 +51,7 @@ namespace struct address_cells_checker : public checker { address_cells_checker(const char *name) : checker(name) {} - virtual bool check_node(device_tree *tree, node *n) + virtual bool check_node(device_tree *tree, const node_ptr &n) { // If this has no children, it trivially meets the // conditions. @@ -61,8 +61,7 @@ namespace } bool found_address = false; bool found_size = false; - for (node::property_iterator i=n->property_begin(), - e=n->property_end() ; i!=e ; ++i) + for (auto i=n->property_begin(), e=n->property_end() ; i!=e ; ++i) { if (!found_address) { @@ -91,7 +90,7 @@ namespace } // anonymous namespace bool -checker::visit_node(device_tree *tree, node *n) +checker::visit_node(device_tree *tree, const node_ptr &n) { path.push_back(std::make_pair(n->name, n->unit_address)); // Check this node @@ -100,8 +99,7 @@ checker::visit_node(device_tree *tree, node *n) return false; } // Now check its properties - for (node::property_iterator i=n->property_begin(), e=n->property_end() - ; i!=e ; ++i) + for (auto i=n->property_begin(), e=n->property_end() ; i!=e ; ++i) { if (!check_property(tree, n, *i)) { @@ -125,22 +123,21 @@ void checker::report_error(const char *errmsg) { fprintf(stderr, "Error: %s, while checking node: ", errmsg); - for (device_tree::node_path::iterator p=path.begin()+1, pe=path.end() ; - p!=pe ; ++p) + for (auto &p : path) { putc('/', stderr); - p->first.dump(); - if (!(p->second.empty())) + p.first.dump(); + if (!(p.second.empty())) { putc('@', stderr); - p->second.dump(); + p.second.dump(); } } fprintf(stderr, " [-W%s]\n", checker_name); } bool -property_checker::check_property(device_tree *tree, node *n, property *p) +property_checker::check_property(device_tree *tree, const node_ptr &n, property_ptr p) { if (p->get_key() == key) { @@ -154,7 +151,7 @@ property_checker::check_property(device_tree *tree, node *n, property *p) } bool -property_size_checker::check(device_tree *tree, node *n, property *p) +property_size_checker::check(device_tree *tree, const node_ptr &n, property_ptr p) { uint32_t psize = 0; for (property::value_iterator i=p->begin(),e=p->end() ; i!=e ; ++i) @@ -216,10 +213,9 @@ bool check_manager::run_checks(device_tree *tree, bool keep_going) { bool success = true; - for (std::map::iterator i=checkers.begin(), - e=checkers.end() ; i!=e ; ++i) + for (auto &i : checkers) { - success &= i->second->check_tree(tree); + success &= i.second->check_tree(tree); if (!(success || keep_going)) { break; @@ -231,7 +227,7 @@ check_manager::run_checks(device_tree *tree, bool keep_going) bool check_manager::disable_checker(string name) { - std::map::iterator checker = checkers.find(name); + auto checker = checkers.find(name); if (checker != checkers.end()) { disabled_checkers.insert(std::make_pair(name, @@ -245,8 +241,7 @@ check_manager::disable_checker(string name) bool check_manager::enable_checker(string name) { - std::map::iterator checker = - disabled_checkers.find(name); + auto checker = disabled_checkers.find(name); if (checker != disabled_checkers.end()) { checkers.insert(std::make_pair(name, checker->second)); diff --git a/usr.bin/dtc/checking.hh b/usr.bin/dtc/checking.hh index 0de1d608c4d3..34d28c3342e6 100644 --- a/usr.bin/dtc/checking.hh +++ b/usr.bin/dtc/checking.hh @@ -65,7 +65,7 @@ class checker * Visits each node, calling the checker functions on properties and * nodes. */ - bool visit_node(device_tree *tree, node *n); + bool visit_node(device_tree *tree, const node_ptr &n); protected: /** * Prints the error message, along with the path to the node that @@ -86,7 +86,7 @@ class 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, node *n) + virtual bool check_node(device_tree *tree, const node_ptr &n) { return true; } @@ -94,7 +94,7 @@ class checker * 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, node *n, property *p) + virtual bool check_property(device_tree *tree, const node_ptr &n, property_ptr p) { return true; } @@ -124,7 +124,7 @@ class property_checker : public checker * 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, node *n, property *p); + 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. @@ -134,7 +134,7 @@ class property_checker : public checker /** * The check method, which subclasses should implement. */ - virtual bool check(device_tree *tree, node *n, property *p) = 0; + virtual bool check(device_tree *tree, const node_ptr &n, property_ptr p) = 0; }; /** @@ -149,7 +149,7 @@ 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, node *n, property *p) = 0; + virtual bool check(device_tree *tree, const node_ptr &n, property_ptr p) = 0; }; /** @@ -160,7 +160,7 @@ 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, node *n, property *p) + virtual bool check(device_tree *tree, const node_ptr &n, property_ptr p) { return p->begin() == p->end(); } @@ -175,7 +175,7 @@ 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, node *n, property *p) + virtual bool check(device_tree *tree, const node_ptr &n, property_ptr p) { return (p->begin() + 1 == p->end()) && p->begin()->is_string(); } @@ -190,7 +190,7 @@ struct property_type_checker : { property_type_checker(const char* name, string property_name) : property_checker(name, property_name) {} - virtual bool check(device_tree *tree, node *n, property *p) + virtual bool check(device_tree *tree, const node_ptr &n, property_ptr p) { for (property::value_iterator i=p->begin(),e=p->end() ; i!=e ; ++i) @@ -213,7 +213,7 @@ 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, node *n, property *p) + virtual bool check(device_tree *tree, const node_ptr &n, property_ptr p) { return (p->begin() + 1 == p->end()) && (tree->referenced_node(*p->begin()) != 0); @@ -239,7 +239,7 @@ struct property_size_checker : public property_checker /** * Check, validates that the property has the correct size. */ - virtual bool check(device_tree *tree, node *n, property *p); + virtual bool check(device_tree *tree, const node_ptr &n, property_ptr p); }; @@ -254,12 +254,12 @@ class check_manager * disabling checkers from the command line. When this manager runs, * it will only run the checkers from this map. */ - std::map checkers; + std::unordered_map checkers; /** * The disabled checkers. Moving checkers to this list disables them, * but allows them to be easily moved back. */ - std::map disabled_checkers; + std::unordered_map disabled_checkers; /** * Helper function for adding a property value checker. */ diff --git a/usr.bin/dtc/dtb.cc b/usr.bin/dtc/dtb.cc index 986ef6f717b5..bbcf76d751aa 100644 --- a/usr.bin/dtc/dtb.cc +++ b/usr.bin/dtc/dtb.cc @@ -44,9 +44,9 @@ namespace dtb void output_writer::write_data(byte_buffer b) { - for (byte_buffer::iterator i=b.begin(), e=b.end(); i!=e ; i++) + for (auto i : b) { - write_data(*i); + write_data(i); } } @@ -277,7 +277,7 @@ header::read_dtb(input_buffer &input) uint32_t string_table::add_string(string str) { - std::map::iterator old = string_offsets.find(str); + auto old = string_offsets.find(str); if (old == string_offsets.end()) { uint32_t start = size; @@ -298,10 +298,9 @@ string_table::write(dtb::output_writer &writer) { writer.write_comment(string("Strings table.")); writer.write_label(string("dt_strings_start")); - for (std::vector::iterator i=strings.begin(), e=strings.end() ; - i!=e ; ++i) + for (auto &i : strings) { - writer.write_string(*i); + writer.write_string(i); } writer.write_label(string("dt_strings_end")); } diff --git a/usr.bin/dtc/dtc.cc b/usr.bin/dtc/dtc.cc index b7d52921abe8..269c90e5e274 100644 --- a/usr.bin/dtc/dtc.cc +++ b/usr.bin/dtc/dtc.cc @@ -67,7 +67,7 @@ static void usage(const char* argv0) "[-O output_format]\n" "\t\t[-o output_file] [-R entries] [-S bytes] [-p bytes]" "[-V blob_version]\n" - "\t\t-W [no-]checker_name] input_file\n", basename(argv0)); + "\t\t-W [no-]checker_name] input_file\n", basename((char*)argv0)); } /** diff --git a/usr.bin/dtc/fdt.cc b/usr.bin/dtc/fdt.cc index 082ebd993d79..3908e0ef13b7 100644 --- a/usr.bin/dtc/fdt.cc +++ b/usr.bin/dtc/fdt.cc @@ -33,8 +33,10 @@ #define __STDC_LIMIT_MACROS 1 #include "fdt.hh" +#include "dtb.hh" #include + #include #include #include @@ -44,7 +46,7 @@ #include #include #include -#include "dtb.hh" +#include namespace dtc { @@ -126,13 +128,25 @@ property_value::resolve_type() bool is_all_printable = true; int nuls = 0; int bytes = 0; - for (byte_buffer::iterator i=byte_data.begin(), e=byte_data.end()-1; i nuls)) || bytes == 0) { type = STRING; - if (nuls > 0) + if (nuls > 1) { type = STRING_LIST; } @@ -162,15 +176,25 @@ property_value::write_as_string(FILE *file) } else { - for (byte_buffer::iterator i=byte_data.begin(), e=byte_data.end()-1; i!=e ; ++i) + 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') + if (i == '\0') { fputs("\", \"", file); continue; } - putc(*i, file); + putc(i, file); + } + if (hasNull) + { + byte_data.push_back('\0'); } } putc('"', file); @@ -181,7 +205,7 @@ property_value::write_as_cells(FILE *file) { putc('<', file); assert((byte_data.size() % 4) == 0); - for (byte_buffer::iterator i=byte_data.begin(), e=byte_data.end(); i!=e ; ++i) + for (auto i=byte_data.begin(), e=byte_data.end(); i!=e ; ++i) { uint32_t v = 0; v = (v << 8) | *i; @@ -204,7 +228,7 @@ void property_value::write_as_bytes(FILE *file) { putc('[', file); - for (byte_buffer::iterator i=byte_data.begin(), e=byte_data.end(); i!=e ; i++) + for (auto i=byte_data.begin(), e=byte_data.end(); i!=e ; i++) { fprintf(file, "%02hhx", *i); if (i+1 != e) @@ -238,8 +262,26 @@ property::parse_string(input_buffer &input) } void -property::parse_cells(input_buffer &input) +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; @@ -251,6 +293,12 @@ property::parse_cells(input_buffer &input) // 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. @@ -278,20 +326,37 @@ property::parse_cells(input_buffer &input) { //FIXME: We should support labels in the middle //of these, but we don't. - long long val; + unsigned long long val; if (!input.consume_integer(val)) { input.parse_error("Expected numbers in array of cells"); valid = false; return; } - if ((val < 0) || (val > UINT32_MAX)) + if (val > cell_max) { + fprintf(stderr, "%lld > %lld\n", val, cell_max); input.parse_error("Value out of range"); valid = false; return; } - push_big_endian(v.byte_data, (uint32_t)val); + 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(); } } @@ -432,11 +497,35 @@ property::property(input_buffer &input, 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); + parse_cells(input, 32); break; case '[': parse_bytes(input); @@ -458,27 +547,25 @@ property::property(input_buffer &input, } } -property* +property_ptr property::parse_dtb(input_buffer &structs, input_buffer &strings) { - property *p = new property(structs, strings); + property_ptr p(new property(structs, strings)); if (!p->valid) { - delete p; - p = 0; + p = nullptr; } return p; } -property* +property_ptr property::parse(input_buffer &input, string key, string label, bool semicolonTerminated, define_map *defines) { - property *p = new property(input, key, label, semicolonTerminated, defines); + property_ptr p(new property(input, key, label, semicolonTerminated, defines)); if (!p->valid) { - delete p; - p = 0; + p = nullptr; } return p; } @@ -498,6 +585,35 @@ property::write(dtb::output_writer &writer, dtb::string_table &strings) 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) { @@ -516,8 +632,23 @@ property::write_dts(FILE *file, int indent) } if (!values.empty()) { + std::vector *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 (value_iterator i=begin(), e=end() ; i!=e ; ++i) + for (auto i=vals->begin(), e=vals->end() ; i!=e ; ++i) { i->write_dts(file); if (i+1 != e) @@ -590,13 +721,13 @@ node::node(input_buffer &structs, input_buffer &strings) : valid(true) // Child node, parse it. case dtb::FDT_BEGIN_NODE: { - node *child = node::parse_dtb(structs, strings); + node_ptr child = node::parse_dtb(structs, strings); if (child == 0) { valid = false; return; } - children.push_back(child); + children.push_back(std::move(child)); break; } // End of this node, no errors. @@ -605,7 +736,7 @@ node::node(input_buffer &structs, input_buffer &strings) : valid(true) // Property, parse it. case dtb::FDT_PROP: { - property *prop = property::parse_dtb(structs, strings); + property_ptr prop = property::parse_dtb(structs, strings); if (prop == 0) { valid = false; @@ -667,7 +798,7 @@ node::node(input_buffer &input, string n, string l, string a, define_map *define // If we're parsing a property, then we must actually do that. if (input.consume('=')) { - property *p= property::parse(input, child_name, + property_ptr p = property::parse(input, child_name, child_label, true, defines); if (p == 0) { @@ -680,11 +811,11 @@ node::node(input_buffer &input, string n, string l, string a, define_map *define } else if (!is_property && input[0] == ('{')) { - node *child = node::parse(input, child_name, + node_ptr child = node::parse(input, child_name, child_label, child_address, defines); if (child) { - children.push_back(child); + children.push_back(std::move(child)); } else { @@ -693,7 +824,7 @@ node::node(input_buffer &input, string n, string l, string a, define_map *define } else if (input.consume(';')) { - properties.push_back(new property(child_name, child_label)); + properties.push_back(property_ptr(new property(child_name, child_label))); } else { @@ -706,13 +837,13 @@ node::node(input_buffer &input, string n, string l, string a, define_map *define } bool -node::cmp_properties(property *p1, property *p2) +node::cmp_properties(property_ptr &p1, property_ptr &p2) { return p1->get_key() < p2->get_key(); } bool -node::cmp_children(node *c1, node *c2) +node::cmp_children(node_ptr &c1, node_ptr &c2) { if (c1->name == c2->name) { @@ -732,63 +863,47 @@ node::sort() } } -node* +node_ptr node::parse(input_buffer &input, string name, string label, string address, define_map *defines) { - node *n = new node(input, name, label, address, defines); + node_ptr n(new node(input, name, label, address, defines)); if (!n->valid) { - delete n; n = 0; } return n; } -node* +node_ptr node::parse_dtb(input_buffer &structs, input_buffer &strings) { - node *n = new node(structs, strings); + node_ptr n(new node(structs, strings)); if (!n->valid) { - delete n; n = 0; } return n; } -node::~node() -{ - while (!children.empty()) - { - delete children.back(); - children.pop_back(); - } - while (!properties.empty()) - { - delete properties.back(); - properties.pop_back(); - } -} - -property* +property_ptr node::get_property(string key) { - for (property_iterator i=property_begin(), e=property_end() ; i!=e ; ++i) + for (auto &i : properties) { - if ((*i)->get_key() == key) + if (i->get_key() == key) { - return *i; + return i; } } return 0; } void -node::merge_node(node *other) +node::merge_node(node_ptr other) { if (!other->label.empty()) { @@ -799,40 +914,39 @@ node::merge_node(node *other) // 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. - while (!other->properties.empty()) + for (auto &p : other->properties) { - property *p = other->properties.front(); - for (property_iterator i=property_begin(), e=property_end() ; i!=e ; ++i) + bool found = false; + for (auto i=property_begin(), e=property_end() ; i!=e ; ++i) { if ((*i)->get_key() == p->get_key()) { - delete *i; - properties.erase(i); + *i = p; + found = true; break; } } - add_property(p); - other->properties.erase(other->properties.begin()); + if (!found) + { + add_property(p); + } } - while (!other->children.empty()) + for (auto &c : other->children) { - node *c = other->children.front(); bool found = false; - for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i) + for (auto &i : children) { - if ((*i)->name == c->name && (*i)->unit_address == c->unit_address) + if (i->name == c->name && i->unit_address == c->unit_address) { - (*i)->merge_node(c); - delete c; + i->merge_node(std::move(c)); found = true; break; } } if (!found) { - children.push_back(c); + children.push_back(std::move(c)); } - other->children.erase(other->children.begin()); } } @@ -850,7 +964,7 @@ node::write(dtb::output_writer &writer, dtb::string_table &strings) writer.write_comment(name); writer.write_data(name_buffer); writer.write_data((uint8_t)0); - for (property_iterator i=property_begin(), e=property_end() ; i!=e ; ++i) + for (auto i=property_begin(), e=property_end() ; i!=e ; ++i) { (*i)->write(writer, strings); } @@ -868,11 +982,13 @@ node::write_dts(FILE *file, int indent) { putc('\t', file); } +#ifdef PRINT_LABELS if (label != string()) { label.print(file); fputs(": ", file); } +#endif if (name != string()) { name.print(file); @@ -883,7 +999,7 @@ node::write_dts(FILE *file, int indent) unit_address.print(file); } fputs(" {\n\n", file); - for (property_iterator i=property_begin(), e=property_end() ; i!=e ; ++i) + for (auto i=property_begin(), e=property_end() ; i!=e ; ++i) { (*i)->write_dts(file, indent+1); } @@ -899,7 +1015,7 @@ node::write_dts(FILE *file, int indent) } void -device_tree::collect_names_recursive(node* n, node_path &path) +device_tree::collect_names_recursive(node_ptr &n, node_path &path) { string name = n->label; path.push_back(std::make_pair(n->name, n->unit_address)); @@ -907,13 +1023,13 @@ device_tree::collect_names_recursive(node* n, node_path &path) { if (node_names.find(name) == node_names.end()) { - node_names.insert(std::make_pair(name, n)); + node_names.insert(std::make_pair(name, n.get())); node_paths.insert(std::make_pair(name, path)); } else { node_names[name] = (node*)-1; - std::map::iterator i = node_paths.find(name); + auto i = node_paths.find(name); if (i != node_paths.end()) { node_paths.erase(name); @@ -930,7 +1046,7 @@ device_tree::collect_names_recursive(node* n, node_path &path) path.pop_back(); // Now we collect the phandles and properties that reference // other nodes. - for (node::property_iterator i=n->property_begin(), e=n->property_end() ; i!=e ; ++i) + for (auto i=n->property_begin(), e=n->property_end() ; i!=e ; ++i) { for (property::value_iterator p=(*i)->begin(),pe=(*i)->end() ; p!=pe ; ++p) { @@ -956,7 +1072,7 @@ device_tree::collect_names_recursive(node* n, node_path &path) else { uint32_t phandle = (*i)->begin()->get_as_uint32(); - used_phandles.insert(std::make_pair(phandle, n)); + used_phandles.insert(std::make_pair(phandle, n.get())); } } } @@ -966,18 +1082,21 @@ 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 (std::vector::iterator i=cross_references.begin(), e=cross_references.end() ; i!=e ; ++i) + for (auto *pv : cross_references) { - property_value* pv = *i; node_path path = node_paths[pv->string_data]; // Skip the first name in the path. It's always "", and implicitly / - for (node_path::iterator p=path.begin()+1, pe=path.end() ; p!=pe ; ++p) + 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); @@ -987,23 +1106,22 @@ device_tree::resolve_cross_references() p->second.push_to_buffer(pv->byte_data); } } - pv->byte_data.push_back(0); } uint32_t phandle = 1; - for (std::vector::iterator i=phandles.begin(), e=phandles.end() ; i!=e ; ++i) + for (auto &i : phandles) { - string target_name = (*i)->string_data; + string target_name = i->string_data; node *target = node_names[target_name]; if (target == 0) { - fprintf(stderr, "Failed to find node with label:"); + 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 *p = target->get_property("phandle"); + property_ptr p = target->get_property("phandle"); if (p == 0) { p = target->get_property("linux,phandle"); @@ -1029,33 +1147,140 @@ device_tree::resolve_cross_references() push_big_endian(v.byte_data, phandle++); if (phandle_node_name == BOTH || phandle_node_name == LINUX) { - p = new property(string("linux,phandle")); + 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 = new property(string("phandle")); + 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); + p->begin()->push_to_buffer(i->byte_data); + assert(i->byte_data.size() == 4); } } void -device_tree::parse_roots(input_buffer &input, std::vector &roots) +device_tree::parse_file(input_buffer &input, + const std::string &dir, + std::vector &roots, + FILE *depfile, + bool &read_header) { input.next_token(); - while (valid && input.consume('/')) + // Read the header + if (input.consume("/dts-v1/;")) + { + read_header = true; + } + input.next_token(); + while(input.consume("/include/")) { + 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(); - node *n = node::parse(input, string("", 1), string(), string(), &defines); + if (!input.consume('"')) + { + input.parse_error("Expected quoted filename"); + valid = false; + return; + } + 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())); + input.consume('"'); + input.next_token(); + if (!reallyInclude) + { + continue; + } + + input_buffer *include_buffer = buffer_for_file(include_file.c_str()); + + if (include_buffer == 0) + { + for (auto i : include_paths) + { + include_file = i + '/' + file; + include_buffer = buffer_for_file(include_file.c_str()); + if (include_buffer != 0) + { + 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); + } + input.next_token(); + if (!read_header) + { + input.parse_error("Expected /dts-v1/; version string"); + } + // 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) && + (input.next_token(), + input.consume_integer(len)))) + { + input.parse_error("Expected size on /memreserve/ node."); + } + input.next_token(); + input.consume(';'); + reservations.push_back(reservation(start, len)); + } + input.next_token(); + 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(n); + roots.push_back(std::move(n)); } else { @@ -1071,13 +1296,17 @@ device_tree::buffer_for_file(const char *path) if (string(path) == string("-")) { input_buffer *b = new stream_input_buffer(); - buffers.push_back(b); + 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\n", path); + fprintf(stderr, "Unable to open file '%s'. %s\n", path, strerror(errno)); return 0; } struct stat st; @@ -1091,7 +1320,11 @@ device_tree::buffer_for_file(const char *path) // Keep the buffer that owns the memory around for the lifetime // of this FDT. Ones simply referring to it may have shorter // lifetimes. - buffers.push_back(b); + if (b) + { + std::unique_ptr ptr(b); + buffers.push_back(std::move(ptr)); + } close(source); return b; } @@ -1109,13 +1342,12 @@ device_tree::write(int fd) // Build the reservation table reservation_writer.write_comment(string("Memory reservations")); reservation_writer.write_label(string("dt_reserve_map")); - for (std::vector::iterator i=reservations.begin(), - e=reservations.end() ; i!=e ; ++i) + for (auto &i : reservations) { reservation_writer.write_comment(string("Reservation start")); - reservation_writer.write_data(i->first); + reservation_writer.write_data(i.first); reservation_writer.write_comment(string("Reservation length")); - reservation_writer.write_data(i->first); + 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++) @@ -1202,10 +1434,9 @@ device_tree::write_dts(int fd) { const char msg[] = "/memreserve/"; fwrite(msg, sizeof(msg), 1, file); - for (std::vector::iterator i=reservations.begin(), - e=reservations.end() ; i!=e ; ++i) + for (auto &i : reservations) { - fprintf(file, " %" PRIx64 " %" PRIx64, i->first, i->second); + fprintf(file, " %" PRIx64 " %" PRIx64, i.first, i.second); } fputs(";\n\n", file); } @@ -1276,125 +1507,16 @@ 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; + std::vector roots; input_buffer &input = *in; - input.next_token(); bool read_header = false; - // Read the header - if (input.consume("/dts-v1/;")) - { - read_header = true; - } - input.next_token(); - while(input.consume("/include/")) - { - 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('"')) - { - input.parse_error("Expected quoted filename"); - valid = false; - return; - } - int length = 0; - while (input[length] != '"') length++; - - const char *file = (const char*)input; - const char *dir = dirname(fn); - int dir_length = strlen(dir); - char *include_file = (char*)malloc(strlen(dir) + length + 2); - memcpy(include_file, dir, dir_length); - include_file[dir_length] = '/'; - memcpy(include_file+dir_length+1, file, length); - include_file[dir_length+length+1] = 0; - - input.consume(include_file+dir_length+1); - input.consume('"'); - if (!reallyInclude) - { - continue; - } - - input_buffer *include_buffer = buffer_for_file(include_file); - - if (include_buffer == 0) - { - for (std::vector::iterator i=include_paths.begin(), e=include_paths.end() ; e!=i ; ++i) - { - free(include_file); - dir = *i; - dir_length = strlen(dir); - include_file = (char*)malloc(strlen(dir) + - length + 2); - memcpy(include_file, dir, dir_length); - include_file[dir_length] = '/'; - memcpy(include_file+dir_length+1, file, length); - include_file[dir_length+length+1] = 0; - include_buffer = buffer_for_file(include_file); - if (include_buffer != 0) - { - break; - } - } - } - if (depfile != 0) - { - putc(' ', depfile); - fputs(include_file, depfile); - } - if (include_buffer == 0) - { - valid = false; - return; - } - input_buffer &include = *include_buffer; - free((void*)include_file); - - if (!read_header) - { - include.next_token(); - read_header = include.consume("/dts-v1/;"); - } - parse_roots(include, roots); - } - input.next_token(); - if (!read_header) - { - input.parse_error("Expected /dts-v1/; version string"); - } - // Read any memory reservations - while(input.consume("/memreserve/")) - { - long long start, len; - input.next_token(); - // Read the start and length. - if (!(input.consume_integer(start) && - (input.next_token(), - input.consume_integer(len)))) - { - input.parse_error("Expected size on /memreserve/ node."); - } - input.next_token(); - input.consume(';'); - reservations.push_back(reservation(start, len)); - } - parse_roots(input, roots); + parse_file(input, dir, roots, depfile, read_header); switch (roots.size()) { case 0: @@ -1402,42 +1524,42 @@ device_tree::parse_dts(const char *fn, FILE *depfile) input.parse_error("Failed to find root node /."); return; case 1: - root = roots[0]; + root = std::move(roots[0]); break; default: { - root = roots[0]; - for (std::vector::iterator i=roots.begin()+1, - e=roots.end() ; i!=e ; ++i) + root = std::move(roots[0]); + for (auto i=++(roots.begin()), e=roots.end() ; i!=e ; ++i) { - root->merge_node(*i); - delete *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)); + } } - roots.resize(1); } } collect_names(); resolve_cross_references(); } -device_tree::~device_tree() -{ - if (root != 0) - { - delete root; - } - while (!buffers.empty()) - { - delete buffers.back(); - buffers.pop_back(); - } - for (define_map::iterator i=defines.begin(), e=defines.end() ; - i!=e ; ++i) - { - delete i->second; - } -} - bool device_tree::parse_define(const char *def) { char *val = strchr(def, '='); @@ -1454,10 +1576,10 @@ bool device_tree::parse_define(const char *def) string name(def, val-def); val++; input_buffer in = input_buffer(val, strlen(val)); - property *p = property::parse(in, name, string(), false); + property_ptr p = property::parse(in, name, string(), false); if (p) defines[name] = p; - return p; + return (bool)p; } } // namespace fdt diff --git a/usr.bin/dtc/fdt.hh b/usr.bin/dtc/fdt.hh index 3ac10847e5fa..7340a73154c1 100644 --- a/usr.bin/dtc/fdt.hh +++ b/usr.bin/dtc/fdt.hh @@ -32,7 +32,10 @@ #ifndef _FDT_HH_ #define _FDT_HH_ -#include +#include +#include +#include +#include #include "util.hh" #include "string.hh" @@ -49,7 +52,19 @@ class string_table; namespace fdt { class property; -typedef std::map define_map; +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. @@ -186,6 +201,11 @@ struct property_value * - 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 @@ -250,7 +270,7 @@ class property /** * Parses one or more 32-bit values enclosed in angle brackets. */ - void parse_cells(input_buffer &input); + void parse_cells(input_buffer &input, int cell_size); /** * Parses an array of bytes, contained within square brackets. */ @@ -299,18 +319,18 @@ class property * property from the input, and returns it on success. On any parse * error, this will return 0. */ - static property* parse_dtb(input_buffer &structs, + 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* parse(input_buffer &input, - string key, - string label=string(), - bool semicolonTerminated=true, - define_map *defines=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. */ @@ -378,15 +398,19 @@ class node * name followed by an at symbol. */ string unit_address; + /** + * The type for the property vector. + */ + typedef std::vector property_vector; private: /** * The properties contained within this node. */ - std::vector properties; + property_vector properties; /** * The children of this node. */ - std::vector children; + std::vector children; /** * A flag indicating whether this node is valid. This is set to false * if an error occurs during parsing. @@ -415,7 +439,7 @@ class node * Comparison function for properties, used when sorting the properties * vector. Orders the properties based on their names. */ - static inline bool cmp_properties(property *p1, property *p2); + static inline bool cmp_properties(property_ptr &p1, property_ptr &p2); /* { return p1->get_key() < p2->get_key(); @@ -426,16 +450,7 @@ class node * 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 *c1, node *c2); - /* - { - if (c1->name == c2->name) - { - return c1->unit_address < c2->unit_address; - } - return c1->name < c2->name; - } - */ + static inline bool cmp_children(node_ptr &c1, node_ptr &c2); public: /** * Sorts the node's properties and children into alphabetical order and @@ -445,7 +460,7 @@ class node /** * Iterator type for child nodes. */ - typedef std::vector::iterator child_iterator; + typedef std::vector::iterator child_iterator; /** * Returns an iterator for the first child of this node. */ @@ -460,21 +475,17 @@ class node { return children.end(); } - /** - * Iterator type for properties of a node. - */ - typedef std::vector::iterator property_iterator; /** * Returns an iterator after the last property of this node. */ - inline property_iterator property_begin() + inline property_vector::iterator property_begin() { return properties.begin(); } /** * Returns an iterator for the first property of this node. */ - inline property_iterator property_end() + inline property_vector::iterator property_end() { return properties.end(); } @@ -485,11 +496,11 @@ class node * cursor on the open brace of the property, after the name and so on * have been parsed. */ - static node* parse(input_buffer &input, - string name, - string label=string(), - string address=string(), - define_map *defines=0); + 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 @@ -497,21 +508,16 @@ class node * cursor on the open brace of the property, after the name and so on * have been parsed. */ - static node* parse_dtb(input_buffer &structs, input_buffer &strings); - /** - * Destroys the node, recursively deleting all of its properties and - * children. - */ - ~node(); + 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 *get_property(string key); + property_ptr get_property(string key); /** * Adds a new property to this node. */ - inline void add_property(property *p) + inline void add_property(property_ptr &p) { properties.push_back(p); } @@ -519,7 +525,7 @@ class node * 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 *other); + 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 @@ -584,18 +590,18 @@ class device_tree /** * Root node. All other nodes are children of this node. */ - node *root; + node_ptr root; /** * Mapping from names to nodes. Only unambiguous names are recorded, * duplicate names are stored as (node*)-1. */ - std::map node_names; + 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::map node_paths; + 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. @@ -607,12 +613,16 @@ class device_tree * 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; + 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 @@ -622,13 +632,13 @@ class device_tree * find phandles that were provided by the user explicitly when we are * doing checking. */ - std::map used_phandles; + 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; + std::vector include_paths; /** * Dictionary of predefined macros provided on the command line. */ @@ -655,7 +665,13 @@ class device_tree * used in resolving cross references. Also collects phandle * properties that have been explicitly added. */ - void collect_names_recursive(node* n, node_path &path); + 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. */ @@ -667,9 +683,16 @@ class device_tree */ void resolve_cross_references(); /** - * Parses root nodes from the top level of a dts file. + * 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_roots(input_buffer &input, std::vector &roots); + 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 @@ -706,7 +729,7 @@ class device_tree /** * Default constructor. Creates a valid, but empty FDT. */ - device_tree() : phandle_node_name(EPAPR), valid(true), root(0), + device_tree() : phandle_node_name(EPAPR), valid(true), boot_cpu(0), spare_reserve_map_entries(0), minimum_blob_size(0), blob_padding(0) {} /** @@ -719,10 +742,6 @@ class device_tree * a file that contains device tree source. */ void parse_dts(const char *fn, FILE *depfile); - /** - * Destroy the tree and any input buffers that it holds. - */ - ~device_tree(); /** * Returns whether this tree is valid. */ @@ -741,7 +760,7 @@ class device_tree * Returns a pointer to the root node of this tree. No ownership * transfer. */ - inline node *get_root() const + inline const node_ptr &get_root() const { return root; } @@ -767,7 +786,8 @@ class device_tree */ void add_include_path(const char *path) { - include_paths.push_back(path); + std::string p(path); + include_paths.push_back(std::move(p)); } /** * Sets the number of empty reserve map entries to add. diff --git a/usr.bin/dtc/input_buffer.cc b/usr.bin/dtc/input_buffer.cc index c83044d9d8fb..fe8c402d8eb5 100644 --- a/usr.bin/dtc/input_buffer.cc +++ b/usr.bin/dtc/input_buffer.cc @@ -113,7 +113,7 @@ input_buffer::consume(const char *str) } bool -input_buffer::consume_integer(long long &outInt) +input_buffer::consume_integer(unsigned long long &outInt) { // The first character must be a digit. Hex and octal strings // are prefixed by 0 and 0x, respectively. @@ -122,7 +122,7 @@ input_buffer::consume_integer(long long &outInt) return false; } char *end=0; - outInt = strtoll(&buffer[cursor], &end, 0); + outInt = strtoull(&buffer[cursor], &end, 0); if (end == &buffer[cursor]) { return false; @@ -168,9 +168,8 @@ input_buffer::next_token() // Eat the / ++(*this); } - // Parse // comments and # comments - if (((*this)[0] == '/' && (*this)[1] == '/') || - (*this)[0] == '#') + // Parse // comments + if (((*this)[0] == '/' && (*this)[1] == '/')) { // eat the start of the comment ++(*this); @@ -238,11 +237,12 @@ mmap_input_buffer::mmap_input_buffer(int fd) : input_buffer(0, 0) perror("Failed to stat file"); } size = sb.st_size; - buffer = (const char*)mmap(0, size, PROT_READ, - MAP_PREFAULT_READ, fd, 0); - if (buffer == 0) + buffer = (const char*)mmap(0, size, PROT_READ, MAP_PRIVATE | + MAP_PREFAULT_READ, fd, 0); + if (buffer == MAP_FAILED) { perror("Failed to mmap file"); + exit(EXIT_FAILURE); } } diff --git a/usr.bin/dtc/input_buffer.hh b/usr.bin/dtc/input_buffer.hh index 9a38312385bd..5b1f5d648ed8 100644 --- a/usr.bin/dtc/input_buffer.hh +++ b/usr.bin/dtc/input_buffer.hh @@ -80,6 +80,10 @@ class input_buffer */ 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. @@ -181,7 +185,7 @@ class input_buffer * * The parsed value is returned via the argument. */ - bool consume_integer(long long &outInt); + bool consume_integer(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 diff --git a/usr.bin/dtc/string.hh b/usr.bin/dtc/string.hh index 45bc4fda71c5..f6acc1b2e8a4 100644 --- a/usr.bin/dtc/string.hh +++ b/usr.bin/dtc/string.hh @@ -33,6 +33,8 @@ #ifndef _STRING_HH_ #define _STRING_HH_ #include "input_buffer.hh" +#include +#include namespace dtc { @@ -48,6 +50,7 @@ namespace dtc */ class string { + friend std::hash; /** Start address. Contained within the mmap()'d input file and not * owned by this object. */ const char *start; @@ -143,5 +146,19 @@ class string }; } // namespace dtc +namespace std +{ + template<> + struct hash + { + std::size_t operator()(dtc::string const& s) const + { + std::string str(s.start, s.length); + std::hash h; + return h(str); + } + }; +} + #endif // !_STRING_HH_ -- cgit v1.2.3