xref: /freebsd/usr.bin/dtc/fdt.cc (revision 6b7b2d80ed4d728d3ffd12c422e57798c1b63a84)
1 /*-
2  * Copyright (c) 2013 David Chisnall
3  * All rights reserved.
4  *
5  * This software was developed by SRI International and the University of
6  * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237)
7  * ("CTSRD"), as part of the DARPA CRASH research programme.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  * 1. Redistributions of source code must retain the above copyright
13  *    notice, this list of conditions and the following disclaimer.
14  * 2. Redistributions in binary form must reproduce the above copyright
15  *    notice, this list of conditions and the following disclaimer in the
16  *    documentation and/or other materials provided with the distribution.
17  *
18  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
22  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28  * SUCH DAMAGE.
29  *
30  * $FreeBSD$
31  */
32 
33 #define __STDC_LIMIT_MACROS 1
34 
35 #include "fdt.hh"
36 #include "dtb.hh"
37 
38 #include <algorithm>
39 
40 #include <ctype.h>
41 #include <fcntl.h>
42 #include <inttypes.h>
43 #include <libgen.h>
44 #include <stdio.h>
45 #include <stdlib.h>
46 #include <unistd.h>
47 #include <sys/types.h>
48 #include <sys/stat.h>
49 #include <errno.h>
50 
51 namespace dtc
52 {
53 
54 namespace fdt
55 {
56 
57 uint32_t
58 property_value::get_as_uint32()
59 {
60 	if (byte_data.size() != 4)
61 	{
62 		return 0;
63 	}
64 	uint32_t v = 0;
65 	v &= byte_data[0] << 24;
66 	v &= byte_data[1] << 16;
67 	v &= byte_data[2] << 8;
68 	v &= byte_data[3] << 0;
69 	return v;
70 }
71 
72 void
73 property_value::push_to_buffer(byte_buffer &buffer)
74 {
75 	if (!byte_data.empty())
76 	{
77 		buffer.insert(buffer.end(), byte_data.begin(), byte_data.end());
78 	}
79 	else
80 	{
81 		string_data.push_to_buffer(buffer, true);
82 		// Trailing nul
83 		buffer.push_back(0);
84 	}
85 }
86 
87 void
88 property_value::write_dts(FILE *file)
89 {
90 	resolve_type();
91 	switch (type)
92 	{
93 		default:
94 			assert(0 && "Invalid type");
95 		case STRING:
96 		case STRING_LIST:
97 		case CROSS_REFERENCE:
98 			write_as_string(file);
99 			break;
100 		case PHANDLE:
101 			write_as_cells(file);
102 			break;
103 		case BINARY:
104 			if (byte_data.size() % 4 == 0)
105 			{
106 				write_as_cells(file);
107 				break;
108 			}
109 			write_as_bytes(file);
110 			break;
111 	}
112 }
113 
114 void
115 property_value::resolve_type()
116 {
117 	if (type != UNKNOWN)
118 	{
119 		return;
120 	}
121 	if (byte_data.empty())
122 	{
123 		type = STRING;
124 		return;
125 	}
126 	if (byte_data.back() == 0)
127 	{
128 		bool is_all_printable = true;
129 		int nuls = 0;
130 		int bytes = 0;
131 		bool lastWasNull = false;
132 		for (auto i : byte_data)
133 		{
134 			bytes++;
135 			is_all_printable &= (i == '\0') || isprint(i);
136 			if (i == '\0')
137 			{
138 				// If there are two nulls in a row, then we're probably binary.
139 				if (lastWasNull)
140 				{
141 					type = BINARY;
142 					return;
143 				}
144 				nuls++;
145 				lastWasNull = true;
146 			}
147 			else
148 			{
149 				lastWasNull = false;
150 			}
151 			if (!is_all_printable)
152 			{
153 				break;
154 			}
155 		}
156 		if ((is_all_printable && (bytes > nuls)) || bytes == 0)
157 		{
158 			type = STRING;
159 			if (nuls > 1)
160 			{
161 				type = STRING_LIST;
162 			}
163 			return;
164 		}
165 	}
166 	type = BINARY;
167 }
168 
169 void
170 property_value::write_as_string(FILE *file)
171 {
172 	putc('"', file);
173 	if (byte_data.empty())
174 	{
175 		string_data.print(file);
176 	}
177 	else
178 	{
179 		bool hasNull = (byte_data.back() == '\0');
180 		// Remove trailing null bytes from the string before printing as dts.
181 		if (hasNull)
182 		{
183 			byte_data.pop_back();
184 		}
185 		for (auto i : byte_data)
186 		{
187 			// FIXME Escape tabs, newlines, and so on.
188 			if (i == '\0')
189 			{
190 				fputs("\", \"", file);
191 				continue;
192 			}
193 			putc(i, file);
194 		}
195 		if (hasNull)
196 		{
197 			byte_data.push_back('\0');
198 		}
199 	}
200 	putc('"', file);
201 }
202 
203 void
204 property_value::write_as_cells(FILE *file)
205 {
206 	putc('<', file);
207 	assert((byte_data.size() % 4) == 0);
208 	for (auto i=byte_data.begin(), e=byte_data.end(); i!=e ; ++i)
209 	{
210 		uint32_t v = 0;
211 		v = (v << 8) | *i;
212 		++i;
213 		v = (v << 8) | *i;
214 		++i;
215 		v = (v << 8) | *i;
216 		++i;
217 		v = (v << 8) | *i;
218 		fprintf(file, "0x%" PRIx32, v);
219 		if (i+1 != e)
220 		{
221 			putc(' ', file);
222 		}
223 	}
224 	putc('>', file);
225 }
226 
227 void
228 property_value::write_as_bytes(FILE *file)
229 {
230 	putc('[', file);
231 	for (auto i=byte_data.begin(), e=byte_data.end(); i!=e ; i++)
232 	{
233 		fprintf(file, "%02hhx", *i);
234 		if (i+1 != e)
235 		{
236 			putc(' ', file);
237 		}
238 	}
239 	putc(']', file);
240 }
241 
242 void
243 property::parse_string(input_buffer &input)
244 {
245 	property_value v;
246 	assert(input[0] == '"');
247 	++input;
248 	const char *start = (const char*)input;
249 	int length = 0;
250 	while (char c = input[0])
251 	{
252 		if (c == '"' && input[-1] != '\\')
253 		{
254 			input.consume('"');
255 			break;
256 		}
257 		++input;
258 		++length;
259 	}
260 	v.string_data = string(start, length);
261 	values.push_back(v);
262 }
263 
264 void
265 property::parse_cells(input_buffer &input, int cell_size)
266 {
267 	assert(input[0] == '<');
268 	++input;
269 	property_value v;
270 	input.next_token();
271 	while (!input.consume('>'))
272 	{
273 		input.next_token();
274 		// If this is a phandle then we need to get the name of the
275 		// referenced node
276 		if (input.consume('&'))
277 		{
278 			if (cell_size != 32)
279 			{
280 				input.parse_error("reference only permitted in 32-bit arrays");
281 				valid = false;
282 				return;
283 			}
284 			input.next_token();
285 			// FIXME: We should support full paths here, but we
286 			// don't.
287 			string referenced = string::parse_node_name(input);
288 			if (referenced.empty())
289 			{
290 				input.parse_error("Expected node name");
291 				valid = false;
292 				return;
293 			}
294 			input.next_token();
295 			// If we already have some bytes, make the phandle a
296 			// separate component.
297 			if (!v.byte_data.empty())
298 			{
299 				values.push_back(v);
300 				v = property_value();
301 			}
302 			v.string_data = referenced;
303 			v.type = property_value::PHANDLE;
304 			values.push_back(v);
305 			v = property_value();
306 		}
307 		else
308 		{
309 			//FIXME: We should support labels in the middle
310 			//of these, but we don't.
311 			unsigned long long val;
312 			if (!input.consume_integer_expression(val))
313 			{
314 				input.parse_error("Expected numbers in array of cells");
315 				valid = false;
316 				return;
317 			}
318 			switch (cell_size)
319 			{
320 				case 8:
321 					v.byte_data.push_back(val);
322 					break;
323 				case 16:
324 					push_big_endian(v.byte_data, (uint16_t)val);
325 					break;
326 				case 32:
327 					push_big_endian(v.byte_data, (uint32_t)val);
328 					break;
329 				case 64:
330 					push_big_endian(v.byte_data, (uint64_t)val);
331 					break;
332 				default:
333 					assert(0 && "Invalid cell size!");
334 			}
335 			input.next_token();
336 		}
337 	}
338 	// Don't store an empty string value here.
339 	if (v.byte_data.size() > 0)
340 	{
341 		values.push_back(v);
342 	}
343 }
344 
345 void
346 property::parse_bytes(input_buffer &input)
347 {
348 	assert(input[0] == '[');
349 	++input;
350 	property_value v;
351 	input.next_token();
352 	while (!input.consume(']'))
353 	{
354 		{
355 			//FIXME: We should support
356 			//labels in the middle of
357 			//these, but we don't.
358 			uint8_t val;
359 			if (!input.consume_hex_byte(val))
360 			{
361 				input.parse_error("Expected hex bytes in array of bytes");
362 				valid = false;
363 				return;
364 			}
365 			v.byte_data.push_back(val);
366 			input.next_token();
367 		}
368 	}
369 	values.push_back(v);
370 }
371 
372 void
373 property::parse_reference(input_buffer &input)
374 {
375 	assert(input[0] == '&');
376 	++input;
377 	input.next_token();
378 	property_value v;
379 	v.string_data = string::parse_node_name(input);
380 	if (v.string_data.empty())
381 	{
382 		input.parse_error("Expected node name");
383 		valid = false;
384 		return;
385 	}
386 	v.type = property_value::CROSS_REFERENCE;
387 	values.push_back(v);
388 }
389 
390 property::property(input_buffer &structs, input_buffer &strings)
391 {
392 	uint32_t name_offset;
393 	uint32_t length;
394 	valid = structs.consume_binary(length) &&
395 		structs.consume_binary(name_offset);
396 	if (!valid)
397 	{
398 		fprintf(stderr, "Failed to read property\n");
399 		return;
400 	}
401 	// Find the name
402 	input_buffer name_buffer = strings.buffer_from_offset(name_offset);
403 	if (name_buffer.empty())
404 	{
405 		fprintf(stderr, "Property name offset %" PRIu32
406 			" is past the end of the strings table\n",
407 			name_offset);
408 		valid = false;
409 		return;
410 	}
411 	key = string(name_buffer);
412 
413 	// If we're empty, do not push anything as value.
414 	if (!length)
415 		return;
416 
417 	// Read the value
418 	uint8_t byte;
419 	property_value v;
420 	for (uint32_t i=0 ; i<length ; i++)
421 	{
422 		if (!(valid = structs.consume_binary(byte)))
423 		{
424 			fprintf(stderr, "Failed to read property value\n");
425 			return;
426 		}
427 		v.byte_data.push_back(byte);
428 	}
429 	values.push_back(v);
430 }
431 
432 void property::parse_define(input_buffer &input, define_map *defines)
433 {
434 	input.consume('$');
435 	if (!defines)
436 	{
437 		input.parse_error("No predefined properties to match name\n");
438 		valid = false;
439 		return;
440 	}
441 	string name = string::parse_property_name(input);
442 	define_map::iterator found;
443 	if ((name == string()) ||
444 	    ((found = defines->find(name)) == defines->end()))
445 	{
446 		input.parse_error("Undefined property name\n");
447 		valid = false;
448 		return;
449 	}
450 	values.push_back((*found).second->values[0]);
451 }
452 
453 property::property(input_buffer &input,
454                    string k,
455                    string l,
456                    bool semicolonTerminated,
457                    define_map *defines) : key(k), label(l), valid(true)
458 {
459 	do {
460 		input.next_token();
461 		switch (input[0])
462 		{
463 			case '$':
464 			{
465 				parse_define(input, defines);
466 				if (valid)
467 				{
468 					break;
469 				}
470 			}
471 			default:
472 				input.parse_error("Invalid property value.");
473 				valid = false;
474 				return;
475 			case '/':
476 			{
477 				unsigned long long bits = 0;
478 				valid = input.consume("/bits/");
479 				input.next_token();
480 				valid &= input.consume_integer(bits);
481 				if ((bits != 8) &&
482 				    (bits != 16) &&
483 				    (bits != 32) &&
484 				    (bits != 64)) {
485 					input.parse_error("Invalid size for elements");
486 					valid = false;
487 				}
488 				if (!valid) return;
489 				input.next_token();
490 				if (input[0] != '<')
491 				{
492 					input.parse_error("/bits/ directive is only valid on arrays");
493 					valid = false;
494 					return;
495 				}
496 				parse_cells(input, bits);
497 				break;
498 			}
499 			case '"':
500 				parse_string(input);
501 				break;
502 			case '<':
503 				parse_cells(input, 32);
504 				break;
505 			case '[':
506 				parse_bytes(input);
507 				break;
508 			case '&':
509 				parse_reference(input);
510 				break;
511 			case ';':
512 			{
513 				break;
514 			}
515 		}
516 		input.next_token();
517 	} while (input.consume(','));
518 	if (semicolonTerminated && !input.consume(';'))
519 	{
520 		input.parse_error("Expected ; at end of property");
521 		valid = false;
522 	}
523 }
524 
525 property_ptr
526 property::parse_dtb(input_buffer &structs, input_buffer &strings)
527 {
528 	property_ptr p(new property(structs, strings));
529 	if (!p->valid)
530 	{
531 		p = nullptr;
532 	}
533 	return p;
534 }
535 
536 property_ptr
537 property::parse(input_buffer &input, string key, string label,
538                 bool semicolonTerminated, define_map *defines)
539 {
540 	property_ptr p(new property(input, key, label, semicolonTerminated, defines));
541 	if (!p->valid)
542 	{
543 		p = nullptr;
544 	}
545 	return p;
546 }
547 
548 void
549 property::write(dtb::output_writer &writer, dtb::string_table &strings)
550 {
551 	writer.write_token(dtb::FDT_PROP);
552 	byte_buffer value_buffer;
553 	for (value_iterator i=begin(), e=end() ; i!=e ; ++i)
554 	{
555 		i->push_to_buffer(value_buffer);
556 	}
557 	writer.write_data((uint32_t)value_buffer.size());
558 	writer.write_comment(key);
559 	writer.write_data(strings.add_string(key));
560 	writer.write_data(value_buffer);
561 }
562 
563 bool
564 property_value::try_to_merge(property_value &other)
565 {
566 	resolve_type();
567 	switch (type)
568 	{
569 		case UNKNOWN:
570 			__builtin_unreachable();
571 			assert(0);
572 			return false;
573 		case EMPTY:
574 			*this = other;
575 		case STRING:
576 		case STRING_LIST:
577 		case CROSS_REFERENCE:
578 			return false;
579 		case PHANDLE:
580 		case BINARY:
581 			if (other.type == PHANDLE || other.type == BINARY)
582 			{
583 				type = BINARY;
584 				byte_data.insert(byte_data.end(), other.byte_data.begin(),
585 				                 other.byte_data.end());
586 				return true;
587 			}
588 	}
589 	return false;
590 }
591 
592 void
593 property::write_dts(FILE *file, int indent)
594 {
595 	for (int i=0 ; i<indent ; i++)
596 	{
597 		putc('\t', file);
598 	}
599 	if (label != string())
600 	{
601 		label.print(file);
602 		fputs(": ", file);
603 	}
604 	if (key != string())
605 	{
606 		key.print(file);
607 	}
608 	if (!values.empty())
609 	{
610 		std::vector<property_value> *vals = &values;
611 		std::vector<property_value> v;
612 		// If we've got multiple values then try to merge them all together.
613 		if (values.size() > 1)
614 		{
615 			vals = &v;
616 			v.push_back(values.front());
617 			for (auto i=(++begin()), e=end() ; i!=e ; ++i)
618 			{
619 				if (!v.back().try_to_merge(*i))
620 				{
621 					v.push_back(*i);
622 				}
623 			}
624 		}
625 		fputs(" = ", file);
626 		for (auto i=vals->begin(), e=vals->end() ; i!=e ; ++i)
627 		{
628 			i->write_dts(file);
629 			if (i+1 != e)
630 			{
631 				putc(',', file);
632 				putc(' ', file);
633 			}
634 		}
635 	}
636 	fputs(";\n", file);
637 }
638 
639 string
640 node::parse_name(input_buffer &input, bool &is_property, const char *error)
641 {
642 	if (!valid)
643 	{
644 		return string();
645 	}
646 	input.next_token();
647 	if (is_property)
648 	{
649 		return string::parse_property_name(input);
650 	}
651 	string n = string::parse_node_or_property_name(input, is_property);
652 	if (n.empty())
653 	{
654 		if (n.empty())
655 		{
656 			input.parse_error(error);
657 			valid = false;
658 		}
659 	}
660 	return n;
661 }
662 
663 void
664 node::visit(std::function<void(node&)> fn)
665 {
666 	fn(*this);
667 	for (auto &&c : children)
668 	{
669 		c->visit(fn);
670 	}
671 }
672 
673 node::node(input_buffer &structs, input_buffer &strings) : valid(true)
674 {
675 	const char *name_start = (const char*)structs;
676 	int name_length = 0;
677 	while (structs[0] != '\0' && structs[0] != '@')
678 	{
679 		name_length++;
680 		++structs;
681 	}
682 	name = string(name_start, name_length);
683 	if (structs[0] == '@')
684 	{
685 		++structs;
686 		name_start = (const char*)structs;
687 		name_length = 0;
688 		while (structs[0] != '\0')
689 		{
690 			name_length++;
691 			++structs;
692 		}
693 		unit_address = string(name_start, name_length);
694 	}
695 	++structs;
696 	uint32_t token;
697 	while (structs.consume_binary(token))
698 	{
699 		switch (token)
700 		{
701 			default:
702 				fprintf(stderr, "Unexpected token 0x%" PRIx32
703 					" while parsing node.\n", token);
704 				valid = false;
705 				return;
706 			// Child node, parse it.
707 			case dtb::FDT_BEGIN_NODE:
708 			{
709 				node_ptr child = node::parse_dtb(structs, strings);
710 				if (child == 0)
711 				{
712 					valid = false;
713 					return;
714 				}
715 				children.push_back(std::move(child));
716 				break;
717 			}
718 			// End of this node, no errors.
719 			case dtb::FDT_END_NODE:
720 				return;
721 			// Property, parse it.
722 			case dtb::FDT_PROP:
723 			{
724 				property_ptr prop = property::parse_dtb(structs, strings);
725 				if (prop == 0)
726 				{
727 					valid = false;
728 					return;
729 				}
730 				props.push_back(prop);
731 				break;
732 			}
733 				break;
734 			// End of structs table.  Should appear after
735 			// the end of the last node.
736 			case dtb::FDT_END:
737 				fprintf(stderr, "Unexpected FDT_END token while parsing node.\n");
738 				valid = false;
739 				return;
740 			// NOPs are padding.  Ignore them.
741 			case dtb::FDT_NOP:
742 				break;
743 		}
744 	}
745 	fprintf(stderr, "Failed to read token from structs table while parsing node.\n");
746 	valid = false;
747 	return;
748 }
749 
750 node::node(input_buffer &input, string n, string l, string a, define_map *defines) :
751 	label(l), name(n), unit_address(a), valid(true)
752 {
753 	if (!input.consume('{'))
754 	{
755 		input.parse_error("Expected { to start new device tree node.\n");
756 	}
757 	input.next_token();
758 	while (valid && !input.consume('}'))
759 	{
760 		// flag set if we find any characters that are only in
761 		// the property name character set, not the node
762 		bool is_property = false;
763 		string child_name, child_label, child_address;
764 		child_name = parse_name(input, is_property,
765 				"Expected property or node name");
766 		if (input.consume(':'))
767 		{
768 			// Node labels can contain any characters?  The
769 			// spec doesn't say, so we guess so...
770 			is_property = false;
771 			child_label = child_name;
772 			child_name = parse_name(input, is_property, "Expected property or node name");
773 		}
774 		if (input.consume('@'))
775 		{
776 			child_address = parse_name(input, is_property, "Expected unit address");
777 		}
778 		if (!valid)
779 		{
780 			return;
781 		}
782 		input.next_token();
783 		// If we're parsing a property, then we must actually do that.
784 		if (input.consume('='))
785 		{
786 			property_ptr p = property::parse(input, child_name,
787 					child_label, true, defines);
788 			if (p == 0)
789 			{
790 				valid = false;
791 			}
792 			else
793 			{
794 				props.push_back(p);
795 			}
796 		}
797 		else if (!is_property && input[0] == ('{'))
798 		{
799 			node_ptr child = node::parse(input, child_name,
800 					child_label, child_address, defines);
801 			if (child)
802 			{
803 				children.push_back(std::move(child));
804 			}
805 			else
806 			{
807 				valid = false;
808 			}
809 		}
810 		else if (input.consume(';'))
811 		{
812 			props.push_back(property_ptr(new property(child_name, child_label)));
813 		}
814 		else
815 		{
816 			input.parse_error("Error parsing property.");
817 			valid = false;
818 		}
819 		input.next_token();
820 	}
821 	input.consume(';');
822 }
823 
824 bool
825 node::cmp_properties(property_ptr &p1, property_ptr &p2)
826 {
827 	return p1->get_key() < p2->get_key();
828 }
829 
830 bool
831 node::cmp_children(node_ptr &c1, node_ptr &c2)
832 {
833 	if (c1->name == c2->name)
834 	{
835 		return c1->unit_address < c2->unit_address;
836 	}
837 	return c1->name < c2->name;
838 }
839 
840 void
841 node::sort()
842 {
843 	std::sort(property_begin(), property_end(), cmp_properties);
844 	std::sort(child_begin(), child_end(), cmp_children);
845 	for (auto &c : child_nodes())
846 	{
847 		c->sort();
848 	}
849 }
850 
851 node_ptr
852 node::parse(input_buffer &input,
853             string name,
854             string label,
855             string address,
856             define_map *defines)
857 {
858 	node_ptr n(new node(input, name, label, address, defines));
859 	if (!n->valid)
860 	{
861 		n = 0;
862 	}
863 	return n;
864 }
865 
866 node_ptr
867 node::parse_dtb(input_buffer &structs, input_buffer &strings)
868 {
869 	node_ptr n(new node(structs, strings));
870 	if (!n->valid)
871 	{
872 		n = 0;
873 	}
874 	return n;
875 }
876 
877 property_ptr
878 node::get_property(string key)
879 {
880 	for (auto &i : props)
881 	{
882 		if (i->get_key() == key)
883 		{
884 			return i;
885 		}
886 	}
887 	return 0;
888 }
889 
890 void
891 node::merge_node(node_ptr other)
892 {
893 	if (!other->label.empty())
894 	{
895 		label = other->label;
896 	}
897 	// Note: this is an O(n*m) operation.  It might be sensible to
898 	// optimise this if we find that there are nodes with very
899 	// large numbers of properties, but for typical usage the
900 	// entire vector will fit (easily) into cache, so iterating
901 	// over it repeatedly isn't that expensive.
902 	for (auto &p : other->properties())
903 	{
904 		bool found = false;
905 		for (auto &mp : properties())
906 		{
907 			if (mp->get_key() == p->get_key())
908 			{
909 				mp = p;
910 				found = true;
911 				break;
912 			}
913 		}
914 		if (!found)
915 		{
916 			add_property(p);
917 		}
918 	}
919 	for (auto &c : other->children)
920 	{
921 		bool found = false;
922 		for (auto &i : children)
923 		{
924 			if (i->name == c->name && i->unit_address == c->unit_address)
925 			{
926 				i->merge_node(std::move(c));
927 				found = true;
928 				break;
929 			}
930 		}
931 		if (!found)
932 		{
933 			children.push_back(std::move(c));
934 		}
935 	}
936 }
937 
938 void
939 node::write(dtb::output_writer &writer, dtb::string_table &strings)
940 {
941 	writer.write_token(dtb::FDT_BEGIN_NODE);
942 	byte_buffer name_buffer;
943 	name.push_to_buffer(name_buffer);
944 	if (unit_address != string())
945 	{
946 		name_buffer.push_back('@');
947 		unit_address.push_to_buffer(name_buffer);
948 	}
949 	writer.write_comment(name);
950 	writer.write_data(name_buffer);
951 	writer.write_data((uint8_t)0);
952 	for (auto p : properties())
953 	{
954 		p->write(writer, strings);
955 	}
956 	for (auto &c : child_nodes())
957 	{
958 		c->write(writer, strings);
959 	}
960 	writer.write_token(dtb::FDT_END_NODE);
961 }
962 
963 void
964 node::write_dts(FILE *file, int indent)
965 {
966 	for (int i=0 ; i<indent ; i++)
967 	{
968 		putc('\t', file);
969 	}
970 #ifdef PRINT_LABELS
971 	if (label != string())
972 	{
973 		label.print(file);
974 		fputs(": ", file);
975 	}
976 #endif
977 	if (name != string())
978 	{
979 		name.print(file);
980 	}
981 	if (unit_address != string())
982 	{
983 		putc('@', file);
984 		unit_address.print(file);
985 	}
986 	fputs(" {\n\n", file);
987 	for (auto p : properties())
988 	{
989 		p->write_dts(file, indent+1);
990 	}
991 	for (auto &c : child_nodes())
992 	{
993 		c->write_dts(file, indent+1);
994 	}
995 	for (int i=0 ; i<indent ; i++)
996 	{
997 		putc('\t', file);
998 	}
999 	fputs("};\n", file);
1000 }
1001 
1002 void
1003 device_tree::collect_names_recursive(node_ptr &n, node_path &path)
1004 {
1005 	string name = n->label;
1006 	path.push_back(std::make_pair(n->name, n->unit_address));
1007 	if (name != string())
1008 	{
1009 		if (node_names.find(name) == node_names.end())
1010 		{
1011 			node_names.insert(std::make_pair(name, n.get()));
1012 			node_paths.insert(std::make_pair(name, path));
1013 		}
1014 		else
1015 		{
1016 			node_names[name] = (node*)-1;
1017 			auto i = node_paths.find(name);
1018 			if (i != node_paths.end())
1019 			{
1020 				node_paths.erase(name);
1021 			}
1022 			fprintf(stderr, "Label not unique: ");
1023 			name.dump();
1024 			fprintf(stderr, ".  References to this label will not be resolved.");
1025 		}
1026 	}
1027 	for (auto &c : n->child_nodes())
1028 	{
1029 		collect_names_recursive(c, path);
1030 	}
1031 	path.pop_back();
1032 	// Now we collect the phandles and properties that reference
1033 	// other nodes.
1034 	for (auto &p : n->properties())
1035 	{
1036 		for (auto &v : *p)
1037 		{
1038 			if (v.is_phandle())
1039 			{
1040 				phandles.push_back(&v);
1041 			}
1042 			if (v.is_cross_reference())
1043 			{
1044 				cross_references.push_back(&v);
1045 			}
1046 		}
1047 		if (p->get_key() == string("phandle") ||
1048 		    p->get_key() == string("linux,phandle"))
1049 		{
1050 			if (p->begin()->byte_data.size() != 4)
1051 			{
1052 				fprintf(stderr, "Invalid phandle value for node ");
1053 				n->name.dump();
1054 				fprintf(stderr, ".  Should be a 4-byte value.\n");
1055 				valid = false;
1056 			}
1057 			else
1058 			{
1059 				uint32_t phandle = p->begin()->get_as_uint32();
1060 				used_phandles.insert(std::make_pair(phandle, n.get()));
1061 			}
1062 		}
1063 	}
1064 }
1065 
1066 void
1067 device_tree::collect_names()
1068 {
1069 	node_path p;
1070 	node_names.clear();
1071 	node_paths.clear();
1072 	cross_references.clear();
1073 	phandles.clear();
1074 	collect_names_recursive(root, p);
1075 }
1076 
1077 void
1078 device_tree::resolve_cross_references()
1079 {
1080 	for (auto *pv : cross_references)
1081 	{
1082 		node_path path = node_paths[pv->string_data];
1083 		// Skip the first name in the path.  It's always "", and implicitly /
1084 		for (auto p=path.begin()+1, pe=path.end() ; p!=pe ; ++p)
1085 		{
1086 			pv->byte_data.push_back('/');
1087 			p->first.push_to_buffer(pv->byte_data);
1088 			if (!(p->second.empty()))
1089 			{
1090 				pv->byte_data.push_back('@');
1091 				p->second.push_to_buffer(pv->byte_data);
1092 				pv->byte_data.push_back(0);
1093 			}
1094 		}
1095 	}
1096 	std::unordered_set<property_value*> phandle_set;
1097 	for (auto &i : phandles)
1098 	{
1099 		phandle_set.insert(i);
1100 	}
1101 	std::vector<property_value*> sorted_phandles;
1102 	root->visit([&](node &n) {
1103 		for (auto &p : n.properties())
1104 		{
1105 			for (auto &v : *p)
1106 			{
1107 				if (phandle_set.count(&v))
1108 				{
1109 					sorted_phandles.push_back(&v);
1110 				}
1111 			}
1112 		}
1113 	});
1114 	assert(sorted_phandles.size() == phandles.size());
1115 
1116 	uint32_t phandle = 1;
1117 	for (auto &i : sorted_phandles)
1118 	{
1119 		string target_name = i->string_data;
1120 		node *target = node_names[target_name];
1121 		if (target == 0)
1122 		{
1123 			fprintf(stderr, "Failed to find node with label: ");
1124 			target_name.dump();
1125 			fprintf(stderr, "\n");
1126 			valid = 0;
1127 			return;
1128 		}
1129 		// If there is an existing phandle, use it
1130 		property_ptr p = target->get_property("phandle");
1131 		if (p == 0)
1132 		{
1133 			p = target->get_property("linux,phandle");
1134 		}
1135 		if (p == 0)
1136 		{
1137 			// Otherwise insert a new phandle node
1138 			property_value v;
1139 			while (used_phandles.find(phandle) != used_phandles.end())
1140 			{
1141 				// Note that we only don't need to
1142 				// store this phandle in the set,
1143 				// because we are monotonically
1144 				// increasing the value of phandle and
1145 				// so will only ever revisit this value
1146 				// if we have used 2^32 phandles, at
1147 				// which point our blob won't fit in
1148 				// any 32-bit system and we've done
1149 				// something badly wrong elsewhere
1150 				// already.
1151 				phandle++;
1152 			}
1153 			push_big_endian(v.byte_data, phandle++);
1154 			if (phandle_node_name == BOTH || phandle_node_name == LINUX)
1155 			{
1156 				p.reset(new property(string("linux,phandle")));
1157 				p->add_value(v);
1158 				target->add_property(p);
1159 			}
1160 			if (phandle_node_name == BOTH || phandle_node_name == EPAPR)
1161 			{
1162 				p.reset(new property(string("phandle")));
1163 				p->add_value(v);
1164 				target->add_property(p);
1165 			}
1166 		}
1167 		p->begin()->push_to_buffer(i->byte_data);
1168 		assert(i->byte_data.size() == 4);
1169 	}
1170 }
1171 
1172 bool
1173 device_tree::parse_include(input_buffer &input,
1174                         const std::string &dir,
1175                         std::vector<node_ptr> &roots,
1176                         FILE *depfile,
1177                         bool &read_header)
1178 {
1179 	if (!input.consume("/include/"))
1180 	{
1181 		return false;
1182 	}
1183 	bool reallyInclude = true;
1184 	if (input.consume("if "))
1185 	{
1186 		input.next_token();
1187 		string name = string::parse_property_name(input);
1188 		// XXX: Error handling
1189 		if (defines.find(name) == defines.end())
1190 		{
1191 			reallyInclude = false;
1192 		}
1193 		input.consume('/');
1194 	}
1195 	input.next_token();
1196 	if (!input.consume('"'))
1197 	{
1198 		input.parse_error("Expected quoted filename");
1199 		valid = false;
1200 		return false;
1201 	}
1202 	int length = 0;
1203 	while (input[length] != '"') length++;
1204 
1205 	std::string file((const char*)input, length);
1206 	std::string include_file = dir + '/' + file;
1207 	input.consume(file.c_str());
1208 	if (!reallyInclude)
1209 	{
1210 		input.consume('"');
1211 		input.next_token();
1212 		return true;
1213 	}
1214 
1215 	input_buffer *include_buffer = buffer_for_file(include_file.c_str(), false);
1216 
1217 	if (include_buffer == 0)
1218 	{
1219 		for (auto i : include_paths)
1220 		{
1221 			include_file = i + '/' + file;
1222 			include_buffer = buffer_for_file(include_file.c_str());
1223 			if (include_buffer != 0)
1224 			{
1225 				break;
1226 			}
1227 		}
1228 	}
1229 	if (depfile != 0)
1230 	{
1231 		putc(' ', depfile);
1232 		fputs(include_file.c_str(), depfile);
1233 	}
1234 	if (include_buffer == 0)
1235 	{
1236 		input.parse_error("Unable to locate input file");
1237 		input.consume('"');
1238 		input.next_token();
1239 		valid = false;
1240 		return true;
1241 	}
1242 	input.consume('"');
1243 	input.next_token();
1244 	parse_file(*include_buffer, dir, roots, depfile, read_header);
1245 	return true;
1246 }
1247 
1248 void
1249 device_tree::parse_file(input_buffer &input,
1250                         const std::string &dir,
1251                         std::vector<node_ptr> &roots,
1252                         FILE *depfile,
1253                         bool &read_header)
1254 {
1255 	input.next_token();
1256 	// Read the header
1257 	if (input.consume("/dts-v1/;"))
1258 	{
1259 		read_header = true;
1260 	}
1261 	input.next_token();
1262 	input.next_token();
1263 	if (!read_header)
1264 	{
1265 		input.parse_error("Expected /dts-v1/; version string");
1266 	}
1267 	while(parse_include(input, dir, roots, depfile, read_header)) {}
1268 	// Read any memory reservations
1269 	while(input.consume("/memreserve/"))
1270 	{
1271 		unsigned long long start, len;
1272 		input.next_token();
1273 		// Read the start and length.
1274 		if (!(input.consume_integer_expression(start) &&
1275 		    (input.next_token(),
1276 		    input.consume_integer_expression(len))))
1277 		{
1278 			input.parse_error("Expected size on /memreserve/ node.");
1279 		}
1280 		input.next_token();
1281 		input.consume(';');
1282 		reservations.push_back(reservation(start, len));
1283 	}
1284 	input.next_token();
1285 	while(parse_include(input, dir, roots, depfile, read_header)) {}
1286 	while (valid && !input.finished())
1287 	{
1288 		node_ptr n;
1289 		if (input.consume('/'))
1290 		{
1291 			input.next_token();
1292 			n = node::parse(input, string(), string(), string(), &defines);
1293 		}
1294 		else if (input.consume('&'))
1295 		{
1296 			input.next_token();
1297 			string name = string::parse_node_name(input);
1298 			input.next_token();
1299 			n = node::parse(input, name, string(), string(), &defines);
1300 		}
1301 		else
1302 		{
1303 			input.parse_error("Failed to find root node /.");
1304 		}
1305 		if (n)
1306 		{
1307 			roots.push_back(std::move(n));
1308 		}
1309 		else
1310 		{
1311 			valid = false;
1312 		}
1313 		input.next_token();
1314 		while(parse_include(input, dir, roots, depfile, read_header)) {}
1315 	}
1316 }
1317 
1318 input_buffer*
1319 device_tree::buffer_for_file(const char *path, bool warn)
1320 {
1321 	if (string(path) == string("-"))
1322 	{
1323 		input_buffer *b = new stream_input_buffer();
1324 		if (b)
1325 		{
1326 			std::unique_ptr<input_buffer> ptr(b);
1327 			buffers.push_back(std::move(ptr));
1328 		}
1329 		return b;
1330 	}
1331 	int source = open(path, O_RDONLY);
1332 	if (source == -1)
1333 	{
1334 		if (warn)
1335 		{
1336 			fprintf(stderr, "Unable to open file '%s'.  %s\n", path, strerror(errno));
1337 		}
1338 		return 0;
1339 	}
1340 	struct stat st;
1341 	if (fstat(source, &st) == 0 && S_ISDIR(st.st_mode))
1342 	{
1343 		fprintf(stderr, "File %s is a directory\n", path);
1344 		close(source);
1345 		return 0;
1346 	}
1347 	input_buffer *b = new mmap_input_buffer(source);
1348 	// Keep the buffer that owns the memory around for the lifetime
1349 	// of this FDT.  Ones simply referring to it may have shorter
1350 	// lifetimes.
1351 	if (b)
1352 	{
1353 		std::unique_ptr<input_buffer> ptr(b);
1354 		buffers.push_back(std::move(ptr));
1355 	}
1356 	close(source);
1357 	return b;
1358 }
1359 
1360 template<class writer> void
1361 device_tree::write(int fd)
1362 {
1363 	dtb::string_table st;
1364 	dtb::header head;
1365 	writer head_writer;
1366 	writer reservation_writer;
1367 	writer struct_writer;
1368 	writer strings_writer;
1369 
1370 	// Build the reservation table
1371 	reservation_writer.write_comment(string("Memory reservations"));
1372 	reservation_writer.write_label(string("dt_reserve_map"));
1373 	for (auto &i : reservations)
1374 	{
1375 		reservation_writer.write_comment(string("Reservation start"));
1376 		reservation_writer.write_data(i.first);
1377 		reservation_writer.write_comment(string("Reservation length"));
1378 		reservation_writer.write_data(i.first);
1379 	}
1380 	// Write n spare reserve map entries, plus the trailing 0.
1381 	for (uint32_t i=0 ; i<=spare_reserve_map_entries ; i++)
1382 	{
1383 		reservation_writer.write_data((uint64_t)0);
1384 		reservation_writer.write_data((uint64_t)0);
1385 	}
1386 
1387 
1388 	struct_writer.write_comment(string("Device tree"));
1389 	struct_writer.write_label(string("dt_struct_start"));
1390 	root->write(struct_writer, st);
1391 	struct_writer.write_token(dtb::FDT_END);
1392 	struct_writer.write_label(string("dt_struct_end"));
1393 
1394 	st.write(strings_writer);
1395 	// Find the strings size before we stick padding on the end.
1396 	// Note: We should possibly use a new writer for the padding.
1397 	head.size_dt_strings = strings_writer.size();
1398 
1399 	// Stick the padding in the strings writer, but after the
1400 	// marker indicating that it's the end.
1401 	// Note: We probably should add a padding call to the writer so
1402 	// that the asm back end can write padding directives instead
1403 	// of a load of 0 bytes.
1404 	for (uint32_t i=0 ; i<blob_padding ; i++)
1405 	{
1406 		strings_writer.write_data((uint8_t)0);
1407 	}
1408 	head.totalsize = sizeof(head) + strings_writer.size() +
1409 		struct_writer.size() + reservation_writer.size();
1410 	while (head.totalsize < minimum_blob_size)
1411 	{
1412 		head.totalsize++;
1413 		strings_writer.write_data((uint8_t)0);
1414 	}
1415 	head.off_dt_struct = sizeof(head) + reservation_writer.size();;
1416 	head.off_dt_strings = head.off_dt_struct + struct_writer.size();
1417 	head.off_mem_rsvmap = sizeof(head);
1418 	head.boot_cpuid_phys = boot_cpu;
1419 	head.size_dt_struct = struct_writer.size();
1420 	head.write(head_writer);
1421 
1422 	head_writer.write_to_file(fd);
1423 	reservation_writer.write_to_file(fd);
1424 	struct_writer.write_to_file(fd);
1425 	strings_writer.write_label(string("dt_blob_end"));
1426 	strings_writer.write_to_file(fd);
1427 }
1428 
1429 node*
1430 device_tree::referenced_node(property_value &v)
1431 {
1432 	if (v.is_phandle())
1433 	{
1434 		return node_names[v.string_data];
1435 	}
1436 	if (v.is_binary())
1437 	{
1438 		return used_phandles[v.get_as_uint32()];
1439 	}
1440 	return 0;
1441 }
1442 
1443 void
1444 device_tree::write_binary(int fd)
1445 {
1446 	write<dtb::binary_writer>(fd);
1447 }
1448 
1449 void
1450 device_tree::write_asm(int fd)
1451 {
1452 	write<dtb::asm_writer>(fd);
1453 }
1454 
1455 void
1456 device_tree::write_dts(int fd)
1457 {
1458 	FILE *file = fdopen(fd, "w");
1459 	fputs("/dts-v1/;\n\n", file);
1460 
1461 	if (!reservations.empty())
1462 	{
1463 		const char msg[] = "/memreserve/";
1464 		fwrite(msg, sizeof(msg), 1, file);
1465 		for (auto &i : reservations)
1466 		{
1467 			fprintf(file, " %" PRIx64 " %" PRIx64, i.first, i.second);
1468 		}
1469 		fputs(";\n\n", file);
1470 	}
1471 	putc('/', file);
1472 	putc(' ', file);
1473 	root->write_dts(file, 0);
1474 	fclose(file);
1475 }
1476 
1477 void
1478 device_tree::parse_dtb(const char *fn, FILE *)
1479 {
1480 	input_buffer *in = buffer_for_file(fn);
1481 	if (in == 0)
1482 	{
1483 		valid = false;
1484 		return;
1485 	}
1486 	input_buffer &input = *in;
1487 	dtb::header h;
1488 	valid = h.read_dtb(input);
1489 	boot_cpu = h.boot_cpuid_phys;
1490 	if (h.last_comp_version > 17)
1491 	{
1492 		fprintf(stderr, "Don't know how to read this version of the device tree blob");
1493 		valid = false;
1494 	}
1495 	if (!valid)
1496 	{
1497 		return;
1498 	}
1499 	input_buffer reservation_map =
1500 		input.buffer_from_offset(h.off_mem_rsvmap, 0);
1501 	uint64_t start, length;
1502 	do
1503 	{
1504 		if (!(reservation_map.consume_binary(start) &&
1505 		      reservation_map.consume_binary(length)))
1506 		{
1507 			fprintf(stderr, "Failed to read memory reservation table\n");
1508 			valid = false;
1509 			return;
1510 		}
1511 	} while (!((start == 0) && (length == 0)));
1512 	input_buffer struct_table =
1513 		input.buffer_from_offset(h.off_dt_struct, h.size_dt_struct);
1514 	input_buffer strings_table =
1515 		input.buffer_from_offset(h.off_dt_strings, h.size_dt_strings);
1516 	uint32_t token;
1517 	if (!(struct_table.consume_binary(token) &&
1518 		(token == dtb::FDT_BEGIN_NODE)))
1519 	{
1520 		fprintf(stderr, "Expected FDT_BEGIN_NODE token.\n");
1521 		valid = false;
1522 		return;
1523 	}
1524 	root = node::parse_dtb(struct_table, strings_table);
1525 	if (!(struct_table.consume_binary(token) && (token == dtb::FDT_END)))
1526 	{
1527 		fprintf(stderr, "Expected FDT_END token after parsing root node.\n");
1528 		valid = false;
1529 		return;
1530 	}
1531 	valid = (root != 0);
1532 }
1533 
1534 void
1535 device_tree::parse_dts(const char *fn, FILE *depfile)
1536 {
1537 	input_buffer *in = buffer_for_file(fn);
1538 	std::string dir(dirname((char*)fn));
1539 	if (in == 0)
1540 	{
1541 		valid = false;
1542 		return;
1543 	}
1544 	std::vector<node_ptr> roots;
1545 	input_buffer &input = *in;
1546 	bool read_header = false;
1547 	parse_file(input, dir, roots, depfile, read_header);
1548 	switch (roots.size())
1549 	{
1550 		case 0:
1551 			valid = false;
1552 			input.parse_error("Failed to find root node /.");
1553 			return;
1554 		case 1:
1555 			root = std::move(roots[0]);
1556 			break;
1557 		default:
1558 		{
1559 			root = std::move(roots[0]);
1560 			for (auto i=++(roots.begin()), e=roots.end() ; i!=e ; ++i)
1561 			{
1562 				auto &node = *i;
1563 				string name = node->name;
1564 				if (name == string())
1565 				{
1566 					root->merge_node(std::move(node));
1567 				}
1568 				else
1569 				{
1570 					auto existing = node_names.find(name);
1571 					if (existing == node_names.end())
1572 					{
1573 						collect_names();
1574 						existing = node_names.find(name);
1575 					}
1576 					if (existing == node_names.end())
1577 					{
1578 						fprintf(stderr, "Unable to merge node: ");
1579 						name.dump();
1580 						fprintf(stderr, "\n");
1581 					}
1582 					existing->second->merge_node(std::move(node));
1583 				}
1584 			}
1585 		}
1586 	}
1587 	collect_names();
1588 	resolve_cross_references();
1589 }
1590 
1591 bool device_tree::parse_define(const char *def)
1592 {
1593 	char *val = strchr(def, '=');
1594 	if (!val)
1595 	{
1596 		if (strlen(def) != 0)
1597 		{
1598 			string name(def);
1599 			defines[name];
1600 			return true;
1601 		}
1602 		return false;
1603 	}
1604 	string name(def, val-def);
1605 	val++;
1606 	input_buffer in = input_buffer(val, strlen(val));
1607 	property_ptr p = property::parse(in, name, string(), false);
1608 	if (p)
1609 		defines[name] = p;
1610 	return (bool)p;
1611 }
1612 
1613 } // namespace fdt
1614 
1615 } // namespace dtc
1616 
1617