Import new (BSDL) device tree compiler. Now built by default, so that it can't

be used on the host system (and not installed on the device, if required).  The
GPL'd one is still available if there are any devices that need it (make
universe passes with it, including kernels that use fdt, but there may be some
out-of-tree ones).  WITH_GPL_DTC can be used to select the old one, for now.

Probably won't be MFC'd, but we'll remove the GPL'd version in head after the
new one has had a lot more testing and ship it in 10.0.

1 files changed, 1357 insertions, 0 deletions

diff --git a/usr.bin/dtc/fdt.cc b/usr.bin/dtc/fdt.cc
new file mode 100644
index 0000000..70b7d45
--- /dev/null
+++ b/usr.bin/dtc/fdt.cc
@@ -0,0 +1,1357 @@
+/*-
+ * 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 "fdt.hh"
+
+#include <algorithm>
+#include <inttypes.h>
+#include <fcntl.h>
+#include <libgen.h>
+#include "dtb.hh"
+
+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;
+		for (byte_buffer::iterator i=byte_data.begin(), e=byte_data.end()-1; i<e ; i++)
+		{
+			bytes++;
+			is_all_printable &= (*i == '\0') || isprint(*i);
+			if (*i == '\0')
+			{
+				nuls++;
+			}
+			if (!is_all_printable)
+			{
+				break;
+			}
+		}
+		if (is_all_printable && (bytes > nuls))
+		{
+			type = STRING;
+			if (nuls > 0)
+			{
+				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
+	{
+		for (byte_buffer::iterator i=byte_data.begin(), e=byte_data.end()-1; i!=e ; ++i)
+		{
+			// FIXME Escape tabs, newlines, and so on.
+			if (*i == '\0')
+			{
+				fputs("\", \"", file);
+				continue;
+			}
+			putc(*i, file);
+		}
+	}
+	putc('"', file);
+}
+
+void
+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)
+	{
+		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 (byte_buffer::iterator i=byte_data.begin(), e=byte_data.end(); i!=e ; i++)
+	{
+		fprintf(file, "%hhx", *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)
+{
+	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('&'))
+		{
+			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.
+			long long val;
+			if (!input.consume_integer(val))
+			{
+				input.parse_error("Expected numbers in array of cells");
+				valid = false;
+				return;
+			}
+			push_big_endian(v.byte_data, (uint32_t)val);
+			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);
+	// Read the value
+	uint8_t byte;
+	property_value v;
+	for (uint32_t i=0 ; i<length ; i++)
+	{
+		if (!(valid = structs.consume_binary(byte)))
+		{
+			fprintf(stderr, "Failed to read property value\n");
+			return;
+		}
+		v.byte_data.push_back(byte);
+	}
+	values.push_back(v);
+}
+
+property::property(input_buffer &input, string k, string l) : key(k), label(l),
+	valid(true)
+{
+	do {
+		input.next_token();
+		switch (input[0])
+		{
+			default:
+				input.parse_error("Invalid property value.");
+				valid = false;
+				return;
+			case '"':
+				parse_string(input);
+				break;
+			case '<':
+				parse_cells(input);
+				break;
+			case '[':
+				parse_bytes(input);
+				break;
+			case '&':
+				parse_reference(input);
+				break;
+			case ';':
+			{
+				break;
+			}
+		}
+		input.next_token();
+	} while (input.consume(','));
+	if (!input.consume(';'))
+	{
+		input.parse_error("Expected ; at end of property");
+		valid = false;
+	}
+}
+
+property*
+property::parse_dtb(input_buffer &structs, input_buffer &strings)
+{
+	property *p = new property(structs, strings);
+	if (!p->valid)
+	{
+		delete p;
+		p = 0;
+	}
+	return p;
+}
+
+property*
+property::parse(input_buffer &input, string key, string label)
+{
+	property *p = new property(input, key, label);
+	if (!p->valid)
+	{
+		delete p;
+		p = 0;
+	}
+	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);
+}
+
+void
+property::write_dts(FILE *file, int indent)
+{
+	for (int i=0 ; i<indent ; i++)
+	{
+		putc('\t', file);
+	}
+	if (label != string())
+	{
+		label.print(file);
+		fputs(": ", file);
+	}
+	if (key != string())
+	{
+		key.print(file);
+	}
+	if (!values.empty())
+	{
+		fputs(" = ", file);
+		for (value_iterator i=begin(), e=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;
+}
+
+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 *child = node::parse_dtb(structs, strings);
+				if (child == 0)
+				{
+					valid = false;
+					return;
+				}
+				children.push_back(child);
+				break;
+			}
+			// End of this node, no errors.
+			case dtb::FDT_END_NODE:
+				return;
+			// Property, parse it.
+			case dtb::FDT_PROP:
+			{
+				property *prop = property::parse_dtb(structs, strings);
+				if (prop == 0)
+				{
+					valid = false;
+					return;
+				}
+				properties.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) : 
+	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 *p= property::parse(input, child_name,
+					child_label);
+			if (p == 0)
+			{
+				valid = false;
+			}
+			else
+			{
+				properties.push_back(p);
+			}
+		}
+		else if (!is_property && input[0] == ('{'))
+		{
+			node *child = node::parse(input, child_name,
+					child_label, child_address);
+			if (child)
+			{
+				children.push_back(child);
+			}
+			else
+			{
+				valid = false;
+			}
+		}
+		else if (input.consume(';'))
+		{
+			properties.push_back(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 *p1, property *p2)
+{
+	return p1->get_key() < p2->get_key();
+}
+
+bool
+node::cmp_children(node *c1, node *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)
+	{
+		(*i)->sort();
+	}
+}
+
+node*
+node::parse(input_buffer &input, string name, string label, string address)
+{
+	node *n = new node(input, name, label, address);
+	if (!n->valid)
+	{
+		delete n;
+		n = 0;
+	}
+	return n;
+}
+
+node*
+node::parse_dtb(input_buffer &structs, input_buffer &strings)
+{
+	node *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*
+node::get_property(string key)
+{
+	for (property_iterator i=property_begin(), e=property_end() ; i!=e ; ++i)
+	{
+		if ((*i)->get_key() == key)
+		{
+			return *i;
+		}
+	}
+	return 0;
+}
+
+void
+node::merge_node(node *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.
+	while (!other->properties.empty())
+	{
+		property *p = other->properties.front();
+		for (property_iterator i=property_begin(), e=property_end() ; i!=e ; ++i)
+		{
+			if ((*i)->get_key() == p->get_key())
+			{
+				delete *i;
+				properties.erase(i);
+				break;
+			}
+		}
+		add_property(p);
+		other->properties.erase(other->properties.begin());
+	}
+	while (!other->children.empty())
+	{
+		node *c = other->children.front();
+		bool found = false;
+		for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i)
+		{
+			if ((*i)->name == c->name && (*i)->unit_address == c->unit_address)
+			{
+				(*i)->merge_node(c);
+				delete c;
+				found = true;
+				break;
+			}
+		}
+		if (!found)
+		{
+			children.push_back(c);
+		}
+		other->children.erase(other->children.begin());
+	}
+}
+
+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 (property_iterator i=property_begin(), e=property_end() ; i!=e ; ++i)
+	{
+		(*i)->write(writer, strings);
+	}
+	for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i)
+	{
+		(*i)->write(writer, strings);
+	}
+	writer.write_token(dtb::FDT_END_NODE);
+}
+
+void
+node::write_dts(FILE *file, int indent)
+{
+	for (int i=0 ; i<indent ; i++)
+	{
+		putc('\t', file);
+	}
+	if (label != string())
+	{
+		label.print(file);
+		fputs(": ", file);
+	}
+	if (name != string())
+	{
+		name.print(file);
+	}
+	if (unit_address != string())
+	{
+		putc('@', file);
+		unit_address.print(file);
+	}
+	fputs(" {\n\n", file);
+	for (property_iterator i=property_begin(), e=property_end() ; i!=e ; ++i)
+	{
+		(*i)->write_dts(file, indent+1);
+	}
+	for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i)
+	{
+		(*i)->write_dts(file, indent+1);
+	}
+	for (int i=0 ; i<indent ; i++)
+	{
+		putc('\t', file);
+	}
+	fputs("};\n", file);
+}
+
+void
+device_tree::collect_names_recursive(node* n, node_path &path)
+{
+	string name = n->label;
+	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));
+			node_paths.insert(std::make_pair(name, path));
+		}
+		else
+		{
+			node_names[name] = (node*)-1;
+			std::map<string, node_path>::iterator 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)
+	{
+		collect_names_recursive(*i, 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 (property::value_iterator p=(*i)->begin(),pe=(*i)->end() ; p!=pe ; ++p)
+		{
+			if (p->is_phandle())
+			{
+				phandles.push_back(&*p);
+			}
+			if (p->is_cross_reference())
+			{
+				cross_references.push_back(&*p);
+			}
+		}
+		if ((*i)->get_key() == string("phandle") ||
+		    (*i)->get_key() == string("linux,phandle"))
+		{
+			if ((*i)->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();
+				used_phandles.insert(std::make_pair(phandle, n));
+			}
+		}
+	}
+}
+
+void
+device_tree::collect_names()
+{
+	node_path p;
+	collect_names_recursive(root, p);
+}
+
+void
+device_tree::resolve_cross_references()
+{
+	for (std::vector<property_value*>::iterator i=cross_references.begin(), e=cross_references.end() ; i!=e ; ++i)
+	{
+		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)
+		{
+			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;
+	for (std::vector<property_value*>::iterator i=phandles.begin(), e=phandles.end() ; i!=e ; ++i)
+	{
+		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 *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 = 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->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_roots(input_buffer &input, std::vector<node*> &roots)
+{
+	input.next_token();
+	while (valid && input.consume('/'))
+	{
+		input.next_token();
+		node *n = node::parse(input, string("", 1));
+		if (n)
+		{
+			roots.push_back(n);
+		}
+		else
+		{
+			valid = false;
+		}
+	}
+}
+
+input_buffer*
+device_tree::buffer_for_file(const char *path)
+{
+	if (string(path) == string("-"))
+	{
+		input_buffer *b = new stream_input_buffer();
+		buffers.push_back(b);
+		return b;
+	}
+	int source = open(path, O_RDONLY);
+	if (source == -1)
+	{
+		fprintf(stderr, "Unable to open file %s\n", path);
+		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.
+	buffers.push_back(b);
+	close(source);
+	return b;
+}
+
+template<class writer> 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 (std::vector<reservation>::iterator i=reservations.begin(),
+	     e=reservations.end() ; i!=e ; ++i)
+	{
+		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<blob_padding ; i++)
+	{
+		strings_writer.write_data((uint8_t)0);
+	}
+	head.totalsize = sizeof(head) + strings_writer.size() +
+		struct_writer.size() + reservation_writer.size();
+	while (head.totalsize < minimum_blob_size)
+	{
+		head.totalsize++;
+		strings_writer.write_data((uint8_t)0);
+	}
+	head.off_dt_struct = sizeof(head) + reservation_writer.size();;
+	head.off_dt_strings = head.off_dt_struct + struct_writer.size();
+	head.off_mem_rsvmap = sizeof(head);
+	head.boot_cpuid_phys = boot_cpu;
+	head.size_dt_struct = struct_writer.size();
+	head.write(head_writer);
+
+	head_writer.write_to_file(fd);
+	reservation_writer.write_to_file(fd);
+	struct_writer.write_to_file(fd);
+	strings_writer.write_label(string("dt_blob_end"));
+	strings_writer.write_to_file(fd);
+}
+
+node*
+device_tree::referenced_node(property_value &v)
+{
+	if (v.is_phandle())
+	{
+		return node_names[v.string_data];
+	}
+	if (v.is_binary())
+	{
+		return used_phandles[v.get_as_uint32()];
+	}
+	return 0;
+}
+
+void
+device_tree::write_binary(int fd)
+{
+	write<dtb::binary_writer>(fd);
+}
+
+void
+device_tree::write_asm(int fd)
+{
+	write<dtb::asm_writer>(fd);
+}
+
+void
+device_tree::write_dts(int fd)
+{
+	FILE *file = fdopen(fd, "w");
+	fputs("/dtc-v1/;\n\n", file);
+
+	if (!reservations.empty())
+	{
+		const char msg[] = "/memreserve/";
+		fwrite(msg, sizeof(msg), 1, file);
+		for (std::vector<reservation>::iterator i=reservations.begin(),
+		     e=reservations.end() ; i!=e ; ++i)
+		{
+			fprintf(stderr, " %" 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)
+{
+	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);
+	if (in == 0)
+	{
+		valid = false;
+		return;
+	}
+	std::vector<node*> 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/"))
+	{
+		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_buffer *include_buffer = buffer_for_file(include_file);
+
+		if (include_buffer == 0)
+		{
+			for (std::vector<const char*>::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;
+		input.consume(include_file+dir_length+1);
+		input.consume('"');
+		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 /dts-v1/; version string");
+		}
+		input.next_token();
+		input.consume(';');
+		reservations.push_back(reservation(start, len));
+	}
+	parse_roots(input, roots);
+	switch (roots.size())
+	{
+		case 0:
+			valid = false;
+			input.parse_error("Failed to find root node /.");
+			return;
+		case 1:
+			root = roots[0];
+			break;
+		default:
+		{
+			root = roots[0];
+			for (std::vector<node*>::iterator i=roots.begin()+1,
+			     e=roots.end() ; i!=e ; ++i)
+			{
+				root->merge_node(*i);
+				delete *i;
+			}
+			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();
+	}
+}
+
+} // namespace fdt
+
+} // namespace dtc
+