common/utils/vector.c

   1 /* nbdkit
   2  * Copyright Red Hat
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  * * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *
  11  * * Redistributions in binary form must reproduce the above copyright
  12  * notice, this list of conditions and the following disclaimer in the
  13  * documentation and/or other materials provided with the distribution.
  14  *
  15  * * Neither the name of Red Hat nor the names of its contributors may be
  16  * used to endorse or promote products derived from this software without
  17  * specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  21  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
  22  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
  23  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  26  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  27  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  28  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  29  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  */
  32
  33 #include <config.h>
  34
  35 #include <stdio.h>
  36 #include <stdlib.h>
  37 #include <unistd.h>
  38 #include <errno.h>
  39 #include <assert.h>
  40
  41 #include "checked-overflow.h"
  42 #include "posix_memalign.h"
  43 #include "sysconf.h"
  44 #include "vector.h"
  45
  46 static int
  47 calculate_capacity (struct generic_vector *v, size_t n, size_t itemsize,
  48                     size_t *newcap_r, size_t *newbytes_r)
  49 {
  50   size_t reqcap, reqbytes, newcap, newbytes, t;
  51
  52   /* New capacity requested.  We must allocate this minimum (or fail).
  53    *   reqcap = v->cap + n
  54    *   reqbytes = reqcap * itemsize
  55    */
  56   if (ADD_OVERFLOW (v->cap, n, &reqcap) ||
  57       MUL_OVERFLOW (reqcap, itemsize, &reqbytes)) {
  58     errno = ENOMEM;
  59     return -1;
  60   }
  61
  62   /* However for the sake of optimization, scale buffer by 3/2 so that
  63    * repeated reservations don't call realloc often.
  64    *   newcap = v->cap + (v->cap + 1) / 2
  65    *   newbytes = newcap * itemsize
  66    */
  67   if (ADD_OVERFLOW (v->cap, 1u, &t) ||
  68       ADD_OVERFLOW (v->cap, t/2, &newcap) ||
  69       MUL_OVERFLOW (newcap, itemsize, &newbytes) ||
  70       newbytes < reqbytes) {
  71     /* If that either overflows or is less than the minimum requested,
  72      * fall back to the requested capacity.
  73      */
  74     newcap = reqcap;
  75     newbytes = reqbytes;
  76   }
  77
  78   *newcap_r = newcap;
  79   *newbytes_r = newbytes;
  80   return 0;
  81 }
  82
  83 int
  84 generic_vector_reserve (struct generic_vector *v, size_t n, size_t itemsize)
  85 {
  86   void *newptr;
  87   size_t newcap, newbytes;
  88
  89   if (calculate_capacity (v, n, itemsize, &newcap, &newbytes) == -1)
  90     return -1;
  91
  92   newptr = realloc (v->ptr, newbytes);
  93   if (newptr == NULL)
  94     return -1;
  95
  96   v->ptr = newptr;
  97   v->cap = newcap;
  98   return 0;
  99 }
 100
 101 /* Always allocates a buffer which is page aligned (both base and size). */
 102 int
 103 generic_vector_reserve_page_aligned (struct generic_vector *v,
 104                                      size_t n, size_t itemsize)
 105 {
 106   int r;
 107   void *newptr;
 108   size_t newcap, newbytes;
 109   long pagesize;
 110   size_t extra, extra_items;
 111
 112   pagesize = sysconf (_SC_PAGESIZE);
 113   assert (pagesize > 1);
 114
 115   assert (pagesize % itemsize == 0);
 116
 117   if (calculate_capacity (v, n, itemsize, &newcap, &newbytes) == -1)
 118     return -1;
 119
 120   /* If the new size (in bytes) is not a full page then we have to
 121    * round up to the next page.
 122    */
 123   extra = newbytes & (pagesize - 1);
 124   if (extra > 0) {
 125     extra_items = (pagesize - extra) / itemsize;
 126
 127     if (ADD_OVERFLOW (newcap, extra_items, &newcap) ||
 128         ADD_OVERFLOW (newbytes, extra_items * itemsize, &newbytes)) {
 129       errno = ENOMEM;
 130       return -1;
 131     }
 132   }
 133
 134   if ((r = posix_memalign (&newptr, pagesize, newbytes)) != 0) {
 135     errno = r;
 136     return -1;
 137   }
 138
 139   /* How much to copy here?
 140    *
 141    * vector_reserve always makes the buffer larger so we don't have to
 142    * deal with the case of a shrinking buffer.
 143    *
 144    * Like the underlying realloc we do not have to zero the newly
 145    * reserved elements.
 146    *
 147    * However (like realloc) we have to copy the existing elements even
 148    * those that are not allocated and only reserved (between 'len' and
 149    * 'cap').
 150    *
 151    * The spec of vector is not clear on the last two points, but
 152    * existing code depends on this undocumented behaviour.
 153    */
 154   memcpy (newptr, v->ptr, v->cap * itemsize);
 155   free (v->ptr);
 156   v->ptr = newptr;
 157   v->cap = newcap;
 158   return 0;
 159 }