See ChangeLog: Wed Jul 7 13:23:40 CEST 1999 Werner Koch
[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 #if defined(M_DEBUG) || defined(M_GUARD)
52   static void membug( const char *fmt, ... );
53 #endif
54
55 #ifdef M_DEBUG
56
57   #ifndef M_GUARD
58     #define M_GUARD 1
59   #endif
60   #undef m_alloc
61   #undef m_alloc_clear
62   #undef m_alloc_secure
63   #undef m_alloc_secure_clear
64   #undef m_realloc
65   #undef m_free
66   #undef m_check
67   #undef m_strdup
68   #define FNAME(a)  m_debug_ ##a
69   #define FNAMEPRT  , const char *info
70   #define FNAMEARG  , info
71   #define store_len(p,n,m) do { add_entry(p,n,m, \
72                                         info, __FUNCTION__);  } while(0)
73 #else
74   #define FNAME(a)  m_ ##a
75   #define FNAMEPRT
76   #define FNAMEARG
77   #define store_len(p,n,m) do { ((byte*)p)[EXTRA_ALIGN+0] = n;                \
78                                 ((byte*)p)[EXTRA_ALIGN+1] = n >> 8 ;          \
79                                 ((byte*)p)[EXTRA_ALIGN+2] = n >> 16 ;         \
80                                 ((byte*)p)[EXTRA_ALIGN+3] = m? MAGIC_SEC_BYTE \
81                                                  : MAGIC_NOR_BYTE;  \
82                               } while(0)
83 #endif
84
85
86 #ifdef M_GUARD
87 static long used_memory;
88 #endif
89
90 #ifdef M_DEBUG  /* stuff used for memory debuging */
91
92 struct info_entry {
93     struct info_entry *next;
94     unsigned count;     /* call count */
95     const char *info;   /* the reference to the info string */
96 };
97
98 struct memtbl_entry {
99     const void *user_p;  /* for reference: the pointer given to the user */
100     size_t      user_n;  /* length requested by the user */
101     struct memtbl_entry *next; /* to build a list of unused entries */
102     const struct info_entry *info; /* points into the table with */
103                                    /* the info strings */
104     unsigned inuse:1; /* this entry is in use */
105     unsigned count:31;
106 };
107
108
109 #define INFO_BUCKETS 53
110 #define info_hash(p)  ( *(u32*)((p)) % INFO_BUCKETS )
111 static struct info_entry *info_strings[INFO_BUCKETS]; /* hash table */
112
113 static struct memtbl_entry *memtbl;  /* the table with the memory info */
114 static unsigned memtbl_size;    /* number of allocated entries */
115 static unsigned memtbl_len;     /* number of used entries */
116 static struct memtbl_entry *memtbl_unused;/* to keep track of unused entries */
117
118 static void dump_table_at_exit(void);
119 static void dump_table(void);
120 static void check_allmem( const char *info );
121
122 /****************
123  * Put the new P into the debug table and return a pointer to the table entry.
124  * mode is true for security. BY is the name of the function which called us.
125  */
126 static void
127 add_entry( byte *p, unsigned n, int mode, const char *info, const char *by )
128 {
129     unsigned index;
130     struct memtbl_entry *e;
131     struct info_entry *ie;
132
133     if( memtbl_len < memtbl_size  )
134         index = memtbl_len++;
135     else {
136         struct memtbl_entry *e;
137         /* look for a used entry in the table.  We take the first one,
138          * so that freed entries remain as long as possible in the table
139          * (free appends a new one)
140          */
141         if( (e = memtbl_unused) ) {
142             index = e - memtbl;
143             memtbl_unused = e->next;
144             e->next = NULL;
145         }
146         else { /* no free entries in the table: extend the table */
147             if( !memtbl_size ) { /* first time */
148                 memtbl_size = 100;
149                 if( !(memtbl = calloc( memtbl_size, sizeof *memtbl )) )
150                     membug("memory debug table malloc failed\n");
151                 index = 0;
152                 memtbl_len = 1;
153                 atexit( dump_table_at_exit );
154             }
155             else { /* realloc */
156                 unsigned n = memtbl_size / 4; /* enlarge by 25% */
157                 if(!(memtbl = realloc(memtbl, (memtbl_size+n)*sizeof *memtbl)))
158                     membug("memory debug table realloc failed\n");
159                 memset(memtbl+memtbl_size, 0, n*sizeof *memtbl );
160                 memtbl_size += n;
161                 index = memtbl_len++;
162             }
163         }
164     }
165     e = memtbl+index;
166     if( e->inuse )
167         membug("Ooops: entry %u is flagged as in use\n", index);
168     e->user_p = p + 4;
169     e->user_n = n;
170     e->count++;
171     if( e->next )
172         membug("Ooops: entry is in free entry list\n");
173     /* do we already have this info string */
174     for( ie = info_strings[info_hash(info)]; ie; ie = ie->next )
175         if( ie->info == info )
176             break;
177     if( !ie ) { /* no: make a new entry */
178         if( !(ie = malloc( sizeof *ie )) )
179             membug("can't allocate info entry\n");
180         ie->next = info_strings[info_hash(info)];
181         info_strings[info_hash(info)] = ie;
182         ie->info = info;
183         ie->count = 0;
184     }
185     ie->count++;
186     e->info = ie;
187     e->inuse = 1;
188
189     /* put the index at the start of the memory */
190     p[0] = index;
191     p[1] = index >> 8 ;
192     p[2] = index >> 16 ;
193     p[3] = mode? MAGIC_SEC_BYTE : MAGIC_NOR_BYTE  ;
194     if( DBG_MEMORY )
195         log_debug( "%s allocates %u bytes using %s\n", info, e->user_n, by );
196 }
197
198
199
200 /****************
201  * Check that the memory block is correct. The magic byte has already been
202  * checked. Checks which are done here:
203  *    - see whether the index points into our memory table
204  *    - see whether P is the same as the one stored in the table
205  *    - see whether we have already freed this block.
206  */
207 struct memtbl_entry *
208 check_mem( const byte *p, const char *info )
209 {
210     unsigned n;
211     struct memtbl_entry *e;
212
213     n  = p[EXTRA_ALIGN+0];
214     n |= p[EXTRA_ALIGN+1] << 8;
215     n |= p[EXTRA_ALIGN+2] << 16;
216
217     if( n >= memtbl_len )
218         membug("memory at %p corrupted: index=%u table_len=%u (%s)\n",
219                                       p+EXTRA_ALIGN+4, n, memtbl_len, info );
220     e = memtbl+n;
221
222     if( e->user_p != p+EXTRA_ALIGN+4 )
223         membug("memory at %p corrupted: reference mismatch (%s)\n",
224                                                         p+EXTRA_ALIGN+4, info );
225     if( !e->inuse )
226         membug("memory at %p corrupted: marked as free (%s)\n",
227                                                         p+EXTRA_ALIGN+4, info );
228
229     if( !(p[EXTRA_ALIGN+3] == MAGIC_NOR_BYTE
230         || p[EXTRA_ALIGN+3] == MAGIC_SEC_BYTE) )
231         membug("memory at %p corrupted: underflow=%02x (%s)\n",
232                                  p+EXTRA_ALIGN+4, p[EXTRA_ALIGN+3], info );
233     if( p[EXTRA_ALIGN+4+e->user_n] != MAGIC_END_BYTE )
234         membug("memory at %p corrupted: overflow=%02x (%s)\n",
235                      p+EXTRA_ALIGN+4, p[EXTRA_ALIGN+4+e->user_n], info );
236     return e;
237 }
238
239
240 /****************
241  * free the entry and the memory (replaces free)
242  */
243 static void
244 free_entry( byte *p, const char *info )
245 {
246     struct memtbl_entry *e, *e2;
247
248     check_allmem("add_entry");
249
250     e = check_mem(p, info);
251     if( DBG_MEMORY )
252         log_debug( "%s frees %u bytes alloced by %s\n",
253                                 info, e->user_n, e->info->info );
254     if( !e->inuse ) {
255         if( e->user_p == p + EXTRA_ALIGN+ 4 )
256             membug("freeing an already freed pointer at %p\n", p+EXTRA_ALIGN+4 );
257         else
258             membug("freeing pointer %p which is flagged as freed\n", p+EXTRA_ALIGN+4 );
259     }
260
261     e->inuse = 0;
262     e->next = NULL;
263     if( !memtbl_unused )
264         memtbl_unused = e;
265     else {
266         for(e2=memtbl_unused; e2->next; e2 = e2->next )
267             ;
268         e2->next = e;
269     }
270     memset(p,'f', e->user_n+5);
271     free(p);
272 }
273
274 static void
275 dump_entry(struct memtbl_entry *e )
276 {
277     unsigned n = e - memtbl;
278
279     fprintf(stderr, "mem %4u%c %5u %p %5u %s (%u)\n",
280          n, e->inuse?'a':'u', e->count,  e->user_p, e->user_n,
281                               e->info->info, e->info->count );
282
283
284 }
285
286
287 static void
288 dump_table_at_exit( void)
289 {
290     if( DBG_MEMSTAT )
291         dump_table();
292 }
293
294 static void
295 dump_table( void)
296 {
297     unsigned n;
298     struct memtbl_entry *e;
299     ulong sum = 0, chunks =0;
300
301     for( e = memtbl, n = 0; n < memtbl_len; n++, e++ ) {
302         if(e->inuse) {
303             dump_entry(e);
304             sum += e->user_n;
305             chunks++;
306         }
307     }
308     fprintf(stderr, "          memory used: %8lu bytes in %ld chunks\n",
309                                                            sum, chunks );
310 }
311
312
313 static void
314 check_allmem( const char *info )
315 {
316     unsigned n;
317     struct memtbl_entry *e;
318
319     for( e = memtbl, n = 0; n < memtbl_len; n++, e++ )
320         if( e->inuse )
321             check_mem(e->user_p-4-EXTRA_ALIGN, info);
322 }
323
324 #endif /* M_DEBUG */
325
326 #if defined(M_DEBUG) || defined(M_GUARD)
327 static void
328 membug( const char *fmt, ... )
329 {
330     va_list arg_ptr ;
331
332     fprintf(stderr, "\nMemory Error: " ) ;
333     va_start( arg_ptr, fmt ) ;
334     vfprintf(stderr,fmt,arg_ptr) ;
335     va_end(arg_ptr);
336     fflush(stderr);
337   #ifdef M_DEBUG
338     if( DBG_MEMSTAT )
339         dump_table();
340   #endif
341     abort();
342 }
343 #endif
344
345 void
346 m_print_stats( const char *prefix )
347 {
348   #ifdef M_DEBUG
349     unsigned n;
350     struct memtbl_entry *e;
351     ulong sum = 0, chunks =0;
352
353     for( e = memtbl, n = 0; n < memtbl_len; n++, e++ ) {
354         if(e->inuse) {
355             sum += e->user_n;
356             chunks++;
357         }
358     }
359
360     log_debug( "%s%smemstat: %8lu bytes in %ld chunks used\n",
361                 prefix? prefix:"", prefix? ": ":"", sum, chunks );
362   #elif defined(M_GUARD)
363     log_debug( "%s%smemstat: %8ld bytes\n",
364                 prefix? prefix:"", prefix? ": ":"", used_memory );
365   #endif
366 }
367
368 void
369 m_dump_table( const char *prefix )
370 {
371   #if M_DEBUG
372     fprintf(stderr,"Memory-Table-Dump: %s\n", prefix);
373     dump_table();
374   #endif
375     m_print_stats( prefix );
376 }
377
378
379 static void
380 out_of_core(size_t n, int secure)
381 {
382     log_fatal("out of %s memory while allocating %u bytes\n",
383                         secure? "secure":"" ,(unsigned)n );
384
385 }
386
387 /****************
388  * Allocate memory of size n.
389  * This function gives up if we do not have enough memory
390  */
391 void *
392 FNAME(alloc)( size_t n FNAMEPRT )
393 {
394     char *p;
395
396   #ifdef M_GUARD
397     if( !(p = malloc( n + EXTRA_ALIGN+5 )) )
398         out_of_core(n,0);
399     store_len(p,n,0);
400     used_memory += n;
401     p[4+EXTRA_ALIGN+n] = MAGIC_END_BYTE;
402     return p+EXTRA_ALIGN+4;
403   #else
404     if( !(p = malloc( n )) )
405         out_of_core(n,0);
406     return p;
407   #endif
408 }
409
410 /****************
411  * Allocate memory of size n from the secure memory pool.
412  * This function gives up if we do not have enough memory
413  */
414 void *
415 FNAME(alloc_secure)( size_t n FNAMEPRT )
416 {
417     char *p;
418
419   #ifdef M_GUARD
420     if( !(p = secmem_malloc( n +EXTRA_ALIGN+ 5 )) )
421         out_of_core(n,1);
422     store_len(p,n,1);
423     p[4+EXTRA_ALIGN+n] = MAGIC_END_BYTE;
424     return p+EXTRA_ALIGN+4;
425   #else
426     if( !(p = secmem_malloc( n )) )
427         out_of_core(n,1);
428     return p;
429   #endif
430 }
431
432 void *
433 FNAME(alloc_clear)( size_t n FNAMEPRT )
434 {
435     void *p;
436     p = FNAME(alloc)( n FNAMEARG );
437     memset(p, 0, n );
438     return p;
439 }
440
441 void *
442 FNAME(alloc_secure_clear)( size_t n FNAMEPRT)
443 {
444     void *p;
445     p = FNAME(alloc_secure)( n FNAMEARG );
446     memset(p, 0, n );
447     return p;
448 }
449
450
451 /****************
452  * realloc and clear the old space
453  */
454 void *
455 FNAME(realloc)( void *a, size_t n FNAMEPRT )
456 {
457   #ifdef M_GUARD
458     unsigned char *p = a;
459     void *b;
460     size_t len = m_size(a);
461
462     if( len >= n ) /* we don't shrink for now */
463         return a;
464     if( p[-1] == MAGIC_SEC_BYTE )
465         b = FNAME(alloc_secure_clear)(n FNAMEARG);
466     else
467         b = FNAME(alloc_clear)(n FNAMEARG);
468     FNAME(check)(NULL FNAMEARG);
469     memcpy(b, a, len );
470     FNAME(free)(p FNAMEARG);
471   #else
472     void *b;
473
474     if( m_is_secure(a) ) {
475         if( !(b = secmem_realloc( a, n )) )
476             out_of_core(n,1);
477     }
478     else {
479         if( !(b = realloc( a, n )) )
480             out_of_core(n,0);
481     }
482   #endif
483     return b;
484 }
485
486
487
488 /****************
489  * Free a pointer
490  */
491 void
492 FNAME(free)( void *a FNAMEPRT )
493 {
494     byte *p = a;
495
496     if( !p )
497         return;
498   #ifdef M_DEBUG
499     free_entry(p-EXTRA_ALIGN-4, info);
500   #elif  M_GUARD
501     m_check(p);
502     if( m_is_secure(a) )
503         secmem_free(p-EXTRA_ALIGN-4);
504     else {
505         used_memory -= m_size(a);
506         free(p-EXTRA_ALIGN-4);
507     }
508   #else
509     if( m_is_secure(a) )
510         secmem_free(p);
511     else
512         free(p);
513   #endif
514 }
515
516
517 void
518 FNAME(check)( const void *a FNAMEPRT )
519 {
520   #ifdef M_GUARD
521     const byte *p = a;
522
523   #ifdef M_DEBUG
524     if( p )
525         check_mem(p-EXTRA_ALIGN-4, info);
526     else
527         check_allmem(info);
528   #else
529     if( !p )
530         return;
531     if( !(p[-1] == MAGIC_NOR_BYTE || p[-1] == MAGIC_SEC_BYTE) )
532         membug("memory at %p corrupted (underflow=%02x)\n", p, p[-1] );
533     else if( p[m_size(p)] != MAGIC_END_BYTE )
534         membug("memory at %p corrupted (overflow=%02x)\n", p, p[-1] );
535   #endif
536   #endif
537 }
538
539
540 size_t
541 m_size( const void *a )
542 {
543   #ifndef M_GUARD
544     log_debug("Ooops, m_size called\n");
545     return 0;
546   #else
547     const byte *p = a;
548     size_t n;
549
550   #ifdef M_DEBUG
551     n = check_mem(p-EXTRA_ALIGN-4, "m_size")->user_n;
552   #else
553     n  = ((byte*)p)[-4];
554     n |= ((byte*)p)[-3] << 8;
555     n |= ((byte*)p)[-2] << 16;
556   #endif
557     return n;
558   #endif
559 }
560
561
562 #if 0 /* not used */
563 /****************
564  * Make a copy of the memory block at a
565  */
566 void *
567 FNAME(copy)( const void *a FNAMEPRT )
568 {
569     void *b;
570     size_t n;
571
572     if( !a )
573         return NULL;
574
575     n = m_size(a); Aiiiih woher nehmen
576     if( m_is_secure(a) )
577         b = FNAME(alloc_secure)(n FNAMEARG);
578     else
579         b = FNAME(alloc)(n FNAMEARG);
580     memcpy(b, a, n );
581     return b;
582 }
583 #endif
584
585 char *
586 FNAME(strdup)( const char *a FNAMEPRT )
587 {
588     size_t n = strlen(a);
589     char *p = FNAME(alloc)(n+1 FNAMEARG);
590     strcpy(p, a);
591     return p;
592 }
593