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