2 * fmd.c, parser frontend and utility functions for flashmap descriptor language
4 * Copyright (C) 2015 Google, Inc.
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; version 2 of the License.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
19 #include "fmd_parser.h"
20 #include "fmd_scanner.h"
28 * Validate the given flashmap descriptor node's properties. In particular:
29 * - Ensure its name is globally unique.
30 * - Ensure its offset, if known, isn't located before the end of the previous
31 * section, if this can be determined.
32 * - Ensure its offset, if known, isn't located after the beginning of the next
33 * section or off the end of its parent section, if this can be determined.
34 * - Ensure its size is nonzero.
35 * - Ensure that the combination of its size and offset, if they are both
36 * known, doesn't place its end after the beginning of the next section or
37 * off the end of its parent section, if this can be determined.
38 * In the case of a validation error, the particular problem is reported to
39 * standard error and this function returns false. It should be noted that this
40 * function makes no claim that the members of the node's child list are valid:
41 * under no circumstances is any recursive validation performed.
43 * @param node The flashmap descriptor node to be validated
44 * @param start Optional minimum permissible base of the section to be
45 * validated, to be provided if known
46 * @param end Optional maximum permissible offset to the end of the section to
47 * be validated, to be provided if known
48 * @return Whether the node is valid
50 static bool validate_descriptor_node(const struct flashmap_descriptor
*node
,
51 struct unsigned_option start
, struct unsigned_option end
) {
54 ENTRY search_key
= {node
->name
, NULL
};
55 if (hsearch(search_key
, FIND
)) {
56 ERROR("Multiple sections with name '%s'\n", node
->name
);
59 if (!hsearch(search_key
, ENTER
))
62 if (node
->offset_known
) {
63 if (start
.val_known
&& node
->offset
< start
.val
) {
64 ERROR("Section '%s' starts too low\n", node
->name
);
66 } else if (end
.val_known
&& node
->offset
> end
.val
) {
67 ERROR("Section '%s' starts too high\n", node
->name
);
72 if (node
->size_known
) {
73 if (node
->size
== 0) {
74 ERROR("Section '%s' given no space\n", node
->name
);
76 } else if (node
->offset_known
) {
77 unsigned node_end
= node
->offset
+ node
->size
;
78 if (end
.val_known
&& node_end
> end
.val
) {
79 ERROR("Section '%s' too big\n", node
->name
);
89 * Performs reverse lateral processing of sibling nodes, as described by the
90 * documentation of its caller, validate_and_complete_info(). If it encounters
91 * a node that is invalid in a way that couldn't have been discovered earlier,
92 * it explains the problem to standard output and returns false.
94 * @param first_incomplete_it First node whose offset or size couldn't be
95 * determined during forward processing
96 * @param cur_incomplete_it Last node whose offset or size is unknown
97 * @param end_watermark Offset to the end of the unresolved region
98 * @return Whether all completed nodes were still valid
100 static bool complete_missing_info_backward(
101 flashmap_descriptor_iterator_t first_incomplete_it
,
102 flashmap_descriptor_iterator_t cur_incomplete_it
,
103 unsigned end_watermark
)
105 assert(first_incomplete_it
);
106 assert(cur_incomplete_it
);
107 assert(cur_incomplete_it
>= first_incomplete_it
);
110 struct flashmap_descriptor
*cur
= *cur_incomplete_it
;
112 assert(cur
->offset_known
|| cur
->size_known
);
113 if (!cur
->offset_known
) {
114 if (cur
->size
> end_watermark
) {
115 ERROR("Section '%s' too big\n", cur
->name
);
118 cur
->offset_known
= true;
119 cur
->offset
= end_watermark
-= cur
->size
;
120 } else if (!cur
->size_known
) {
121 if (cur
->offset
> end_watermark
) {
122 ERROR("Section '%s' starts too high\n",
126 cur
->size_known
= true;
127 cur
->size
= end_watermark
- cur
->offset
;
128 end_watermark
= cur
->offset
;
130 } while (--cur_incomplete_it
>= first_incomplete_it
);
136 * Recursively examine each descendant of the provided flashmap descriptor node
137 * to ensure its position and size are known, attempt to infer them otherwise,
138 * and validate their values once they've been populated.
139 * This processes nodes according to the following algorithm:
140 * - At each level of the tree, it moves laterally between siblings, keeping
141 * a watermark of its current offset relative to the previous section, which
142 * it uses to fill in any unknown offsets it encounters along the way.
143 * - The first time it encounters a sibling with unknown size, it loses track
144 * of the watermark, and is therefore unable to complete further offsets;
145 * instead, if the watermark was known before, it marks the current node as
146 * the first that couldn't be completed in the initial pass.
147 * - If the current watermark is unknown (i.e. a node has been marked as the
148 * first incomplete one) and one with a fixed offset is encountered, a
149 * reverse lateral traversal is dispatched that uses that provided offset as
150 * a reverse watermark to complete all unknown fields until it finishes with
151 * the node marked as the first incomplete one: at this point, that flag is
152 * cleared, the watermark is updated, and forward processing resumes from
154 * - If the watermark is unknown (i.e. node(s) are incomplete) after traversing
155 * all children of a particular parent node, reverse processing is employed
156 * as described above, except that the reverse watermark is initialized to
157 * the parent node's size instead of the (nonexistent) next node's offset.
158 * - Once all of a node's children have been processed, the algorithm applies
159 * itself recursively to each of the child nodes; thus, lower levels of the
160 * tree are processed only after their containing levels are finished.
161 * This approach can fail in two possible ways (in which case the problem is
162 * reported to standard output and this function returns false):
163 * - Processing reveals that some node's provided value is invalid in some way.
164 * - Processing determines that one or more provided values require an omitted
165 * field to take a nonsensical value.
166 * - Processing determines that it is impossible to determine a group of
167 * omitted values. This state is detected when a node whose offset *and*
168 * value are omitted is encountered during forward processing and while the
169 * current watermark is unknown: in such a case, neither can be known without
170 * being provided with either the other or more context.
171 * The function notably performs neither validation nor completion on the parent
172 * node it is passed; thus, it is important to ensure that that node is valid.
173 * (At the very least, it must have a valid size field in order for the
174 * algorithm to work on its children.)
176 * @param cur_level Parent node, which must minimally already have a valid size
177 * @return Whether completing and validating the children succeeded
179 static bool validate_and_complete_info(struct flashmap_descriptor
*cur_level
)
182 assert(cur_level
->size_known
);
184 // Our watermark is only known when first_incomplete_it is NULL.
185 flashmap_descriptor_iterator_t first_incomplete_it
= NULL
;
186 unsigned watermark
= 0;
188 fmd_foreach_child_iterator(cur_it
, cur_level
) {
189 struct flashmap_descriptor
*cur_section
= *cur_it
;
191 if (first_incomplete_it
) {
192 if (cur_section
->offset_known
) {
193 if (complete_missing_info_backward(
194 first_incomplete_it
, cur_it
- 1,
195 cur_section
->offset
)) {
196 first_incomplete_it
= NULL
;
197 watermark
= cur_section
->offset
;
202 // Otherwise, we can't go back until a provided offset.
203 } else if (!cur_section
->offset_known
) {
204 cur_section
->offset_known
= true;
205 cur_section
->offset
= watermark
;
208 assert(cur_level
->size_known
);
209 struct unsigned_option max_endpoint
= {true, cur_level
->size
};
210 if (cur_it
!= cur_level
->list
+ cur_level
->list_len
- 1) {
211 struct flashmap_descriptor
*next_section
= cur_it
[1];
212 max_endpoint
.val_known
= next_section
->offset_known
;
213 max_endpoint
.val
= next_section
->offset
;
215 if (!validate_descriptor_node(cur_section
,
216 (struct unsigned_option
)
217 {!first_incomplete_it
, watermark
},
221 if (!cur_section
->size_known
) {
222 if (!cur_section
->offset_known
) {
223 ERROR("Cannot determine either offset or size of section '%s'\n",
226 } else if (!first_incomplete_it
) {
227 first_incomplete_it
= cur_it
;
229 // We shouldn't find an unknown size within an
230 // incomplete region because the backward
231 // traversal at the beginning of this node's
232 // processing should have concluded said region.
233 assert(!first_incomplete_it
);
235 } else if (!first_incomplete_it
) {
236 watermark
= cur_section
->offset
+ cur_section
->size
;
240 if (first_incomplete_it
&&
241 !complete_missing_info_backward(first_incomplete_it
,
242 cur_level
->list
+ cur_level
->list_len
- 1,
246 fmd_foreach_child(cur_section
, cur_level
) {
247 assert(cur_section
->offset_known
);
248 assert(cur_section
->size_known
);
250 if (!validate_and_complete_info(cur_section
))
257 static void print_with_prefix(const struct flashmap_descriptor
*tree
,
263 printf("%ssection '%s' has ", pre
, tree
->name
);
265 if (tree
->offset_known
)
266 printf("offset %uB, ", tree
->offset
);
268 fputs("unknown offset, ", stdout
);
270 if (tree
->size_known
)
271 printf("size %uB, ", tree
->size
);
273 fputs("unknown size, ", stdout
);
275 printf("and %zu subsections", tree
->list_len
);
276 if (tree
->list_len
) {
279 char child_prefix
[strlen(pre
) + 1];
280 strcpy(child_prefix
, pre
);
281 strcat(child_prefix
, "\t");
282 fmd_foreach_child(each
, tree
)
283 print_with_prefix(each
, child_prefix
);
289 struct flashmap_descriptor
*fmd_create(FILE *stream
)
295 struct flashmap_descriptor
*ret
= NULL
;
304 // This hash table is used to store the declared name of each
305 // section and ensure that each is globally unique.
306 if (!hcreate(fmd_count_nodes(ret
))) {
307 perror("E: While initializing hashtable");
312 // Even though we haven't checked that the root node (ret) has
313 // a size field as required by this function, the parser
314 // warrants that it does because the grammar requires it.
315 if (!validate_and_complete_info(ret
)) {
327 void fmd_cleanup(struct flashmap_descriptor
*victim
)
333 for (unsigned idx
= 0; idx
< victim
->list_len
; ++idx
)
334 fmd_cleanup(victim
->list
[idx
]);
339 size_t fmd_count_nodes(const struct flashmap_descriptor
*tree
)
347 fmd_foreach_child(lower
, tree
)
348 count
+= fmd_count_nodes(lower
);
352 const struct flashmap_descriptor
*fmd_find_node(
353 const struct flashmap_descriptor
*root
, const char *name
)
358 if (strcmp(root
->name
, name
) == 0)
361 fmd_foreach_child(descendant
, root
) {
362 const struct flashmap_descriptor
*match
=
363 fmd_find_node(descendant
, name
);
370 unsigned fmd_calc_absolute_offset(const struct flashmap_descriptor
*root
,
376 if (strcmp(root
->name
, name
) == 0)
379 fmd_foreach_child(descendant
, root
) {
380 unsigned subtotal
= fmd_calc_absolute_offset(descendant
, name
);
381 if (subtotal
!= FMD_NOTFOUND
)
382 return descendant
->offset
+ subtotal
;
387 void fmd_print(const struct flashmap_descriptor
*tree
)
389 print_with_prefix(tree
, "");