1 /* xalloc.h -- malloc with out-of-memory checking
2
3 Copyright (C) 1990-2000, 2003-2004, 2006-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 #ifndef XALLOC_H_
19 # define XALLOC_H_
20
21 # include <stddef.h>
22
23 #include "intprops.h"
24
25
26 # ifdef __cplusplus
27 extern "C" {
28 # endif
29
30
31 # ifndef __attribute__
32 # if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8)
33 # define __attribute__(arg)
34 # endif
35 # endif
36
37 # ifndef ATTRIBUTE_NORETURN
38 # define ATTRIBUTE_NORETURN __attribute__ ((__noreturn__))
39 # endif
40
41 # ifndef ATTRIBUTE_MALLOC
42 # if __GNUC__ >= 3
43 # define ATTRIBUTE_MALLOC __attribute__ ((__malloc__))
44 # else
45 # define ATTRIBUTE_MALLOC
46 # endif
47 # endif
48
49 /* This function is always triggered when memory is exhausted.
50 It must be defined by the application, either explicitly
51 or by using gnulib's xalloc-die module. This is the
52 function to call when one wants the program to die because of a
53 memory allocation failure. */
54 extern void xalloc_die (void) ATTRIBUTE_NORETURN;
55
56 void *xmalloc (size_t s) ATTRIBUTE_MALLOC;
57 void *xzalloc (size_t s) ATTRIBUTE_MALLOC;
58 void *xcalloc (size_t n, size_t s) ATTRIBUTE_MALLOC;
59 void *xrealloc (void *p, size_t s);
60 void *x2realloc (void *p, size_t *pn);
61 void *xpalloc (void *pa, idx_t *nitems, idx_t nitems_incr_min,
62 ptrdiff_t nitems_max, idx_t item_size);
63 void *xmemdup (void const *p, size_t s) ATTRIBUTE_MALLOC;
64 char *xstrdup (char const *str) ATTRIBUTE_MALLOC;
65
66 /* Return 1 if an array of N objects, each of size S, cannot exist due
67 to size arithmetic overflow. S must be positive and N must be
68 nonnegative. This is a macro, not an inline function, so that it
69 works correctly even when SIZE_MAX < N.
70
71 By gnulib convention, SIZE_MAX represents overflow in size
72 calculations, so the conservative dividend to use here is
73 SIZE_MAX - 1, since SIZE_MAX might represent an overflowed value.
74 However, malloc (SIZE_MAX) fails on all known hosts where
75 sizeof (ptrdiff_t) <= sizeof (size_t), so do not bother to test for
76 exactly-SIZE_MAX allocations on such hosts; this avoids a test and
77 branch when S is known to be 1. */
78 # define xalloc_oversized(n, s) \
79 ((size_t) (sizeof (ptrdiff_t) <= sizeof (size_t) ? -1 : -2) / (s) < (n))
80
81
82 /* In the following macros, T must be an elementary or structure/union or
83 typedef'ed type, or a pointer to such a type. To apply one of the
84 following macros to a function pointer or array type, you need to typedef
85 it first and use the typedef name. */
86
87 /* Allocate an object of type T dynamically, with error checking. */
88 /* extern t *XMALLOC (typename t); */
89 # define XMALLOC(t) ((t *) xmalloc (sizeof (t)))
90
91 /* Allocate memory for N elements of type T, with error checking. */
92 /* extern t *XNMALLOC (size_t n, typename t); */
93 # define XNMALLOC(n, t) \
94 ((t *) (sizeof (t) == 1 ? xmalloc (n) : xnmalloc (n, sizeof (t))))
95
96 /* Allocate an object of type T dynamically, with error checking,
97 and zero it. */
98 /* extern t *XZALLOC (typename t); */
99 # define XZALLOC(t) ((t *) xzalloc (sizeof (t)))
100
101 /* Allocate memory for N elements of type T, with error checking,
102 and zero it. */
103 /* extern t *XCALLOC (size_t n, typename t); */
104 # define XCALLOC(n, t) \
105 ((t *) (sizeof (t) == 1 ? xzalloc (n) : xcalloc (n, sizeof (t))))
106
107 /*
108 * Gawk uses this file only to keep dfa.c happy.
109 * We're therefore safe in manually defining HAVE_INLINE to
110 * make the !@#$%^&*() thing just work.
111 */
112 #ifdef GAWK
113 #define HAVE_INLINE 1 /* so there. nyah, nyah, nyah. */
114 #endif
115
116 # if HAVE_INLINE
117 # define static_inline static inline
118 # else
119 void *xnmalloc (size_t n, size_t s) ATTRIBUTE_MALLOC;
120 void *xnrealloc (void *p, size_t n, size_t s);
121 void *x2nrealloc (void *p, size_t *pn, size_t s);
122 char *xcharalloc (size_t n) ATTRIBUTE_MALLOC;
123 # endif
124
125 # ifdef static_inline
126
127 /* Allocate an array of N objects, each with S bytes of memory,
128 dynamically, with error checking. S must be nonzero. */
129
130 static_inline void *xnmalloc (size_t n, size_t s) ATTRIBUTE_MALLOC;
131 static_inline void *
132 xnmalloc (size_t n, size_t s)
133 {
134 if (xalloc_oversized (n, s))
135 xalloc_die ();
136 return xmalloc (n * s);
137 }
138
139 #ifdef GAWK
140 #include <errno.h>
141 extern void r_fatal(const char *msg, ...) ATTRIBUTE_NORETURN ;
142
143 void *
144 xmalloc(size_t bytes)
145 {
146 void *p;
147 if (bytes == 0)
148 bytes = 1; /* avoid dfa.c mishegos */
149 if ((p = malloc(bytes)) == NULL)
150 xalloc_die ();
151 return p;
152 }
153
154 /* Allocate an array of N objects, each with S bytes of memory,
155 dynamically, with error checking. S must be nonzero.
156 Clear the contents afterwards. */
157
158 void *
159 xcalloc(size_t nmemb, size_t size)
160 {
161 void *p;
162
163 if (nmemb == 0 || size == 0)
164 nmemb = size = 1; /* avoid dfa.c mishegos */
165 if ((p = calloc(nmemb, size)) == NULL)
166 xalloc_die ();
167 return p;
168 }
169
170 /* Reallocate a pointer to a new size, with error checking. */
171
172 void *
173 xrealloc(void *p, size_t size)
174 {
175 void *new_p = realloc(p, size);
176 if (new_p == 0)
177 xalloc_die ();
178
179 return new_p;
180 }
181
182 /* xalloc_die --- fatal error message when malloc fails, needed by dfa.c */
183
184 void
185 xalloc_die (void)
186 {
187 r_fatal(_("xalloc: malloc failed: %s"), strerror(errno));
188 }
189
190 /* Clone an object P of size S, with error checking. There's no need
191 for xnmemdup (P, N, S), since xmemdup (P, N * S) works without any
192 need for an arithmetic overflow check. */
193
194 void *
195 xmemdup (void const *p, size_t s)
196 {
197 return memcpy (xmalloc (s), p, s);
198 }
199
200 /* xstrdup --- strdup and die if fails */
201 char *xstrdup(const char *s)
202 {
203 char *p;
204 int l;
205
206 if (s == NULL)
207 r_fatal(_("xstrdup: null parameter"));
208
209 l = strlen(s);
210 p = xmemdup(s, l + 1);
211 p[l] = '\0';
212
213 return p;
214 }
215 #endif
216
217 /* Change the size of an allocated block of memory P to an array of N
218 objects each of S bytes, with error checking. S must be nonzero. */
219
220 static_inline void *
221 xnrealloc (void *p, size_t n, size_t s)
222 {
223 if (xalloc_oversized (n, s))
224 xalloc_die ();
225 return xrealloc (p, n * s);
226 }
227
228 /* If P is null, allocate a block of at least *PN such objects;
229 otherwise, reallocate P so that it contains more than *PN objects
230 each of S bytes. S must be nonzero. Set *PN to the new number of
231 objects, and return the pointer to the new block. *PN is never set
232 to zero, and the returned pointer is never null.
233
234 Repeated reallocations are guaranteed to make progress, either by
235 allocating an initial block with a nonzero size, or by allocating a
236 larger block.
237
238 In the following implementation, nonzero sizes are increased by a
239 factor of approximately 1.5 so that repeated reallocations have
240 O(N) overall cost rather than O(N**2) cost, but the
241 specification for this function does not guarantee that rate.
242
243 Here is an example of use:
244
245 int *p = NULL;
246 size_t used = 0;
247 size_t allocated = 0;
248
249 void
250 append_int (int value)
251 {
252 if (used == allocated)
253 p = x2nrealloc (p, &allocated, sizeof *p);
254 p[used++] = value;
255 }
256
257 This causes x2nrealloc to allocate a block of some nonzero size the
258 first time it is called.
259
260 To have finer-grained control over the initial size, set *PN to a
261 nonzero value before calling this function with P == NULL. For
262 example:
263
264 int *p = NULL;
265 size_t used = 0;
266 size_t allocated = 0;
267 size_t allocated1 = 1000;
268
269 void
270 append_int (int value)
271 {
272 if (used == allocated)
273 {
274 p = x2nrealloc (p, &allocated1, sizeof *p);
275 allocated = allocated1;
276 }
277 p[used++] = value;
278 }
279
280 */
281
282 static_inline void *
283 x2nrealloc (void *p, size_t *pn, size_t s)
284 {
285 size_t n = *pn;
286
287 if (! p)
288 {
289 if (! n)
290 {
291 /* The approximate size to use for initial small allocation
292 requests, when the invoking code specifies an old size of
293 zero. 64 bytes is the largest "small" request for the
294 GNU C library malloc. */
295 enum { DEFAULT_MXFAST = 64 * sizeof (size_t) / 4 };
296
297 n = DEFAULT_MXFAST / s;
298 n += !n;
299 }
300 }
301 else
302 {
303 /* Set N = ceil (1.5 * N) so that progress is made if N == 1.
304 Check for overflow, so that N * S stays in size_t range.
305 The check is slightly conservative, but an exact check isn't
306 worth the trouble. */
307 if ((size_t) -1 / 3 * 2 / s <= n)
308 xalloc_die ();
309 n += n / 2 + 1;
310 }
311
312 *pn = n;
313 return xrealloc (p, n * s);
314 }
315
316 /* Return a pointer to a new buffer of N bytes. This is like xmalloc,
317 except it returns char *. */
318
319 static_inline char *xcharalloc (size_t n) ATTRIBUTE_MALLOC;
320 static_inline char *
321 xcharalloc (size_t n)
322 {
323 return XNMALLOC (n, char);
324 }
325
326 /* Allocate S bytes of zeroed memory dynamically, with error checking.
327 There's no need for xnzalloc (N, S), since it would be equivalent
328 to xcalloc (N, S). */
329
330 inline void *
331 xzalloc (size_t s)
332 {
333 return xcalloc(1, s);
334 }
335
336 # endif
337
338 # ifdef __cplusplus
339 }
340
341 /* C++ does not allow conversions from void * to other pointer types
342 without a cast. Use templates to work around the problem when
343 possible. */
344
345 template <typename T> inline T *
346 xrealloc (T *p, size_t s)
347 {
348 return (T *) xrealloc ((void *) p, s);
349 }
350
351 template <typename T> inline T *
352 xnrealloc (T *p, size_t n, size_t s)
353 {
354 return (T *) xnrealloc ((void *) p, n, s);
355 }
356
357 template <typename T> inline T *
358 x2realloc (T *p, size_t *pn)
359 {
360 return (T *) x2realloc ((void *) p, pn);
361 }
362
363 template <typename T> inline T *
364 x2nrealloc (T *p, size_t *pn, size_t s)
365 {
366 return (T *) x2nrealloc ((void *) p, pn, s);
367 }
368
369 template <typename T> inline T *
370 xmemdup (T const *p, size_t s)
371 {
372 return (T *) xmemdup ((void const *) p, s);
373 }
374
375 # endif
376
377 /* Grow PA, which points to an array of *NITEMS items, and return the
378 location of the reallocated array, updating *NITEMS to reflect its
379 new size. The new array will contain at least NITEMS_INCR_MIN more
380 items, but will not contain more than NITEMS_MAX items total.
381 ITEM_SIZE is the size of each item, in bytes.
382
383 ITEM_SIZE and NITEMS_INCR_MIN must be positive. *NITEMS must be
384 nonnegative. If NITEMS_MAX is -1, it is treated as if it were
385 infinity.
386
387 If PA is null, then allocate a new array instead of reallocating
388 the old one.
389
390 Thus, to grow an array A without saving its old contents, do
391 { free (A); A = xpalloc (NULL, &AITEMS, ...); }. */
392
393 #define MIN(x, y) ((x) < (y) ? (x) : (y))
394
395 void *
396 xpalloc (void *pa, idx_t *nitems, idx_t nitems_incr_min,
397 ptrdiff_t nitems_max, idx_t item_size)
398 {
399 idx_t n0 = *nitems;
400
401 /* The approximate size to use for initial small allocation
402 requests. This is the largest "small" request for the GNU C
403 library malloc. */
404 enum { DEFAULT_MXFAST = 64 * sizeof (size_t) / 4 };
405
406 /* If the array is tiny, grow it to about (but no greater than)
407 DEFAULT_MXFAST bytes. Otherwise, grow it by about 50%.
408 Adjust the growth according to three constraints: NITEMS_INCR_MIN,
409 NITEMS_MAX, and what the C language can represent safely. */
410
411 idx_t n, nbytes;
412 if (INT_ADD_WRAPV (n0, n0 >> 1, &n))
413 n = IDX_MAX;
414 if (0 <= nitems_max && nitems_max < n)
415 n = nitems_max;
416
417 idx_t adjusted_nbytes
418 = ((INT_MULTIPLY_WRAPV (n, item_size, &nbytes) || SIZE_MAX < nbytes)
419 ? MIN (IDX_MAX, SIZE_MAX)
420 : nbytes < DEFAULT_MXFAST ? DEFAULT_MXFAST : 0);
421 if (adjusted_nbytes)
422 {
423 n = adjusted_nbytes / item_size;
424 nbytes = adjusted_nbytes - adjusted_nbytes % item_size;
425 }
426
427 if (! pa)
428 *nitems = 0;
429 if (n - n0 < nitems_incr_min
430 && (INT_ADD_WRAPV (n0, nitems_incr_min, &n)
431 || (0 <= nitems_max && nitems_max < n)
432 || INT_MULTIPLY_WRAPV (n, item_size, &nbytes)))
433 xalloc_die ();
434 pa = xrealloc (pa, nbytes);
435 *nitems = n;
436 return pa;
437 }
438
439 /* Clone an object P of size S, with error checking. Append
440 a terminating NUL byte. */
441
442 char *
443 ximemdup0 (void const *p, idx_t s)
444 {
445 char *result = malloc(s + 1);
446 result[s] = 0;
447 return memcpy (result, p, s);
448 }
449
450
451 #endif /* !XALLOC_H_ */