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