server/extents.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 <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 "cleanup.h"
  45 #include "isaligned.h"
  46 #include "minmax.h"
  47 #include "rounding.h"
  48 #include "vector.h"
  49
  50 #include "internal.h"
  51
  52 /* Cap nr_extents to avoid sending over-large replies to the client,
  53  * and to avoid a plugin with frequent alternations consuming too much
  54  * memory.
  55  */
  56 #define MAX_EXTENTS (1 * 1024 * 1024)
  57
  58 /* Appendable list of extents. */
  59 DEFINE_VECTOR_TYPE (extents, struct nbdkit_extent);
  60
  61 struct nbdkit_extents {
  62   extents extents;
  63
  64   uint64_t start, end; /* end is one byte beyond the end of the range */
  65
  66   /* Where we expect the next extent to be added.  If
  67    * nbdkit_add_extent has never been called this is -1.  Note this
  68    * field is updated even if we don't actually add the extent because
  69    * it's used to check for API violations.
  70    */
  71   int64_t next;
  72 };
  73
  74 NBDKIT_DLL_PUBLIC struct nbdkit_extents *
  75 nbdkit_extents_new (uint64_t start, uint64_t end)
  76 {
  77   struct nbdkit_extents *r;
  78
  79   if (start > INT64_MAX || end > INT64_MAX) {
  80     nbdkit_error ("nbdkit_extents_new: "
  81                   "start (%" PRIu64 ") or end (%" PRIu64 ") > INT64_MAX",
  82                   start, end);
  83     errno = ERANGE;
  84     return NULL;
  85   }
  86
  87   /* 0-length ranges are possible, so start == end is not an error. */
  88   if (start > end) {
  89     nbdkit_error ("nbdkit_extents_new: "
  90                   "start (%" PRIu64 ") >= end (%" PRIu64 ")",
  91                   start, end);
  92     errno = ERANGE;
  93     return NULL;
  94   }
  95
  96   r = malloc (sizeof *r);
  97   if (r == NULL) {
  98     nbdkit_error ("nbdkit_extents_new: malloc: %m");
  99     return NULL;
 100   }
 101   r->extents = (extents) empty_vector;
 102   r->start = start;
 103   r->end = end;
 104   r->next = -1;
 105   return r;
 106 }
 107
 108 NBDKIT_DLL_PUBLIC void
 109 nbdkit_extents_free (struct nbdkit_extents *exts)
 110 {
 111   if (exts) {
 112     free (exts->extents.ptr);
 113     free (exts);
 114   }
 115 }
 116
 117 NBDKIT_DLL_PUBLIC size_t
 118 nbdkit_extents_count (const struct nbdkit_extents *exts)
 119 {
 120   return exts->extents.len;
 121 }
 122
 123 NBDKIT_DLL_PUBLIC struct nbdkit_extent
 124 nbdkit_get_extent (const struct nbdkit_extents *exts, size_t i)
 125 {
 126   assert (i < exts->extents.len);
 127   return exts->extents.ptr[i];
 128 }
 129
 130 /* Insert *e in the list at the end. */
 131 static int
 132 append_extent (struct nbdkit_extents *exts, const struct nbdkit_extent *e)
 133 {
 134   if (extents_append (&exts->extents, *e) == -1) {
 135     nbdkit_error ("nbdkit_add_extent: realloc: %m");
 136     return -1;
 137   }
 138
 139   return 0;
 140 }
 141
 142 NBDKIT_DLL_PUBLIC int
 143 nbdkit_add_extent (struct nbdkit_extents *exts,
 144                    uint64_t offset, uint64_t length, uint32_t type)
 145 {
 146   uint64_t overlap;
 147
 148   /* Extents must be added in strictly ascending, contiguous order. */
 149   if (exts->next >= 0 && exts->next != offset) {
 150     nbdkit_error ("nbdkit_add_extent: "
 151                   "extents must be added in ascending order and "
 152                   "must be contiguous");
 153     errno = ERANGE;
 154     return -1;
 155   }
 156   exts->next = offset + length;
 157
 158   /* Ignore zero-length extents. */
 159   if (length == 0)
 160     return 0;
 161
 162   /* Ignore extents beyond the end of the range, or if list is full. */
 163   if (offset >= exts->end || exts->extents.len >= MAX_EXTENTS)
 164     return 0;
 165
 166   /* Shorten extents that overlap the end of the range. */
 167   if (offset + length > exts->end) {
 168     overlap = offset + length - exts->end;
 169     length -= overlap;
 170   }
 171
 172   if (exts->extents.len == 0) {
 173     /* If there are no existing extents, and the new extent is
 174      * entirely before start, ignore it.
 175      */
 176     if (offset + length <= exts->start)
 177       return 0;
 178
 179     /* If there are no existing extents, and the new extent is after
 180      * start, then this is a bug in the plugin.
 181      */
 182     if (offset > exts->start) {
 183       nbdkit_error ("nbdkit_add_extent: "
 184                     "first extent must not be > start (%" PRIu64 ")",
 185                     exts->start);
 186       errno = ERANGE;
 187       return -1;
 188     }
 189
 190     /* If there are no existing extents, and the new extent overlaps
 191      * start, truncate it so it starts at start.
 192      */
 193     overlap = exts->start - offset;
 194     length -= overlap;
 195     offset += overlap;
 196   }
 197
 198   /* If we get here we are going to either add or extend. */
 199   if (exts->extents.len > 0 &&
 200       exts->extents.ptr[exts->extents.len-1].type == type) {
 201     /* Coalesce with the last extent. */
 202     exts->extents.ptr[exts->extents.len-1].length += length;
 203     return 0;
 204   }
 205   else {
 206     /* Add a new extent. */
 207     const struct nbdkit_extent e =
 208       { .offset = offset, .length = length, .type = type };
 209     return append_extent (exts, &e);
 210   }
 211 }
 212
 213 /* Compute aligned extents on behalf of a filter. */
 214 NBDKIT_DLL_PUBLIC int
 215 nbdkit_extents_aligned (struct context *next_c,
 216                         uint32_t count, uint64_t offset,
 217                         uint32_t flags, uint32_t align,
 218                         struct nbdkit_extents *exts, int *err)
 219 {
 220   struct nbdkit_next_ops *next = &next_c->next;
 221   size_t i;
 222   struct nbdkit_extent *e, *e2;
 223
 224   assert (IS_ALIGNED (count | offset, align));
 225
 226   /* Perform an initial query, then scan for the first unaligned extent. */
 227   if (next->extents (next_c, count, offset, flags, exts, err) == -1)
 228     return -1;
 229   for (i = 0; i < exts->extents.len; ++i) {
 230     e = &exts->extents.ptr[i];
 231     if (!IS_ALIGNED (e->length, align)) {
 232       /* If the unalignment is past align, just truncate and return early */
 233       if (e->offset + e->length > offset + align) {
 234         e->length = ROUND_DOWN (e->length, align);
 235         exts->extents.len = i + !!e->length;
 236         exts->next = e->offset + e->length;
 237         break;
 238       }
 239
 240       /* Otherwise, coalesce until we have at least align bytes, which
 241        * may require further queries. The type bits are:
 242        *  NBDKIT_EXTENT_HOLE (1<<0)
 243        *  NBDKIT_EXTENT_ZERO (1<<1)
 244        * and the NBD protocol says any future bits will also have the
 245        * desired property that returning '0' is the safe default for
 246        * the generic case.  Thus, performing the bitwise-and
 247        * intersection of the types of underlying extents gives the
 248        * correct type for our merged extent.
 249        */
 250       assert (i == 0);
 251       while (e->length < align) {
 252         if (exts->extents.len > 1) {
 253           e->length += exts->extents.ptr[1].length;
 254           e->type &= exts->extents.ptr[1].type;
 255           extents_remove (&exts->extents, 1);
 256         }
 257         else {
 258           /* The plugin needs a fresh extents object each time, but
 259            * with care, we can merge it into the callers' exts.
 260            */
 261           extents tmp;
 262           CLEANUP_EXTENTS_FREE struct nbdkit_extents *extents2 = NULL;
 263
 264           extents2 = nbdkit_extents_new (e->offset + e->length,
 265                                          offset + align);
 266           if (extents2 == NULL) {
 267             *err = errno;
 268             return -1;
 269           }
 270           if (next->extents (next_c, align - e->length,
 271                              offset + e->length,
 272                              flags & ~NBDKIT_FLAG_REQ_ONE,
 273                              extents2, err) == -1)
 274             return -1;
 275           e2 = &extents2->extents.ptr[0];
 276           assert (e2->offset == e->offset + e->length);
 277           e2->offset = e->offset;
 278           e2->length += e->length;
 279           e2->type &= e->type;
 280           e = e2;
 281           tmp = exts->extents;
 282           exts->extents = extents2->extents;
 283           extents2->extents = tmp;
 284         }
 285       }
 286       e->length = align;
 287       exts->extents.len = 1;
 288       exts->next = e->offset + e->length;
 289       break;
 290     }
 291   }
 292   /* Once we get here, all extents are aligned. */
 293   return 0;
 294 }
 295
 296 /* This is a convenient wrapper around next_ops->extents which can be
 297  * used from filters where you want to get a complete set of extents
 298  * covering the region [offset..offset+count-1].
 299  */
 300 NBDKIT_DLL_PUBLIC struct nbdkit_extents *
 301 nbdkit_extents_full (struct context *next_c,
 302                      uint32_t count, uint64_t offset, uint32_t flags,
 303                      int *err)
 304 {
 305   struct nbdkit_next_ops *next = &next_c->next;
 306   struct nbdkit_extents *ret;
 307
 308   /* Clear REQ_ONE to ask the plugin for as much information as it is
 309    * willing to return (the plugin may still truncate if it is too
 310    * costly to provide everything).
 311    */
 312   flags &= ~NBDKIT_FLAG_REQ_ONE;
 313
 314   ret = nbdkit_extents_new (offset, offset+count);
 315   if (ret == NULL) goto error0;
 316
 317   while (count > 0) {
 318     const uint64_t old_offset = offset;
 319     size_t i;
 320
 321     CLEANUP_EXTENTS_FREE struct nbdkit_extents *t
 322       = nbdkit_extents_new (offset, offset+count);
 323     if (t == NULL) goto error1;
 324
 325     if (next->extents (next_c, count, offset, flags, t, err) == -1)
 326       goto error0;
 327
 328     for (i = 0; i < nbdkit_extents_count (t); ++i) {
 329       const struct nbdkit_extent e = nbdkit_get_extent (t, i);
 330       if (nbdkit_add_extent (ret, e.offset, e.length, e.type) == -1)
 331         goto error1;
 332
 333       assert (e.length <= count);
 334       offset += e.length;
 335       count -= e.length;
 336     }
 337
 338     /* If the plugin is behaving we must make forward progress. */
 339     assert (offset > old_offset);
 340   }
 341
 342   return ret;
 343
 344  error1:
 345   *err = errno;
 346  error0:
 347   nbdkit_extents_free (ret);
 348   return NULL;
 349 }