1// SPDX-License-Identifier: GPL-2.0-or-later
   2/*
   3 * (C) Copyright David Gibson <dwg@au1.ibm.com>, IBM Corporation.  2005.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
   4 */
   5
   6#include "dtc.h"
   7#include "srcpos.h"
   8
   9/*
  10 * Tree building functions
  11 */
  12
  13void add_label(struct label **labels, char *label)
  14{
  15	struct label *new;
  16
  17	/* Make sure the label isn't already there */
  18	for_each_label_withdel(*labels, new)
  19		if (streq(new->label, label)) {
  20			new->deleted = 0;
  21			return;
  22		}
  23
  24	new = xmalloc(sizeof(*new));
  25	memset(new, 0, sizeof(*new));
  26	new->label = label;
  27	new->next = *labels;
  28	*labels = new;
  29}
  30
  31void delete_labels(struct label **labels)
  32{
  33	struct label *label;
  34
  35	for_each_label(*labels, label)
  36		label->deleted = 1;
  37}
  38
  39struct property *build_property(const char *name, struct data val,
  40				struct srcpos *srcpos)
  41{
  42	struct property *new = xmalloc(sizeof(*new));
  43
  44	memset(new, 0, sizeof(*new));
  45
  46	new->name = xstrdup(name);
  47	new->val = val;
  48	new->srcpos = srcpos_copy(srcpos);
  49
  50	return new;
  51}
  52
  53struct property *build_property_delete(const char *name)
  54{
  55	struct property *new = xmalloc(sizeof(*new));
  56
  57	memset(new, 0, sizeof(*new));
  58
  59	new->name = xstrdup(name);
  60	new->deleted = 1;
  61
  62	return new;
  63}
  64
  65struct property *chain_property(struct property *first, struct property *list)
  66{
  67	assert(first->next == NULL);
  68
  69	first->next = list;
  70	return first;
  71}
  72
  73struct property *reverse_properties(struct property *first)
  74{
  75	struct property *p = first;
  76	struct property *head = NULL;
  77	struct property *next;
  78
  79	while (p) {
  80		next = p->next;
  81		p->next = head;
  82		head = p;
  83		p = next;
  84	}
  85	return head;
  86}
  87
  88struct node *build_node(struct property *proplist, struct node *children,
  89			struct srcpos *srcpos)
  90{
  91	struct node *new = xmalloc(sizeof(*new));
  92	struct node *child;
  93
  94	memset(new, 0, sizeof(*new));
  95
  96	new->proplist = reverse_properties(proplist);
  97	new->children = children;
  98	new->srcpos = srcpos_copy(srcpos);
  99
 100	for_each_child(new, child) {
 101		child->parent = new;
 102	}
 103
 104	return new;
 105}
 106
 107struct node *build_node_delete(struct srcpos *srcpos)
 108{
 109	struct node *new = xmalloc(sizeof(*new));
 110
 111	memset(new, 0, sizeof(*new));
 112
 113	new->deleted = 1;
 114	new->srcpos = srcpos_copy(srcpos);
 115
 116	return new;
 117}
 118
 119struct node *name_node(struct node *node, const char *name)
 120{
 121	assert(node->name == NULL);
 122
 123	node->name = xstrdup(name);
 124
 125	return node;
 126}
 127
 128struct node *omit_node_if_unused(struct node *node)
 129{
 130	node->omit_if_unused = 1;
 131
 132	return node;
 133}
 134
 135struct node *reference_node(struct node *node)
 136{
 137	node->is_referenced = 1;
 138
 139	return node;
 140}
 141
 142struct node *merge_nodes(struct node *old_node, struct node *new_node)
 143{
 144	struct property *new_prop, *old_prop;
 145	struct node *new_child, *old_child;
 146	struct label *l;
 147
 148	old_node->deleted = 0;
 149
 150	/* Add new node labels to old node */
 151	for_each_label_withdel(new_node->labels, l)
 152		add_label(&old_node->labels, l->label);
 153
 154	/* Move properties from the new node to the old node.  If there
 155	 * is a collision, replace the old value with the new */
 156	while (new_node->proplist) {
 157		/* Pop the property off the list */
 158		new_prop = new_node->proplist;
 159		new_node->proplist = new_prop->next;
 160		new_prop->next = NULL;
 161
 162		if (new_prop->deleted) {
 163			delete_property_by_name(old_node, new_prop->name);
 164			free(new_prop);
 165			continue;
 166		}
 167
 168		/* Look for a collision, set new value if there is */
 169		for_each_property_withdel(old_node, old_prop) {
 170			if (streq(old_prop->name, new_prop->name)) {
 171				/* Add new labels to old property */
 172				for_each_label_withdel(new_prop->labels, l)
 173					add_label(&old_prop->labels, l->label);
 174
 175				old_prop->val = new_prop->val;
 176				old_prop->deleted = 0;
 177				free(old_prop->srcpos);
 178				old_prop->srcpos = new_prop->srcpos;
 179				free(new_prop);
 180				new_prop = NULL;
 181				break;
 182			}
 183		}
 184
 185		/* if no collision occurred, add property to the old node. */
 186		if (new_prop)
 187			add_property(old_node, new_prop);
 188	}
 189
 190	/* Move the override child nodes into the primary node.  If
 191	 * there is a collision, then merge the nodes. */
 192	while (new_node->children) {
 193		/* Pop the child node off the list */
 194		new_child = new_node->children;
 195		new_node->children = new_child->next_sibling;
 196		new_child->parent = NULL;
 197		new_child->next_sibling = NULL;
 198
 199		if (new_child->deleted) {
 200			delete_node_by_name(old_node, new_child->name);
 201			free(new_child);
 202			continue;
 203		}
 204
 205		/* Search for a collision.  Merge if there is */
 206		for_each_child_withdel(old_node, old_child) {
 207			if (streq(old_child->name, new_child->name)) {
 208				merge_nodes(old_child, new_child);
 209				new_child = NULL;
 210				break;
 211			}
 212		}
 213
 214		/* if no collision occurred, add child to the old node. */
 215		if (new_child)
 216			add_child(old_node, new_child);
 217	}
 218
 219	old_node->srcpos = srcpos_extend(old_node->srcpos, new_node->srcpos);
 220
 221	/* The new node contents are now merged into the old node.  Free
 222	 * the new node. */
 223	free(new_node);
 224
 225	return old_node;
 226}
 227
 228struct node * add_orphan_node(struct node *dt, struct node *new_node, char *ref)
 229{
 230	static unsigned int next_orphan_fragment = 0;
 231	struct node *node;
 232	struct property *p;
 233	struct data d = empty_data;
 234	char *name;
 235
 236	if (ref[0] == '/') {
 237		d = data_add_marker(d, TYPE_STRING, ref);
 238		d = data_append_data(d, ref, strlen(ref) + 1);
 239
 240		p = build_property("target-path", d, NULL);
 241	} else {
 242		d = data_add_marker(d, REF_PHANDLE, ref);
 243		d = data_append_integer(d, 0xffffffff, 32);
 244
 245		p = build_property("target", d, NULL);
 246	}
 247
 248	xasprintf(&name, "fragment@%u",
 249			next_orphan_fragment++);
 250	name_node(new_node, "__overlay__");
 251	node = build_node(p, new_node, NULL);
 252	name_node(node, name);
 253	free(name);
 254
 255	add_child(dt, node);
 256	return dt;
 257}
 258
 259struct node *chain_node(struct node *first, struct node *list)
 260{
 261	assert(first->next_sibling == NULL);
 262
 263	first->next_sibling = list;
 264	return first;
 265}
 266
 267void add_property(struct node *node, struct property *prop)
 268{
 269	struct property **p;
 270
 271	prop->next = NULL;
 272
 273	p = &node->proplist;
 274	while (*p)
 275		p = &((*p)->next);
 276
 277	*p = prop;
 278}
 279
 280void delete_property_by_name(struct node *node, char *name)
 281{
 282	struct property *prop = node->proplist;
 283
 284	while (prop) {
 285		if (streq(prop->name, name)) {
 286			delete_property(prop);
 287			return;
 288		}
 289		prop = prop->next;
 290	}
 291}
 292
 293void delete_property(struct property *prop)
 294{
 295	prop->deleted = 1;
 296	delete_labels(&prop->labels);
 297}
 298
 299void add_child(struct node *parent, struct node *child)
 300{
 301	struct node **p;
 302
 303	child->next_sibling = NULL;
 304	child->parent = parent;
 305
 306	p = &parent->children;
 307	while (*p)
 308		p = &((*p)->next_sibling);
 309
 310	*p = child;
 311}
 312
 313void delete_node_by_name(struct node *parent, char *name)
 314{
 315	struct node *node = parent->children;
 316
 317	while (node) {
 318		if (streq(node->name, name)) {
 319			delete_node(node);
 320			return;
 321		}
 322		node = node->next_sibling;
 323	}
 324}
 325
 326void delete_node(struct node *node)
 327{
 328	struct property *prop;
 329	struct node *child;
 330
 331	node->deleted = 1;
 332	for_each_child(node, child)
 333		delete_node(child);
 334	for_each_property(node, prop)
 335		delete_property(prop);
 336	delete_labels(&node->labels);
 337}
 338
 339void append_to_property(struct node *node,
 340			char *name, const void *data, int len,
 341			enum markertype type)
 342{
 343	struct data d;
 344	struct property *p;
 345
 346	p = get_property(node, name);
 347	if (p) {
 348		d = data_add_marker(p->val, type, name);
 349		d = data_append_data(d, data, len);
 350		p->val = d;
 351	} else {
 352		d = data_add_marker(empty_data, type, name);
 353		d = data_append_data(d, data, len);
 354		p = build_property(name, d, NULL);
 355		add_property(node, p);
 356	}
 357}
 358
 359struct reserve_info *build_reserve_entry(uint64_t address, uint64_t size)
 360{
 361	struct reserve_info *new = xmalloc(sizeof(*new));
 362
 363	memset(new, 0, sizeof(*new));
 364
 365	new->address = address;
 366	new->size = size;
 367
 368	return new;
 369}
 370
 371struct reserve_info *chain_reserve_entry(struct reserve_info *first,
 372					struct reserve_info *list)
 373{
 374	assert(first->next == NULL);
 375
 376	first->next = list;
 377	return first;
 378}
 379
 380struct reserve_info *add_reserve_entry(struct reserve_info *list,
 381				      struct reserve_info *new)
 382{
 383	struct reserve_info *last;
 384
 385	new->next = NULL;
 386
 387	if (! list)
 388		return new;
 389
 390	for (last = list; last->next; last = last->next)
 391		;
 392
 393	last->next = new;
 394
 395	return list;
 396}
 397
 398struct dt_info *build_dt_info(unsigned int dtsflags,
 399			      struct reserve_info *reservelist,
 400			      struct node *tree, uint32_t boot_cpuid_phys)
 401{
 402	struct dt_info *dti;
 403
 404	dti = xmalloc(sizeof(*dti));
 405	dti->dtsflags = dtsflags;
 406	dti->reservelist = reservelist;
 407	dti->dt = tree;
 408	dti->boot_cpuid_phys = boot_cpuid_phys;
 409
 410	return dti;
 411}
 412
 413/*
 414 * Tree accessor functions
 415 */
 416
 417const char *get_unitname(struct node *node)
 418{
 419	if (node->name[node->basenamelen] == '\0')
 420		return "";
 421	else
 422		return node->name + node->basenamelen + 1;
 423}
 424
 425struct property *get_property(struct node *node, const char *propname)
 426{
 427	struct property *prop;
 428
 429	for_each_property(node, prop)
 430		if (streq(prop->name, propname))
 431			return prop;
 432
 433	return NULL;
 434}
 435
 436cell_t propval_cell(struct property *prop)
 437{
 438	assert(prop->val.len == sizeof(cell_t));
 439	return fdt32_to_cpu(*((fdt32_t *)prop->val.val));
 440}
 441
 442cell_t propval_cell_n(struct property *prop, unsigned int n)
 443{
 444	assert(prop->val.len / sizeof(cell_t) > n);
 445	return fdt32_to_cpu(*((fdt32_t *)prop->val.val + n));
 446}
 447
 448struct property *get_property_by_label(struct node *tree, const char *label,
 449				       struct node **node)
 450{
 451	struct property *prop;
 452	struct node *c;
 453
 454	*node = tree;
 455
 456	for_each_property(tree, prop) {
 457		struct label *l;
 458
 459		for_each_label(prop->labels, l)
 460			if (streq(l->label, label))
 461				return prop;
 462	}
 463
 464	for_each_child(tree, c) {
 465		prop = get_property_by_label(c, label, node);
 466		if (prop)
 467			return prop;
 468	}
 469
 470	*node = NULL;
 471	return NULL;
 472}
 473
 474struct marker *get_marker_label(struct node *tree, const char *label,
 475				struct node **node, struct property **prop)
 476{
 477	struct marker *m;
 478	struct property *p;
 479	struct node *c;
 480
 481	*node = tree;
 482
 483	for_each_property(tree, p) {
 484		*prop = p;
 485		m = p->val.markers;
 486		for_each_marker_of_type(m, LABEL)
 487			if (streq(m->ref, label))
 488				return m;
 489	}
 490
 491	for_each_child(tree, c) {
 492		m = get_marker_label(c, label, node, prop);
 493		if (m)
 494			return m;
 495	}
 496
 497	*prop = NULL;
 498	*node = NULL;
 499	return NULL;
 500}
 501
 502struct node *get_subnode(struct node *node, const char *nodename)
 503{
 504	struct node *child;
 505
 506	for_each_child(node, child)
 507		if (streq(child->name, nodename))
 508			return child;
 509
 510	return NULL;
 511}
 512
 513struct node *get_node_by_path(struct node *tree, const char *path)
 514{
 515	const char *p;
 516	struct node *child;
 517
 518	if (!path || ! (*path)) {
 519		if (tree->deleted)
 520			return NULL;
 521		return tree;
 522	}
 523
 524	while (path[0] == '/')
 525		path++;
 526
 527	p = strchr(path, '/');
 528
 529	for_each_child(tree, child) {
 530		if (p && strprefixeq(path, (size_t)(p - path), child->name))
 531			return get_node_by_path(child, p+1);
 532		else if (!p && streq(path, child->name))
 533			return child;
 534	}
 535
 536	return NULL;
 537}
 538
 539struct node *get_node_by_label(struct node *tree, const char *label)
 540{
 541	struct node *child, *node;
 542	struct label *l;
 543
 544	assert(label && (strlen(label) > 0));
 545
 546	for_each_label(tree->labels, l)
 547		if (streq(l->label, label))
 548			return tree;
 549
 550	for_each_child(tree, child) {
 551		node = get_node_by_label(child, label);
 552		if (node)
 553			return node;
 554	}
 555
 556	return NULL;
 557}
 558
 559struct node *get_node_by_phandle(struct node *tree, cell_t phandle)
 560{
 561	struct node *child, *node;
 562
 563	if (!phandle_is_valid(phandle)) {
 564		assert(generate_fixups);
 565		return NULL;
 566	}
 567
 568	if (tree->phandle == phandle) {
 569		if (tree->deleted)
 570			return NULL;
 571		return tree;
 572	}
 573
 574	for_each_child(tree, child) {
 575		node = get_node_by_phandle(child, phandle);
 576		if (node)
 577			return node;
 578	}
 579
 580	return NULL;
 581}
 582
 583struct node *get_node_by_ref(struct node *tree, const char *ref)
 584{
 585	struct node *target = tree;
 586	const char *label = NULL, *path = NULL;
 587
 588	if (streq(ref, "/"))
 589		return tree;
 590
 591	if (ref[0] == '/')
 592		path = ref;
 593	else
 594		label = ref;
 595
 596	if (label) {
 597		const char *slash = strchr(label, '/');
 598		char *buf = NULL;
 599
 600		if (slash) {
 601			buf = xstrndup(label, slash - label);
 602			label = buf;
 603			path = slash + 1;
 604		}
 605
 606		target = get_node_by_label(tree, label);
 607
 608		free(buf);
 609
 610		if (!target)
 611			return NULL;
 612	}
 613
 614	if (path)
 615		target = get_node_by_path(target, path);
 616
 617	return target;
 618}
 619
 620static void add_phandle_property(struct node *node,
 621				 const char *name, int format)
 622{
 623	struct data d;
 624
 625	if (!(phandle_format & format))
 626		return;
 627	if (get_property(node, name))
 628		return;
 629
 630	d = data_add_marker(empty_data, TYPE_UINT32, NULL);
 631	d = data_append_cell(d, node->phandle);
 632
 633	add_property(node, build_property(name, d, NULL));
 634}
 635
 636cell_t get_node_phandle(struct node *root, struct node *node)
 637{
 638	static cell_t phandle = 1; /* FIXME: ick, static local */
 639
 640	if (phandle_is_valid(node->phandle))
 641		return node->phandle;
 642
 643	while (get_node_by_phandle(root, phandle))
 644		phandle++;
 645
 646	node->phandle = phandle;
 647
 648	add_phandle_property(node, "linux,phandle", PHANDLE_LEGACY);
 649	add_phandle_property(node, "phandle", PHANDLE_EPAPR);
 
 
 
 
 
 
 
 
 
 650
 651	/* If the node *does* have a phandle property, we must
 652	 * be dealing with a self-referencing phandle, which will be
 653	 * fixed up momentarily in the caller */
 654
 655	return node->phandle;
 656}
 657
 658uint32_t guess_boot_cpuid(struct node *tree)
 659{
 660	struct node *cpus, *bootcpu;
 661	struct property *reg;
 662
 663	cpus = get_node_by_path(tree, "/cpus");
 664	if (!cpus)
 665		return 0;
 666
 667
 668	bootcpu = cpus->children;
 669	if (!bootcpu)
 670		return 0;
 671
 672	reg = get_property(bootcpu, "reg");
 673	if (!reg || (reg->val.len != sizeof(uint32_t)))
 674		return 0;
 675
 676	/* FIXME: Sanity check node? */
 677
 678	return propval_cell(reg);
 679}
 680
 681static int cmp_reserve_info(const void *ax, const void *bx)
 682{
 683	const struct reserve_info *a, *b;
 684
 685	a = *((const struct reserve_info * const *)ax);
 686	b = *((const struct reserve_info * const *)bx);
 687
 688	if (a->address < b->address)
 689		return -1;
 690	else if (a->address > b->address)
 691		return 1;
 692	else if (a->size < b->size)
 693		return -1;
 694	else if (a->size > b->size)
 695		return 1;
 696	else
 697		return 0;
 698}
 699
 700static void sort_reserve_entries(struct dt_info *dti)
 701{
 702	struct reserve_info *ri, **tbl;
 703	int n = 0, i = 0;
 704
 705	for (ri = dti->reservelist;
 706	     ri;
 707	     ri = ri->next)
 708		n++;
 709
 710	if (n == 0)
 711		return;
 712
 713	tbl = xmalloc(n * sizeof(*tbl));
 714
 715	for (ri = dti->reservelist;
 716	     ri;
 717	     ri = ri->next)
 718		tbl[i++] = ri;
 719
 720	qsort(tbl, n, sizeof(*tbl), cmp_reserve_info);
 721
 722	dti->reservelist = tbl[0];
 723	for (i = 0; i < (n-1); i++)
 724		tbl[i]->next = tbl[i+1];
 725	tbl[n-1]->next = NULL;
 726
 727	free(tbl);
 728}
 729
 730static int cmp_prop(const void *ax, const void *bx)
 731{
 732	const struct property *a, *b;
 733
 734	a = *((const struct property * const *)ax);
 735	b = *((const struct property * const *)bx);
 736
 737	return strcmp(a->name, b->name);
 738}
 739
 740static void sort_properties(struct node *node)
 741{
 742	int n = 0, i = 0;
 743	struct property *prop, **tbl;
 744
 745	for_each_property_withdel(node, prop)
 746		n++;
 747
 748	if (n == 0)
 749		return;
 750
 751	tbl = xmalloc(n * sizeof(*tbl));
 752
 753	for_each_property_withdel(node, prop)
 754		tbl[i++] = prop;
 755
 756	qsort(tbl, n, sizeof(*tbl), cmp_prop);
 757
 758	node->proplist = tbl[0];
 759	for (i = 0; i < (n-1); i++)
 760		tbl[i]->next = tbl[i+1];
 761	tbl[n-1]->next = NULL;
 762
 763	free(tbl);
 764}
 765
 766static int cmp_subnode(const void *ax, const void *bx)
 767{
 768	const struct node *a, *b;
 769
 770	a = *((const struct node * const *)ax);
 771	b = *((const struct node * const *)bx);
 772
 773	return strcmp(a->name, b->name);
 774}
 775
 776static void sort_subnodes(struct node *node)
 777{
 778	int n = 0, i = 0;
 779	struct node *subnode, **tbl;
 780
 781	for_each_child_withdel(node, subnode)
 782		n++;
 783
 784	if (n == 0)
 785		return;
 786
 787	tbl = xmalloc(n * sizeof(*tbl));
 788
 789	for_each_child_withdel(node, subnode)
 790		tbl[i++] = subnode;
 791
 792	qsort(tbl, n, sizeof(*tbl), cmp_subnode);
 793
 794	node->children = tbl[0];
 795	for (i = 0; i < (n-1); i++)
 796		tbl[i]->next_sibling = tbl[i+1];
 797	tbl[n-1]->next_sibling = NULL;
 798
 799	free(tbl);
 800}
 801
 802static void sort_node(struct node *node)
 803{
 804	struct node *c;
 805
 806	sort_properties(node);
 807	sort_subnodes(node);
 808	for_each_child_withdel(node, c)
 809		sort_node(c);
 810}
 811
 812void sort_tree(struct dt_info *dti)
 813{
 814	sort_reserve_entries(dti);
 815	sort_node(dti->dt);
 816}
 817
 818/* utility helper to avoid code duplication */
 819static struct node *build_and_name_child_node(struct node *parent, const char *name)
 820{
 821	struct node *node;
 822
 823	node = build_node(NULL, NULL, NULL);
 824	name_node(node, name);
 825	add_child(parent, node);
 826
 827	return node;
 828}
 829
 830static struct node *build_root_node(struct node *dt, const char *name)
 831{
 832	struct node *an;
 833
 834	an = get_subnode(dt, name);
 835	if (!an)
 836		an = build_and_name_child_node(dt, name);
 837
 838	if (!an)
 839		die("Could not build root node /%s\n", name);
 840
 841	return an;
 842}
 843
 844static bool any_label_tree(struct dt_info *dti, struct node *node)
 845{
 846	struct node *c;
 847
 848	if (node->labels)
 849		return true;
 850
 851	for_each_child(node, c)
 852		if (any_label_tree(dti, c))
 853			return true;
 854
 855	return false;
 856}
 857
 858static void generate_label_tree_internal(struct dt_info *dti,
 859					 struct node *an, struct node *node,
 860					 bool allocph)
 861{
 862	struct node *dt = dti->dt;
 863	struct node *c;
 864	struct property *p;
 865	struct label *l;
 866
 867	/* if there are labels */
 868	if (node->labels) {
 869
 870		/* now add the label in the node */
 871		for_each_label(node->labels, l) {
 872
 873			/* check whether the label already exists */
 874			p = get_property(an, l->label);
 875			if (p) {
 876				fprintf(stderr, "WARNING: label %s already"
 877					" exists in /%s", l->label,
 878					an->name);
 879				continue;
 880			}
 881
 882			/* insert it */
 883			p = build_property(l->label,
 884				data_copy_escape_string(node->fullpath,
 885						strlen(node->fullpath)),
 886				NULL);
 887			add_property(an, p);
 888		}
 889
 890		/* force allocation of a phandle for this node */
 891		if (allocph)
 892			(void)get_node_phandle(dt, node);
 893	}
 894
 895	for_each_child(node, c)
 896		generate_label_tree_internal(dti, an, c, allocph);
 897}
 898
 899static bool any_fixup_tree(struct dt_info *dti, struct node *node)
 900{
 901	struct node *c;
 902	struct property *prop;
 903	struct marker *m;
 904
 905	for_each_property(node, prop) {
 906		m = prop->val.markers;
 907		for_each_marker_of_type(m, REF_PHANDLE) {
 908			if (!get_node_by_ref(dti->dt, m->ref))
 909				return true;
 910		}
 911	}
 912
 913	for_each_child(node, c) {
 914		if (any_fixup_tree(dti, c))
 915			return true;
 916	}
 917
 918	return false;
 919}
 920
 921static void add_fixup_entry(struct dt_info *dti, struct node *fn,
 922			    struct node *node, struct property *prop,
 923			    struct marker *m)
 924{
 925	char *entry;
 926
 927	/* m->ref can only be a REF_PHANDLE, but check anyway */
 928	assert(m->type == REF_PHANDLE);
 929
 930	/* The format only permits fixups for references to label, not
 931	 * references to path */
 932	if (strchr(m->ref, '/'))
 933		die("Can't generate fixup for reference to path &{%s}\n",
 934		    m->ref);
 935
 936	/* there shouldn't be any ':' in the arguments */
 937	if (strchr(node->fullpath, ':') || strchr(prop->name, ':'))
 938		die("arguments should not contain ':'\n");
 939
 940	xasprintf(&entry, "%s:%s:%u",
 941			node->fullpath, prop->name, m->offset);
 942	append_to_property(fn, m->ref, entry, strlen(entry) + 1, TYPE_STRING);
 943
 944	free(entry);
 945}
 946
 947static void generate_fixups_tree_internal(struct dt_info *dti,
 948					  struct node *fn,
 949					  struct node *node)
 950{
 951	struct node *dt = dti->dt;
 952	struct node *c;
 953	struct property *prop;
 954	struct marker *m;
 955	struct node *refnode;
 956
 957	for_each_property(node, prop) {
 958		m = prop->val.markers;
 959		for_each_marker_of_type(m, REF_PHANDLE) {
 960			refnode = get_node_by_ref(dt, m->ref);
 961			if (!refnode)
 962				add_fixup_entry(dti, fn, node, prop, m);
 963		}
 964	}
 965
 966	for_each_child(node, c)
 967		generate_fixups_tree_internal(dti, fn, c);
 968}
 969
 970static bool any_local_fixup_tree(struct dt_info *dti, struct node *node)
 971{
 972	struct node *c;
 973	struct property *prop;
 974	struct marker *m;
 975
 976	for_each_property(node, prop) {
 977		m = prop->val.markers;
 978		for_each_marker_of_type(m, REF_PHANDLE) {
 979			if (get_node_by_ref(dti->dt, m->ref))
 980				return true;
 981		}
 982	}
 983
 984	for_each_child(node, c) {
 985		if (any_local_fixup_tree(dti, c))
 986			return true;
 987	}
 988
 989	return false;
 990}
 991
 992static void add_local_fixup_entry(struct dt_info *dti,
 993		struct node *lfn, struct node *node,
 994		struct property *prop, struct marker *m,
 995		struct node *refnode)
 996{
 997	struct node *wn, *nwn;	/* local fixup node, walk node, new */
 998	fdt32_t value_32;
 999	char **compp;
1000	int i, depth;
1001
1002	/* walk back retrieving depth */
1003	depth = 0;
1004	for (wn = node; wn; wn = wn->parent)
1005		depth++;
1006
1007	/* allocate name array */
1008	compp = xmalloc(sizeof(*compp) * depth);
1009
1010	/* store names in the array */
1011	for (wn = node, i = depth - 1; wn; wn = wn->parent, i--)
1012		compp[i] = wn->name;
1013
1014	/* walk the path components creating nodes if they don't exist */
1015	for (wn = lfn, i = 1; i < depth; i++, wn = nwn) {
1016		/* if no node exists, create it */
1017		nwn = get_subnode(wn, compp[i]);
1018		if (!nwn)
1019			nwn = build_and_name_child_node(wn, compp[i]);
1020	}
1021
1022	free(compp);
1023
1024	value_32 = cpu_to_fdt32(m->offset);
1025	append_to_property(wn, prop->name, &value_32, sizeof(value_32), TYPE_UINT32);
1026}
1027
1028static void generate_local_fixups_tree_internal(struct dt_info *dti,
1029						struct node *lfn,
1030						struct node *node)
1031{
1032	struct node *dt = dti->dt;
1033	struct node *c;
1034	struct property *prop;
1035	struct marker *m;
1036	struct node *refnode;
1037
1038	for_each_property(node, prop) {
1039		m = prop->val.markers;
1040		for_each_marker_of_type(m, REF_PHANDLE) {
1041			refnode = get_node_by_ref(dt, m->ref);
1042			if (refnode)
1043				add_local_fixup_entry(dti, lfn, node, prop, m, refnode);
1044		}
1045	}
1046
1047	for_each_child(node, c)
1048		generate_local_fixups_tree_internal(dti, lfn, c);
1049}
1050
1051void generate_label_tree(struct dt_info *dti, const char *name, bool allocph)
1052{
1053	if (!any_label_tree(dti, dti->dt))
1054		return;
1055	generate_label_tree_internal(dti, build_root_node(dti->dt, name),
1056				     dti->dt, allocph);
1057}
1058
1059void generate_fixups_tree(struct dt_info *dti, const char *name)
1060{
1061	if (!any_fixup_tree(dti, dti->dt))
1062		return;
1063	generate_fixups_tree_internal(dti, build_root_node(dti->dt, name),
1064				      dti->dt);
1065}
1066
1067void generate_local_fixups_tree(struct dt_info *dti, const char *name)
1068{
1069	if (!any_local_fixup_tree(dti, dti->dt))
1070		return;
1071	generate_local_fixups_tree_internal(dti, build_root_node(dti->dt, name),
1072					    dti->dt);
1073}