[Libguestfs] [PATCH nbdkit 3/4] Add map filter.

Tuesday, 31 July 2018

diff --git a/common-rules.mk b/common-rules.mk
index f600293..ae8d701 100644
--- a/common-rules.mk
+++ b/common-rules.mk
@@ -66,6 +66,7 @@ filters = \
 	delay \
 	fua \
 	log \
+	map \
 	nozero \
 	offset \
 	partition \
diff --git a/configure.ac b/configure.ac
index e8d0a38..2f40984 100644
--- a/configure.ac
+++ b/configure.ac
@@ -575,6 +575,7 @@ AC_CONFIG_FILES([Makefile
                  filters/delay/Makefile
                  filters/fua/Makefile
                  filters/log/Makefile
+                 filters/map/Makefile
                  filters/nozero/Makefile
                  filters/offset/Makefile
                  filters/partition/Makefile
diff --git a/filters/map/Makefile.am b/filters/map/Makefile.am
new file mode 100644
index 0000000..96b5be8
--- /dev/null
+++ b/filters/map/Makefile.am
@@ -0,0 +1,61 @@
+# nbdkit
+# Copyright (C) 2018 Red Hat Inc.
+# All rights reserved.
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions are
+# met:
+#
+# * Redistributions of source code must retain the above copyright
+# notice, this list of conditions and the following disclaimer.
+#
+# * Redistributions in binary form must reproduce the above copyright
+# notice, this list of conditions and the following disclaimer in the
+# documentation and/or other materials provided with the distribution.
+#
+# * Neither the name of Red Hat nor the names of its contributors may be
+# used to endorse or promote products derived from this software without
+# specific prior written permission.
+#
+# THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND
+# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+# THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+# PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
+# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+# USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+# SUCH DAMAGE.
+
+include $(top_srcdir)/common-rules.mk
+
+EXTRA_DIST = nbdkit-map-filter.pod
+
+filter_LTLIBRARIES = nbdkit-map-filter.la
+
+nbdkit_map_filter_la_SOURCES = \
+	map.c \
+	maptype.c \
+	maptype.h \
+	$(top_srcdir)/include/nbdkit-filter.h
+nbdkit_map_filter_la_CPPFLAGS = \
+	-I$(top_srcdir)/include
+nbdkit_map_filter_la_CFLAGS = \
+	$(WARNINGS_CFLAGS)
+nbdkit_map_filter_la_LDFLAGS = \
+	-module -avoid-version -shared
+
+if HAVE_POD
+
+man_MANS = nbdkit-map-filter.1
+CLEANFILES += $(man_MANS)
+
+nbdkit-map-filter.1: nbdkit-map-filter.pod
+	$(PODWRAPPER) --section=1 --man $@ \
+	    --html $(top_builddir)/html/$@.html \
+	    $<
+
+endif HAVE_POD
diff --git a/filters/map/map.c b/filters/map/map.c
new file mode 100644
index 0000000..d551104
--- /dev/null
+++ b/filters/map/map.c
@@ -0,0 +1,256 @@
+/* nbdkit
+ * Copyright (C) 2018 Red Hat Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * * Neither the name of Red Hat nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without
+ * specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+ * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+ * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <config.h>
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+#include <inttypes.h>
+#include <ctype.h>
+#include <assert.h>
+
+#include <nbdkit-filter.h>
+
+#include "maptype.h"
+
+#define THREAD_MODEL NBDKIT_THREAD_MODEL_PARALLEL
+
+static char *filename;          /* Map filename. */
+
+static void
+map_unload (void)
+{
+  free (filename);
+}
+
+/* Expect map=filename on the command line, pass everything else
+ * through.
+ */
+static int
+map_config (nbdkit_next_config *next, void *nxdata,
+            const char *key, const char *value)
+{
+  if (strcmp (key, "map") == 0) {
+    filename = nbdkit_realpath (value);
+    if (filename == NULL)
+      return -1;
+    return 0;
+  }
+  else
+    return next (nxdata, key, value);
+}
+
+/* Check that map parameter was supplied. */
+static int
+map_config_complete (nbdkit_next_config_complete *next, void *nxdata)
+{
+  if (filename == NULL) {
+    nbdkit_error ("map=<filename> must be passed to the map filter");
+    return -1;
+  }
+
+  return next (nxdata);
+}
+
+#define map_config_help \
+  "map=<FILENAME>      (required) Map file."
+
+struct handle {
+  /* We have to load the map file separately for each handle
+   * for a couple of reasons, the second one being critical:
+   *
+   * (1) The map file might change.
+   *
+   * (2) The size of the underlying plugin affects the behaviour
+   * of open-ended intervals in the map.
+   */
+  struct map map;
+};
+
+static void *
+map_open (nbdkit_next_open *next, void *nxdata, int readonly)
+{
+  struct handle *h;
+
+  if (next (nxdata, readonly) == -1)
+    return NULL;
+
+  h = malloc (sizeof *h);
+  if (h == NULL) {
+    nbdkit_error ("malloc: %m");
+    return NULL;
+  }
+  map_init (&h->map);
+
+  return h;
+}
+
+/* Force an early call to get the size of the map, then read the
+ * map file.
+ */
+static int
+map_prepare (struct nbdkit_next_ops *next_ops, void *nxdata,
+             void *handle)
+{
+  struct handle *h = handle;
+  int64_t size;
+
+  size = next_ops->get_size (nxdata);
+  if (size == -1)
+    return -1;
+  nbdkit_debug ("map: plugin size: %" PRIi64, size);
+
+  if (map_load_from_file (filename, size, &h->map) == -1)
+    return -1;
+
+  return 0;
+}
+
+static void
+map_close (void *handle)
+{
+  struct handle *h = handle;
+
+  map_free (&h->map);
+  free (h);
+}
+
+/* Get size. */
+static int64_t
+map_get_size (struct nbdkit_next_ops *next_ops, void *nxdata, void *handle)
+{
+  struct handle *h = handle;
+  int64_t r;
+
+  r = map_size (&h->map);
+  nbdkit_debug ("map: filter size: %" PRIi64, r);
+  return r;
+}
+
+/* Read data. */
+struct pread_data {
+  struct nbdkit_next_ops *next_ops;
+  void *nxdata;
+  void *buf;
+  uint32_t flags;
+  int *err;
+};
+
+static int
+do_pread (void *vp, uint32_t count, uint64_t offs)
+{
+  struct pread_data *data = vp;
+
+  if (data->next_ops->pread (data->nxdata, data->buf,
+                             count, offs, data->flags, data->err) == -1)
+    return -1;
+  data->buf += count;
+  return 0;
+}
+
+static int
+do_pread_unmapped (void *vp, uint32_t count)
+{
+  struct pread_data *data = vp;
+
+  /* Unmapped data reads as zeroes. */
+  memset (data->buf, 0, count);
+  return 0;
+}
+
+static int
+map_pread (struct nbdkit_next_ops *next_ops, void *nxdata,
+           void *handle, void *buf, uint32_t count, uint64_t offs,
+           uint32_t flags, int *err)
+{
+  struct handle *h = handle;
+  struct pread_data data = {
+    .next_ops = next_ops,
+    .nxdata = nxdata,
+    .buf = buf,
+    .flags = flags,
+    .err = err,
+  };
+
+  return map_iter (&h->map, count, offs, &data, do_pread, do_pread_unmapped);
+}
+
+/* Write data. */
+static int
+map_pwrite (struct nbdkit_next_ops *next_ops, void *nxdata,
+            void *handle,
+            const void *buf, uint32_t count, uint64_t offs, uint32_t flags,
+            int *err)
+{
+  abort ();
+}
+
+/* Trim data. */
+static int
+map_trim (struct nbdkit_next_ops *next_ops, void *nxdata,
+          void *handle, uint32_t count, uint64_t offs, uint32_t flags,
+          int *err)
+{
+  abort ();
+}
+
+/* Zero data. */
+static int
+map_zero (struct nbdkit_next_ops *next_ops, void *nxdata,
+          void *handle, uint32_t count, uint64_t offs, uint32_t flags,
+          int *err)
+{
+  abort ();
+}
+
+static struct nbdkit_filter filter = {
+  .name              = "map",
+  .longname          = "nbdkit map filter",
+  .version           = PACKAGE_VERSION,
+  .unload            = map_unload,
+  .config            = map_config,
+  .config_complete   = map_config_complete,
+  .config_help       = map_config_help,
+  .open              = map_open,
+  .prepare           = map_prepare,
+  .close             = map_close,
+  .get_size          = map_get_size,
+  .pread             = map_pread,
+  .pwrite            = map_pwrite,
+  .trim              = map_trim,
+  .zero              = map_zero,
+};
+
+NBDKIT_REGISTER_FILTER(filter)
diff --git a/filters/map/maptype.c b/filters/map/maptype.c
new file mode 100644
index 0000000..ef99363
--- /dev/null
+++ b/filters/map/maptype.c
@@ -0,0 +1,493 @@
+/* nbdkit
+ * Copyright (C) 2018 Red Hat Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * * Neither the name of Red Hat nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without
+ * specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+ * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+ * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <config.h>
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <inttypes.h>
+#include <string.h>
+#include <assert.h>
+
+#include <nbdkit-filter.h>
+
+#include "maptype.h"
+
+/* Produce additional debugging of this module.  Only useful for
+ * finding bugs in the module, so this should normally be disabled.
+ */
+#define MAPTYPE_DEBUG 0
+
+/* Notes on the implementation.
+ *
+ * Throughout the filter we use the following terminology:
+ *
+ * request / requested etc: The client requested range of bytes to
+ * read or update.
+ *
+ * plugin: The target after the client request is mapped.  This is
+ * what is passed along to the underlying plugin (or next filter in
+ * the chain).
+ *
+ * mappings: Single entries (lines) in the map file.  They are of the
+ * form (plugin, request), ie. the mapping is done backwards.
+ *
+ * interval: start-end or (start, length).
+ *
+ * Only one mapping can apply to each requested byte.  This fact is
+ * crucial as it allows us to store the mappings in a simple array
+ * with no overlapping intervals, and use an efficient binary search
+ * to map incoming requests to the plugin.
+ *
+ * When we read the map file we start with an empty array and add the
+ * intervals to it.  At all times we must maintain the invariant that
+ * no intervals in the array may overlap, and therefore we have to
+ * split existing intervals as required.  Earlier mappings are
+ * discarded where they overlap with later mappings.
+ */
+
+/* Compare entries by rq_start. */
+static int
+mapping_compare (const void *mv1, const void *mv2)
+{
+  const struct mapping *m1 = mv1;
+  const struct mapping *m2 = mv2;
+
+  if (m1->rq_start < m2->rq_start)
+    return -1;
+  else if (m1->rq_start > m2->rq_start)
+    return 1;
+  else
+    return 0;
+}
+
+/* Return true if two mappings overlap in the request range. */
+static int
+mappings_overlap (const struct mapping *m1, const struct mapping *m2)
+{
+  return m1->rq_end >= m2->rq_start && m1->rq_start <=
m2->rq_end;
+}
+
+void
+map_init (struct map *map)
+{
+  map->nr_map = 0;
+  map->map = NULL;
+}
+
+void
+map_free (struct map *map)
+{
+  if (!map) return;
+  free (map->map);
+  map_init (map);
+}
+
+/* Return the highest address in the map+1. */
+int64_t
+map_size (struct map *map)
+{
+  if (map->nr_map == 0)
+    return 0;
+  else
+    return map->map[map->nr_map-1].rq_end + 1;
+}
+
+/* Add a single new mapping at the end of the map.  Does NOT maintain
+ * the invariant, use insert_mapping instead.
+ */
+static int
+add_mapping (struct map *map, const struct mapping *mapping)
+{
+  struct mapping *new_map;
+
+  map->nr_map++;
+  new_map = realloc (map->map, map->nr_map * sizeof map->map[0]);
+  if (new_map == NULL) {
+    nbdkit_error ("realloc: %m");
+    return -1;
+  }
+  map->map = new_map;
+  map->map[map->nr_map-1] = *mapping;
+  return 0;
+}
+
+/* Insert a single new mapping into the map.  By splitting
+ * and discarding intervals, this maintains the invariant
+ * described above.
+ */
+static int
+insert_mapping (struct map *map, const struct mapping *new_mapping)
+{
+  size_t i;
+
+  /* Adjust existing mappings if they overlap with this mapping. */
+  for (i = 0; i < map->nr_map; ++i) {
+    if (mappings_overlap (&map->map[i], new_mapping)) {
+      /* The four cases are:
+       *
+       * existing         +---+
+       * new        +-------------------+
+       *                       => erase existing mapping
+       *
+       * existing  +-------------------+
+       * new            +---+
+       *                       => split existing mapping into two
+       *
+       * existing          +-----------+
+       * new            +-----+
+       *                       => adjust start of existing mapping
+       *
+       * existing  +-----------+
+       * new                +-----+
+       *                       => adjust end of existing mapping
+       */
+      if (map->map[i].rq_start >= new_mapping->rq_start &&
+          map->map[i].rq_end <= new_mapping->rq_end) {
+        /* Erase map[i]. */
+        memmove (&map->map[i], &map->map[i+1],
+                 (map->nr_map-i-1) * sizeof map->map[0]);
+        map->nr_map--;
+        i--;
+      }
+      else if (map->map[i].rq_start < new_mapping->rq_start &&
+               map->map[i].rq_end > new_mapping->rq_end) {
+        struct mapping second;
+        uint64_t offset;
+
+        /* Split map[i] by reducing map[i] and creating second mapping. */
+        second.lineno = map->map[i].lineno;
+        second.rq_start = new_mapping->rq_end+1;
+        second.rq_end = map->map[i].rq_end;
+        offset = new_mapping->rq_end+1 - map->map[i].rq_start;
+        second.plugin_start = map->map[i].plugin_start + offset;
+        if (add_mapping (map, &second) == -1)
+          return -1;
+        map->map[i].rq_end = new_mapping->rq_start-1;
+      }
+      else if (map->map[i].rq_start >= new_mapping->rq_start) {
+        uint64_t offset;
+
+        /* Adjust start of map[i]. */
+        offset = new_mapping->rq_end+1 - map->map[i].rq_start;
+        map->map[i].rq_start = new_mapping->rq_end+1;
+        map->map[i].plugin_start += offset;
+      }
+      else if (map->map[i].rq_end <= new_mapping->rq_end)
+        /* Adjust end of map[i]. */
+        map->map[i].rq_end = new_mapping->rq_start-1;
+      else
+        abort ();               /* Should never happen. */
+    }
+  }
+
+  /* Add new mapping at the end.  Note that the new mapping does not
+   * need to be adjusted.
+   */
+  return add_mapping (map, new_mapping);
+}
+
+/* Load the map file. */
+int
+map_load_from_file (const char *filename, int64_t plugin_size,
+                    struct map *map)
+{
+  /* Set of whitespace in the map file. */
+  static const char whitespace[] = " \t\n\r";
+
+  FILE *fp;
+  ssize_t r;
+  size_t len = 0;
+  char *line = NULL;
+  int lineno = 0;
+  size_t i;
+
+  fp = fopen (filename, "r");
+  if (fp == NULL) {
+    nbdkit_error ("open: %s: %m", filename);
+    return -1;
+  }
+  while ((r = getline (&line, &len, fp)) != -1) {
+    char *p, *q, *saveptr;
+    size_t n;
+    int64_t i;
+    int64_t length;         /* signed because -1 means end of input */
+    struct mapping mapping;
+
+    lineno++;
+    mapping.lineno = lineno;
+
+    /* Remove anything after # (comment) character. */
+    p = strchr (line, '#');
+    if (p)
+      *p = '\0';
+
+    /* Trim whitespace at beginning of the line. */
+    n = strspn (line, whitespace);
+    if (n > 0)
+      memmove (line, &line[n], strlen (&line[n]));
+
+    /* Trim whitespace at end of the line (including \n and \r). */
+    n = strlen (line);
+    while (n > 0) {
+      if (strspn (&line[n-1], whitespace) == 0)
+        break;
+      line[n-1] = '\0';
+      n--;
+    }
+
+    /* Ignore blank lines. */
+    if (n == 0)
+      continue;
+
+    /* First field.
+     * Expecting: "start,length" or "start-end" or "start-"
or "start".
+     */
+    p = strtok_r (line, whitespace, &saveptr);
+    if (p == NULL) {
+      /* AFAIK this can never happen. */
+      nbdkit_error ("%s:%d: could not read token", filename, lineno);
+      goto err;
+    }
+    if ((q = strchr (p, ',')) != NULL) { /* start,length */
+      *q = '\0'; q++;
+      i = nbdkit_parse_size (p);
+      if (i == -1)
+        goto err;
+      mapping.plugin_start = i;
+      i = nbdkit_parse_size (q);
+      if (i == -1)
+        goto err;
+      length = i;
+    }
+    else if ((q = strchr (p, '-')) != NULL) { /* start-end or start- */
+      *q = '\0'; q++;
+      i = nbdkit_parse_size (p);
+      if (i == -1)
+        goto err;
+      mapping.plugin_start = i;
+      if (*q == '\0')
+        length = -1;
+      else {
+        i = nbdkit_parse_size (q);
+        if (i == -1)
+          goto err;
+        /* Note: 100-99 is allowed (means zero length).  However the
+         * length must not be negative.
+         */
+        if (i < mapping.plugin_start-1) {
+          nbdkit_error ("%s:%d: length < 0", filename, lineno);
+          goto err;
+        }
+        length = i - mapping.plugin_start + 1;
+      }
+    }
+    else {                      /* start */
+      i = nbdkit_parse_size (p);
+      if (i == -1)
+        goto err;
+      mapping.plugin_start = i;
+      length = -1;
+    }
+
+    /* length == -1 means to the end of the plugin.  Calculate that. */
+    if (length == -1)
+      length = plugin_size - mapping.plugin_start;
+
+    /* A zero-length mapping isn't an error, but can be ignored immediately. */
+    if (length == 0)
+      continue;
+
+    /* Second field.  Expecting a single offset. */
+    p = strtok_r (NULL, whitespace, &saveptr);
+    i = nbdkit_parse_size (p);
+    if (i == -1)
+      goto err;
+    mapping.rq_start = i;
+
+    /* Calculate the end of the output region. */
+    mapping.rq_end = mapping.rq_start + length - 1;
+
+    /* We just ignore everything on the line after the second field.
+     * But don't put anything there, we might use this for something
+     * in future.
+     */
+
+    /* Debug the line as it was read. */
+    nbdkit_debug ("map: %s:%d: "
+                  "plugin.start=%" PRIu64 ", plugin.length=%" PRIi64
", "
+                  "request.start=%" PRIu64 ", request.end=%" PRIu64,
+                  filename, lineno,
+                  mapping.plugin_start, length,
+                  mapping.rq_start, mapping.rq_end);
+
+    /* Insert into the map. */
+    if (insert_mapping (map, &mapping) == -1)
+      goto err;
+  }
+
+  fclose (fp);
+  free (line);
+
+  /* The map maintains an invariant that no intervals are overlapping.
+   * However it is not yet sorted which we need for efficient lookups
+   * (using bsearch), so do that now.
+   */
+  if (map->nr_map > 0)
+    qsort (map->map, map->nr_map, sizeof map->map[0], mapping_compare);
+
+  /* Check there are no overlapping mappings.  Because of the sort
+   * above we only need to check adjacent pairs so this is quite
+   * efficient and we can do it every time.
+   */
+  if (map->nr_map > 0)
+    for (i = 0; i < map->nr_map-1; ++i)
+      assert (!mappings_overlap (&map->map[i], &map->map[i+1]));
+
+  /* If debugging print the final map. */
+  for (i = 0; i < map->nr_map; ++i)
+    nbdkit_debug ("map: map[%zu] = [%" PRIu64 "-%" PRIu64
":"
+                  "%" PRIu64 "] (from %s:%d)",
+                  i, map->map[i].rq_start, map->map[i].rq_end,
+                  map->map[i].plugin_start, filename, map->map[i].lineno);
+
+  return 0;
+
+ err:
+  fclose (fp);
+  free (line);
+  map_free (map);
+  return -1;
+}
+
+/* Look up a single address in the map.
+ *
+ * If mapped, returns the mapping index (in map[]).  In this case
+ * *is_mapped == true.
+ *
+ * If unmapped, returns the mapping index of the next mapped area
+ * (which can be >= nr_map if there are no more mappings).  In this
+ * case *is_mapped == false.
+ *
+ * Note this only works because of the invariant that mappings are not
+ * allowed to overlap.  See description at top of file.
+ */
+size_t
+map_lookup (const struct map *map, uint64_t p, int *is_mapped)
+{
+  size_t lo, hi, mid;
+
+  /* Deal with the special case where the map is completely empty
+   * because it makes the rest of the code easier.
+   */
+  if (map->nr_map == 0) {
+    *is_mapped = 0;
+    return 0;
+  }
+
+  /* Unmapped, before the first interval? */
+  if (p < map->map[0].rq_start) {
+    *is_mapped = 0;
+    return 0;
+  }
+
+  /* Do a binary search to find the mapping. */
+  lo = 0;
+  hi = map->nr_map;
+  while (lo < hi) {
+    mid = (lo + hi) / 2;
+    if (map->map[mid].rq_start <= p && p <= map->map[mid].rq_end)
+      lo = hi = mid; /* terminates loop */
+    else if (p < map->map[mid].rq_start && hi != mid)
+      hi = mid;
+    else if (map->map[mid].rq_end < p && lo != mid)
+      lo = mid;
+    else
+      lo = hi = mid; /* terminates loop */
+  }
+
+  *is_mapped = p <= map->map[lo].rq_end;
+  return lo;
+}
+
+/* Iterate over the map. */
+int
+map_iter (const struct map *map,
+          uint32_t count, uint64_t offs, void *data,
+          int (*mapped_fn) (void *data, uint32_t count, uint64_t offs),
+          int (*unmapped_fn) (void *data, uint32_t count))
+{
+  size_t i;
+  int is_mapped;
+  size_t len;
+
+  while (count > 0) {
+    i = map_lookup (map, offs, &is_mapped);
+
+    if (MAPTYPE_DEBUG)
+      nbdkit_debug ("map: iter: "
+                    "offset %" PRIu64 " %s map[%zu] = "
+                    "[%" PRIu64 "-%" PRIu64 ":%" PRIu64
"]",
+                    offs, is_mapped ? "mapped to" : "unmapped below",
i,
+                    map->map[i].rq_start, map->map[i].rq_end,
+                    map->map[i].plugin_start);
+
+    if (is_mapped) {
+      len = map->map[i].rq_end - offs + 1;
+      if (mapped_fn (data,
+                     len < count ? len : count,
+                     map->map[i].plugin_start + offs
+                     - map->map[i].rq_start) == -1)
+        return -1;
+    }
+    else {
+      if (i < map->nr_map)
+        len = map->map[i].rq_start - offs;
+      else
+        len = count;            /* No more mappings above this one. */
+      if (unmapped_fn (data,
+                       len < count ? len : count) == -1)
+        return -1;
+    }
+
+    if (len < count) {
+      offs += len;
+      count -= len;
+    }
+    else
+      count = 0;                /* Fulfilled whole request. */
+  }
+
+  return 0;
+}
diff --git a/filters/map/maptype.h b/filters/map/maptype.h
new file mode 100644
index 0000000..b24e572
--- /dev/null
+++ b/filters/map/maptype.h
@@ -0,0 +1,76 @@
+/* nbdkit
+ * Copyright (C) 2018 Red Hat Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * * Neither the name of Red Hat nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without
+ * specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+ * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+ * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#ifndef NBDKIT_MAPTYPE_H
+#define NBDKIT_MAPTYPE_H
+
+struct mapping {
+  /* The start and end (inclusive) of the requested interval. */
+  uint64_t rq_start, rq_end;
+
+  /* The interval this maps to in the plugin.  end/length is implied. */
+  uint64_t plugin_start;
+
+  /* The source line for the mapping. */
+  int lineno;
+};
+
+struct map {
+  struct mapping *map;          /* List of mappings. */
+  size_t nr_map;                /* Number of entries in map array. */
+};
+
+/* Initialize the map structure. */
+extern void map_init (struct map *map);
+
+/* This only frees the map->map array. */
+extern void map_free (struct map *map);
+
+/* Return the highest address in the map + 1. */
+extern int64_t map_size (struct map *map);
+
+/* Load the map from a file, constructing the map structure. */
+extern int map_load_from_file (const char *filename, int64_t plugin_size,
+                               struct map *map);
+
+/* Lookup a single address in the map. */
+extern size_t map_lookup (const struct map *map, uint64_t p, int *is_mapped);
+
+/* Iterate over the map. */
+typedef int (*mapped_fn_t) (void *data, uint32_t count, uint64_t offs);
+typedef int (*unmapped_fn_t) (void *data, uint32_t count);
+extern int map_iter (const struct map *map,
+                     uint32_t count, uint64_t offs, void *data,
+                     mapped_fn_t mapped_fn, unmapped_fn_t unmapped_fn);
+
+#endif /* NBDKIT_MAPTYPE_H */
diff --git a/filters/map/nbdkit-map-filter.pod b/filters/map/nbdkit-map-filter.pod
new file mode 100644
index 0000000..05c6b90
--- /dev/null
+++ b/filters/map/nbdkit-map-filter.pod
@@ -0,0 +1,173 @@
+=head1 NAME
+
+nbdkit-map-filter - nbdkit map filter
+
+=head1 SYNOPSIS
+
+ nbdkit --filter=map plugin map=FILENAME [plugin-args...]
+
+=head1 DESCRIPTION
+
+C<nbdkit-map-filter> is a filter that can serve an arbitrary map of
+regions of the underlying plugin.
+
+It is driven by a map file that contains a list of regions from the
+plugin and where they should be served in the output.
+
+For example this map would divide the plugin data into two 16K halves
+and swap them over:
+
+ # map file
+ 0,16K   16K   # aaaaa
+ 16K,16K 0     # bbbbb
+
+When visualised, this map file looks like:
+
+                   ┌──────────────┬──────────────┬─── ─ ─ ─
+ Plugin serves ... │ aaaaaaaaaaaa │ bbbbbbbbbbbb │ (extra data)
+                   │    16K       │    16K       │
+                   └──────────────┴──────────────┴─── ─ ─ ─
+                         │              │
+ Filter                  │    ┌─────────┘
+ transforms ...          └──────────────┐
+                              │         │
+                   ┌──────────▼───┬─────▼────────┐
+ Client sees ...   │ bbbbbbbbbbbb │ aaaaaaaaaaaa │
+                   └──────────────┴──────────────┘
+
+This is how to simulate L<nbdkit-offset-filter(1)> C<offset> and
+C<range> parameters:
+
+ # offset,range
+ 1M,32M         0
+
+                   ┌─────┬─────────────────────┬─── ─ ─ ─
+ Plugin serves ... │     │ ccccccccccccccccccc │ (extra data)
+                   │ 1M  │        32M          │
+                   └─────┴─────────────────────┴─── ─ ─ ─
+ Filter                            │
+ transforms ...              ┌─────┘
+                             │
+                   ┌─────────▼───────────┐
+ Client sees ...   │ ccccccccccccccccccc │
+                   └─────────────────────┘
+
+You can also do obscure things like duplicating regions of the source:
+
+ # map file
+ 0,16K  0
+ 0,16K  16K
+
+                   ┌──────────────┬─── ─ ─ ─
+ Plugin serves ... │ aaaaaaaaaaaa │ (extra data)
+                   │    16K       │
+                   └──────────────┴─── ─ ─ ─
+ Filter                  │
+ transforms ...          └───┬──────────┐
+                             │          │
+                   ┌─────────▼────┬─────▼────────┐
+ Client sees ...   │ aaaaaaaaaaaa │ aaaaaaaaaaaa │
+                   └──────────────┴──────────────┘
+
+=head2 Map file format
+
+The map file describes how regions from the plugin are mapped to the
+output.  There is one line per mapping.  Blank lines are ignored.
+C<#> indicates a comment.
+
+Each line (mapping) has one of the following forms:
+
+ start,length  offset    # see "start,length" below
+ start-end     offset    # see "start-end" below
+ start-        offset    # see "start to end of plugin" below
+ start         offset    # see "start to end of plugin" below
+
+=head2 C<start,length>
+
+ start,length  offset
+
+means that the source region starting at byte C<start>, for C<length>
+bytes, is mapped to C<offset> to C<offset+length-1> in the output.
+
+For example:
+
+ 16K,8K        0
+
+maps the 8K-sized region starting at 16K in the source to the
+beginning (ie. from offset 0) of the output.
+
+=head2 C<start-end>
+
+ start-end     offset
+
+means that the source region starting at byte C<start> through to byte
+C<end> (inclusive) is mapped to C<offset> through to
+C<offset+(end-start)> in the output.
+
+For example:
+
+ 1024-2047     2048
+
+maps the region starting at byte 1024 and ending at byte 2047
+(inclusive) to bytes 2048-3071 in the output.
+
+=head2 C<start> to end of plugin
+
+ start-        offset
+ start         offset
+
+If the C<end> field is omitted it means "up to the end of the
+underlying plugin".
+
+=head2 Size modifiers
+
+You can use the usual power-of-2 size modifiers like C<K>, C<M> etc.
+
+=head2 Overlapping mappings
+
+If there are multiple mappings in the map file that may apply to a
+particular byte of the filter output then it is the last one in the
+file which applies.
+
+=head2 Virtual size
+
+The virtual size of the filter output finishes at the last byte of the
+final mapped region.  Note this is usually different from the size of
+the underlying plugin.
+
+=head2 Unmapped regions
+
+Any unmapped region (followed by a mapped region and therefore not
+beyond the virtual size) reads as zero and returns an error if
+written.
+
+Any mapping or part of a mapping where the source region refers beyond
+the end of the underlying plugin reads as zero and returns an error if
+written.
+
+=head1 PARAMETERS
+
+=over 4
+
+=item B<map=FILENAME>
+
+Specify the map filename (required).  See L</Map file format> above.
+
+=back
+
+=head1 SEE ALSO
+
+L<nbdkit(1)>,
+L<nbdkit-file-plugin(1)>,
+L<nbdkit-filter(3)>,
+L<nbdkit-offset-filter(1)>,
+L<nbdkit-partition-filter(1)>,
+L<nbdkit-truncate-filter(1)>.
+
+=head1 AUTHORS
+
+Richard W.M. Jones
+
+=head1 COPYRIGHT
+
+Copyright (C) 2018 Red Hat Inc.
diff --git a/filters/offset/nbdkit-offset-filter.pod
b/filters/offset/nbdkit-offset-filter.pod
index 6d8f9be..96f9a13 100644
--- a/filters/offset/nbdkit-offset-filter.pod
+++ b/filters/offset/nbdkit-offset-filter.pod
@@ -67,6 +67,7 @@ You can then serve the partition only using:
 L<nbdkit(1)>,
 L<nbdkit-file-plugin(1)>,
 L<nbdkit-filter(3)>,
+L<nbdkit-map-filter(1)>,
 L<nbdkit-partition-filter(1)>,
 L<nbdkit-truncate-filter(1)>.
 
diff --git a/filters/partition/nbdkit-partition-filter.pod
b/filters/partition/nbdkit-partition-filter.pod
index 71a7a3a..8d9aabb 100644
--- a/filters/partition/nbdkit-partition-filter.pod
+++ b/filters/partition/nbdkit-partition-filter.pod
@@ -45,6 +45,7 @@ image).  To serve the first partition only use:
 L<nbdkit(1)>,
 L<nbdkit-file-plugin(1)>,
 L<nbdkit-filter(3)>,
+L<nbdkit-map-filter(1)>,
 L<nbdkit-offset-filter(1)>,
 L<nbdkit-truncate-filter(1)>,
 L<parted(8)>.
diff --git a/plugins/pattern/nbdkit-pattern-plugin.pod
b/plugins/pattern/nbdkit-pattern-plugin.pod
index d2bcd4d..d37d661 100644
--- a/plugins/pattern/nbdkit-pattern-plugin.pod
+++ b/plugins/pattern/nbdkit-pattern-plugin.pod
@@ -58,6 +58,7 @@ This parameter is required.
 
 L<nbdkit(1)>,
 L<nbdkit-plugin(3)>,
+L<nbdkit-map-filter(1)>,
 L<nbdkit-null-plugin(1)>,
 L<nbdkit-offset-filter(1)>,
 L<nbdkit-random-plugin(1)>,
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 4c602d7..2306506 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -58,6 +58,7 @@ EXTRA_DIST = \
 	test-ip.sh \
 	test-log.sh \
 	test.lua \
+	test-map-empty.sh \
 	test-nozero.sh \
 	test_ocaml_plugin.ml \
 	test-ocaml.c \
@@ -547,6 +548,9 @@ TESTS += test-fua.sh
 # log filter test.
 TESTS += test-log.sh
 
+# map filter test.
+TESTS += test-map-empty.sh
+
 # nozero filter test.
 TESTS += test-nozero.sh
 
diff --git a/tests/test-map-empty.sh b/tests/test-map-empty.sh
new file mode 100755
index 0000000..3789234
--- /dev/null
+++ b/tests/test-map-empty.sh
@@ -0,0 +1,85 @@
+#!/bin/bash -
+# nbdkit
+# Copyright (C) 2018 Red Hat Inc.
+# All rights reserved.
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions are
+# met:
+#
+# * Redistributions of source code must retain the above copyright
+# notice, this list of conditions and the following disclaimer.
+#
+# * Redistributions in binary form must reproduce the above copyright
+# notice, this list of conditions and the following disclaimer in the
+# documentation and/or other materials provided with the distribution.
+#
+# * Neither the name of Red Hat nor the names of its contributors may be
+# used to endorse or promote products derived from this software without
+# specific prior written permission.
+#
+# THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND
+# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+# THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+# PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
+# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+# USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+# SUCH DAMAGE.
+
+# Test the map filter with an empty map file.
+
+set -e
+
+files="map-empty.out map-empty.pid map-empty.sock"
+rm -f $files
+
+# Test that qemu-img works
+if ! qemu-img --version >/dev/null; then
+    echo "$0: missing or broken qemu-img"
+    exit 77
+fi
+
+# Run nbdkit with pattern plugin and an empty map file on top.
+nbdkit -P map-empty.pid -U map-empty.sock \
+       --filter=map pattern size=10M map=/dev/null
+
+# We may have to wait a short time for the pid file to appear.
+for i in `seq 1 10`; do
+    if test -f map-empty.pid; then
+        break
+    fi
+    sleep 1
+done
+if ! test -f map-empty.pid; then
+    echo "$0: PID file was not created"
+    exit 1
+fi
+
+pid="$(cat map-empty.pid)"
+
+# Kill the nbdkit process on exit.
+cleanup ()
+{
+    status=$?
+
+    kill $pid
+    rm -f $files
+
+    exit $status
+}
+trap cleanup INT QUIT TERM EXIT ERR
+
+LANG=C qemu-img info 'nbd+unix://?socket=map-empty.sock' |
+    grep "^virtual size:" > map-empty.out
+if [ "$(cat map-empty.out)" != "virtual size: 0 (0 bytes)" ]; then
+    echo "$0: unexpected output:"
+    cat map-empty.out
+    exit 1
+fi
+
+# The cleanup() function is called implicitly on exit.
-- 
2.18.0


    

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

[Libguestfs] [PATCH nbdkit 3/4] Add map filter.