2 * Buffer-based memory allocator
4 * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved
5 * SPDX-License-Identifier: Apache-2.0
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
11 * http://www.apache.org/licenses/LICENSE-2.0
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.
19 * This file is part of mbed TLS (https://tls.mbed.org)
22 #if !defined(MBEDTLS_CONFIG_FILE)
23 #include "mbedtls/config.h"
25 #include MBEDTLS_CONFIG_FILE
28 #if defined(MBEDTLS_MEMORY_BUFFER_ALLOC_C)
29 #include "mbedtls/memory_buffer_alloc.h"
31 /* No need for the header guard as MBEDTLS_MEMORY_BUFFER_ALLOC_C
32 is dependent upon MBEDTLS_PLATFORM_C */
33 #include "mbedtls/platform.h"
37 #if defined(MBEDTLS_MEMORY_BACKTRACE)
41 #if defined(MBEDTLS_THREADING_C)
42 #include "mbedtls/threading.h"
45 /* Implementation that should never be optimized out by the compiler */
46 static void mbedtls_zeroize( void *v
, size_t n
) {
47 volatile unsigned char *p
= v
; while( n
-- ) *p
++ = 0;
50 #define MAGIC1 0xFF00AA55
51 #define MAGIC2 0xEE119966
54 typedef struct _memory_header memory_header
;
62 memory_header
*prev_free
;
63 memory_header
*next_free
;
64 #if defined(MBEDTLS_MEMORY_BACKTRACE)
76 memory_header
*first_free
;
78 #if defined(MBEDTLS_MEMORY_DEBUG)
84 size_t maximum_header_count
;
86 #if defined(MBEDTLS_THREADING_C)
87 mbedtls_threading_mutex_t mutex
;
92 static buffer_alloc_ctx heap
;
94 #if defined(MBEDTLS_MEMORY_DEBUG)
95 static void debug_header( memory_header
*hdr
)
97 #if defined(MBEDTLS_MEMORY_BACKTRACE)
101 mbedtls_fprintf( stderr
, "HDR: PTR(%10zu), PREV(%10zu), NEXT(%10zu), "
102 "ALLOC(%zu), SIZE(%10zu)\n",
103 (size_t) hdr
, (size_t) hdr
->prev
, (size_t) hdr
->next
,
104 hdr
->alloc
, hdr
->size
);
105 mbedtls_fprintf( stderr
, " FPREV(%10zu), FNEXT(%10zu)\n",
106 (size_t) hdr
->prev_free
, (size_t) hdr
->next_free
);
108 #if defined(MBEDTLS_MEMORY_BACKTRACE)
109 mbedtls_fprintf( stderr
, "TRACE: \n" );
110 for( i
= 0; i
< hdr
->trace_count
; i
++ )
111 mbedtls_fprintf( stderr
, "%s\n", hdr
->trace
[i
] );
112 mbedtls_fprintf( stderr
, "\n" );
116 static void debug_chain()
118 memory_header
*cur
= heap
.first
;
120 mbedtls_fprintf( stderr
, "\nBlock list\n" );
127 mbedtls_fprintf( stderr
, "Free list\n" );
128 cur
= heap
.first_free
;
133 cur
= cur
->next_free
;
136 #endif /* MBEDTLS_MEMORY_DEBUG */
138 static int verify_header( memory_header
*hdr
)
140 if( hdr
->magic1
!= MAGIC1
)
142 #if defined(MBEDTLS_MEMORY_DEBUG)
143 mbedtls_fprintf( stderr
, "FATAL: MAGIC1 mismatch\n" );
148 if( hdr
->magic2
!= MAGIC2
)
150 #if defined(MBEDTLS_MEMORY_DEBUG)
151 mbedtls_fprintf( stderr
, "FATAL: MAGIC2 mismatch\n" );
158 #if defined(MBEDTLS_MEMORY_DEBUG)
159 mbedtls_fprintf( stderr
, "FATAL: alloc has illegal value\n" );
164 if( hdr
->prev
!= NULL
&& hdr
->prev
== hdr
->next
)
166 #if defined(MBEDTLS_MEMORY_DEBUG)
167 mbedtls_fprintf( stderr
, "FATAL: prev == next\n" );
172 if( hdr
->prev_free
!= NULL
&& hdr
->prev_free
== hdr
->next_free
)
174 #if defined(MBEDTLS_MEMORY_DEBUG)
175 mbedtls_fprintf( stderr
, "FATAL: prev_free == next_free\n" );
183 static int verify_chain()
185 memory_header
*prv
= heap
.first
, *cur
= heap
.first
->next
;
187 if( verify_header( heap
.first
) != 0 )
189 #if defined(MBEDTLS_MEMORY_DEBUG)
190 mbedtls_fprintf( stderr
, "FATAL: verification of first header "
196 if( heap
.first
->prev
!= NULL
)
198 #if defined(MBEDTLS_MEMORY_DEBUG)
199 mbedtls_fprintf( stderr
, "FATAL: verification failed: "
200 "first->prev != NULL\n" );
207 if( verify_header( cur
) != 0 )
209 #if defined(MBEDTLS_MEMORY_DEBUG)
210 mbedtls_fprintf( stderr
, "FATAL: verification of header "
216 if( cur
->prev
!= prv
)
218 #if defined(MBEDTLS_MEMORY_DEBUG)
219 mbedtls_fprintf( stderr
, "FATAL: verification failed: "
220 "cur->prev != prv\n" );
232 static void *buffer_alloc_calloc( size_t n
, size_t size
)
234 memory_header
*new, *cur
= heap
.first_free
;
237 size_t original_len
, len
;
238 #if defined(MBEDTLS_MEMORY_BACKTRACE)
239 void *trace_buffer
[MAX_BT
];
243 if( heap
.buf
== NULL
|| heap
.first
== NULL
)
246 original_len
= len
= n
* size
;
248 if( n
!= 0 && len
/ n
!= size
)
251 if( len
% MBEDTLS_MEMORY_ALIGN_MULTIPLE
)
253 len
-= len
% MBEDTLS_MEMORY_ALIGN_MULTIPLE
;
254 len
+= MBEDTLS_MEMORY_ALIGN_MULTIPLE
;
257 // Find block that fits
261 if( cur
->size
>= len
)
264 cur
= cur
->next_free
;
270 if( cur
->alloc
!= 0 )
272 #if defined(MBEDTLS_MEMORY_DEBUG)
273 mbedtls_fprintf( stderr
, "FATAL: block in free_list but allocated "
279 #if defined(MBEDTLS_MEMORY_DEBUG)
283 // Found location, split block if > memory_header + 4 room left
285 if( cur
->size
- len
< sizeof(memory_header
) +
286 MBEDTLS_MEMORY_ALIGN_MULTIPLE
)
290 // Remove from free_list
292 if( cur
->prev_free
!= NULL
)
293 cur
->prev_free
->next_free
= cur
->next_free
;
295 heap
.first_free
= cur
->next_free
;
297 if( cur
->next_free
!= NULL
)
298 cur
->next_free
->prev_free
= cur
->prev_free
;
300 cur
->prev_free
= NULL
;
301 cur
->next_free
= NULL
;
303 #if defined(MBEDTLS_MEMORY_DEBUG)
304 heap
.total_used
+= cur
->size
;
305 if( heap
.total_used
> heap
.maximum_used
)
306 heap
.maximum_used
= heap
.total_used
;
308 #if defined(MBEDTLS_MEMORY_BACKTRACE)
309 trace_cnt
= backtrace( trace_buffer
, MAX_BT
);
310 cur
->trace
= backtrace_symbols( trace_buffer
, trace_cnt
);
311 cur
->trace_count
= trace_cnt
;
314 if( ( heap
.verify
& MBEDTLS_MEMORY_VERIFY_ALLOC
) && verify_chain() != 0 )
317 ret
= (unsigned char *) cur
+ sizeof( memory_header
);
318 memset( ret
, 0, original_len
);
323 p
= ( (unsigned char *) cur
) + sizeof(memory_header
) + len
;
324 new = (memory_header
*) p
;
326 new->size
= cur
->size
- len
- sizeof(memory_header
);
329 new->next
= cur
->next
;
330 #if defined(MBEDTLS_MEMORY_BACKTRACE)
332 new->trace_count
= 0;
334 new->magic1
= MAGIC1
;
335 new->magic2
= MAGIC2
;
337 if( new->next
!= NULL
)
338 new->next
->prev
= new;
340 // Replace cur with new in free_list
342 new->prev_free
= cur
->prev_free
;
343 new->next_free
= cur
->next_free
;
344 if( new->prev_free
!= NULL
)
345 new->prev_free
->next_free
= new;
347 heap
.first_free
= new;
349 if( new->next_free
!= NULL
)
350 new->next_free
->prev_free
= new;
355 cur
->prev_free
= NULL
;
356 cur
->next_free
= NULL
;
358 #if defined(MBEDTLS_MEMORY_DEBUG)
360 if( heap
.header_count
> heap
.maximum_header_count
)
361 heap
.maximum_header_count
= heap
.header_count
;
362 heap
.total_used
+= cur
->size
;
363 if( heap
.total_used
> heap
.maximum_used
)
364 heap
.maximum_used
= heap
.total_used
;
366 #if defined(MBEDTLS_MEMORY_BACKTRACE)
367 trace_cnt
= backtrace( trace_buffer
, MAX_BT
);
368 cur
->trace
= backtrace_symbols( trace_buffer
, trace_cnt
);
369 cur
->trace_count
= trace_cnt
;
372 if( ( heap
.verify
& MBEDTLS_MEMORY_VERIFY_ALLOC
) && verify_chain() != 0 )
375 ret
= (unsigned char *) cur
+ sizeof( memory_header
);
376 memset( ret
, 0, original_len
);
381 static void buffer_alloc_free( void *ptr
)
383 memory_header
*hdr
, *old
= NULL
;
384 unsigned char *p
= (unsigned char *) ptr
;
386 if( ptr
== NULL
|| heap
.buf
== NULL
|| heap
.first
== NULL
)
389 if( p
< heap
.buf
|| p
> heap
.buf
+ heap
.len
)
391 #if defined(MBEDTLS_MEMORY_DEBUG)
392 mbedtls_fprintf( stderr
, "FATAL: mbedtls_free() outside of managed "
398 p
-= sizeof(memory_header
);
399 hdr
= (memory_header
*) p
;
401 if( verify_header( hdr
) != 0 )
404 if( hdr
->alloc
!= 1 )
406 #if defined(MBEDTLS_MEMORY_DEBUG)
407 mbedtls_fprintf( stderr
, "FATAL: mbedtls_free() on unallocated "
415 #if defined(MBEDTLS_MEMORY_DEBUG)
417 heap
.total_used
-= hdr
->size
;
420 #if defined(MBEDTLS_MEMORY_BACKTRACE)
423 hdr
->trace_count
= 0;
426 // Regroup with block before
428 if( hdr
->prev
!= NULL
&& hdr
->prev
->alloc
== 0 )
430 #if defined(MBEDTLS_MEMORY_DEBUG)
433 hdr
->prev
->size
+= sizeof(memory_header
) + hdr
->size
;
434 hdr
->prev
->next
= hdr
->next
;
438 if( hdr
->next
!= NULL
)
439 hdr
->next
->prev
= hdr
;
441 memset( old
, 0, sizeof(memory_header
) );
444 // Regroup with block after
446 if( hdr
->next
!= NULL
&& hdr
->next
->alloc
== 0 )
448 #if defined(MBEDTLS_MEMORY_DEBUG)
451 hdr
->size
+= sizeof(memory_header
) + hdr
->next
->size
;
453 hdr
->next
= hdr
->next
->next
;
455 if( hdr
->prev_free
!= NULL
|| hdr
->next_free
!= NULL
)
457 if( hdr
->prev_free
!= NULL
)
458 hdr
->prev_free
->next_free
= hdr
->next_free
;
460 heap
.first_free
= hdr
->next_free
;
462 if( hdr
->next_free
!= NULL
)
463 hdr
->next_free
->prev_free
= hdr
->prev_free
;
466 hdr
->prev_free
= old
->prev_free
;
467 hdr
->next_free
= old
->next_free
;
469 if( hdr
->prev_free
!= NULL
)
470 hdr
->prev_free
->next_free
= hdr
;
472 heap
.first_free
= hdr
;
474 if( hdr
->next_free
!= NULL
)
475 hdr
->next_free
->prev_free
= hdr
;
477 if( hdr
->next
!= NULL
)
478 hdr
->next
->prev
= hdr
;
480 memset( old
, 0, sizeof(memory_header
) );
483 // Prepend to free_list if we have not merged
484 // (Does not have to stay in same order as prev / next list)
488 hdr
->next_free
= heap
.first_free
;
489 if( heap
.first_free
!= NULL
)
490 heap
.first_free
->prev_free
= hdr
;
491 heap
.first_free
= hdr
;
494 if( ( heap
.verify
& MBEDTLS_MEMORY_VERIFY_FREE
) && verify_chain() != 0 )
498 void mbedtls_memory_buffer_set_verify( int verify
)
500 heap
.verify
= verify
;
503 int mbedtls_memory_buffer_alloc_verify()
505 return verify_chain();
508 #if defined(MBEDTLS_MEMORY_DEBUG)
509 void mbedtls_memory_buffer_alloc_status()
511 mbedtls_fprintf( stderr
,
512 "Current use: %zu blocks / %zu bytes, max: %zu blocks / "
513 "%zu bytes (total %zu bytes), alloc / free: %zu / %zu\n",
514 heap
.header_count
, heap
.total_used
,
515 heap
.maximum_header_count
, heap
.maximum_used
,
516 heap
.maximum_header_count
* sizeof( memory_header
)
518 heap
.alloc_count
, heap
.free_count
);
520 if( heap
.first
->next
== NULL
)
521 mbedtls_fprintf( stderr
, "All memory de-allocated in stack buffer\n" );
524 mbedtls_fprintf( stderr
, "Memory currently allocated:\n" );
529 void mbedtls_memory_buffer_alloc_max_get( size_t *max_used
, size_t *max_blocks
)
531 *max_used
= heap
.maximum_used
;
532 *max_blocks
= heap
.maximum_header_count
;
535 void mbedtls_memory_buffer_alloc_max_reset( void )
537 heap
.maximum_used
= 0;
538 heap
.maximum_header_count
= 0;
541 void mbedtls_memory_buffer_alloc_cur_get( size_t *cur_used
, size_t *cur_blocks
)
543 *cur_used
= heap
.total_used
;
544 *cur_blocks
= heap
.header_count
;
546 #endif /* MBEDTLS_MEMORY_DEBUG */
548 #if defined(MBEDTLS_THREADING_C)
549 static void *buffer_alloc_calloc_mutexed( size_t n
, size_t size
)
552 if( mbedtls_mutex_lock( &heap
.mutex
) != 0 )
554 buf
= buffer_alloc_calloc( n
, size
);
555 if( mbedtls_mutex_unlock( &heap
.mutex
) )
560 static void buffer_alloc_free_mutexed( void *ptr
)
562 /* We have to good option here, but corrupting the heap seems
563 * worse than loosing memory. */
564 if( mbedtls_mutex_lock( &heap
.mutex
) )
566 buffer_alloc_free( ptr
);
567 (void) mbedtls_mutex_unlock( &heap
.mutex
);
569 #endif /* MBEDTLS_THREADING_C */
571 void mbedtls_memory_buffer_alloc_init( unsigned char *buf
, size_t len
)
573 memset( &heap
, 0, sizeof(buffer_alloc_ctx
) );
574 memset( buf
, 0, len
);
576 #if defined(MBEDTLS_THREADING_C)
577 mbedtls_mutex_init( &heap
.mutex
);
578 mbedtls_platform_set_calloc_free( buffer_alloc_calloc_mutexed
,
579 buffer_alloc_free_mutexed
);
581 mbedtls_platform_set_calloc_free( buffer_alloc_calloc
, buffer_alloc_free
);
584 if( (size_t) buf
% MBEDTLS_MEMORY_ALIGN_MULTIPLE
)
586 /* Adjust len first since buf is used in the computation */
587 len
-= MBEDTLS_MEMORY_ALIGN_MULTIPLE
588 - (size_t) buf
% MBEDTLS_MEMORY_ALIGN_MULTIPLE
;
589 buf
+= MBEDTLS_MEMORY_ALIGN_MULTIPLE
590 - (size_t) buf
% MBEDTLS_MEMORY_ALIGN_MULTIPLE
;
596 heap
.first
= (memory_header
*) buf
;
597 heap
.first
->size
= len
- sizeof(memory_header
);
598 heap
.first
->magic1
= MAGIC1
;
599 heap
.first
->magic2
= MAGIC2
;
600 heap
.first_free
= heap
.first
;
603 void mbedtls_memory_buffer_alloc_free()
605 #if defined(MBEDTLS_THREADING_C)
606 mbedtls_mutex_free( &heap
.mutex
);
608 mbedtls_zeroize( &heap
, sizeof(buffer_alloc_ctx
) );
611 #if defined(MBEDTLS_SELF_TEST)
612 static int check_pointer( void *p
)
617 if( (size_t) p
% MBEDTLS_MEMORY_ALIGN_MULTIPLE
!= 0 )
623 static int check_all_free( )
626 #if defined(MBEDTLS_MEMORY_DEBUG)
627 heap
.total_used
!= 0 ||
629 heap
.first
!= heap
.first_free
||
630 (void *) heap
.first
!= (void *) heap
.buf
)
638 #define TEST_ASSERT( condition ) \
639 if( ! (condition) ) \
642 mbedtls_printf( "failed\n" ); \
648 int mbedtls_memory_buffer_alloc_self_test( int verbose
)
650 unsigned char buf
[1024];
651 unsigned char *p
, *q
, *r
, *end
;
655 mbedtls_printf( " MBA test #1 (basic alloc-free cycle): " );
657 mbedtls_memory_buffer_alloc_init( buf
, sizeof( buf
) );
659 p
= mbedtls_calloc( 1, 1 );
660 q
= mbedtls_calloc( 1, 128 );
661 r
= mbedtls_calloc( 1, 16 );
663 TEST_ASSERT( check_pointer( p
) == 0 &&
664 check_pointer( q
) == 0 &&
665 check_pointer( r
) == 0 );
671 TEST_ASSERT( check_all_free( ) == 0 );
673 /* Memorize end to compare with the next test */
674 end
= heap
.buf
+ heap
.len
;
676 mbedtls_memory_buffer_alloc_free( );
679 mbedtls_printf( "passed\n" );
682 mbedtls_printf( " MBA test #2 (buf not aligned): " );
684 mbedtls_memory_buffer_alloc_init( buf
+ 1, sizeof( buf
) - 1 );
686 TEST_ASSERT( heap
.buf
+ heap
.len
== end
);
688 p
= mbedtls_calloc( 1, 1 );
689 q
= mbedtls_calloc( 1, 128 );
690 r
= mbedtls_calloc( 1, 16 );
692 TEST_ASSERT( check_pointer( p
) == 0 &&
693 check_pointer( q
) == 0 &&
694 check_pointer( r
) == 0 );
700 TEST_ASSERT( check_all_free( ) == 0 );
702 mbedtls_memory_buffer_alloc_free( );
705 mbedtls_printf( "passed\n" );
708 mbedtls_printf( " MBA test #3 (full): " );
710 mbedtls_memory_buffer_alloc_init( buf
, sizeof( buf
) );
712 p
= mbedtls_calloc( 1, sizeof( buf
) - sizeof( memory_header
) );
714 TEST_ASSERT( check_pointer( p
) == 0 );
715 TEST_ASSERT( mbedtls_calloc( 1, 1 ) == NULL
);
719 p
= mbedtls_calloc( 1, sizeof( buf
) - 2 * sizeof( memory_header
) - 16 );
720 q
= mbedtls_calloc( 1, 16 );
722 TEST_ASSERT( check_pointer( p
) == 0 && check_pointer( q
) == 0 );
723 TEST_ASSERT( mbedtls_calloc( 1, 1 ) == NULL
);
727 TEST_ASSERT( mbedtls_calloc( 1, 17 ) == NULL
);
731 TEST_ASSERT( check_all_free( ) == 0 );
733 mbedtls_memory_buffer_alloc_free( );
736 mbedtls_printf( "passed\n" );
739 mbedtls_memory_buffer_alloc_free( );
743 #endif /* MBEDTLS_SELF_TEST */
745 #endif /* MBEDTLS_MEMORY_BUFFER_ALLOC_C */