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