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