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