00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #include "polarssl/config.h"
00027
00028 #if defined(POLARSSL_MEMORY_C) && defined(POLARSSL_MEMORY_BUFFER_ALLOC_C)
00029
00030 #include "polarssl/memory.h"
00031
00032 #include <string.h>
00033
00034 #if defined(POLARSSL_MEMORY_DEBUG)
00035 #include <stdio.h>
00036 #if defined(POLARSSL_MEMORY_BACKTRACE)
00037 #include <execinfo.h>
00038 #endif
00039 #endif
00040
00041 #if defined(POLARSSL_THREADING_C)
00042 #include "polarssl/threading.h"
00043 #endif
00044
00045 #define MAGIC1 0xFF00AA55
00046 #define MAGIC2 0xEE119966
00047 #define MAX_BT 20
00048
00049 typedef struct _memory_header memory_header;
00050 struct _memory_header
00051 {
00052 size_t magic1;
00053 size_t size;
00054 size_t alloc;
00055 memory_header *prev;
00056 memory_header *next;
00057 memory_header *prev_free;
00058 memory_header *next_free;
00059 #if defined(POLARSSL_MEMORY_BACKTRACE)
00060 char **trace;
00061 size_t trace_count;
00062 #endif
00063 size_t magic2;
00064 };
00065
00066 typedef struct
00067 {
00068 unsigned char *buf;
00069 size_t len;
00070 memory_header *first;
00071 memory_header *first_free;
00072 size_t current_alloc_size;
00073 int verify;
00074 #if defined(POLARSSL_MEMORY_DEBUG)
00075 size_t malloc_count;
00076 size_t free_count;
00077 size_t total_used;
00078 size_t maximum_used;
00079 size_t header_count;
00080 #endif
00081 #if defined(POLARSSL_THREADING_C)
00082 threading_mutex_t mutex;
00083 #endif
00084 }
00085 buffer_alloc_ctx;
00086
00087 static buffer_alloc_ctx heap;
00088
00089 #if defined(POLARSSL_MEMORY_DEBUG)
00090 static void debug_header( memory_header *hdr )
00091 {
00092 #if defined(POLARSSL_MEMORY_BACKTRACE)
00093 size_t i;
00094 #endif
00095
00096 fprintf( stderr, "HDR: PTR(%10u), PREV(%10u), NEXT(%10u), ALLOC(%u), SIZE(%10u)\n",
00097 (size_t) hdr, (size_t) hdr->prev, (size_t) hdr->next,
00098 hdr->alloc, hdr->size );
00099 fprintf( stderr, " FPREV(%10u), FNEXT(%10u)\n",
00100 (size_t) hdr->prev_free, (size_t) hdr->next_free );
00101
00102 #if defined(POLARSSL_MEMORY_BACKTRACE)
00103 fprintf( stderr, "TRACE: \n" );
00104 for( i = 0; i < hdr->trace_count; i++ )
00105 fprintf( stderr, "%s\n", hdr->trace[i] );
00106 fprintf( stderr, "\n" );
00107 #endif
00108 }
00109
00110 static void debug_chain()
00111 {
00112 memory_header *cur = heap.first;
00113
00114 fprintf( stderr, "\nBlock list\n" );
00115 while( cur != NULL )
00116 {
00117 debug_header( cur );
00118 cur = cur->next;
00119 }
00120
00121 fprintf( stderr, "Free list\n" );
00122 cur = heap.first_free;
00123
00124 while( cur != NULL )
00125 {
00126 debug_header( cur );
00127 cur = cur->next_free;
00128 }
00129 }
00130 #endif
00131
00132 static int verify_header( memory_header *hdr )
00133 {
00134 if( hdr->magic1 != MAGIC1 )
00135 {
00136 #if defined(POLARSSL_MEMORY_DEBUG)
00137 fprintf( stderr, "FATAL: MAGIC1 mismatch\n" );
00138 #endif
00139 return( 1 );
00140 }
00141
00142 if( hdr->magic2 != MAGIC2 )
00143 {
00144 #if defined(POLARSSL_MEMORY_DEBUG)
00145 fprintf( stderr, "FATAL: MAGIC2 mismatch\n" );
00146 #endif
00147 return( 1 );
00148 }
00149
00150 if( hdr->alloc > 1 )
00151 {
00152 #if defined(POLARSSL_MEMORY_DEBUG)
00153 fprintf( stderr, "FATAL: alloc has illegal value\n" );
00154 #endif
00155 return( 1 );
00156 }
00157
00158 if( hdr->prev != NULL && hdr->prev == hdr->next )
00159 {
00160 #if defined(POLARSSL_MEMORY_DEBUG)
00161 fprintf( stderr, "FATAL: prev == next\n" );
00162 #endif
00163 return( 1 );
00164 }
00165
00166 if( hdr->prev_free != NULL && hdr->prev_free == hdr->next_free )
00167 {
00168 #if defined(POLARSSL_MEMORY_DEBUG)
00169 fprintf( stderr, "FATAL: prev_free == next_free\n" );
00170 #endif
00171 return( 1 );
00172 }
00173
00174 return( 0 );
00175 }
00176
00177 static int verify_chain()
00178 {
00179 memory_header *prv = heap.first, *cur = heap.first->next;
00180
00181 if( verify_header( heap.first ) != 0 )
00182 {
00183 #if defined(POLARSSL_MEMORY_DEBUG)
00184 fprintf( stderr, "FATAL: verification of first header failed\n" );
00185 #endif
00186 return( 1 );
00187 }
00188
00189 if( heap.first->prev != NULL )
00190 {
00191 #if defined(POLARSSL_MEMORY_DEBUG)
00192 fprintf( stderr, "FATAL: verification failed: first->prev != NULL\n" );
00193 #endif
00194 return( 1 );
00195 }
00196
00197 while( cur != NULL )
00198 {
00199 if( verify_header( cur ) != 0 )
00200 {
00201 #if defined(POLARSSL_MEMORY_DEBUG)
00202 fprintf( stderr, "FATAL: verification of header failed\n" );
00203 #endif
00204 return( 1 );
00205 }
00206
00207 if( cur->prev != prv )
00208 {
00209 #if defined(POLARSSL_MEMORY_DEBUG)
00210 fprintf( stderr, "FATAL: verification failed: cur->prev != prv\n" );
00211 #endif
00212 return( 1 );
00213 }
00214
00215 prv = cur;
00216 cur = cur->next;
00217 }
00218
00219 return( 0 );
00220 }
00221
00222 static void *buffer_alloc_malloc( size_t len )
00223 {
00224 memory_header *new, *cur = heap.first_free;
00225 unsigned char *p;
00226 #if defined(POLARSSL_MEMORY_BACKTRACE)
00227 void *trace_buffer[MAX_BT];
00228 size_t trace_cnt;
00229 #endif
00230
00231 if( heap.buf == NULL || heap.first == NULL )
00232 return( NULL );
00233
00234 if( len % POLARSSL_MEMORY_ALIGN_MULTIPLE )
00235 {
00236 len -= len % POLARSSL_MEMORY_ALIGN_MULTIPLE;
00237 len += POLARSSL_MEMORY_ALIGN_MULTIPLE;
00238 }
00239
00240
00241
00242 while( cur != NULL )
00243 {
00244 if( cur->size >= len )
00245 break;
00246
00247 cur = cur->next_free;
00248 }
00249
00250 if( cur == NULL )
00251 return( NULL );
00252
00253 if( cur->alloc != 0 )
00254 {
00255 #if defined(POLARSSL_MEMORY_DEBUG)
00256 fprintf( stderr, "FATAL: block in free_list but allocated data\n" );
00257 #endif
00258 exit( 1 );
00259 }
00260
00261 #if defined(POLARSSL_MEMORY_DEBUG)
00262 heap.malloc_count++;
00263 #endif
00264
00265
00266
00267 if( cur->size - len < sizeof(memory_header) + POLARSSL_MEMORY_ALIGN_MULTIPLE )
00268 {
00269 cur->alloc = 1;
00270
00271
00272
00273 if( cur->prev_free != NULL )
00274 cur->prev_free->next_free = cur->next_free;
00275 else
00276 heap.first_free = cur->next_free;
00277
00278 if( cur->next_free != NULL )
00279 cur->next_free->prev_free = cur->prev_free;
00280
00281 cur->prev_free = NULL;
00282 cur->next_free = NULL;
00283
00284 #if defined(POLARSSL_MEMORY_DEBUG)
00285 heap.total_used += cur->size;
00286 if( heap.total_used > heap.maximum_used)
00287 heap.maximum_used = heap.total_used;
00288 #endif
00289 #if defined(POLARSSL_MEMORY_BACKTRACE)
00290 trace_cnt = backtrace( trace_buffer, MAX_BT );
00291 cur->trace = backtrace_symbols( trace_buffer, trace_cnt );
00292 cur->trace_count = trace_cnt;
00293 #endif
00294
00295 if( ( heap.verify & MEMORY_VERIFY_ALLOC ) && verify_chain() != 0 )
00296 exit( 1 );
00297
00298 return ( (unsigned char *) cur ) + sizeof(memory_header);
00299 }
00300
00301 p = ( (unsigned char *) cur ) + sizeof(memory_header) + len;
00302 new = (memory_header *) p;
00303
00304 new->size = cur->size - len - sizeof(memory_header);
00305 new->alloc = 0;
00306 new->prev = cur;
00307 new->next = cur->next;
00308 #if defined(POLARSSL_MEMORY_BACKTRACE)
00309 new->trace = NULL;
00310 new->trace_count = 0;
00311 #endif
00312 new->magic1 = MAGIC1;
00313 new->magic2 = MAGIC2;
00314
00315 if( new->next != NULL )
00316 new->next->prev = new;
00317
00318
00319
00320 new->prev_free = cur->prev_free;
00321 new->next_free = cur->next_free;
00322 if( new->prev_free != NULL )
00323 new->prev_free->next_free = new;
00324 else
00325 heap.first_free = new;
00326
00327 if( new->next_free != NULL )
00328 new->next_free->prev_free = new;
00329
00330 cur->alloc = 1;
00331 cur->size = len;
00332 cur->next = new;
00333 cur->prev_free = NULL;
00334 cur->next_free = NULL;
00335
00336 #if defined(POLARSSL_MEMORY_DEBUG)
00337 heap.header_count++;
00338 heap.total_used += cur->size;
00339 if( heap.total_used > heap.maximum_used)
00340 heap.maximum_used = heap.total_used;
00341 #endif
00342 #if defined(POLARSSL_MEMORY_BACKTRACE)
00343 trace_cnt = backtrace( trace_buffer, MAX_BT );
00344 cur->trace = backtrace_symbols( trace_buffer, trace_cnt );
00345 cur->trace_count = trace_cnt;
00346 #endif
00347
00348 if( ( heap.verify & MEMORY_VERIFY_ALLOC ) && verify_chain() != 0 )
00349 exit( 1 );
00350
00351 return ( (unsigned char *) cur ) + sizeof(memory_header);
00352 }
00353
00354 static void buffer_alloc_free( void *ptr )
00355 {
00356 memory_header *hdr, *old = NULL;
00357 unsigned char *p = (unsigned char *) ptr;
00358
00359 if( ptr == NULL || heap.buf == NULL || heap.first == NULL )
00360 return;
00361
00362 if( p < heap.buf || p > heap.buf + heap.len )
00363 {
00364 #if defined(POLARSSL_MEMORY_DEBUG)
00365 fprintf( stderr, "FATAL: polarssl_free() outside of managed space\n" );
00366 #endif
00367 exit( 1 );
00368 }
00369
00370 p -= sizeof(memory_header);
00371 hdr = (memory_header *) p;
00372
00373 if( verify_header( hdr ) != 0 )
00374 exit( 1 );
00375
00376 if( hdr->alloc != 1 )
00377 {
00378 #if defined(POLARSSL_MEMORY_DEBUG)
00379 fprintf( stderr, "FATAL: polarssl_free() on unallocated data\n" );
00380 #endif
00381 exit( 1 );
00382 }
00383
00384 hdr->alloc = 0;
00385
00386 #if defined(POLARSSL_MEMORY_DEBUG)
00387 heap.free_count++;
00388 heap.total_used -= hdr->size;
00389 #endif
00390
00391
00392
00393 if( hdr->prev != NULL && hdr->prev->alloc == 0 )
00394 {
00395 #if defined(POLARSSL_MEMORY_DEBUG)
00396 heap.header_count--;
00397 #endif
00398 hdr->prev->size += sizeof(memory_header) + hdr->size;
00399 hdr->prev->next = hdr->next;
00400 old = hdr;
00401 hdr = hdr->prev;
00402
00403 if( hdr->next != NULL )
00404 hdr->next->prev = hdr;
00405
00406 #if defined(POLARSSL_MEMORY_BACKTRACE)
00407 free( old->trace );
00408 #endif
00409 memset( old, 0, sizeof(memory_header) );
00410 }
00411
00412
00413
00414 if( hdr->next != NULL && hdr->next->alloc == 0 )
00415 {
00416 #if defined(POLARSSL_MEMORY_DEBUG)
00417 heap.header_count--;
00418 #endif
00419 hdr->size += sizeof(memory_header) + hdr->next->size;
00420 old = hdr->next;
00421 hdr->next = hdr->next->next;
00422
00423 if( hdr->prev_free != NULL || hdr->next_free != NULL )
00424 {
00425 if( hdr->prev_free != NULL )
00426 hdr->prev_free->next_free = hdr->next_free;
00427 else
00428 heap.first_free = hdr->next_free;
00429
00430 if( hdr->next_free != NULL )
00431 hdr->next_free->prev_free = hdr->prev_free;
00432 }
00433
00434 hdr->prev_free = old->prev_free;
00435 hdr->next_free = old->next_free;
00436
00437 if( hdr->prev_free != NULL )
00438 hdr->prev_free->next_free = hdr;
00439 else
00440 heap.first_free = hdr;
00441
00442 if( hdr->next_free != NULL )
00443 hdr->next_free->prev_free = hdr;
00444
00445 if( hdr->next != NULL )
00446 hdr->next->prev = hdr;
00447
00448 #if defined(POLARSSL_MEMORY_BACKTRACE)
00449 free( old->trace );
00450 #endif
00451 memset( old, 0, sizeof(memory_header) );
00452 }
00453
00454
00455
00456
00457 if( old == NULL )
00458 {
00459 hdr->next_free = heap.first_free;
00460 heap.first_free->prev_free = hdr;
00461 heap.first_free = hdr;
00462 }
00463
00464 #if defined(POLARSSL_MEMORY_BACKTRACE)
00465 hdr->trace = NULL;
00466 hdr->trace_count = 0;
00467 #endif
00468
00469 if( ( heap.verify & MEMORY_VERIFY_FREE ) && verify_chain() != 0 )
00470 exit( 1 );
00471 }
00472
00473 void memory_buffer_set_verify( int verify )
00474 {
00475 heap.verify = verify;
00476 }
00477
00478 int memory_buffer_alloc_verify()
00479 {
00480 return verify_chain();
00481 }
00482
00483 #if defined(POLARSSL_MEMORY_DEBUG)
00484 void memory_buffer_alloc_status()
00485 {
00486 fprintf( stderr,
00487 "Current use: %u blocks / %u bytes, max: %u bytes, malloc / free: %u / %u\n",
00488 heap.header_count, heap.total_used, heap.maximum_used,
00489 heap.malloc_count, heap.free_count );
00490
00491 if( heap.first->next == NULL )
00492 fprintf( stderr, "All memory de-allocated in stack buffer\n" );
00493 else
00494 {
00495 fprintf( stderr, "Memory currently allocated:\n" );
00496 debug_chain();
00497 }
00498 }
00499 #endif
00500
00501 #if defined(POLARSSL_THREADING_C)
00502 static void *buffer_alloc_malloc_mutexed( size_t len )
00503 {
00504 void *buf;
00505 polarssl_mutex_lock( &heap.mutex );
00506 buf = buffer_alloc_malloc( len );
00507 polarssl_mutex_unlock( &heap.mutex );
00508 return( buf );
00509 }
00510
00511 static void buffer_alloc_free_mutexed( void *ptr )
00512 {
00513 polarssl_mutex_lock( &heap.mutex );
00514 buffer_alloc_free( ptr );
00515 polarssl_mutex_unlock( &heap.mutex );
00516 }
00517 #endif
00518
00519 int memory_buffer_alloc_init( unsigned char *buf, size_t len )
00520 {
00521 memset( &heap, 0, sizeof(buffer_alloc_ctx) );
00522 memset( buf, 0, len );
00523
00524 #if defined(POLARSSL_THREADING_C)
00525 polarssl_mutex_init( &heap.mutex );
00526 polarssl_malloc = buffer_alloc_malloc_mutexed;
00527 polarssl_free = buffer_alloc_free_mutexed;
00528 #else
00529 polarssl_malloc = buffer_alloc_malloc;
00530 polarssl_free = buffer_alloc_free;
00531 #endif
00532
00533 heap.buf = buf;
00534 heap.len = len;
00535
00536 heap.first = (memory_header *) buf;
00537 heap.first->size = len - sizeof(memory_header);
00538 heap.first->magic1 = MAGIC1;
00539 heap.first->magic2 = MAGIC2;
00540 heap.first_free = heap.first;
00541 return( 0 );
00542 }
00543
00544 void memory_buffer_alloc_free()
00545 {
00546 #if defined(POLARSSL_THREADING_C)
00547 polarssl_mutex_free( &heap.mutex );
00548 #endif
00549 memset( &heap, 0, sizeof(buffer_alloc_ctx) );
00550 }
00551
00552 #endif