[Libguestfs] [PATCH nbdkit 3/4] Add map filter.
Eric Blake
eblake at redhat.com
Tue Jul 31 22:22:32 UTC 2018
On 07/31/2018 02:55 PM, Richard W.M. Jones wrote:
> Serve an arbitrary map of regions of the underlying plugin.
> ---
> +#define map_config_help \
> + "map=<FILENAME> (required) Map file."
Maybe worth a "see man page for format"?
I have not closely read the code; at this point, it is just a quick
review on the documentation/comments.
> +/* 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
Maybe: Only the final applicable mapping can apply to each requested byte?
> + * 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.
since this paragraph is all about maintaining the invariant in favor of
each subsequent mapping, and thus the file format itself permits
overlaps for shorthands for special-casing subregions.
Is there a syntax for explicitly mentioning a subset is unmapped even
after a larger mapping is applied first (perhaps useful for redacting a
portion of a disk containing sensitive information)?
> +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
should that be 'two/three'?
> + *
> + * existing +-----------+
> + * new +-----+
> + * => adjust start of existing mapping
or is it really a case that you first split into two, then adjust one of
the two
> + *
> + * 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 │
> + └──────────────┴──────────────┘
> +
When duplicating things, do we want to document that a single
transaction is carried out in the order seen by the client (where
aliases at later bytes overwrite any data written into the earlier alias
in a long transaction), or do we want to put in hedge wording that (in
the future) a request might be split into smaller regions that get
operated on in parallel (thereby making the end contents indeterminate
when writing to two aliases of the same byte in one transaction)?
> +=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.
Since you already support '2k', '2m' and such as shorthands for the
start, is it worth creating a convenient shorthand for expressing '3M-1'
for an end rather than having to write out 3145727?
> +
> +=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.
Is there a syntax for explicitly adding an unmapped tail, to make the
filter's output longer than the underlying plugin's size?
> +
> +=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.
Ah, so using the '(start,length) offset' entry does allow for an
explicit unmapped tail at the end of the underlying plugin.
--
Eric Blake, Principal Software Engineer
Red Hat, Inc. +1-919-301-3266
Virtualization: qemu.org | libvirt.org
More information about the Libguestfs
mailing list