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