fmap.c
1 /* SPDX-License-Identifier: BSD-3-Clause or GPL-2.0-only */ 2 3 #include <ctype.h> 4 #include <stdlib.h> 5 #include <stdio.h> 6 #include <string.h> 7 #include <fcntl.h> 8 #include <unistd.h> 9 #include <sys/types.h> 10 #include <sys/stat.h> 11 #include <sys/mman.h> 12 #include <errno.h> 13 #include <inttypes.h> 14 #include <limits.h> 15 #include <assert.h> 16 #include <commonlib/bsd/sysincludes.h> 17 #include <commonlib/bsd/helpers.h> 18 19 #include "fmap.h" 20 #include "kv_pair.h" 21 #include "valstr.h" 22 23 const struct valstr flag_lut[] = { 24 { FMAP_AREA_STATIC, "static" }, 25 { FMAP_AREA_COMPRESSED, "compressed" }, 26 { FMAP_AREA_RO, "ro" }, 27 { FMAP_AREA_PRESERVE, "preserve" }, 28 }; 29 30 /* returns size of fmap data structure if successful, <0 to indicate error */ 31 int fmap_size(const struct fmap *fmap) 32 { 33 if (!fmap) 34 return -1; 35 36 return sizeof(*fmap) + (le16toh(fmap->nareas) * sizeof(struct fmap_area)); 37 } 38 39 /* Make a best-effort assessment if the given fmap is real */ 40 static int is_valid_fmap(const struct fmap *fmap) 41 { 42 if (memcmp(fmap, FMAP_SIGNATURE, strlen(FMAP_SIGNATURE)) != 0) 43 return 0; 44 /* strings containing the magic tend to fail here */ 45 if (fmap->ver_major != FMAP_VER_MAJOR) 46 return 0; 47 /* a basic consistency check: flash should be larger than fmap */ 48 if (le32toh(fmap->size) < 49 sizeof(*fmap) + le16toh(fmap->nareas) * sizeof(struct fmap_area)) 50 return 0; 51 52 /* fmap-alikes along binary data tend to fail on having a valid, 53 * null-terminated string in the name field.*/ 54 int i = 0; 55 while (i < FMAP_STRLEN) { 56 if (fmap->name[i] == 0) 57 break; 58 if (!isgraph(fmap->name[i])) 59 return 0; 60 if (i == FMAP_STRLEN - 1) { 61 /* name is specified to be null terminated single-word string 62 * without spaces. We did not break in the 0 test, we know it 63 * is a printable spaceless string but we're seeing FMAP_STRLEN 64 * symbols, which is one too many. 65 */ 66 return 0; 67 } 68 i++; 69 } 70 return 1; 71 72 } 73 74 /* brute force linear search */ 75 static long int fmap_lsearch(const uint8_t *image, size_t len) 76 { 77 unsigned long offset; 78 int fmap_found = 0; 79 80 for (offset = 0; offset < len - strlen(FMAP_SIGNATURE); offset++) { 81 if (is_valid_fmap((const struct fmap *)&image[offset])) { 82 fmap_found = 1; 83 break; 84 } 85 } 86 87 if (!fmap_found) 88 return -1; 89 90 if (offset + fmap_size((const struct fmap *)&image[offset]) > len) 91 return -1; 92 93 return offset; 94 } 95 96 /* if image length is a power of 2, use binary search */ 97 static long fmap_bsearch(const uint8_t *image, size_t len) 98 { 99 unsigned long offset; 100 int fmap_found = 0, stride; 101 102 /* 103 * For efficient operation, we start with the largest stride possible 104 * and then decrease the stride on each iteration. Also, check for a 105 * remainder when modding the offset with the previous stride. This 106 * makes it so that each offset is only checked once. 107 */ 108 for (stride = len / 2; stride >= 16; stride /= 2) { 109 if (fmap_found) 110 break; 111 112 for (offset = 0; 113 offset < len - strlen(FMAP_SIGNATURE); 114 offset += stride) { 115 if ((offset % (stride * 2) == 0) && (offset != 0)) 116 continue; 117 if (is_valid_fmap( 118 (const struct fmap *)&image[offset])) { 119 fmap_found = 1; 120 break; 121 } 122 } 123 } 124 125 if (!fmap_found) 126 return -1; 127 128 if (offset + fmap_size((const struct fmap *)&image[offset]) > len) 129 return -1; 130 131 return offset; 132 } 133 134 static int popcnt(unsigned int u) 135 { 136 int count; 137 138 /* K&R method */ 139 for (count = 0; u; count++) 140 u &= (u - 1); 141 142 return count; 143 } 144 145 long fmap_find(const uint8_t *image, unsigned int image_len) 146 { 147 long ret = -1; 148 149 if ((image == NULL) || (image_len == 0)) 150 return -1; 151 152 if (popcnt(image_len) == 1) 153 ret = fmap_bsearch(image, image_len); 154 else 155 ret = fmap_lsearch(image, image_len); 156 157 return ret; 158 } 159 160 int fmap_print(const struct fmap *fmap) 161 { 162 int i; 163 struct kv_pair *kv = NULL; 164 const uint8_t *tmp; 165 166 kv = kv_pair_new(); 167 if (!kv) 168 return -1; 169 170 tmp = fmap->signature; 171 kv_pair_fmt(kv, "fmap_signature", 172 "0x%02x%02x%02x%02x%02x%02x%02x%02x", 173 tmp[0], tmp[1], tmp[2], tmp[3], 174 tmp[4], tmp[5], tmp[6], tmp[7]); 175 kv_pair_fmt(kv, "fmap_ver_major", "%d", fmap->ver_major); 176 kv_pair_fmt(kv, "fmap_ver_minor","%d", fmap->ver_minor); 177 kv_pair_fmt(kv, "fmap_base", "0x%016llx", 178 (unsigned long long)le64toh(fmap->base)); 179 kv_pair_fmt(kv, "fmap_size", "0x%04x", le32toh(fmap->size)); 180 kv_pair_fmt(kv, "fmap_name", "%s", fmap->name); 181 kv_pair_fmt(kv, "fmap_nareas", "%d", le16toh(fmap->nareas)); 182 kv_pair_print(kv); 183 kv_pair_free(kv); 184 185 for (i = 0; i < le16toh(fmap->nareas); i++) { 186 struct kv_pair *pair; 187 uint16_t flags; 188 char *str; 189 190 pair = kv_pair_new(); 191 if (!pair) 192 return -1; 193 194 kv_pair_fmt(pair, "area_offset", "0x%08x", 195 le32toh(fmap->areas[i].offset)); 196 kv_pair_fmt(pair, "area_size", "0x%08x", 197 le32toh(fmap->areas[i].size)); 198 kv_pair_fmt(pair, "area_name", "%s", 199 fmap->areas[i].name); 200 kv_pair_fmt(pair, "area_flags_raw", "0x%02x", 201 le16toh(fmap->areas[i].flags)); 202 203 /* Print descriptive strings for flags rather than the field */ 204 flags = le16toh(fmap->areas[i].flags); 205 str = fmap_flags_to_string(flags); 206 if (str == NULL) { 207 kv_pair_free(pair); 208 return -1; 209 } 210 kv_pair_fmt(pair, "area_flags", "%s", str); 211 free(str); 212 213 kv_pair_print(pair); 214 kv_pair_free(pair); 215 } 216 217 return 0; 218 } 219 220 /* convert raw flags field to user-friendly string */ 221 char *fmap_flags_to_string(uint16_t flags) 222 { 223 char *str = NULL; 224 unsigned int i, total_size; 225 226 str = malloc(1); 227 str[0] = '\0'; 228 total_size = 1; 229 230 for (i = 0; i < sizeof(flags) * CHAR_BIT; i++) { 231 if (!flags) 232 break; 233 234 if (flags & (1 << i)) { 235 const char *tmp = val2str(1 << i, flag_lut); 236 237 total_size += strlen(tmp); 238 str = realloc(str, total_size); 239 strcat(str, tmp); 240 241 flags &= ~(1 << i); 242 if (flags) { 243 total_size++; 244 str = realloc(str, total_size); 245 strcat(str, ","); 246 } 247 } 248 } 249 250 return str; 251 } 252 253 /* allocate and initialize a new fmap structure */ 254 struct fmap *fmap_create(uint64_t base, uint32_t size, uint8_t *name) 255 { 256 struct fmap *fmap; 257 258 fmap = malloc(sizeof(*fmap)); 259 if (!fmap) 260 return NULL; 261 262 memset(fmap, 0, sizeof(*fmap)); 263 memcpy(&fmap->signature, FMAP_SIGNATURE, strlen(FMAP_SIGNATURE)); 264 fmap->ver_major = FMAP_VER_MAJOR; 265 fmap->ver_minor = FMAP_VER_MINOR; 266 fmap->base = htole64(base); 267 fmap->size = htole32(size); 268 memccpy(&fmap->name, name, '\0', FMAP_STRLEN); 269 270 return fmap; 271 } 272 273 /* free memory used by an fmap structure */ 274 void fmap_destroy(struct fmap *fmap) { 275 free(fmap); 276 } 277 278 /* append area to existing structure, return new total size if successful */ 279 int fmap_append_area(struct fmap **fmap, 280 uint32_t offset, uint32_t size, 281 const uint8_t *name, uint16_t flags) 282 { 283 struct fmap_area *area; 284 int orig_size, new_size; 285 286 if ((fmap == NULL || *fmap == NULL) || (name == NULL)) 287 return -1; 288 289 /* too many areas */ 290 if (le16toh((*fmap)->nareas) >= 0xffff) 291 return -1; 292 293 orig_size = fmap_size(*fmap); 294 new_size = orig_size + sizeof(*area); 295 296 *fmap = realloc(*fmap, new_size); 297 if (*fmap == NULL) 298 return -1; 299 300 area = (struct fmap_area *)((uint8_t *)*fmap + orig_size); 301 memset(area, 0, sizeof(*area)); 302 memccpy(&area->name, name, '\0', FMAP_STRLEN); 303 area->offset = htole32(offset); 304 area->size = htole32(size); 305 area->flags = htole16(flags); 306 307 (*fmap)->nareas = htole16(le16toh((*fmap)->nareas) + 1); 308 return new_size; 309 } 310 311 const struct fmap_area *fmap_find_area(const struct fmap *fmap, 312 const char *name) 313 { 314 int i; 315 const struct fmap_area *area = NULL; 316 317 if (!fmap || !name) 318 return NULL; 319 320 for (i = 0; i < le16toh(fmap->nareas); i++) { 321 if (!strcmp((const char *)fmap->areas[i].name, name)) { 322 area = &fmap->areas[i]; 323 break; 324 } 325 } 326 327 return area; 328 } 329 330 /* 331 * LCOV_EXCL_START 332 * Unit testing stuff done here so we do not need to expose static functions. 333 */ 334 static enum test_status { pass = EXIT_SUCCESS, fail = EXIT_FAILURE } status; 335 static struct fmap *fmap_create_test(void) 336 { 337 struct fmap *fmap; 338 uint64_t base = 0; 339 uint32_t size = 0x100000; 340 char name[] = "test_fmap"; 341 342 status = fail; 343 344 fmap = fmap_create(base, size, (uint8_t *)name); 345 if (!fmap) 346 return NULL; 347 348 if (memcmp(&fmap->signature, FMAP_SIGNATURE, strlen(FMAP_SIGNATURE))) { 349 printf("FAILURE: signature is incorrect\n"); 350 goto fmap_create_test_exit; 351 } 352 353 if ((fmap->ver_major != FMAP_VER_MAJOR) || 354 (fmap->ver_minor != FMAP_VER_MINOR)) { 355 printf("FAILURE: version is incorrect\n"); 356 goto fmap_create_test_exit; 357 } 358 359 if (le64toh(fmap->base) != base) { 360 printf("FAILURE: base is incorrect\n"); 361 goto fmap_create_test_exit; 362 } 363 364 if (le32toh(fmap->size) != 0x100000) { 365 printf("FAILURE: size is incorrect\n"); 366 goto fmap_create_test_exit; 367 } 368 369 if (strcmp((char *)fmap->name, "test_fmap")) { 370 printf("FAILURE: name is incorrect\n"); 371 goto fmap_create_test_exit; 372 } 373 374 if (le16toh(fmap->nareas) != 0) { 375 printf("FAILURE: number of areas is incorrect\n"); 376 goto fmap_create_test_exit; 377 } 378 379 status = pass; 380 fmap_create_test_exit: 381 /* preserve fmap if all went well */ 382 if (status == fail) { 383 fmap_destroy(fmap); 384 fmap = NULL; 385 } 386 return fmap; 387 } 388 389 static int fmap_print_test(struct fmap *fmap) 390 { 391 return fmap_print(fmap); 392 } 393 394 static int fmap_size_test(void) 395 { 396 status = fail; 397 398 if (fmap_size(NULL) >= 0) { 399 printf("FAILURE: failed to abort on NULL pointer input\n"); 400 goto fmap_size_test_exit; 401 } 402 403 status = pass; 404 fmap_size_test_exit: 405 return status; 406 } 407 408 /* this test re-allocates the fmap, so it gets a double-pointer */ 409 static int fmap_append_area_test(struct fmap **fmap) 410 { 411 int total_size; 412 uint16_t nareas_orig; 413 /* test_area will be used by fmap_csum_test and find_area_test */ 414 struct fmap_area test_area = { 415 .offset = htole32(0x400), 416 .size = htole32(0x10000), 417 .name = "test_area_1", 418 .flags = htole16(FMAP_AREA_STATIC), 419 }; 420 421 status = fail; 422 423 if ((fmap_append_area(NULL, 0, 0, test_area.name, 0) >= 0) || 424 (fmap_append_area(fmap, 0, 0, NULL, 0) >= 0)) { 425 printf("FAILURE: failed to abort on NULL pointer input\n"); 426 goto fmap_append_area_test_exit; 427 } 428 429 nareas_orig = le16toh((*fmap)->nareas); 430 (*fmap)->nareas = htole16(~(0)); 431 if (fmap_append_area(fmap, 0, 0, (const uint8_t *)"foo", 0) >= 0) { 432 printf("FAILURE: failed to abort with too many areas\n"); 433 goto fmap_append_area_test_exit; 434 } 435 (*fmap)->nareas = htole16(nareas_orig); 436 437 total_size = sizeof(**fmap) + sizeof(test_area); 438 if (fmap_append_area(fmap, 439 le32toh(test_area.offset), 440 le32toh(test_area.size), 441 test_area.name, 442 le16toh(test_area.flags) 443 ) != total_size) { 444 printf("failed to append area\n"); 445 goto fmap_append_area_test_exit; 446 } 447 448 if (le16toh((*fmap)->nareas) != 1) { 449 printf("FAILURE: failed to increment number of areas\n"); 450 goto fmap_append_area_test_exit; 451 } 452 453 status = pass; 454 fmap_append_area_test_exit: 455 return status; 456 } 457 458 static int fmap_find_area_test(struct fmap *fmap) 459 { 460 status = fail; 461 char area_name[] = "test_area_1"; 462 463 if (fmap_find_area(NULL, area_name) || 464 fmap_find_area(fmap, NULL)) { 465 printf("FAILURE: failed to abort on NULL pointer input\n"); 466 goto fmap_find_area_test_exit; 467 } 468 469 if (fmap_find_area(fmap, area_name) == NULL) { 470 printf("FAILURE: failed to find \"%s\"\n", area_name); 471 goto fmap_find_area_test_exit; 472 } 473 474 status = pass; 475 fmap_find_area_test_exit: 476 return status; 477 } 478 479 static int fmap_flags_to_string_test(void) 480 { 481 char *str = NULL; 482 char *my_str = NULL; 483 unsigned int i; 484 uint16_t flags; 485 486 status = fail; 487 488 /* no area flag */ 489 str = fmap_flags_to_string(0); 490 if (!str || strcmp(str, "")) { 491 printf("FAILURE: failed to return empty string when no flag" 492 "are set"); 493 goto fmap_flags_to_string_test_exit; 494 } 495 free(str); 496 497 /* single area flags */ 498 for (i = 0; i < ARRAY_SIZE(flag_lut); i++) { 499 if (!flag_lut[i].str) 500 continue; 501 502 if ((str = fmap_flags_to_string(flag_lut[i].val)) == NULL) { 503 printf("FAILURE: failed to translate flag to string"); 504 goto fmap_flags_to_string_test_exit; 505 } 506 free(str); 507 } 508 509 /* construct our own flags field and string using all available flags 510 * and compare output with fmap_flags_to_string() */ 511 my_str = calloc(256, 1); 512 flags = 0; 513 for (i = 0; i < ARRAY_SIZE(flag_lut); i++) { 514 if (!flag_lut[i].str) 515 continue; 516 else if (i > 0) 517 strcat(my_str, ","); 518 519 flags |= flag_lut[i].val; 520 strcat(my_str, flag_lut[i].str); 521 } 522 523 str = fmap_flags_to_string(flags); 524 if (strcmp(str, my_str)) { 525 printf("FAILURE: bad result from fmap_flags_to_string\n"); 526 goto fmap_flags_to_string_test_exit; 527 } 528 529 status = pass; 530 fmap_flags_to_string_test_exit: 531 free(str); 532 free(my_str); 533 return status; 534 535 } 536 537 static int fmap_find_test(struct fmap *fmap) 538 { 539 uint8_t *buf; 540 size_t total_size, offset; 541 542 status = fail; 543 544 /* 545 * Note: In these tests, we'll use fmap_find() and control usage of 546 * lsearch and bsearch by using a power-of-2 total_size. For lsearch, 547 * use total_size - 1. For bsearch, use total_size. 548 */ 549 550 total_size = 0x100000; 551 buf = calloc(total_size, 1); 552 553 /* test if image length is zero */ 554 if (fmap_find(buf, 0) >= 0) { 555 printf("FAILURE: failed to abort on zero-length image\n"); 556 goto fmap_find_test_exit; 557 } 558 559 /* test if no fmap exists */ 560 if (fmap_find(buf, total_size - 1) >= 0) { 561 printf("FAILURE: lsearch returned false positive\n"); 562 goto fmap_find_test_exit; 563 } 564 if (fmap_find(buf, total_size) >= 0) { 565 printf("FAILURE: bsearch returned false positive\n"); 566 goto fmap_find_test_exit; 567 } 568 569 /* simple test case: fmap at (total_size / 2) + 1 */ 570 offset = (total_size / 2) + 1; 571 memcpy(&buf[offset], fmap, fmap_size(fmap)); 572 573 if ((unsigned)fmap_find(buf, total_size - 1) != offset) { 574 printf("FAILURE: lsearch failed to find fmap\n"); 575 goto fmap_find_test_exit; 576 } 577 if ((unsigned)fmap_find(buf, total_size) != offset) { 578 printf("FAILURE: bsearch failed to find fmap\n"); 579 goto fmap_find_test_exit; 580 } 581 582 /* test bsearch if offset is at 0 */ 583 offset = 0; 584 memset(buf, 0, total_size); 585 memcpy(buf, fmap, fmap_size(fmap)); 586 if ((unsigned)fmap_find(buf, total_size) != offset) { 587 printf("FAILURE: bsearch failed to find fmap at offset 0\n"); 588 goto fmap_find_test_exit; 589 } 590 591 /* test overrun detection */ 592 memset(buf, 0, total_size); 593 memcpy(&buf[total_size - fmap_size(fmap) + 1], 594 fmap, 595 fmap_size(fmap) + 1); 596 if (fmap_find(buf, total_size - 1) >= 0) { 597 printf("FAILURE: lsearch failed to catch overrun\n"); 598 goto fmap_find_test_exit; 599 } 600 if (fmap_find(buf, total_size) >= 0) { 601 printf("FAILURE: bsearch failed to catch overrun\n"); 602 goto fmap_find_test_exit; 603 } 604 605 status = pass; 606 fmap_find_test_exit: 607 free(buf); 608 return status; 609 } 610 611 int fmap_test(void) 612 { 613 int rc = EXIT_SUCCESS; 614 struct fmap *my_fmap; 615 616 /* 617 * This test has two parts: Creation of an fmap with one or more 618 * area(s), and other stuff. Since a valid fmap is required to run 619 * many tests, we abort if fmap creation fails in any way. 620 * 621 * Also, fmap_csum_test() makes some assumptions based on the areas 622 * appended. See fmap_append_area_test() for details. 623 */ 624 if ((my_fmap = fmap_create_test()) == NULL) { 625 rc = EXIT_FAILURE; 626 goto fmap_test_exit; 627 } 628 629 if (fmap_find_test(my_fmap)) { 630 rc = EXIT_FAILURE; 631 goto fmap_test_exit; 632 } 633 634 if (fmap_append_area_test(&my_fmap)) { 635 rc = EXIT_FAILURE; 636 goto fmap_test_exit; 637 } 638 639 rc |= fmap_find_area_test(my_fmap); 640 rc |= fmap_size_test(); 641 rc |= fmap_flags_to_string_test(); 642 rc |= fmap_print_test(my_fmap); 643 644 fmap_test_exit: 645 fmap_destroy(my_fmap); 646 if (rc) 647 printf("FAILED\n"); 648 return rc; 649 } 650 /* LCOV_EXCL_STOP */