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

Serve an arbitrary map of regions of the underlying plugin. ---

+#define map_config_help \ + "map=<FILENAME> (required) Map file."

+/* 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.

+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 + */

+++ 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 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.