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