| 1 | /* Safe automatic memory allocation. |
| 2 | Copyright (C) 2003, 2006-2007, 2009-2014 Free Software Foundation, Inc. |
| 3 | Written by Bruno Haible <bruno@clisp.org>, 2003. |
| 4 | |
| 5 | This program is free software; you can redistribute it and/or modify |
| 6 | it under the terms of the GNU Lesser General Public License as published by |
| 7 | the Free Software Foundation; either version 2, or (at your option) |
| 8 | any later version. |
| 9 | |
| 10 | This program is distributed in the hope that it will be useful, |
| 11 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 13 | GNU Lesser General Public License for more details. |
| 14 | |
| 15 | You should have received a copy of the GNU Lesser General Public License |
| 16 | along with this program; if not, see <http://www.gnu.org/licenses/>. */ |
| 17 | |
| 18 | #define _GL_USE_STDLIB_ALLOC 1 |
| 19 | #include <config.h> |
| 20 | |
| 21 | /* Specification. */ |
| 22 | #include "malloca.h" |
| 23 | |
| 24 | #include <stdint.h> |
| 25 | |
| 26 | #include "verify.h" |
| 27 | |
| 28 | /* The speed critical point in this file is freea() applied to an alloca() |
| 29 | result: it must be fast, to match the speed of alloca(). The speed of |
| 30 | mmalloca() and freea() in the other case are not critical, because they |
| 31 | are only invoked for big memory sizes. */ |
| 32 | |
| 33 | #if HAVE_ALLOCA |
| 34 | |
| 35 | /* Store the mmalloca() results in a hash table. This is needed to reliably |
| 36 | distinguish a mmalloca() result and an alloca() result. |
| 37 | |
| 38 | Although it is possible that the same pointer is returned by alloca() and |
| 39 | by mmalloca() at different times in the same application, it does not lead |
| 40 | to a bug in freea(), because: |
| 41 | - Before a pointer returned by alloca() can point into malloc()ed memory, |
| 42 | the function must return, and once this has happened the programmer must |
| 43 | not call freea() on it anyway. |
| 44 | - Before a pointer returned by mmalloca() can point into the stack, it |
| 45 | must be freed. The only function that can free it is freea(), and |
| 46 | when freea() frees it, it also removes it from the hash table. */ |
| 47 | |
| 48 | #define MAGIC_NUMBER 0x1415fb4a |
| 49 | #define MAGIC_SIZE sizeof (int) |
| 50 | /* This is how the header info would look like without any alignment |
| 51 | considerations. */ |
| 52 | struct preliminary_header { void *next; int magic; }; |
| 53 | /* But the header's size must be a multiple of sa_alignment_max. */ |
| 54 | #define HEADER_SIZE \ |
| 55 | (((sizeof (struct preliminary_header) + sa_alignment_max - 1) / sa_alignment_max) * sa_alignment_max) |
| 56 | union header { |
| 57 | void *next; |
| 58 | struct { |
| 59 | char room[HEADER_SIZE - MAGIC_SIZE]; |
| 60 | int word; |
| 61 | } magic; |
| 62 | }; |
| 63 | verify (HEADER_SIZE == sizeof (union header)); |
| 64 | /* We make the hash table quite big, so that during lookups the probability |
| 65 | of empty hash buckets is quite high. There is no need to make the hash |
| 66 | table resizable, because when the hash table gets filled so much that the |
| 67 | lookup becomes slow, it means that the application has memory leaks. */ |
| 68 | #define HASH_TABLE_SIZE 257 |
| 69 | static void * mmalloca_results[HASH_TABLE_SIZE]; |
| 70 | |
| 71 | #endif |
| 72 | |
| 73 | void * |
| 74 | mmalloca (size_t n) |
| 75 | { |
| 76 | #if HAVE_ALLOCA |
| 77 | /* Allocate one more word, that serves as an indicator for malloc()ed |
| 78 | memory, so that freea() of an alloca() result is fast. */ |
| 79 | size_t nplus = n + HEADER_SIZE; |
| 80 | |
| 81 | if (nplus >= n) |
| 82 | { |
| 83 | void *p = malloc (nplus); |
| 84 | |
| 85 | if (p != NULL) |
| 86 | { |
| 87 | size_t slot; |
| 88 | union header *h = p; |
| 89 | |
| 90 | p = h + 1; |
| 91 | |
| 92 | /* Put a magic number into the indicator word. */ |
| 93 | h->magic.word = MAGIC_NUMBER; |
| 94 | |
| 95 | /* Enter p into the hash table. */ |
| 96 | slot = (uintptr_t) p % HASH_TABLE_SIZE; |
| 97 | h->next = mmalloca_results[slot]; |
| 98 | mmalloca_results[slot] = p; |
| 99 | |
| 100 | return p; |
| 101 | } |
| 102 | } |
| 103 | /* Out of memory. */ |
| 104 | return NULL; |
| 105 | #else |
| 106 | # if !MALLOC_0_IS_NONNULL |
| 107 | if (n == 0) |
| 108 | n = 1; |
| 109 | # endif |
| 110 | return malloc (n); |
| 111 | #endif |
| 112 | } |
| 113 | |
| 114 | #if HAVE_ALLOCA |
| 115 | void |
| 116 | freea (void *p) |
| 117 | { |
| 118 | /* mmalloca() may have returned NULL. */ |
| 119 | if (p != NULL) |
| 120 | { |
| 121 | /* Attempt to quickly distinguish the mmalloca() result - which has |
| 122 | a magic indicator word - and the alloca() result - which has an |
| 123 | uninitialized indicator word. It is for this test that sa_increment |
| 124 | additional bytes are allocated in the alloca() case. */ |
| 125 | if (((int *) p)[-1] == MAGIC_NUMBER) |
| 126 | { |
| 127 | /* Looks like a mmalloca() result. To see whether it really is one, |
| 128 | perform a lookup in the hash table. */ |
| 129 | size_t slot = (uintptr_t) p % HASH_TABLE_SIZE; |
| 130 | void **chain = &mmalloca_results[slot]; |
| 131 | for (; *chain != NULL;) |
| 132 | { |
| 133 | union header *h = p; |
| 134 | if (*chain == p) |
| 135 | { |
| 136 | /* Found it. Remove it from the hash table and free it. */ |
| 137 | union header *p_begin = h - 1; |
| 138 | *chain = p_begin->next; |
| 139 | free (p_begin); |
| 140 | return; |
| 141 | } |
| 142 | h = *chain; |
| 143 | chain = &h[-1].next; |
| 144 | } |
| 145 | } |
| 146 | /* At this point, we know it was not a mmalloca() result. */ |
| 147 | } |
| 148 | } |
| 149 | #endif |