1/*-
2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
3 *
4 * Copyright (c) 2013 David Chisnall
5 * All rights reserved.
6 *
7 * This software was developed by SRI International and the University of
8 * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237)
9 * ("CTSRD"), as part of the DARPA CRASH research programme.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 *    notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 *    notice, this list of conditions and the following disclaimer in the
18 *    documentation and/or other materials provided with the distribution.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 *
32 * $FreeBSD: stable/11/usr.bin/dtc/fdt.cc 358205 2020-02-21 04:34:54Z kevans $
33 */
34
35#define __STDC_LIMIT_MACROS 1
36
37#include "fdt.hh"
38#include "dtb.hh"
39
40#include <algorithm>
41#include <sstream>
42
43#include <ctype.h>
44#include <fcntl.h>
45#include <inttypes.h>
46#include <libgen.h>
47#include <stdio.h>
48#include <stdlib.h>
49#include <string.h>
50#include <unistd.h>
51#include <sys/types.h>
52#include <sys/stat.h>
53#include <errno.h>
54
55using std::string;
56
57namespace dtc
58{
59
60namespace fdt
61{
62
63uint32_t
64property_value::get_as_uint32()
65{
66	if (byte_data.size() != 4)
67	{
68		return 0;
69	}
70	uint32_t v = 0;
71	v &= byte_data[0] << 24;
72	v &= byte_data[1] << 16;
73	v &= byte_data[2] << 8;
74	v &= byte_data[3] << 0;
75	return v;
76}
77
78void
79property_value::push_to_buffer(byte_buffer &buffer)
80{
81	if (!byte_data.empty())
82	{
83		buffer.insert(buffer.end(), byte_data.begin(), byte_data.end());
84	}
85	else
86	{
87		push_string(buffer, string_data, true);
88		// Trailing nul
89		buffer.push_back(0);
90	}
91}
92
93void
94property_value::write_dts(FILE *file)
95{
96	resolve_type();
97	switch (type)
98	{
99		default:
100			assert(0 && "Invalid type");
101		case STRING:
102		case STRING_LIST:
103		case CROSS_REFERENCE:
104			write_as_string(file);
105			break;
106		case PHANDLE:
107			write_as_cells(file);
108			break;
109		case BINARY:
110			if (byte_data.size() % 4 == 0)
111			{
112				write_as_cells(file);
113				break;
114			}
115			write_as_bytes(file);
116			break;
117	}
118}
119
120void
121property_value::resolve_type()
122{
123	if (type != UNKNOWN)
124	{
125		return;
126	}
127	if (byte_data.empty())
128	{
129		type = STRING;
130		return;
131	}
132	if (byte_data.back() == 0)
133	{
134		bool is_all_printable = true;
135		int nuls = 0;
136		int bytes = 0;
137		bool lastWasNull = false;
138		for (auto i : byte_data)
139		{
140			bytes++;
141			is_all_printable &= (i == '\0') || isprint(i);
142			if (i == '\0')
143			{
144				// If there are two nulls in a row, then we're probably binary.
145				if (lastWasNull)
146				{
147					type = BINARY;
148					return;
149				}
150				nuls++;
151				lastWasNull = true;
152			}
153			else
154			{
155				lastWasNull = false;
156			}
157			if (!is_all_printable)
158			{
159				break;
160			}
161		}
162		if ((is_all_printable && (bytes > nuls)) || bytes == 0)
163		{
164			type = STRING;
165			if (nuls > 1)
166			{
167				type = STRING_LIST;
168			}
169			return;
170		}
171	}
172	type = BINARY;
173}
174
175size_t
176property_value::size()
177{
178	if (!byte_data.empty())
179	{
180		return byte_data.size();
181	}
182	return string_data.size() + 1;
183}
184
185void
186property_value::write_as_string(FILE *file)
187{
188	putc('"', file);
189	if (byte_data.empty())
190	{
191		fputs(string_data.c_str(), file);
192	}
193	else
194	{
195		bool hasNull = (byte_data.back() == '\0');
196		// Remove trailing null bytes from the string before printing as dts.
197		if (hasNull)
198		{
199			byte_data.pop_back();
200		}
201		for (auto i : byte_data)
202		{
203			// FIXME Escape tabs, newlines, and so on.
204			if (i == '\0')
205			{
206				fputs("\", \"", file);
207				continue;
208			}
209			putc(i, file);
210		}
211		if (hasNull)
212		{
213			byte_data.push_back('\0');
214		}
215	}
216	putc('"', file);
217}
218
219void
220property_value::write_as_cells(FILE *file)
221{
222	putc('<', file);
223	assert((byte_data.size() % 4) == 0);
224	for (auto i=byte_data.begin(), e=byte_data.end(); i!=e ; ++i)
225	{
226		uint32_t v = 0;
227		v = (v << 8) | *i;
228		++i;
229		v = (v << 8) | *i;
230		++i;
231		v = (v << 8) | *i;
232		++i;
233		v = (v << 8) | *i;
234		fprintf(file, "0x%" PRIx32, v);
235		if (i+1 != e)
236		{
237			putc(' ', file);
238		}
239	}
240	putc('>', file);
241}
242
243void
244property_value::write_as_bytes(FILE *file)
245{
246	putc('[', file);
247	for (auto i=byte_data.begin(), e=byte_data.end(); i!=e ; i++)
248	{
249		fprintf(file, "%02hhx", *i);
250		if (i+1 != e)
251		{
252			putc(' ', file);
253		}
254	}
255	putc(']', file);
256}
257
258void
259property::parse_string(text_input_buffer &input)
260{
261	property_value v;
262	assert(*input == '"');
263	++input;
264	std::vector<char> bytes;
265	bool isEscaped = false;
266	while (char c = *input)
267	{
268		if (c == '"' && !isEscaped)
269		{
270			input.consume('"');
271			break;
272		}
273		isEscaped = (c == '\\');
274		bytes.push_back(c);
275		++input;
276	}
277	v.string_data = string(bytes.begin(), bytes.end());
278	values.push_back(v);
279}
280
281void
282property::parse_cells(text_input_buffer &input, int cell_size)
283{
284	assert(*input == '<');
285	++input;
286	property_value v;
287	input.next_token();
288	while (!input.consume('>'))
289	{
290		input.next_token();
291		// If this is a phandle then we need to get the name of the
292		// referenced node
293		if (input.consume('&'))
294		{
295			if (cell_size != 32)
296			{
297				input.parse_error("reference only permitted in 32-bit arrays");
298				valid = false;
299				return;
300			}
301			input.next_token();
302			string referenced;
303			if (!input.consume('{'))
304			{
305				referenced = input.parse_node_name();
306			}
307			else
308			{
309				referenced = input.parse_to('}');
310				input.consume('}');
311			}
312			if (referenced.empty())
313			{
314				input.parse_error("Expected node name");
315				valid = false;
316				return;
317			}
318			input.next_token();
319			// If we already have some bytes, make the phandle a
320			// separate component.
321			if (!v.byte_data.empty())
322			{
323				values.push_back(v);
324				v = property_value();
325			}
326			v.string_data = referenced;
327			v.type = property_value::PHANDLE;
328			values.push_back(v);
329			v = property_value();
330		}
331		else
332		{
333			//FIXME: We should support labels in the middle
334			//of these, but we don't.
335			unsigned long long val;
336			if (!input.consume_integer_expression(val))
337			{
338				input.parse_error("Expected numbers in array of cells");
339				valid = false;
340				return;
341			}
342			switch (cell_size)
343			{
344				case 8:
345					v.byte_data.push_back(val);
346					break;
347				case 16:
348					push_big_endian(v.byte_data, (uint16_t)val);
349					break;
350				case 32:
351					push_big_endian(v.byte_data, (uint32_t)val);
352					break;
353				case 64:
354					push_big_endian(v.byte_data, (uint64_t)val);
355					break;
356				default:
357					assert(0 && "Invalid cell size!");
358			}
359			input.next_token();
360		}
361	}
362	// Don't store an empty string value here.
363	if (v.byte_data.size() > 0)
364	{
365		values.push_back(v);
366	}
367}
368
369void
370property::parse_bytes(text_input_buffer &input)
371{
372	assert(*input == '[');
373	++input;
374	property_value v;
375	input.next_token();
376	while (!input.consume(']'))
377	{
378		{
379			//FIXME: We should support
380			//labels in the middle of
381			//these, but we don't.
382			uint8_t val;
383			if (!input.consume_hex_byte(val))
384			{
385				input.parse_error("Expected hex bytes in array of bytes");
386				valid = false;
387				return;
388			}
389			v.byte_data.push_back(val);
390			input.next_token();
391		}
392	}
393	values.push_back(v);
394}
395
396void
397property::parse_reference(text_input_buffer &input)
398{
399	assert(*input == '&');
400	++input;
401	input.next_token();
402	property_value v;
403	v.string_data = input.parse_node_name();
404	if (v.string_data.empty())
405	{
406		input.parse_error("Expected node name");
407		valid = false;
408		return;
409	}
410	v.type = property_value::CROSS_REFERENCE;
411	values.push_back(v);
412}
413
414property::property(input_buffer &structs, input_buffer &strings)
415{
416	uint32_t name_offset;
417	uint32_t length;
418	valid = structs.consume_binary(length) &&
419		structs.consume_binary(name_offset);
420	if (!valid)
421	{
422		fprintf(stderr, "Failed to read property\n");
423		return;
424	}
425	// Find the name
426	input_buffer name_buffer = strings.buffer_from_offset(name_offset);
427	if (name_buffer.finished())
428	{
429		fprintf(stderr, "Property name offset %" PRIu32
430			" is past the end of the strings table\n",
431			name_offset);
432		valid = false;
433		return;
434	}
435	key = name_buffer.parse_to(0);
436
437	// If we're empty, do not push anything as value.
438	if (!length)
439		return;
440
441	// Read the value
442	uint8_t byte;
443	property_value v;
444	for (uint32_t i=0 ; i<length ; i++)
445	{
446		if (!(valid = structs.consume_binary(byte)))
447		{
448			fprintf(stderr, "Failed to read property value\n");
449			return;
450		}
451		v.byte_data.push_back(byte);
452	}
453	values.push_back(v);
454}
455
456void property::parse_define(text_input_buffer &input, define_map *defines)
457{
458	input.consume('$');
459	if (!defines)
460	{
461		input.parse_error("No predefined properties to match name\n");
462		valid = false;
463		return;
464	}
465	string name = input.parse_property_name();
466	define_map::iterator found;
467	if ((name == string()) ||
468	    ((found = defines->find(name)) == defines->end()))
469	{
470		input.parse_error("Undefined property name\n");
471		valid = false;
472		return;
473	}
474	values.push_back((*found).second->values[0]);
475}
476
477property::property(text_input_buffer &input,
478                   string &&k,
479                   string_set &&l,
480                   bool semicolonTerminated,
481                   define_map *defines) : key(k), labels(l), valid(true)
482{
483	do {
484		input.next_token();
485		switch (*input)
486		{
487			case '$':
488			{
489				parse_define(input, defines);
490				if (valid)
491				{
492					break;
493				}
494			}
495			[[fallthrough]];
496			default:
497				input.parse_error("Invalid property value.");
498				valid = false;
499				return;
500			case '/':
501			{
502				if (input.consume("/incbin/(\""))
503				{
504					auto loc = input.location();
505					std::string filename = input.parse_to('"');
506					if (!(valid = input.consume('"')))
507					{
508						loc.report_error("Syntax error, expected '\"' to terminate /incbin/(");
509						return;
510					}
511					property_value v;
512					if (!(valid = input.read_binary_file(filename, v.byte_data)))
513					{
514						input.parse_error("Cannot open binary include file");
515						return;
516					}
517					if (!(valid &= input.consume(')')))
518					{
519						input.parse_error("Syntax error, expected ')' to terminate /incbin/(");
520						return;
521					}
522					values.push_back(v);
523					break;
524				}
525				unsigned long long bits = 0;
526				valid = input.consume("/bits/");
527				input.next_token();
528				valid &= input.consume_integer(bits);
529				if ((bits != 8) &&
530				    (bits != 16) &&
531				    (bits != 32) &&
532				    (bits != 64)) {
533					input.parse_error("Invalid size for elements");
534					valid = false;
535				}
536				if (!valid) return;
537				input.next_token();
538				if (*input != '<')
539				{
540					input.parse_error("/bits/ directive is only valid on arrays");
541					valid = false;
542					return;
543				}
544				parse_cells(input, bits);
545				break;
546			}
547			case '"':
548				parse_string(input);
549				break;
550			case '<':
551				parse_cells(input, 32);
552				break;
553			case '[':
554				parse_bytes(input);
555				break;
556			case '&':
557				parse_reference(input);
558				break;
559			case ';':
560			{
561				break;
562			}
563		}
564		input.next_token();
565	} while (input.consume(','));
566	if (semicolonTerminated && !input.consume(';'))
567	{
568		input.parse_error("Expected ; at end of property");
569		valid = false;
570	}
571}
572
573property_ptr
574property::parse_dtb(input_buffer &structs, input_buffer &strings)
575{
576	property_ptr p(new property(structs, strings));
577	if (!p->valid)
578	{
579		p = nullptr;
580	}
581	return p;
582}
583
584property_ptr
585property::parse(text_input_buffer &input, string &&key, string_set &&label,
586                bool semicolonTerminated, define_map *defines)
587{
588	property_ptr p(new property(input,
589	                            std::move(key),
590	                            std::move(label),
591	                            semicolonTerminated,
592	                            defines));
593	if (!p->valid)
594	{
595		p = nullptr;
596	}
597	return p;
598}
599
600void
601property::write(dtb::output_writer &writer, dtb::string_table &strings)
602{
603	writer.write_token(dtb::FDT_PROP);
604	byte_buffer value_buffer;
605	for (value_iterator i=begin(), e=end() ; i!=e ; ++i)
606	{
607		i->push_to_buffer(value_buffer);
608	}
609	writer.write_data((uint32_t)value_buffer.size());
610	writer.write_comment(key);
611	writer.write_data(strings.add_string(key));
612	writer.write_data(value_buffer);
613}
614
615bool
616property_value::try_to_merge(property_value &other)
617{
618	resolve_type();
619	switch (type)
620	{
621		case UNKNOWN:
622			__builtin_unreachable();
623			assert(0);
624			return false;
625		case EMPTY:
626			*this = other;
627			[[fallthrough]];
628		case STRING:
629		case STRING_LIST:
630		case CROSS_REFERENCE:
631			return false;
632		case PHANDLE:
633		case BINARY:
634			if (other.type == PHANDLE || other.type == BINARY)
635			{
636				type = BINARY;
637				byte_data.insert(byte_data.end(), other.byte_data.begin(),
638				                 other.byte_data.end());
639				return true;
640			}
641	}
642	return false;
643}
644
645void
646property::write_dts(FILE *file, int indent)
647{
648	for (int i=0 ; i<indent ; i++)
649	{
650		putc('\t', file);
651	}
652#ifdef PRINT_LABELS
653	for (auto &l : labels)
654	{
655		fputs(l.c_str(), file);
656		fputs(": ", file);
657	}
658#endif
659	if (key != string())
660	{
661		fputs(key.c_str(), file);
662	}
663	if (!values.empty())
664	{
665		std::vector<property_value> *vals = &values;
666		std::vector<property_value> v;
667		// If we've got multiple values then try to merge them all together.
668		if (values.size() > 1)
669		{
670			vals = &v;
671			v.push_back(values.front());
672			for (auto i=(++begin()), e=end() ; i!=e ; ++i)
673			{
674				if (!v.back().try_to_merge(*i))
675				{
676					v.push_back(*i);
677				}
678			}
679		}
680		fputs(" = ", file);
681		for (auto i=vals->begin(), e=vals->end() ; i!=e ; ++i)
682		{
683			i->write_dts(file);
684			if (i+1 != e)
685			{
686				putc(',', file);
687				putc(' ', file);
688			}
689		}
690	}
691	fputs(";\n", file);
692}
693
694size_t
695property::offset_of_value(property_value &val)
696{
697	size_t off = 0;
698	for (auto &v : values)
699	{
700		if (&v == &val)
701		{
702			return off;
703		}
704		off += v.size();
705	}
706	return -1;
707}
708
709string
710node::parse_name(text_input_buffer &input, bool &is_property, const char *error)
711{
712	if (!valid)
713	{
714		return string();
715	}
716	input.next_token();
717	if (is_property)
718	{
719		return input.parse_property_name();
720	}
721	string n = input.parse_node_or_property_name(is_property);
722	if (n.empty())
723	{
724		if (n.empty())
725		{
726			input.parse_error(error);
727			valid = false;
728		}
729	}
730	return n;
731}
732
733node::visit_behavior
734node::visit(std::function<visit_behavior(node&, node*)> fn, node *parent)
735{
736	visit_behavior behavior;
737	behavior = fn(*this, parent);
738	if (behavior == VISIT_BREAK)
739	{
740		return VISIT_BREAK;
741	}
742	else if (behavior != VISIT_CONTINUE)
743	{
744		for (auto &&c : children)
745		{
746			behavior = c->visit(fn, this);
747			// Any status other than VISIT_RECURSE stops our execution and
748			// bubbles up to our caller.  The caller may then either continue
749			// visiting nodes that are siblings to this one or completely halt
750			// visiting.
751			if (behavior != VISIT_RECURSE)
752			{
753				return behavior;
754			}
755		}
756	}
757	// Continue recursion by default
758	return VISIT_RECURSE;
759}
760
761node::node(input_buffer &structs, input_buffer &strings) : valid(true)
762{
763	std::vector<char> bytes;
764	while (structs[0] != '\0' && structs[0] != '@')
765	{
766		bytes.push_back(structs[0]);
767		++structs;
768	}
769	name = string(bytes.begin(), bytes.end());
770	bytes.clear();
771	if (structs[0] == '@')
772	{
773		++structs;
774		while (structs[0] != '\0')
775		{
776			bytes.push_back(structs[0]);
777			++structs;
778		}
779		unit_address = string(bytes.begin(), bytes.end());
780	}
781	++structs;
782	uint32_t token;
783	while (structs.consume_binary(token))
784	{
785		switch (token)
786		{
787			default:
788				fprintf(stderr, "Unexpected token 0x%" PRIx32
789					" while parsing node.\n", token);
790				valid = false;
791				return;
792			// Child node, parse it.
793			case dtb::FDT_BEGIN_NODE:
794			{
795				node_ptr child = node::parse_dtb(structs, strings);
796				if (child == 0)
797				{
798					valid = false;
799					return;
800				}
801				children.push_back(std::move(child));
802				break;
803			}
804			// End of this node, no errors.
805			case dtb::FDT_END_NODE:
806				return;
807			// Property, parse it.
808			case dtb::FDT_PROP:
809			{
810				property_ptr prop = property::parse_dtb(structs, strings);
811				if (prop == 0)
812				{
813					valid = false;
814					return;
815				}
816				props.push_back(prop);
817				break;
818			}
819				break;
820			// End of structs table.  Should appear after
821			// the end of the last node.
822			case dtb::FDT_END:
823				fprintf(stderr, "Unexpected FDT_END token while parsing node.\n");
824				valid = false;
825				return;
826			// NOPs are padding.  Ignore them.
827			case dtb::FDT_NOP:
828				break;
829		}
830	}
831	fprintf(stderr, "Failed to read token from structs table while parsing node.\n");
832	valid = false;
833	return;
834}
835
836
837node::node(const string &n,
838           const std::vector<property_ptr> &p)
839	: name(n)
840{
841	props.insert(props.begin(), p.begin(), p.end());
842}
843
844node_ptr node::create_special_node(const string &name,
845                                   const std::vector<property_ptr> &props)
846{
847	node_ptr n(new node(name, props));
848	return n;
849}
850
851node::node(text_input_buffer &input,
852           device_tree &tree,
853           string &&n,
854           std::unordered_set<string> &&l,
855           string &&a,
856           define_map *defines)
857	: labels(l), name(n), unit_address(a), valid(true)
858{
859	if (!input.consume('{'))
860	{
861		input.parse_error("Expected { to start new device tree node.\n");
862	}
863	input.next_token();
864	while (valid && !input.consume('}'))
865	{
866		// flag set if we find any characters that are only in
867		// the property name character set, not the node
868		bool is_property = false;
869		// flag set if our node is marked as /omit-if-no-ref/ to be
870		// garbage collected later if nothing references it
871		bool marked_omit_if_no_ref = false;
872		string child_name, child_address;
873		std::unordered_set<string> child_labels;
874		auto parse_delete = [&](const char *expected, bool at)
875		{
876			if (child_name == string())
877			{
878				input.parse_error(expected);
879				valid = false;
880				return;
881			}
882			input.next_token();
883			if (at && input.consume('@'))
884			{
885				child_name += '@';
886				child_name += parse_name(input, is_property, "Expected unit address");
887			}
888			if (!input.consume(';'))
889			{
890				input.parse_error("Expected semicolon");
891				valid = false;
892				return;
893			}
894			input.next_token();
895		};
896		if (input.consume("/delete-node/"))
897		{
898			input.next_token();
899			child_name = input.parse_node_name();
900			parse_delete("Expected node name", true);
901			if (valid)
902			{
903				deleted_children.insert(child_name);
904			}
905			continue;
906		}
907		if (input.consume("/delete-property/"))
908		{
909			input.next_token();
910			child_name = input.parse_property_name();
911			parse_delete("Expected property name", false);
912			if (valid)
913			{
914				deleted_props.insert(child_name);
915			}
916			continue;
917		}
918		if (input.consume("/omit-if-no-ref/"))
919		{
920			input.next_token();
921			marked_omit_if_no_ref = true;
922			tree.set_needs_garbage_collection();
923		}
924		child_name = parse_name(input, is_property,
925				"Expected property or node name");
926		while (input.consume(':'))
927		{
928			// Node labels can contain any characters?  The
929			// spec doesn't say, so we guess so...
930			is_property = false;
931			child_labels.insert(std::move(child_name));
932			child_name = parse_name(input, is_property, "Expected property or node name");
933		}
934		if (input.consume('@'))
935		{
936			child_address = parse_name(input, is_property, "Expected unit address");
937		}
938		if (!valid)
939		{
940			return;
941		}
942		input.next_token();
943		// If we're parsing a property, then we must actually do that.
944		if (input.consume('='))
945		{
946			property_ptr p = property::parse(input, std::move(child_name),
947					std::move(child_labels), true, defines);
948			if (p == 0)
949			{
950				valid = false;
951			}
952			else
953			{
954				props.push_back(p);
955			}
956		}
957		else if (!is_property && *input == ('{'))
958		{
959			node_ptr child = node::parse(input, tree, std::move(child_name),
960					std::move(child_labels), std::move(child_address), defines);
961			if (child)
962			{
963				child->omit_if_no_ref = marked_omit_if_no_ref;
964				children.push_back(std::move(child));
965			}
966			else
967			{
968				valid = false;
969			}
970		}
971		else if (input.consume(';'))
972		{
973			props.push_back(property_ptr(new property(std::move(child_name), std::move(child_labels))));
974		}
975		else
976		{
977			input.parse_error("Error parsing property.  Expected property value");
978			valid = false;
979		}
980		input.next_token();
981	}
982	input.next_token();
983	input.consume(';');
984}
985
986bool
987node::cmp_properties(property_ptr &p1, property_ptr &p2)
988{
989	return p1->get_key() < p2->get_key();
990}
991
992bool
993node::cmp_children(node_ptr &c1, node_ptr &c2)
994{
995	if (c1->name == c2->name)
996	{
997		return c1->unit_address < c2->unit_address;
998	}
999	return c1->name < c2->name;
1000}
1001
1002void
1003node::sort()
1004{
1005	std::sort(property_begin(), property_end(), cmp_properties);
1006	std::sort(child_begin(), child_end(), cmp_children);
1007	for (auto &c : child_nodes())
1008	{
1009		c->sort();
1010	}
1011}
1012
1013node_ptr
1014node::parse(text_input_buffer &input,
1015            device_tree &tree,
1016            string &&name,
1017            string_set &&label,
1018            string &&address,
1019            define_map *defines)
1020{
1021	node_ptr n(new node(input,
1022	                    tree,
1023	                    std::move(name),
1024	                    std::move(label),
1025	                    std::move(address),
1026	                    defines));
1027	if (!n->valid)
1028	{
1029		n = 0;
1030	}
1031	return n;
1032}
1033
1034node_ptr
1035node::parse_dtb(input_buffer &structs, input_buffer &strings)
1036{
1037	node_ptr n(new node(structs, strings));
1038	if (!n->valid)
1039	{
1040		n = 0;
1041	}
1042	return n;
1043}
1044
1045property_ptr
1046node::get_property(const string &key)
1047{
1048	for (auto &i : props)
1049	{
1050		if (i->get_key() == key)
1051		{
1052			return i;
1053		}
1054	}
1055	return 0;
1056}
1057
1058void
1059node::merge_node(node_ptr &other)
1060{
1061	for (auto &l : other->labels)
1062	{
1063		labels.insert(l);
1064	}
1065	children.erase(std::remove_if(children.begin(), children.end(),
1066			[&](const node_ptr &p) {
1067				string full_name = p->name;
1068				if (p->unit_address != string())
1069				{
1070					full_name += '@';
1071					full_name += p->unit_address;
1072				}
1073				if (other->deleted_children.count(full_name) > 0)
1074				{
1075					other->deleted_children.erase(full_name);
1076					return true;
1077				}
1078				return false;
1079			}), children.end());
1080	props.erase(std::remove_if(props.begin(), props.end(),
1081			[&](const property_ptr &p) {
1082				if (other->deleted_props.count(p->get_key()) > 0)
1083				{
1084					other->deleted_props.erase(p->get_key());
1085					return true;
1086				}
1087				return false;
1088			}), props.end());
1089	// Note: this is an O(n*m) operation.  It might be sensible to
1090	// optimise this if we find that there are nodes with very
1091	// large numbers of properties, but for typical usage the
1092	// entire vector will fit (easily) into cache, so iterating
1093	// over it repeatedly isn't that expensive.
1094	for (auto &p : other->properties())
1095	{
1096		bool found = false;
1097		for (auto &mp : properties())
1098		{
1099			if (mp->get_key() == p->get_key())
1100			{
1101				mp = p;
1102				found = true;
1103				break;
1104			}
1105		}
1106		if (!found)
1107		{
1108			add_property(p);
1109		}
1110	}
1111	for (auto &c : other->children)
1112	{
1113		bool found = false;
1114		for (auto &i : children)
1115		{
1116			if (i->name == c->name && i->unit_address == c->unit_address)
1117			{
1118				i->merge_node(c);
1119				found = true;
1120				break;
1121			}
1122		}
1123		if (!found)
1124		{
1125			children.push_back(std::move(c));
1126		}
1127	}
1128}
1129
1130void
1131node::write(dtb::output_writer &writer, dtb::string_table &strings)
1132{
1133	writer.write_token(dtb::FDT_BEGIN_NODE);
1134	byte_buffer name_buffer;
1135	push_string(name_buffer, name);
1136	if (unit_address != string())
1137	{
1138		name_buffer.push_back('@');
1139		push_string(name_buffer, unit_address);
1140	}
1141	writer.write_comment(name);
1142	writer.write_data(name_buffer);
1143	writer.write_data((uint8_t)0);
1144	for (auto p : properties())
1145	{
1146		p->write(writer, strings);
1147	}
1148	for (auto &c : child_nodes())
1149	{
1150		c->write(writer, strings);
1151	}
1152	writer.write_token(dtb::FDT_END_NODE);
1153}
1154
1155void
1156node::write_dts(FILE *file, int indent)
1157{
1158	for (int i=0 ; i<indent ; i++)
1159	{
1160		putc('\t', file);
1161	}
1162#ifdef PRINT_LABELS
1163	for (auto &label : labels)
1164	{
1165		fprintf(file, "%s: ", label.c_str());
1166	}
1167#endif
1168	if (name != string())
1169	{
1170		fputs(name.c_str(), file);
1171	}
1172	if (unit_address != string())
1173	{
1174		putc('@', file);
1175		fputs(unit_address.c_str(), file);
1176	}
1177	fputs(" {\n\n", file);
1178	for (auto p : properties())
1179	{
1180		p->write_dts(file, indent+1);
1181	}
1182	for (auto &c : child_nodes())
1183	{
1184		c->write_dts(file, indent+1);
1185	}
1186	for (int i=0 ; i<indent ; i++)
1187	{
1188		putc('\t', file);
1189	}
1190	fputs("};\n", file);
1191}
1192
1193void
1194device_tree::collect_names_recursive(node_ptr &n, node_path &path)
1195{
1196	path.push_back(std::make_pair(n->name, n->unit_address));
1197	for (const string &name : n->labels)
1198	{
1199		if (name != string())
1200		{
1201			auto iter = node_names.find(name);
1202			if (iter == node_names.end())
1203			{
1204				node_names.insert(std::make_pair(name, n.get()));
1205				node_paths.insert(std::make_pair(name, path));
1206				ordered_node_paths.push_back({name, path});
1207			}
1208			else
1209			{
1210				node_names.erase(iter);
1211				auto i = node_paths.find(name);
1212				if (i != node_paths.end())
1213				{
1214					node_paths.erase(name);
1215				}
1216				fprintf(stderr, "Label not unique: %s.  References to this label will not be resolved.\n", name.c_str());
1217			}
1218		}
1219	}
1220	for (auto &c : n->child_nodes())
1221	{
1222		collect_names_recursive(c, path);
1223	}
1224	// Now we collect the phandles and properties that reference
1225	// other nodes.
1226	for (auto &p : n->properties())
1227	{
1228		for (auto &v : *p)
1229		{
1230			if (v.is_phandle())
1231			{
1232				fixups.push_back({path, p, v});
1233			}
1234			if (v.is_cross_reference())
1235			{
1236				cross_references.push_back(&v);
1237			}
1238		}
1239		if ((p->get_key() == "phandle") ||
1240		    (p->get_key() == "linux,phandle"))
1241		{
1242			if (p->begin()->byte_data.size() != 4)
1243			{
1244				fprintf(stderr, "Invalid phandle value for node %s.  Should be a 4-byte value.\n", n->name.c_str());
1245				valid = false;
1246			}
1247			else
1248			{
1249				uint32_t phandle = p->begin()->get_as_uint32();
1250				used_phandles.insert(std::make_pair(phandle, n.get()));
1251			}
1252		}
1253	}
1254	path.pop_back();
1255}
1256
1257void
1258device_tree::collect_names()
1259{
1260	node_path p;
1261	node_names.clear();
1262	node_paths.clear();
1263	ordered_node_paths.clear();
1264	cross_references.clear();
1265	fixups.clear();
1266	collect_names_recursive(root, p);
1267}
1268
1269property_ptr
1270device_tree::assign_phandle(node *n, uint32_t &phandle)
1271{
1272	// If there is an existing phandle, use it
1273	property_ptr p = n->get_property("phandle");
1274	if (p == 0)
1275	{
1276		p = n->get_property("linux,phandle");
1277	}
1278	if (p == 0)
1279	{
1280		// Otherwise insert a new phandle node
1281		property_value v;
1282		while (used_phandles.find(phandle) != used_phandles.end())
1283		{
1284			// Note that we only don't need to
1285			// store this phandle in the set,
1286			// because we are monotonically
1287			// increasing the value of phandle and
1288			// so will only ever revisit this value
1289			// if we have used 2^32 phandles, at
1290			// which point our blob won't fit in
1291			// any 32-bit system and we've done
1292			// something badly wrong elsewhere
1293			// already.
1294			phandle++;
1295		}
1296		push_big_endian(v.byte_data, phandle++);
1297		if (phandle_node_name == BOTH || phandle_node_name == LINUX)
1298		{
1299			p.reset(new property("linux,phandle"));
1300			p->add_value(v);
1301			n->add_property(p);
1302		}
1303		if (phandle_node_name == BOTH || phandle_node_name == EPAPR)
1304		{
1305			p.reset(new property("phandle"));
1306			p->add_value(v);
1307			n->add_property(p);
1308		}
1309	}
1310
1311	return (p);
1312}
1313
1314void
1315device_tree::assign_phandles(node_ptr &n, uint32_t &next)
1316{
1317	if (!n->labels.empty())
1318	{
1319		assign_phandle(n.get(), next);
1320	}
1321
1322	for (auto &c : n->child_nodes())
1323	{
1324		assign_phandles(c, next);
1325	}
1326}
1327
1328void
1329device_tree::resolve_cross_references(uint32_t &phandle)
1330{
1331	for (auto *pv : cross_references)
1332	{
1333		node_path path = node_paths[pv->string_data];
1334		auto p = path.begin();
1335		auto pe = path.end();
1336		if (p != pe)
1337		{
1338			// Skip the first name in the path.  It's always "", and implicitly /
1339			for (++p ; p!=pe ; ++p)
1340			{
1341				pv->byte_data.push_back('/');
1342				push_string(pv->byte_data, p->first);
1343				if (!(p->second.empty()))
1344				{
1345					pv->byte_data.push_back('@');
1346					push_string(pv->byte_data, p->second);
1347				}
1348			}
1349			pv->byte_data.push_back(0);
1350		}
1351	}
1352	std::unordered_map<property_value*, fixup&> phandle_set;
1353	for (auto &i : fixups)
1354	{
1355		phandle_set.insert({&i.val, i});
1356	}
1357	std::vector<std::reference_wrapper<fixup>> sorted_phandles;
1358	root->visit([&](node &n, node *) {
1359		for (auto &p : n.properties())
1360		{
1361			for (auto &v : *p)
1362			{
1363				auto i = phandle_set.find(&v);
1364				if (i != phandle_set.end())
1365				{
1366					sorted_phandles.push_back(i->second);
1367				}
1368			}
1369		}
1370		// Allow recursion
1371		return node::VISIT_RECURSE;
1372	}, nullptr);
1373	assert(sorted_phandles.size() == fixups.size());
1374	for (auto &i : sorted_phandles)
1375	{
1376		string target_name = i.get().val.string_data;
1377		node *target = nullptr;
1378		string possible;
1379		// If the node name is a path, then look it up by following the path,
1380		// otherwise jump directly to the named node.
1381		if (target_name[0] == '/')
1382		{
1383			string path;
1384			target = root.get();
1385			std::istringstream ss(target_name);
1386			string path_element;
1387			// Read the leading /
1388			std::getline(ss, path_element, '/');
1389			// Iterate over path elements
1390			while (!ss.eof())
1391			{
1392				path += '/';
1393				std::getline(ss, path_element, '/');
1394				std::istringstream nss(path_element);
1395				string node_name, node_address;
1396				std::getline(nss, node_name, '@');
1397				std::getline(nss, node_address, '@');
1398				node *next = nullptr;
1399				for (auto &c : target->child_nodes())
1400				{
1401					if (c->name == node_name)
1402					{
1403						if (c->unit_address == node_address)
1404						{
1405							next = c.get();
1406							break;
1407						}
1408						else
1409						{
1410							possible = path + c->name;
1411							if (c->unit_address != string())
1412							{
1413								possible += '@';
1414								possible += c->unit_address;
1415							}
1416						}
1417					}
1418				}
1419				path += node_name;
1420				if (node_address != string())
1421				{
1422					path += '@';
1423					path += node_address;
1424				}
1425				target = next;
1426				if (target == nullptr)
1427				{
1428					break;
1429				}
1430			}
1431		}
1432		else
1433		{
1434			target = node_names[target_name];
1435		}
1436		if (target == nullptr)
1437		{
1438			if (is_plugin)
1439			{
1440				unresolved_fixups.push_back(i);
1441				continue;
1442			}
1443			else
1444			{
1445				fprintf(stderr, "Failed to find node with label: %s\n", target_name.c_str());
1446				if (possible != string())
1447				{
1448					fprintf(stderr, "Possible intended match: %s\n", possible.c_str());
1449				}
1450				valid = 0;
1451				return;
1452			}
1453		}
1454		// If there is an existing phandle, use it
1455		property_ptr p = assign_phandle(target, phandle);
1456		p->begin()->push_to_buffer(i.get().val.byte_data);
1457		assert(i.get().val.byte_data.size() == 4);
1458	}
1459}
1460
1461bool
1462device_tree::garbage_collect_marked_nodes()
1463{
1464	std::unordered_set<node*> previously_referenced_nodes;
1465	std::unordered_set<node*> newly_referenced_nodes;
1466
1467	auto mark_referenced_nodes_used = [&](node &n)
1468	{
1469		for (auto &p : n.properties())
1470		{
1471			for (auto &v : *p)
1472			{
1473				if (v.is_phandle())
1474				{
1475					node *nx = node_names[v.string_data];
1476					if (nx == nullptr)
1477					{
1478						// Try it again, but as a path
1479						for (auto &s : node_paths)
1480						{
1481							if (v.string_data == s.second.to_string())
1482							{
1483								nx = node_names[s.first];
1484								break;
1485							}
1486						}
1487					}
1488					if (nx == nullptr)
1489					{
1490						// Couldn't resolve this one?
1491						continue;
1492					}
1493					// Only mark those currently unmarked
1494					if (!nx->used)
1495					{
1496							nx->used = 1;
1497							newly_referenced_nodes.insert(nx);
1498					}
1499				}
1500			}
1501		}
1502	};
1503
1504	// Seed our referenced nodes with those that have been seen by a node that
1505	// either will not be omitted if it's unreferenced or has a symbol.
1506	// Nodes with symbols are explicitly not garbage collected because they may
1507	// be expected for referencing by an overlay, and we do not want surprises
1508	// there.
1509	root->visit([&](node &n, node *) {
1510		if (!n.omit_if_no_ref || (write_symbols && !n.labels.empty()))
1511		{
1512			mark_referenced_nodes_used(n);
1513		}
1514		// Recurse as normal
1515		return node::VISIT_RECURSE;
1516	}, nullptr);
1517
1518	while (!newly_referenced_nodes.empty())
1519	{
1520			previously_referenced_nodes = std::move(newly_referenced_nodes);
1521			for (auto *n : previously_referenced_nodes)
1522			{
1523				mark_referenced_nodes_used(*n);
1524			}
1525	}
1526
1527	previously_referenced_nodes.clear();
1528	bool children_deleted = false;
1529
1530	// Delete
1531	root->visit([&](node &n, node *) {
1532		bool gc_children = false;
1533
1534		for (auto &cn : n.child_nodes())
1535		{
1536				if (cn->omit_if_no_ref && !cn->used)
1537				{
1538					gc_children = true;
1539					break;
1540				}
1541		}
1542
1543		if (gc_children)
1544		{
1545			children_deleted = true;
1546			n.delete_children_if([](node_ptr &nx) {
1547				return (nx->omit_if_no_ref && !nx->used);
1548			});
1549
1550			return node::VISIT_CONTINUE;
1551		}
1552
1553		return node::VISIT_RECURSE;
1554	}, nullptr);
1555
1556	return children_deleted;
1557}
1558
1559void
1560device_tree::parse_file(text_input_buffer &input,
1561                        std::vector<node_ptr> &roots,
1562                        bool &read_header)
1563{
1564	input.next_token();
1565	// Read the header
1566	if (input.consume("/dts-v1/;"))
1567	{
1568		read_header = true;
1569	}
1570	input.next_token();
1571	if (input.consume("/plugin/;"))
1572	{
1573		is_plugin = true;
1574	}
1575	input.next_token();
1576	if (!read_header)
1577	{
1578		input.parse_error("Expected /dts-v1/; version string");
1579	}
1580	// Read any memory reservations
1581	while (input.consume("/memreserve/"))
1582	{
1583		unsigned long long start, len;
1584		input.next_token();
1585		// Read the start and length.
1586		if (!(input.consume_integer_expression(start) &&
1587		    (input.next_token(),
1588		    input.consume_integer_expression(len))))
1589		{
1590			input.parse_error("Expected size on /memreserve/ node.");
1591		}
1592		else
1593		{
1594			reservations.push_back(reservation(start, len));
1595		}
1596		input.next_token();
1597		input.consume(';');
1598		input.next_token();
1599	}
1600	while (valid && !input.finished())
1601	{
1602		node_ptr n;
1603		if (input.consume('/'))
1604		{
1605			input.next_token();
1606			n = node::parse(input, *this, string(), string_set(), string(), &defines);
1607		}
1608		else if (input.consume('&'))
1609		{
1610			input.next_token();
1611			string name;
1612			bool name_is_path_reference = false;
1613			// This is to deal with names intended as path references, e.g. &{/path}.
1614			// While it may make sense in a non-plugin context, we don't support such
1615			// usage at this time.
1616			if (input.consume('{') && is_plugin)
1617			{
1618				name = input.parse_to('}');
1619				input.consume('}');
1620				name_is_path_reference = true;
1621			}
1622			else
1623			{
1624				name = input.parse_node_name();
1625			}
1626			input.next_token();
1627			n = node::parse(input, *this, std::move(name), string_set(), string(), &defines);
1628			if (n)
1629			{
1630				n->name_is_path_reference = name_is_path_reference;
1631			}
1632		}
1633		else
1634		{
1635			input.parse_error("Failed to find root node /.");
1636		}
1637		if (n)
1638		{
1639			roots.push_back(std::move(n));
1640		}
1641		else
1642		{
1643			valid = false;
1644		}
1645		input.next_token();
1646	}
1647}
1648
1649template<class writer> void
1650device_tree::write(int fd)
1651{
1652	dtb::string_table st;
1653	dtb::header head;
1654	writer head_writer;
1655	writer reservation_writer;
1656	writer struct_writer;
1657	writer strings_writer;
1658
1659	// Build the reservation table
1660	reservation_writer.write_comment(string("Memory reservations"));
1661	reservation_writer.write_label(string("dt_reserve_map"));
1662	for (auto &i : reservations)
1663	{
1664		reservation_writer.write_comment(string("Reservation start"));
1665		reservation_writer.write_data(i.first);
1666		reservation_writer.write_comment(string("Reservation length"));
1667		reservation_writer.write_data(i.second);
1668	}
1669	// Write n spare reserve map entries, plus the trailing 0.
1670	for (uint32_t i=0 ; i<=spare_reserve_map_entries ; i++)
1671	{
1672		reservation_writer.write_data((uint64_t)0);
1673		reservation_writer.write_data((uint64_t)0);
1674	}
1675
1676
1677	struct_writer.write_comment(string("Device tree"));
1678	struct_writer.write_label(string("dt_struct_start"));
1679	root->write(struct_writer, st);
1680	struct_writer.write_token(dtb::FDT_END);
1681	struct_writer.write_label(string("dt_struct_end"));
1682
1683	st.write(strings_writer);
1684	// Find the strings size before we stick padding on the end.
1685	// Note: We should possibly use a new writer for the padding.
1686	head.size_dt_strings = strings_writer.size();
1687
1688	// Stick the padding in the strings writer, but after the
1689	// marker indicating that it's the end.
1690	// Note: We probably should add a padding call to the writer so
1691	// that the asm back end can write padding directives instead
1692	// of a load of 0 bytes.
1693	for (uint32_t i=0 ; i<blob_padding ; i++)
1694	{
1695		strings_writer.write_data((uint8_t)0);
1696	}
1697	head.totalsize = sizeof(head) + strings_writer.size() +
1698		struct_writer.size() + reservation_writer.size();
1699	while (head.totalsize < minimum_blob_size)
1700	{
1701		head.totalsize++;
1702		strings_writer.write_data((uint8_t)0);
1703	}
1704	head.off_dt_struct = sizeof(head) + reservation_writer.size();;
1705	head.off_dt_strings = head.off_dt_struct + struct_writer.size();
1706	head.off_mem_rsvmap = sizeof(head);
1707	head.boot_cpuid_phys = boot_cpu;
1708	head.size_dt_struct = struct_writer.size();
1709	head.write(head_writer);
1710
1711	head_writer.write_to_file(fd);
1712	reservation_writer.write_to_file(fd);
1713	struct_writer.write_to_file(fd);
1714	strings_writer.write_label(string("dt_blob_end"));
1715	strings_writer.write_to_file(fd);
1716}
1717
1718node*
1719device_tree::referenced_node(property_value &v)
1720{
1721	if (v.is_phandle())
1722	{
1723		return node_names[v.string_data];
1724	}
1725	if (v.is_binary())
1726	{
1727		return used_phandles[v.get_as_uint32()];
1728	}
1729	return 0;
1730}
1731
1732void
1733device_tree::write_binary(int fd)
1734{
1735	write<dtb::binary_writer>(fd);
1736}
1737
1738void
1739device_tree::write_asm(int fd)
1740{
1741	write<dtb::asm_writer>(fd);
1742}
1743
1744void
1745device_tree::write_dts(int fd)
1746{
1747	FILE *file = fdopen(fd, "w");
1748	fputs("/dts-v1/;\n\n", file);
1749
1750	if (!reservations.empty())
1751	{
1752		const char msg[] = "/memreserve/";
1753		// Exclude the null byte when we're writing it out to the file.
1754		fwrite(msg, sizeof(msg) - 1, 1, file);
1755		for (auto &i : reservations)
1756		{
1757			fprintf(file, " 0x%" PRIx64 " 0x%" PRIx64, i.first, i.second);
1758		}
1759		fputs(";\n\n", file);
1760	}
1761	putc('/', file);
1762	putc(' ', file);
1763	root->write_dts(file, 0);
1764	fclose(file);
1765}
1766
1767void
1768device_tree::parse_dtb(const string &fn, FILE *)
1769{
1770	auto in = input_buffer::buffer_for_file(fn);
1771	if (in == 0)
1772	{
1773		valid = false;
1774		return;
1775	}
1776	input_buffer &input = *in;
1777	dtb::header h;
1778	valid = h.read_dtb(input);
1779	boot_cpu = h.boot_cpuid_phys;
1780	if (h.last_comp_version > 17)
1781	{
1782		fprintf(stderr, "Don't know how to read this version of the device tree blob");
1783		valid = false;
1784	}
1785	if (!valid)
1786	{
1787		return;
1788	}
1789	input_buffer reservation_map =
1790		input.buffer_from_offset(h.off_mem_rsvmap, 0);
1791	uint64_t start, length;
1792	do
1793	{
1794		if (!(reservation_map.consume_binary(start) &&
1795		      reservation_map.consume_binary(length)))
1796		{
1797			fprintf(stderr, "Failed to read memory reservation table\n");
1798			valid = false;
1799			return;
1800		}
1801		if (start != 0 || length != 0)
1802		{
1803			reservations.push_back(reservation(start, length));
1804		}
1805	} while (!((start == 0) && (length == 0)));
1806	input_buffer struct_table =
1807		input.buffer_from_offset(h.off_dt_struct, h.size_dt_struct);
1808	input_buffer strings_table =
1809		input.buffer_from_offset(h.off_dt_strings, h.size_dt_strings);
1810	uint32_t token;
1811	if (!(struct_table.consume_binary(token) &&
1812		(token == dtb::FDT_BEGIN_NODE)))
1813	{
1814		fprintf(stderr, "Expected FDT_BEGIN_NODE token.\n");
1815		valid = false;
1816		return;
1817	}
1818	root = node::parse_dtb(struct_table, strings_table);
1819	if (!(struct_table.consume_binary(token) && (token == dtb::FDT_END)))
1820	{
1821		fprintf(stderr, "Expected FDT_END token after parsing root node.\n");
1822		valid = false;
1823		return;
1824	}
1825	valid = (root != 0);
1826}
1827
1828string
1829device_tree::node_path::to_string() const
1830{
1831	string path;
1832	auto p = begin();
1833	auto pe = end();
1834	if ((p == pe) || (p+1 == pe))
1835	{
1836		return string("/");
1837	}
1838	// Skip the first name in the path.  It's always "", and implicitly /
1839	for (++p ; p!=pe ; ++p)
1840	{
1841		path += '/';
1842		path += p->first;
1843		if (!(p->second.empty()))
1844		{
1845			path += '@';
1846			path += p->second;
1847		}
1848	}
1849	return path;
1850}
1851
1852node_ptr
1853device_tree::create_fragment_wrapper(node_ptr &node, int &fragnum)
1854{
1855	// In a plugin, we can massage these non-/ root nodes into into a fragment
1856	std::string fragment_address = "fragment@" + std::to_string(fragnum);
1857	++fragnum;
1858
1859	std::vector<property_ptr> symbols;
1860
1861	// Intentionally left empty
1862	node_ptr newroot = node::create_special_node("", symbols);
1863	node_ptr wrapper = node::create_special_node("__overlay__", symbols);
1864
1865	// Generate the fragment with $propname = <&name>
1866	property_value v;
1867	std::string propname;
1868	v.string_data = node->name;
1869	if (!node->name_is_path_reference)
1870	{
1871		propname = "target";
1872		v.type = property_value::PHANDLE;
1873	}
1874	else
1875	{
1876		propname = "target-path";
1877		v.type = property_value::STRING;
1878	}
1879	auto prop = std::make_shared<property>(std::string(propname));
1880	prop->add_value(v);
1881	symbols.push_back(prop);
1882
1883	node_ptr fragment = node::create_special_node(fragment_address, symbols);
1884
1885	wrapper->merge_node(node);
1886	fragment->add_child(std::move(wrapper));
1887	newroot->add_child(std::move(fragment));
1888	return newroot;
1889}
1890
1891node_ptr
1892device_tree::generate_root(node_ptr &node, int &fragnum)
1893{
1894
1895	string name = node->name;
1896	if (name == string())
1897	{
1898		return std::move(node);
1899	}
1900	else if (!is_plugin)
1901	{
1902		return nullptr;
1903	}
1904
1905	return create_fragment_wrapper(node, fragnum);
1906}
1907
1908void
1909device_tree::reassign_fragment_numbers(node_ptr &node, int &delta)
1910{
1911
1912	for (auto &c : node->child_nodes())
1913	{
1914		if (c->name == std::string("fragment"))
1915		{
1916			int current_address = std::stoi(c->unit_address, nullptr, 16);
1917			std::ostringstream new_address;
1918			current_address += delta;
1919			// It's possible that we hopped more than one somewhere, so just reset
1920			// delta to the next in sequence.
1921			delta = current_address + 1;
1922			new_address << std::hex << current_address;
1923			c->unit_address = new_address.str();
1924		}
1925	}
1926}
1927
1928void
1929device_tree::parse_dts(const string &fn, FILE *depfile)
1930{
1931	auto in = input_buffer::buffer_for_file(fn);
1932	if (!in)
1933	{
1934		valid = false;
1935		return;
1936	}
1937	std::vector<node_ptr> roots;
1938	std::unordered_set<string> defnames;
1939	for (auto &i : defines)
1940	{
1941		defnames.insert(i.first);
1942	}
1943	text_input_buffer input(std::move(in),
1944	                        std::move(defnames),
1945	                        std::vector<string>(include_paths),
1946	                        dirname(fn),
1947	                        depfile);
1948	bool read_header = false;
1949	int fragnum = 0;
1950	parse_file(input, roots, read_header);
1951	switch (roots.size())
1952	{
1953		case 0:
1954			valid = false;
1955			input.parse_error("Failed to find root node /.");
1956			return;
1957		case 1:
1958			root = generate_root(roots[0], fragnum);
1959			if (!root)
1960			{
1961				valid = false;
1962				input.parse_error("Failed to find root node /.");
1963				return;
1964			}
1965			break;
1966		default:
1967		{
1968			root = generate_root(roots[0], fragnum);
1969			if (!root)
1970			{
1971				valid = false;
1972				input.parse_error("Failed to find root node /.");
1973				return;
1974			}
1975			for (auto i=++(roots.begin()), e=roots.end() ; i!=e ; ++i)
1976			{
1977				auto &node = *i;
1978				string name = node->name;
1979				if (name == string())
1980				{
1981					if (is_plugin)
1982					{
1983						// Re-assign any fragment numbers based on a delta of
1984						// fragnum before we merge it
1985						reassign_fragment_numbers(node, fragnum);
1986					}
1987					root->merge_node(node);
1988				}
1989				else
1990				{
1991					auto existing = node_names.find(name);
1992					if (existing == node_names.end())
1993					{
1994						collect_names();
1995						existing = node_names.find(name);
1996					}
1997					if (existing == node_names.end())
1998					{
1999						if (is_plugin)
2000						{
2001							auto fragment = create_fragment_wrapper(node, fragnum);
2002							root->merge_node(fragment);
2003						}
2004						else
2005						{
2006							fprintf(stderr, "Unable to merge node: %s\n", name.c_str());
2007						}
2008					}
2009					else
2010					{
2011						existing->second->merge_node(node);
2012					}
2013				}
2014			}
2015		}
2016	}
2017	collect_names();
2018	// Return value indicates whether we've dirtied the tree or not and need to
2019	// recollect names
2020	if (garbage_collect && garbage_collect_marked_nodes())
2021	{
2022		collect_names();
2023	}
2024	uint32_t phandle = 1;
2025	// If we're writing symbols, go ahead and assign phandles to the entire
2026	// tree. We'll do this before we resolve cross references, just to keep
2027	// order semi-predictable and stable.
2028	if (write_symbols)
2029	{
2030		assign_phandles(root, phandle);
2031	}
2032	resolve_cross_references(phandle);
2033	if (write_symbols)
2034	{
2035		std::vector<property_ptr> symbols;
2036		// Create a symbol table.  Each label  in this device tree may be
2037		// referenced by other plugins, so we create a __symbols__ node inside
2038		// the root that contains mappings (properties) from label names to
2039		// paths.
2040		for (auto i=ordered_node_paths.rbegin(), e=ordered_node_paths.rend() ; i!=e ; ++i)
2041		{
2042			auto &s = *i;
2043			if (node_paths.find(s.first) == node_paths.end())
2044			{
2045				// Erased node, skip it.
2046				continue;
2047			}
2048			property_value v;
2049			v.string_data = s.second.to_string();
2050			v.type = property_value::STRING;
2051			string name = s.first;
2052			auto prop = std::make_shared<property>(std::move(name));
2053			prop->add_value(v);
2054			symbols.push_back(prop);
2055		}
2056		root->add_child(node::create_special_node("__symbols__", symbols));
2057	}
2058	// If this is a plugin, then we also need to create two extra nodes.
2059	// Internal phandles will need to be renumbered to avoid conflicts with
2060	// already-loaded nodes and external references will need to be
2061	// resolved.
2062	if (is_plugin)
2063	{
2064		std::vector<property_ptr> symbols;
2065		// Create the fixups entry.  This is of the form:
2066		// {target} = {path}:{property name}:{offset}
2067		auto create_fixup_entry = [&](fixup &i, string target)
2068			{
2069				string value = i.path.to_string();
2070				value += ':';
2071				value += i.prop->get_key();
2072				value += ':';
2073				value += std::to_string(i.prop->offset_of_value(i.val));
2074				property_value v;
2075				v.string_data = value;
2076				v.type = property_value::STRING;
2077				auto prop = std::make_shared<property>(std::move(target));
2078				prop->add_value(v);
2079				return prop;
2080			};
2081		// If we have any unresolved phandle references in this plugin,
2082		// then we must update them to 0xdeadbeef and leave a property in
2083		// the /__fixups__ node whose key is the label and whose value is
2084		// as described above.
2085		if (!unresolved_fixups.empty())
2086		{
2087			for (auto &i : unresolved_fixups)
2088			{
2089				auto &val = i.get().val;
2090				symbols.push_back(create_fixup_entry(i, val.string_data));
2091				val.byte_data.push_back(0xde);
2092				val.byte_data.push_back(0xad);
2093				val.byte_data.push_back(0xbe);
2094				val.byte_data.push_back(0xef);
2095				val.type = property_value::BINARY;
2096			}
2097			root->add_child(node::create_special_node("__fixups__", symbols));
2098		}
2099		symbols.clear();
2100		// If we have any resolved phandle references in this plugin, then
2101		// we must create a child in the __local_fixups__ node whose path
2102		// matches the node path from the root and whose value contains the
2103		// location of the reference within a property.
2104
2105		// Create a local_fixups node that is initially empty.
2106		node_ptr local_fixups = node::create_special_node("__local_fixups__", symbols);
2107		for (auto &i : fixups)
2108		{
2109			if (!i.val.is_phandle())
2110			{
2111				continue;
2112			}
2113			node *n = local_fixups.get();
2114			for (auto &p : i.path)
2115			{
2116				// Skip the implicit root
2117				if (p.first.empty())
2118				{
2119					continue;
2120				}
2121				bool found = false;
2122				for (auto &c : n->child_nodes())
2123				{
2124					if (c->name == p.first)
2125					{
2126						if (c->unit_address == p.second)
2127						{
2128							n = c.get();
2129							found = true;
2130							break;
2131						}
2132					}
2133				}
2134				if (!found)
2135				{
2136					string path = p.first;
2137					if (!(p.second.empty()))
2138					{
2139						path += '@';
2140						path += p.second;
2141					}
2142					n->add_child(node::create_special_node(path, symbols));
2143					n = (--n->child_end())->get();
2144				}
2145			}
2146			assert(n);
2147			property_value pv;
2148			push_big_endian(pv.byte_data, static_cast<uint32_t>(i.prop->offset_of_value(i.val)));
2149			pv.type = property_value::BINARY;
2150			auto key = i.prop->get_key();
2151			property_ptr prop = n->get_property(key);
2152			// If we don't have an existing property then create one and
2153			// use this property value
2154			if (!prop)
2155			{
2156				prop = std::make_shared<property>(std::move(key));
2157				n->add_property(prop);
2158				prop->add_value(pv);
2159			}
2160			else
2161			{
2162				// If we do have an existing property value, try to append
2163				// this value.
2164				property_value &old_val = *(--prop->end());
2165				if (!old_val.try_to_merge(pv))
2166				{
2167					prop->add_value(pv);
2168				}
2169			}
2170		}
2171		// We've iterated over all fixups, but only emit the
2172		// __local_fixups__ if we found some that were resolved internally.
2173		if (local_fixups->child_begin() != local_fixups->child_end())
2174		{
2175			root->add_child(std::move(local_fixups));
2176		}
2177	}
2178}
2179
2180bool device_tree::parse_define(const char *def)
2181{
2182	const char *val = strchr(def, '=');
2183	if (!val)
2184	{
2185		if (strlen(def) != 0)
2186		{
2187			string name(def);
2188			defines[name];
2189			return true;
2190		}
2191		return false;
2192	}
2193	string name(def, val-def);
2194	string name_copy = name;
2195	val++;
2196	std::unique_ptr<input_buffer> raw(new input_buffer(val, strlen(val)));
2197	text_input_buffer in(std::move(raw),
2198	                     std::unordered_set<string>(),
2199	                     std::vector<string>(),
2200	                     string(),
2201	                     nullptr);
2202	property_ptr p = property::parse(in, std::move(name_copy), string_set(), false);
2203	if (p)
2204		defines[name] = p;
2205	return (bool)p;
2206}
2207
2208} // namespace fdt
2209
2210} // namespace dtc
2211
2212