PolarSSL v1.3.9
memory_buffer_alloc.c
Go to the documentation of this file.
1 /*
2  * Buffer-based memory allocator
3  *
4  * Copyright (C) 2006-2014, Brainspark B.V.
5  *
6  * This file is part of PolarSSL (http://www.polarssl.org)
7  * Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
8  *
9  * All rights reserved.
10  *
11  * This program is free software; you can redistribute it and/or modify
12  * it under the terms of the GNU General Public License as published by
13  * the Free Software Foundation; either version 2 of the License, or
14  * (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License along
22  * with this program; if not, write to the Free Software Foundation, Inc.,
23  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
24  */
25 
26 #if !defined(POLARSSL_CONFIG_FILE)
27 #include "polarssl/config.h"
28 #else
29 #include POLARSSL_CONFIG_FILE
30 #endif
31 
32 #if defined(POLARSSL_MEMORY_BUFFER_ALLOC_C)
33 
35 
36 #include <string.h>
37 
38 #if defined(POLARSSL_MEMORY_DEBUG)
39 #include <stdio.h>
40 #endif
41 #if defined(POLARSSL_MEMORY_BACKTRACE)
42 #include <execinfo.h>
43 #endif
44 
45 #if defined(POLARSSL_THREADING_C)
46 #include "polarssl/threading.h"
47 #endif
48 
49 #if defined(POLARSSL_PLATFORM_C)
50 #include "polarssl/platform.h"
51 #else
52 #define polarssl_fprintf fprintf
53 #endif
54 
55 /* Implementation that should never be optimized out by the compiler */
56 static void polarssl_zeroize( void *v, size_t n ) {
57  volatile unsigned char *p = v; while( n-- ) *p++ = 0;
58 }
59 
60 #define MAGIC1 0xFF00AA55
61 #define MAGIC2 0xEE119966
62 #define MAX_BT 20
63 
64 typedef struct _memory_header memory_header;
65 struct _memory_header
66 {
67  size_t magic1;
68  size_t size;
69  size_t alloc;
70  memory_header *prev;
71  memory_header *next;
72  memory_header *prev_free;
73  memory_header *next_free;
74 #if defined(POLARSSL_MEMORY_BACKTRACE)
75  char **trace;
76  size_t trace_count;
77 #endif
78  size_t magic2;
79 };
80 
81 typedef struct
82 {
83  unsigned char *buf;
84  size_t len;
85  memory_header *first;
86  memory_header *first_free;
87  size_t current_alloc_size;
88  int verify;
89 #if defined(POLARSSL_MEMORY_DEBUG)
90  size_t malloc_count;
91  size_t free_count;
92  size_t total_used;
93  size_t maximum_used;
94  size_t header_count;
95  size_t maximum_header_count;
96 #endif
97 #if defined(POLARSSL_THREADING_C)
98  threading_mutex_t mutex;
99 #endif
100 }
101 buffer_alloc_ctx;
102 
103 static buffer_alloc_ctx heap;
104 
105 #if defined(POLARSSL_MEMORY_DEBUG)
106 static void debug_header( memory_header *hdr )
107 {
108 #if defined(POLARSSL_MEMORY_BACKTRACE)
109  size_t i;
110 #endif
111 
112  polarssl_fprintf( stderr, "HDR: PTR(%10zu), PREV(%10zu), NEXT(%10zu), "
113  "ALLOC(%zu), SIZE(%10zu)\n",
114  (size_t) hdr, (size_t) hdr->prev, (size_t) hdr->next,
115  hdr->alloc, hdr->size );
116  polarssl_fprintf( stderr, " FPREV(%10zu), FNEXT(%10zu)\n",
117  (size_t) hdr->prev_free, (size_t) hdr->next_free );
118 
119 #if defined(POLARSSL_MEMORY_BACKTRACE)
120  polarssl_fprintf( stderr, "TRACE: \n" );
121  for( i = 0; i < hdr->trace_count; i++ )
122  polarssl_fprintf( stderr, "%s\n", hdr->trace[i] );
123  polarssl_fprintf( stderr, "\n" );
124 #endif
125 }
126 
127 static void debug_chain()
128 {
129  memory_header *cur = heap.first;
130 
131  polarssl_fprintf( stderr, "\nBlock list\n" );
132  while( cur != NULL )
133  {
134  debug_header( cur );
135  cur = cur->next;
136  }
137 
138  polarssl_fprintf( stderr, "Free list\n" );
139  cur = heap.first_free;
140 
141  while( cur != NULL )
142  {
143  debug_header( cur );
144  cur = cur->next_free;
145  }
146 }
147 #endif /* POLARSSL_MEMORY_DEBUG */
148 
149 static int verify_header( memory_header *hdr )
150 {
151  if( hdr->magic1 != MAGIC1 )
152  {
153 #if defined(POLARSSL_MEMORY_DEBUG)
154  polarssl_fprintf( stderr, "FATAL: MAGIC1 mismatch\n" );
155 #endif
156  return( 1 );
157  }
158 
159  if( hdr->magic2 != MAGIC2 )
160  {
161 #if defined(POLARSSL_MEMORY_DEBUG)
162  polarssl_fprintf( stderr, "FATAL: MAGIC2 mismatch\n" );
163 #endif
164  return( 1 );
165  }
166 
167  if( hdr->alloc > 1 )
168  {
169 #if defined(POLARSSL_MEMORY_DEBUG)
170  polarssl_fprintf( stderr, "FATAL: alloc has illegal value\n" );
171 #endif
172  return( 1 );
173  }
174 
175  if( hdr->prev != NULL && hdr->prev == hdr->next )
176  {
177 #if defined(POLARSSL_MEMORY_DEBUG)
178  polarssl_fprintf( stderr, "FATAL: prev == next\n" );
179 #endif
180  return( 1 );
181  }
182 
183  if( hdr->prev_free != NULL && hdr->prev_free == hdr->next_free )
184  {
185 #if defined(POLARSSL_MEMORY_DEBUG)
186  polarssl_fprintf( stderr, "FATAL: prev_free == next_free\n" );
187 #endif
188  return( 1 );
189  }
190 
191  return( 0 );
192 }
193 
194 static int verify_chain()
195 {
196  memory_header *prv = heap.first, *cur = heap.first->next;
197 
198  if( verify_header( heap.first ) != 0 )
199  {
200 #if defined(POLARSSL_MEMORY_DEBUG)
201  polarssl_fprintf( stderr, "FATAL: verification of first header "
202  "failed\n" );
203 #endif
204  return( 1 );
205  }
206 
207  if( heap.first->prev != NULL )
208  {
209 #if defined(POLARSSL_MEMORY_DEBUG)
210  polarssl_fprintf( stderr, "FATAL: verification failed: "
211  "first->prev != NULL\n" );
212 #endif
213  return( 1 );
214  }
215 
216  while( cur != NULL )
217  {
218  if( verify_header( cur ) != 0 )
219  {
220 #if defined(POLARSSL_MEMORY_DEBUG)
221  polarssl_fprintf( stderr, "FATAL: verification of header "
222  "failed\n" );
223 #endif
224  return( 1 );
225  }
226 
227  if( cur->prev != prv )
228  {
229 #if defined(POLARSSL_MEMORY_DEBUG)
230  polarssl_fprintf( stderr, "FATAL: verification failed: "
231  "cur->prev != prv\n" );
232 #endif
233  return( 1 );
234  }
235 
236  prv = cur;
237  cur = cur->next;
238  }
239 
240  return( 0 );
241 }
242 
243 static void *buffer_alloc_malloc( size_t len )
244 {
245  memory_header *new, *cur = heap.first_free;
246  unsigned char *p;
247 #if defined(POLARSSL_MEMORY_BACKTRACE)
248  void *trace_buffer[MAX_BT];
249  size_t trace_cnt;
250 #endif
251 
252  if( heap.buf == NULL || heap.first == NULL )
253  return( NULL );
254 
256  {
257  len -= len % POLARSSL_MEMORY_ALIGN_MULTIPLE;
259  }
260 
261  // Find block that fits
262  //
263  while( cur != NULL )
264  {
265  if( cur->size >= len )
266  break;
267 
268  cur = cur->next_free;
269  }
270 
271  if( cur == NULL )
272  return( NULL );
273 
274  if( cur->alloc != 0 )
275  {
276 #if defined(POLARSSL_MEMORY_DEBUG)
277  polarssl_fprintf( stderr, "FATAL: block in free_list but allocated "
278  "data\n" );
279 #endif
280  exit( 1 );
281  }
282 
283 #if defined(POLARSSL_MEMORY_DEBUG)
284  heap.malloc_count++;
285 #endif
286 
287  // Found location, split block if > memory_header + 4 room left
288  //
289  if( cur->size - len < sizeof(memory_header) +
290  POLARSSL_MEMORY_ALIGN_MULTIPLE )
291  {
292  cur->alloc = 1;
293 
294  // Remove from free_list
295  //
296  if( cur->prev_free != NULL )
297  cur->prev_free->next_free = cur->next_free;
298  else
299  heap.first_free = cur->next_free;
300 
301  if( cur->next_free != NULL )
302  cur->next_free->prev_free = cur->prev_free;
303 
304  cur->prev_free = NULL;
305  cur->next_free = NULL;
306 
307 #if defined(POLARSSL_MEMORY_DEBUG)
308  heap.total_used += cur->size;
309  if( heap.total_used > heap.maximum_used )
310  heap.maximum_used = heap.total_used;
311 #endif
312 #if defined(POLARSSL_MEMORY_BACKTRACE)
313  trace_cnt = backtrace( trace_buffer, MAX_BT );
314  cur->trace = backtrace_symbols( trace_buffer, trace_cnt );
315  cur->trace_count = trace_cnt;
316 #endif
317 
318  if( ( heap.verify & MEMORY_VERIFY_ALLOC ) && verify_chain() != 0 )
319  exit( 1 );
320 
321  return( ( (unsigned char *) cur ) + sizeof(memory_header) );
322  }
323 
324  p = ( (unsigned char *) cur ) + sizeof(memory_header) + len;
325  new = (memory_header *) p;
326 
327  new->size = cur->size - len - sizeof(memory_header);
328  new->alloc = 0;
329  new->prev = cur;
330  new->next = cur->next;
331 #if defined(POLARSSL_MEMORY_BACKTRACE)
332  new->trace = NULL;
333  new->trace_count = 0;
334 #endif
335  new->magic1 = MAGIC1;
336  new->magic2 = MAGIC2;
337 
338  if( new->next != NULL )
339  new->next->prev = new;
340 
341  // Replace cur with new in free_list
342  //
343  new->prev_free = cur->prev_free;
344  new->next_free = cur->next_free;
345  if( new->prev_free != NULL )
346  new->prev_free->next_free = new;
347  else
348  heap.first_free = new;
349 
350  if( new->next_free != NULL )
351  new->next_free->prev_free = new;
352 
353  cur->alloc = 1;
354  cur->size = len;
355  cur->next = new;
356  cur->prev_free = NULL;
357  cur->next_free = NULL;
358 
359 #if defined(POLARSSL_MEMORY_DEBUG)
360  heap.header_count++;
361  if( heap.header_count > heap.maximum_header_count )
362  heap.maximum_header_count = heap.header_count;
363  heap.total_used += cur->size;
364  if( heap.total_used > heap.maximum_used )
365  heap.maximum_used = heap.total_used;
366 #endif
367 #if defined(POLARSSL_MEMORY_BACKTRACE)
368  trace_cnt = backtrace( trace_buffer, MAX_BT );
369  cur->trace = backtrace_symbols( trace_buffer, trace_cnt );
370  cur->trace_count = trace_cnt;
371 #endif
372 
373  if( ( heap.verify & MEMORY_VERIFY_ALLOC ) && verify_chain() != 0 )
374  exit( 1 );
375 
376  return( ( (unsigned char *) cur ) + sizeof(memory_header) );
377 }
378 
379 static void buffer_alloc_free( void *ptr )
380 {
381  memory_header *hdr, *old = NULL;
382  unsigned char *p = (unsigned char *) ptr;
383 
384  if( ptr == NULL || heap.buf == NULL || heap.first == NULL )
385  return;
386 
387  if( p < heap.buf || p > heap.buf + heap.len )
388  {
389 #if defined(POLARSSL_MEMORY_DEBUG)
390  polarssl_fprintf( stderr, "FATAL: polarssl_free() outside of managed "
391  "space\n" );
392 #endif
393  exit( 1 );
394  }
395 
396  p -= sizeof(memory_header);
397  hdr = (memory_header *) p;
398 
399  if( verify_header( hdr ) != 0 )
400  exit( 1 );
401 
402  if( hdr->alloc != 1 )
403  {
404 #if defined(POLARSSL_MEMORY_DEBUG)
405  polarssl_fprintf( stderr, "FATAL: polarssl_free() on unallocated "
406  "data\n" );
407 #endif
408  exit( 1 );
409  }
410 
411  hdr->alloc = 0;
412 
413 #if defined(POLARSSL_MEMORY_DEBUG)
414  heap.free_count++;
415  heap.total_used -= hdr->size;
416 #endif
417 
418  // Regroup with block before
419  //
420  if( hdr->prev != NULL && hdr->prev->alloc == 0 )
421  {
422 #if defined(POLARSSL_MEMORY_DEBUG)
423  heap.header_count--;
424 #endif
425  hdr->prev->size += sizeof(memory_header) + hdr->size;
426  hdr->prev->next = hdr->next;
427  old = hdr;
428  hdr = hdr->prev;
429 
430  if( hdr->next != NULL )
431  hdr->next->prev = hdr;
432 
433 #if defined(POLARSSL_MEMORY_BACKTRACE)
434  free( old->trace );
435 #endif
436  memset( old, 0, sizeof(memory_header) );
437  }
438 
439  // Regroup with block after
440  //
441  if( hdr->next != NULL && hdr->next->alloc == 0 )
442  {
443 #if defined(POLARSSL_MEMORY_DEBUG)
444  heap.header_count--;
445 #endif
446  hdr->size += sizeof(memory_header) + hdr->next->size;
447  old = hdr->next;
448  hdr->next = hdr->next->next;
449 
450  if( hdr->prev_free != NULL || hdr->next_free != NULL )
451  {
452  if( hdr->prev_free != NULL )
453  hdr->prev_free->next_free = hdr->next_free;
454  else
455  heap.first_free = hdr->next_free;
456 
457  if( hdr->next_free != NULL )
458  hdr->next_free->prev_free = hdr->prev_free;
459  }
460 
461  hdr->prev_free = old->prev_free;
462  hdr->next_free = old->next_free;
463 
464  if( hdr->prev_free != NULL )
465  hdr->prev_free->next_free = hdr;
466  else
467  heap.first_free = hdr;
468 
469  if( hdr->next_free != NULL )
470  hdr->next_free->prev_free = hdr;
471 
472  if( hdr->next != NULL )
473  hdr->next->prev = hdr;
474 
475 #if defined(POLARSSL_MEMORY_BACKTRACE)
476  free( old->trace );
477 #endif
478  memset( old, 0, sizeof(memory_header) );
479  }
480 
481  // Prepend to free_list if we have not merged
482  // (Does not have to stay in same order as prev / next list)
483  //
484  if( old == NULL )
485  {
486  hdr->next_free = heap.first_free;
487  heap.first_free->prev_free = hdr;
488  heap.first_free = hdr;
489  }
490 
491 #if defined(POLARSSL_MEMORY_BACKTRACE)
492  hdr->trace = NULL;
493  hdr->trace_count = 0;
494 #endif
495 
496  if( ( heap.verify & MEMORY_VERIFY_FREE ) && verify_chain() != 0 )
497  exit( 1 );
498 }
499 
500 void memory_buffer_set_verify( int verify )
501 {
502  heap.verify = verify;
503 }
504 
506 {
507  return verify_chain();
508 }
509 
510 #if defined(POLARSSL_MEMORY_DEBUG)
511 void memory_buffer_alloc_status()
512 {
513  polarssl_fprintf( stderr,
514  "Current use: %zu blocks / %zu bytes, max: %zu blocks / "
515  "%zu bytes (total %zu bytes), malloc / free: %zu / %zu\n",
516  heap.header_count, heap.total_used,
517  heap.maximum_header_count, heap.maximum_used,
518  heap.maximum_header_count * sizeof( memory_header )
519  + heap.maximum_used,
520  heap.malloc_count, heap.free_count );
521 
522  if( heap.first->next == NULL )
523  polarssl_fprintf( stderr, "All memory de-allocated in stack buffer\n" );
524  else
525  {
526  polarssl_fprintf( stderr, "Memory currently allocated:\n" );
527  debug_chain();
528  }
529 }
530 #endif /* POLARSSL_MEMORY_DEBUG */
531 
532 #if defined(POLARSSL_THREADING_C)
533 static void *buffer_alloc_malloc_mutexed( size_t len )
534 {
535  void *buf;
536  polarssl_mutex_lock( &heap.mutex );
537  buf = buffer_alloc_malloc( len );
538  polarssl_mutex_unlock( &heap.mutex );
539  return( buf );
540 }
541 
542 static void buffer_alloc_free_mutexed( void *ptr )
543 {
544  polarssl_mutex_lock( &heap.mutex );
545  buffer_alloc_free( ptr );
546  polarssl_mutex_unlock( &heap.mutex );
547 }
548 #endif /* POLARSSL_THREADING_C */
549 
550 int memory_buffer_alloc_init( unsigned char *buf, size_t len )
551 {
552  memset( &heap, 0, sizeof(buffer_alloc_ctx) );
553  memset( buf, 0, len );
554 
555 #if defined(POLARSSL_THREADING_C)
556  polarssl_mutex_init( &heap.mutex );
557  platform_set_malloc_free( buffer_alloc_malloc_mutexed,
558  buffer_alloc_free_mutexed );
559 #else
560  platform_set_malloc_free( buffer_alloc_malloc, buffer_alloc_free );
561 #endif
562 
563  if( (size_t) buf % POLARSSL_MEMORY_ALIGN_MULTIPLE )
564  {
565  buf += POLARSSL_MEMORY_ALIGN_MULTIPLE
566  - (size_t) buf % POLARSSL_MEMORY_ALIGN_MULTIPLE;
567  len -= (size_t) buf % POLARSSL_MEMORY_ALIGN_MULTIPLE;
568  }
569 
570  heap.buf = buf;
571  heap.len = len;
572 
573  heap.first = (memory_header *) buf;
574  heap.first->size = len - sizeof(memory_header);
575  heap.first->magic1 = MAGIC1;
576  heap.first->magic2 = MAGIC2;
577  heap.first_free = heap.first;
578  return( 0 );
579 }
580 
582 {
583 #if defined(POLARSSL_THREADING_C)
584  polarssl_mutex_free( &heap.mutex );
585 #endif
586  polarssl_zeroize( &heap, sizeof(buffer_alloc_ctx) );
587 }
588 
589 #endif /* POLARSSL_MEMORY_BUFFER_ALLOC_C */