Richard W.M. Jones
2023-May-17 10:06 UTC
[Libguestfs] [PATCH nbdkit v2 6/6] New filter: evil
This filter adds random data corruption when reading from the
underlying plugin.
---
filters/error/nbdkit-error-filter.pod | 4 +
filters/evil/nbdkit-evil-filter.pod | 167 ++++++++++
configure.ac | 2 +
filters/evil/Makefile.am | 77 +++++
tests/Makefile.am | 18 ++
filters/evil/evil.c | 422 ++++++++++++++++++++++++++
tests/test-evil-cosmic.sh | 77 +++++
tests/test-evil-large-p.sh | 55 ++++
tests/test-evil-small-p.sh | 57 ++++
tests/test-evil-stuck-high-bits.sh | 91 ++++++
tests/test-evil-stuck-low-bits.sh | 84 +++++
tests/test-evil-stuck-wires.sh | 85 ++++++
12 files changed, 1139 insertions(+)
diff --git a/filters/error/nbdkit-error-filter.pod
b/filters/error/nbdkit-error-filter.pod
index 49f21d10a..91af7f713 100644
--- a/filters/error/nbdkit-error-filter.pod
+++ b/filters/error/nbdkit-error-filter.pod
@@ -25,6 +25,9 @@ All parameters are optional, but you should usually specify
one of the
C<error-rate> or C<error-*-rate> parameters,
B<otherwise this filter will do nothing>.
+L<nbdkit-evil-filter(1)> is a related filter that injects data
+corruption instead of errors.
+
=head1 EXAMPLES
Inject a low rate of errors randomly into the connection:
@@ -162,6 +165,7 @@ C<nbdkit-error-filter> first appeared in nbdkit 1.6.
=head1 SEE ALSO
L<nbdkit(1)>,
+L<nbdkit-evil-filter(1)>,
L<nbdkit-file-plugin(1)>,
L<nbdkit-full-plugin(1)>,
L<nbdkit-retry-filter(1)>,
diff --git a/filters/evil/nbdkit-evil-filter.pod
b/filters/evil/nbdkit-evil-filter.pod
new file mode 100644
index 000000000..ff4010d33
--- /dev/null
+++ b/filters/evil/nbdkit-evil-filter.pod
@@ -0,0 +1,167 @@
+=head1 NAME
+
+nbdkit-evil-filter - add random data corruption to reads
+
+=head1 SYNOPSIS
+
+ nbdkit --filter=evil PLUGIN [PLUGIN-ARGS...]
+ evil=[cosmic-rays|stuck-bits|stuck-wires]
+ [evil-probability=PROB] [evil-stuck-probability=PROB]
+ [evil-seed=SEED]
+
+=head1 DESCRIPTION
+
+nbdkit-evil-filter is a Byzantine filter for L<nbdkit(1)> that
+randomly corrupts data when reading from the underlying plugin. This
+can be used for testing filesystem checksums. Note that it does not
+change write operations, so the underlying plugin contains the correct
+data.
+
+L<nbdkit-error-filter(1)> is a related filter that injects hard errors
+into the NBD protocol.
+
+This filter has several modes, controlled using the C<evil=...>
+parameter. These are:
+
+=over 4
+
+=item C<evil=cosmic-rays>
+
+Bits are flipped at random when reading data. The probability that a
+bit is flipped is controlled using the C<evil-probability> parameter,
+defaulting to 1e-8 (on average 1 in every 100 million bits read is
+flipped).
+
+=item C<evil=stuck-bits>
+
+This is the default mode.
+
+Fixed bits in the backing file are stuck randomly high or low. The
+C<evil-probability> parameter controls the expected probability that a
+particular bit is stuck, defaulting in this mode to 1e-8 (1 in 100
+million). C<evil-stuck-probability> controls the probability that a
+stuck bit is read as its stuck value or its correct value, defaulting
+to 100% (always read as a stuck bit).
+
+=item C<evil=stuck-wires>
+
+This is similar to C<stuck-bits> but instead of simulating bad backing
+data, it simulates stuck wires along the data path (eg. in a
+register). The difference is that when reading, the stuck bit always
+happens at the same position in the packet of data being read,
+regardless of where on the underlying disk it is being read from.
+C<evil-probability> and controls the probability of a stuck wire,
+defaulting in this mode to 1e-6 (1 in 1 million).
+C<evil-stuck-probability> controls the probability that a stuck bit is
+read as its stuck value or its correct value, defaulting to 100%
+(always read as a stuck bit).
+
+=back
+
+=head1 EXAMPLES
+
+Add some stuck bits to the backing file at random:
+
+ nbdkit --filter=evil file disk.img
+
+Cosmic rays will flip (on average) one in every 100 million bits
+copied from the backing file over NBD:
+
+ nbdkit --filter=evil file disk.img evil=cosmic-rays \
+ --run 'nbdcopy $uri output.img'
+
+=head1 NOTES
+
+=head2 Extents
+
+Plugins can be sparse. This filter only corrupts bits in non-sparse
+parts of the backing disk and it leaves sparse regions unchanged
+(which is realistic behaviour). If you wish to use this filter to
+corrupt sparse regions, then combine this filter with
+L<nbdkit-noextents-filter(1)>. For example:
+
+ nbdkit --filter=evil --filter=noextents memory 1G
+
+=head2 Probability limited to [ 1e-12 .. 1/8 ]
+
+The current implementation limits probabilities to the range
+S<[ 1e-12 .. 1/8 ]>. Values below this range are treated the same as
+0%. Values above this range are treated the same as 100%.
+
+=head1 PARAMETERS
+
+=over 4
+
+=item B<evil=cosmic-rays>
+
+=item B<evil=stuck-bits>
+
+=item B<evil=stuck-wires>
+
+Select the mode of evil. See the L</DESCRIPTION> above. The default
+is C<stuck-bits>.
+
+=item B<evil-probability=>N
+
+=item B<evil-probability=>NB<:>M
+
+=item B<evil-probability=>NB<%>
+
+Set the probability for the mode. You can either use a floating point
+number between 0 and 1, eg. C<evil-probability=0.001> or
+C<evil-probability=1e-6>. Or you can write it as N in M, eg.
+C<evil-probability=1:1000000> or C<evil-probability=3.33:100000>.
Or
+you can write this as a percentage, eg. C<evil-probability=1%>.
+
+The default probability depends on the mode.
+
+=item B<evil-seed=>SEED
+
+To make runs repeatable, use this to set a seed for the random number
+generator. The default is to choose a seed at random.
+
+=item B<evil-stuck-probability=>N
+
+=item B<evil-stuck-probability=>NB<:>M
+
+=item B<evil-stuck-probability=>NB<%>
+
+For the "stuck-*" modes, the probability that when reading a stuck
bit
+you will read the stuck bit or the correct value. This defaults to 1
+(ie. 100%) which means the bit is always stuck. Setting it to 0.5 for
+example will mean that half the time the bit appears stuck and half
+the time you see the correct value.
+
+=back
+
+=head1 FILES
+
+=over 4
+
+=item F<$filterdir/nbdkit-evil-filter.so>
+
+The filter.
+
+Use C<nbdkit --dump-config> to find the location of C<$filterdir>.
+
+=back
+
+=head1 VERSION
+
+C<nbdkit-pause-filter> first appeared in nbdkit 1.36.
+
+=head1 SEE ALSO
+
+L<nbdkit(1)>,
+L<nbdkit-filter(3)>,
+L<nbdkit-delay-filter(1)>,
+L<nbdkit-noextents-filter(1)>,
+L<nbdkit-error-filter(1)>.
+
+=head1 AUTHORS
+
+Richard W.M. Jones
+
+=head1 COPYRIGHT
+
+Copyright Red Hat
diff --git a/configure.ac b/configure.ac
index 310de7ac1..18431958a 100644
--- a/configure.ac
+++ b/configure.ac
@@ -124,6 +124,7 @@ filters="\
exportname \
ext2 \
extentlist \
+ evil \
fua \
gzip \
ip \
@@ -1534,6 +1535,7 @@ AC_CONFIG_FILES([Makefile
filters/exportname/Makefile
filters/ext2/Makefile
filters/extentlist/Makefile
+ filters/evil/Makefile
filters/fua/Makefile
filters/gzip/Makefile
filters/ip/Makefile
diff --git a/filters/evil/Makefile.am b/filters/evil/Makefile.am
new file mode 100644
index 000000000..ac6337428
--- /dev/null
+++ b/filters/evil/Makefile.am
@@ -0,0 +1,77 @@
+# nbdkit
+# Copyright Red Hat
+#
+# 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-evil-filter.pod
+
+# Relies on a Unix domain socket.
+if !IS_WINDOWS
+
+filter_LTLIBRARIES = nbdkit-evil-filter.la
+
+nbdkit_evil_filter_la_SOURCES = \
+ evil.c \
+ $(top_srcdir)/include/nbdkit-filter.h \
+ $(NULL)
+
+nbdkit_evil_filter_la_CPPFLAGS = \
+ -I$(top_srcdir)/include \
+ -I$(top_builddir)/include \
+ -I$(top_srcdir)/common/include \
+ -I$(top_srcdir)/common/utils \
+ $(NULL)
+nbdkit_evil_filter_la_CFLAGS = $(WARNINGS_CFLAGS)
+nbdkit_evil_filter_la_LIBADD = \
+ $(top_builddir)/common/utils/libutils.la \
+ $(IMPORT_LIBRARY_ON_WINDOWS) \
+ $(NULL)
+nbdkit_evil_filter_la_LDFLAGS = \
+ -module -avoid-version -shared $(NO_UNDEFINED_ON_WINDOWS) \
+ $(NULL)
+if USE_LINKER_SCRIPT
+nbdkit_evil_filter_la_LDFLAGS += \
+ -Wl,--version-script=$(top_srcdir)/filters/filters.syms
+endif
+
+if HAVE_POD
+
+man_MANS = nbdkit-evil-filter.1
+CLEANFILES += $(man_MANS)
+
+nbdkit-evil-filter.1: nbdkit-evil-filter.pod \
+ $(top_builddir)/podwrapper.pl
+ $(PODWRAPPER) --section=1 --man $@ \
+ --html $(top_builddir)/html/$@.html \
+ $<
+
+endif HAVE_POD
+endif !IS_WINDOWS
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 3ae13d660..9233c371e 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -1598,6 +1598,24 @@ EXTRA_DIST += \
test-error-triggered.sh \
$(NULL)
+# evil filter test.
+TESTS += \
+ test-evil-cosmic.sh \
+ test-evil-large-p.sh \
+ test-evil-small-p.sh \
+ test-evil-stuck-high-bits.sh \
+ test-evil-stuck-low-bits.sh \
+ test-evil-stuck-wires.sh \
+ $(NULL)
+EXTRA_DIST += \
+ test-evil-cosmic.sh \
+ test-evil-large-p.sh \
+ test-evil-small-p.sh \
+ test-evil-stuck-high-bits.sh \
+ test-evil-stuck-low-bits.sh \
+ test-evil-stuck-wires.sh \
+ $(NULL)
+
# exitlast filter test.
TESTS += test-exitlast.sh
EXTRA_DIST += test-exitlast.sh
diff --git a/filters/evil/evil.c b/filters/evil/evil.c
new file mode 100644
index 000000000..a6e0a9ed2
--- /dev/null
+++ b/filters/evil/evil.c
@@ -0,0 +1,422 @@
+/* nbdkit
+ * Copyright Red Hat
+ *
+ * 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 <stdbool.h>
+#include <stdint.h>
+#include <inttypes.h>
+#include <string.h>
+#include <time.h>
+#include <assert.h>
+
+#include <nbdkit-filter.h>
+
+#include "minmax.h"
+#include "ispowerof2.h"
+#include "random.h"
+
+enum mode {
+ COSMIC_RAYS,
+ STUCK_BITS,
+ STUCK_WIRES,
+};
+static const char *evil_mode_to_string (enum mode);
+
+static enum mode evil_mode = STUCK_BITS;
+static double evil_probability = -1; /* default depends on mode */
+static double evil_stuck_probability = 1.0;
+static uint32_t evil_seed;
+
+/* Probabilities < ? are treated as zero to avoid both divide by zero
+ * problems and potentially exploding values in calculations.
+ */
+#define EPSILON 1e-12
+
+/* Probabilities > MAXP are treated as 100%. This is because our
+ * algorithm below can corrupt at most 1 bit per byte and doesn't make
+ * progress otherwise.
+ */
+#define MAXP (1.0/8.0)
+
+static void
+evil_load (void)
+{
+ evil_seed = time (NULL);
+}
+
+static int
+evil_config (nbdkit_next_config *next, nbdkit_backend *nxdata,
+ const char *key, const char *value)
+{
+ if (strcmp (key, "evil") == 0 || strcmp (key,
"evil-mode") == 0) {
+ if (strcmp (value, "cosmic-rays") == 0 ||
+ strcmp (value, "cosmic") == 0) {
+ evil_mode = COSMIC_RAYS;
+ return 0;
+ }
+ else if (strcmp (value, "stuck-bits") == 0 ||
+ strcmp (value, "stuck-bit") == 0 ||
+ strcmp (value, "stuck") == 0) {
+ evil_mode = STUCK_BITS;
+ return 0;
+ }
+ else if (strcmp (value, "stuck-wires") == 0 ||
+ strcmp (value, "stuck-wire") == 0) {
+ evil_mode = STUCK_WIRES;
+ return 0;
+ }
+ else {
+ nbdkit_error ("evil: unknown mode: %s", value);
+ return -1;
+ }
+ }
+ else if (strcmp (key, "evil-probability") == 0) {
+ if (nbdkit_parse_probability ("evil-probability", value,
+ &evil_probability) == -1)
+ return -1;
+ if (evil_probability < 0 || evil_probability > 1) {
+ nbdkit_error ("%s: probability out of range, should be [0..1]",
key);
+ return -1;
+ }
+ return 0;
+ }
+ else if (strcmp (key, "evil-stuck-probability") == 0) {
+ if (nbdkit_parse_probability ("evil-stuck-probability", value,
+ &evil_stuck_probability) == -1)
+ return -1;
+ if (evil_stuck_probability < 0 || evil_stuck_probability > 1) {
+ nbdkit_error ("%s: probability out of range, should be [0..1]",
key);
+ return -1;
+ }
+ return 0;
+ }
+ else if (strcmp (key, "evil-seed") == 0) {
+ if (nbdkit_parse_uint32_t ("evil-seed", value, &evil_seed) ==
-1)
+ return -1;
+ return 0;
+ }
+ else
+ return next (nxdata, key, value);
+}
+
+static int
+evil_config_complete (nbdkit_next_config_complete *next,
+ nbdkit_backend *nxdata)
+{
+ if (evil_probability < 0) {
+ /* Choose default probability based on the chosen mode. */
+ switch (evil_mode) {
+ case COSMIC_RAYS:
+ case STUCK_BITS:
+ evil_probability = 1e-8;
+ break;
+ case STUCK_WIRES:
+ evil_probability = 1e-6;
+ }
+ }
+
+ return next (nxdata);
+}
+
+#define evil_config_help \
+ "evil=cosmic-rays|stuck-bits|stuck-wires\n" \
+ " Set the mode (default:
cosmic-rays).\n" \
+ "evil-probability=PROB Probability of flipped or stuck
bit.\n" \
+ "evil-seed=SEED Random number seed.\n" \
+ "evil-stuck-probability=PROB Probability of stuck bit being
stuck."
+
+/* This is the heart of the algorithm, the function which corrupts
+ * the buffer after reading it from the plugin.
+ *
+ * The observation is that if we have a block of (eg) size 10**6 bits
+ * and our probability of finding a corrupt bit is (eg) 1/10**4, then
+ * we expect approximately 100 bits in the block to be corrupted.
+ *
+ * For stuck bits we want the corrupted bits to be the same on each
+ * access, either relative to the backing disk (STUCK_BITS) or to the
+ * request (STUCK_WIRES).
+ *
+ * Instead of creating an expensive bitmap ahead of time covering the
+ * whole disk, we can use the random number generator with a fixed
+ * seed derived from the offset of the start of the block. We can
+ * then choose a random number uniformly in the range [0..2*(1/P)] (in
+ * the example [0..2*10**4]) as the distance to the next corrupt bit.
+ * We jump forwards, corrupt that bit, and repeat until we reach the
+ * end of the block.
+ *
+ * "Corrupted" in this case can mean flipped by cosmic rays or stuck,
+ * depending on the filter mode.
+ *
+ * On average this will choose the right number of bits in the block.
+ * (Although their distribution will be suboptimal. In a uniform
+ * distribution it should be possible for two corrupted bits to be
+ * greater than 2*(1/P) apart, but the above algorithm would not do
+ * this. In practice this probably doesn't matter.)
+ *
+ * Note that "block" != "buffer", especially in the
STUCK_BITS mode.
+ * We iterate over blocks as above, but only corrupt a bit when it
+ * happens to coincide with the buffer we have just read.
+ *
+ * We choose the block size adaptively so that at least 100 bits in
+ * the block will be corrupted. The block size must be a power of 2.
+ * The block size thus depends on the probability.
+ */
+enum corruption_type { FLIP, STUCK };
+
+static uint64_t block_size; /* in bytes */
+static struct random_state state; /* only used for cosmic-rays */
+
+static int
+evil_thread_model (void)
+{
+ switch (evil_mode) {
+ case COSMIC_RAYS:
+ /* Because cosmic-rays uses the global random state we need to
+ * tighten the thread model.
+ */
+ return NBDKIT_THREAD_MODEL_SERIALIZE_REQUESTS;
+
+ case STUCK_BITS:
+ case STUCK_WIRES:
+ return NBDKIT_THREAD_MODEL_PARALLEL;
+ }
+ abort ();
+}
+
+static int
+evil_get_ready (int thread_model)
+{
+ switch (evil_mode) {
+ case COSMIC_RAYS:
+ xsrandom ((uint64_t) evil_seed, &state);
+ break;
+
+ case STUCK_BITS:
+ case STUCK_WIRES:
+ ;
+ }
+
+ /* Choose the block size based on the probability, so that at least
+ * 100 bits are expected to be corrupted in the block. Block size
+ * must be a power of 2.
+ *
+ * Example: P = 1e-4
+ * => ideal block_size = 100 / 1e-4 = 1e6 (bits) = 1e6 / 8
(bytes)
+ * => next power of 2 block_size = 131072 = 2**17
+ * => expected bits per block = ~104
+ */
+ if (evil_probability < EPSILON || evil_probability > MAXP)
+ block_size = 1024*1024; /* unused so value doesn't matter */
+ else
+ block_size = next_power_of_2 ((uint64_t) (100. / evil_probability) / 8);
+
+ nbdkit_debug ("evil: mode: %s, P: %lg, seed: %" PRIu32,
+ evil_mode_to_string (evil_mode),
+ evil_probability, evil_seed);
+ nbdkit_debug ("evil: block_size: %" PRIu64 " (2**%d)",
+ block_size, log_2_bits (block_size));
+ nbdkit_debug ("evil: expected bits per block: %g",
+ 8 * block_size * evil_probability);
+
+ return 0;
+}
+
+static void corrupt_all_bits (uint8_t *buf, uint32_t count,
+ struct random_state *rs,
+ enum corruption_type ct);
+static uint8_t corrupt_one_bit (uint8_t byte, unsigned bit,
+ uint64_t rand, enum corruption_type ct);
+
+static void
+corrupt_buffer (uint8_t *buf, uint32_t count, uint64_t offset_in_block,
+ struct random_state *rs, enum corruption_type ct)
+{
+ /* No corruption, and avoids a divide by zero below. */
+ if (evil_probability < EPSILON) return;
+
+ /* 100% corruption, avoids lack of progress in the loop below. */
+ if (evil_probability > MAXP) {
+ corrupt_all_bits (buf, count, rs, ct);
+ return;
+ }
+
+ uint64_t offs, intvl, i, rand;
+ const uint64_t invp2 = (uint64_t) (2.0 / evil_probability);
+
+ assert ((offset_in_block & ~(block_size-1)) == 0);
+
+ /* Iterate over the whole block from the start. */
+ for (offs = 0; offs < offset_in_block + count; ) {
+ /* Choose the length of the interval to the next corrupted bit, by
+ * picking a random number in [0..2*(1/P)].
+ *
+ * Remember this is in bits!
+ */
+ intvl = xrandom (rs) % invp2;
+
+ /* Consume one more random state. We may or may not use this.
+ * But we need to always consume two random states per iteration
+ * to make the output predictable.
+ */
+ rand = xrandom (rs);
+
+ /* Adjust offs to that byte. */
+ offs += intvl / 8;
+
+ /* If we have gone past the end of buffer, stop. */
+ if (offs >= offset_in_block + count) break;
+
+ /* If the current offs lies within the buffer, corrupt a bit. */
+ if (offs >= offset_in_block) {
+ i = offs - offset_in_block;
+ assert (i < count);
+ buf[i] = corrupt_one_bit (buf[i], intvl & 7, rand, ct);
+ }
+ }
+}
+
+static void
+corrupt_all_bits (uint8_t *buf, uint32_t count,
+ struct random_state *rs, enum corruption_type ct)
+{
+ size_t i;
+ unsigned bit;
+ uint64_t rand;
+
+ /* This is used when MAXP < P <= 100%. We treat it the same as 100%
+ * and corrupt all bits.
+ */
+ for (i = 0; i < count; ++i) {
+ for (bit = 0; bit < 8; ++bit) {
+ rand = xrandom (rs);
+ buf[i] = corrupt_one_bit (buf[i], bit, rand, ct);
+ }
+ }
+}
+
+static uint8_t
+corrupt_one_bit (uint8_t byte, unsigned bit,
+ uint64_t rand, enum corruption_type ct)
+{
+ const unsigned mask = 1 << bit;
+
+ switch (ct) {
+ case FLIP:
+ byte ^= mask;
+ break;
+ case STUCK:
+ rand &= 0xffffffff;
+ if (evil_stuck_probability * 0x100000000 > rand) {
+ if (rand & 1) /* stuck high or low? */
+ byte |= mask;
+ else
+ byte &= ~mask;
+ }
+ }
+ return byte;
+}
+
+/* Read data. */
+static int
+evil_pread (nbdkit_next *next,
+ void *handle, void *buf, uint32_t count, uint64_t offset,
+ uint32_t flags, int *err)
+{
+ uint64_t seed, bstart, len;
+ struct random_state local_state;
+
+ if (next->pread (next, buf, count, offset, flags, err) == -1)
+ return -1;
+
+ switch (evil_mode) {
+ case COSMIC_RAYS:
+ /* Use the global random state because we want to flip bits at random. */
+ corrupt_buffer (buf, count, 0, &state, FLIP);
+ break;
+
+ case STUCK_BITS:
+ /* Split the request to align with blocks. */
+ bstart = offset & ~(block_size-1);
+ while (count > 0) {
+ /* Set the seed so we corrupt the same bits relative to the offset. */
+ seed = (int64_t) evil_seed + bstart;
+ xsrandom (seed, &local_state);
+ /* If the buffer straddles two blocks, shorten to just the part
+ * inside the first block.
+ */
+ len = MIN (count, bstart + block_size - offset);
+ corrupt_buffer (buf, len, offset - bstart, &local_state, STUCK);
+ bstart += block_size;
+ offset += len;
+ buf += len;
+ count -= len;
+ }
+ break;
+
+ case STUCK_WIRES:
+ /* Set the seed so we corrupt the same bits in every request. */
+ seed = (int64_t) evil_seed;
+ xsrandom (seed, &local_state);
+ corrupt_buffer (buf, count, 0, &local_state, STUCK);
+ break;
+ }
+
+ return 0;
+}
+
+static const char *
+evil_mode_to_string (enum mode mode)
+{
+ switch (mode) {
+ case COSMIC_RAYS: return "cosmic-rays";
+ case STUCK_BITS: return "stuck-bits";
+ case STUCK_WIRES: return "stuck-wires";
+ }
+ abort ();
+}
+
+static struct nbdkit_filter filter = {
+ .name = "evil",
+ .longname = "nbdkit evil filter",
+ .load = evil_load,
+ .config = evil_config,
+ .config_complete = evil_config_complete,
+ .config_help = evil_config_help,
+ .thread_model = evil_thread_model,
+ .get_ready = evil_get_ready,
+ .pread = evil_pread,
+};
+
+NBDKIT_REGISTER_FILTER (filter)
diff --git a/tests/test-evil-cosmic.sh b/tests/test-evil-cosmic.sh
new file mode 100755
index 000000000..2e5e6ab24
--- /dev/null
+++ b/tests/test-evil-cosmic.sh
@@ -0,0 +1,77 @@
+#!/usr/bin/env bash
+# nbdkit
+# Copyright Red Hat
+#
+# 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 evil filter with cosmic rays.
+
+source ./functions.sh
+set -e
+set -x
+
+requires_plugin null
+requires_filter evil
+requires_filter noextents
+requires nbdcopy --version
+requires $PYTHON --version
+
+f="test-evil-cosmic.out"
+rm -f $f
+cleanup_fn rm -f $f
+
+# 80 million zero bits in the backing disk, and the filter will
+# randomly flip (ie. set high) 1 in 800,000 bits, or about 100.
+
+# XXX Actually the number of set bits clusters around 80. There could
+# be a mistake in my calculations or the interval algorithm we use
+# might be biased.
+
+export f
+nbdkit -U - null 10000000 \
+ --filter=evil --filter=noextents \
+ evil=cosmic-rays evil-probability=1/800000 \
+ --run 'nbdcopy "$uri" $f'
+
+# Count the number of bits set in the output file. Easier to use
+# Python here ...
+
+$PYTHON -c '
+import os
+fh = open(os.environ["f"], "rb")
+buf = bytearray(fh.read())
+r = 0
+for b in buf:
+ if b != 0:
+ r += bin(b).count("1")
+
+print("non-zero bits: %d" % r)
+
+assert(r > 20 and r < 180)
+'
diff --git a/tests/test-evil-large-p.sh b/tests/test-evil-large-p.sh
new file mode 100755
index 000000000..47d558678
--- /dev/null
+++ b/tests/test-evil-large-p.sh
@@ -0,0 +1,55 @@
+#!/usr/bin/env bash
+# nbdkit
+# Copyright Red Hat
+#
+# 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 evil filter with large probabilities.
+
+source ./functions.sh
+set -e
+set -x
+
+requires_plugin null
+requires_filter evil
+requires_filter noextents
+requires nbdcopy --version
+
+# This is the largest probability we support.
+nbdkit -U - -fv null 1M \
+ --filter=evil --filter=noextents evil-probability=1/8 \
+ --run 'nbdcopy "$uri" null:'
+
+# Anything larger is treated as 100%.
+nbdkit -U - -fv null 1M \
+ --filter=evil --filter=noextents evil-probability=0.5 \
+ --run 'nbdcopy "$uri" null:'
+nbdkit -U - -fv null 1M \
+ --filter=evil --filter=noextents evil-probability=1.0 \
+ --run 'nbdcopy "$uri" null:'
diff --git a/tests/test-evil-small-p.sh b/tests/test-evil-small-p.sh
new file mode 100755
index 000000000..377ef579b
--- /dev/null
+++ b/tests/test-evil-small-p.sh
@@ -0,0 +1,57 @@
+#!/usr/bin/env bash
+# nbdkit
+# Copyright Red Hat
+#
+# 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 evil filter with small probabilities.
+
+source ./functions.sh
+set -e
+set -x
+
+requires_plugin null
+requires_filter evil
+requires_filter noextents
+requires nbdcopy --version
+
+# Check absence of divide by zero errors.
+nbdkit -U - -fv null 1M \
+ --filter=evil --filter=noextents evil-probability=0 \
+ --run 'nbdcopy "$uri" null:'
+
+# Smallest valid probability.
+nbdkit -U - -fv null 1M \
+ --filter=evil --filter=noextents evil-probability=1e-12 \
+ --run 'nbdcopy "$uri" null:'
+
+# Should be treated same as P = 0.
+nbdkit -U - -fv null 1M \
+ --filter=evil --filter=noextents evil-probability=1e-13 \
+ --run 'nbdcopy "$uri" null:'
diff --git a/tests/test-evil-stuck-high-bits.sh
b/tests/test-evil-stuck-high-bits.sh
new file mode 100755
index 000000000..7af1bfdc8
--- /dev/null
+++ b/tests/test-evil-stuck-high-bits.sh
@@ -0,0 +1,91 @@
+#!/usr/bin/env bash
+# nbdkit
+# Copyright Red Hat
+#
+# 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 evil filter in the default mode ("stuck-bits").
+
+source ./functions.sh
+set -e
+set -x
+
+requires_plugin null
+requires_filter evil
+requires_filter noextents
+requires_nbdsh_uri
+
+sock=$(mktemp -u /tmp/nbdkit-test-sock.XXXXXX)
+pidfile=evil-stuck-high-bits.pid
+files="$sock $pidfile"
+rm -f $files
+cleanup_fn rm -f $files
+
+# Run nbdkit with the evil filter.
+start_nbdkit -P $pidfile -U $sock \
+ --filter=evil --filter=noextents \
+ null 1G evil-probability=1/800000
+
+# Since 1 in 800,000 bits are stuck (on average), for every 100,000
+# bytes that we read we expect about 1 stuck bit. Note however that
+# bits are stuck randomly low or high, and against the null filter you
+# cannot see a stuck low bit, so in fact we expect to see only 1 stuck
+# bit per 200,000 bytes.
+#
+# There is a separate test for stuck low bits (test-evil-stuck-low-bits.sh).
+#
+# Also stuck bits should be consistent across reads.
+
+nbdsh -u "nbd+unix://?socket=$sock" \
+ -c - <<EOF
+def count_bits(buf):
+ r = 0
+ for i in range(0, len(buf)-1):
+ if buf[i] != 0:
+ r += bin(buf[i]).count("1")
+ return r
+
+def find_bit(buf):
+ for i in range(0, len(buf)-1):
+ if buf[i] != 0:
+ return i
+ return 0
+
+# Expect about 50 stuck-high bits.
+buf = h.pread(10000000, 0)
+bits = count_bits(buf)
+print("stuck high bits: %d (expected 50)" % bits)
+assert(bits > 20 and bits < 80)
+
+# If we read subsets they should match the contents of the buffer.
+i = find_bit(buf)
+buf1 = h.pread(1000, i)
+assert(buf1 == buf[i:i+1000])
+
+EOF
diff --git a/tests/test-evil-stuck-low-bits.sh
b/tests/test-evil-stuck-low-bits.sh
new file mode 100755
index 000000000..6f90b21ba
--- /dev/null
+++ b/tests/test-evil-stuck-low-bits.sh
@@ -0,0 +1,84 @@
+#!/usr/bin/env bash
+# nbdkit
+# Copyright Red Hat
+#
+# 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 evil filter in the default mode ("stuck-bits").
+
+source ./functions.sh
+set -e
+set -x
+
+requires_plugin ones
+requires_filter evil
+requires_nbdsh_uri
+
+sock=$(mktemp -u /tmp/nbdkit-test-sock.XXXXXX)
+pidfile=evil-stuck-low-bits.pid
+files="$sock $pidfile"
+rm -f $files
+cleanup_fn rm -f $files
+
+# Run nbdkit with the evil filter.
+start_nbdkit -P $pidfile -U $sock \
+ --filter=evil \
+ ones 1G evil-probability=1/800000
+
+# See description in test-evil-stuck-high-bits.sh. This test uses the
+# ones plugin to test for stuck low bits. The other parameters are
+# the same.
+
+nbdsh -u "nbd+unix://?socket=$sock" \
+ -c - <<EOF
+def count_bits(buf):
+ r = 0
+ for i in range(0, len(buf)-1):
+ if buf[i] != 0xff:
+ r += 8 - bin(buf[i]).count("1")
+ return r
+
+def find_bit(buf):
+ for i in range(0, len(buf)-1):
+ if buf[i] != 0xff:
+ return i
+ return 0
+
+# Expect about 50 stuck-low bits.
+buf = h.pread(10000000, 32*1024*1024)
+bits = count_bits(buf)
+print("stuck low bits: %d (expected 50)" % bits)
+assert(bits > 20 and bits < 80)
+
+# If we read subsets they should match the contents of the buffer.
+i = find_bit(buf)
+buf1 = h.pread(1000, 32*1024*1024 + i)
+assert(buf1 == buf[i:i+1000])
+
+EOF
diff --git a/tests/test-evil-stuck-wires.sh b/tests/test-evil-stuck-wires.sh
new file mode 100755
index 000000000..262b02049
--- /dev/null
+++ b/tests/test-evil-stuck-wires.sh
@@ -0,0 +1,85 @@
+#!/usr/bin/env bash
+# nbdkit
+# Copyright Red Hat
+#
+# 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 evil filter in stuck-wires mode.
+
+source ./functions.sh
+set -e
+set -x
+
+requires_plugin null
+requires_filter evil
+requires_filter noextents
+requires_nbdsh_uri
+
+sock=$(mktemp -u /tmp/nbdkit-test-sock.XXXXXX)
+pidfile=evil-stuck-wires.pid
+files="$sock $pidfile"
+rm -f $files
+cleanup_fn rm -f $files
+
+# Run nbdkit with the evil filter.
+start_nbdkit -P $pidfile -U $sock \
+ --filter=evil --filter=noextents \
+ null 1G evil=stuck-wires evil-probability=1/10000
+
+# Reads from the filter should have 1:10,000 bits stuck high or low.
+# However we don't see stuck low bits since we are always reading
+# zeroes, so we only expect about 1:20,000 bits stuck high.
+#
+# If we read 10,000,000 bytes (80,000,000 bits) we would expect about
+# 4000 stuck bits.
+#
+# No matter where we read from the pattern of stuck bits should be the
+# same (stuck wires, not backing bits).
+
+nbdsh -u "nbd+unix://?socket=$sock" \
+ -c - <<EOF
+def count_bits(buf):
+ r = 0
+ for i in range(0, len(buf)-1):
+ if buf[i] != 0:
+ r += bin(buf[i]).count("1")
+ return r
+
+buf1 = h.pread(10000000, 0)
+bits = count_bits(buf1)
+print("stuck high bits: %d (expected 4000)" % bits)
+assert(bits > 3000 and bits < 5000)
+
+# These buffers should be identical.
+buf2 = h.pread(10000000, 1024)
+buf3 = h.pread(10000000, 32*1024*1024 - 9999)
+assert(buf1 == buf2)
+assert(buf1 == buf3)
+
+EOF
--
2.39.2
On Wed, May 17, 2023 at 11:06:59AM +0100, Richard W.M. Jones wrote:> This filter adds random data corruption when reading from the > underlying plugin. > ---> +=head1 VERSION > + > +C<nbdkit-pause-filter> first appeared in nbdkit 1.36.Missed touching up this part of your copy-paste.> +static enum mode evil_mode = STUCK_BITS; > +static double evil_probability = -1; /* default depends on mode */ > +static double evil_stuck_probability = 1.0; > +static uint32_t evil_seed; > + > +/* Probabilities < ? are treated as zero to avoid both divide by zero > + * problems and potentially exploding values in calculations. > + */ > +#define EPSILON 1e-12 > + > +/* Probabilities > MAXP are treated as 100%. This is because our > + * algorithm below can corrupt at most 1 bit per byte and doesn't make > + * progress otherwise. > + */ > +#define MAXP (1.0/8.0)These are reasonable constraints given your algorithm.> + > +/* This is the heart of the algorithm, the function which corrupts > + * the buffer after reading it from the plugin. > + * > + * The observation is that if we have a block of (eg) size 10**6 bits > + * and our probability of finding a corrupt bit is (eg) 1/10**4, then > + * we expect approximately 100 bits in the block to be corrupted. > + * > + * For stuck bits we want the corrupted bits to be the same on each > + * access, either relative to the backing disk (STUCK_BITS) or to the > + * request (STUCK_WIRES). > + * > + * Instead of creating an expensive bitmap ahead of time covering the > + * whole disk, we can use the random number generator with a fixed > + * seed derived from the offset of the start of the block. We can > + * then choose a random number uniformly in the range [0..2*(1/P)] (in > + * the example [0..2*10**4]) as the distance to the next corrupt bit. > + * We jump forwards, corrupt that bit, and repeat until we reach the > + * end of the block. > + * > + * "Corrupted" in this case can mean flipped by cosmic rays or stuck, > + * depending on the filter mode. > + * > + * On average this will choose the right number of bits in the block. > + * (Although their distribution will be suboptimal. In a uniform > + * distribution it should be possible for two corrupted bits to be > + * greater than 2*(1/P) apart, but the above algorithm would not do > + * this. In practice this probably doesn't matter.)Likewise, in theory with a uniform distribution, it should be possible (although generally improbable) for any two adjacent bits to be corrupted, but in practice adjacent corruption is only possible for the last bit in one byte followed by the first bit in the next byte, since MAXP is chosen so that we always resume at the next byte after performing a corruption (so only 1 out of 8 positions is even a candidate for an adjacent corruption). One of the interesting points that comes out of the study of information theory and checksumming algorithms is the design of algorithms that can detect or even correct a small run of consecutively corrupt bits, since corruptions do tend to occur in bursts. For example, CRC32 [1] can detect 100% of bursts of < 32 consecutive bit corruptions if that is the only corruption in the packet (it takes either longer bursts, or more than one disjoint corruption, before you can run into a false negative where CRC says the overall packet was good despite the corruption). As written, the evil filter has a maximum burst of 1; maybe adding a maximum-burst parameter (find the bit position(s) to inject errors at, then randomly choose the burst size of the error at that point) might be a worthwhile future addition. But I don't see it as being essential to getting a first round of the filter committed. If we do add a burst parameter, you may also want to consider whether your current choice of a 50/50 stuck high vs. stuck low may need to consider more failure modes (entire burst stuck high, entire burst stuck low, all bits in the burst inverted, or a random number used as the xor mask for which bits in the burst to flip...). Do we care about cross-version compatibility (the same bits will be corrupt for a deterministic seed, regarless of future changes to the filter), or is it merely single-run consistency (for this build of nbdkit, a deterministic seed flips this particular set of bits, but the set of bits flipped may change in the next build of nbdkit when we start consuming randomness differently in order to account for more corruption modes). (I'd probably lean to explicitly documenting that we do not guarantee cross-version determinism; leaving the door open to consume randomness differently in the future.) [1] https://en.wikipedia.org/wiki/Cyclic_redundancy_check> + > +static int > +evil_get_ready (int thread_model) > +{ > + switch (evil_mode) { > + case COSMIC_RAYS: > + xsrandom ((uint64_t) evil_seed, &state); > + break; > + > + case STUCK_BITS: > + case STUCK_WIRES: > + ; > + } > + > + /* Choose the block size based on the probability, so that at least > + * 100 bits are expected to be corrupted in the block. Block size > + * must be a power of 2. > + * > + * Example: P = 1e-4 > + * => ideal block_size = 100 / 1e-4 = 1e6 (bits) = 1e6 / 8 (bytes) > + * => next power of 2 block_size = 131072 = 2**17 > + * => expected bits per block = ~104 > + */ > + if (evil_probability < EPSILON || evil_probability > MAXP) > + block_size = 1024*1024; /* unused so value doesn't matter */ > + else > + block_size = next_power_of_2 ((uint64_t) (100. / evil_probability) / 8); > + > + nbdkit_debug ("evil: mode: %s, P: %lg, seed: %" PRIu32, > + evil_mode_to_string (evil_mode), > + evil_probability, evil_seed); > + nbdkit_debug ("evil: block_size: %" PRIu64 " (2**%d)", > + block_size, log_2_bits (block_size)); > + nbdkit_debug ("evil: expected bits per block: %g", > + 8 * block_size * evil_probability);Definitely a useful addition over v1.> + > + return 0; > +} > + > +static void corrupt_all_bits (uint8_t *buf, uint32_t count, > + struct random_state *rs, > + enum corruption_type ct); > +static uint8_t corrupt_one_bit (uint8_t byte, unsigned bit, > + uint64_t rand, enum corruption_type ct); > + > +static void > +corrupt_buffer (uint8_t *buf, uint32_t count, uint64_t offset_in_block, > + struct random_state *rs, enum corruption_type ct) > +{ > + /* No corruption, and avoids a divide by zero below. */ > + if (evil_probability < EPSILON) return; > + > + /* 100% corruption, avoids lack of progress in the loop below. */ > + if (evil_probability > MAXP) { > + corrupt_all_bits (buf, count, rs, ct); > + return; > + } > + > + uint64_t offs, intvl, i, rand;Since 'rand' is also reserved as the name of the <stdlib.h> function, you may want to pick a different name to this variable to avoid -Wshadow warnings.> + const uint64_t invp2 = (uint64_t) (2.0 / evil_probability); > + > + assert ((offset_in_block & ~(block_size-1)) == 0); > + > + /* Iterate over the whole block from the start. */ > + for (offs = 0; offs < offset_in_block + count; ) { > + /* Choose the length of the interval to the next corrupted bit, by > + * picking a random number in [0..2*(1/P)]. > + * > + * Remember this is in bits! > + */ > + intvl = xrandom (rs) % invp2; > + > + /* Consume one more random state. We may or may not use this. > + * But we need to always consume two random states per iteration > + * to make the output predictable. > + */ > + rand = xrandom (rs); > + > + /* Adjust offs to that byte. */ > + offs += intvl / 8; > + > + /* If we have gone past the end of buffer, stop. */ > + if (offs >= offset_in_block + count) break; > + > + /* If the current offs lies within the buffer, corrupt a bit. */ > + if (offs >= offset_in_block) { > + i = offs - offset_in_block; > + assert (i < count); > + buf[i] = corrupt_one_bit (buf[i], intvl & 7, rand, ct); > + } > + } > +} > + > +static void > +corrupt_all_bits (uint8_t *buf, uint32_t count, > + struct random_state *rs, enum corruption_type ct) > +{ > + size_t i; > + unsigned bit; > + uint64_t rand; > + > + /* This is used when MAXP < P <= 100%. We treat it the same as 100% > + * and corrupt all bits. > + */ > + for (i = 0; i < count; ++i) { > + for (bit = 0; bit < 8; ++bit) { > + rand = xrandom (rs); > + buf[i] = corrupt_one_bit (buf[i], bit, rand, ct); > + } > + }Is this actually corrupting all bits, or corrupting 1 bit per byte? I found the function name a bit confusing. (Doing XOR with -1 to invert all bits is not the same as choosing a random bit pattern but where only about 50% of the bits get flipped - but both behaviors can prove interesting to see how filesystems cope with such corruptions)> +} > + > +static uint8_t > +corrupt_one_bit (uint8_t byte, unsigned bit, > + uint64_t rand, enum corruption_type ct)Another use of 'rand' that might be confusing given the <stdlib.h> function.> +{ > + const unsigned mask = 1 << bit; > + > + switch (ct) { > + case FLIP: > + byte ^= mask; > + break; > + case STUCK: > + rand &= 0xffffffff; > + if (evil_stuck_probability * 0x100000000 > rand) { > + if (rand & 1) /* stuck high or low? */ > + byte |= mask; > + else > + byte &= ~mask; > + } > + } > + return byte; > +}And I ran out of review time today, before finishing reading the rest of your patch. -- Eric Blake, Principal Software Engineer Red Hat, Inc. +1-919-301-3266 Virtualization: qemu.org | libvirt.org
On Wed, May 17, 2023 at 11:06:59AM +0100, Richard W.M. Jones wrote:> This filter adds random data corruption when reading from the > underlying plugin. > ---> +++ b/tests/test-evil-small-p.sh > @@ -0,0 +1,57 @@ > + > +# Check absence of divide by zero errors. > +nbdkit -U - -fv null 1M \ > + --filter=evil --filter=noextents evil-probability=0 \ > + --run 'nbdcopy "$uri" null:' > + > +# Smallest valid probability. > +nbdkit -U - -fv null 1M \ > + --filter=evil --filter=noextents evil-probability=1e-12 \ > + --run 'nbdcopy "$uri" null:' > + > +# Should be treated same as P = 0. > +nbdkit -U - -fv null 1M \ > + --filter=evil --filter=noextents evil-probability=1e-13 \ > + --run 'nbdcopy "$uri" null:' > diff --git a/tests/test-evil-stuck-high-bits.sh b/tests/test-evil-stuck-high-bits.shMaybe worth capturing the output and grepping for the expected outputs, rather than requiring human post-parsing of the log file? Same for the large-p counterpart test. Not a show-stopper. At this point, I think you can go ahead and commit what you've cleaned up based on these reviews, and we can do any further cleanups as followups rather than needing to see a full v3 posting. -- Eric Blake, Principal Software Engineer Red Hat, Inc. +1-919-301-3266 Virtualization: qemu.org | libvirt.org