1 /* xmalloc.c -- malloc with out of memory checking
2
3 Copyright (C) 1990-2000, 2002-2006, 2008-2021 Free Software Foundation, Inc.
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 of the License, or
8 (at your option) 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 <https://www.gnu.org/licenses/>. */
17
18 #include <config.h>
19
20 #define XALLOC_INLINE _GL_EXTERN_INLINE
21
22 #include "xalloc.h"
23
24 #include "ialloc.h"
25 #include "intprops.h"
26 #include "minmax.h"
27
28 #include <stdlib.h>
29 #include <string.h>
30
31 static void * _GL_ATTRIBUTE_PURE
32 nonnull (void *p)
33 {
34 if (!p)
35 xalloc_die ();
36 return p;
37 }
38
39 /* Allocate S bytes of memory dynamically, with error checking. */
40
41 void *
42 xmalloc (size_t s)
43 {
44 return nonnull (malloc (s));
45 }
46
47 void *
48 ximalloc (idx_t s)
49 {
50 return nonnull (imalloc (s));
51 }
52
53 char *
54 xcharalloc (size_t n)
55 {
56 return XNMALLOC (n, char);
57 }
58
59 /* Change the size of an allocated block of memory P to S bytes,
60 with error checking. */
61
62 void *
63 xrealloc (void *p, size_t s)
64 {
65 void *r = realloc (p, s);
66 if (!r && (!p || s))
67 xalloc_die ();
68 return r;
69 }
70
71 void *
72 xirealloc (void *p, idx_t s)
73 {
74 return nonnull (irealloc (p, s));
75 }
76
77 /* Change the size of an allocated block of memory P to an array of N
78 objects each of S bytes, with error checking. */
79
80 void *
81 xreallocarray (void *p, size_t n, size_t s)
82 {
83 void *r = reallocarray (p, n, s);
84 if (!r && (!p || (n && s)))
85 xalloc_die ();
86 return r;
87 }
88
89 void *
90 xireallocarray (void *p, idx_t n, idx_t s)
91 {
92 return nonnull (ireallocarray (p, n, s));
93 }
94
95 /* Allocate an array of N objects, each with S bytes of memory,
96 dynamically, with error checking. S must be nonzero. */
97
98 void *
99 xnmalloc (size_t n, size_t s)
100 {
101 return xreallocarray (NULL, n, s);
102 }
103
104 /* If P is null, allocate a block of at least *PS bytes; otherwise,
105 reallocate P so that it contains more than *PS bytes. *PS must be
106 nonzero unless P is null. Set *PS to the new block's size, and
107 return the pointer to the new block. *PS is never set to zero, and
108 the returned pointer is never null. */
109
110 void *
111 x2realloc (void *p, size_t *ps)
112 {
113 return x2nrealloc (p, ps, 1);
114 }
115
116 /* If P is null, allocate a block of at least *PN such objects;
117 otherwise, reallocate P so that it contains more than *PN objects
118 each of S bytes. S must be nonzero. Set *PN to the new number of
119 objects, and return the pointer to the new block. *PN is never set
120 to zero, and the returned pointer is never null.
121
122 Repeated reallocations are guaranteed to make progress, either by
123 allocating an initial block with a nonzero size, or by allocating a
124 larger block.
125
126 In the following implementation, nonzero sizes are increased by a
127 factor of approximately 1.5 so that repeated reallocations have
128 O(N) overall cost rather than O(N**2) cost, but the
129 specification for this function does not guarantee that rate.
130
131 Here is an example of use:
132
133 int *p = NULL;
134 size_t used = 0;
135 size_t allocated = 0;
136
137 void
138 append_int (int value)
139 {
140 if (used == allocated)
141 p = x2nrealloc (p, &allocated, sizeof *p);
142 p[used++] = value;
143 }
144
145 This causes x2nrealloc to allocate a block of some nonzero size the
146 first time it is called.
147
148 To have finer-grained control over the initial size, set *PN to a
149 nonzero value before calling this function with P == NULL. For
150 example:
151
152 int *p = NULL;
153 size_t used = 0;
154 size_t allocated = 0;
155 size_t allocated1 = 1000;
156
157 void
158 append_int (int value)
159 {
160 if (used == allocated)
161 {
162 p = x2nrealloc (p, &allocated1, sizeof *p);
163 allocated = allocated1;
164 }
165 p[used++] = value;
166 }
167
168 */
169
170 void *
171 x2nrealloc (void *p, size_t *pn, size_t s)
172 {
173 size_t n = *pn;
174
175 if (! p)
176 {
177 if (! n)
178 {
179 /* The approximate size to use for initial small allocation
180 requests, when the invoking code specifies an old size of
181 zero. This is the largest "small" request for the GNU C
182 library malloc. */
183 enum { DEFAULT_MXFAST = 64 * sizeof (size_t) / 4 };
184
185 n = DEFAULT_MXFAST / s;
186 n += !n;
187 }
188 }
189 else
190 {
191 /* Set N = floor (1.5 * N) + 1 to make progress even if N == 0. */
192 if (INT_ADD_WRAPV (n, (n >> 1) + 1, &n))
193 xalloc_die ();
194 }
195
196 p = xreallocarray (p, n, s);
197 *pn = n;
198 return p;
199 }
200
201 /* Grow PA, which points to an array of *PN items, and return the
202 location of the reallocated array, updating *PN to reflect its
203 new size. The new array will contain at least N_INCR_MIN more
204 items, but will not contain more than N_MAX items total.
205 S is the size of each item, in bytes.
206
207 S and N_INCR_MIN must be positive. *PN must be
208 nonnegative. If N_MAX is -1, it is treated as if it were
209 infinity.
210
211 If PA is null, then allocate a new array instead of reallocating
212 the old one.
213
214 Thus, to grow an array A without saving its old contents, do
215 { free (A); A = xpalloc (NULL, &AITEMS, ...); }. */
216
217 void *
218 xpalloc (void *pa, idx_t *pn, idx_t n_incr_min, ptrdiff_t n_max, idx_t s)
219 {
220 idx_t n0 = *pn;
221
222 /* The approximate size to use for initial small allocation
223 requests. This is the largest "small" request for the GNU C
224 library malloc. */
225 enum { DEFAULT_MXFAST = 64 * sizeof (size_t) / 4 };
226
227 /* If the array is tiny, grow it to about (but no greater than)
228 DEFAULT_MXFAST bytes. Otherwise, grow it by about 50%.
229 Adjust the growth according to three constraints: N_INCR_MIN,
230 N_MAX, and what the C language can represent safely. */
231
232 idx_t n;
233 if (INT_ADD_WRAPV (n0, n0 >> 1, &n))
234 n = IDX_MAX;
235 if (0 <= n_max && n_max < n)
236 n = n_max;
237
238 /* NBYTES is of a type suitable for holding the count of bytes in an object.
239 This is typically idx_t, but it should be size_t on (theoretical?)
240 platforms where SIZE_MAX < IDX_MAX so xpalloc does not pass
241 values greater than SIZE_MAX to xrealloc. */
242 #if IDX_MAX <= SIZE_MAX
243 idx_t nbytes;
244 #else
245 size_t nbytes;
246 #endif
247 idx_t adjusted_nbytes
248 = (INT_MULTIPLY_WRAPV (n, s, &nbytes)
249 ? MIN (IDX_MAX, SIZE_MAX)
250 : nbytes < DEFAULT_MXFAST ? DEFAULT_MXFAST : 0);
251 if (adjusted_nbytes)
252 {
253 n = adjusted_nbytes / s;
254 nbytes = adjusted_nbytes - adjusted_nbytes % s;
255 }
256
257 if (! pa)
258 *pn = 0;
259 if (n - n0 < n_incr_min
260 && (INT_ADD_WRAPV (n0, n_incr_min, &n)
261 || (0 <= n_max && n_max < n)
262 || INT_MULTIPLY_WRAPV (n, s, &nbytes)))
263 xalloc_die ();
264 pa = xrealloc (pa, nbytes);
265 *pn = n;
266 return pa;
267 }
268
269 /* Allocate S bytes of zeroed memory dynamically, with error checking.
270 There's no need for xnzalloc (N, S), since it would be equivalent
271 to xcalloc (N, S). */
272
273 void *
274 xzalloc (size_t s)
275 {
276 return xcalloc (s, 1);
277 }
278
279 void *
280 xizalloc (idx_t s)
281 {
282 return xicalloc (s, 1);
283 }
284
285 /* Allocate zeroed memory for N elements of S bytes, with error
286 checking. S must be nonzero. */
287
288 void *
289 xcalloc (size_t n, size_t s)
290 {
291 return nonnull (calloc (n, s));
292 }
293
294 void *
295 xicalloc (idx_t n, idx_t s)
296 {
297 return nonnull (icalloc (n, s));
298 }
299
300 /* Clone an object P of size S, with error checking. There's no need
301 for xnmemdup (P, N, S), since xmemdup (P, N * S) works without any
302 need for an arithmetic overflow check. */
303
304 void *
305 xmemdup (void const *p, size_t s)
306 {
307 return memcpy (xmalloc (s), p, s);
308 }
309
310 void *
311 ximemdup (void const *p, idx_t s)
312 {
313 return memcpy (ximalloc (s), p, s);
314 }
315
316 /* Clone an object P of size S, with error checking. Append
317 a terminating NUL byte. */
318
319 char *
320 ximemdup0 (void const *p, idx_t s)
321 {
322 char *result = ximalloc (s + 1);
323 result[s] = 0;
324 return memcpy (result, p, s);
325 }
326
327 /* Clone STRING. */
328
329 char *
330 xstrdup (char const *string)
331 {
332 return xmemdup (string, strlen (string) + 1);
333 }