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