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