.
[gnupg.git] / util / memory.c
1 /* memory.c  -  memory allocation
2  *      Copyright (C) 1998 Free Software Foundation, Inc.
3  *
4  * We use our own memory allocation functions instead of plain malloc(),
5  * so that we can provide some special enhancements:
6  *  a) functions to provide memory from a secure memory.
7  *  b) by looking at the requested allocation size we
8  *     can reuse memory very quickly (e.g. MPI storage)
9  *     (really needed?)
10  *  c) memory usage reporting if compiled with M_DEBUG
11  *  d) memory checking if compiled with M_GUARD
12  *
13  * This file is part of GNUPG.
14  *
15  * GNUPG is free software; you can redistribute it and/or modify
16  * it under the terms of the GNU General Public License as published by
17  * the Free Software Foundation; either version 2 of the License, or
18  * (at your option) any later version.
19  *
20  * GNUPG is distributed in the hope that it will be useful,
21  * but WITHOUT ANY WARRANTY; without even the implied warranty of
22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
23  * GNU General Public License for more details.
24  *
25  * You should have received a copy of the GNU General Public License
26  * along with this program; if not, write to the Free Software
27  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
28  */
29
30 #include <config.h>
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34 #include <stdarg.h>
35
36 #include "types.h"
37 #include "memory.h"
38 #include "util.h"
39
40
41 #define MAGIC_NOR_BYTE 0x55
42 #define MAGIC_SEC_BYTE 0xcc
43 #define MAGIC_END_BYTE 0xaa
44
45 #if SIZEOF_UNSIGNED_LONG == 8
46   #define EXTRA_ALIGN 4
47 #else
48   #define EXTRA_ALIGN 0
49 #endif
50
51 const void membug( const char *fmt, ... );
52
53 #ifdef M_DEBUG
54   #ifndef M_GUARD
55     #define M_GUARD 1
56   #endif
57   #undef m_alloc
58   #undef m_alloc_clear
59   #undef m_alloc_secure
60   #undef m_alloc_secure_clear
61   #undef m_realloc
62   #undef m_free
63   #undef m_check
64   #undef m_strdup
65   #define FNAME(a)  m_debug_ ##a
66   #define FNAMEPRT  , const char *info
67   #define FNAMEARG  , info
68   #define store_len(p,n,m) do { add_entry(p,n,m, \
69                                         info, __FUNCTION__);  } while(0)
70 #else
71   #define FNAME(a)  m_ ##a
72   #define FNAMEPRT
73   #define FNAMEARG
74   #define store_len(p,n,m) do { ((byte*)p)[EXTRA_ALIGN+0] = n;                \
75                                 ((byte*)p)[EXTRA_ALIGN+1] = n >> 8 ;          \
76                                 ((byte*)p)[EXTRA_ALIGN+2] = n >> 16 ;         \
77                                 ((byte*)p)[EXTRA_ALIGN+3] = m? MAGIC_SEC_BYTE \
78                                                  : MAGIC_NOR_BYTE;  \
79                               } while(0)
80 #endif
81
82
83 #ifdef M_DEBUG  /* stuff used for memory debuging */
84
85 struct info_entry {
86     struct info_entry *next;
87     unsigned count;     /* call count */
88     const char *info;   /* the reference to the info string */
89 };
90
91 struct memtbl_entry {
92     const void *user_p;  /* for reference: the pointer given to the user */
93     size_t      user_n;  /* length requested by the user */
94     struct memtbl_entry *next; /* to build a list of unused entries */
95     const struct info_entry *info; /* points into the table with */
96                                    /* the info strings */
97     unsigned inuse:1; /* this entry is in use */
98     unsigned count:31;
99 };
100
101
102 #define INFO_BUCKETS 53
103 #define info_hash(p)  ( *(u32*)((p)) % INFO_BUCKETS )
104 static struct info_entry *info_strings[INFO_BUCKETS]; /* hash table */
105
106 static struct memtbl_entry *memtbl;  /* the table with the memory info */
107 static unsigned memtbl_size;    /* number of allocated entries */
108 static unsigned memtbl_len;     /* number of used entries */
109 static struct memtbl_entry *memtbl_unused;/* to keep track of unused entries */
110
111 static void dump_table_at_exit(void);
112 static void dump_table(void);
113 static void check_allmem( const char *info );
114
115 /****************
116  * Put the new P into the debug table and return a pointer to the table entry.
117  * mode is true for security. BY is the name of the function which called us.
118  */
119 static void
120 add_entry( byte *p, unsigned n, int mode, const char *info, const char *by )
121 {
122     unsigned index;
123     struct memtbl_entry *e;
124     struct info_entry *ie;
125
126     if( memtbl_len < memtbl_size  )
127         index = memtbl_len++;
128     else {
129         struct memtbl_entry *e;
130         /* look for a used entry in the table.  We take the first one,
131          * so that freed entries remain as long as possible in the table
132          * (free appends a new one)
133          */
134         if( (e = memtbl_unused) ) {
135             index = e - memtbl;
136             memtbl_unused = e->next;
137             e->next = NULL;
138         }
139         else { /* no free entries in the table: extend the table */
140             if( !memtbl_size ) { /* first time */
141                 memtbl_size = 100;
142                 if( !(memtbl = calloc( memtbl_size, sizeof *memtbl )) )
143                     membug("memory debug table malloc failed\n");
144                 index = 0;
145                 memtbl_len = 1;
146                 atexit( dump_table_at_exit );
147             }
148             else { /* realloc */
149                 unsigned n = memtbl_size / 4; /* enlarge by 25% */
150                 if(!(memtbl = realloc(memtbl, (memtbl_size+n)*sizeof *memtbl)))
151                     membug("memory debug table realloc failed\n");
152                 memset(memtbl+memtbl_size, 0, n*sizeof *memtbl );
153                 memtbl_size += n;
154                 index = memtbl_len++;
155             }
156         }
157     }
158     e = memtbl+index;
159     if( e->inuse )
160         membug("Ooops: entry %u is flagged as in use\n", index);
161     e->user_p = p + 4;
162     e->user_n = n;
163     e->count++;
164     if( e->next )
165         membug("Ooops: entry is in free entry list\n");
166     /* do we already have this info string */
167     for( ie = info_strings[info_hash(info)]; ie; ie = ie->next )
168         if( ie->info == info )
169             break;
170     if( !ie ) { /* no: make a new entry */
171         if( !(ie = malloc( sizeof *ie )) )
172             membug("can't allocate info entry\n");
173         ie->next = info_strings[info_hash(info)];
174         info_strings[info_hash(info)] = ie;
175         ie->info = info;
176         ie->count = 0;
177     }
178     ie->count++;
179     e->info = ie;
180     e->inuse = 1;
181
182     /* put the index at the start of the memory */
183     p[0] = index;
184     p[1] = index >> 8 ;
185     p[2] = index >> 16 ;
186     p[3] = mode? MAGIC_SEC_BYTE : MAGIC_NOR_BYTE  ;
187     if( DBG_MEMORY )
188         log_debug( "%s allocates %u bytes using %s\n", info, e->user_n, by );
189 }
190
191
192
193 /****************
194  * Check that the memory block is correct. The magic byte has already been
195  * checked. Checks which are done here:
196  *    - see whether the index points into our memory table
197  *    - see whether P is the same as the one stored in the table
198  *    - see whether we have already freed this block.
199  */
200 struct memtbl_entry *
201 check_mem( const byte *p, const char *info )
202 {
203     unsigned n;
204     struct memtbl_entry *e;
205
206     n  = p[EXTRA_ALIGN+0];
207     n |= p[EXTRA_ALIGN+1] << 8;
208     n |= p[EXTRA_ALIGN+2] << 16;
209
210     if( n >= memtbl_len )
211         membug("memory at %p corrupted: index=%u table_len=%u (%s)\n",
212                                       p+EXTRA_ALIGN+4, n, memtbl_len, info );
213     e = memtbl+n;
214
215     if( e->user_p != p+EXTRA_ALIGN+4 )
216         membug("memory at %p corrupted: reference mismatch (%s)\n",
217                                                         p+EXTRA_ALIGN+4, info );
218     if( !e->inuse )
219         membug("memory at %p corrupted: marked as free (%s)\n",
220                                                         p+EXTRA_ALIGN+4, info );
221
222     if( !(p[EXTRA_ALIGN+3] == MAGIC_NOR_BYTE
223         || p[EXTRA_ALIGN+3] == MAGIC_SEC_BYTE) )
224         membug("memory at %p corrupted: underflow=%02x (%s)\n",
225                                  p+EXTRA_ALIGN+4, p[EXTRA_ALIGN+3], info );
226     if( p[EXTRA_ALIGN+4+e->user_n] != MAGIC_END_BYTE )
227         membug("memory at %p corrupted: overflow=%02x (%s)\n",
228                      p+EXTRA_ALIGN+4, p[EXTRA_ALIGN+4+e->user_n], info );
229     return e;
230 }
231
232
233 /****************
234  * free the entry and the memory (replaces free)
235  */
236 static void
237 free_entry( byte *p, const char *info )
238 {
239     struct memtbl_entry *e, *e2;
240
241     check_allmem("add_entry");
242
243     e = check_mem(p, info);
244     if( DBG_MEMORY )
245         log_debug( "%s frees %u bytes alloced by %s\n",
246                                 info, e->user_n, e->info->info );
247     if( !e->inuse ) {
248         if( e->user_p == p + EXTRA_ALIGN+ 4 )
249             membug("freeing an already freed pointer at %p\n", p+EXTRA_ALIGN+4 );
250         else
251             membug("freeing pointer %p which is flagged as freed\n", p+EXTRA_ALIGN+4 );
252     }
253
254     e->inuse = 0;
255     e->next = NULL;
256     if( !memtbl_unused )
257         memtbl_unused = e;
258     else {
259         for(e2=memtbl_unused; e2->next; e2 = e2->next )
260             ;
261         e2->next = e;
262     }
263     memset(p,'f', e->user_n+5);
264     free(p);
265 }
266
267 static void
268 dump_entry(struct memtbl_entry *e )
269 {
270     unsigned n = e - memtbl;
271
272     fprintf(stderr, "mem %4u%c %5u %p %5u %s (%u)\n",
273          n, e->inuse?'a':'u', e->count,  e->user_p, e->user_n,
274                               e->info->info, e->info->count );
275
276
277 }
278
279
280 static void
281 dump_table_at_exit( void)
282 {
283     if( DBG_MEMSTAT )
284         dump_table();
285 }
286
287 static void
288 dump_table( void)
289 {
290     unsigned n;
291     struct memtbl_entry *e;
292     ulong sum = 0, chunks =0;
293
294     for( e = memtbl, n = 0; n < memtbl_len; n++, e++ ) {
295         if(e->inuse) {
296             dump_entry(e);
297             sum += e->user_n;
298             chunks++;
299         }
300     }
301     fprintf(stderr, "          memory used: %8lu bytes in %ld chunks\n",
302                                                            sum, chunks );
303 }
304
305 static void
306 check_allmem( const char *info )
307 {
308     unsigned n;
309     struct memtbl_entry *e;
310
311     for( e = memtbl, n = 0; n < memtbl_len; n++, e++ )
312         if( e->inuse )
313             check_mem(e->user_p-4-EXTRA_ALIGN, info);
314 }
315
316 #endif /* M_DEBUG */
317
318 const void
319 membug( const char *fmt, ... )
320 {
321     va_list arg_ptr ;
322
323     fprintf(stderr, "\nMemory Error: " ) ;
324     va_start( arg_ptr, fmt ) ;
325     vfprintf(stderr,fmt,arg_ptr) ;
326     va_end(arg_ptr);
327     fflush(stderr);
328   #ifdef M_DEBUG
329     if( DBG_MEMSTAT )
330         dump_table();
331   #endif
332     abort();
333 }
334
335
336 static void
337 out_of_core(size_t n, int secure)
338 {
339     log_fatal("out of %s memory while allocating %u bytes\n",
340                         secure? "secure":"" ,(unsigned)n );
341
342 }
343
344 /****************
345  * Allocate memory of size n.
346  * This function gives up if we do not have enough memory
347  */
348 void *
349 FNAME(alloc)( size_t n FNAMEPRT )
350 {
351     char *p;
352
353   #ifdef M_GUARD
354     if( !(p = malloc( n + EXTRA_ALIGN+5 )) )
355         out_of_core(n,0);
356     store_len(p,n,0);
357     p[4+EXTRA_ALIGN+n] = MAGIC_END_BYTE;
358     return p+EXTRA_ALIGN+4;
359   #else
360     if( !(p = malloc( n )) )
361         out_of_core(n,0);
362     return p;
363   #endif
364 }
365
366 /****************
367  * Allocate memory of size n from the secure memory pool.
368  * This function gives up if we do not have enough memory
369  */
370 void *
371 FNAME(alloc_secure)( size_t n FNAMEPRT )
372 {
373     char *p;
374
375   #ifdef M_GUARD
376     if( !(p = secmem_malloc( n +EXTRA_ALIGN+ 5 )) )
377         out_of_core(n,1);
378     store_len(p,n,1);
379     p[4+EXTRA_ALIGN+n] = MAGIC_END_BYTE;
380     return p+EXTRA_ALIGN+4;
381   #else
382     if( !(p = secmem_malloc( n )) )
383         out_of_core(n,1);
384     return p;
385   #endif
386 }
387
388 void *
389 FNAME(alloc_clear)( size_t n FNAMEPRT )
390 {
391     void *p;
392     p = FNAME(alloc)( n FNAMEARG );
393     memset(p, 0, n );
394     return p;
395 }
396
397 void *
398 FNAME(alloc_secure_clear)( size_t n FNAMEPRT)
399 {
400     void *p;
401     p = FNAME(alloc_secure)( n FNAMEARG );
402     memset(p, 0, n );
403     return p;
404 }
405
406
407 /****************
408  * realloc and clear the old space
409  */
410 void *
411 FNAME(realloc)( void *a, size_t n FNAMEPRT )
412 {
413   #ifdef M_GUARD
414     unsigned char *p = a;
415     void *b;
416     size_t len = m_size(a);
417
418     if( len >= n ) /* we don't shrink for now */
419         return a;
420     if( p[-1] == MAGIC_SEC_BYTE )
421         b = FNAME(alloc_secure_clear)(n FNAMEARG);
422     else
423         b = FNAME(alloc_clear)(n FNAMEARG);
424     FNAME(check)(NULL FNAMEARG);
425     memcpy(b, a, len );
426     FNAME(free)(p FNAMEARG);
427   #else
428     void *b;
429
430     if( m_is_secure(a) ) {
431         if( !(b = secmem_realloc( a, n )) )
432             out_of_core(n,1);
433     }
434     else {
435         if( !(b = realloc( a, n )) )
436             out_of_core(n,0);
437     }
438   #endif
439     return b;
440 }
441
442
443
444 /****************
445  * Free a pointer
446  */
447 void
448 FNAME(free)( void *a FNAMEPRT )
449 {
450     byte *p = a;
451
452     if( !p )
453         return;
454   #ifdef M_DEBUG
455     free_entry(p-EXTRA_ALIGN-4, info);
456   #elif  M_GUARD
457     m_check(p);
458     if( m_is_secure(a) )
459         secmem_free(p-EXTRA_ALIGN-4);
460     else
461         free(p-EXTRA_ALIGN-4);
462   #else
463     if( m_is_secure(a) )
464         secmem_free(p);
465     else
466         free(p);
467   #endif
468 }
469
470
471 void
472 FNAME(check)( const void *a FNAMEPRT )
473 {
474   #ifdef M_GUARD
475     const byte *p = a;
476
477   #ifdef M_DEBUG
478     if( p )
479         check_mem(p-EXTRA_ALIGN-4, info);
480     else
481         check_allmem(info);
482   #else
483     if( !p )
484         return;
485     if( !(p[-1] == MAGIC_NOR_BYTE || p[-1] == MAGIC_SEC_BYTE) )
486         membug("memory at %p corrupted (underflow=%02x)\n", p, p[-1] );
487     else if( p[m_size(p)] != MAGIC_END_BYTE )
488         membug("memory at %p corrupted (overflow=%02x)\n", p, p[-1] );
489   #endif
490   #endif
491 }
492
493
494 size_t
495 m_size( const void *a )
496 {
497   #ifndef M_GUARD
498     log_debug("Ooops, m_size called\n");
499     return 0;
500   #else
501     const byte *p = a;
502     size_t n;
503
504   #ifdef M_DEBUG
505     n = check_mem(p-EXTRA_ALIGN-4, "m_size")->user_n;
506   #else
507     n  = ((byte*)p)[-4];
508     n |= ((byte*)p)[-3] << 8;
509     n |= ((byte*)p)[-2] << 16;
510   #endif
511     return n;
512   #endif
513 }
514
515
516 #if 0 /* not used */
517 /****************
518  * Make a copy of the memory block at a
519  */
520 void *
521 FNAME(copy)( const void *a FNAMEPRT )
522 {
523     void *b;
524     size_t n;
525
526     if( !a )
527         return NULL;
528
529     n = m_size(a); Aiiiih woher nehmen
530     if( m_is_secure(a) )
531         b = FNAME(alloc_secure)(n FNAMEARG);
532     else
533         b = FNAME(alloc)(n FNAMEARG);
534     memcpy(b, a, n );
535     return b;
536 }
537 #endif
538
539 char *
540 FNAME(strdup)( const char *a FNAMEPRT )
541 {
542     size_t n = strlen(a);
543     char *p = FNAME(alloc)(n+1 FNAMEARG);
544     strcpy(p, a);
545     return p;
546 }
547