fmd.c
1 /* fmd.c, parser frontend and utility functions for flashmap descriptor language */ 2 /* SPDX-License-Identifier: GPL-2.0-only */ 3 4 #include "fmd.h" 5 6 #include "common.h" 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, 39 struct unsigned_option start, struct unsigned_option end) 40 { 41 assert(node); 42 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 */ 51 ENTRY search_key = {node->name, NULL}; 52 #else 53 ENTRY search_key = {strdup(node->name), NULL}; 54 #endif 55 56 if (hsearch(search_key, FIND)) { 57 ERROR("Multiple sections with name '%s'\n", node->name); 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) { 65 ERROR("Section '%s' starts too low\n", node->name); 66 return false; 67 } else if (end.val_known && node->offset > end.val) { 68 ERROR("Section '%s' starts too high\n", node->name); 69 return false; 70 } 71 } 72 73 if (node->size_known) { 74 if (node->size == 0) { 75 ERROR("Section '%s' given no space\n", node->name); 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) { 80 ERROR("Section '%s' too big\n", node->name); 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) { 116 ERROR("Section '%s' too big\n", cur->name); 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) { 123 ERROR("Section '%s' starts too high\n", 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) { 224 ERROR("Cannot determine either offset or size of section '%s'\n", 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 280 char child_prefix[strlen(pre) + 2]; 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))) { 308 perror("E: While initializing hashtable"); 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 }