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