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
8 #include "libfdt_env.h"
17 #include "libfdt_internal.h"
20 * fdt_add_region() - Add a new region to our list
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
26 * @info: State information
27 * @offset: Start offset of region
28 * @size: Size of region
30 static int fdt_add_region(struct fdt_region_state *info, int offset, int size)
32 struct fdt_region *reg;
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) {
52 static int region_list_contains_offset(struct fdt_region_state *info,
53 const void *fdt, int target)
55 struct fdt_region *reg;
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)
67 int fdt_add_alias_regions(const void *fdt, struct fdt_region *region, int count,
68 int max_regions, struct fdt_region_state *info)
70 int base = fdt_off_dt_struct(fdt);
71 int node, node_end, offset;
74 node = fdt_subnode_offset(fdt, 0, "aliases");
76 return -FDT_ERR_NOTFOUND;
78 /* The aliases node must come before the others */
79 node_end = fdt_next_subnode(fdt, node);
81 return -FDT_ERR_BADLAYOUT;
82 node_end -= sizeof(fdt32_t);
85 info->region = region;
88 info->max_regions = max_regions;
90 for (offset = fdt_first_property_offset(fdt, node);
92 offset = fdt_next_property_offset(fdt, offset)) {
93 const struct fdt_property *prop;
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))
102 next = fdt_next_property_offset(fdt, offset);
104 next = node_end - sizeof(fdt32_t);
106 if (!did_alias_header) {
107 fdt_add_region(info, base + node, 12);
108 did_alias_header = 1;
110 fdt_add_region(info, base + offset, next - offset);
113 /* Add the 'end' tag */
114 if (did_alias_header)
115 fdt_add_region(info, base + node_end, sizeof(fdt32_t));
117 return info->count < max_regions ? info->count : -FDT_ERR_NOSPACE;
121 * fdt_include_supernodes() - Include supernodes required by this node
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:
132 * If we decide to include testing then we need the root node to have a valid
133 * tree. This function adds those regions.
135 * @info: State information
136 * @depth: Current stack depth
138 static int fdt_include_supernodes(struct fdt_region_state *info, int depth)
140 int base = fdt_off_dt_struct(info->fdt);
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.
150 for (i = 0; i <= depth; i++) {
151 if (!info->stack[i].included) {
152 start = info->stack[i].offset;
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))
159 /* Remember that this supernode is now included */
160 info->stack[i].included = 1;
164 /* Force (later) generation of the FDT_END_NODE tag */
165 if (!info->stack[i].want)
166 info->stack[i].want = WANT_NODES_ONLY;
181 int 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)
188 struct fdt_region_ptrs *p = &info->ptrs;
190 /* Set up our state */
193 info->max_regions = 1;
195 p->want = WANT_NOTHING;
200 p->done = FDT_DONE_NOTHING;
202 return fdt_next_region(fdt, h_include, priv, region,
203 path, path_len, flags, info);
207 * Theory of operation
212 Note: in this description 'included' means that a node (or other part of
213 the tree) should be included in the region list, i.e. it will have a region
214 which covers its part of the tree.
216 This function maintains some state from the last time it is called. It
217 checks 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
219 something to include, it sets info->start to its offset. This marks the
220 start of the region we want to include.
222 Once info->start is set to the start (i.e. not -1), we continue scanning
223 until we find something that we don't want included. This will be the end
224 of a region. At this point we can close off the region and add it to the
225 list. So we do so, and reset info->start to -1.
227 One complication here is that we want to merge regions. So when we come to
228 add another region later, we may in fact merge it with the previous one if
229 one ends where the other starts.
231 The function fdt_add_region() will return -1 if it fails to add the region,
232 because we already have a region ready to be returned, and the new one
233 cannot be merged in with it. In this case, we must return the region we
234 found, and wait for another call to this function. When it comes, we will
235 repeat the processing of the tag and again try to add a region. This time it
238 The current state of the pointers (stack, offset, etc.) is maintained in
239 a ptrs member. At the start of every loop iteration we make a copy of it.
240 The copy is then updated as the tag is processed. Only if we get to the end
241 of the loop iteration (and successfully call fdt_add_region() if we need
242 to) can we commit the changes we have made to these pointers. For example,
243 if we see an FDT_END_NODE tag we will decrement the depth value. But if we
244 need to add a region for this tag (let's say because the previous tag is
245 included and this FDT_END_NODE tag is not included) then we will only commit
246 the result if we were able to add the region. That allows us to retry again
249 We keep track of a variable called 'want' which tells us what we want to
250 include when there is no specific information provided by the h_include
251 function for a particular property. This basically handles the inclusion of
252 properties which are pulled in by virtue of the node they are in. So if you
253 include a node, its properties are also included. In this case 'want' will
254 be WANT_NODES_AND_PROPS. The FDT_REG_DIRECT_SUBNODES feature also makes use
255 of 'want'. While we are inside the subnode, 'want' will be set to
256 WANT_NODES_ONLY, so that only the subnode's FDT_BEGIN_NODE and FDT_END_NODE
257 tags will be included, and properties will be skipped. If WANT_NOTHING is
258 selected, then we will just rely on what the h_include() function tells us.
260 Using 'want' we work out 'include', which tells us whether this current tag
261 should be included or not. As you can imagine, if the value of 'include'
262 changes, that means we are on a boundary between nodes to include and nodes
263 to exclude. At this point we either close off a previous region and add it
264 to the list, or mark the start of a new region.
266 Apart from the nodes, we have mem_rsvmap, the FDT_END tag and the string
267 list. Each of these dealt with as a whole (i.e. we create a region for each
268 if it is to be included). For mem_rsvmap we don't allow it to merge with
269 the first struct region. For the stringlist we don't allow it to merge with
270 the last struct region (which contains at minimum the FDT_END tag).
272 int 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)
279 int base = fdt_off_dt_struct(fdt);
283 info->region = region;
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)))
292 info->can_merge = 0; /* Don't allow merging with this */
293 info->ptrs.done = FDT_DONE_MEM_RSVMAP;
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
303 while (info->ptrs.done < FDT_DONE_STRUCT) {
304 const struct fdt_property *prop;
305 struct fdt_region_ptrs p;
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.
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
327 offset = p.nextoffset;
328 tag = fdt_next_tag(fdt, offset, &p.nextoffset);
329 stop_at = p.nextoffset;
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,
339 include = p.want >= WANT_NODES_AND_PROPS;
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.
349 if ((flags & FDT_REG_SUPERNODES) && val &&
351 p.want = WANT_NODES_ONLY;
354 /* Value grepping is not yet supported */
358 include = p.want >= WANT_NODES_AND_PROPS;
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;
371 /* Build the full path of this node */
372 if (p.end != path + 1)
376 info->stack[p.depth].want = p.want;
377 info->stack[p.depth].offset = offset;
380 * If we are not intending to include this node unless
381 * it matches, make sure we stop *before* its tag.
383 if (p.want == WANT_NODES_ONLY ||
384 !(flags & (FDT_REG_DIRECT_SUBNODES |
385 FDT_REG_ALL_SUBNODES))) {
387 p.want = WANT_NOTHING;
389 val = h_include(priv, fdt, offset, FDT_IS_NODE, path,
392 /* Include this if requested */
394 p.want = (flags & FDT_REG_ALL_SUBNODES) ?
395 WANT_ALL_NODES_AND_PROPS :
396 WANT_NODES_AND_PROPS;
399 /* If not requested, decay our 'p.want' value */
401 if (p.want != WANT_ALL_NODES_AND_PROPS)
404 /* Not including this tag, so stop now */
410 * Decide whether to include this tag, and update our
411 * stack with the state for this node
414 info->stack[p.depth].included = include;
420 return -FDT_ERR_BADSTRUCTURE;
423 * If we don't want this node, stop right away, unless
424 * we are including subnodes
426 if (!p.want && !(flags & FDT_REG_DIRECT_SUBNODES))
428 p.want = info->stack[p.depth].want;
430 while (p.end > path && *--p.end != '/')
436 /* We always include the end tag */
438 p.done = FDT_DONE_STRUCT;
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))
449 info->start = offset;
453 * If this tag is not to be included, finish up the current
456 if (!include && info->start != -1) {
457 if (fdt_add_region(info, base + info->start,
458 stop_at - info->start))
464 /* If we have made it this far, we can commit our pointers */
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;
473 if (fdt_add_region(info, base + info->start,
474 info->ptrs.nextoffset - info->start))
478 if (info->ptrs.done < FDT_DONE_STRINGS) {
479 if (flags & FDT_REG_ADD_STRING_TAB) {
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)))
491 return info->count > 0 ? 0 : -FDT_ERR_NOTFOUND;