summaryrefslogtreecommitdiffstats
path: root/gl/malloca.c
diff options
context:
space:
mode:
Diffstat (limited to 'gl/malloca.c')
-rw-r--r--gl/malloca.c165
1 files changed, 64 insertions, 101 deletions
diff --git a/gl/malloca.c b/gl/malloca.c
index 311be56..f055b1e 100644
--- a/gl/malloca.c
+++ b/gl/malloca.c
@@ -1,19 +1,19 @@
1/* Safe automatic memory allocation. 1/* Safe automatic memory allocation.
2 Copyright (C) 2003, 2006-2007, 2009-2013 Free Software Foundation, Inc. 2 Copyright (C) 2003, 2006-2007, 2009-2023 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2003. 3 Written by Bruno Haible <bruno@clisp.org>, 2003, 2018.
4 4
5 This program is free software; you can redistribute it and/or modify 5 This file is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by 6 it under the terms of the GNU Lesser General Public License as
7 the Free Software Foundation; either version 3, or (at your option) 7 published by the Free Software Foundation; either version 2.1 of the
8 any later version. 8 License, or (at your option) any later version.
9 9
10 This program is distributed in the hope that it will be useful, 10 This file is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of 11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details. 13 GNU Lesser General Public License for more details.
14 14
15 You should have received a copy of the GNU General Public License 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/>. */ 16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17 17
18#define _GL_USE_STDLIB_ALLOC 1 18#define _GL_USE_STDLIB_ALLOC 1
19#include <config.h> 19#include <config.h>
@@ -21,82 +21,56 @@
21/* Specification. */ 21/* Specification. */
22#include "malloca.h" 22#include "malloca.h"
23 23
24#include <stdint.h> 24#include <stdckdint.h>
25 25
26#include "verify.h" 26#include "idx.h"
27 27
28/* The speed critical point in this file is freea() applied to an alloca() 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 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 30 mmalloca() and freea() in the other case are not critical, because they
31 are only invoked for big memory sizes. */ 31 are only invoked for big memory sizes.
32 32 Here we use a bit in the address as an indicator, an idea by Ondřej Bílka.
33#if HAVE_ALLOCA 33 malloca() can return three types of pointers:
34 34 - Pointers ≡ 0 mod 2*sa_alignment_max come from stack allocation.
35/* Store the mmalloca() results in a hash table. This is needed to reliably 35 - Pointers ≡ sa_alignment_max mod 2*sa_alignment_max come from heap
36 distinguish a mmalloca() result and an alloca() result. 36 allocation.
37 37 - NULL comes from a failed heap allocation. */
38 Although it is possible that the same pointer is returned by alloca() and 38
39 by mmalloca() at different times in the same application, it does not lead 39/* Type for holding very small pointer differences. */
40 to a bug in freea(), because: 40typedef unsigned char small_t;
41 - Before a pointer returned by alloca() can point into malloc()ed memory, 41/* Verify that it is wide enough. */
42 the function must return, and once this has happened the programmer must 42static_assert (2 * sa_alignment_max - 1 <= (small_t) -1);
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. */
52struct 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)
56union header {
57 void *next;
58 struct {
59 char room[HEADER_SIZE - MAGIC_SIZE];
60 int word;
61 } magic;
62};
63verify (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
69static void * mmalloca_results[HASH_TABLE_SIZE];
70
71#endif
72 43
73void * 44void *
74mmalloca (size_t n) 45mmalloca (size_t n)
75{ 46{
76#if HAVE_ALLOCA 47#if HAVE_ALLOCA
77 /* Allocate one more word, that serves as an indicator for malloc()ed 48 /* Allocate one more word, used to determine the address to pass to freea(),
78 memory, so that freea() of an alloca() result is fast. */ 49 and room for the alignment ≡ sa_alignment_max mod 2*sa_alignment_max. */
79 size_t nplus = n + HEADER_SIZE; 50 uintptr_t alignment2_mask = 2 * sa_alignment_max - 1;
80 51 int plus = sizeof (small_t) + alignment2_mask;
81 if (nplus >= n) 52 idx_t nplus;
53 if (!ckd_add (&nplus, n, plus) && !xalloc_oversized (nplus, 1))
82 { 54 {
83 void *p = malloc (nplus); 55 char *mem = (char *) malloc (nplus);
84 56
85 if (p != NULL) 57 if (mem != NULL)
86 { 58 {
87 size_t slot; 59 uintptr_t umem = (uintptr_t)mem, umemplus;
88 union header *h = p; 60 /* The ckd_add avoids signed integer overflow on
89 61 theoretical platforms where UINTPTR_MAX <= INT_MAX. */
90 p = h + 1; 62 ckd_add (&umemplus, umem, sizeof (small_t) + sa_alignment_max - 1);
91 63 idx_t offset = ((umemplus & ~alignment2_mask)
92 /* Put a magic number into the indicator word. */ 64 + sa_alignment_max - umem);
93 h->magic.word = MAGIC_NUMBER; 65 void *vp = mem + offset;
94 66 small_t *p = vp;
95 /* Enter p into the hash table. */ 67 /* Here p >= mem + sizeof (small_t),
96 slot = (uintptr_t) p % HASH_TABLE_SIZE; 68 and p <= mem + sizeof (small_t) + 2 * sa_alignment_max - 1
97 h->next = mmalloca_results[slot]; 69 hence p + n <= mem + nplus.
98 mmalloca_results[slot] = p; 70 So, the memory range [p, p+n) lies in the allocated memory range
99 71 [mem, mem + nplus). */
72 p[-1] = offset;
73 /* p ≡ sa_alignment_max mod 2*sa_alignment_max. */
100 return p; 74 return p;
101 } 75 }
102 } 76 }
@@ -115,35 +89,24 @@ mmalloca (size_t n)
115void 89void
116freea (void *p) 90freea (void *p)
117{ 91{
118 /* mmalloca() may have returned NULL. */ 92 /* Check argument. */
119 if (p != NULL) 93 if ((uintptr_t) p & (sa_alignment_max - 1))
120 { 94 {
121 /* Attempt to quickly distinguish the mmalloca() result - which has 95 /* p was not the result of a malloca() call. Invalid argument. */
122 a magic indicator word - and the alloca() result - which has an 96 abort ();
123 uninitialized indicator word. It is for this test that sa_increment 97 }
124 additional bytes are allocated in the alloca() case. */ 98 /* Determine whether p was a non-NULL pointer returned by mmalloca(). */
125 if (((int *) p)[-1] == MAGIC_NUMBER) 99 if ((uintptr_t) p & sa_alignment_max)
126 { 100 {
127 /* Looks like a mmalloca() result. To see whether it really is one, 101 void *mem = (char *) p - ((small_t *) p)[-1];
128 perform a lookup in the hash table. */ 102 free (mem);
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 } 103 }
148} 104}
149#endif 105#endif
106
107/*
108 * Hey Emacs!
109 * Local Variables:
110 * coding: utf-8
111 * End:
112 */