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