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