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