Line data Source code
1 : /* Safe automatic memory allocation.
2 : Copyright (C) 2003, 2006-2007, 2009-2016 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 0 : 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 500000 : 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 750000 : 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
|