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