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