1 // SPDX-License-Identifier: GPL-2.0+ OR BSD-2-Clause
2 /*
3 * libfdt - Flat Device Tree manipulation
4 * Copyright (C) 2013 Google, Inc
5 * Written by Simon Glass <sjg@chromium.org>
6 */
7
8 #include <fdt_support.h>
9 #include <linux/libfdt_env.h>
10 #include <fdt_region.h>
11
12 #ifndef USE_HOSTCC
13 #include <fdt.h>
14 #include <linux/libfdt.h>
15 #else
16 #include "fdt_host.h"
17 #endif
18
19 #define FDT_MAX_DEPTH 32
20
str_in_list(const char * str,char * const list[],int count)21 static int str_in_list(const char *str, char * const list[], int count)
22 {
23 int i;
24
25 for (i = 0; i < count; i++)
26 if (!strcmp(list[i], str))
27 return 1;
28
29 return 0;
30 }
31
fdt_find_regions(const void * fdt,char * const inc[],int inc_count,char * const exc_prop[],int exc_prop_count,struct fdt_region region[],int max_regions,char * path,int path_len,int add_string_tab)32 int fdt_find_regions(const void *fdt, char * const inc[], int inc_count,
33 char * const exc_prop[], int exc_prop_count,
34 struct fdt_region region[], int max_regions,
35 char *path, int path_len, int add_string_tab)
36 {
37 int stack[FDT_MAX_DEPTH] = { 0 };
38 char *end;
39 int nextoffset = 0;
40 uint32_t tag;
41 int count = 0;
42 int start = -1;
43 int depth = -1;
44 int want = 0;
45 int base = fdt_off_dt_struct(fdt);
46 bool expect_end = false;
47
48 end = path;
49 *end = '\0';
50 do {
51 const struct fdt_property *prop;
52 const char *name;
53 const char *str;
54 int include = 0;
55 int stop_at = 0;
56 int offset;
57 int len;
58
59 offset = nextoffset;
60 tag = fdt_next_tag(fdt, offset, &nextoffset);
61 stop_at = nextoffset;
62
63 /* If we see two root nodes, something is wrong */
64 if (expect_end && tag != FDT_END)
65 return -FDT_ERR_BADLAYOUT;
66
67 switch (tag) {
68 case FDT_PROP:
69 include = want >= 2;
70 stop_at = offset;
71 prop = fdt_get_property_by_offset(fdt, offset, NULL);
72 str = fdt_string(fdt, fdt32_to_cpu(prop->nameoff));
73 if (!str)
74 return -FDT_ERR_BADSTRUCTURE;
75 if (str_in_list(str, exc_prop, exc_prop_count))
76 include = 0;
77 break;
78
79 case FDT_NOP:
80 include = want >= 2;
81 stop_at = offset;
82 break;
83
84 case FDT_BEGIN_NODE:
85 depth++;
86 if (depth == FDT_MAX_DEPTH)
87 return -FDT_ERR_BADSTRUCTURE;
88 name = fdt_get_name(fdt, offset, &len);
89
90 /* The root node must have an empty name */
91 if (!depth && *name)
92 return -FDT_ERR_BADLAYOUT;
93 if (end - path + 2 + len >= path_len)
94 return -FDT_ERR_NOSPACE;
95 if (end != path + 1)
96 *end++ = '/';
97 strcpy(end, name);
98 end += len;
99 stack[depth] = want;
100 if (want == 1)
101 stop_at = offset;
102 if (str_in_list(path, inc, inc_count))
103 want = 2;
104 else if (want)
105 want--;
106 else
107 stop_at = offset;
108 include = want;
109 break;
110
111 case FDT_END_NODE:
112 /* Depth must never go below -1 */
113 if (depth < 0)
114 return -FDT_ERR_BADSTRUCTURE;
115 include = want;
116 want = stack[depth--];
117 while (end > path && *--end != '/')
118 ;
119 *end = '\0';
120 if (depth == -1)
121 expect_end = true;
122 break;
123
124 case FDT_END:
125 include = 1;
126 break;
127 }
128
129 if (include && start == -1) {
130 /* Should we merge with previous? */
131 if (count && count <= max_regions &&
132 offset == region[count - 1].offset +
133 region[count - 1].size - base)
134 start = region[--count].offset - base;
135 else
136 start = offset;
137 }
138
139 if (!include && start != -1) {
140 if (count < max_regions) {
141 region[count].offset = base + start;
142 region[count].size = stop_at - start;
143 }
144 count++;
145 start = -1;
146 }
147 } while (tag != FDT_END);
148
149 if (nextoffset != fdt_size_dt_struct(fdt))
150 return -FDT_ERR_BADLAYOUT;
151
152 /* Add a region for the END tag and the string table */
153 if (count < max_regions) {
154 region[count].offset = base + start;
155 region[count].size = nextoffset - start;
156 if (add_string_tab)
157 region[count].size += fdt_size_dt_strings(fdt);
158 }
159 count++;
160
161 return count;
162 }
163
164 /**
165 * fdt_add_region() - Add a new region to our list
166 * @info: State information
167 * @offset: Start offset of region
168 * @size: Size of region
169 *
170 * The region is added if there is space, but in any case we increment the
171 * count. If permitted, and the new region overlaps the last one, we merge
172 * them.
173 */
fdt_add_region(struct fdt_region_state * info,int offset,int size)174 static int fdt_add_region(struct fdt_region_state *info, int offset, int size)
175 {
176 struct fdt_region *reg;
177
178 reg = info->region ? &info->region[info->count - 1] : NULL;
179 if (info->can_merge && info->count &&
180 info->count <= info->max_regions &&
181 reg && offset <= reg->offset + reg->size) {
182 reg->size = offset + size - reg->offset;
183 } else if (info->count++ < info->max_regions) {
184 if (reg) {
185 reg++;
186 reg->offset = offset;
187 reg->size = size;
188 if (!(offset - fdt_off_dt_struct(info->fdt)))
189 info->have_node = true;
190 }
191 } else {
192 return -1;
193 }
194
195 return 0;
196 }
197
region_list_contains_offset(struct fdt_region_state * info,const void * fdt,int target)198 static int region_list_contains_offset(struct fdt_region_state *info,
199 const void *fdt, int target)
200 {
201 struct fdt_region *reg;
202 int num;
203
204 target += fdt_off_dt_struct(fdt);
205 for (reg = info->region, num = 0; num < info->count; reg++, num++) {
206 if (target >= reg->offset && target < reg->offset + reg->size)
207 return 1;
208 }
209
210 return 0;
211 }
212
213 /**
214 * fdt_add_alias_regions() - Add regions covering the aliases that we want
215 *
216 * The /aliases node is not automatically included by fdtgrep unless the
217 * command-line arguments cause to be included (or not excluded). However
218 * aliases are special in that we generally want to include those which
219 * reference a node that fdtgrep includes.
220 *
221 * In fact we want to include only aliases for those nodes still included in
222 * the fdt, and drop the other aliases since they point to nodes that will not
223 * be present.
224 *
225 * This function scans the aliases and adds regions for those which we want
226 * to keep.
227 *
228 * @fdt: Device tree to scan
229 * @region: List of regions
230 * @count: Number of regions in the list so far (i.e. starting point for this
231 * function)
232 * @max_regions: Maximum number of regions in @region list
233 * @info: Place to put the region state
234 * Return: number of regions after processing, or -FDT_ERR_NOSPACE if we did
235 * not have enough room in the regions table for the regions we wanted to add.
236 */
fdt_add_alias_regions(const void * fdt,struct fdt_region * region,int count,int max_regions,struct fdt_region_state * info)237 int fdt_add_alias_regions(const void *fdt, struct fdt_region *region, int count,
238 int max_regions, struct fdt_region_state *info)
239 {
240 int base = fdt_off_dt_struct(fdt);
241 int node, node_end, offset;
242 int did_alias_header;
243
244 node = fdt_subnode_offset(fdt, 0, "aliases");
245 if (node < 0)
246 return -FDT_ERR_NOTFOUND;
247
248 /*
249 * Find the next node so that we know where the /aliases node ends. We
250 * need special handling if /aliases is the last node.
251 */
252 node_end = fdt_next_subnode(fdt, node);
253 if (node_end == -FDT_ERR_NOTFOUND)
254 /* Move back to the FDT_END_NODE tag of '/' */
255 node_end = fdt_size_dt_struct(fdt) - sizeof(fdt32_t) * 2;
256 else if (node_end < 0) /* other error */
257 return node_end;
258 node_end -= sizeof(fdt32_t); /* Move to FDT_END_NODE tag of /aliases */
259
260 did_alias_header = 0;
261 info->region = region;
262 info->count = count;
263 info->can_merge = 0;
264 info->max_regions = max_regions;
265
266 for (offset = fdt_first_property_offset(fdt, node);
267 offset >= 0;
268 offset = fdt_next_property_offset(fdt, offset)) {
269 const struct fdt_property *prop;
270 const char *name;
271 int target, next;
272
273 prop = fdt_get_property_by_offset(fdt, offset, NULL);
274 name = fdt_string(fdt, fdt32_to_cpu(prop->nameoff));
275 target = fdt_path_offset(fdt, name);
276 if (!region_list_contains_offset(info, fdt, target))
277 continue;
278 next = fdt_next_property_offset(fdt, offset);
279 if (next < 0)
280 next = node_end;
281
282 if (!did_alias_header) {
283 fdt_add_region(info, base + node, 12);
284 did_alias_header = 1;
285 }
286 fdt_add_region(info, base + offset, next - offset);
287 }
288
289 /* Add the FDT_END_NODE tag */
290 if (did_alias_header)
291 fdt_add_region(info, base + node_end, sizeof(fdt32_t));
292
293 return info->count < max_regions ? info->count : -FDT_ERR_NOSPACE;
294 }
295
296 /**
297 * fdt_include_supernodes() - Include supernodes required by this node
298 * @info: State information
299 * @depth: Current stack depth
300 *
301 * When we decided to include a node or property which is not at the top
302 * level, this function forces the inclusion of higher level nodes. For
303 * example, given this tree:
304 *
305 * / {
306 * testing {
307 * }
308 * }
309 *
310 * If we decide to include testing then we need the root node to have a valid
311 * tree. This function adds those regions.
312 */
fdt_include_supernodes(struct fdt_region_state * info,int depth)313 static int fdt_include_supernodes(struct fdt_region_state *info, int depth)
314 {
315 int base = fdt_off_dt_struct(info->fdt);
316 int start, stop_at;
317 int i;
318
319 /*
320 * Work down the stack looking for supernodes that we didn't include.
321 * The algortihm here is actually pretty simple, since we know that
322 * no previous subnode had to include these nodes, or if it did, we
323 * marked them as included (on the stack) already.
324 */
325 for (i = 0; i <= depth; i++) {
326 if (!info->stack[i].included) {
327 start = info->stack[i].offset;
328
329 /* Add the FDT_BEGIN_NODE tag of this supernode */
330 fdt_next_tag(info->fdt, start, &stop_at);
331 if (fdt_add_region(info, base + start, stop_at - start))
332 return -1;
333
334 /* Remember that this supernode is now included */
335 info->stack[i].included = 1;
336 info->can_merge = 1;
337 }
338
339 /* Force (later) generation of the FDT_END_NODE tag */
340 if (!info->stack[i].want)
341 info->stack[i].want = WANT_NODES_ONLY;
342 }
343
344 return 0;
345 }
346
347 /*
348 * Tracks the progress through the device tree. Everything fdt_next_region() is
349 * called it picks up at the same state as last time, looks at info->start and
350 * decides what region to add next
351 */
352 enum {
353 FDT_DONE_NOTHING, /* Starting */
354 FDT_DONE_MEM_RSVMAP, /* Completed mem_rsvmap region */
355 FDT_DONE_STRUCT, /* Completed struct region */
356 FDT_DONE_EMPTY, /* Completed checking for empty struct region */
357 FDT_DONE_END, /* Completed the FDT_END tag */
358 FDT_DONE_STRINGS, /* Completed the strings */
359 FDT_DONE_ALL, /* All done */
360 };
361
fdt_first_region(const void * fdt,int (* h_include)(void * priv,const void * fdt,int offset,int type,const char * data,int size),void * priv,struct fdt_region * region,char * path,int path_len,int flags,struct fdt_region_state * info)362 int fdt_first_region(const void *fdt,
363 int (*h_include)(void *priv, const void *fdt, int offset,
364 int type, const char *data, int size),
365 void *priv, struct fdt_region *region,
366 char *path, int path_len, int flags,
367 struct fdt_region_state *info)
368 {
369 struct fdt_region_ptrs *p = &info->ptrs;
370
371 /* Set up our state */
372 info->fdt = fdt;
373 info->can_merge = 1;
374 info->max_regions = 1;
375 info->start = -1;
376 info->have_node = false;
377 p->want = WANT_NOTHING;
378 p->end = path;
379 *p->end = '\0';
380 p->nextoffset = 0;
381 p->depth = -1;
382 p->done = FDT_DONE_NOTHING;
383
384 return fdt_next_region(fdt, h_include, priv, region,
385 path, path_len, flags, info);
386 }
387
388 /***********************************************************************
389 *
390 * Theory of operation
391 *
392 * Note: in this description 'included' means that a node (or other part
393 * of the tree) should be included in the region list, i.e. it will have
394 * a region which covers its part of the tree.
395 *
396 * This function maintains some state from the last time it is called.
397 * It checks the next part of the tree that it is supposed to look at
398 * (p.nextoffset) to see if that should be included or not. When it
399 * finds something to include, it sets info->start to its offset. This
400 * marks the start of the region we want to include.
401 *
402 * Once info->start is set to the start (i.e. not -1), we continue
403 * scanning until we find something that we don't want included. This
404 * will be the end of a region. At this point we can close off the
405 * region and add it to the list. So we do so, and reset info->start
406 * to -1.
407 *
408 * One complication here is that we want to merge regions. So when we
409 * come to add another region later, we may in fact merge it with the
410 * previous one if one ends where the other starts.
411 *
412 * The function fdt_add_region() will return -1 if it fails to add the
413 * region, because we already have a region ready to be returned, and
414 * the new one cannot be merged in with it. In this case, we must return
415 * the region we found, and wait for another call to this function.
416 * When it comes, we will repeat the processing of the tag and again
417 * try to add a region. This time it will succeed.
418 *
419 * The current state of the pointers (stack, offset, etc.) is maintained
420 * in a ptrs member. At the start of every loop iteration we make a copy
421 * of it. The copy is then updated as the tag is processed. Only if we
422 * get to the end of the loop iteration (and successfully call
423 * fdt_add_region() if we need to) can we commit the changes we have
424 * made to these pointers. For example, if we see an FDT_END_NODE tag,
425 * we will decrement the depth value. But if we need to add a region
426 * for this tag (let's say because the previous tag is included and this
427 * FDT_END_NODE tag is not included) then we will only commit the result
428 * if we were able to add the region. That allows us to retry again next
429 * time.
430 *
431 * We keep track of a variable called 'want' which tells us what we want
432 * to include when there is no specific information provided by the
433 * h_include function for a particular property. This basically handles
434 * the inclusion of properties which are pulled in by virtue of the node
435 * they are in. So if you include a node, its properties are also
436 * included. In this case 'want' will be WANT_NODES_AND_PROPS. The
437 * FDT_REG_DIRECT_SUBNODES feature also makes use of 'want'. While we
438 * are inside the subnode, 'want' will be set to WANT_NODES_ONLY, so
439 * that only the subnode's FDT_BEGIN_NODE and FDT_END_NODE tags will be
440 * included, and properties will be skipped. If WANT_NOTHING is
441 * selected, then we will just rely on what the h_include() function
442 * tells us.
443 *
444 * Using 'want' we work out 'include', which tells us whether this
445 * current tag should be included or not. As you can imagine, if the
446 * value of 'include' changes, that means we are on a boundary between
447 * nodes to include and nodes to exclude. At this point we either close
448 * off a previous region and add it to the list, or mark the start of a
449 * new region.
450 *
451 * Apart from the nodes, we have mem_rsvmap, the FDT_END tag and the
452 * string list. Each of these dealt with as a whole (i.e. we create a
453 * region for each if it is to be included). For mem_rsvmap we don't
454 * allow it to merge with the first struct region. For the stringlist,
455 * we don't allow it to merge with the last struct region (which
456 * contains at minimum the FDT_END tag).
457 *
458 *********************************************************************/
459
fdt_next_region(const void * fdt,int (* h_include)(void * priv,const void * fdt,int offset,int type,const char * data,int size),void * priv,struct fdt_region * region,char * path,int path_len,int flags,struct fdt_region_state * info)460 int fdt_next_region(const void *fdt,
461 int (*h_include)(void *priv, const void *fdt, int offset,
462 int type, const char *data, int size),
463 void *priv, struct fdt_region *region,
464 char *path, int path_len, int flags,
465 struct fdt_region_state *info)
466 {
467 int base = fdt_off_dt_struct(fdt);
468 int last_node = 0;
469 const char *str;
470
471 info->region = region;
472 info->count = 0;
473 if (info->ptrs.done < FDT_DONE_MEM_RSVMAP &&
474 (flags & FDT_REG_ADD_MEM_RSVMAP)) {
475 /* Add the memory reserve map into its own region */
476 if (fdt_add_region(info, fdt_off_mem_rsvmap(fdt),
477 fdt_off_dt_struct(fdt) -
478 fdt_off_mem_rsvmap(fdt)))
479 return 0;
480 info->can_merge = 0; /* Don't allow merging with this */
481 info->ptrs.done = FDT_DONE_MEM_RSVMAP;
482 }
483
484 /*
485 * Work through the tags one by one, deciding whether each needs to
486 * be included or not. We set the variable 'include' to indicate our
487 * decision. 'want' is used to track what we want to include - it
488 * allows us to pick up all the properties (and/or subnode tags) of
489 * a node.
490 */
491 while (info->ptrs.done < FDT_DONE_STRUCT) {
492 const struct fdt_property *prop;
493 struct fdt_region_ptrs p;
494 const char *name;
495 int include = 0;
496 int stop_at = 0;
497 uint32_t tag;
498 int offset;
499 int val;
500 int len;
501
502 /*
503 * Make a copy of our pointers. If we make it to the end of
504 * this block then we will commit them back to info->ptrs.
505 * Otherwise we can try again from the same starting state
506 * next time we are called.
507 */
508 p = info->ptrs;
509
510 /*
511 * Find the tag, and the offset of the next one. If we need to
512 * stop including tags, then by default we stop *after*
513 * including the current tag
514 */
515 offset = p.nextoffset;
516 tag = fdt_next_tag(fdt, offset, &p.nextoffset);
517 stop_at = p.nextoffset;
518
519 switch (tag) {
520 case FDT_PROP:
521 stop_at = offset;
522 prop = fdt_get_property_by_offset(fdt, offset, NULL);
523 str = fdt_string(fdt, fdt32_to_cpu(prop->nameoff));
524 val = h_include(priv, fdt, last_node, FDT_IS_PROP, str,
525 strlen(str) + 1);
526 if (val == -1) {
527 include = p.want >= WANT_NODES_AND_PROPS;
528 } else {
529 include = val;
530 /*
531 * Make sure we include the } for this block.
532 * It might be more correct to have this done
533 * by the call to fdt_include_supernodes() in
534 * the case where it adds the node we are
535 * currently in, but this is equivalent.
536 */
537 if ((flags & FDT_REG_SUPERNODES) && val &&
538 !p.want)
539 p.want = WANT_NODES_ONLY;
540 }
541
542 /* Value grepping is not yet supported */
543 break;
544
545 case FDT_NOP:
546 include = p.want >= WANT_NODES_AND_PROPS;
547 stop_at = offset;
548 break;
549
550 case FDT_BEGIN_NODE:
551 last_node = offset;
552 p.depth++;
553 if (p.depth == FDT_MAX_DEPTH)
554 return -FDT_ERR_BADSTRUCTURE;
555 name = fdt_get_name(fdt, offset, &len);
556 if (p.end - path + 2 + len >= path_len)
557 return -FDT_ERR_NOSPACE;
558
559 /* Build the full path of this node */
560 if (p.end != path + 1)
561 *p.end++ = '/';
562 strcpy(p.end, name);
563 p.end += len;
564 info->stack[p.depth].want = p.want;
565 info->stack[p.depth].offset = offset;
566
567 /*
568 * If we are not intending to include this node unless
569 * it matches, make sure we stop *before* its tag.
570 */
571 if (p.want == WANT_NODES_ONLY ||
572 !(flags & (FDT_REG_DIRECT_SUBNODES |
573 FDT_REG_ALL_SUBNODES))) {
574 stop_at = offset;
575 p.want = WANT_NOTHING;
576 }
577 val = h_include(priv, fdt, offset, FDT_IS_NODE, path,
578 p.end - path + 1);
579
580 /* Include this if requested */
581 if (val) {
582 p.want = (flags & FDT_REG_ALL_SUBNODES) ?
583 WANT_ALL_NODES_AND_PROPS :
584 WANT_NODES_AND_PROPS;
585 }
586
587 /* If not requested, decay our 'p.want' value */
588 else if (p.want) {
589 if (p.want != WANT_ALL_NODES_AND_PROPS)
590 p.want--;
591
592 /* Not including this tag, so stop now */
593 } else {
594 stop_at = offset;
595 }
596
597 /*
598 * Decide whether to include this tag, and update our
599 * stack with the state for this node
600 */
601 include = p.want;
602 info->stack[p.depth].included = include;
603 break;
604
605 case FDT_END_NODE:
606 include = p.want;
607 if (p.depth < 0)
608 return -FDT_ERR_BADSTRUCTURE;
609
610 /*
611 * If we don't want this node, stop right away, unless
612 * we are including subnodes
613 */
614 if (!p.want && !(flags & FDT_REG_DIRECT_SUBNODES))
615 stop_at = offset;
616 p.want = info->stack[p.depth].want;
617 p.depth--;
618 while (p.end > path && *--p.end != '/')
619 ;
620 *p.end = '\0';
621 break;
622
623 case FDT_END:
624 /* We always include the end tag */
625 include = 1;
626 p.done = FDT_DONE_STRUCT;
627 break;
628 }
629
630 /* If this tag is to be included, mark it as region start */
631 if (include && info->start == -1) {
632 /* Include any supernodes required by this one */
633 if (flags & FDT_REG_SUPERNODES) {
634 if (fdt_include_supernodes(info, p.depth))
635 return 0;
636 }
637 info->start = offset;
638 }
639
640 /*
641 * If this tag is not to be included, finish up the current
642 * region.
643 */
644 if (!include && info->start != -1) {
645 if (!info->start)
646 info->have_node = true;
647 if (fdt_add_region(info, base + info->start,
648 stop_at - info->start))
649 return 0;
650 info->start = -1;
651 info->can_merge = 1;
652 }
653
654 /* If we have made it this far, we can commit our pointers */
655 info->ptrs = p;
656 }
657
658 if (info->ptrs.done < FDT_DONE_EMPTY) {
659 /*
660 * Handle a special case where no nodes have been written. Write
661 * the first { so we have at least something, since
662 * FDT_REG_SUPERNODES means that a valid tree is required. A
663 * tree with no nodes is not valid
664 */
665 if ((flags & FDT_REG_SUPERNODES) && !info->have_node &&
666 info->start) {
667 /* Output the FDT_BEGIN_NODE and the empty name */
668 if (fdt_add_region(info, base, 8))
669 return 0;
670 }
671 info->ptrs.done++;
672 }
673
674 /* Add a region for the END tag and a separate one for string table */
675 if (info->ptrs.done < FDT_DONE_END) {
676 if (info->ptrs.nextoffset != fdt_size_dt_struct(fdt))
677 return -FDT_ERR_BADSTRUCTURE;
678
679 /* Output the } before the end tag to finish it off */
680 if (info->start == fdt_size_dt_struct(fdt) - 4)
681 info->start -= 4;
682
683 if (fdt_add_region(info, base + info->start,
684 info->ptrs.nextoffset - info->start))
685 return 0;
686 info->ptrs.done++;
687 }
688 if (info->ptrs.done < FDT_DONE_STRINGS) {
689 if (flags & FDT_REG_ADD_STRING_TAB) {
690 info->can_merge = 0;
691 if (fdt_off_dt_strings(fdt) <
692 base + info->ptrs.nextoffset)
693 return -FDT_ERR_BADLAYOUT;
694 if (fdt_add_region(info, fdt_off_dt_strings(fdt),
695 fdt_size_dt_strings(fdt)))
696 return 0;
697 }
698 info->ptrs.done++;
699 }
700
701 return info->count > 0 ? 0 : -FDT_ERR_NOTFOUND;
702 }
703