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