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 */
fmap_size(const struct fmap * fmap)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 */
is_valid_fmap(const struct fmap * fmap)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 */
fmap_lsearch(const uint8_t * image,size_t len)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 */
fmap_bsearch(const uint8_t * image,size_t len)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
popcnt(unsigned int u)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
fmap_find(const uint8_t * image,unsigned int image_len)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
fmap_print(const struct fmap * fmap)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 */
fmap_flags_to_string(uint16_t flags)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 */
fmap_create(uint64_t base,uint32_t size,uint8_t * name)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 */
fmap_destroy(struct fmap * fmap)274 void fmap_destroy(struct fmap *fmap) {
275 free(fmap);
276 }
277
278 /* append area to existing structure, return new total size if successful */
fmap_append_area(struct fmap ** fmap,uint32_t offset,uint32_t size,const uint8_t * name,uint16_t flags)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
fmap_find_area(const struct fmap * fmap,const char * name)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;
fmap_create_test(void)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
fmap_print_test(struct fmap * fmap)389 static int fmap_print_test(struct fmap *fmap)
390 {
391 return fmap_print(fmap);
392 }
393
fmap_size_test(void)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 */
fmap_append_area_test(struct fmap ** fmap)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
fmap_find_area_test(struct fmap * fmap)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
fmap_flags_to_string_test(void)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
fmap_find_test(struct fmap * fmap)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
fmap_test(void)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 */
651