dtc(1): Update to 1a79f5f26631

Highlights:
- Bugfix for order in which /delete-node/ and /delete-property/ are
  processed [0]
- /omit-if-no-ref/ support has been added (used only by U-Boot at this
  point, in theory)
- GPL dtc compat version bumped to 1.4.7
- Various small fixes and compatibility improvements

Reported by:	strejda [0]
MFC after:	1 week

1 files changed, 166 insertions, 36 deletions

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();
 				}
 			}