Patrick Georgi | ea063cb | 2020-05-08 19:28:13 +0200 | [diff] [blame] | 1 | /* fmd.c, parser frontend and utility functions for flashmap descriptor language */ |
Patrick Georgi | 7333a11 | 2020-05-08 20:48:04 +0200 | [diff] [blame] | 2 | /* SPDX-License-Identifier: GPL-2.0-only */ |
Sol Boucher | 69b88bf | 2015-02-26 11:47:19 -0800 | [diff] [blame] | 3 | |
| 4 | #include "fmd.h" |
| 5 | |
Sol Boucher | b974081 | 2015-03-18 10:13:48 -0700 | [diff] [blame] | 6 | #include "common.h" |
Sol Boucher | 69b88bf | 2015-02-26 11:47:19 -0800 | [diff] [blame] | 7 | #include "fmd_parser.h" |
| 8 | #include "fmd_scanner.h" |
| 9 | #include "option.h" |
| 10 | |
| 11 | #include <assert.h> |
| 12 | #include <search.h> |
| 13 | #include <string.h> |
| 14 | |
| 15 | /* |
| 16 | * Validate the given flashmap descriptor node's properties. In particular: |
| 17 | * - Ensure its name is globally unique. |
| 18 | * - Ensure its offset, if known, isn't located before the end of the previous |
| 19 | * section, if this can be determined. |
| 20 | * - Ensure its offset, if known, isn't located after the beginning of the next |
| 21 | * section or off the end of its parent section, if this can be determined. |
| 22 | * - Ensure its size is nonzero. |
| 23 | * - Ensure that the combination of its size and offset, if they are both |
| 24 | * known, doesn't place its end after the beginning of the next section or |
| 25 | * off the end of its parent section, if this can be determined. |
| 26 | * In the case of a validation error, the particular problem is reported to |
| 27 | * standard error and this function returns false. It should be noted that this |
| 28 | * function makes no claim that the members of the node's child list are valid: |
| 29 | * under no circumstances is any recursive validation performed. |
| 30 | * |
| 31 | * @param node The flashmap descriptor node to be validated |
| 32 | * @param start Optional minimum permissible base of the section to be |
| 33 | * validated, to be provided if known |
| 34 | * @param end Optional maximum permissible offset to the end of the section to |
| 35 | * be validated, to be provided if known |
| 36 | * @return Whether the node is valid |
| 37 | */ |
| 38 | static bool validate_descriptor_node(const struct flashmap_descriptor *node, |
Stefan Reinauer | 477a0d6 | 2016-04-20 22:11:25 -0700 | [diff] [blame] | 39 | struct unsigned_option start, struct unsigned_option end) |
| 40 | { |
Sol Boucher | 69b88bf | 2015-02-26 11:47:19 -0800 | [diff] [blame] | 41 | assert(node); |
| 42 | |
Stefan Reinauer | 477a0d6 | 2016-04-20 22:11:25 -0700 | [diff] [blame] | 43 | #if __GLIBC__ |
| 44 | /* GLIBC is different than the BSD libc implementations: |
| 45 | * The hdestroy() [function does] not free the buffers pointed |
| 46 | * to by the key and data elements of the hash table entries. |
| 47 | * vs: |
| 48 | * The hdestroy() function calls free(3) for each comparison key in |
| 49 | * the search table but not the data item associated with the key. |
| 50 | */ |
Sol Boucher | 69b88bf | 2015-02-26 11:47:19 -0800 | [diff] [blame] | 51 | ENTRY search_key = {node->name, NULL}; |
Stefan Reinauer | 477a0d6 | 2016-04-20 22:11:25 -0700 | [diff] [blame] | 52 | #else |
| 53 | ENTRY search_key = {strdup(node->name), NULL}; |
| 54 | #endif |
| 55 | |
Sol Boucher | 69b88bf | 2015-02-26 11:47:19 -0800 | [diff] [blame] | 56 | if (hsearch(search_key, FIND)) { |
Sol Boucher | b974081 | 2015-03-18 10:13:48 -0700 | [diff] [blame] | 57 | ERROR("Multiple sections with name '%s'\n", node->name); |
Sol Boucher | 69b88bf | 2015-02-26 11:47:19 -0800 | [diff] [blame] | 58 | return false; |
| 59 | } |
| 60 | if (!hsearch(search_key, ENTER)) |
| 61 | assert(false); |
| 62 | |
| 63 | if (node->offset_known) { |
| 64 | if (start.val_known && node->offset < start.val) { |
Sol Boucher | b974081 | 2015-03-18 10:13:48 -0700 | [diff] [blame] | 65 | ERROR("Section '%s' starts too low\n", node->name); |
Sol Boucher | 69b88bf | 2015-02-26 11:47:19 -0800 | [diff] [blame] | 66 | return false; |
| 67 | } else if (end.val_known && node->offset > end.val) { |
Sol Boucher | b974081 | 2015-03-18 10:13:48 -0700 | [diff] [blame] | 68 | ERROR("Section '%s' starts too high\n", node->name); |
Sol Boucher | 69b88bf | 2015-02-26 11:47:19 -0800 | [diff] [blame] | 69 | return false; |
| 70 | } |
| 71 | } |
| 72 | |
| 73 | if (node->size_known) { |
| 74 | if (node->size == 0) { |
Sol Boucher | b974081 | 2015-03-18 10:13:48 -0700 | [diff] [blame] | 75 | ERROR("Section '%s' given no space\n", node->name); |
Sol Boucher | 69b88bf | 2015-02-26 11:47:19 -0800 | [diff] [blame] | 76 | return false; |
| 77 | } else if (node->offset_known) { |
| 78 | unsigned node_end = node->offset + node->size; |
| 79 | if (end.val_known && node_end > end.val) { |
Sol Boucher | b974081 | 2015-03-18 10:13:48 -0700 | [diff] [blame] | 80 | ERROR("Section '%s' too big\n", node->name); |
Sol Boucher | 69b88bf | 2015-02-26 11:47:19 -0800 | [diff] [blame] | 81 | return false; |
| 82 | } |
| 83 | } |
| 84 | } |
| 85 | |
| 86 | return true; |
| 87 | } |
| 88 | |
| 89 | /* |
| 90 | * Performs reverse lateral processing of sibling nodes, as described by the |
| 91 | * documentation of its caller, validate_and_complete_info(). If it encounters |
| 92 | * a node that is invalid in a way that couldn't have been discovered earlier, |
| 93 | * it explains the problem to standard output and returns false. |
| 94 | * |
| 95 | * @param first_incomplete_it First node whose offset or size couldn't be |
| 96 | * determined during forward processing |
| 97 | * @param cur_incomplete_it Last node whose offset or size is unknown |
| 98 | * @param end_watermark Offset to the end of the unresolved region |
| 99 | * @return Whether all completed nodes were still valid |
| 100 | */ |
| 101 | static bool complete_missing_info_backward( |
| 102 | flashmap_descriptor_iterator_t first_incomplete_it, |
| 103 | flashmap_descriptor_iterator_t cur_incomplete_it, |
| 104 | unsigned end_watermark) |
| 105 | { |
| 106 | assert(first_incomplete_it); |
| 107 | assert(cur_incomplete_it); |
| 108 | assert(cur_incomplete_it >= first_incomplete_it); |
| 109 | |
| 110 | do { |
| 111 | struct flashmap_descriptor *cur = *cur_incomplete_it; |
| 112 | |
| 113 | assert(cur->offset_known || cur->size_known); |
| 114 | if (!cur->offset_known) { |
| 115 | if (cur->size > end_watermark) { |
Sol Boucher | b974081 | 2015-03-18 10:13:48 -0700 | [diff] [blame] | 116 | ERROR("Section '%s' too big\n", cur->name); |
Sol Boucher | 69b88bf | 2015-02-26 11:47:19 -0800 | [diff] [blame] | 117 | return false; |
| 118 | } |
| 119 | cur->offset_known = true; |
| 120 | cur->offset = end_watermark -= cur->size; |
| 121 | } else if (!cur->size_known) { |
| 122 | if (cur->offset > end_watermark) { |
Sol Boucher | b974081 | 2015-03-18 10:13:48 -0700 | [diff] [blame] | 123 | ERROR("Section '%s' starts too high\n", |
Sol Boucher | 69b88bf | 2015-02-26 11:47:19 -0800 | [diff] [blame] | 124 | cur->name); |
| 125 | return false; |
| 126 | } |
| 127 | cur->size_known = true; |
| 128 | cur->size = end_watermark - cur->offset; |
| 129 | end_watermark = cur->offset; |
| 130 | } |
| 131 | } while (--cur_incomplete_it >= first_incomplete_it); |
| 132 | |
| 133 | return true; |
| 134 | } |
| 135 | |
| 136 | /* |
| 137 | * Recursively examine each descendant of the provided flashmap descriptor node |
| 138 | * to ensure its position and size are known, attempt to infer them otherwise, |
| 139 | * and validate their values once they've been populated. |
| 140 | * This processes nodes according to the following algorithm: |
| 141 | * - At each level of the tree, it moves laterally between siblings, keeping |
| 142 | * a watermark of its current offset relative to the previous section, which |
| 143 | * it uses to fill in any unknown offsets it encounters along the way. |
| 144 | * - The first time it encounters a sibling with unknown size, it loses track |
| 145 | * of the watermark, and is therefore unable to complete further offsets; |
| 146 | * instead, if the watermark was known before, it marks the current node as |
| 147 | * the first that couldn't be completed in the initial pass. |
| 148 | * - If the current watermark is unknown (i.e. a node has been marked as the |
| 149 | * first incomplete one) and one with a fixed offset is encountered, a |
| 150 | * reverse lateral traversal is dispatched that uses that provided offset as |
| 151 | * a reverse watermark to complete all unknown fields until it finishes with |
| 152 | * the node marked as the first incomplete one: at this point, that flag is |
| 153 | * cleared, the watermark is updated, and forward processing resumes from |
| 154 | * where it left off. |
| 155 | * - If the watermark is unknown (i.e. node(s) are incomplete) after traversing |
| 156 | * all children of a particular parent node, reverse processing is employed |
| 157 | * as described above, except that the reverse watermark is initialized to |
| 158 | * the parent node's size instead of the (nonexistent) next node's offset. |
| 159 | * - Once all of a node's children have been processed, the algorithm applies |
| 160 | * itself recursively to each of the child nodes; thus, lower levels of the |
| 161 | * tree are processed only after their containing levels are finished. |
| 162 | * This approach can fail in two possible ways (in which case the problem is |
| 163 | * reported to standard output and this function returns false): |
| 164 | * - Processing reveals that some node's provided value is invalid in some way. |
| 165 | * - Processing determines that one or more provided values require an omitted |
| 166 | * field to take a nonsensical value. |
| 167 | * - Processing determines that it is impossible to determine a group of |
| 168 | * omitted values. This state is detected when a node whose offset *and* |
| 169 | * value are omitted is encountered during forward processing and while the |
| 170 | * current watermark is unknown: in such a case, neither can be known without |
| 171 | * being provided with either the other or more context. |
| 172 | * The function notably performs neither validation nor completion on the parent |
| 173 | * node it is passed; thus, it is important to ensure that that node is valid. |
| 174 | * (At the very least, it must have a valid size field in order for the |
| 175 | * algorithm to work on its children.) |
| 176 | * |
| 177 | * @param cur_level Parent node, which must minimally already have a valid size |
| 178 | * @return Whether completing and validating the children succeeded |
| 179 | */ |
| 180 | static bool validate_and_complete_info(struct flashmap_descriptor *cur_level) |
| 181 | { |
| 182 | assert(cur_level); |
| 183 | assert(cur_level->size_known); |
| 184 | |
| 185 | // Our watermark is only known when first_incomplete_it is NULL. |
| 186 | flashmap_descriptor_iterator_t first_incomplete_it = NULL; |
| 187 | unsigned watermark = 0; |
| 188 | |
| 189 | fmd_foreach_child_iterator(cur_it, cur_level) { |
| 190 | struct flashmap_descriptor *cur_section = *cur_it; |
| 191 | |
| 192 | if (first_incomplete_it) { |
| 193 | if (cur_section->offset_known) { |
| 194 | if (complete_missing_info_backward( |
| 195 | first_incomplete_it, cur_it - 1, |
| 196 | cur_section->offset)) { |
| 197 | first_incomplete_it = NULL; |
| 198 | watermark = cur_section->offset; |
| 199 | } else { |
| 200 | return false; |
| 201 | } |
| 202 | } |
| 203 | // Otherwise, we can't go back until a provided offset. |
| 204 | } else if (!cur_section->offset_known) { |
| 205 | cur_section->offset_known = true; |
| 206 | cur_section->offset = watermark; |
| 207 | } |
| 208 | |
| 209 | assert(cur_level->size_known); |
| 210 | struct unsigned_option max_endpoint = {true, cur_level->size}; |
| 211 | if (cur_it != cur_level->list + cur_level->list_len - 1) { |
| 212 | struct flashmap_descriptor *next_section = cur_it[1]; |
| 213 | max_endpoint.val_known = next_section->offset_known; |
| 214 | max_endpoint.val = next_section->offset; |
| 215 | } |
| 216 | if (!validate_descriptor_node(cur_section, |
| 217 | (struct unsigned_option) |
| 218 | {!first_incomplete_it, watermark}, |
| 219 | max_endpoint)) |
| 220 | return false; |
| 221 | |
| 222 | if (!cur_section->size_known) { |
| 223 | if (!cur_section->offset_known) { |
Sol Boucher | b974081 | 2015-03-18 10:13:48 -0700 | [diff] [blame] | 224 | ERROR("Cannot determine either offset or size of section '%s'\n", |
Sol Boucher | 69b88bf | 2015-02-26 11:47:19 -0800 | [diff] [blame] | 225 | cur_section->name); |
| 226 | return false; |
| 227 | } else if (!first_incomplete_it) { |
| 228 | first_incomplete_it = cur_it; |
| 229 | } else { |
| 230 | // We shouldn't find an unknown size within an |
| 231 | // incomplete region because the backward |
| 232 | // traversal at the beginning of this node's |
| 233 | // processing should have concluded said region. |
| 234 | assert(!first_incomplete_it); |
| 235 | } |
| 236 | } else if (!first_incomplete_it) { |
| 237 | watermark = cur_section->offset + cur_section->size; |
| 238 | } |
| 239 | } |
| 240 | |
| 241 | if (first_incomplete_it && |
| 242 | !complete_missing_info_backward(first_incomplete_it, |
| 243 | cur_level->list + cur_level->list_len - 1, |
| 244 | cur_level->size)) |
| 245 | return false; |
| 246 | |
| 247 | fmd_foreach_child(cur_section, cur_level) { |
| 248 | assert(cur_section->offset_known); |
| 249 | assert(cur_section->size_known); |
| 250 | |
| 251 | if (!validate_and_complete_info(cur_section)) |
| 252 | return false; |
| 253 | } |
| 254 | |
| 255 | return true; |
| 256 | } |
| 257 | |
| 258 | static void print_with_prefix(const struct flashmap_descriptor *tree, |
| 259 | const char *pre) |
| 260 | { |
| 261 | assert(tree); |
| 262 | assert(pre); |
| 263 | |
| 264 | printf("%ssection '%s' has ", pre, tree->name); |
| 265 | |
| 266 | if (tree->offset_known) |
| 267 | printf("offset %uB, ", tree->offset); |
| 268 | else |
| 269 | fputs("unknown offset, ", stdout); |
| 270 | |
| 271 | if (tree->size_known) |
| 272 | printf("size %uB, ", tree->size); |
| 273 | else |
| 274 | fputs("unknown size, ", stdout); |
| 275 | |
| 276 | printf("and %zu subsections", tree->list_len); |
| 277 | if (tree->list_len) { |
| 278 | puts(":"); |
| 279 | |
Patrick Georgi | dce629b | 2017-01-13 13:30:54 +0100 | [diff] [blame] | 280 | char child_prefix[strlen(pre) + 2]; |
Sol Boucher | 69b88bf | 2015-02-26 11:47:19 -0800 | [diff] [blame] | 281 | strcpy(child_prefix, pre); |
| 282 | strcat(child_prefix, "\t"); |
| 283 | fmd_foreach_child(each, tree) |
| 284 | print_with_prefix(each, child_prefix); |
| 285 | } else { |
| 286 | puts(""); |
| 287 | } |
| 288 | } |
| 289 | |
| 290 | struct flashmap_descriptor *fmd_create(FILE *stream) |
| 291 | { |
| 292 | assert(stream); |
| 293 | |
| 294 | yyin = stream; |
| 295 | |
| 296 | struct flashmap_descriptor *ret = NULL; |
| 297 | if (yyparse() == 0) |
| 298 | ret = res; |
| 299 | |
| 300 | yylex_destroy(); |
| 301 | yyin = NULL; |
| 302 | res = NULL; |
| 303 | |
| 304 | if (ret) { |
| 305 | // This hash table is used to store the declared name of each |
| 306 | // section and ensure that each is globally unique. |
| 307 | if (!hcreate(fmd_count_nodes(ret))) { |
Sol Boucher | b974081 | 2015-03-18 10:13:48 -0700 | [diff] [blame] | 308 | perror("E: While initializing hashtable"); |
Sol Boucher | 69b88bf | 2015-02-26 11:47:19 -0800 | [diff] [blame] | 309 | fmd_cleanup(ret); |
| 310 | return NULL; |
| 311 | } |
| 312 | |
| 313 | // Even though we haven't checked that the root node (ret) has |
| 314 | // a size field as required by this function, the parser |
| 315 | // warrants that it does because the grammar requires it. |
| 316 | if (!validate_and_complete_info(ret)) { |
| 317 | hdestroy(); |
| 318 | fmd_cleanup(ret); |
| 319 | return NULL; |
| 320 | } |
| 321 | |
| 322 | hdestroy(); |
| 323 | } |
| 324 | |
| 325 | return ret; |
| 326 | } |
| 327 | |
| 328 | void fmd_cleanup(struct flashmap_descriptor *victim) |
| 329 | { |
| 330 | if (!victim) |
| 331 | return; |
| 332 | |
| 333 | free(victim->name); |
| 334 | for (unsigned idx = 0; idx < victim->list_len; ++idx) |
| 335 | fmd_cleanup(victim->list[idx]); |
| 336 | free(victim->list); |
| 337 | free(victim); |
| 338 | } |
| 339 | |
| 340 | size_t fmd_count_nodes(const struct flashmap_descriptor *tree) |
| 341 | { |
| 342 | assert(tree); |
| 343 | |
| 344 | if (!tree->list_len) |
| 345 | return 1; |
| 346 | |
| 347 | unsigned count = 1; |
| 348 | fmd_foreach_child(lower, tree) |
| 349 | count += fmd_count_nodes(lower); |
| 350 | return count; |
| 351 | } |
| 352 | |
| 353 | const struct flashmap_descriptor *fmd_find_node( |
| 354 | const struct flashmap_descriptor *root, const char *name) |
| 355 | { |
| 356 | assert(root); |
| 357 | assert(name); |
| 358 | |
| 359 | if (strcmp(root->name, name) == 0) |
| 360 | return root; |
| 361 | |
| 362 | fmd_foreach_child(descendant, root) { |
| 363 | const struct flashmap_descriptor *match = |
| 364 | fmd_find_node(descendant, name); |
| 365 | if (match) |
| 366 | return match; |
| 367 | } |
| 368 | return NULL; |
| 369 | } |
| 370 | |
| 371 | unsigned fmd_calc_absolute_offset(const struct flashmap_descriptor *root, |
| 372 | const char *name) |
| 373 | { |
| 374 | assert(root); |
| 375 | assert(name); |
| 376 | |
| 377 | if (strcmp(root->name, name) == 0) |
| 378 | return 0; |
| 379 | |
| 380 | fmd_foreach_child(descendant, root) { |
| 381 | unsigned subtotal = fmd_calc_absolute_offset(descendant, name); |
| 382 | if (subtotal != FMD_NOTFOUND) |
| 383 | return descendant->offset + subtotal; |
| 384 | } |
| 385 | return FMD_NOTFOUND; |
| 386 | } |
| 387 | |
| 388 | void fmd_print(const struct flashmap_descriptor *tree) |
| 389 | { |
| 390 | print_with_prefix(tree, ""); |
| 391 | } |