filters/extentlist/extentlist.c

   1 /* nbdkit
   2  * Copyright (C) 2019-2020 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 <inttypes.h>
  39 #include <string.h>
  40 #include <errno.h>
  41 #include <assert.h>
  42
  43 #include <nbdkit-filter.h>
  44
  45 #include "cleanup.h"
  46 #include "getline.h"
  47 #include "minmax.h"
  48 #include "vector.h"
  49
  50 #define HOLE (NBDKIT_EXTENT_HOLE|NBDKIT_EXTENT_ZERO)
  51
  52 static const char *extentlist;
  53
  54 /* List of extents.  Once we've finally parsed them this will be
  55  * ordered, non-overlapping and have no gaps.
  56  */
  57 struct extent {
  58   uint64_t offset, length;
  59   uint32_t type;
  60 };
  61 DEFINE_VECTOR_TYPE(extent_list, struct extent);
  62 static extent_list extents;
  63
  64 static void
  65 extentlist_unload (void)
  66 {
  67   free (extents.ptr);
  68 }
  69
  70 /* Called for each key=value passed on the command line. */
  71 static int
  72 extentlist_config (nbdkit_next_config *next, nbdkit_backend *nxdata,
  73                    const char *key, const char *value)
  74 {
  75   if (strcmp (key, "extentlist") == 0) {
  76     if (extentlist != NULL) {
  77       nbdkit_error ("extentlist cannot appear twice");
  78       exit (EXIT_FAILURE);
  79     }
  80     extentlist = value;
  81     return 0;
  82   }
  83   else
  84     return next (nxdata, key, value);
  85 }
  86
  87 static int
  88 extentlist_config_complete (nbdkit_next_config_complete *next,
  89                             nbdkit_backend *nxdata)
  90 {
  91   if (extentlist == NULL) {
  92     nbdkit_error ("you must supply the extentlist parameter "
  93                   "on the command line");
  94     return -1;
  95   }
  96
  97   return next (nxdata);
  98 }
  99
 100 static int
 101 compare_offsets (const struct extent *e1, const struct extent *e2)
 102 {
 103   if (e1->offset < e2->offset)
 104     return -1;
 105   else if (e1->offset > e2->offset)
 106     return 1;
 107   else
 108     return 0;
 109 }
 110
 111 static int
 112 compare_ranges (const void *ev1, const struct extent *e2)
 113 {
 114   const struct extent *e1 = ev1;
 115
 116   if (e1->offset < e2->offset)
 117     return -1;
 118   else if (e1->offset >= e2->offset + e2->length)
 119     return 1;
 120   else
 121     return 0;
 122 }
 123
 124 /* Similar to parse_extents in plugins/sh/methods.c */
 125 static void
 126 parse_extentlist (void)
 127 {
 128   FILE *fp;
 129   CLEANUP_FREE char *line = NULL;
 130   size_t linelen = 0;
 131   ssize_t len;
 132   size_t i;
 133   uint64_t end;
 134
 135   assert (extentlist != NULL);
 136   assert (extents.ptr == NULL);
 137   assert (extents.len == 0);
 138
 139   fp = fopen (extentlist, "r");
 140   if (!fp) {
 141     nbdkit_error ("open: %s: %m", extentlist);
 142     exit (EXIT_FAILURE);
 143   }
 144
 145   while ((len = getline (&line, &linelen, fp)) != -1) {
 146     const char *delim = " \t";
 147     char *sp, *p;
 148     int64_t offset, length;
 149     uint32_t type;
 150
 151     if (len > 0 && line[len-1] == '\n') {
 152       line[len-1] = '\0';
 153       len--;
 154     }
 155
 156     if ((p = strtok_r (line, delim, &sp)) == NULL) {
 157     parse_error:
 158       nbdkit_error ("%s: cannot parse %s", extentlist, line);
 159       exit (EXIT_FAILURE);
 160     }
 161     offset = nbdkit_parse_size (p);
 162     if (offset == -1)
 163       exit (EXIT_FAILURE);
 164
 165     if ((p = strtok_r (NULL, delim, &sp)) == NULL)
 166       goto parse_error;
 167     length = nbdkit_parse_size (p);
 168     if (length == -1)
 169       exit (EXIT_FAILURE);
 170
 171     /* Skip zero length extents.  Makes the rest of the code easier. */
 172     if (length == 0)
 173       continue;
 174
 175     if ((p = strtok_r (NULL, delim, &sp)) == NULL)
 176       /* empty type field means allocated data (0) */
 177       type = 0;
 178     else if (sscanf (p, "%" SCNu32, &type) == 1)
 179       ;
 180     else {
 181       type = 0;
 182       if (strstr (p, "hole") != NULL)
 183         type |= NBDKIT_EXTENT_HOLE;
 184       if (strstr (p, "zero") != NULL)
 185         type |= NBDKIT_EXTENT_ZERO;
 186     }
 187
 188     if (extent_list_append (&extents,
 189                             (struct extent){.offset = offset, .length=length,
 190                                             .type=type}) == -1) {
 191       nbdkit_error ("realloc: %m");
 192       exit (EXIT_FAILURE);
 193     }
 194   }
 195
 196   fclose (fp);
 197
 198   /* Sort the extents by offset. */
 199   extent_list_sort (&extents, compare_offsets);
 200
 201   /* There must not be overlaps at this point. */
 202   end = 0;
 203   for (i = 0; i < extents.len; ++i) {
 204     if (extents.ptr[i].offset < end ||
 205         extents.ptr[i].offset + extents.ptr[i].length < extents.ptr[i].offset) {
 206       nbdkit_error ("extents in the extent list are overlapping");
 207       exit (EXIT_FAILURE);
 208     }
 209     end = extents.ptr[i].offset + extents.ptr[i].length;
 210   }
 211
 212   /* If there's a gap at the beginning, insert a hole|zero extent. */
 213   if (extents.len == 0 || extents.ptr[0].offset > 0) {
 214     end = extents.len == 0 ? UINT64_MAX : extents.ptr[0].offset;
 215     if (extent_list_insert (&extents,
 216                             (struct extent){.offset = 0, .length = end,
 217                                             .type = HOLE},
 218                             0) == -1) {
 219       nbdkit_error ("realloc: %m");
 220       exit (EXIT_FAILURE);
 221     }
 222   }
 223
 224   /* Now insert hole|zero extents after every extent where there
 225    * is a gap between that extent and the next one.
 226    */
 227   for (i = 0; i < extents.len-1; ++i) {
 228     end = extents.ptr[i].offset + extents.ptr[i].length;
 229     if (end < extents.ptr[i+1].offset)
 230       if (extent_list_insert (&extents,
 231                               (struct extent){.offset = end,
 232                                               .length = extents.ptr[i+1].offset - end,
 233                                               .type = HOLE},
 234                               i+1) == -1) {
 235         nbdkit_error ("realloc: %m");
 236         exit (EXIT_FAILURE);
 237       }
 238   }
 239
 240   /* If there's a gap at the end, insert a hole|zero extent. */
 241   end = extents.ptr[extents.len-1].offset + extents.ptr[extents.len-1].length;
 242   if (end < UINT64_MAX) {
 243     if (extent_list_append (&extents,
 244                             (struct extent){.offset = end,
 245                                             .length = UINT64_MAX-end,
 246                                             .type = HOLE}) == -1) {
 247       nbdkit_error ("realloc: %m");
 248       exit (EXIT_FAILURE);
 249     }
 250   }
 251
 252   /* Debug the final list. */
 253   for (i = 0; i < extents.len; ++i) {
 254     nbdkit_debug ("extentlist: "
 255                   "extent[%zu] = %" PRIu64 "-%" PRIu64 " (length %" PRIu64 ")"
 256                   " type %" PRIu32,
 257                   i, extents.ptr[i].offset,
 258                   extents.ptr[i].offset + extents.ptr[i].length - 1,
 259                   extents.ptr[i].length,
 260                   extents.ptr[i].type);
 261   }
 262 }
 263
 264 static int
 265 extentlist_get_ready (int thread_model)
 266 {
 267   parse_extentlist ();
 268
 269   return 0;
 270 }
 271
 272 static int
 273 extentlist_can_extents (nbdkit_next *next,
 274                         void *handle)
 275 {
 276   return 1;
 277 }
 278
 279 /* Use ‘-D extentlist.lookup=1’ to debug the function below. */
 280 NBDKIT_DLL_PUBLIC int extentlist_debug_lookup = 0;
 281
 282 /* Read extents. */
 283 static int
 284 extentlist_extents (nbdkit_next *next,
 285                     void *handle, uint32_t count, uint64_t offset,
 286                     uint32_t flags,
 287                     struct nbdkit_extents *ret_extents,
 288                     int *err)
 289 {
 290   const struct extent eoffset = { .offset = offset };
 291   struct extent *p;
 292   ssize_t i;
 293   uint64_t end;
 294
 295   /* Find the starting point in the extents list. */
 296   p = extent_list_search (&extents, &eoffset, compare_ranges);
 297   assert (p != NULL);
 298   i = p - extents.ptr;
 299
 300   /* Add extents to the output. */
 301   while (count > 0) {
 302     if (extentlist_debug_lookup)
 303       nbdkit_debug ("extentlist lookup: "
 304                     "loop i=%zd count=%" PRIu32 " offset=%" PRIu64,
 305                     i, count, offset);
 306
 307     end = extents.ptr[i].offset + extents.ptr[i].length;
 308     if (nbdkit_add_extent (ret_extents, offset, end - offset,
 309                            extents.ptr[i].type) == -1)
 310       return -1;
 311
 312     count -= MIN (count, end-offset);
 313     offset = end;
 314     i++;
 315   }
 316
 317   return 0;
 318 }
 319
 320 static struct nbdkit_filter filter = {
 321   .name              = "extentlist",
 322   .longname          = "nbdkit extentlist filter",
 323   .unload            = extentlist_unload,
 324   .config            = extentlist_config,
 325   .config_complete   = extentlist_config_complete,
 326   .get_ready         = extentlist_get_ready,
 327   .can_extents       = extentlist_can_extents,
 328   .extents           = extentlist_extents,
 329 };
 330
 331 NBDKIT_REGISTER_FILTER(filter)