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_max_get(size_t *max_used, size_t *max_blocks)
524{
525 *max_used = heap.maximum_used;
526 *max_blocks = heap.maximum_header_count;
527}
528
529void mbedtls_memory_buffer_alloc_max_reset(void)
530{
531 heap.maximum_used = 0;
532 heap.maximum_header_count = 0;
533}
534
535void mbedtls_memory_buffer_alloc_cur_get(size_t *cur_used, size_t *cur_blocks)
536{
537 *cur_used = heap.total_used;
538 *cur_blocks = heap.header_count;
539}
540#endif /* MBEDTLS_MEMORY_DEBUG */
541
542#if defined(MBEDTLS_THREADING_C)
543static void *buffer_alloc_calloc_mutexed(size_t n, size_t size)
544{
545 void *buf;
546 if (mbedtls_mutex_lock(&heap.mutex) != 0) {
547 return NULL;
548 }
549 buf = buffer_alloc_calloc(n, size);
550 if (mbedtls_mutex_unlock(&heap.mutex)) {
551 return NULL;
552 }
553 return buf;
554}
555
556static void buffer_alloc_free_mutexed(void *ptr)
557{
558 /* We have no good option here, but corrupting the heap seems
559 * worse than losing memory. */
560 if (mbedtls_mutex_lock(&heap.mutex)) {
561 return;
562 }
563 buffer_alloc_free(ptr);
564 (void) mbedtls_mutex_unlock(&heap.mutex);
565}
566#endif /* MBEDTLS_THREADING_C */
567
568void mbedtls_memory_buffer_alloc_init(unsigned char *buf, size_t len)
569{
570 memset(&heap, 0, sizeof(buffer_alloc_ctx));
571
572#if defined(MBEDTLS_THREADING_C)
573 mbedtls_mutex_init(&heap.mutex);
574 mbedtls_platform_set_calloc_free(buffer_alloc_calloc_mutexed,
575 buffer_alloc_free_mutexed);
576#else
577 mbedtls_platform_set_calloc_free(buffer_alloc_calloc, buffer_alloc_free);
578#endif
579
580 if (len < sizeof(memory_header) + MBEDTLS_MEMORY_ALIGN_MULTIPLE) {
581 return;
582 } else if ((size_t) buf % MBEDTLS_MEMORY_ALIGN_MULTIPLE) {
583 /* Adjust len first since buf is used in the computation */
584 len -= MBEDTLS_MEMORY_ALIGN_MULTIPLE
585 - (size_t) buf % MBEDTLS_MEMORY_ALIGN_MULTIPLE;
586 buf += MBEDTLS_MEMORY_ALIGN_MULTIPLE
587 - (size_t) buf % MBEDTLS_MEMORY_ALIGN_MULTIPLE;
588 }
589
590 memset(buf, 0, len);
591
592 heap.buf = buf;
593 heap.len = len;
594
595 heap.first = (memory_header *) buf;
596 heap.first->size = len - sizeof(memory_header);
597 heap.first->magic1 = MAGIC1;
598 heap.first->magic2 = MAGIC2;
599 heap.first_free = heap.first;
600}
601
602void mbedtls_memory_buffer_alloc_free(void)
603{
604#if defined(MBEDTLS_THREADING_C)
605 mbedtls_mutex_free(&heap.mutex);
606#endif
607 mbedtls_platform_zeroize(&heap, sizeof(buffer_alloc_ctx));
608}
609
610#if defined(MBEDTLS_SELF_TEST)
611static int check_pointer(void *p)
612{
613 if (p == NULL) {
614 return -1;
615 }
616
617 if ((size_t) p % MBEDTLS_MEMORY_ALIGN_MULTIPLE != 0) {
618 return -1;
619 }
620
621 return 0;
622}
623
624static int check_all_free(void)
625{
626 if (
627#if defined(MBEDTLS_MEMORY_DEBUG)
628 heap.total_used != 0 ||
629#endif
630 heap.first != heap.first_free ||
631 (void *) heap.first != (void *) heap.buf) {
632 return -1;
633 }
634
635 return 0;
636}
637
638#define TEST_ASSERT(condition) \
639 if (!(condition)) \
640 { \
641 if (verbose != 0) \
642 mbedtls_printf("failed\n"); \
643 \
644 ret = 1; \
645 goto cleanup; \
646 }
647
648int mbedtls_memory_buffer_alloc_self_test(int verbose)
649{
650 unsigned char buf[1024];
651 unsigned char *p, *q, *r, *end;
652 int ret = 0;
653
654 if (verbose != 0) {
655 mbedtls_printf(" MBA test #1 (basic alloc-free cycle): ");
656 }
657
658 mbedtls_memory_buffer_alloc_init(buf, sizeof(buf));
659
660 p = mbedtls_calloc(1, 1);
661 q = mbedtls_calloc(1, 128);
662 r = mbedtls_calloc(1, 16);
663
664 TEST_ASSERT(check_pointer(p) == 0 &&
665 check_pointer(q) == 0 &&
666 check_pointer(r) == 0);
667
668 mbedtls_free(r);
669 mbedtls_free(q);
670 mbedtls_free(p);
671
672 TEST_ASSERT(check_all_free() == 0);
673
674 /* Memorize end to compare with the next test */
675 end = heap.buf + heap.len;
676
677 mbedtls_memory_buffer_alloc_free();
678
679 if (verbose != 0) {
680 mbedtls_printf("passed\n");
681 }
682
683 if (verbose != 0) {
684 mbedtls_printf(" MBA test #2 (buf not aligned): ");
685 }
686
687 mbedtls_memory_buffer_alloc_init(buf + 1, sizeof(buf) - 1);
688
689 TEST_ASSERT(heap.buf + heap.len == end);
690
691 p = mbedtls_calloc(1, 1);
692 q = mbedtls_calloc(1, 128);
693 r = mbedtls_calloc(1, 16);
694
695 TEST_ASSERT(check_pointer(p) == 0 &&
696 check_pointer(q) == 0 &&
697 check_pointer(r) == 0);
698
699 mbedtls_free(r);
700 mbedtls_free(q);
701 mbedtls_free(p);
702
703 TEST_ASSERT(check_all_free() == 0);
704
705 mbedtls_memory_buffer_alloc_free();
706
707 if (verbose != 0) {
708 mbedtls_printf("passed\n");
709 }
710
711 if (verbose != 0) {
712 mbedtls_printf(" MBA test #3 (full): ");
713 }
714
715 mbedtls_memory_buffer_alloc_init(buf, sizeof(buf));
716
717 p = mbedtls_calloc(1, sizeof(buf) - sizeof(memory_header));
718
719 TEST_ASSERT(check_pointer(p) == 0);
720 TEST_ASSERT(mbedtls_calloc(1, 1) == NULL);
721
722 mbedtls_free(p);
723
724 p = mbedtls_calloc(1, sizeof(buf) - 2 * sizeof(memory_header) - 16);
725 q = mbedtls_calloc(1, 16);
726
727 TEST_ASSERT(check_pointer(p) == 0 && check_pointer(q) == 0);
728 TEST_ASSERT(mbedtls_calloc(1, 1) == NULL);
729
730 mbedtls_free(q);
731
732 TEST_ASSERT(mbedtls_calloc(1, 17) == NULL);
733
734 mbedtls_free(p);
735
736 TEST_ASSERT(check_all_free() == 0);
737
738 mbedtls_memory_buffer_alloc_free();
739
740 if (verbose != 0) {
741 mbedtls_printf("passed\n");
742 }
743
744cleanup:
745 mbedtls_memory_buffer_alloc_free();
746
747 return ret;
748}
749#endif /* MBEDTLS_SELF_TEST */
750
751#endif /* MBEDTLS_MEMORY_BUFFER_ALLOC_C */
752