memory_buffer_alloc.c (18589B)
1 /* 2 * Buffer-based memory allocator 3 * 4 * Copyright The Mbed TLS Contributors 5 * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later 6 */ 7 8 #include "common.h" 9 10 #if defined(MBEDTLS_MEMORY_BUFFER_ALLOC_C) 11 #include "mbedtls/memory_buffer_alloc.h" 12 13 /* No need for the header guard as MBEDTLS_MEMORY_BUFFER_ALLOC_C 14 is dependent upon MBEDTLS_PLATFORM_C */ 15 #include "mbedtls/platform.h" 16 #include "mbedtls/platform_util.h" 17 18 #include <string.h> 19 20 #if defined(MBEDTLS_MEMORY_BACKTRACE) 21 #include <execinfo.h> 22 #endif 23 24 #if defined(MBEDTLS_THREADING_C) 25 #include "mbedtls/threading.h" 26 #endif 27 28 #define MAGIC1 0xFF00AA55 29 #define MAGIC2 0xEE119966 30 #define MAX_BT 20 31 32 typedef struct _memory_header memory_header; 33 struct _memory_header { 34 size_t magic1; 35 size_t size; 36 size_t alloc; 37 memory_header *prev; 38 memory_header *next; 39 memory_header *prev_free; 40 memory_header *next_free; 41 #if defined(MBEDTLS_MEMORY_BACKTRACE) 42 char **trace; 43 size_t trace_count; 44 #endif 45 size_t magic2; 46 }; 47 48 typedef struct { 49 unsigned char *buf; 50 size_t len; 51 memory_header *first; 52 memory_header *first_free; 53 int verify; 54 #if defined(MBEDTLS_MEMORY_DEBUG) 55 size_t alloc_count; 56 size_t free_count; 57 size_t total_used; 58 size_t maximum_used; 59 size_t header_count; 60 size_t maximum_header_count; 61 #endif 62 #if defined(MBEDTLS_THREADING_C) 63 mbedtls_threading_mutex_t mutex; 64 #endif 65 } 66 buffer_alloc_ctx; 67 68 static buffer_alloc_ctx heap; 69 70 #if defined(MBEDTLS_MEMORY_DEBUG) 71 static void debug_header(memory_header *hdr) 72 { 73 #if defined(MBEDTLS_MEMORY_BACKTRACE) 74 size_t i; 75 #endif 76 77 mbedtls_fprintf(stderr, "HDR: PTR(%10zu), PREV(%10zu), NEXT(%10zu), " 78 "ALLOC(%zu), SIZE(%10zu)\n", 79 (size_t) hdr, (size_t) hdr->prev, (size_t) hdr->next, 80 hdr->alloc, hdr->size); 81 mbedtls_fprintf(stderr, " FPREV(%10zu), FNEXT(%10zu)\n", 82 (size_t) hdr->prev_free, (size_t) hdr->next_free); 83 84 #if defined(MBEDTLS_MEMORY_BACKTRACE) 85 mbedtls_fprintf(stderr, "TRACE: \n"); 86 for (i = 0; i < hdr->trace_count; i++) { 87 mbedtls_fprintf(stderr, "%s\n", hdr->trace[i]); 88 } 89 mbedtls_fprintf(stderr, "\n"); 90 #endif 91 } 92 93 static void debug_chain(void) 94 { 95 memory_header *cur = heap.first; 96 97 mbedtls_fprintf(stderr, "\nBlock list\n"); 98 while (cur != NULL) { 99 debug_header(cur); 100 cur = cur->next; 101 } 102 103 mbedtls_fprintf(stderr, "Free list\n"); 104 cur = heap.first_free; 105 106 while (cur != NULL) { 107 debug_header(cur); 108 cur = cur->next_free; 109 } 110 } 111 #endif /* MBEDTLS_MEMORY_DEBUG */ 112 113 static int verify_header(memory_header *hdr) 114 { 115 if (hdr->magic1 != MAGIC1) { 116 #if defined(MBEDTLS_MEMORY_DEBUG) 117 mbedtls_fprintf(stderr, "FATAL: MAGIC1 mismatch\n"); 118 #endif 119 return 1; 120 } 121 122 if (hdr->magic2 != MAGIC2) { 123 #if defined(MBEDTLS_MEMORY_DEBUG) 124 mbedtls_fprintf(stderr, "FATAL: MAGIC2 mismatch\n"); 125 #endif 126 return 1; 127 } 128 129 if (hdr->alloc > 1) { 130 #if defined(MBEDTLS_MEMORY_DEBUG) 131 mbedtls_fprintf(stderr, "FATAL: alloc has illegal value\n"); 132 #endif 133 return 1; 134 } 135 136 if (hdr->prev != NULL && hdr->prev == hdr->next) { 137 #if defined(MBEDTLS_MEMORY_DEBUG) 138 mbedtls_fprintf(stderr, "FATAL: prev == next\n"); 139 #endif 140 return 1; 141 } 142 143 if (hdr->prev_free != NULL && hdr->prev_free == hdr->next_free) { 144 #if defined(MBEDTLS_MEMORY_DEBUG) 145 mbedtls_fprintf(stderr, "FATAL: prev_free == next_free\n"); 146 #endif 147 return 1; 148 } 149 150 return 0; 151 } 152 153 static int verify_chain(void) 154 { 155 memory_header *prv = heap.first, *cur; 156 157 if (prv == NULL || verify_header(prv) != 0) { 158 #if defined(MBEDTLS_MEMORY_DEBUG) 159 mbedtls_fprintf(stderr, "FATAL: verification of first header " 160 "failed\n"); 161 #endif 162 return 1; 163 } 164 165 if (heap.first->prev != NULL) { 166 #if defined(MBEDTLS_MEMORY_DEBUG) 167 mbedtls_fprintf(stderr, "FATAL: verification failed: " 168 "first->prev != NULL\n"); 169 #endif 170 return 1; 171 } 172 173 cur = heap.first->next; 174 175 while (cur != NULL) { 176 if (verify_header(cur) != 0) { 177 #if defined(MBEDTLS_MEMORY_DEBUG) 178 mbedtls_fprintf(stderr, "FATAL: verification of header " 179 "failed\n"); 180 #endif 181 return 1; 182 } 183 184 if (cur->prev != prv) { 185 #if defined(MBEDTLS_MEMORY_DEBUG) 186 mbedtls_fprintf(stderr, "FATAL: verification failed: " 187 "cur->prev != prv\n"); 188 #endif 189 return 1; 190 } 191 192 prv = cur; 193 cur = cur->next; 194 } 195 196 return 0; 197 } 198 199 static void *buffer_alloc_calloc(size_t n, size_t size) 200 { 201 memory_header *new, *cur = heap.first_free; 202 unsigned char *p; 203 void *ret; 204 size_t original_len, len; 205 #if defined(MBEDTLS_MEMORY_BACKTRACE) 206 void *trace_buffer[MAX_BT]; 207 size_t trace_cnt; 208 #endif 209 210 if (heap.buf == NULL || heap.first == NULL) { 211 return NULL; 212 } 213 214 original_len = len = n * size; 215 216 if (n == 0 || size == 0 || len / n != size) { 217 return NULL; 218 } else if (len > (size_t) -MBEDTLS_MEMORY_ALIGN_MULTIPLE) { 219 return NULL; 220 } 221 222 if (len % MBEDTLS_MEMORY_ALIGN_MULTIPLE) { 223 len -= len % MBEDTLS_MEMORY_ALIGN_MULTIPLE; 224 len += MBEDTLS_MEMORY_ALIGN_MULTIPLE; 225 } 226 227 // Find block that fits 228 // 229 while (cur != NULL) { 230 if (cur->size >= len) { 231 break; 232 } 233 234 cur = cur->next_free; 235 } 236 237 if (cur == NULL) { 238 return NULL; 239 } 240 241 if (cur->alloc != 0) { 242 #if defined(MBEDTLS_MEMORY_DEBUG) 243 mbedtls_fprintf(stderr, "FATAL: block in free_list but allocated " 244 "data\n"); 245 #endif 246 mbedtls_exit(1); 247 } 248 249 #if defined(MBEDTLS_MEMORY_DEBUG) 250 heap.alloc_count++; 251 #endif 252 253 // Found location, split block if > memory_header + 4 room left 254 // 255 if (cur->size - len < sizeof(memory_header) + 256 MBEDTLS_MEMORY_ALIGN_MULTIPLE) { 257 cur->alloc = 1; 258 259 // Remove from free_list 260 // 261 if (cur->prev_free != NULL) { 262 cur->prev_free->next_free = cur->next_free; 263 } else { 264 heap.first_free = cur->next_free; 265 } 266 267 if (cur->next_free != NULL) { 268 cur->next_free->prev_free = cur->prev_free; 269 } 270 271 cur->prev_free = NULL; 272 cur->next_free = NULL; 273 274 #if defined(MBEDTLS_MEMORY_DEBUG) 275 heap.total_used += cur->size; 276 if (heap.total_used > heap.maximum_used) { 277 heap.maximum_used = heap.total_used; 278 } 279 #endif 280 #if defined(MBEDTLS_MEMORY_BACKTRACE) 281 trace_cnt = backtrace(trace_buffer, MAX_BT); 282 cur->trace = backtrace_symbols(trace_buffer, trace_cnt); 283 cur->trace_count = trace_cnt; 284 #endif 285 286 if ((heap.verify & MBEDTLS_MEMORY_VERIFY_ALLOC) && verify_chain() != 0) { 287 mbedtls_exit(1); 288 } 289 290 ret = (unsigned char *) cur + sizeof(memory_header); 291 memset(ret, 0, original_len); 292 293 return ret; 294 } 295 296 p = ((unsigned char *) cur) + sizeof(memory_header) + len; 297 new = (memory_header *) p; 298 299 new->size = cur->size - len - sizeof(memory_header); 300 new->alloc = 0; 301 new->prev = cur; 302 new->next = cur->next; 303 #if defined(MBEDTLS_MEMORY_BACKTRACE) 304 new->trace = NULL; 305 new->trace_count = 0; 306 #endif 307 new->magic1 = MAGIC1; 308 new->magic2 = MAGIC2; 309 310 if (new->next != NULL) { 311 new->next->prev = new; 312 } 313 314 // Replace cur with new in free_list 315 // 316 new->prev_free = cur->prev_free; 317 new->next_free = cur->next_free; 318 if (new->prev_free != NULL) { 319 new->prev_free->next_free = new; 320 } else { 321 heap.first_free = new; 322 } 323 324 if (new->next_free != NULL) { 325 new->next_free->prev_free = new; 326 } 327 328 cur->alloc = 1; 329 cur->size = len; 330 cur->next = new; 331 cur->prev_free = NULL; 332 cur->next_free = NULL; 333 334 #if defined(MBEDTLS_MEMORY_DEBUG) 335 heap.header_count++; 336 if (heap.header_count > heap.maximum_header_count) { 337 heap.maximum_header_count = heap.header_count; 338 } 339 heap.total_used += cur->size; 340 if (heap.total_used > heap.maximum_used) { 341 heap.maximum_used = heap.total_used; 342 } 343 #endif 344 #if defined(MBEDTLS_MEMORY_BACKTRACE) 345 trace_cnt = backtrace(trace_buffer, MAX_BT); 346 cur->trace = backtrace_symbols(trace_buffer, trace_cnt); 347 cur->trace_count = trace_cnt; 348 #endif 349 350 if ((heap.verify & MBEDTLS_MEMORY_VERIFY_ALLOC) && verify_chain() != 0) { 351 mbedtls_exit(1); 352 } 353 354 ret = (unsigned char *) cur + sizeof(memory_header); 355 memset(ret, 0, original_len); 356 357 return ret; 358 } 359 360 static void buffer_alloc_free(void *ptr) 361 { 362 memory_header *hdr, *old = NULL; 363 unsigned char *p = (unsigned char *) ptr; 364 365 if (ptr == NULL || heap.buf == NULL || heap.first == NULL) { 366 return; 367 } 368 369 if (p < heap.buf || p >= heap.buf + heap.len) { 370 #if defined(MBEDTLS_MEMORY_DEBUG) 371 mbedtls_fprintf(stderr, "FATAL: mbedtls_free() outside of managed " 372 "space\n"); 373 #endif 374 mbedtls_exit(1); 375 } 376 377 p -= sizeof(memory_header); 378 hdr = (memory_header *) p; 379 380 if (verify_header(hdr) != 0) { 381 mbedtls_exit(1); 382 } 383 384 if (hdr->alloc != 1) { 385 #if defined(MBEDTLS_MEMORY_DEBUG) 386 mbedtls_fprintf(stderr, "FATAL: mbedtls_free() on unallocated " 387 "data\n"); 388 #endif 389 mbedtls_exit(1); 390 } 391 392 hdr->alloc = 0; 393 394 #if defined(MBEDTLS_MEMORY_DEBUG) 395 heap.free_count++; 396 heap.total_used -= hdr->size; 397 #endif 398 399 #if defined(MBEDTLS_MEMORY_BACKTRACE) 400 free(hdr->trace); 401 hdr->trace = NULL; 402 hdr->trace_count = 0; 403 #endif 404 405 // Regroup with block before 406 // 407 if (hdr->prev != NULL && hdr->prev->alloc == 0) { 408 #if defined(MBEDTLS_MEMORY_DEBUG) 409 heap.header_count--; 410 #endif 411 hdr->prev->size += sizeof(memory_header) + hdr->size; 412 hdr->prev->next = hdr->next; 413 old = hdr; 414 hdr = hdr->prev; 415 416 if (hdr->next != NULL) { 417 hdr->next->prev = hdr; 418 } 419 420 memset(old, 0, sizeof(memory_header)); 421 } 422 423 // Regroup with block after 424 // 425 if (hdr->next != NULL && hdr->next->alloc == 0) { 426 #if defined(MBEDTLS_MEMORY_DEBUG) 427 heap.header_count--; 428 #endif 429 hdr->size += sizeof(memory_header) + hdr->next->size; 430 old = hdr->next; 431 hdr->next = hdr->next->next; 432 433 if (hdr->prev_free != NULL || hdr->next_free != NULL) { 434 if (hdr->prev_free != NULL) { 435 hdr->prev_free->next_free = hdr->next_free; 436 } else { 437 heap.first_free = hdr->next_free; 438 } 439 440 if (hdr->next_free != NULL) { 441 hdr->next_free->prev_free = hdr->prev_free; 442 } 443 } 444 445 hdr->prev_free = old->prev_free; 446 hdr->next_free = old->next_free; 447 448 if (hdr->prev_free != NULL) { 449 hdr->prev_free->next_free = hdr; 450 } else { 451 heap.first_free = hdr; 452 } 453 454 if (hdr->next_free != NULL) { 455 hdr->next_free->prev_free = hdr; 456 } 457 458 if (hdr->next != NULL) { 459 hdr->next->prev = hdr; 460 } 461 462 memset(old, 0, sizeof(memory_header)); 463 } 464 465 // Prepend to free_list if we have not merged 466 // (Does not have to stay in same order as prev / next list) 467 // 468 if (old == NULL) { 469 hdr->next_free = heap.first_free; 470 if (heap.first_free != NULL) { 471 heap.first_free->prev_free = hdr; 472 } 473 heap.first_free = hdr; 474 } 475 476 if ((heap.verify & MBEDTLS_MEMORY_VERIFY_FREE) && verify_chain() != 0) { 477 mbedtls_exit(1); 478 } 479 } 480 481 void mbedtls_memory_buffer_set_verify(int verify) 482 { 483 heap.verify = verify; 484 } 485 486 int mbedtls_memory_buffer_alloc_verify(void) 487 { 488 return verify_chain(); 489 } 490 491 #if defined(MBEDTLS_MEMORY_DEBUG) 492 void mbedtls_memory_buffer_alloc_status(void) 493 { 494 mbedtls_fprintf(stderr, 495 "Current use: %zu blocks / %zu bytes, max: %zu blocks / " 496 "%zu bytes (total %zu bytes), alloc / free: %zu / %zu\n", 497 heap.header_count, heap.total_used, 498 heap.maximum_header_count, heap.maximum_used, 499 heap.maximum_header_count * sizeof(memory_header) 500 + heap.maximum_used, 501 heap.alloc_count, heap.free_count); 502 503 if (heap.first->next == NULL) { 504 mbedtls_fprintf(stderr, "All memory de-allocated in stack buffer\n"); 505 } else { 506 mbedtls_fprintf(stderr, "Memory currently allocated:\n"); 507 debug_chain(); 508 } 509 } 510 511 void mbedtls_memory_buffer_alloc_count_get(size_t *alloc_count, size_t *free_count) 512 { 513 *alloc_count = heap.alloc_count; 514 *free_count = heap.free_count; 515 } 516 517 void mbedtls_memory_buffer_alloc_max_get(size_t *max_used, size_t *max_blocks) 518 { 519 *max_used = heap.maximum_used; 520 *max_blocks = heap.maximum_header_count; 521 } 522 523 void mbedtls_memory_buffer_alloc_max_reset(void) 524 { 525 heap.maximum_used = 0; 526 heap.maximum_header_count = 0; 527 } 528 529 void mbedtls_memory_buffer_alloc_cur_get(size_t *cur_used, size_t *cur_blocks) 530 { 531 *cur_used = heap.total_used; 532 *cur_blocks = heap.header_count; 533 } 534 #endif /* MBEDTLS_MEMORY_DEBUG */ 535 536 #if defined(MBEDTLS_THREADING_C) 537 static void *buffer_alloc_calloc_mutexed(size_t n, size_t size) 538 { 539 void *buf; 540 if (mbedtls_mutex_lock(&heap.mutex) != 0) { 541 return NULL; 542 } 543 buf = buffer_alloc_calloc(n, size); 544 if (mbedtls_mutex_unlock(&heap.mutex)) { 545 return NULL; 546 } 547 return buf; 548 } 549 550 static void buffer_alloc_free_mutexed(void *ptr) 551 { 552 /* We have no good option here, but corrupting the heap seems 553 * worse than losing memory. */ 554 if (mbedtls_mutex_lock(&heap.mutex)) { 555 return; 556 } 557 buffer_alloc_free(ptr); 558 (void) mbedtls_mutex_unlock(&heap.mutex); 559 } 560 #endif /* MBEDTLS_THREADING_C */ 561 562 void mbedtls_memory_buffer_alloc_init(unsigned char *buf, size_t len) 563 { 564 memset(&heap, 0, sizeof(buffer_alloc_ctx)); 565 566 #if defined(MBEDTLS_THREADING_C) 567 mbedtls_mutex_init(&heap.mutex); 568 mbedtls_platform_set_calloc_free(buffer_alloc_calloc_mutexed, 569 buffer_alloc_free_mutexed); 570 #else 571 mbedtls_platform_set_calloc_free(buffer_alloc_calloc, buffer_alloc_free); 572 #endif 573 574 if (len < sizeof(memory_header) + MBEDTLS_MEMORY_ALIGN_MULTIPLE) { 575 return; 576 } else if ((size_t) buf % MBEDTLS_MEMORY_ALIGN_MULTIPLE) { 577 /* Adjust len first since buf is used in the computation */ 578 len -= MBEDTLS_MEMORY_ALIGN_MULTIPLE 579 - (size_t) buf % MBEDTLS_MEMORY_ALIGN_MULTIPLE; 580 buf += MBEDTLS_MEMORY_ALIGN_MULTIPLE 581 - (size_t) buf % MBEDTLS_MEMORY_ALIGN_MULTIPLE; 582 } 583 584 memset(buf, 0, len); 585 586 heap.buf = buf; 587 heap.len = len; 588 589 heap.first = (memory_header *) buf; 590 heap.first->size = len - sizeof(memory_header); 591 heap.first->magic1 = MAGIC1; 592 heap.first->magic2 = MAGIC2; 593 heap.first_free = heap.first; 594 } 595 596 void mbedtls_memory_buffer_alloc_free(void) 597 { 598 #if defined(MBEDTLS_THREADING_C) 599 mbedtls_mutex_free(&heap.mutex); 600 #endif 601 mbedtls_platform_zeroize(&heap, sizeof(buffer_alloc_ctx)); 602 } 603 604 #if defined(MBEDTLS_SELF_TEST) 605 static int check_pointer(void *p) 606 { 607 if (p == NULL) { 608 return -1; 609 } 610 611 if ((size_t) p % MBEDTLS_MEMORY_ALIGN_MULTIPLE != 0) { 612 return -1; 613 } 614 615 return 0; 616 } 617 618 static int check_all_free(void) 619 { 620 if ( 621 #if defined(MBEDTLS_MEMORY_DEBUG) 622 heap.total_used != 0 || 623 #endif 624 heap.first != heap.first_free || 625 (void *) heap.first != (void *) heap.buf) { 626 return -1; 627 } 628 629 return 0; 630 } 631 632 #define TEST_ASSERT(condition) \ 633 if (!(condition)) \ 634 { \ 635 if (verbose != 0) \ 636 mbedtls_printf("failed\n"); \ 637 \ 638 ret = 1; \ 639 goto cleanup; \ 640 } 641 642 int mbedtls_memory_buffer_alloc_self_test(int verbose) 643 { 644 unsigned char buf[1024]; 645 unsigned char *p, *q, *r, *end; 646 int ret = 0; 647 648 if (verbose != 0) { 649 mbedtls_printf(" MBA test #1 (basic alloc-free cycle): "); 650 } 651 652 mbedtls_memory_buffer_alloc_init(buf, sizeof(buf)); 653 654 p = mbedtls_calloc(1, 1); 655 q = mbedtls_calloc(1, 128); 656 r = mbedtls_calloc(1, 16); 657 658 TEST_ASSERT(check_pointer(p) == 0 && 659 check_pointer(q) == 0 && 660 check_pointer(r) == 0); 661 662 mbedtls_free(r); 663 mbedtls_free(q); 664 mbedtls_free(p); 665 666 TEST_ASSERT(check_all_free() == 0); 667 668 /* Memorize end to compare with the next test */ 669 end = heap.buf + heap.len; 670 671 mbedtls_memory_buffer_alloc_free(); 672 673 if (verbose != 0) { 674 mbedtls_printf("passed\n"); 675 } 676 677 if (verbose != 0) { 678 mbedtls_printf(" MBA test #2 (buf not aligned): "); 679 } 680 681 mbedtls_memory_buffer_alloc_init(buf + 1, sizeof(buf) - 1); 682 683 TEST_ASSERT(heap.buf + heap.len == end); 684 685 p = mbedtls_calloc(1, 1); 686 q = mbedtls_calloc(1, 128); 687 r = mbedtls_calloc(1, 16); 688 689 TEST_ASSERT(check_pointer(p) == 0 && 690 check_pointer(q) == 0 && 691 check_pointer(r) == 0); 692 693 mbedtls_free(r); 694 mbedtls_free(q); 695 mbedtls_free(p); 696 697 TEST_ASSERT(check_all_free() == 0); 698 699 mbedtls_memory_buffer_alloc_free(); 700 701 if (verbose != 0) { 702 mbedtls_printf("passed\n"); 703 } 704 705 if (verbose != 0) { 706 mbedtls_printf(" MBA test #3 (full): "); 707 } 708 709 mbedtls_memory_buffer_alloc_init(buf, sizeof(buf)); 710 711 p = mbedtls_calloc(1, sizeof(buf) - sizeof(memory_header)); 712 713 TEST_ASSERT(check_pointer(p) == 0); 714 TEST_ASSERT(mbedtls_calloc(1, 1) == NULL); 715 716 mbedtls_free(p); 717 718 p = mbedtls_calloc(1, sizeof(buf) - 2 * sizeof(memory_header) - 16); 719 q = mbedtls_calloc(1, 16); 720 721 TEST_ASSERT(check_pointer(p) == 0 && check_pointer(q) == 0); 722 TEST_ASSERT(mbedtls_calloc(1, 1) == NULL); 723 724 mbedtls_free(q); 725 726 TEST_ASSERT(mbedtls_calloc(1, 17) == NULL); 727 728 mbedtls_free(p); 729 730 TEST_ASSERT(check_all_free() == 0); 731 732 mbedtls_memory_buffer_alloc_free(); 733 734 if (verbose != 0) { 735 mbedtls_printf("passed\n"); 736 } 737 738 cleanup: 739 mbedtls_memory_buffer_alloc_free(); 740 741 return ret; 742 } 743 #endif /* MBEDTLS_SELF_TEST */ 744 745 #endif /* MBEDTLS_MEMORY_BUFFER_ALLOC_C */