include/alloc_buffer.h

   1 /* Allocation from a fixed-size buffer.
   2    Copyright (C) 2017-2018 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the License, or (at your option) any later version.
   9
  10    The GNU C Library 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 GNU
  13    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with the GNU C Library; if not, see
  17    <http://www.gnu.org/licenses/>.  */
  18
  19 /* Allocation buffers are used to carve out sub-allocations from a
  20    larger allocation.  Their primary application is in writing NSS
  21    modules, which receive a caller-allocated buffer in which they are
  22    expected to store variable-length results:
  23
  24      void *buffer = ...;
  25      size_t buffer_size = ...;
  26
  27      struct alloc_buffer buf = alloc_buffer_create (buffer, buffer_size);
  28      result->gr_name = alloc_buffer_copy_string (&buf, name);
  29
  30      // Allocate a list of group_count groups and copy strings into it.
  31      char **group_list = alloc_buffer_alloc_array
  32        (&buf, char *, group_count  + 1);
  33      if (group_list == NULL)
  34        return ...; // Request a larger buffer.
  35      for (int i = 0; i < group_count; ++i)
  36        group_list[i] = alloc_buffer_copy_string (&buf, group_list_src[i]);
  37      group_list[group_count] = NULL;
  38      ...
  39
  40      if (alloc_buffer_has_failed (&buf))
  41        return ...; // Request a larger buffer.
  42      result->gr_mem = group_list;
  43      ...
  44
  45    Note that it is not necessary to check the results of individual
  46    allocation operations if the returned pointer is not dereferenced.
  47    Allocation failure is sticky, so one check using
  48    alloc_buffer_has_failed at the end covers all previous failures.
  49
  50    A different use case involves combining multiple heap allocations
  51    into a single, large one.  In the following example, an array of
  52    doubles and an array of ints is allocated:
  53
  54      size_t double_array_size = ...;
  55      size_t int_array_size = ...;
  56
  57      void *heap_ptr;
  58      struct alloc_buffer buf = alloc_buffer_allocate
  59        (double_array_size * sizeof (double) + int_array_size * sizeof (int),
  60         &heap_ptr);
  61      _Static_assert (__alignof__ (double) >= __alignof__ (int),
  62                      "no padding after double array");
  63      double *double_array = alloc_buffer_alloc_array
  64        (&buf, double, double_array_size);
  65      int *int_array = alloc_buffer_alloc_array (&buf, int, int_array_size);
  66      if (alloc_buffer_has_failed (&buf))
  67        return ...; // Report error.
  68      ...
  69      free (heap_ptr);
  70
  71    The advantage over manual coding is that the computation of the
  72    allocation size does not need an overflow check.  In case of an
  73    overflow, one of the subsequent allocations from the buffer will
  74    fail.  The initial size computation is checked for consistency at
  75    run time, too.  */
  76
  77 #ifndef _ALLOC_BUFFER_H
  78 #define _ALLOC_BUFFER_H
  79
  80 #include <inttypes.h>
  81 #include <stdbool.h>
  82 #include <stddef.h>
  83 #include <stdlib.h>
  84 #include <sys/param.h>
  85
  86 /* struct alloc_buffer objects refer to a region of bytes in memory of a
  87    fixed size.  The functions below can be used to allocate single
  88    objects and arrays from this memory region, or write to its end.
  89    On allocation failure (or if an attempt to write beyond the end of
  90    the buffer with one of the copy functions), the buffer enters a
  91    failed state.
  92
  93    struct alloc_buffer objects can be copied.  The backing buffer will
  94    be shared, but the current write position will be independent.
  95
  96    Conceptually, the memory region consists of a current write pointer
  97    and a limit, beyond which the write pointer cannot move.  */
  98 struct alloc_buffer
  99 {
 100   /* uintptr_t is used here to simplify the alignment code, and to
 101      avoid issues undefined subtractions if the buffer covers more
 102      than half of the address space (which would result in differences
 103      which could not be represented as a ptrdiff_t value).  */
 104   uintptr_t __alloc_buffer_current;
 105   uintptr_t __alloc_buffer_end;
 106 };
 107
 108 enum
 109   {
 110     /* The value for the __alloc_buffer_current member which marks the
 111        buffer as invalid (together with a zero-length buffer).  */
 112     __ALLOC_BUFFER_INVALID_POINTER = 0,
 113   };
 114
 115 /* Internal function.  Terminate the process using __libc_fatal.  */
 116 void __libc_alloc_buffer_create_failure (void *start, size_t size);
 117
 118 /* Create a new allocation buffer.  The byte range from START to START
 119    + SIZE - 1 must be valid, and the allocation buffer allocates
 120    objects from that range.  If START is NULL (so that SIZE must be
 121    0), the buffer is marked as failed immediately.  */
 122 static inline struct alloc_buffer
 123 alloc_buffer_create (void *start, size_t size)
 124 {
 125   uintptr_t current = (uintptr_t) start;
 126   uintptr_t end = (uintptr_t) start + size;
 127   if (end < current)
 128     __libc_alloc_buffer_create_failure (start, size);
 129   return (struct alloc_buffer) { current, end };
 130 }
 131
 132 /* Internal function.  See alloc_buffer_allocate below.  */
 133 struct alloc_buffer __libc_alloc_buffer_allocate (size_t size, void **pptr)
 134   __attribute__ ((nonnull (2)));
 135
 136 /* Allocate a buffer of SIZE bytes using malloc.  The returned buffer
 137    is in a failed state if malloc fails.  *PPTR points to the start of
 138    the buffer and can be used to free it later, after the returned
 139    buffer has been freed.  */
 140 static __always_inline __attribute__ ((nonnull (2)))
 141 struct alloc_buffer alloc_buffer_allocate (size_t size, void **pptr)
 142 {
 143   return __libc_alloc_buffer_allocate (size, pptr);
 144 }
 145
 146 /* Mark the buffer as failed.  */
 147 static inline void __attribute__ ((nonnull (1)))
 148 alloc_buffer_mark_failed (struct alloc_buffer *buf)
 149 {
 150   buf->__alloc_buffer_current = __ALLOC_BUFFER_INVALID_POINTER;
 151   buf->__alloc_buffer_end = __ALLOC_BUFFER_INVALID_POINTER;
 152 }
 153
 154 /* Return the remaining number of bytes in the buffer.  */
 155 static __always_inline __attribute__ ((nonnull (1))) size_t
 156 alloc_buffer_size (const struct alloc_buffer *buf)
 157 {
 158   return buf->__alloc_buffer_end - buf->__alloc_buffer_current;
 159 }
 160
 161 /* Return true if the buffer has been marked as failed.  */
 162 static inline bool __attribute__ ((nonnull (1)))
 163 alloc_buffer_has_failed (const struct alloc_buffer *buf)
 164 {
 165   return buf->__alloc_buffer_current == __ALLOC_BUFFER_INVALID_POINTER;
 166 }
 167
 168 /* Add a single byte to the buffer (consuming the space for this
 169    byte).  Mark the buffer as failed if there is not enough room.  */
 170 static inline void __attribute__ ((nonnull (1)))
 171 alloc_buffer_add_byte (struct alloc_buffer *buf, unsigned char b)
 172 {
 173   if (__glibc_likely (buf->__alloc_buffer_current < buf->__alloc_buffer_end))
 174     {
 175       *(unsigned char *) buf->__alloc_buffer_current = b;
 176       ++buf->__alloc_buffer_current;
 177     }
 178   else
 179     alloc_buffer_mark_failed (buf);
 180 }
 181
 182 /* Obtain a pointer to LENGTH bytes in BUF, and consume these bytes.
 183    NULL is returned if there is not enough room, and the buffer is
 184    marked as failed, or if the buffer has already failed.
 185    (Zero-length allocations from an empty buffer which has not yet
 186    failed succeed.)  */
 187 static inline __attribute__ ((nonnull (1))) void *
 188 alloc_buffer_alloc_bytes (struct alloc_buffer *buf, size_t length)
 189 {
 190   if (length <= alloc_buffer_size (buf))
 191     {
 192       void *result = (void *) buf->__alloc_buffer_current;
 193       buf->__alloc_buffer_current += length;
 194       return result;
 195     }
 196   else
 197     {
 198       alloc_buffer_mark_failed (buf);
 199       return NULL;
 200     }
 201 }
 202
 203 /* Internal function.  Statically assert that the type size is
 204    constant and valid.  */
 205 static __always_inline size_t
 206 __alloc_buffer_assert_size (size_t size)
 207 {
 208   if (!__builtin_constant_p (size))
 209     {
 210       __errordecl (error, "type size is not constant");
 211       error ();
 212     }
 213   else if (size == 0)
 214     {
 215       __errordecl (error, "type size is zero");
 216       error ();
 217     }
 218   return size;
 219 }
 220
 221 /* Internal function.  Statically assert that the type alignment is
 222    constant and valid.  */
 223 static __always_inline size_t
 224 __alloc_buffer_assert_align (size_t align)
 225 {
 226   if (!__builtin_constant_p (align))
 227     {
 228       __errordecl (error, "type alignment is not constant");
 229       error ();
 230     }
 231   else if (align == 0)
 232     {
 233       __errordecl (error, "type alignment is zero");
 234       error ();
 235     }
 236   else if (!powerof2 (align))
 237     {
 238       __errordecl (error, "type alignment is not a power of two");
 239       error ();
 240     }
 241   return align;
 242 }
 243
 244 /* Internal function.  Obtain a pointer to an object.  */
 245 static inline __attribute__ ((nonnull (1))) void *
 246 __alloc_buffer_alloc (struct alloc_buffer *buf, size_t size, size_t align)
 247 {
 248   if (size == 1 && align == 1)
 249     return alloc_buffer_alloc_bytes (buf, size);
 250
 251   size_t current = buf->__alloc_buffer_current;
 252   size_t aligned = roundup (current, align);
 253   size_t new_current = aligned + size;
 254   if (aligned >= current        /* No overflow in align step.  */
 255       && new_current >= size    /* No overflow in size computation.  */
 256       && new_current <= buf->__alloc_buffer_end) /* Room in buffer.  */
 257     {
 258       buf->__alloc_buffer_current = new_current;
 259       return (void *) aligned;
 260     }
 261   else
 262     {
 263       alloc_buffer_mark_failed (buf);
 264       return NULL;
 265     }
 266 }
 267
 268 /* Obtain a TYPE * pointer to an object in BUF of TYPE.  Consume these
 269    bytes from the buffer.  Return NULL and mark the buffer as failed
 270    if there is not enough room in the buffer, or if the buffer has
 271    failed before.  */
 272 #define alloc_buffer_alloc(buf, type)                           \
 273   ((type *) __alloc_buffer_alloc                                \
 274    (buf, __alloc_buffer_assert_size (sizeof (type)),            \
 275     __alloc_buffer_assert_align (__alignof__ (type))))
 276
 277 /* Internal function.  Obtain a pointer to an object which is
 278    subsequently added.  */
 279 static inline const __attribute__ ((nonnull (1))) void *
 280 __alloc_buffer_next (struct alloc_buffer *buf, size_t align)
 281 {
 282   if (align == 1)
 283     return (const void *) buf->__alloc_buffer_current;
 284
 285   size_t current = buf->__alloc_buffer_current;
 286   size_t aligned = roundup (current, align);
 287   if (aligned >= current        /* No overflow in align step.  */
 288       && aligned <= buf->__alloc_buffer_end) /* Room in buffer.  */
 289     {
 290       buf->__alloc_buffer_current = aligned;
 291       return (const void *) aligned;
 292     }
 293   else
 294     {
 295       alloc_buffer_mark_failed (buf);
 296       return NULL;
 297     }
 298 }
 299
 300 /* Like alloc_buffer_alloc, but do not advance the pointer beyond the
 301    object (so a subseqent call to alloc_buffer_next or
 302    alloc_buffer_alloc returns the same pointer).  Note that the buffer
 303    is still aligned according to the requirements of TYPE.  The effect
 304    of this function is similar to allocating a zero-length array from
 305    the buffer.  */
 306 #define alloc_buffer_next(buf, type)                            \
 307   ((const type *) __alloc_buffer_next                           \
 308    (buf, __alloc_buffer_assert_align (__alignof__ (type))))
 309
 310 /* Internal function.  Allocate an array.  */
 311 void * __libc_alloc_buffer_alloc_array (struct alloc_buffer *buf,
 312                                         size_t size, size_t align,
 313                                         size_t count)
 314   __attribute__ ((nonnull (1)));
 315
 316 /* Obtain a TYPE * pointer to an array of COUNT objects in BUF of
 317    TYPE.  Consume these bytes from the buffer.  Return NULL and mark
 318    the buffer as failed if there is not enough room in the buffer,
 319    or if the buffer has failed before.  (Zero-length allocations from
 320    an empty buffer which has not yet failed succeed.)  */
 321 #define alloc_buffer_alloc_array(buf, type, count)       \
 322   ((type *) __libc_alloc_buffer_alloc_array              \
 323    (buf, __alloc_buffer_assert_size (sizeof (type)),     \
 324     __alloc_buffer_assert_align (__alignof__ (type)),    \
 325     count))
 326
 327 /* Internal function.  See alloc_buffer_copy_bytes below.  */
 328 struct alloc_buffer __libc_alloc_buffer_copy_bytes (struct alloc_buffer,
 329                                                     const void *, size_t)
 330   __attribute__ ((nonnull (2)));
 331
 332 /* Copy SIZE bytes starting at SRC into the buffer.  If there is not
 333    enough room in the buffer, the buffer is marked as failed.  No
 334    alignment of the buffer is performed.  */
 335 static inline __attribute__ ((nonnull (1, 2))) void
 336 alloc_buffer_copy_bytes (struct alloc_buffer *buf, const void *src, size_t size)
 337 {
 338   *buf = __libc_alloc_buffer_copy_bytes (*buf, src, size);
 339 }
 340
 341 /* Internal function.  See alloc_buffer_copy_string below.  */
 342 struct alloc_buffer __libc_alloc_buffer_copy_string (struct alloc_buffer,
 343                                                      const char *)
 344   __attribute__ ((nonnull (2)));
 345
 346 /* Copy the string at SRC into the buffer, including its null
 347    terminator.  If there is not enough room in the buffer, the buffer
 348    is marked as failed.  Return a pointer to the string.  */
 349 static inline __attribute__ ((nonnull (1, 2))) char *
 350 alloc_buffer_copy_string (struct alloc_buffer *buf, const char *src)
 351 {
 352   char *result = (char *) buf->__alloc_buffer_current;
 353   *buf = __libc_alloc_buffer_copy_string (*buf, src);
 354   if (alloc_buffer_has_failed (buf))
 355     result = NULL;
 356   return result;
 357 }
 358
 359 #ifndef _ISOMAC
 360 libc_hidden_proto (__libc_alloc_buffer_alloc_array)
 361 libc_hidden_proto (__libc_alloc_buffer_allocate)
 362 libc_hidden_proto (__libc_alloc_buffer_copy_bytes)
 363 libc_hidden_proto (__libc_alloc_buffer_copy_string)
 364 libc_hidden_proto (__libc_alloc_buffer_create_failure)
 365 #endif
 366
 367 #endif /* _ALLOC_BUFFER_H */