blob: 747d8bb86aa418111b172ef549fc7d2e9a6cc79b [file] [log] [blame]
Simon Glassc3c4c002015-06-23 15:38:27 -06001/*
2 * libfdt - Flat Device Tree manipulation
3 * Copyright (C) 2013 Google, Inc
4 * Written by Simon Glass <sjg@chromium.org>
5 * SPDX-License-Identifier: GPL-2.0+ BSD-2-Clause
6 */
7
8#include "libfdt_env.h"
9
10#ifndef USE_HOSTCC
11#include <fdt.h>
12#include <libfdt.h>
13#else
14#include "fdt_host.h"
15#endif
16
17#include "libfdt_internal.h"
18
19/**
20 * fdt_add_region() - Add a new region to our list
21 *
22 * The region is added if there is space, but in any case we increment the
23 * count. If permitted, and the new region overlaps the last one, we merge
24 * them.
25 *
26 * @info: State information
27 * @offset: Start offset of region
28 * @size: Size of region
29 */
30static int fdt_add_region(struct fdt_region_state *info, int offset, int size)
31{
32 struct fdt_region *reg;
33
34 reg = info->region ? &info->region[info->count - 1] : NULL;
35 if (info->can_merge && info->count &&
36 info->count <= info->max_regions &&
37 reg && offset <= reg->offset + reg->size) {
38 reg->size = offset + size - reg->offset;
39 } else if (info->count++ < info->max_regions) {
40 if (reg) {
41 reg++;
42 reg->offset = offset;
43 reg->size = size;
44 }
45 } else {
46 return -1;
47 }
48
49 return 0;
50}
51
52static int region_list_contains_offset(struct fdt_region_state *info,
53 const void *fdt, int target)
54{
55 struct fdt_region *reg;
56 int num;
57
58 target += fdt_off_dt_struct(fdt);
59 for (reg = info->region, num = 0; num < info->count; reg++, num++) {
60 if (target >= reg->offset && target < reg->offset + reg->size)
61 return 1;
62 }
63
64 return 0;
65}
66
67int fdt_add_alias_regions(const void *fdt, struct fdt_region *region, int count,
68 int max_regions, struct fdt_region_state *info)
69{
70 int base = fdt_off_dt_struct(fdt);
71 int node, node_end, offset;
72 int did_alias_header;
73
74 node = fdt_subnode_offset(fdt, 0, "aliases");
75 if (node < 0)
76 return -FDT_ERR_NOTFOUND;
77
78 /* The aliases node must come before the others */
79 node_end = fdt_next_subnode(fdt, node);
80 if (node_end <= 0)
81 return -FDT_ERR_BADLAYOUT;
82 node_end -= sizeof(fdt32_t);
83
84 did_alias_header = 0;
85 info->region = region;
86 info->count = count;
87 info->can_merge = 0;
88 info->max_regions = max_regions;
89
90 for (offset = fdt_first_property_offset(fdt, node);
91 offset >= 0;
92 offset = fdt_next_property_offset(fdt, offset)) {
93 const struct fdt_property *prop;
94 const char *name;
95 int target, next;
96
97 prop = fdt_get_property_by_offset(fdt, offset, NULL);
98 name = fdt_string(fdt, fdt32_to_cpu(prop->nameoff));
99 target = fdt_path_offset(fdt, name);
100 if (!region_list_contains_offset(info, fdt, target))
101 continue;
102 next = fdt_next_property_offset(fdt, offset);
103 if (next < 0)
Simon Glass9d8ac952015-10-17 19:41:15 -0600104 next = node_end;
Simon Glassc3c4c002015-06-23 15:38:27 -0600105
106 if (!did_alias_header) {
107 fdt_add_region(info, base + node, 12);
108 did_alias_header = 1;
109 }
110 fdt_add_region(info, base + offset, next - offset);
111 }
112
113 /* Add the 'end' tag */
114 if (did_alias_header)
115 fdt_add_region(info, base + node_end, sizeof(fdt32_t));
116
117 return info->count < max_regions ? info->count : -FDT_ERR_NOSPACE;
118}
119
120/**
121 * fdt_include_supernodes() - Include supernodes required by this node
122 *
123 * When we decided to include a node or property which is not at the top
124 * level, this function forces the inclusion of higher level nodes. For
125 * example, given this tree:
126 *
127 * / {
128 * testing {
129 * }
130 * }
131 *
132 * If we decide to include testing then we need the root node to have a valid
133 * tree. This function adds those regions.
134 *
135 * @info: State information
136 * @depth: Current stack depth
137 */
138static int fdt_include_supernodes(struct fdt_region_state *info, int depth)
139{
140 int base = fdt_off_dt_struct(info->fdt);
141 int start, stop_at;
142 int i;
143
144 /*
145 * Work down the stack looking for supernodes that we didn't include.
146 * The algortihm here is actually pretty simple, since we know that
147 * no previous subnode had to include these nodes, or if it did, we
148 * marked them as included (on the stack) already.
149 */
150 for (i = 0; i <= depth; i++) {
151 if (!info->stack[i].included) {
152 start = info->stack[i].offset;
153
154 /* Add the FDT_BEGIN_NODE tag of this supernode */
155 fdt_next_tag(info->fdt, start, &stop_at);
156 if (fdt_add_region(info, base + start, stop_at - start))
157 return -1;
158
159 /* Remember that this supernode is now included */
160 info->stack[i].included = 1;
161 info->can_merge = 1;
162 }
163
164 /* Force (later) generation of the FDT_END_NODE tag */
165 if (!info->stack[i].want)
166 info->stack[i].want = WANT_NODES_ONLY;
167 }
168
169 return 0;
170}
171
172enum {
173 FDT_DONE_NOTHING,
174 FDT_DONE_MEM_RSVMAP,
175 FDT_DONE_STRUCT,
176 FDT_DONE_END,
177 FDT_DONE_STRINGS,
178 FDT_DONE_ALL,
179};
180
181int fdt_first_region(const void *fdt,
182 int (*h_include)(void *priv, const void *fdt, int offset,
183 int type, const char *data, int size),
184 void *priv, struct fdt_region *region,
185 char *path, int path_len, int flags,
186 struct fdt_region_state *info)
187{
188 struct fdt_region_ptrs *p = &info->ptrs;
189
190 /* Set up our state */
191 info->fdt = fdt;
192 info->can_merge = 1;
193 info->max_regions = 1;
194 info->start = -1;
195 p->want = WANT_NOTHING;
196 p->end = path;
197 *p->end = '\0';
198 p->nextoffset = 0;
199 p->depth = -1;
200 p->done = FDT_DONE_NOTHING;
201
202 return fdt_next_region(fdt, h_include, priv, region,
203 path, path_len, flags, info);
204}
205
206/*
207 * Theory of operation
208 *
209 *
210 *
211
212Note: in this description 'included' means that a node (or other part of
213the tree) should be included in the region list, i.e. it will have a region
214which covers its part of the tree.
215
216This function maintains some state from the last time it is called. It
217checks the next part of the tree that it is supposed to look at
218(p.nextoffset) to see if that should be included or not. When it finds
219something to include, it sets info->start to its offset. This marks the
220start of the region we want to include.
221
222Once info->start is set to the start (i.e. not -1), we continue scanning
223until we find something that we don't want included. This will be the end
224of a region. At this point we can close off the region and add it to the
225list. So we do so, and reset info->start to -1.
226
227One complication here is that we want to merge regions. So when we come to
228add another region later, we may in fact merge it with the previous one if
229one ends where the other starts.
230
231The function fdt_add_region() will return -1 if it fails to add the region,
232because we already have a region ready to be returned, and the new one
233cannot be merged in with it. In this case, we must return the region we
234found, and wait for another call to this function. When it comes, we will
235repeat the processing of the tag and again try to add a region. This time it
236will succeed.
237
238The current state of the pointers (stack, offset, etc.) is maintained in
239a ptrs member. At the start of every loop iteration we make a copy of it.
240The copy is then updated as the tag is processed. Only if we get to the end
241of the loop iteration (and successfully call fdt_add_region() if we need
242to) can we commit the changes we have made to these pointers. For example,
243if we see an FDT_END_NODE tag we will decrement the depth value. But if we
244need to add a region for this tag (let's say because the previous tag is
245included and this FDT_END_NODE tag is not included) then we will only commit
246the result if we were able to add the region. That allows us to retry again
247next time.
248
249We keep track of a variable called 'want' which tells us what we want to
250include when there is no specific information provided by the h_include
251function for a particular property. This basically handles the inclusion of
252properties which are pulled in by virtue of the node they are in. So if you
253include a node, its properties are also included. In this case 'want' will
254be WANT_NODES_AND_PROPS. The FDT_REG_DIRECT_SUBNODES feature also makes use
255of 'want'. While we are inside the subnode, 'want' will be set to
256WANT_NODES_ONLY, so that only the subnode's FDT_BEGIN_NODE and FDT_END_NODE
257tags will be included, and properties will be skipped. If WANT_NOTHING is
258selected, then we will just rely on what the h_include() function tells us.
259
260Using 'want' we work out 'include', which tells us whether this current tag
261should be included or not. As you can imagine, if the value of 'include'
262changes, that means we are on a boundary between nodes to include and nodes
263to exclude. At this point we either close off a previous region and add it
264to the list, or mark the start of a new region.
265
266Apart from the nodes, we have mem_rsvmap, the FDT_END tag and the string
267list. Each of these dealt with as a whole (i.e. we create a region for each
268if it is to be included). For mem_rsvmap we don't allow it to merge with
269the first struct region. For the stringlist we don't allow it to merge with
270the last struct region (which contains at minimum the FDT_END tag).
271*/
272int fdt_next_region(const void *fdt,
273 int (*h_include)(void *priv, const void *fdt, int offset,
274 int type, const char *data, int size),
275 void *priv, struct fdt_region *region,
276 char *path, int path_len, int flags,
277 struct fdt_region_state *info)
278{
279 int base = fdt_off_dt_struct(fdt);
280 int last_node = 0;
281 const char *str;
282
283 info->region = region;
284 info->count = 0;
285 if (info->ptrs.done < FDT_DONE_MEM_RSVMAP &&
286 (flags & FDT_REG_ADD_MEM_RSVMAP)) {
287 /* Add the memory reserve map into its own region */
288 if (fdt_add_region(info, fdt_off_mem_rsvmap(fdt),
289 fdt_off_dt_struct(fdt) -
290 fdt_off_mem_rsvmap(fdt)))
291 return 0;
292 info->can_merge = 0; /* Don't allow merging with this */
293 info->ptrs.done = FDT_DONE_MEM_RSVMAP;
294 }
295
296 /*
297 * Work through the tags one by one, deciding whether each needs to
298 * be included or not. We set the variable 'include' to indicate our
299 * decision. 'want' is used to track what we want to include - it
300 * allows us to pick up all the properties (and/or subnode tags) of
301 * a node.
302 */
303 while (info->ptrs.done < FDT_DONE_STRUCT) {
304 const struct fdt_property *prop;
305 struct fdt_region_ptrs p;
306 const char *name;
307 int include = 0;
308 int stop_at = 0;
309 uint32_t tag;
310 int offset;
311 int val;
312 int len;
313
314 /*
315 * Make a copy of our pointers. If we make it to the end of
316 * this block then we will commit them back to info->ptrs.
317 * Otherwise we can try again from the same starting state
318 * next time we are called.
319 */
320 p = info->ptrs;
321
322 /*
323 * Find the tag, and the offset of the next one. If we need to
324 * stop including tags, then by default we stop *after*
325 * including the current tag
326 */
327 offset = p.nextoffset;
328 tag = fdt_next_tag(fdt, offset, &p.nextoffset);
329 stop_at = p.nextoffset;
330
331 switch (tag) {
332 case FDT_PROP:
333 stop_at = offset;
334 prop = fdt_get_property_by_offset(fdt, offset, NULL);
335 str = fdt_string(fdt, fdt32_to_cpu(prop->nameoff));
336 val = h_include(priv, fdt, last_node, FDT_IS_PROP, str,
337 strlen(str) + 1);
338 if (val == -1) {
339 include = p.want >= WANT_NODES_AND_PROPS;
340 } else {
341 include = val;
342 /*
343 * Make sure we include the } for this block.
344 * It might be more correct to have this done
345 * by the call to fdt_include_supernodes() in
346 * the case where it adds the node we are
347 * currently in, but this is equivalent.
348 */
349 if ((flags & FDT_REG_SUPERNODES) && val &&
350 !p.want)
351 p.want = WANT_NODES_ONLY;
352 }
353
354 /* Value grepping is not yet supported */
355 break;
356
357 case FDT_NOP:
358 include = p.want >= WANT_NODES_AND_PROPS;
359 stop_at = offset;
360 break;
361
362 case FDT_BEGIN_NODE:
363 last_node = offset;
364 p.depth++;
365 if (p.depth == FDT_MAX_DEPTH)
366 return -FDT_ERR_TOODEEP;
367 name = fdt_get_name(fdt, offset, &len);
368 if (p.end - path + 2 + len >= path_len)
369 return -FDT_ERR_NOSPACE;
370
371 /* Build the full path of this node */
372 if (p.end != path + 1)
373 *p.end++ = '/';
374 strcpy(p.end, name);
375 p.end += len;
376 info->stack[p.depth].want = p.want;
377 info->stack[p.depth].offset = offset;
378
379 /*
380 * If we are not intending to include this node unless
381 * it matches, make sure we stop *before* its tag.
382 */
383 if (p.want == WANT_NODES_ONLY ||
384 !(flags & (FDT_REG_DIRECT_SUBNODES |
385 FDT_REG_ALL_SUBNODES))) {
386 stop_at = offset;
387 p.want = WANT_NOTHING;
388 }
389 val = h_include(priv, fdt, offset, FDT_IS_NODE, path,
390 p.end - path + 1);
391
392 /* Include this if requested */
393 if (val) {
394 p.want = (flags & FDT_REG_ALL_SUBNODES) ?
395 WANT_ALL_NODES_AND_PROPS :
396 WANT_NODES_AND_PROPS;
397 }
398
399 /* If not requested, decay our 'p.want' value */
400 else if (p.want) {
401 if (p.want != WANT_ALL_NODES_AND_PROPS)
402 p.want--;
403
404 /* Not including this tag, so stop now */
405 } else {
406 stop_at = offset;
407 }
408
409 /*
410 * Decide whether to include this tag, and update our
411 * stack with the state for this node
412 */
413 include = p.want;
414 info->stack[p.depth].included = include;
415 break;
416
417 case FDT_END_NODE:
418 include = p.want;
419 if (p.depth < 0)
420 return -FDT_ERR_BADSTRUCTURE;
421
422 /*
423 * If we don't want this node, stop right away, unless
424 * we are including subnodes
425 */
426 if (!p.want && !(flags & FDT_REG_DIRECT_SUBNODES))
427 stop_at = offset;
428 p.want = info->stack[p.depth].want;
429 p.depth--;
430 while (p.end > path && *--p.end != '/')
431 ;
432 *p.end = '\0';
433 break;
434
435 case FDT_END:
436 /* We always include the end tag */
437 include = 1;
438 p.done = FDT_DONE_STRUCT;
439 break;
440 }
441
442 /* If this tag is to be included, mark it as region start */
443 if (include && info->start == -1) {
444 /* Include any supernodes required by this one */
445 if (flags & FDT_REG_SUPERNODES) {
446 if (fdt_include_supernodes(info, p.depth))
447 return 0;
448 }
449 info->start = offset;
450 }
451
452 /*
453 * If this tag is not to be included, finish up the current
454 * region.
455 */
456 if (!include && info->start != -1) {
457 if (fdt_add_region(info, base + info->start,
458 stop_at - info->start))
459 return 0;
460 info->start = -1;
461 info->can_merge = 1;
462 }
463
464 /* If we have made it this far, we can commit our pointers */
465 info->ptrs = p;
466 }
467
468 /* Add a region for the END tag and a separate one for string table */
469 if (info->ptrs.done < FDT_DONE_END) {
470 if (info->ptrs.nextoffset != fdt_size_dt_struct(fdt))
471 return -FDT_ERR_BADSTRUCTURE;
472
473 if (fdt_add_region(info, base + info->start,
474 info->ptrs.nextoffset - info->start))
475 return 0;
476 info->ptrs.done++;
477 }
478 if (info->ptrs.done < FDT_DONE_STRINGS) {
479 if (flags & FDT_REG_ADD_STRING_TAB) {
480 info->can_merge = 0;
481 if (fdt_off_dt_strings(fdt) <
482 base + info->ptrs.nextoffset)
483 return -FDT_ERR_BADLAYOUT;
484 if (fdt_add_region(info, fdt_off_dt_strings(fdt),
485 fdt_size_dt_strings(fdt)))
486 return 0;
487 }
488 info->ptrs.done++;
489 }
490
491 return info->count > 0 ? 0 : -FDT_ERR_NOTFOUND;
492}