lib/xmalloc.c

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