8 files changed, 299 insertions, 47 deletions

diff --git a/usr.bin/dtc/dtb.cc b/usr.bin/dtc/dtb.cc
index 5808e16ec75e..d7aecba02800 100644
--- a/usr.bin/dtc/dtb.cc
+++ b/usr.bin/dtc/dtb.cc
@@ -37,9 +37,33 @@
 #include <inttypes.h>
 #include <stdio.h>
 #include <unistd.h>
+#include <errno.h>
 
 using std::string;
 
+namespace {
+
+void write(dtc::byte_buffer &buffer, int fd)
+{
+	size_t size = buffer.size();
+	uint8_t *data = buffer.data();
+	while (size > 0)
+	{
+		ssize_t r = ::write(fd, data, size);
+		if (r >= 0)
+		{
+			data += r;
+			size -= r;
+		}
+		else if (errno != EAGAIN)
+		{
+			fprintf(stderr, "Writing to file failed\n");
+			exit(-1);
+		}
+	}
+}
+}
+
 namespace dtc
 {
 namespace dtb
@@ -90,8 +114,7 @@ binary_writer::write_data(uint64_t v)
 void
 binary_writer::write_to_file(int fd)
 {
-	// FIXME: Check return
-	write(fd, buffer.data(), buffer.size());
+	write(buffer, fd);
 }
 
 uint32_t
@@ -222,8 +245,7 @@ asm_writer::write_data(uint64_t v)
 void
 asm_writer::write_to_file(int fd)
 {
-	// FIXME: Check return
-	write(fd, buffer.data(), buffer.size());
+	write(buffer, fd);
 }
 
 uint32_t
diff --git a/usr.bin/dtc/dtb.hh b/usr.bin/dtc/dtb.hh
index d0e42a152ea1..4930246f9984 100644
--- a/usr.bin/dtc/dtb.hh
+++ b/usr.bin/dtc/dtb.hh
@@ -109,6 +109,8 @@ inline const char *token_type_name(token_type t)
 			return "FDT_END";
 	}
 	assert(0);
+	// Not reached.
+	return nullptr;
 }
 
 /**
diff --git a/usr.bin/dtc/dtc.1 b/usr.bin/dtc/dtc.1
index 63b946d3dbe2..fea4b3da9d54 100644
--- a/usr.bin/dtc/dtc.1
+++ b/usr.bin/dtc/dtc.1
@@ -30,7 +30,7 @@
 .\"
 .\" $FreeBSD$
 .\"/
-.Dd April 7, 2018
+.Dd March 27, 2019
 .Dt DTC 1
 .Os
 .Sh NAME
@@ -304,7 +304,18 @@ Overlay blobs can be applied at boot time by setting
 in
 .Xr loader.conf 5 .
 Multiple overlays may be specified, and they will be applied in the order given.
-.El
+.Sh NODE OMISSION
+This utility supports the
+.Va /omit-if-no-ref/
+statement to mark nodes for omission if they are ultimately not referenced
+elsewhere in the device tree.
+This may be used in more space-constrained environments to remove nodes that may
+not be applicable to the specific device the tree is being compiled for.
+.Pp
+When the
+.Fl @
+flag is used to write symbols, nodes with labels will be considered referenced
+and will not be removed from the tree.
 .Sh EXAMPLES
 The command:
 .Pp
@@ -403,7 +414,11 @@ A dtc tool first appeared in
 This version of the tool first appeared in
 .Fx 10.0 .
 .Sh AUTHORS
-.An David T. Chisnall
+.Nm
+was written by
+.An David T. Chisnall .
+Some features were added later by
+.An Kyle Evans .
 .Pp
 Note: The fact that the tool and the author share the same initials is entirely
 coincidental.
diff --git a/usr.bin/dtc/dtc.cc b/usr.bin/dtc/dtc.cc
index aec5c3a4ab14..b9423f486815 100644
--- a/usr.bin/dtc/dtc.cc
+++ b/usr.bin/dtc/dtc.cc
@@ -38,6 +38,7 @@
 #include <limits.h>
 #include <stdio.h>
 #include <stdlib.h>
+#include <string.h>
 #include <time.h>
 #include <unistd.h>
 
@@ -65,7 +66,7 @@ int version_minor_compatible = 4;
  * The current patch level of the tool.
  */
 int version_patch = 0;
-int version_patch_compatible = 0;
+int version_patch_compatible = 7;
 
 void usage(const string &argv0)
 {
@@ -105,7 +106,7 @@ main(int argc, char **argv)
 	bool debug_mode = false;
 	auto write_fn = &device_tree::write_binary;
 	auto read_fn = &device_tree::parse_dts;
-	uint32_t boot_cpu;
+	uint32_t boot_cpu = 0;
 	bool boot_cpu_specified = false;
 	bool keep_going = false;
 	bool sort = false;
diff --git a/usr.bin/dtc/fdt.cc b/usr.bin/dtc/fdt.cc
index 3148ec35a414..fa4125ffe6ef 100644
--- a/usr.bin/dtc/fdt.cc
+++ b/usr.bin/dtc/fdt.cc
@@ -46,6 +46,7 @@
 #include <libgen.h>
 #include <stdio.h>
 #include <stdlib.h>
+#include <string.h>
 #include <unistd.h>
 #include <sys/types.h>
 #include <sys/stat.h>
@@ -491,6 +492,7 @@ property::property(text_input_buffer &input,
 					break;
 				}
 			}
+			[[fallthrough]];
 			default:
 				input.parse_error("Invalid property value.");
 				valid = false;
@@ -622,6 +624,7 @@ property_value::try_to_merge(property_value &other)
 			return false;
 		case EMPTY:
 			*this = other;
+			[[fallthrough]];
 		case STRING:
 		case STRING_LIST:
 		case CROSS_REFERENCE:
@@ -846,6 +849,7 @@ node_ptr node::create_special_node(const string &name,
 }
 
 node::node(text_input_buffer &input,
+           device_tree &tree,
            string &&n,
            std::unordered_set<string> &&l,
            string &&a,
@@ -862,6 +866,9 @@ node::node(text_input_buffer &input,
 		// flag set if we find any characters that are only in
 		// the property name character set, not the node 
 		bool is_property = false;
+		// flag set if our node is marked as /omit-if-no-ref/ to be
+		// garbage collected later if nothing references it
+		bool marked_omit_if_no_ref = false;
 		string child_name, child_address;
 		std::unordered_set<string> child_labels;
 		auto parse_delete = [&](const char *expected, bool at)
@@ -908,6 +915,12 @@ node::node(text_input_buffer &input,
 			}
 			continue;
 		}
+		if (input.consume("/omit-if-no-ref/"))
+		{
+			input.next_token();
+			marked_omit_if_no_ref = true;
+			tree.set_needs_garbage_collection();
+		}
 		child_name = parse_name(input, is_property,
 				"Expected property or node name");
 		while (input.consume(':'))
@@ -943,10 +956,11 @@ node::node(text_input_buffer &input,
 		}
 		else if (!is_property && *input == ('{'))
 		{
-			node_ptr child = node::parse(input, std::move(child_name),
+			node_ptr child = node::parse(input, tree, std::move(child_name),
 					std::move(child_labels), std::move(child_address), defines);
 			if (child)
 			{
+				child->omit_if_no_ref = marked_omit_if_no_ref;
 				children.push_back(std::move(child));
 			}
 			else
@@ -998,12 +1012,14 @@ node::sort()
 
 node_ptr
 node::parse(text_input_buffer &input,
+            device_tree &tree,
             string &&name,
             string_set &&label,
             string &&address,
             define_map *defines)
 {
 	node_ptr n(new node(input,
+	                    tree,
 	                    std::move(name),
 	                    std::move(label),
 	                    std::move(address),
@@ -1046,6 +1062,30 @@ node::merge_node(node_ptr &other)
 	{
 		labels.insert(l);
 	}
+	children.erase(std::remove_if(children.begin(), children.end(),
+			[&](const node_ptr &p) {
+				string full_name = p->name;
+				if (p->unit_address != string())
+				{
+					full_name += '@';
+					full_name += p->unit_address;
+				}
+				if (other->deleted_children.count(full_name) > 0)
+				{
+					other->deleted_children.erase(full_name);
+					return true;
+				}
+				return false;
+			}), children.end());
+	props.erase(std::remove_if(props.begin(), props.end(),
+			[&](const property_ptr &p) {
+				if (other->deleted_props.count(p->get_key()) > 0)
+				{
+					other->deleted_props.erase(p->get_key());
+					return true;
+				}
+				return false;
+			}), props.end());
 	// 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
@@ -1085,30 +1125,6 @@ node::merge_node(node_ptr &other)
 			children.push_back(std::move(c));
 		}
 	}
-	children.erase(std::remove_if(children.begin(), children.end(),
-			[&](const node_ptr &p) {
-				string full_name = p->name;
-				if (p->unit_address != string())
-				{
-					full_name += '@';
-					full_name += p->unit_address;
-				}
-				if (other->deleted_children.count(full_name) > 0)
-				{
-					other->deleted_children.erase(full_name);
-					return true;
-				}
-				return false;
-			}), children.end());
-	props.erase(std::remove_if(props.begin(), props.end(),
-			[&](const property_ptr &p) {
-				if (other->deleted_props.count(p->get_key()) > 0)
-				{
-					other->deleted_props.erase(p->get_key());
-					return true;
-				}
-				return false;
-			}), props.end());
 }
 
 void
@@ -1187,6 +1203,7 @@ device_tree::collect_names_recursive(node_ptr &n, node_path &path)
 			{
 				node_names.insert(std::make_pair(name, n.get()));
 				node_paths.insert(std::make_pair(name, path));
+				ordered_node_paths.push_back({name, path});
 			}
 			else
 			{
@@ -1243,6 +1260,7 @@ device_tree::collect_names()
 	node_path p;
 	node_names.clear();
 	node_paths.clear();
+	ordered_node_paths.clear();
 	cross_references.clear();
 	fixups.clear();
 	collect_names_recursive(root, p);
@@ -1353,7 +1371,6 @@ device_tree::resolve_cross_references(uint32_t &phandle)
 		return node::VISIT_RECURSE;
 	}, nullptr);
 	assert(sorted_phandles.size() == fixups.size());
-
 	for (auto &i : sorted_phandles)
 	{
 		string target_name = i.get().val.string_data;
@@ -1441,6 +1458,103 @@ device_tree::resolve_cross_references(uint32_t &phandle)
 	}
 }
 
+bool
+device_tree::garbage_collect_marked_nodes()
+{
+	std::unordered_set<node*> previously_referenced_nodes;
+	std::unordered_set<node*> newly_referenced_nodes;
+
+	auto mark_referenced_nodes_used = [&](node &n)
+	{
+		for (auto &p : n.properties())
+		{
+			for (auto &v : *p)
+			{
+				if (v.is_phandle())
+				{
+					node *nx = node_names[v.string_data];
+					if (nx == nullptr)
+					{
+						// Try it again, but as a path
+						for (auto &s : node_paths)
+						{
+							if (v.string_data == s.second.to_string())
+							{
+								nx = node_names[s.first];
+								break;
+							}
+						}
+					}
+					if (nx == nullptr)
+					{
+						// Couldn't resolve this one?
+						continue;
+					}
+					// Only mark those currently unmarked
+					if (!nx->used)
+					{
+							nx->used = 1;
+							newly_referenced_nodes.insert(nx);
+					}
+				}
+			}
+		}
+	};
+
+	// Seed our referenced nodes with those that have been seen by a node that
+	// either will not be omitted if it's unreferenced or has a symbol.
+	// Nodes with symbols are explicitly not garbage collected because they may
+	// be expected for referencing by an overlay, and we do not want surprises
+	// there.
+	root->visit([&](node &n, node *) {
+		if (!n.omit_if_no_ref || (write_symbols && !n.labels.empty()))
+		{
+			mark_referenced_nodes_used(n);
+		}
+		// Recurse as normal
+		return node::VISIT_RECURSE;
+	}, nullptr);
+
+	while (!newly_referenced_nodes.empty())
+	{
+			previously_referenced_nodes = std::move(newly_referenced_nodes);
+			for (auto *n : previously_referenced_nodes)
+			{
+				mark_referenced_nodes_used(*n);
+			}
+	}
+
+	previously_referenced_nodes.clear();
+	bool children_deleted = false;
+
+	// Delete
+	root->visit([&](node &n, node *) {
+		bool gc_children = false;
+
+		for (auto &cn : n.child_nodes())
+		{
+				if (cn->omit_if_no_ref && !cn->used)
+				{
+					gc_children = true;
+					break;
+				}
+		}
+
+		if (gc_children)
+		{
+			children_deleted = true;
+			n.delete_children_if([](node_ptr &nx) {
+				return (nx->omit_if_no_ref && !nx->used);
+			});
+
+			return node::VISIT_CONTINUE;
+		}
+
+		return node::VISIT_RECURSE;
+	}, nullptr);
+
+	return children_deleted;
+}
 
 void
 device_tree::parse_file(text_input_buffer &input,
@@ -1486,7 +1600,7 @@ device_tree::parse_file(text_input_buffer &input,
 		if (input.consume('/'))
 		{
 			input.next_token();
-			n = node::parse(input, string(), string_set(), string(), &defines);
+			n = node::parse(input, *this, string(), string_set(), string(), &defines);
 		}
 		else if (input.consume('&'))
 		{
@@ -1507,7 +1621,7 @@ device_tree::parse_file(text_input_buffer &input,
 				name = input.parse_node_name();
 			}
 			input.next_token();
-			n = node::parse(input, std::move(name), string_set(), string(), &defines);
+			n = node::parse(input, *this, std::move(name), string_set(), string(), &defines);
 			n->name_is_path_reference = name_is_path_reference;
 		}
 		else
@@ -1890,6 +2004,12 @@ device_tree::parse_dts(const string &fn, FILE *depfile)
 		}
 	}
 	collect_names();
+	// Return value indicates whether we've dirtied the tree or not and need to
+	// recollect names
+	if (garbage_collect && garbage_collect_marked_nodes())
+	{
+		collect_names();
+	}
 	uint32_t phandle = 1;
 	// If we're writing symbols, go ahead and assign phandles to the entire
 	// tree. We'll do this before we resolve cross references, just to keep
@@ -1906,8 +2026,14 @@ device_tree::parse_dts(const string &fn, FILE *depfile)
 		// referenced by other plugins, so we create a __symbols__ node inside
 		// the root that contains mappings (properties) from label names to
 		// paths.
-		for (auto &s : node_paths)
+		for (auto i=ordered_node_paths.rbegin(), e=ordered_node_paths.rend() ; i!=e ; ++i)
 		{
+			auto &s = *i;
+			if (node_paths.find(s.first) == node_paths.end())
+			{
+				// Erased node, skip it.
+				continue;
+			}
 			property_value v;
 			v.string_data = s.second.to_string();
 			v.type = property_value::STRING;
@@ -1986,19 +2112,23 @@ device_tree::parse_dts(const string &fn, FILE *depfile)
 				{
 					if (c->name == p.first)
 					{
-						string path = p.first;
-						if (!(p.second.empty()))
+						if (c->unit_address == p.second)
 						{
-							path += '@';
-							path += p.second;
+							n = c.get();
+							found = true;
+							break;
 						}
-						n->add_child(node::create_special_node(path, symbols));
-						n = (--n->child_end())->get();
 					}
 				}
 				if (!found)
 				{
-					n->add_child(node::create_special_node(p.first, symbols));
+					string path = p.first;
+					if (!(p.second.empty()))
+					{
+						path += '@';
+						path += p.second;
+					}
+					n->add_child(node::create_special_node(path, symbols));
 					n = (--n->child_end())->get();
 				}
 			}
diff --git a/usr.bin/dtc/fdt.hh b/usr.bin/dtc/fdt.hh
index 3781d13c617f..2e414e145c7d 100644
--- a/usr.bin/dtc/fdt.hh
+++ b/usr.bin/dtc/fdt.hh
@@ -56,6 +56,7 @@ namespace fdt
 {
 class property;
 class node;
+class device_tree;
 /**
  * Type for (owned) pointers to properties.
  */
@@ -418,6 +419,17 @@ class node
 	 */
 	std::string unit_address;
 	/**
+	 * A flag indicating that this node has been marked /omit-if-no-ref/ and
+	 * will be omitted if it is not referenced, either directly or indirectly,
+	 * by a node that is not similarly denoted.
+	 */
+	bool omit_if_no_ref = false;
+	/**
+	 * A flag indicating that this node has been referenced, either directly
+	 * or indirectly, by a node that is not marked /omit-if-no-ref/.
+	 */
+	bool used = false;
+	/**
 	 * The type for the property vector.
 	 */
 	typedef std::vector<property_ptr> property_vector;
@@ -507,6 +519,7 @@ class node
 	 * already been parsed.
 	 */
 	node(text_input_buffer &input,
+	     device_tree &tree,
 	     std::string &&n,
 	     std::unordered_set<std::string> &&l,
 	     std::string &&a,
@@ -603,6 +616,7 @@ class node
 	 * have been parsed.
 	 */
 	static node_ptr parse(text_input_buffer &input,
+	                      device_tree &tree,
 	                      std::string &&name,
 	                      std::unordered_set<std::string> &&label=std::unordered_set<std::string>(),
 	                      std::string &&address=std::string(),
@@ -640,6 +654,13 @@ class node
 		children.push_back(std::move(n));
 	}
 	/**
+	 * Deletes any children from this node.
+	 */
+	inline void delete_children_if(bool (*predicate)(node_ptr &))
+	{
+		children.erase(std::remove_if(children.begin(), children.end(), predicate), children.end());
+	}
+	/**
 	 * Merges a node into this one.  Any properties present in both are
 	 * overridden, any properties present in only one are preserved.
 	 */
@@ -710,6 +731,11 @@ class device_tree
 	 */
 	bool valid = true;
 	/**
+	 * Flag indicating that this tree requires garbage collection.  This will be
+	 * set to true if a node marked /omit-if-no-ref/ is encountered.
+	 */
+	bool garbage_collect = false;
+	/**
 	 * 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
@@ -736,6 +762,12 @@ class device_tree
 	 */
 	std::unordered_map<std::string, node_path> node_paths;
 	/**
+	 * All of the elements in `node_paths` in the order that they were
+	 * created.  This is used for emitting the `__symbols__` section, where
+	 * we want to guarantee stable ordering.
+	 */
+	std::vector<std::pair<std::string, node_path>> ordered_node_paths;
+	/**
 	 * A collection of property values that are references to other nodes.
 	 * These should be expanded to the full path of their targets.
 	 */
@@ -847,10 +879,20 @@ class device_tree
 	 * node must have their values replaced by either the node path or
 	 * phandle value.  The phandle parameter holds the next phandle to be
 	 * assigned, should the need arise.  It will be incremented upon each
-	 * assignment of a phandle.
+	 * assignment of a phandle.  Garbage collection of unreferenced nodes
+	 * marked for "delete if unreferenced" will also occur here.
 	 */
 	void resolve_cross_references(uint32_t &phandle);
 	/**
+	 * Garbage collects nodes that have been marked /omit-if-no-ref/ and do not
+	 * have any references to them from nodes that are similarly marked.  This
+	 * is a fairly expensive operation.  The return value indicates whether the
+	 * tree has been dirtied as a result of this operation, so that the caller
+	 * may take appropriate measures to bring the device tree into a consistent
+	 * state as needed.
+	 */
+	bool garbage_collect_marked_nodes();
+	/**
 	 * 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,
@@ -933,6 +975,14 @@ class device_tree
 		return valid;
 	}
 	/**
+	 * Mark this tree as needing garbage collection, because an /omit-if-no-ref/
+	 * node has been encountered.
+	 */
+	void set_needs_garbage_collection()
+	{
+		garbage_collect = true;
+	}
+	/**
 	 * Sets the format for writing phandle properties.
 	 */
 	inline void set_phandle_format(phandle_format f)
diff --git a/usr.bin/dtc/input_buffer.cc b/usr.bin/dtc/input_buffer.cc
index 38b38b46c878..1f4775c8b78c 100644
--- a/usr.bin/dtc/input_buffer.cc
+++ b/usr.bin/dtc/input_buffer.cc
@@ -126,7 +126,7 @@ mmap_input_buffer::~mmap_input_buffer()
 {
 	if (buffer != 0)
 	{
-		munmap((void*)buffer, size);
+		munmap(const_cast<char*>(buffer), size);
 	}
 }
 
diff --git a/usr.bin/dtc/util.hh b/usr.bin/dtc/util.hh
index 84646b444b3a..2f0727e87eb5 100644
--- a/usr.bin/dtc/util.hh
+++ b/usr.bin/dtc/util.hh
@@ -47,6 +47,38 @@
 #endif
 #endif
 
+#ifdef MISSING_DIGITTOINT
+namespace
+{
+	/**
+	 * Glibc doesn't have a definition of digittoint, so provide our own.
+	 */
+	inline int digittoint(int c)
+	{
+		switch (c)
+		{
+			default:
+			case '0': return 0;
+			case '1': return 1;
+			case '2': return 2;
+			case '3': return 3;
+			case '4': return 4;
+			case '5': return 5;
+			case '6': return 6;
+			case '7': return 7;
+			case '8': return 8;
+			case '9': return 9;
+			case 'a': return 10;
+			case 'b': return 11;
+			case 'c': return 12;
+			case 'd': return 13;
+			case 'e': return 14;
+			case 'f': return 15;
+		}
+	}
+}
+#endif
+
 namespace dtc {
 
 /**