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