[Libguestfs] [PATCH nbdkit 3/4] Add map filter.
Richard W.M. Jones
rjones at redhat.com
Tue Jul 31 19:55:51 UTC 2018
Serve an arbitrary map of regions of the underlying plugin.
---
common-rules.mk | 1 +
configure.ac | 1 +
filters/map/Makefile.am | 61 +++
filters/map/map.c | 256 +++++++++
filters/map/maptype.c | 493 ++++++++++++++++++
filters/map/maptype.h | 76 +++
filters/map/nbdkit-map-filter.pod | 173 ++++++
filters/offset/nbdkit-offset-filter.pod | 1 +
filters/partition/nbdkit-partition-filter.pod | 1 +
plugins/pattern/nbdkit-pattern-plugin.pod | 1 +
tests/Makefile.am | 4 +
tests/test-map-empty.sh | 85 +++
12 files changed, 1153 insertions(+)
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
More information about the Libguestfs
mailing list