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