server/extents.c

   1 /* nbdkit
   2  * Copyright (C) 2019 Red Hat Inc.
   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 <stdint.h>
  38 #include <stdbool.h>
  39 #include <string.h>
  40 #include <inttypes.h>
  41 #include <errno.h>
  42 #include <assert.h>
  43
  44 #include "minmax.h"
  45
  46 #include "internal.h"
  47
  48 /* Cap nr_extents to avoid sending over-large replies to the client,
  49  * and to avoid a plugin with frequent alternations consuming too much
  50  * memory.
  51  */
  52 #define MAX_EXTENTS (1 * 1024 * 1024)
  53
  54 struct nbdkit_extents {
  55   struct nbdkit_extent *extents;
  56   size_t nr_extents, allocated;
  57
  58   uint64_t start, end; /* end is one byte beyond the end of the range */
  59
  60   /* Where we expect the next extent to be added.  If
  61    * nbdkit_add_extent has never been called this is -1.  Note this
  62    * field is updated even if we don't actually add the extent because
  63    * it's used to check for API violations.
  64    */
  65   int64_t next;
  66 };
  67
  68 struct nbdkit_extents *
  69 nbdkit_extents_new (uint64_t start, uint64_t end)
  70 {
  71   struct nbdkit_extents *r;
  72
  73   if (start > INT64_MAX || end > INT64_MAX) {
  74     nbdkit_error ("nbdkit_extents_new: "
  75                   "start (%" PRIu64 ") or end (%" PRIu64 ") > INT64_MAX",
  76                   start, end);
  77     errno = ERANGE;
  78     return NULL;
  79   }
  80
  81   /* 0-length ranges are possible, so start == end is not an error. */
  82   if (start > end) {
  83     nbdkit_error ("nbdkit_extents_new: "
  84                   "start (%" PRIu64 ") >= end (%" PRIu64 ")",
  85                   start, end);
  86     errno = ERANGE;
  87     return NULL;
  88   }
  89
  90   r = malloc (sizeof *r);
  91   if (r == NULL) {
  92     nbdkit_error ("nbdkit_extents_new: malloc: %m");
  93     return NULL;
  94   }
  95   r->extents = NULL;
  96   r->nr_extents = r->allocated = 0;
  97   r->start = start;
  98   r->end = end;
  99   r->next = -1;
 100   return r;
 101 }
 102
 103 void
 104 nbdkit_extents_free (struct nbdkit_extents *exts)
 105 {
 106   if (exts) {
 107     free (exts->extents);
 108     free (exts);
 109   }
 110 }
 111
 112 size_t
 113 nbdkit_extents_count (const struct nbdkit_extents *exts)
 114 {
 115   return exts->nr_extents;
 116 }
 117
 118 struct nbdkit_extent
 119 nbdkit_get_extent (const struct nbdkit_extents *exts, size_t i)
 120 {
 121   assert (i < exts->nr_extents);
 122   return exts->extents[i];
 123 }
 124
 125 /* Insert *e in the list at the end. */
 126 static int
 127 append_extent (struct nbdkit_extents *exts, const struct nbdkit_extent *e)
 128 {
 129   if (exts->nr_extents >= exts->allocated) {
 130     size_t new_allocated;
 131     struct nbdkit_extent *new_extents;
 132
 133     new_allocated = exts->allocated;
 134     if (new_allocated == 0)
 135       new_allocated = 1;
 136     new_allocated *= 2;
 137     new_extents =
 138       realloc (exts->extents, new_allocated * sizeof (struct nbdkit_extent));
 139     if (new_extents == NULL) {
 140       nbdkit_error ("nbdkit_add_extent: realloc: %m");
 141       return -1;
 142     }
 143     exts->allocated = new_allocated;
 144     exts->extents = new_extents;
 145   }
 146
 147   exts->extents[exts->nr_extents] = *e;
 148   exts->nr_extents++;
 149   return 0;
 150 }
 151
 152 int
 153 nbdkit_add_extent (struct nbdkit_extents *exts,
 154                    uint64_t offset, uint64_t length, uint32_t type)
 155 {
 156   uint64_t overlap;
 157
 158   /* Extents must be added in strictly ascending, contiguous order. */
 159   if (exts->next >= 0 && exts->next != offset) {
 160     nbdkit_error ("nbdkit_add_extent: "
 161                   "extents must be added in ascending order and "
 162                   "must be contiguous");
 163     errno = ERANGE;
 164     return -1;
 165   }
 166   exts->next = offset + length;
 167
 168   /* Ignore zero-length extents. */
 169   if (length == 0)
 170     return 0;
 171
 172   /* Ignore extents beyond the end of the range, or if list is full. */
 173   if (offset >= exts->end || exts->nr_extents >= MAX_EXTENTS)
 174     return 0;
 175
 176   /* Shorten extents that overlap the end of the range. */
 177   if (offset + length > exts->end) {
 178     overlap = offset + length - exts->end;
 179     length -= overlap;
 180   }
 181
 182   if (exts->nr_extents == 0) {
 183     /* If there are no existing extents, and the new extent is
 184      * entirely before start, ignore it.
 185      */
 186     if (offset + length <= exts->start)
 187       return 0;
 188
 189     /* If there are no existing extents, and the new extent is after
 190      * start, then this is a bug in the plugin.
 191      */
 192     if (offset > exts->start) {
 193       nbdkit_error ("nbdkit_add_extent: "
 194                     "first extent must not be > start (%" PRIu64 ")",
 195                     exts->start);
 196       errno = ERANGE;
 197       return -1;
 198     }
 199
 200     /* If there are no existing extents, and the new extent overlaps
 201      * start, truncate it so it starts at start.
 202      */
 203     overlap = exts->start - offset;
 204     length -= overlap;
 205     offset += overlap;
 206   }
 207
 208   /* If we get here we are going to either add or extend. */
 209   if (exts->nr_extents > 0 &&
 210       exts->extents[exts->nr_extents-1].type == type) {
 211     /* Coalesce with the last extent. */
 212     exts->extents[exts->nr_extents-1].length += length;
 213     return 0;
 214   }
 215   else {
 216     /* Add a new extent. */
 217     const struct nbdkit_extent e =
 218       { .offset = offset, .length = length, .type = type };
 219     return append_extent (exts, &e);
 220   }
 221 }