1251607Sdim/* Safe automatic memory allocation. 2251607Sdim Copyright (C) 2003, 2006 Free Software Foundation, Inc. 3251607Sdim Written by Bruno Haible <bruno@clisp.org>, 2003. 4251607Sdim 5251607Sdim This program is free software; you can redistribute it and/or modify 6251607Sdim it under the terms of the GNU General Public License as published by 7251607Sdim the Free Software Foundation; either version 2, or (at your option) 8251607Sdim any later version. 9251607Sdim 10251607Sdim This program is distributed in the hope that it will be useful, 11251607Sdim but WITHOUT ANY WARRANTY; without even the implied warranty of 12251607Sdim MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13251607Sdim GNU General Public License for more details. 14251607Sdim 15251607Sdim You should have received a copy of the GNU General Public License 16251607Sdim along with this program; if not, write to the Free Software Foundation, 17251607Sdim Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ 18251607Sdim 19251607Sdim#include <config.h> 20251607Sdim 21251607Sdim/* Specification. */ 22251607Sdim#include "allocsa.h" 23251607Sdim 24251607Sdim/* The speed critical point in this file is freesa() applied to an alloca() 25251607Sdim result: it must be fast, to match the speed of alloca(). The speed of 26251607Sdim mallocsa() and freesa() in the other case are not critical, because they 27251607Sdim are only invoked for big memory sizes. */ 28251607Sdim 29251607Sdim#if HAVE_ALLOCA 30251607Sdim 31251607Sdim/* Store the mallocsa() results in a hash table. This is needed to reliably 32251607Sdim distinguish a mallocsa() result and an alloca() result. 33251607Sdim 34251607Sdim Although it is possible that the same pointer is returned by alloca() and 35251607Sdim by mallocsa() at different times in the same application, it does not lead 36251607Sdim to a bug in freesa(), because: 37251607Sdim - Before a pointer returned by alloca() can point into malloc()ed memory, 38251607Sdim the function must return, and once this has happened the programmer must 39251607Sdim not call freesa() on it anyway. 40251607Sdim - Before a pointer returned by mallocsa() can point into the stack, it 41251607Sdim must be freed. The only function that can free it is freesa(), and 42251607Sdim when freesa() frees it, it also removes it from the hash table. */ 43251607Sdim 44251607Sdim#define MAGIC_NUMBER 0x1415fb4a 45251607Sdim#define MAGIC_SIZE sizeof (int) 46251607Sdim/* This is how the header info would look like without any alignment 47 considerations. */ 48struct preliminary_header { void *next; char room[MAGIC_SIZE]; }; 49/* But the header's size must be a multiple of sa_alignment_max. */ 50#define HEADER_SIZE \ 51 (((sizeof (struct preliminary_header) + sa_alignment_max - 1) / sa_alignment_max) * sa_alignment_max) 52struct header { void *next; char room[HEADER_SIZE - sizeof (struct preliminary_header) + MAGIC_SIZE]; }; 53/* Verify that HEADER_SIZE == sizeof (struct header). */ 54typedef int verify1[2 * (HEADER_SIZE == sizeof (struct header)) - 1]; 55/* We make the hash table quite big, so that during lookups the probability 56 of empty hash buckets is quite high. There is no need to make the hash 57 table resizable, because when the hash table gets filled so much that the 58 lookup becomes slow, it means that the application has memory leaks. */ 59#define HASH_TABLE_SIZE 257 60static void * mallocsa_results[HASH_TABLE_SIZE]; 61 62#endif 63 64void * 65mallocsa (size_t n) 66{ 67#if HAVE_ALLOCA 68 /* Allocate one more word, that serves as an indicator for malloc()ed 69 memory, so that freesa() of an alloca() result is fast. */ 70 size_t nplus = n + HEADER_SIZE; 71 72 if (nplus >= n) 73 { 74 char *p = (char *) malloc (nplus); 75 76 if (p != NULL) 77 { 78 size_t slot; 79 80 p += HEADER_SIZE; 81 82 /* Put a magic number into the indicator word. */ 83 ((int *) p)[-1] = MAGIC_NUMBER; 84 85 /* Enter p into the hash table. */ 86 slot = (unsigned long) p % HASH_TABLE_SIZE; 87 ((struct header *) (p - HEADER_SIZE))->next = mallocsa_results[slot]; 88 mallocsa_results[slot] = p; 89 90 return p; 91 } 92 } 93 /* Out of memory. */ 94 return NULL; 95#else 96# if !MALLOC_0_IS_NONNULL 97 if (n == 0) 98 n = 1; 99# endif 100 return malloc (n); 101#endif 102} 103 104#if HAVE_ALLOCA 105void 106freesa (void *p) 107{ 108 /* mallocsa() may have returned NULL. */ 109 if (p != NULL) 110 { 111 /* Attempt to quickly distinguish the mallocsa() result - which has 112 a magic indicator word - and the alloca() result - which has an 113 uninitialized indicator word. It is for this test that sa_increment 114 additional bytes are allocated in the alloca() case. */ 115 if (((int *) p)[-1] == MAGIC_NUMBER) 116 { 117 /* Looks like a mallocsa() result. To see whether it really is one, 118 perform a lookup in the hash table. */ 119 size_t slot = (unsigned long) p % HASH_TABLE_SIZE; 120 void **chain = &mallocsa_results[slot]; 121 for (; *chain != NULL;) 122 { 123 if (*chain == p) 124 { 125 /* Found it. Remove it from the hash table and free it. */ 126 char *p_begin = (char *) p - HEADER_SIZE; 127 *chain = ((struct header *) p_begin)->next; 128 free (p_begin); 129 return; 130 } 131 chain = &((struct header *) ((char *) *chain - HEADER_SIZE))->next; 132 } 133 } 134 /* At this point, we know it was not a mallocsa() result. */ 135 } 136} 137#endif 138