util/cbfstool/flashmap/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 int 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 int fmap_bsearch(const uint8_t *image, size_t len)
  98 {
  99         unsigned long int offset = -1;
 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 int fmap_find(const uint8_t *image, unsigned int image_len)
 146 {
 147         long int 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 */