xref: /openbmc/u-boot/lib/libfdt/fdt_region.c (revision 4519668b)
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 
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  */
30 static 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 
52 static 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 
67 int 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)
104 			next = node_end - sizeof(fdt32_t);
105 
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  */
138 static 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 
172 enum {
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 
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)
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 
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.
215 
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.
221 
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.
226 
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.
230 
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
236 will succeed.
237 
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
247 next time.
248 
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.
259 
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.
265 
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).
271 */
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)
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 }
493