Improved prime number test
[gnupg.git] / util / memory.c
1 /* memory.c  -  memory allocation
2  *      Copyright (c) 1997 by Werner Koch (dd9jn)
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  *     Don't know how to handle it yet, but it may be possible to
8  *     use memory which can't be swapped out.
9  *  b) By looking at the requested allocation size we
10  *     can reuse memory very quickly (e.g. MPI storage)
11  *  c) A controlbyte gives us the opportunity to use only one
12  *     free() function and do some overflow checking.
13  *  d) memory checking and reporting if compiled with M_DEBUG
14  *
15  * This file is part of G10.
16  *
17  * G10 is free software; you can redistribute it and/or modify
18  * it under the terms of the GNU General Public License as published by
19  * the Free Software Foundation; either version 2 of the License, or
20  * (at your option) any later version.
21  *
22  * G10 is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
25  * GNU General Public License for more details.
26  *
27  * You should have received a copy of the GNU General Public License
28  * along with this program; if not, write to the Free Software
29  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
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 const void membug( const char *fmt, ... );
48
49 #ifdef M_DEBUG
50   #undef m_alloc
51   #undef m_alloc_clear
52   #undef m_alloc_secure
53   #undef m_alloc_secure_clear
54   #undef m_realloc
55   #undef m_free
56   #undef m_check
57   #define FNAME(a)  m_debug_ ##a
58   #define FNAMEPRT  , const char *info
59   #define FNAMEARG  , info
60   #define store_len(p,n,m) do { add_entry(p,n,m, \
61                                         info, __FUNCTION__);  } while(0)
62 #else
63   #define FNAME(a)  m_ ##a
64   #define FNAMEPRT
65   #define FNAMEARG
66   #define store_len(p,n,m) do { ((byte*)p)[0] = n;                  \
67                                 ((byte*)p)[1] = n >> 8 ;            \
68                                 ((byte*)p)[2] = n >> 16 ;           \
69                                 ((byte*)p)[3] = m? MAGIC_SEC_BYTE   \
70                                                  : MAGIC_NOR_BYTE;  \
71                               } while(0)
72 #endif
73
74
75 #ifdef M_DEBUG  /* stuff used for memory debuging */
76
77 struct info_entry {
78     struct info_entry *next;
79     unsigned count;     /* call count */
80     const char *info;   /* the reference to the info string */
81 };
82
83 struct memtbl_entry {
84     const void *user_p;  /* for reference: the pointer given to the user */
85     size_t      user_n;  /* length requested by the user */
86     struct memtbl_entry *next; /* to build a list of unused entries */
87     const struct info_entry *info; /* points into the table with */
88                                    /* the info strings */
89     unsigned inuse:1; /* this entry is in use */
90     unsigned count:31;
91 };
92
93
94 #define INFO_BUCKETS 53
95 #define info_hash(p)  ( *(u32*)((p)) % INFO_BUCKETS )
96 static struct info_entry *info_strings[INFO_BUCKETS]; /* hash table */
97
98 static struct memtbl_entry *memtbl;  /* the table with the memory infos */
99 static unsigned memtbl_size;    /* number of allocated entries */
100 static unsigned memtbl_len;     /* number of used entries */
101 static struct memtbl_entry *memtbl_unused;/* to keep track of unused entries */
102
103 static void dump_table(void);
104 static void check_allmem( const char *info );
105
106 /****************
107  * Put the new P into the debug table and return a pointer to the table entry.
108  * mode is true for security. BY is the name of the function which called us.
109  */
110 static void
111 add_entry( byte *p, unsigned n, int mode, const char *info, const char *by )
112 {
113     unsigned index;
114     struct memtbl_entry *e;
115     struct info_entry *ie;
116
117     if( memtbl_len < memtbl_size  )
118         index = memtbl_len++;
119     else {
120         struct memtbl_entry *e;
121         /* look for an used entry in the table. We take the first one,
122          * so that freed entries remain as long as possible in the table
123          * (free appends a new one)
124          */
125         if( (e = memtbl_unused) ) {
126             index = e - memtbl;
127             memtbl_unused = e->next;
128             e->next = NULL;
129         }
130         else { /* no free entries in the table: extend the table */
131             if( !memtbl_size ) { /* first time */
132                 memtbl_size = 100;
133                 if( !(memtbl = calloc( memtbl_size, sizeof *memtbl )) )
134                     membug("memory debug table malloc failed\n");
135                 index = 0;
136                 memtbl_len = 1;
137                 if( DBG_MEMSTAT )
138                     atexit( dump_table );
139             }
140             else { /* realloc */
141                 unsigned n = memtbl_size / 4; /* enlarge by 25% */
142                 if(!(memtbl = realloc(memtbl, (memtbl_size+n)*sizeof *memtbl)))
143                     membug("memory debug table realloc failed\n");
144                 memset(memtbl+memtbl_size, 0, n*sizeof *memtbl );
145                 memtbl_size += n;
146                 index = memtbl_len++;
147             }
148         }
149     }
150     e = memtbl+index;
151     if( e->inuse )
152         membug("Ooops: entry %u is flagged as in use\n", index);
153     e->user_p = p + 4;
154     e->user_n = n;
155     e->count++;
156     if( e->next )
157         membug("Ooops: entry is in free entry list\n");
158     /* do we already have this info string */
159     for( ie = info_strings[info_hash(info)]; ie; ie = ie->next )
160         if( ie->info == info )
161             break;
162     if( !ie ) { /* no: make a new entry */
163         if( !(ie = malloc( sizeof *ie )) )
164             membug("can't allocate info entry\n");
165         ie->next = info_strings[info_hash(info)];
166         info_strings[info_hash(info)] = ie;
167         ie->info = info;
168         ie->count = 0;
169     }
170     ie->count++;
171     e->info = ie;
172     e->inuse = 1;
173
174     /* put the index at the start of the memory */
175     p[0] = index;
176     p[1] = index >> 8 ;
177     p[2] = index >> 16 ;
178     p[3] = mode? MAGIC_SEC_BYTE : MAGIC_NOR_BYTE  ;
179     if( DBG_MEMORY )
180         log_debug( "%s allocates %u bytes using %s\n", info, e->user_n, by );
181 }
182
183
184
185 /****************
186  * Check that the memory block is correct. The magic byte has already been
187  * checked. Checks which are done here:
188  *    - see wether the index points into our memory table
189  *    - see wether P is the same as the one stored in the table
190  *    - see wether we have already freed this block.
191  */
192 struct memtbl_entry *
193 check_mem( const byte *p, const char *info )
194 {
195     unsigned n;
196     struct memtbl_entry *e;
197
198     n  = p[0];
199     n |= p[1] << 8;
200     n |= p[2] << 16;
201
202     if( n >= memtbl_len )
203         membug("memory at %p corrupted: index=%u table_len=%u (%s)\n",
204                                                  p+4, n, memtbl_len, info );
205     e = memtbl+n;
206
207     if( e->user_p != p+4 )
208         membug("memory at %p corrupted: reference mismatch (%s)\n", p+4, info );
209     if( !e->inuse )
210         membug("memory at %p corrupted: marked as free (%s)\n", p+4, info );
211
212     if( !(p[3] == MAGIC_NOR_BYTE || p[3] == MAGIC_SEC_BYTE) )
213         membug("memory at %p corrupted: underflow=%02x (%s)\n", p+4, p[3], info );
214     if( p[4+e->user_n] != MAGIC_END_BYTE )
215         membug("memory at %p corrupted: overflow=%02x (%s)\n", p+4, p[4+e->user_n], info );
216     return e;
217 }
218
219
220 /****************
221  * free the entry and the memory (replaces free)
222  */
223 static void
224 free_entry( byte *p, const char *info )
225 {
226     struct memtbl_entry *e, *e2;
227
228     check_allmem("add_entry");
229
230     e = check_mem(p, info);
231     if( DBG_MEMORY )
232         log_debug( "%s frees %u bytes alloced by %s\n",
233                                 info, e->user_n, e->info->info );
234     if( !e->inuse ) {
235         if( e->user_p == p + 4 )
236             membug("freeing an already freed pointer at %p\n", p+4 );
237         else
238             membug("freeing pointer %p which is flagged as freed\n", p+4 );
239     }
240
241     e->inuse = 0;
242     e->next = NULL;
243     if( !memtbl_unused )
244         memtbl_unused = e;
245     else {
246         for(e2=memtbl_unused; e2->next; e2 = e2->next )
247             ;
248         e2->next = e;
249     }
250     memset(p,'f', e->user_n+5);
251     free(p);
252 }
253
254 static void
255 dump_entry(struct memtbl_entry *e )
256 {
257     unsigned n = e - memtbl;
258
259     fprintf(stderr, "mem %4u%c %5u %p %5u %s (%u)\n",
260          n, e->inuse?'a':'u', e->count,  e->user_p, e->user_n,
261                               e->info->info, e->info->count );
262
263
264 }
265
266 static void
267 dump_table( void)
268 {
269     unsigned n;
270     struct memtbl_entry *e;
271     ulong sum = 0, chunks =0;
272
273     for( e = memtbl, n = 0; n < memtbl_len; n++, e++ ) {
274         if(e->inuse) {
275             dump_entry(e);
276             sum += e->user_n;
277             chunks++;
278         }
279     }
280     fprintf(stderr, "          memory used: %8lu bytes in %ld chunks\n",
281                                                            sum, chunks );
282 }
283
284 static void
285 check_allmem( const char *info )
286 {
287     unsigned n;
288     struct memtbl_entry *e;
289
290     for( e = memtbl, n = 0; n < memtbl_len; n++, e++ )
291         if( e->inuse )
292             check_mem(e->user_p-4, info);
293 }
294
295 #endif /* M_DEBUG */
296
297 const void
298 membug( const char *fmt, ... )
299 {
300     va_list arg_ptr ;
301
302     fprintf(stderr, "\nMemory Error: " ) ;
303     va_start( arg_ptr, fmt ) ;
304     vfprintf(stderr,fmt,arg_ptr) ;
305     va_end(arg_ptr);
306     fflush(stderr);
307   #ifdef M_DEBUG
308     if( DBG_MEMSTAT )
309         dump_table();
310   #endif
311     abort();
312 }
313
314
315 static void
316 out_of_core(size_t n)
317 {
318     log_fatal("out of memory while allocating %u bytes\n", (unsigned)n );
319 }
320
321 /****************
322  * Allocate memory of size n.
323  * This function gives up if we do not have enough memory
324  */
325 void *
326 FNAME(alloc)( size_t n FNAMEPRT )
327 {
328     char *p;
329
330     if( !(p = malloc( n + 5 )) )
331         out_of_core(n);
332     store_len(p,n,0);
333     p[4+n] = MAGIC_END_BYTE; /* need to add the length somewhere */
334     return p+4;
335 }
336
337 /****************
338  * Allocate memory of size n from the secure memory pool.
339  * This function gives up if we do not have enough memory
340  */
341 void *
342 FNAME(alloc_secure)( size_t n FNAMEPRT )
343 {
344     char *p;
345
346     if( !(p = malloc( n + 5 )) ) /* fixme: should alloc from the secure heap*/
347         out_of_core(n);
348     store_len(p,n,1);
349     p[4+n] = MAGIC_END_BYTE;
350     return p+4;
351 }
352
353 void *
354 FNAME(alloc_clear)( size_t n FNAMEPRT )
355 {
356     void *p;
357     p = FNAME(alloc)( n FNAMEARG );
358     memset(p, 0, n );
359     return p;
360 }
361
362 void *
363 FNAME(alloc_secure_clear)( size_t n FNAMEPRT)
364 {
365     void *p;
366     p = FNAME(alloc_secure)( n FNAMEARG );
367     memset(p, 0, n );
368     return p;
369 }
370
371
372 /****************
373  * realloc and clear the new space
374  */
375 void *
376 FNAME(realloc)( void *a, size_t n FNAMEPRT )
377 {   /* FIXME: should be optimized :-) */
378     unsigned char *p = a;
379     void *b;
380     size_t len = m_size(a);
381
382     if( len >= n ) /* we don't shrink for now */
383         return a;
384     if( p[-1] == MAGIC_SEC_BYTE )
385         b = FNAME(alloc_secure_clear)(n FNAMEARG);
386     else
387         b = FNAME(alloc_clear)(n FNAMEARG);
388     FNAME(check)(NULL FNAMEARG);
389     memcpy(b, a, len );
390     FNAME(free)(p FNAMEARG);
391     return b;
392 }
393
394
395
396 /****************
397  * Free a pointer
398  */
399 void
400 FNAME(free)( void *a FNAMEPRT )
401 {
402     byte *p = a;
403
404     if( !p )
405         return;
406   #ifdef M_DEBUG
407     free_entry(p-4, info);
408   #else
409     m_check(p);
410     free(p-4);
411   #endif
412 }
413
414
415 void
416 FNAME(check)( const void *a FNAMEPRT )
417 {
418     const byte *p = a;
419
420   #ifdef M_DEBUG
421     if( p )
422         check_mem(p-4, info);
423     else
424         check_allmem(info);
425   #else
426     if( !p )
427         return;
428     if( !(p[-1] == MAGIC_NOR_BYTE || p[-1] == MAGIC_SEC_BYTE) )
429         membug("memory at %p corrupted (underflow=%02x)\n", p, p[-1] );
430     else if( p[m_size(p)] != MAGIC_END_BYTE )
431         membug("memory at %p corrupted (overflow=%02x)\n", p, p[-1] );
432   #endif
433 }
434
435
436 size_t
437 m_size( const void *a )
438 {
439     const byte *p = a;
440     size_t n;
441
442   #ifdef M_DEBUG
443     n = check_mem(p-4, "m_size")->user_n;
444   #else
445     n  = ((byte*)p)[-4];
446     n |= ((byte*)p)[-3] << 8;
447     n |= ((byte*)p)[-2] << 16;
448   #endif
449     return n;
450 }
451
452
453 int
454 m_is_secure( const void *p )
455 {
456     return p && ((byte*)p)[-1] == MAGIC_SEC_BYTE;
457 }
458