PolarSSL v1.3.7
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 #if defined(POLARSSL_MEMORY_BACKTRACE)
41 #include <execinfo.h>
42 #endif
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 #define MAGIC1 0xFF00AA55
56 #define MAGIC2 0xEE119966
57 #define MAX_BT 20
58 
59 typedef struct _memory_header memory_header;
60 struct _memory_header
61 {
62  size_t magic1;
63  size_t size;
64  size_t alloc;
65  memory_header *prev;
66  memory_header *next;
67  memory_header *prev_free;
68  memory_header *next_free;
69 #if defined(POLARSSL_MEMORY_BACKTRACE)
70  char **trace;
71  size_t trace_count;
72 #endif
73  size_t magic2;
74 };
75 
76 typedef struct
77 {
78  unsigned char *buf;
79  size_t len;
80  memory_header *first;
81  memory_header *first_free;
82  size_t current_alloc_size;
83  int verify;
84 #if defined(POLARSSL_MEMORY_DEBUG)
85  size_t malloc_count;
86  size_t free_count;
87  size_t total_used;
88  size_t maximum_used;
89  size_t header_count;
90  size_t maximum_header_count;
91 #endif
92 #if defined(POLARSSL_THREADING_C)
93  threading_mutex_t mutex;
94 #endif
95 }
96 buffer_alloc_ctx;
97 
98 static buffer_alloc_ctx heap;
99 
100 #if defined(POLARSSL_MEMORY_DEBUG)
101 static void debug_header( memory_header *hdr )
102 {
103 #if defined(POLARSSL_MEMORY_BACKTRACE)
104  size_t i;
105 #endif
106 
107  polarssl_fprintf( stderr, "HDR: PTR(%10u), PREV(%10u), NEXT(%10u), "
108  "ALLOC(%u), SIZE(%10u)\n",
109  (size_t) hdr, (size_t) hdr->prev, (size_t) hdr->next,
110  hdr->alloc, hdr->size );
111  polarssl_fprintf( stderr, " FPREV(%10u), FNEXT(%10u)\n",
112  (size_t) hdr->prev_free, (size_t) hdr->next_free );
113 
114 #if defined(POLARSSL_MEMORY_BACKTRACE)
115  polarssl_fprintf( stderr, "TRACE: \n" );
116  for( i = 0; i < hdr->trace_count; i++ )
117  polarssl_fprintf( stderr, "%s\n", hdr->trace[i] );
118  polarssl_fprintf( stderr, "\n" );
119 #endif
120 }
121 
122 static void debug_chain()
123 {
124  memory_header *cur = heap.first;
125 
126  polarssl_fprintf( stderr, "\nBlock list\n" );
127  while( cur != NULL )
128  {
129  debug_header( cur );
130  cur = cur->next;
131  }
132 
133  polarssl_fprintf( stderr, "Free list\n" );
134  cur = heap.first_free;
135 
136  while( cur != NULL )
137  {
138  debug_header( cur );
139  cur = cur->next_free;
140  }
141 }
142 #endif /* POLARSSL_MEMORY_DEBUG */
143 
144 static int verify_header( memory_header *hdr )
145 {
146  if( hdr->magic1 != MAGIC1 )
147  {
148 #if defined(POLARSSL_MEMORY_DEBUG)
149  polarssl_fprintf( stderr, "FATAL: MAGIC1 mismatch\n" );
150 #endif
151  return( 1 );
152  }
153 
154  if( hdr->magic2 != MAGIC2 )
155  {
156 #if defined(POLARSSL_MEMORY_DEBUG)
157  polarssl_fprintf( stderr, "FATAL: MAGIC2 mismatch\n" );
158 #endif
159  return( 1 );
160  }
161 
162  if( hdr->alloc > 1 )
163  {
164 #if defined(POLARSSL_MEMORY_DEBUG)
165  polarssl_fprintf( stderr, "FATAL: alloc has illegal value\n" );
166 #endif
167  return( 1 );
168  }
169 
170  if( hdr->prev != NULL && hdr->prev == hdr->next )
171  {
172 #if defined(POLARSSL_MEMORY_DEBUG)
173  polarssl_fprintf( stderr, "FATAL: prev == next\n" );
174 #endif
175  return( 1 );
176  }
177 
178  if( hdr->prev_free != NULL && hdr->prev_free == hdr->next_free )
179  {
180 #if defined(POLARSSL_MEMORY_DEBUG)
181  polarssl_fprintf( stderr, "FATAL: prev_free == next_free\n" );
182 #endif
183  return( 1 );
184  }
185 
186  return( 0 );
187 }
188 
189 static int verify_chain()
190 {
191  memory_header *prv = heap.first, *cur = heap.first->next;
192 
193  if( verify_header( heap.first ) != 0 )
194  {
195 #if defined(POLARSSL_MEMORY_DEBUG)
196  polarssl_fprintf( stderr, "FATAL: verification of first header "
197  "failed\n" );
198 #endif
199  return( 1 );
200  }
201 
202  if( heap.first->prev != NULL )
203  {
204 #if defined(POLARSSL_MEMORY_DEBUG)
205  polarssl_fprintf( stderr, "FATAL: verification failed: "
206  "first->prev != NULL\n" );
207 #endif
208  return( 1 );
209  }
210 
211  while( cur != NULL )
212  {
213  if( verify_header( cur ) != 0 )
214  {
215 #if defined(POLARSSL_MEMORY_DEBUG)
216  polarssl_fprintf( stderr, "FATAL: verification of header "
217  "failed\n" );
218 #endif
219  return( 1 );
220  }
221 
222  if( cur->prev != prv )
223  {
224 #if defined(POLARSSL_MEMORY_DEBUG)
225  polarssl_fprintf( stderr, "FATAL: verification failed: "
226  "cur->prev != prv\n" );
227 #endif
228  return( 1 );
229  }
230 
231  prv = cur;
232  cur = cur->next;
233  }
234 
235  return( 0 );
236 }
237 
238 static void *buffer_alloc_malloc( size_t len )
239 {
240  memory_header *new, *cur = heap.first_free;
241  unsigned char *p;
242 #if defined(POLARSSL_MEMORY_BACKTRACE)
243  void *trace_buffer[MAX_BT];
244  size_t trace_cnt;
245 #endif
246 
247  if( heap.buf == NULL || heap.first == NULL )
248  return( NULL );
249 
251  {
252  len -= len % POLARSSL_MEMORY_ALIGN_MULTIPLE;
254  }
255 
256  // Find block that fits
257  //
258  while( cur != NULL )
259  {
260  if( cur->size >= len )
261  break;
262 
263  cur = cur->next_free;
264  }
265 
266  if( cur == NULL )
267  return( NULL );
268 
269  if( cur->alloc != 0 )
270  {
271 #if defined(POLARSSL_MEMORY_DEBUG)
272  polarssl_fprintf( stderr, "FATAL: block in free_list but allocated "
273  "data\n" );
274 #endif
275  exit( 1 );
276  }
277 
278 #if defined(POLARSSL_MEMORY_DEBUG)
279  heap.malloc_count++;
280 #endif
281 
282  // Found location, split block if > memory_header + 4 room left
283  //
284  if( cur->size - len < sizeof(memory_header) +
285  POLARSSL_MEMORY_ALIGN_MULTIPLE )
286  {
287  cur->alloc = 1;
288 
289  // Remove from free_list
290  //
291  if( cur->prev_free != NULL )
292  cur->prev_free->next_free = cur->next_free;
293  else
294  heap.first_free = cur->next_free;
295 
296  if( cur->next_free != NULL )
297  cur->next_free->prev_free = cur->prev_free;
298 
299  cur->prev_free = NULL;
300  cur->next_free = NULL;
301 
302 #if defined(POLARSSL_MEMORY_DEBUG)
303  heap.total_used += cur->size;
304  if( heap.total_used > heap.maximum_used)
305  heap.maximum_used = heap.total_used;
306 #endif
307 #if defined(POLARSSL_MEMORY_BACKTRACE)
308  trace_cnt = backtrace( trace_buffer, MAX_BT );
309  cur->trace = backtrace_symbols( trace_buffer, trace_cnt );
310  cur->trace_count = trace_cnt;
311 #endif
312 
313  if( ( heap.verify & MEMORY_VERIFY_ALLOC ) && verify_chain() != 0 )
314  exit( 1 );
315 
316  return ( (unsigned char *) cur ) + sizeof(memory_header);
317  }
318 
319  p = ( (unsigned char *) cur ) + sizeof(memory_header) + len;
320  new = (memory_header *) p;
321 
322  new->size = cur->size - len - sizeof(memory_header);
323  new->alloc = 0;
324  new->prev = cur;
325  new->next = cur->next;
326 #if defined(POLARSSL_MEMORY_BACKTRACE)
327  new->trace = NULL;
328  new->trace_count = 0;
329 #endif
330  new->magic1 = MAGIC1;
331  new->magic2 = MAGIC2;
332 
333  if( new->next != NULL )
334  new->next->prev = new;
335 
336  // Replace cur with new in free_list
337  //
338  new->prev_free = cur->prev_free;
339  new->next_free = cur->next_free;
340  if( new->prev_free != NULL )
341  new->prev_free->next_free = new;
342  else
343  heap.first_free = new;
344 
345  if( new->next_free != NULL )
346  new->next_free->prev_free = new;
347 
348  cur->alloc = 1;
349  cur->size = len;
350  cur->next = new;
351  cur->prev_free = NULL;
352  cur->next_free = NULL;
353 
354 #if defined(POLARSSL_MEMORY_DEBUG)
355  heap.header_count++;
356  if( heap.header_count > heap.maximum_header_count )
357  heap.maximum_header_count = heap.header_count;
358  heap.total_used += cur->size;
359  if( heap.total_used > heap.maximum_used)
360  heap.maximum_used = heap.total_used;
361 #endif
362 #if defined(POLARSSL_MEMORY_BACKTRACE)
363  trace_cnt = backtrace( trace_buffer, MAX_BT );
364  cur->trace = backtrace_symbols( trace_buffer, trace_cnt );
365  cur->trace_count = trace_cnt;
366 #endif
367 
368  if( ( heap.verify & MEMORY_VERIFY_ALLOC ) && verify_chain() != 0 )
369  exit( 1 );
370 
371  return ( (unsigned char *) cur ) + sizeof(memory_header);
372 }
373 
374 static void buffer_alloc_free( void *ptr )
375 {
376  memory_header *hdr, *old = NULL;
377  unsigned char *p = (unsigned char *) ptr;
378 
379  if( ptr == NULL || heap.buf == NULL || heap.first == NULL )
380  return;
381 
382  if( p < heap.buf || p > heap.buf + heap.len )
383  {
384 #if defined(POLARSSL_MEMORY_DEBUG)
385  polarssl_fprintf( stderr, "FATAL: polarssl_free() outside of managed "
386  "space\n" );
387 #endif
388  exit( 1 );
389  }
390 
391  p -= sizeof(memory_header);
392  hdr = (memory_header *) p;
393 
394  if( verify_header( hdr ) != 0 )
395  exit( 1 );
396 
397  if( hdr->alloc != 1 )
398  {
399 #if defined(POLARSSL_MEMORY_DEBUG)
400  polarssl_fprintf( stderr, "FATAL: polarssl_free() on unallocated "
401  "data\n" );
402 #endif
403  exit( 1 );
404  }
405 
406  hdr->alloc = 0;
407 
408 #if defined(POLARSSL_MEMORY_DEBUG)
409  heap.free_count++;
410  heap.total_used -= hdr->size;
411 #endif
412 
413  // Regroup with block before
414  //
415  if( hdr->prev != NULL && hdr->prev->alloc == 0 )
416  {
417 #if defined(POLARSSL_MEMORY_DEBUG)
418  heap.header_count--;
419 #endif
420  hdr->prev->size += sizeof(memory_header) + hdr->size;
421  hdr->prev->next = hdr->next;
422  old = hdr;
423  hdr = hdr->prev;
424 
425  if( hdr->next != NULL )
426  hdr->next->prev = hdr;
427 
428 #if defined(POLARSSL_MEMORY_BACKTRACE)
429  free( old->trace );
430 #endif
431  memset( old, 0, sizeof(memory_header) );
432  }
433 
434  // Regroup with block after
435  //
436  if( hdr->next != NULL && hdr->next->alloc == 0 )
437  {
438 #if defined(POLARSSL_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  {
447  if( hdr->prev_free != NULL )
448  hdr->prev_free->next_free = hdr->next_free;
449  else
450  heap.first_free = hdr->next_free;
451 
452  if( hdr->next_free != NULL )
453  hdr->next_free->prev_free = hdr->prev_free;
454  }
455 
456  hdr->prev_free = old->prev_free;
457  hdr->next_free = old->next_free;
458 
459  if( hdr->prev_free != NULL )
460  hdr->prev_free->next_free = hdr;
461  else
462  heap.first_free = hdr;
463 
464  if( hdr->next_free != NULL )
465  hdr->next_free->prev_free = hdr;
466 
467  if( hdr->next != NULL )
468  hdr->next->prev = hdr;
469 
470 #if defined(POLARSSL_MEMORY_BACKTRACE)
471  free( old->trace );
472 #endif
473  memset( old, 0, sizeof(memory_header) );
474  }
475 
476  // Prepend to free_list if we have not merged
477  // (Does not have to stay in same order as prev / next list)
478  //
479  if( old == NULL )
480  {
481  hdr->next_free = heap.first_free;
482  heap.first_free->prev_free = hdr;
483  heap.first_free = hdr;
484  }
485 
486 #if defined(POLARSSL_MEMORY_BACKTRACE)
487  hdr->trace = NULL;
488  hdr->trace_count = 0;
489 #endif
490 
491  if( ( heap.verify & MEMORY_VERIFY_FREE ) && verify_chain() != 0 )
492  exit( 1 );
493 }
494 
495 void memory_buffer_set_verify( int verify )
496 {
497  heap.verify = verify;
498 }
499 
501 {
502  return verify_chain();
503 }
504 
505 #if defined(POLARSSL_MEMORY_DEBUG)
506 void memory_buffer_alloc_status()
507 {
508  polarssl_fprintf( stderr,
509  "Current use: %u blocks / %u bytes, max: %u blocks / "
510  "%u bytes (total %u bytes), malloc / free: %u / %u\n",
511  heap.header_count, heap.total_used,
512  heap.maximum_header_count, heap.maximum_used,
513  heap.maximum_header_count * sizeof( memory_header )
514  + heap.maximum_used,
515  heap.malloc_count, heap.free_count );
516 
517  if( heap.first->next == NULL )
518  polarssl_fprintf( stderr, "All memory de-allocated in stack buffer\n" );
519  else
520  {
521  polarssl_fprintf( stderr, "Memory currently allocated:\n" );
522  debug_chain();
523  }
524 }
525 #endif /* POLARSSL_MEMORY_DEBUG */
526 
527 #if defined(POLARSSL_THREADING_C)
528 static void *buffer_alloc_malloc_mutexed( size_t len )
529 {
530  void *buf;
531  polarssl_mutex_lock( &heap.mutex );
532  buf = buffer_alloc_malloc( len );
533  polarssl_mutex_unlock( &heap.mutex );
534  return( buf );
535 }
536 
537 static void buffer_alloc_free_mutexed( void *ptr )
538 {
539  polarssl_mutex_lock( &heap.mutex );
540  buffer_alloc_free( ptr );
541  polarssl_mutex_unlock( &heap.mutex );
542 }
543 #endif /* POLARSSL_THREADING_C */
544 
545 int memory_buffer_alloc_init( unsigned char *buf, size_t len )
546 {
547  memset( &heap, 0, sizeof(buffer_alloc_ctx) );
548  memset( buf, 0, len );
549 
550 #if defined(POLARSSL_THREADING_C)
551  polarssl_mutex_init( &heap.mutex );
552  platform_set_malloc_free( buffer_alloc_malloc_mutexed,
553  buffer_alloc_free_mutexed );
554 #else
555  platform_set_malloc_free( buffer_alloc_malloc, buffer_alloc_free );
556 #endif
557 
558  heap.buf = buf;
559  heap.len = len;
560 
561  heap.first = (memory_header *) buf;
562  heap.first->size = len - sizeof(memory_header);
563  heap.first->magic1 = MAGIC1;
564  heap.first->magic2 = MAGIC2;
565  heap.first_free = heap.first;
566  return( 0 );
567 }
568 
570 {
571 #if defined(POLARSSL_THREADING_C)
572  polarssl_mutex_free( &heap.mutex );
573 #endif
574  memset( &heap, 0, sizeof(buffer_alloc_ctx) );
575 }
576 
577 #endif /* POLARSSL_MEMORY_BUFFER_ALLOC_C */
#define POLARSSL_MEMORY_ALIGN_MULTIPLE
Align on multiples of this value.
int(* polarssl_mutex_lock)(threading_mutex_t *mutex)
void memory_buffer_alloc_free(void)
Free the mutex for thread-safety and clear remaining memory.
Configuration options (set of defines)
PolarSSL Platform abstraction layer.
void memory_buffer_set_verify(int verify)
Determine when the allocator should automatically verify the state of the entire chain of headers / m...
int memory_buffer_alloc_init(unsigned char *buf, size_t len)
Initialize use of stack-based memory allocator.
#define MEMORY_VERIFY_FREE
Threading abstraction layer.
#define MEMORY_VERIFY_ALLOC
int memory_buffer_alloc_verify(void)
Verifies that all headers in the memory buffer are correct and contain sane values.
Buffer-based memory allocator.
int(* polarssl_mutex_free)(threading_mutex_t *mutex)
int(* polarssl_mutex_unlock)(threading_mutex_t *mutex)
int(* polarssl_mutex_init)(threading_mutex_t *mutex)
#define polarssl_fprintf
Definition: platform.h:121