Branch data Line data Source code
1 : : /* Safe automatic memory allocation.
2 : : Copyright (C) 2003, 2006-2007, 2009-2013 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 General Public License as published by
7 : : the Free Software Foundation; either version 3, 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 General Public License for more details.
14 : :
15 : : You should have received a copy of the GNU 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 : 250000 : 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 : 250000 : size_t nplus = n + HEADER_SIZE;
80 : :
81 [ + - ]: 250000 : if (nplus >= n)
82 : : {
83 : 250000 : void *p = malloc (nplus);
84 : :
85 [ + - ]: 250000 : if (p != NULL)
86 : : {
87 : : size_t slot;
88 : 250000 : union header *h = p;
89 : :
90 : 250000 : p = h + 1;
91 : :
92 : : /* Put a magic number into the indicator word. */
93 : 250000 : h->magic.word = MAGIC_NUMBER;
94 : :
95 : : /* Enter p into the hash table. */
96 : 250000 : slot = (uintptr_t) p % HASH_TABLE_SIZE;
97 : 250000 : h->next = mmalloca_results[slot];
98 : 250000 : mmalloca_results[slot] = p;
99 : :
100 : 250000 : return p;
101 : : }
102 : : }
103 : : /* Out of memory. */
104 : 250000 : 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 : 500000 : freea (void *p)
117 : : {
118 : : /* mmalloca() may have returned NULL. */
119 [ + - ]: 500000 : 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 [ + + ]: 500000 : 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 : 250000 : size_t slot = (uintptr_t) p % HASH_TABLE_SIZE;
130 : 250000 : void **chain = &mmalloca_results[slot];
131 [ + - ]: 250000 : for (; *chain != NULL;)
132 : : {
133 : 250000 : union header *h = p;
134 [ + - ]: 250000 : if (*chain == p)
135 : : {
136 : : /* Found it. Remove it from the hash table and free it. */
137 : 250000 : union header *p_begin = h - 1;
138 : 250000 : *chain = p_begin->next;
139 : 250000 : free (p_begin);
140 : 500000 : return;
141 : : }
142 : 0 : h = *chain;
143 : 0 : chain = &h[-1].next;
144 : : }
145 : : }
146 : : /* At this point, we know it was not a mmalloca() result. */
147 : : }
148 : : }
149 : : #endif
|
