[PATCH nbdkit 0/5] New ones plugin and evil filter
This is just a bit of silliness I was thinking about on the plane last week. Yes, I know nbdkit_parse_probability uses scanf and that's bad. I still think we should fix scanf. We might call the new filter "--filter=corruption" instead, but this name stuck. Rich.
In nbdkit-error-filter we need to parse parameters as probabilities. This is useful enough to add to nbdkit, since we will use it in another filter in future. --- docs/nbdkit-plugin.pod | 19 +++++++ plugins/python/nbdkit-python-plugin.pod | 6 ++ include/nbdkit-common.h | 2 + server/nbdkit.syms | 1 + server/public.c | 37 +++++++++++++ server/test-public.c | 73 +++++++++++++++++++++++++ plugins/ocaml/NBDKit.mli | 11 ++-- plugins/ocaml/NBDKit.ml | 2 + plugins/ocaml/bindings.c | 16 ++++++ plugins/python/modfunctions.c | 21 +++++++ tests/test-python-plugin.py | 12 ++++ tests/test_ocaml_plugin.ml | 1 + 12 files changed, 196 insertions(+), 5 deletions(-) diff --git a/docs/nbdkit-plugin.pod b/docs/nbdkit-plugin.pod index 860c5cecb..e8d30a98e 100644 --- a/docs/nbdkit-plugin.pod +++ b/docs/nbdkit-plugin.pod @@ -1433,6 +1433,25 @@ C<str> can be a string containing a case-insensitive form of various common toggle values. The function returns 0 or 1 if the parse was successful. If there was an error, it returns C<-1>. +=head2 Parsing probabilities + +Use the C<nbdkit_parse_probability> utility function to parse +probabilities. Common formats understood include: C<"0.1">, C<"10%"> +or C<"1:10">, which all mean a probability of 1 in 10. + + int nbdkit_parse_probability (const char *what, const char *str, + double *ret); + +The C<what> parameter is printed in error messages to provide context. +The C<str> parameter is the probability string. + +On success the function returns C<0> and sets C<*ret>. B<Note> that +the probability returned may be outside the range S<[ 0.0..1.0 ]>, for +example if C<str == "200%">. If you want to clamp the result you must +check that yourself. + +On error, nbdkit_error is called and C<-1> is returned. + =head2 Reading passwords The C<nbdkit_read_password> utility function can be used to read diff --git a/plugins/python/nbdkit-python-plugin.pod b/plugins/python/nbdkit-python-plugin.pod index e328cc2e0..0e55dcfcc 100644 --- a/plugins/python/nbdkit-python-plugin.pod +++ b/plugins/python/nbdkit-python-plugin.pod @@ -136,6 +136,12 @@ C<import errno>. Parse a string (such as "100M") into a size in bytes. Wraps the C<nbdkit_parse_size()> C function. +=head3 C<nbdkit.parse_probability(what, str)> + +Parse a string (such as "100%") into a probability, returning a +floating point number. Wraps the C<nbdkit_parse_probability()> C +function. + =head3 C<nbdkit.shutdown()> Request asynchronous server shutdown. diff --git a/include/nbdkit-common.h b/include/nbdkit-common.h index e070245b8..b44e77323 100644 --- a/include/nbdkit-common.h +++ b/include/nbdkit-common.h @@ -105,6 +105,8 @@ NBDKIT_EXTERN_DECL (void, nbdkit_vdebug, NBDKIT_EXTERN_DECL (char *, nbdkit_absolute_path, (const char *path)); NBDKIT_EXTERN_DECL (int64_t, nbdkit_parse_size, (const char *str)); +NBDKIT_EXTERN_DECL (int, nbdkit_parse_probability, + (const char *what, const char *str, double *r)); NBDKIT_EXTERN_DECL (int, nbdkit_parse_bool, (const char *str)); NBDKIT_EXTERN_DECL (int, nbdkit_parse_int, (const char *what, const char *str, int *r)); diff --git a/server/nbdkit.syms b/server/nbdkit.syms index 353ea2a98..c6480e43e 100644 --- a/server/nbdkit.syms +++ b/server/nbdkit.syms @@ -67,6 +67,7 @@ nbdkit_parse_int64_t; nbdkit_parse_int8_t; nbdkit_parse_int; + nbdkit_parse_probability; nbdkit_parse_size; nbdkit_parse_uint16_t; nbdkit_parse_uint32_t; diff --git a/server/public.c b/server/public.c index 71ea6779d..fe2b48c7c 100644 --- a/server/public.c +++ b/server/public.c @@ -421,6 +421,43 @@ nbdkit_parse_size (const char *str) return size * scale; } +NBDKIT_DLL_PUBLIC int +nbdkit_parse_probability (const char *what, const char *str, + double *retp) +{ + double d, d2; + char c; + int n; + + if (sscanf (str, "%lg%[:/]%lg%n", &d, &c, &d2, &n) == 3 && + strcmp (&str[n], "") == 0) { /* N:M or N/M */ + if (d == 0 && d2 == 0) /* 0/0 is OK */ + ; + else if (d2 == 0) /* N/0 is bad */ + goto bad_parse; + else + d /= d2; + } + else if (sscanf (str, "%lg%n", &d, &n) == 1) { + if (strcmp (&str[n], "%") == 0) /* percentage */ + d /= 100.0; + else if (strcmp (&str[n], "") == 0) /* probability */ + ; + else + goto bad_parse; + } + else + goto bad_parse; + + if (retp) + *retp = d; + return 0; + + bad_parse: + nbdkit_error ("%s: could not parse '%s'", what, str); + return -1; +} + /* Parse a string as a boolean, or return -1 after reporting the error. */ NBDKIT_DLL_PUBLIC int diff --git a/server/test-public.c b/server/test-public.c index 676411290..0d84abdd2 100644 --- a/server/test-public.c +++ b/server/test-public.c @@ -200,6 +200,78 @@ test_nbdkit_parse_size (void) return pass; } +static bool +test_nbdkit_parse_probability (void) +{ + size_t i; + bool pass = true; + struct pair { + const char *str; + int result; + double expected; + } tests[] = { + /* Bogus strings */ + { "", -1 }, + { "garbage", -1 }, + { "0garbage", -1 }, + { "1X", -1 }, + { "1%%", -1 }, + { "1:", -1 }, + { "1:1:1", -1 }, + { "1:0", -1 }, /* format is valid but divide by zero is not allowed */ + { "1/", -1 }, + { "1/2/3", -1 }, + + /* Numbers. */ + { "0", 0, 0 }, + { "1", 0, 1 }, + { "2", 0, 2 }, /* values outside [0..1] range are allowed */ + { "0.1", 0, 0.1 }, + { "0.5", 0, 0.5 }, + { "0.9", 0, 0.9 }, + { "1.0000", 0, 1 }, + + /* Percentages. */ + { "0%", 0, 0 }, + { "50%", 0, 0.5 }, + { "100%", 0, 1 }, + { "90.25%", 0, 0.9025 }, + + /* N in M */ + { "1:1000", 0, 0.001 }, + { "1/1000", 0, 0.001 }, + { "2:99", 0, 2.0/99 }, + { "2/99", 0, 2.0/99 }, + { "0:1000000", 0, 0 }, + }; + + for (i = 0; i < ARRAY_SIZE (tests); i++) { + int r; + double d; + + error_flagged = false; + r = nbdkit_parse_probability ("test", tests[i].str, &d); + if (r != tests[i].result) { + fprintf (stderr, + "Wrong return value for %s, got %d, expected %d\n", + tests[i].str, r, tests[i].result); + pass = false; + } + if (r == 0 && d != tests[i].expected) { + fprintf (stderr, + "Wrong result for %s, got %g, expected %g\n", + tests[i].str, d, tests[i].expected); + pass = false; + } + if ((r == -1) != error_flagged) { + fprintf (stderr, "Wrong error message handling for %s\n", tests[i].str); + pass = false; + } + } + + return pass; +} + static bool test_nbdkit_parse_ints (void) { @@ -503,6 +575,7 @@ main (int argc, char *argv[]) { bool pass = true; pass &= test_nbdkit_parse_size (); + pass &= test_nbdkit_parse_probability (); pass &= test_nbdkit_parse_ints (); pass &= test_nbdkit_read_password (); /* nbdkit_absolute_path and nbdkit_nanosleep not unit-tested here, but diff --git a/plugins/ocaml/NBDKit.mli b/plugins/ocaml/NBDKit.mli index 81447d07d..bc190f267 100644 --- a/plugins/ocaml/NBDKit.mli +++ b/plugins/ocaml/NBDKit.mli @@ -134,9 +134,9 @@ val register_plugin : into [EINVAL]. *) val set_error : Unix.error -> unit -(** Bindings for [nbdkit_parse_size], [nbdkit_parse_bool] and - [nbdkit_read_password]. See nbdkit-plugin(3) for information - about these functions. +(** Bindings for [nbdkit_parse_size], [nbdkit_parse_probability], + [nbdkit_parse_bool] and [nbdkit_read_password]. See + nbdkit-plugin(3) for information about these functions. On error these functions all raise [Invalid_argument]. The actual error is sent to the nbdkit error log and is not @@ -145,10 +145,11 @@ val set_error : Unix.error -> unit (* Note OCaml has functions already for parsing other integers, so * there is no need to bind them here. We only bind the functions * which have special abilities in nbdkit: [parse_size] can parse - * human sizes, [parse_bool] parses a range of nbdkit-specific - * boolean strings, and [read_password] suppresses echo. + * human sizes, [parse_probability] and [parse_bool] parses a range + * of nbdkit-specific strings, and [read_password] suppresses echo. *) val parse_size : string -> int64 +val parse_probability : string -> string -> float val parse_bool : string -> bool val read_password : string -> string diff --git a/plugins/ocaml/NBDKit.ml b/plugins/ocaml/NBDKit.ml index e1cf28c94..2d1696917 100644 --- a/plugins/ocaml/NBDKit.ml +++ b/plugins/ocaml/NBDKit.ml @@ -160,6 +160,8 @@ let register_plugin ~name (* Bindings to nbdkit server functions. *) external set_error : Unix.error -> unit = "ocaml_nbdkit_set_error" [@@noalloc] external parse_size : string -> int64 = "ocaml_nbdkit_parse_size" +external parse_probability : string -> string -> float = + "ocaml_nbdkit_parse_probability" external parse_bool : string -> bool = "ocaml_nbdkit_parse_bool" external read_password : string -> string = "ocaml_nbdkit_read_password" external realpath : string -> string = "ocaml_nbdkit_realpath" diff --git a/plugins/ocaml/bindings.c b/plugins/ocaml/bindings.c index f2c9ca07d..4885feac5 100644 --- a/plugins/ocaml/bindings.c +++ b/plugins/ocaml/bindings.c @@ -74,6 +74,22 @@ ocaml_nbdkit_parse_size (value strv) CAMLreturn (rv); } +NBDKIT_DLL_PUBLIC value +ocaml_nbdkit_parse_probability (value whatv, value strv) +{ + CAMLparam2 (whatv, strv); + CAMLlocal1 (dv); + int r; + double d; + + r = nbdkit_parse_probability (String_val (whatv), String_val (strv), &d); + if (r == -1) + caml_invalid_argument ("nbdkit_parse_probability"); + dv = caml_copy_double (d); + + CAMLreturn (dv); +} + NBDKIT_DLL_PUBLIC value ocaml_nbdkit_parse_bool (value strv) { diff --git a/plugins/python/modfunctions.c b/plugins/python/modfunctions.c index 479707e78..74bfd6f27 100644 --- a/plugins/python/modfunctions.c +++ b/plugins/python/modfunctions.c @@ -122,11 +122,32 @@ parse_size (PyObject *self, PyObject *args) return PyLong_FromSize_t ((size_t)size); } +/* nbdkit.parse_probability */ +static PyObject * +parse_probability (PyObject *self, PyObject *args) +{ + const char *what, *str; + double d; + + if (!PyArg_ParseTuple (args, "ss:parse_probability", &what, &str)) + return NULL; + + if (nbdkit_parse_probability (what, str, &d) == -1) { + PyErr_SetString (PyExc_ValueError, + "Unable to parse string as probability"); + return NULL; + } + + return PyFloat_FromDouble (d); +} + static PyMethodDef NbdkitMethods[] = { { "debug", debug, METH_VARARGS, "Print a debug message" }, { "export_name", export_name, METH_NOARGS, "Return the optional export name negotiated with the client" }, + { "parse_probability", parse_probability, METH_VARARGS, + "Parse probability strings into floating point number" }, { "parse_size", parse_size, METH_VARARGS, "Parse human-readable size strings into bytes" }, { "set_error", set_error, METH_VARARGS, diff --git a/tests/test-python-plugin.py b/tests/test-python-plugin.py index c3232a112..7f3a2c2e4 100644 --- a/tests/test-python-plugin.py +++ b/tests/test-python-plugin.py @@ -55,8 +55,20 @@ class TestAPI(unittest.TestCase): with self.assertRaises(ValueError): nbdkit.parse_size('foo') + def test_parse_probability(self): + self.assertEqual(nbdkit.parse_probability('test', '1:10'), 0.1) + self.assertEqual(nbdkit.parse_probability('test', '100%'), 1) + self.assertEqual(nbdkit.parse_probability('test', '0'), 0) + + with self.assertRaises(TypeError): + nbdkit.parse_probability('test', 17) + + with self.assertRaises(ValueError): + nbdkit.parse_probability('test', 'bar') + TestAPI().test_parse_size() +TestAPI().test_parse_probability() def config(k, v): diff --git a/tests/test_ocaml_plugin.ml b/tests/test_ocaml_plugin.ml index 8132de8f8..bf998d361 100644 --- a/tests/test_ocaml_plugin.ml +++ b/tests/test_ocaml_plugin.ml @@ -39,6 +39,7 @@ let sparse = Bytes.make nr_sectors '\000' (* sparseness bitmap *) (* Test parse_* functions. *) let () = assert (NBDKit.parse_size "1M" = Int64.of_int (1024*1024)); + assert (NBDKit.parse_probability "test parse probability" "1:10" = 0.1); assert (NBDKit.parse_bool "true" = true); assert (NBDKit.parse_bool "0" = false) -- 2.39.2
On 5/16/23 14:12, Richard W.M. Jones wrote:
In nbdkit-error-filter we need to parse parameters as probabilities. This is useful enough to add to nbdkit, since we will use it in another filter in future. --- docs/nbdkit-plugin.pod | 19 +++++++ plugins/python/nbdkit-python-plugin.pod | 6 ++ include/nbdkit-common.h | 2 + server/nbdkit.syms | 1 + server/public.c | 37 +++++++++++++ server/test-public.c | 73 +++++++++++++++++++++++++ plugins/ocaml/NBDKit.mli | 11 ++-- plugins/ocaml/NBDKit.ml | 2 + plugins/ocaml/bindings.c | 16 ++++++ plugins/python/modfunctions.c | 21 +++++++ tests/test-python-plugin.py | 12 ++++ tests/test_ocaml_plugin.ml | 1 + 12 files changed, 196 insertions(+), 5 deletions(-)
diff --git a/docs/nbdkit-plugin.pod b/docs/nbdkit-plugin.pod index 860c5cecb..e8d30a98e 100644 --- a/docs/nbdkit-plugin.pod +++ b/docs/nbdkit-plugin.pod @@ -1433,6 +1433,25 @@ C<str> can be a string containing a case-insensitive form of various common toggle values. The function returns 0 or 1 if the parse was successful. If there was an error, it returns C<-1>.
+=head2 Parsing probabilities + +Use the C<nbdkit_parse_probability> utility function to parse +probabilities. Common formats understood include: C<"0.1">, C<"10%"> +or C<"1:10">, which all mean a probability of 1 in 10. + + int nbdkit_parse_probability (const char *what, const char *str, + double *ret); + +The C<what> parameter is printed in error messages to provide context. +The C<str> parameter is the probability string. + +On success the function returns C<0> and sets C<*ret>. B<Note> that +the probability returned may be outside the range S<[ 0.0..1.0 ]>, for +example if C<str == "200%">. If you want to clamp the result you must +check that yourself. + +On error, nbdkit_error is called and C<-1> is returned. + =head2 Reading passwords
The C<nbdkit_read_password> utility function can be used to read diff --git a/plugins/python/nbdkit-python-plugin.pod b/plugins/python/nbdkit-python-plugin.pod index e328cc2e0..0e55dcfcc 100644 --- a/plugins/python/nbdkit-python-plugin.pod +++ b/plugins/python/nbdkit-python-plugin.pod @@ -136,6 +136,12 @@ C<import errno>. Parse a string (such as "100M") into a size in bytes. Wraps the C<nbdkit_parse_size()> C function.
+=head3 C<nbdkit.parse_probability(what, str)> + +Parse a string (such as "100%") into a probability, returning a +floating point number. Wraps the C<nbdkit_parse_probability()> C +function. + =head3 C<nbdkit.shutdown()>
Request asynchronous server shutdown. diff --git a/include/nbdkit-common.h b/include/nbdkit-common.h index e070245b8..b44e77323 100644 --- a/include/nbdkit-common.h +++ b/include/nbdkit-common.h @@ -105,6 +105,8 @@ NBDKIT_EXTERN_DECL (void, nbdkit_vdebug,
NBDKIT_EXTERN_DECL (char *, nbdkit_absolute_path, (const char *path)); NBDKIT_EXTERN_DECL (int64_t, nbdkit_parse_size, (const char *str)); +NBDKIT_EXTERN_DECL (int, nbdkit_parse_probability, + (const char *what, const char *str, double *r)); NBDKIT_EXTERN_DECL (int, nbdkit_parse_bool, (const char *str)); NBDKIT_EXTERN_DECL (int, nbdkit_parse_int, (const char *what, const char *str, int *r)); diff --git a/server/nbdkit.syms b/server/nbdkit.syms index 353ea2a98..c6480e43e 100644 --- a/server/nbdkit.syms +++ b/server/nbdkit.syms @@ -67,6 +67,7 @@ nbdkit_parse_int64_t; nbdkit_parse_int8_t; nbdkit_parse_int; + nbdkit_parse_probability; nbdkit_parse_size; nbdkit_parse_uint16_t; nbdkit_parse_uint32_t; diff --git a/server/public.c b/server/public.c index 71ea6779d..fe2b48c7c 100644 --- a/server/public.c +++ b/server/public.c @@ -421,6 +421,43 @@ nbdkit_parse_size (const char *str) return size * scale; }
+NBDKIT_DLL_PUBLIC int +nbdkit_parse_probability (const char *what, const char *str, + double *retp) +{ + double d, d2; + char c; + int n; + + if (sscanf (str, "%lg%[:/]%lg%n", &d, &c, &d2, &n) == 3 && + strcmp (&str[n], "") == 0) { /* N:M or N/M */ + if (d == 0 && d2 == 0) /* 0/0 is OK */ + ; + else if (d2 == 0) /* N/0 is bad */ + goto bad_parse; + else + d /= d2;
I don't want to be a spoilsport, but this division makes me extra nervous [1], on top of parsing floating point *at all* [2]. [2] Eric has just posted a 19-part series, v2, for QEMU, for fixing the numerous issues in QEMU's floating point parser. Personal opinion: QEMU doesn't even have a *valid reason* for parsing floating point! All QEMU deals with are *integer quantities* such as disk images consisting of whole numbers of bytes! But again, that's just a personal opinion. [1] I maintain that floating point is only a part of the C language so that C could be made "competitive" with Fortran. Therefore I honestly believe that *no* floating point should be done in C without fully engaging in numerical analysis. I'm not up to that -- I've had numerical analysis in college, and I remember just enough of it to steer the heck clear of it. In C99, there's a whole chapter dedicated to the floating point environment (7.6 Floating-point environment <fenv.h>), and there's also the normative Annex F ("IEC 60559 floating-point arithmetic"). In this particular case, we have a floating point division. The divisor "d2" can be an extremely small *positive* number (DBL_MIN, or another value with a very small positive mantissa and a huge absolute value negative exponent, like FLT_RADIX raised to DBL_MIN_EXP), and the dividend "d" may be a huge positive number (DBL_MAX, or another value with a large positive mantissa and a huge positive exponent like FLT_RADIX raised to DBL_MAX_EXP). The quotient d/d2 is then almost certainly not representable in the type -- the resultant exponent would have to be about (DBL_MAX_EXP - DBL_MIN_EXP), which in practice is about 2 * DBL_MAX_EXP -- and there's just not another exponent bit available in the type for that. And I can't even say whether that would result in a silent NaN, or a silent positive infinity, or a floating point exception. I don't like code that I can't reason about (even if it is ultimately my fault, for not knowing the language well enough). Relatedly... in patch#5, we have: + block_size = next_power_of_2 ((uint64_t) (100. / evil_probability)); where "evil_probability" comes from nbdkit_parse_probability(), and is checked separately to be in [0, 1] (both boundaries inclusive, per the code). So, evil_probability==0 will produce a division by zero here, but even if we assume that's just a typo and we actually mean to exclude 0, the user can still provide a value near DBL_MIN on the command line, like 1E-37. 100 is 1E+2, so the quotient is 1E+39. Representing 10^39 in binary requires ceil(39 * log2(10)) bits -- that's 130 bits; uint64_t is too small for that. And then the following applies from C99: 6.3.1.4 Real floating and integer When a finite value of real floating type is converted to an integer type other than _Bool, the fractional part is discarded (i.e., the value is truncated toward zero). If the value of the integral part cannot be represented by the integer type, the behavior is undefined. [Footnote 50] Footnote 50: The remaindering operation performed when a value of integer type is converted to unsigned type need not be performed when a value of real floating type is converted to unsigned type. Thus, the range of portable real floating values is (−1, Utype_MAX+1). (Note the round parens in the footnote: it means the boundaries are *excluded*. So, a value like -0.5 will be truncated to zero, and a value like UINT64_MAX + 0.5 will be truncated to UINT64_MAX, but (-1) itself and (UINT64_MAX + 1) itself are not permitted already.) I recommend the following: take two unsigned integers, numerator "a" and denominator "b", from the command line. We know how to parse those safely. Maintain those values separately. In every calculation where we need to multiply x by a/b, calculate (x*a)/b, and use MUL_OVERFLOW() for the multiplication. Where we need to divide x by (a/b), use (x*b)/a, again with MUL_OVERFLOW(). (And of course the divisor must never be 0.) In case we can determine the possible range for "x" *in advance*, for example because we know we're going to divide x=100 by (a/b), we can *also* determine the safe range for "a" and "b" as well -- for x=100, x*b must fit in a uint64_t, so "b" must not exceed UINT64_MAX/100, and that can be verified safely after parsing. Floating point is in fact *supposed* to take away all this messing, and "compress" the ratio into the mantissa, and set the exponent (the scale) accordingly. But the simplicity is deceiving, due to cancellation, error accumulation, etc. (Cue the articles "what every programmer should know about floating point".) I don't think I can *safely* use floating point, I can only say when something looks unsafe. Maintaining two positive integers (numerator and denominator) is more work, but I can at least *reason* about those. If Eric is OK with this patch set, I won't try to block it, it just makes me feel very uncomfortable. It's more than just scanf() lacking proper internal error handling; the real complications come when we perform operations on the floating point values. Laszlo
+ } + else if (sscanf (str, "%lg%n", &d, &n) == 1) { + if (strcmp (&str[n], "%") == 0) /* percentage */ + d /= 100.0; + else if (strcmp (&str[n], "") == 0) /* probability */ + ; + else + goto bad_parse; + } + else + goto bad_parse; + + if (retp) + *retp = d; + return 0; + + bad_parse: + nbdkit_error ("%s: could not parse '%s'", what, str); + return -1; +} + /* Parse a string as a boolean, or return -1 after reporting the error. */ NBDKIT_DLL_PUBLIC int diff --git a/server/test-public.c b/server/test-public.c index 676411290..0d84abdd2 100644 --- a/server/test-public.c +++ b/server/test-public.c @@ -200,6 +200,78 @@ test_nbdkit_parse_size (void) return pass; }
+static bool +test_nbdkit_parse_probability (void) +{ + size_t i; + bool pass = true; + struct pair { + const char *str; + int result; + double expected; + } tests[] = { + /* Bogus strings */ + { "", -1 }, + { "garbage", -1 }, + { "0garbage", -1 }, + { "1X", -1 }, + { "1%%", -1 }, + { "1:", -1 }, + { "1:1:1", -1 }, + { "1:0", -1 }, /* format is valid but divide by zero is not allowed */ + { "1/", -1 }, + { "1/2/3", -1 }, + + /* Numbers. */ + { "0", 0, 0 }, + { "1", 0, 1 }, + { "2", 0, 2 }, /* values outside [0..1] range are allowed */ + { "0.1", 0, 0.1 }, + { "0.5", 0, 0.5 }, + { "0.9", 0, 0.9 }, + { "1.0000", 0, 1 }, + + /* Percentages. */ + { "0%", 0, 0 }, + { "50%", 0, 0.5 }, + { "100%", 0, 1 }, + { "90.25%", 0, 0.9025 }, + + /* N in M */ + { "1:1000", 0, 0.001 }, + { "1/1000", 0, 0.001 }, + { "2:99", 0, 2.0/99 }, + { "2/99", 0, 2.0/99 }, + { "0:1000000", 0, 0 }, + }; + + for (i = 0; i < ARRAY_SIZE (tests); i++) { + int r; + double d; + + error_flagged = false; + r = nbdkit_parse_probability ("test", tests[i].str, &d); + if (r != tests[i].result) { + fprintf (stderr, + "Wrong return value for %s, got %d, expected %d\n", + tests[i].str, r, tests[i].result); + pass = false; + } + if (r == 0 && d != tests[i].expected) { + fprintf (stderr, + "Wrong result for %s, got %g, expected %g\n", + tests[i].str, d, tests[i].expected); + pass = false; + } + if ((r == -1) != error_flagged) { + fprintf (stderr, "Wrong error message handling for %s\n", tests[i].str); + pass = false; + } + } + + return pass; +} + static bool test_nbdkit_parse_ints (void) { @@ -503,6 +575,7 @@ main (int argc, char *argv[]) { bool pass = true; pass &= test_nbdkit_parse_size (); + pass &= test_nbdkit_parse_probability (); pass &= test_nbdkit_parse_ints (); pass &= test_nbdkit_read_password (); /* nbdkit_absolute_path and nbdkit_nanosleep not unit-tested here, but diff --git a/plugins/ocaml/NBDKit.mli b/plugins/ocaml/NBDKit.mli index 81447d07d..bc190f267 100644 --- a/plugins/ocaml/NBDKit.mli +++ b/plugins/ocaml/NBDKit.mli @@ -134,9 +134,9 @@ val register_plugin : into [EINVAL]. *) val set_error : Unix.error -> unit
-(** Bindings for [nbdkit_parse_size], [nbdkit_parse_bool] and - [nbdkit_read_password]. See nbdkit-plugin(3) for information - about these functions. +(** Bindings for [nbdkit_parse_size], [nbdkit_parse_probability], + [nbdkit_parse_bool] and [nbdkit_read_password]. See + nbdkit-plugin(3) for information about these functions.
On error these functions all raise [Invalid_argument]. The actual error is sent to the nbdkit error log and is not @@ -145,10 +145,11 @@ val set_error : Unix.error -> unit (* Note OCaml has functions already for parsing other integers, so * there is no need to bind them here. We only bind the functions * which have special abilities in nbdkit: [parse_size] can parse - * human sizes, [parse_bool] parses a range of nbdkit-specific - * boolean strings, and [read_password] suppresses echo. + * human sizes, [parse_probability] and [parse_bool] parses a range + * of nbdkit-specific strings, and [read_password] suppresses echo. *) val parse_size : string -> int64 +val parse_probability : string -> string -> float val parse_bool : string -> bool val read_password : string -> string
diff --git a/plugins/ocaml/NBDKit.ml b/plugins/ocaml/NBDKit.ml index e1cf28c94..2d1696917 100644 --- a/plugins/ocaml/NBDKit.ml +++ b/plugins/ocaml/NBDKit.ml @@ -160,6 +160,8 @@ let register_plugin ~name (* Bindings to nbdkit server functions. *) external set_error : Unix.error -> unit = "ocaml_nbdkit_set_error" [@@noalloc] external parse_size : string -> int64 = "ocaml_nbdkit_parse_size" +external parse_probability : string -> string -> float = + "ocaml_nbdkit_parse_probability" external parse_bool : string -> bool = "ocaml_nbdkit_parse_bool" external read_password : string -> string = "ocaml_nbdkit_read_password" external realpath : string -> string = "ocaml_nbdkit_realpath" diff --git a/plugins/ocaml/bindings.c b/plugins/ocaml/bindings.c index f2c9ca07d..4885feac5 100644 --- a/plugins/ocaml/bindings.c +++ b/plugins/ocaml/bindings.c @@ -74,6 +74,22 @@ ocaml_nbdkit_parse_size (value strv) CAMLreturn (rv); }
+NBDKIT_DLL_PUBLIC value +ocaml_nbdkit_parse_probability (value whatv, value strv) +{ + CAMLparam2 (whatv, strv); + CAMLlocal1 (dv); + int r; + double d; + + r = nbdkit_parse_probability (String_val (whatv), String_val (strv), &d); + if (r == -1) + caml_invalid_argument ("nbdkit_parse_probability"); + dv = caml_copy_double (d); + + CAMLreturn (dv); +} + NBDKIT_DLL_PUBLIC value ocaml_nbdkit_parse_bool (value strv) { diff --git a/plugins/python/modfunctions.c b/plugins/python/modfunctions.c index 479707e78..74bfd6f27 100644 --- a/plugins/python/modfunctions.c +++ b/plugins/python/modfunctions.c @@ -122,11 +122,32 @@ parse_size (PyObject *self, PyObject *args) return PyLong_FromSize_t ((size_t)size); }
+/* nbdkit.parse_probability */ +static PyObject * +parse_probability (PyObject *self, PyObject *args) +{ + const char *what, *str; + double d; + + if (!PyArg_ParseTuple (args, "ss:parse_probability", &what, &str)) + return NULL; + + if (nbdkit_parse_probability (what, str, &d) == -1) { + PyErr_SetString (PyExc_ValueError, + "Unable to parse string as probability"); + return NULL; + } + + return PyFloat_FromDouble (d); +} + static PyMethodDef NbdkitMethods[] = { { "debug", debug, METH_VARARGS, "Print a debug message" }, { "export_name", export_name, METH_NOARGS, "Return the optional export name negotiated with the client" }, + { "parse_probability", parse_probability, METH_VARARGS, + "Parse probability strings into floating point number" }, { "parse_size", parse_size, METH_VARARGS, "Parse human-readable size strings into bytes" }, { "set_error", set_error, METH_VARARGS, diff --git a/tests/test-python-plugin.py b/tests/test-python-plugin.py index c3232a112..7f3a2c2e4 100644 --- a/tests/test-python-plugin.py +++ b/tests/test-python-plugin.py @@ -55,8 +55,20 @@ class TestAPI(unittest.TestCase): with self.assertRaises(ValueError): nbdkit.parse_size('foo')
+ def test_parse_probability(self): + self.assertEqual(nbdkit.parse_probability('test', '1:10'), 0.1) + self.assertEqual(nbdkit.parse_probability('test', '100%'), 1) + self.assertEqual(nbdkit.parse_probability('test', '0'), 0) + + with self.assertRaises(TypeError): + nbdkit.parse_probability('test', 17) + + with self.assertRaises(ValueError): + nbdkit.parse_probability('test', 'bar') +
TestAPI().test_parse_size() +TestAPI().test_parse_probability()
def config(k, v): diff --git a/tests/test_ocaml_plugin.ml b/tests/test_ocaml_plugin.ml index 8132de8f8..bf998d361 100644 --- a/tests/test_ocaml_plugin.ml +++ b/tests/test_ocaml_plugin.ml @@ -39,6 +39,7 @@ let sparse = Bytes.make nr_sectors '\000' (* sparseness bitmap *) (* Test parse_* functions. *) let () = assert (NBDKit.parse_size "1M" = Int64.of_int (1024*1024)); + assert (NBDKit.parse_probability "test parse probability" "1:10" = 0.1); assert (NBDKit.parse_bool "true" = true); assert (NBDKit.parse_bool "0" = false)
On Tue, May 16, 2023 at 07:20:16PM +0200, Laszlo Ersek wrote:
On 5/16/23 14:12, Richard W.M. Jones wrote:
In nbdkit-error-filter we need to parse parameters as probabilities. This is useful enough to add to nbdkit, since we will use it in another filter in future. ---
I'll start with the good, before focusing on the questionable. You make a compelling argument about wanting to reuse already-existing code for parsing a percentage. It is indeed useful to have a single utility function, to be reused by multiple plugins and filters, so that we have consistent grammars for what we are willing to accept (rather than multiple ad hoc parsers being subtly different), and where we can fix any bugs or add new supported parses in just one location. So that is a strong argument in favor of this patch if we can justify why having a floating point error representation in the first place is worthwhile. The latter, of course, is harder to argue; so just because this patch is good at eliminating redundancy does not necessarily mean it is a good idea to use floating point.
+=head2 Parsing probabilities + +Use the C<nbdkit_parse_probability> utility function to parse +probabilities. Common formats understood include: C<"0.1">, C<"10%"> +or C<"1:10">, which all mean a probability of 1 in 10. + + int nbdkit_parse_probability (const char *what, const char *str, + double *ret); + +The C<what> parameter is printed in error messages to provide context. +The C<str> parameter is the probability string. + +On success the function returns C<0> and sets C<*ret>. B<Note> that +the probability returned may be outside the range S<[ 0.0..1.0 ]>, for +example if C<str == "200%">. If you want to clamp the result you must +check that yourself.
Would it be helpful if the utility function included bounds that the result must lie between? As in: if (nbdkit_parse_probability ("my function", str, 0.0, 1.0, &value) == -1) return -1; where code that wants to allow larger than 100% can do so by passing different bounds?
+NBDKIT_DLL_PUBLIC int +nbdkit_parse_probability (const char *what, const char *str, + double *retp) +{ + double d, d2; + char c; + int n; + + if (sscanf (str, "%lg%[:/]%lg%n", &d, &c, &d2, &n) == 3 && + strcmp (&str[n], "") == 0) { /* N:M or N/M */
This accepts LOTS of strings. Maybe that is intentional, but still, it accepts more than you documented. For example, it accepts "-inf:nan(0x0)", but only on some platforms (since expanded nan(...) sequences are implementation defined), even though I can't possibly see how that makes for a valid percentage.
+ if (d == 0 && d2 == 0) /* 0/0 is OK */ + ;
So your intent is to allow bypassing 0/0 to instead behave identically to 0%.
+ else if (d2 == 0) /* N/0 is bad */ + goto bad_parse; + else + d /= d2;
I don't want to be a spoilsport, but this division makes me extra nervous [1], on top of parsing floating point *at all* [2].
[2] Eric has just posted a 19-part series, v2, for QEMU, for fixing the numerous issues in QEMU's floating point parser. Personal opinion: QEMU doesn't even have a *valid reason* for parsing floating point! All QEMU deals with are *integer quantities* such as disk images consisting of whole numbers of bytes! But again, that's just a personal opinion.
No offense taken. And while you are correct that my v2 series for qemu clocked in at 19 patches, it doesn't necessarily translate to 19 bugs fixed (although it was definitely more than one), nor were they all in floating point (one of the bugs was in qemu_strtoui() which is integer only). In short, my biggest time sink there was fixing technical debt on needing a LOT more unit tests to make sure I wasn't inadvertently breaking some corner case (and with strtod() or scanf("%g"), there are a LOT of those). Still, being able to write 1.5G rather than 1610612736 explains why qemu goes to the bother of attempting to allow certain floating point strings. So inspired by your concern, I just took another look at nbdkit_parse_size(), which currently has rather terse public documentation of: | Use the C<nbdkit_parse_size> utility function to parse human-readable | size strings such as "100M" into the size in bytes. | | int64_t nbdkit_parse_size (const char *str); | | C<str> can be a string in a number of common formats. The function | returns the size in bytes. If there was an error, it returns C<-1>. but where you are better reading server/public.c to see what we actually parse, along with server/test-public.c:test_nbdkit_parse_size() for what we promise not to break (currently, no strings with '.' are in our explicitly supported set). The former has: /* XXX Should we also parse things like '1.5M'? */ /* XXX Should we allow hex? If so, hex cannot use scaling suffixes, * because some of them are valid hex digits */ which are some of the very corner cases I was just dealing with in qemu's qemu_strtosz(); and the latter has its own shortfalls (for example, classifying "8E" as a bogus string, instead of in the section of strings leading to overflow - the real reason we reject 8E is because it doesn't fit as a positive value in off_t). Alas, since qemu has a stricter license, I can't just copy my work there over to nbdkit without also exercising my right as author to dual-license it more permissively. But the way our docs are currently written, we do seem to reserve the right to make strings that currently fail to parse start validly parsing in the future (such as 1.5M).
[1] I maintain that floating point is only a part of the C language so that C could be made "competitive" with Fortran. Therefore I honestly believe that *no* floating point should be done in C without fully engaging in numerical analysis. I'm not up to that -- I've had numerical analysis in college, and I remember just enough of it to steer the heck clear of it. In C99, there's a whole chapter dedicated to the floating point environment (7.6 Floating-point environment <fenv.h>), and there's also the normative Annex F ("IEC 60559 floating-point arithmetic").
In this particular case, we have a floating point division. The divisor "d2" can be an extremely small *positive* number (DBL_MIN, or another value with a very small positive mantissa and a huge absolute value negative exponent, like FLT_RADIX raised to DBL_MIN_EXP), and the dividend "d" may be a huge positive number (DBL_MAX, or another value with a large positive mantissa and a huge positive exponent like FLT_RADIX raised to DBL_MAX_EXP).
The quotient d/d2 is then almost certainly not representable in the type -- the resultant exponent would have to be about (DBL_MAX_EXP - DBL_MIN_EXP), which in practice is about 2 * DBL_MAX_EXP -- and there's just not another exponent bit available in the type for that.
And I can't even say whether that would result in a silent NaN, or a silent positive infinity, or a floating point exception. I don't like code that I can't reason about (even if it is ultimately my fault, for not knowing the language well enough).
C is a lot looser here than other languages. For example, Java took pains to define that division by 0 or infinity produces platform-independent reliable results (at the expense of someone writing a Java virtual machine having to do slower implementations which special case anything that the hardware does not natively do in the same manner). At any rate, I agree with you that floating point division, when you have not validated that the unbounded-precision result won't overflow/underflow under rounding scenarios, is not trivial to think about.
Relatedly... in patch#5, we have:
+ block_size = next_power_of_2 ((uint64_t) (100. / evil_probability));
where "evil_probability" comes from nbdkit_parse_probability(), and is checked separately to be in [0, 1] (both boundaries inclusive, per the code).
So, evil_probability==0 will produce a division by zero here, but even if we assume that's just a typo and we actually mean to exclude 0, the user can still provide a value near DBL_MIN on the command line, like 1E-37. 100 is 1E+2, so the quotient is 1E+39. Representing 10^39 in binary requires ceil(39 * log2(10)) bits -- that's 130 bits; uint64_t is too small for that. And then the following applies from C99:
6.3.1.4 Real floating and integer
When a finite value of real floating type is converted to an integer type other than _Bool, the fractional part is discarded (i.e., the value is truncated toward zero). If the value of the integral part cannot be represented by the integer type, the behavior is undefined. [Footnote 50]
Footnote 50:
The remaindering operation performed when a value of integer type is converted to unsigned type need not be performed when a value of real floating type is converted to unsigned type. Thus, the range of portable real floating values is (−1, Utype_MAX+1).
Oh, so my assumption (in my reply to patch 5, before replying to this email) that (uint64_t)INFINITY produces UINT64_MAX is invalid (again, maybe something I'm remembering from Java taking pains to explicitly specify that). It may happen to do so, but other values are also possible, and the compiler can also use this explicit promise of UB to optimize things differently than we would like. Yeah, this really is a bear-trap.
(Note the round parens in the footnote: it means the boundaries are *excluded*. So, a value like -0.5 will be truncated to zero, and a value like UINT64_MAX + 0.5 will be truncated to UINT64_MAX, but (-1) itself and (UINT64_MAX + 1) itself are not permitted already.)
I challenge you to find a system where 'double' can hold the value UINT64_MAX + 0.5 with sufficient precision (IEEE double only requires 51 bits of precision). In fact, some of the back-story of my work on qemu's floating point parser was an earlier bug report, raised by nbdkit's unit testing, when we discovered that qemu was rounding large values (because of its trip through 'double') rather than matching an integral parse (found when qemu was unable to produce large sparse images as large as nbdkit because of the lost precision). Semi-related, just last week, I also fixed a bug in glib where it was assuming that the round trip (uint64_t)(long double)(uint64_t)value would not lose precision, which happens to be the case on x86_64 but is not true on other hardware; but here we're using sscanf with 'double' not 'long double'.
I recommend the following: take two unsigned integers, numerator "a" and denominator "b", from the command line. We know how to parse those safely.
Maintain those values separately.
In every calculation where we need to multiply x by a/b, calculate (x*a)/b, and use MUL_OVERFLOW() for the multiplication. Where we need to divide x by (a/b), use (x*b)/a, again with MUL_OVERFLOW(). (And of course the divisor must never be 0.)
In case we can determine the possible range for "x" *in advance*, for example because we know we're going to divide x=100 by (a/b), we can *also* determine the safe range for "a" and "b" as well -- for x=100, x*b must fit in a uint64_t, so "b" must not exceed UINT64_MAX/100, and that can be verified safely after parsing.
Floating point is in fact *supposed* to take away all this messing, and "compress" the ratio into the mantissa, and set the exponent (the scale) accordingly. But the simplicity is deceiving, due to cancellation, error accumulation, etc. (Cue the articles "what every programmer should know about floating point".)
I don't think I can *safely* use floating point, I can only say when something looks unsafe. Maintaining two positive integers (numerator and denominator) is more work, but I can at least *reason* about those.
If Eric is OK with this patch set, I won't try to block it, it just makes me feel very uncomfortable. It's more than just scanf() lacking proper internal error handling; the real complications come when we perform operations on the floating point values.
Our pre-existing error filter is already doing percentage calculations via floating point, so on the grounds that this patch is consolidating common code patterns to avoid reimplementation, we're good. But as you say, representing things as a ratio between two integers may be more maintainable than floating point where accuracy matters, or this may be a case where we are explicit that use of the floating point fractions as a percentage is intentionally liable to rounding issues. Still, avoiding undefined behavior when the division can overflow (whether that be the overflow to floating point infinity or even the overflow beyond UINT64_MAX), does make it worth questioning if floating point is our best representation, or at a minimum if we want to be stricter in what we parse before passing a substring on to strtod() so that we have more control over the values (part of my 19 patches to qemu was explicitly truncating any string at 'e' or 'E' so that strtod() could not do an exponent parse that would inadverently hit overflow to INFINITY). -- Eric Blake, Principal Software Engineer Red Hat, Inc. +1-919-301-3266 Virtualization: qemu.org | libvirt.org
On Tue, May 16, 2023 at 02:35:38PM -0500, Eric Blake wrote:
+=head2 Parsing probabilities + +Use the C<nbdkit_parse_probability> utility function to parse +probabilities. Common formats understood include: C<"0.1">, C<"10%"> +or C<"1:10">, which all mean a probability of 1 in 10. + + int nbdkit_parse_probability (const char *what, const char *str, + double *ret); + +The C<what> parameter is printed in error messages to provide context. +The C<str> parameter is the probability string. + +On success the function returns C<0> and sets C<*ret>. B<Note> that +the probability returned may be outside the range S<[ 0.0..1.0 ]>, for +example if C<str == "200%">. If you want to clamp the result you must +check that yourself.
Would it be helpful if the utility function included bounds that the result must lie between? As in:
if (nbdkit_parse_probability ("my function", str, 0.0, 1.0, &value) == -1) return -1;
where code that wants to allow larger than 100% can do so by passing different bounds?
I had an earlier version which attempted this, but the problem is it's hard to describe when the upper or lower limit is not bounded. Or at least you'd need to add flags which makes the binding in other languages more difficult.
+NBDKIT_DLL_PUBLIC int +nbdkit_parse_probability (const char *what, const char *str, + double *retp) +{ + double d, d2; + char c; + int n; + + if (sscanf (str, "%lg%[:/]%lg%n", &d, &c, &d2, &n) == 3 && + strcmp (&str[n], "") == 0) { /* N:M or N/M */
This accepts LOTS of strings. Maybe that is intentional, but still, it accepts more than you documented. For example, it accepts "-inf:nan(0x0)", but only on some platforms (since expanded nan(...) sequences are implementation defined), even though I can't possibly see how that makes for a valid percentage.
+ if (d == 0 && d2 == 0) /* 0/0 is OK */ + ;
So your intent is to allow bypassing 0/0 to instead behave identically to 0%.
+ else if (d2 == 0) /* N/0 is bad */ + goto bad_parse; + else + d /= d2;
I don't want to be a spoilsport, but this division makes me extra nervous [1], on top of parsing floating point *at all* [2].
[2] Eric has just posted a 19-part series, v2, for QEMU, for fixing the numerous issues in QEMU's floating point parser. Personal opinion: QEMU doesn't even have a *valid reason* for parsing floating point! All QEMU deals with are *integer quantities* such as disk images consisting of whole numbers of bytes! But again, that's just a personal opinion.
No offense taken. And while you are correct that my v2 series for qemu clocked in at 19 patches, it doesn't necessarily translate to 19 bugs fixed (although it was definitely more than one), nor were they all in floating point (one of the bugs was in qemu_strtoui() which is integer only). In short, my biggest time sink there was fixing technical debt on needing a LOT more unit tests to make sure I wasn't inadvertently breaking some corner case (and with strtod() or scanf("%g"), there are a LOT of those).
Still, being able to write 1.5G rather than 1610612736 explains why qemu goes to the bother of attempting to allow certain floating point strings. So inspired by your concern, I just took another look at nbdkit_parse_size(), which currently has rather terse public documentation of:
| Use the C<nbdkit_parse_size> utility function to parse human-readable | size strings such as "100M" into the size in bytes. | | int64_t nbdkit_parse_size (const char *str); | | C<str> can be a string in a number of common formats. The function | returns the size in bytes. If there was an error, it returns C<-1>.
but where you are better reading server/public.c to see what we actually parse, along with server/test-public.c:test_nbdkit_parse_size() for what we promise not to break (currently, no strings with '.' are in our explicitly supported set). The former has:
/* XXX Should we also parse things like '1.5M'? */ /* XXX Should we allow hex? If so, hex cannot use scaling suffixes, * because some of them are valid hex digits */
which are some of the very corner cases I was just dealing with in qemu's qemu_strtosz(); and the latter has its own shortfalls (for example, classifying "8E" as a bogus string, instead of in the section of strings leading to overflow - the real reason we reject 8E is because it doesn't fit as a positive value in off_t). Alas, since qemu has a stricter license, I can't just copy my work there over to nbdkit without also exercising my right as author to dual-license it more permissively. But the way our docs are currently written, we do seem to reserve the right to make strings that currently fail to parse start validly parsing in the future (such as 1.5M).
[1] I maintain that floating point is only a part of the C language so that C could be made "competitive" with Fortran. Therefore I honestly believe that *no* floating point should be done in C without fully engaging in numerical analysis. I'm not up to that -- I've had numerical analysis in college, and I remember just enough of it to steer the heck clear of it. In C99, there's a whole chapter dedicated to the floating point environment (7.6 Floating-point environment <fenv.h>), and there's also the normative Annex F ("IEC 60559 floating-point arithmetic").
In this particular case, we have a floating point division. The divisor "d2" can be an extremely small *positive* number (DBL_MIN, or another value with a very small positive mantissa and a huge absolute value negative exponent, like FLT_RADIX raised to DBL_MIN_EXP), and the dividend "d" may be a huge positive number (DBL_MAX, or another value with a large positive mantissa and a huge positive exponent like FLT_RADIX raised to DBL_MAX_EXP).
The quotient d/d2 is then almost certainly not representable in the type -- the resultant exponent would have to be about (DBL_MAX_EXP - DBL_MIN_EXP), which in practice is about 2 * DBL_MAX_EXP -- and there's just not another exponent bit available in the type for that.
And I can't even say whether that would result in a silent NaN, or a silent positive infinity, or a floating point exception. I don't like code that I can't reason about (even if it is ultimately my fault, for not knowing the language well enough).
C is a lot looser here than other languages. For example, Java took pains to define that division by 0 or infinity produces platform-independent reliable results (at the expense of someone writing a Java virtual machine having to do slower implementations which special case anything that the hardware does not natively do in the same manner). At any rate, I agree with you that floating point division, when you have not validated that the unbounded-precision result won't overflow/underflow under rounding scenarios, is not trivial to think about.
Relatedly... in patch#5, we have:
+ block_size = next_power_of_2 ((uint64_t) (100. / evil_probability));
where "evil_probability" comes from nbdkit_parse_probability(), and is checked separately to be in [0, 1] (both boundaries inclusive, per the code).
So, evil_probability==0 will produce a division by zero here, but even if we assume that's just a typo and we actually mean to exclude 0, the user can still provide a value near DBL_MIN on the command line, like 1E-37. 100 is 1E+2, so the quotient is 1E+39. Representing 10^39 in binary requires ceil(39 * log2(10)) bits -- that's 130 bits; uint64_t is too small for that. And then the following applies from C99:
6.3.1.4 Real floating and integer
When a finite value of real floating type is converted to an integer type other than _Bool, the fractional part is discarded (i.e., the value is truncated toward zero). If the value of the integral part cannot be represented by the integer type, the behavior is undefined. [Footnote 50]
Footnote 50:
The remaindering operation performed when a value of integer type is converted to unsigned type need not be performed when a value of real floating type is converted to unsigned type. Thus, the range of portable real floating values is (−1, Utype_MAX+1).
Oh, so my assumption (in my reply to patch 5, before replying to this email) that (uint64_t)INFINITY produces UINT64_MAX is invalid (again, maybe something I'm remembering from Java taking pains to explicitly specify that). It may happen to do so, but other values are also possible, and the compiler can also use this explicit promise of UB to optimize things differently than we would like. Yeah, this really is a bear-trap.
(Note the round parens in the footnote: it means the boundaries are *excluded*. So, a value like -0.5 will be truncated to zero, and a value like UINT64_MAX + 0.5 will be truncated to UINT64_MAX, but (-1) itself and (UINT64_MAX + 1) itself are not permitted already.)
I challenge you to find a system where 'double' can hold the value UINT64_MAX + 0.5 with sufficient precision (IEEE double only requires 51 bits of precision). In fact, some of the back-story of my work on qemu's floating point parser was an earlier bug report, raised by nbdkit's unit testing, when we discovered that qemu was rounding large values (because of its trip through 'double') rather than matching an integral parse (found when qemu was unable to produce large sparse images as large as nbdkit because of the lost precision). Semi-related, just last week, I also fixed a bug in glib where it was assuming that the round trip (uint64_t)(long double)(uint64_t)value would not lose precision, which happens to be the case on x86_64 but is not true on other hardware; but here we're using sscanf with 'double' not 'long double'.
I recommend the following: take two unsigned integers, numerator "a" and denominator "b", from the command line. We know how to parse those safely.
Maintain those values separately.
In every calculation where we need to multiply x by a/b, calculate (x*a)/b, and use MUL_OVERFLOW() for the multiplication. Where we need to divide x by (a/b), use (x*b)/a, again with MUL_OVERFLOW(). (And of course the divisor must never be 0.)
In case we can determine the possible range for "x" *in advance*, for example because we know we're going to divide x=100 by (a/b), we can *also* determine the safe range for "a" and "b" as well -- for x=100, x*b must fit in a uint64_t, so "b" must not exceed UINT64_MAX/100, and that can be verified safely after parsing.
Floating point is in fact *supposed* to take away all this messing, and "compress" the ratio into the mantissa, and set the exponent (the scale) accordingly. But the simplicity is deceiving, due to cancellation, error accumulation, etc. (Cue the articles "what every programmer should know about floating point".)
I don't think I can *safely* use floating point, I can only say when something looks unsafe. Maintaining two positive integers (numerator and denominator) is more work, but I can at least *reason* about those.
If Eric is OK with this patch set, I won't try to block it, it just makes me feel very uncomfortable. It's more than just scanf() lacking proper internal error handling; the real complications come when we perform operations on the floating point values.
Our pre-existing error filter is already doing percentage calculations via floating point, so on the grounds that this patch is consolidating common code patterns to avoid reimplementation, we're good. But as you say, representing things as a ratio between two integers may be more maintainable than floating point where accuracy matters, or this may be a case where we are explicit that use of the floating point fractions as a percentage is intentionally liable to rounding issues. Still, avoiding undefined behavior when the division can overflow (whether that be the overflow to floating point infinity or even the overflow beyond UINT64_MAX), does make it worth questioning if floating point is our best representation, or at a minimum if we want to be stricter in what we parse before passing a substring on to strtod() so that we have more control over the values (part of my 19 patches to qemu was explicitly truncating any string at 'e' or 'E' so that strtod() could not do an exponent parse that would inadverently hit overflow to INFINITY).
I'm not really sure we reached a conclusion so far, but I did want to say that I changed the evil filter impl so that it now treats any 0 <= P < 1e-12 as effectively 0. (P == evil-probability; P < 0 and P > 1 are still rejected at config time as before). With P == 1e-12: nbdkit: debug: evil: mode: stuck-bits, P: 1e-12 nbdkit: debug: evil: block_size: 17592186044416 (2**44) nbdkit: debug: evil: expected bits per block: 140.737 (The large block size isn't an issue here as nothing is allocated. However it would be a problem if the block_size calculation overflows, and I believe that limiting P to larger values avoids this.) Also I'm not sure that handling probabilities as a numerator and denominator actually helps here? Both still need to be stored as floats, so it just pushes the same problem to the plugin. Rich. -- Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones Read my programming and virtualization blog: http://rwmj.wordpress.com nbdkit - Flexible, fast NBD server with plugins https://gitlab.com/nbdkit/nbdkit
On Tue, May 16, 2023 at 09:22:31PM +0100, Richard W.M. Jones wrote:
I'm not really sure we reached a conclusion so far, but I did want to say that I changed the evil filter impl so that it now treats any 0 <= P < 1e-12 as effectively 0. (P == evil-probability; P < 0 and P > 1 are still rejected at config time as before).
With P == 1e-12:
nbdkit: debug: evil: mode: stuck-bits, P: 1e-12 nbdkit: debug: evil: block_size: 17592186044416 (2**44) nbdkit: debug: evil: expected bits per block: 140.737
(The large block size isn't an issue here as nothing is allocated. However it would be a problem if the block_size calculation overflows, and I believe that limiting P to larger values avoids this.)
To clarify what I meant ... We aim to choose a block size where about 100 bits are corrupted in the block, which limits the time taken when the code loops over the block. Since the block size must also be a power of 2, it ends up containing slightly more corrupted bits (on average 140 in the case above). The block size is calculated as the reciprocal of P. By limiting P to be either "effectively 0", or in the range [1e-12 .. 1], we avoid creating blocks larger than 2**44. If P < 1e-12 then it is handled by a separate code path and treated as zero. If P > 1e-12 then the block size will be smaller than above. So my reasoning is that this should not overflow anything.
Also I'm not sure that handling probabilities as a numerator and denominator actually helps here? Both still need to be stored as floats, so it just pushes the same problem to the plugin.
Rich. -- Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones Read my programming and virtualization blog: http://rwmj.wordpress.com virt-p2v converts physical machines to virtual machines. Boot with a live CD or over the network (PXE) and turn machines into KVM guests. http://libguestfs.org/virt-v2v
On 5/16/23 22:22, Richard W.M. Jones wrote:
On Tue, May 16, 2023 at 02:35:38PM -0500, Eric Blake wrote:
Our pre-existing error filter is already doing percentage calculations via floating point, so on the grounds that this patch is consolidating common code patterns to avoid reimplementation, we're good. But as you say, representing things as a ratio between two integers may be more maintainable than floating point where accuracy matters, or this may be a case where we are explicit that use of the floating point fractions as a percentage is intentionally liable to rounding issues. Still, avoiding undefined behavior when the division can overflow (whether that be the overflow to floating point infinity or even the overflow beyond UINT64_MAX), does make it worth questioning if floating point is our best representation, or at a minimum if we want to be stricter in what we parse before passing a substring on to strtod() so that we have more control over the values (part of my 19 patches to qemu was explicitly truncating any string at 'e' or 'E' so that strtod() could not do an exponent parse that would inadverently hit overflow to INFINITY).
I'm not really sure we reached a conclusion so far, but I did want to say that I changed the evil filter impl so that it now treats any 0 <= P < 1e-12 as effectively 0. (P == evil-probability; P < 0 and P > 1 are still rejected at config time as before).
With P == 1e-12:
nbdkit: debug: evil: mode: stuck-bits, P: 1e-12 nbdkit: debug: evil: block_size: 17592186044416 (2**44) nbdkit: debug: evil: expected bits per block: 140.737
(The large block size isn't an issue here as nothing is allocated. However it would be a problem if the block_size calculation overflows, and I believe that limiting P to larger values avoids this.)
Right, this is about the direction I could agree with -- and again I want to emphasize that you don't *need* my agreement to proceed with the floating point approach! I think enforcing a minimum for P could be useful too, for wherever we divide by P.
Also I'm not sure that handling probabilities as a numerator and denominator actually helps here? Both still need to be stored as floats, so it just pushes the same problem to the plugin.
No, the point with N/D is that they're both positive integers (well, N may be zero as well), and that they *together* give you a single rational probability, namely N/D. They'd be stored as separate unsigned integer fields everywhere, and the division would only be performed (in unsigned integer) wherever directly needed, such as in (a * N) / D. I don't know if this is compatible with existent code. If we already have code that parses floats (and Eric's comments imply we do), then that code couldn't be rebased on this N/D representation, compatibly. But, I'd consider introducing a new (in a way, "divergent") N/D representation a fair price, for not adding more floating point! Refactoring (extracting common code) is only useful if we can fix the extracted code later on, and that's a tough challenge with floating point. Laszlo
On 5/16/23 21:35, Eric Blake wrote:
On Tue, May 16, 2023 at 07:20:16PM +0200, Laszlo Ersek wrote:
On 5/16/23 14:12, Richard W.M. Jones wrote:
+ else if (d2 == 0) /* N/0 is bad */ + goto bad_parse; + else + d /= d2;
I don't want to be a spoilsport, but this division makes me extra nervous [1], on top of parsing floating point *at all* [2].
[2] Eric has just posted a 19-part series, v2, for QEMU, for fixing the numerous issues in QEMU's floating point parser. Personal opinion: QEMU doesn't even have a *valid reason* for parsing floating point! All QEMU deals with are *integer quantities* such as disk images consisting of whole numbers of bytes! But again, that's just a personal opinion.
No offense taken.
To clarify, I didn't believe it could in any way offend you, technically speaking; I thought my opinion could perhaps be considered offensive by the author of the original QEMU feature, i.e. by the developer who had introduced floating point parsing originally to QEMU (I don't know who that developer was). You're "only" fixing bugs in an existing feature (and improving its test coverage). I'm challenging the existence of the entire feature. I do agree that *IF* the feature exists, it should be reasonably bug-free.
And while you are correct that my v2 series for qemu clocked in at 19 patches, it doesn't necessarily translate to 19 bugs fixed (although it was definitely more than one), nor were they all in floating point (one of the bugs was in qemu_strtoui() which is integer only). In short, my biggest time sink there was fixing technical debt on needing a LOT more unit tests to make sure I wasn't inadvertently breaking some corner case (and with strtod() or scanf("%g"), there are a LOT of those).
Still, being able to write 1.5G rather than 1610612736 explains why qemu goes to the bother of attempting to allow certain floating point strings.
This is actually the core mistake, in my opinion. Preferring "one and half gigabytes" rather than "one billion, six hundred ten million, six hundred twelve thousand, seven hundred thirty six bytes", is understandable. What is *not* understandable, knowing the pitfalls of floating point (!), why the former form was equated with "parsing floating point". Note: I wrote "one and half gigabytes", not "one point five tenths gigabytes". Huge difference! In everyday speech, we use super simple fractions, with both numerator and denominator being very small natural numbers. And especially with multipliers such as K, M, G, T, which are powers of 2 (10, 20, 30, 40, respectively), I would argue that no denominators other than 2, 4 and maybe (!) 8 matter! (Who has ever said, "give me two thirds of a gigabyte"? Or "five sevenths"?) I totally don't see a user entering, as disk size, "1.234567G". I don't even see them entering "1.875G" ("one point eight hundred seventy five thousandths gigabytes"). At best I can see them say "two gigs minus an eighth gig", or "one plus seven eighths gig", but even for that, I need to squint. We don't actually *think* about sizes in numbers that have many digits after the decimal point. What we do is, we think in simple fractions, and have just learned how those simple fractions *look* when written as decimal numbers. So adding a general floating point parser was overkill; it must have looked attractive only because the complications of floating point were under-estimated. So QEMU should have added the following formats instead: - a[s] - b/c[s] - a+b/c[s] where "a" is your usual integer, [s] is an (optional) suffix like K or G, c may be 2, 4 or 8 (nothing else), and b may be [0 .. c-1]. If the suffix is omitted, it is taken as "byte", and then the second and third forms are not permitted (no fractions of bytes). Of course, hindsight is 20/20. I had learned to stay away from floating point very early on; topics in university like bounding errors and non-associativity of floating point addition made me look for articles on the web, and those had permanently convinced me that floating point is *unusable* unless you are able and willing to do complete numerical analysis in your C source code. In practice, C programmers don't even remember the integer promotions and the usual arithmetic conversions. :/ [...]
(Note the round parens in the footnote: it means the boundaries are *excluded*. So, a value like -0.5 will be truncated to zero, and a value like UINT64_MAX + 0.5 will be truncated to UINT64_MAX, but (-1) itself and (UINT64_MAX + 1) itself are not permitted already.)
I challenge you to find a system where 'double' can hold the value UINT64_MAX + 0.5 with sufficient precision (IEEE double only requires 51 bits of precision).
This was just an example (independent of actual fp precision) to illustrate the meaning of the round parens in the footnote. "long double" would work equally well for the example.
In fact, some of the back-story of my work on qemu's floating point parser was an earlier bug report, raised by nbdkit's unit testing, when we discovered that qemu was rounding large values (because of its trip through 'double') rather than matching an integral parse (found when qemu was unable to produce large sparse images as large as nbdkit because of the lost precision). Semi-related, just last week, I also fixed a bug in glib where it was assuming that the round trip (uint64_t)(long double)(uint64_t)value would not lose precision, which happens to be the case on x86_64 but is not true on other hardware;
I remember :)
but here we're using sscanf with 'double' not 'long double'.
Again: yes. This was only a tangent. I meant to quote the fp->integer conversion rule, and then I thought the related footnote deserved additional (but independent) reasoning. By that point I didn't feel tied to "double" any longer, really. [...]
If Eric is OK with this patch set, I won't try to block it, it just makes me feel very uncomfortable. It's more than just scanf() lacking proper internal error handling; the real complications come when we perform operations on the floating point values.
Our pre-existing error filter is already doing percentage calculations via floating point, so on the grounds that this patch is consolidating common code patterns to avoid reimplementation, we're good.
Agreed.
But as you say, representing things as a ratio between two integers may be more maintainable than floating point where accuracy matters, or this may be a case where we are explicit that use of the floating point fractions as a percentage is intentionally liable to rounding issues.
I think that, for using floating point, we should: - error-check any conversion from string to binary (object) representation, - bound the parsed values as early as possible, with an eye towards later use, - in each subsequent operation, show that the result will be in range, and (hopefully) will not see catastrophic loss of precision. I don't insist on this; it's just what I could explicitly ACK.
Still, avoiding undefined behavior when the division can overflow (whether that be the overflow to floating point infinity or even the overflow beyond UINT64_MAX), does make it worth questioning if floating point is our best representation, or at a minimum if we want to be stricter in what we parse before passing a substring on to strtod() so that we have more control over the values (part of my 19 patches to qemu was explicitly truncating any string at 'e' or 'E' so that strtod() could not do an exponent parse that would inadverently hit overflow to INFINITY).
*shudder*. :) I didn't read your patches in detail BTW. I went through the subjects in order, and looked at some details. I could tell it required an immense amount of thinking and work. Dealing with (unsigned!) integers is less work, IMO. Thanks! Laszlo
This replaces the existing ad hoc parsing with the new public function. --- filters/error/nbdkit-error-filter.pod | 12 +++++++----- filters/error/error.c | 14 +------------- 2 files changed, 8 insertions(+), 18 deletions(-) diff --git a/filters/error/nbdkit-error-filter.pod b/filters/error/nbdkit-error-filter.pod index bedd97924..49f21d10a 100644 --- a/filters/error/nbdkit-error-filter.pod +++ b/filters/error/nbdkit-error-filter.pod @@ -6,7 +6,7 @@ nbdkit-error-filter - inject errors for testing clients nbdkit --filter=error PLUGIN [error=EPERM|EIO|ENOMEM|EINVAL|ENOSPC|ESHUTDOWN] - [error-rate=10%|0.1] + [error-rate=10%|0.1|1:10] [error-file=/tmp/inject] [error-pread=...] [error-pread-rate=...] [error-pread-file=...] [error-pwrite=...] [error-pwrite-rate=...] [error-pwrite-file=...] @@ -66,11 +66,13 @@ This parameter is optional and the default is C<EIO> =item B<error-rate=>0..1 +=item B<error-rate=>NB<:>M + The rate of injected errors per NBD request. This can be expressed as -either a percentage between C<0%> and C<100%> or as a probability -between C<0> and C<1>. If C<0%> or C<0> is used then no errors are -ever injected, and if C<100%> or C<1> is used then all requests return -errors. +a percentage between C<0%> and C<100%>, or as a probability between +C<0> and C<1>, or as a ratio like C<1:10>. If C<0%> or C<0> is used +then no errors are ever injected, and if C<100%> or C<1> is used then +all requests return errors. This parameter is optional and the default is C<0%>. B<Unless you set this, the filter will do nothing.> diff --git a/filters/error/error.c b/filters/error/error.c index ac4da8c16..08e19e3bd 100644 --- a/filters/error/error.c +++ b/filters/error/error.c @@ -130,21 +130,9 @@ static int parse_error_rate (const char *key, const char *value, double *retp) { double d; - int n; - if (sscanf (value, "%lg%n", &d, &n) == 1) { - if (strcmp (&value[n], "%") == 0) /* percentage */ - d /= 100.0; - else if (strcmp (&value[n], "") == 0) /* probability */ - ; - else - goto bad_parse; - } - else { - bad_parse: - nbdkit_error ("%s: could not parse rate '%s'", key, value); + if (nbdkit_parse_probability (key, value, &d) == -1) return -1; - } if (d < 0 || d > 1) { nbdkit_error ("%s: rate out of range: '%s' parsed as %g", key, value, d); return -1; -- 2.39.2
It takes a 64 bit integer and finds the next power of 2, eg. next_power_of_2 (510) => 512 (2^9) Taken from https://jameshfisher.com/2018/03/30/round-up-power-2/ with some fixes. --- common/include/ispowerof2.h | 9 +++++++++ common/include/test-ispowerof2.c | 14 ++++++++++++++ 2 files changed, 23 insertions(+) diff --git a/common/include/ispowerof2.h b/common/include/ispowerof2.h index f067caf07..57ebcc4fd 100644 --- a/common/include/ispowerof2.h +++ b/common/include/ispowerof2.h @@ -59,4 +59,13 @@ log_2_bits (unsigned long v) return SIZEOF_LONG*8 - __builtin_clzl (v) - 1; } +/* Round up to next power of 2. + * https://jameshfisher.com/2018/03/30/round-up-power-2/ + */ +static inline uint64_t +next_power_of_2 (uint64_t x) +{ + return x == 1 ? 1 : UINT64_C(1) << (64 - __builtin_clzll (x-1)); +} + #endif /* NBDKIT_ISPOWEROF2_H */ diff --git a/common/include/test-ispowerof2.c b/common/include/test-ispowerof2.c index 9620192f0..fe37c4a32 100644 --- a/common/include/test-ispowerof2.c +++ b/common/include/test-ispowerof2.c @@ -68,5 +68,19 @@ main (void) assert (log_2_bits (0x8000000000000000) == 63); #endif + /* Test next power of 2. */ + assert (next_power_of_2 (1) == 1); + assert (next_power_of_2 (3) == 4); + assert (next_power_of_2 (8) == 8); + assert (next_power_of_2 (9) == 16); + assert (next_power_of_2 (0xffff) == 0x10000); + assert (next_power_of_2 (0x10000) == 0x10000); + assert (next_power_of_2 (UINT64_C ( 0xffffffff)) == 0x100000000); + assert (next_power_of_2 (UINT64_C (0x100000000)) == 0x100000000); + assert (next_power_of_2 (UINT64_C (0x200000001)) == 0x400000000); + assert (next_power_of_2 (UINT64_C (0x6ffffffff)) == 0x800000000); + assert (next_power_of_2 (UINT64_C (0x700000001)) == 0x800000000); + assert (next_power_of_2 (UINT64_C (0x800000000)) == 0x800000000); + exit (EXIT_SUCCESS); } -- 2.39.2
On Tue, May 16, 2023 at 01:12:17PM +0100, Richard W.M. Jones wrote:
It takes a 64 bit integer and finds the next power of 2, eg. next_power_of_2 (510) => 512 (2^9)
Taken from https://jameshfisher.com/2018/03/30/round-up-power-2/ with some fixes. --- common/include/ispowerof2.h | 9 +++++++++ common/include/test-ispowerof2.c | 14 ++++++++++++++ 2 files changed, 23 insertions(+)
diff --git a/common/include/ispowerof2.h b/common/include/ispowerof2.h index f067caf07..57ebcc4fd 100644 --- a/common/include/ispowerof2.h +++ b/common/include/ispowerof2.h @@ -59,4 +59,13 @@ log_2_bits (unsigned long v) return SIZEOF_LONG*8 - __builtin_clzl (v) - 1; }
+/* Round up to next power of 2. + * https://jameshfisher.com/2018/03/30/round-up-power-2/ + */ +static inline uint64_t +next_power_of_2 (uint64_t x) +{ + return x == 1 ? 1 : UINT64_C(1) << (64 - __builtin_clzll (x-1));
1ULL is generally shorter spelling for a 64-bit unsigned '1' than UINT64_C(1). On the other hand, it is not necessarily the same type, as some 64-bit platforms ahave uint64_t as 'unsigned long' instead of 'unsigned long long'; so being explicit avoids mental gyrations on deciphering whether the compiler has unexpected type promotion gotchas, so I like your spelling. next_power_of_2 (0) results in: 1ULL << (64 - __builtin_clzll (-1) 1ULL << (64 - 0) 1ULL << 64 which is undefined behavior. I'd prefer 'x <= 1 ? x : ...' to give us well-defined behavior...
+} + #endif /* NBDKIT_ISPOWEROF2_H */ diff --git a/common/include/test-ispowerof2.c b/common/include/test-ispowerof2.c index 9620192f0..fe37c4a32 100644 --- a/common/include/test-ispowerof2.c +++ b/common/include/test-ispowerof2.c @@ -68,5 +68,19 @@ main (void) assert (log_2_bits (0x8000000000000000) == 63); #endif
+ /* Test next power of 2. */ + assert (next_power_of_2 (1) == 1);
...as well as coverage of an input of 0.
+ assert (next_power_of_2 (3) == 4); + assert (next_power_of_2 (8) == 8); + assert (next_power_of_2 (9) == 16); + assert (next_power_of_2 (0xffff) == 0x10000); + assert (next_power_of_2 (0x10000) == 0x10000); + assert (next_power_of_2 (UINT64_C ( 0xffffffff)) == 0x100000000); + assert (next_power_of_2 (UINT64_C (0x100000000)) == 0x100000000); + assert (next_power_of_2 (UINT64_C (0x200000001)) == 0x400000000); + assert (next_power_of_2 (UINT64_C (0x6ffffffff)) == 0x800000000); + assert (next_power_of_2 (UINT64_C (0x700000001)) == 0x800000000); + assert (next_power_of_2 (UINT64_C (0x800000000)) == 0x800000000); + exit (EXIT_SUCCESS); } -- 2.39.2
-- Eric Blake, Principal Software Engineer Red Hat, Inc. +1-919-301-3266 Virtualization: qemu.org | libvirt.org
On Tue, May 16, 2023 at 07:29:45AM -0500, Eric Blake wrote:
On Tue, May 16, 2023 at 01:12:17PM +0100, Richard W.M. Jones wrote:
It takes a 64 bit integer and finds the next power of 2, eg. next_power_of_2 (510) => 512 (2^9)
Taken from https://jameshfisher.com/2018/03/30/round-up-power-2/ with some fixes. --- common/include/ispowerof2.h | 9 +++++++++ common/include/test-ispowerof2.c | 14 ++++++++++++++ 2 files changed, 23 insertions(+)
diff --git a/common/include/ispowerof2.h b/common/include/ispowerof2.h index f067caf07..57ebcc4fd 100644 --- a/common/include/ispowerof2.h +++ b/common/include/ispowerof2.h @@ -59,4 +59,13 @@ log_2_bits (unsigned long v) return SIZEOF_LONG*8 - __builtin_clzl (v) - 1; }
+/* Round up to next power of 2. + * https://jameshfisher.com/2018/03/30/round-up-power-2/ + */ +static inline uint64_t +next_power_of_2 (uint64_t x) +{ + return x == 1 ? 1 : UINT64_C(1) << (64 - __builtin_clzll (x-1));
1ULL is generally shorter spelling for a 64-bit unsigned '1' than UINT64_C(1). On the other hand, it is not necessarily the same type, as some 64-bit platforms ahave uint64_t as 'unsigned long' instead of 'unsigned long long'; so being explicit avoids mental gyrations on deciphering whether the compiler has unexpected type promotion gotchas, so I like your spelling.
Just a note here that the original code being copied [see link above] does not cast the 1 constant, and in fact does not work past 32 bits. I think it may be that the original code was tested on Windows which IIRC has 64 bit 'int'.
next_power_of_2 (0) results in:
1ULL << (64 - __builtin_clzll (-1) 1ULL << (64 - 0) 1ULL << 64
which is undefined behavior. I'd prefer 'x <= 1 ? x : ...' to give us well-defined behavior...
Good point, will fix.
#endif /* NBDKIT_ISPOWEROF2_H */ diff --git a/common/include/test-ispowerof2.c b/common/include/test-ispowerof2.c index 9620192f0..fe37c4a32 100644 --- a/common/include/test-ispowerof2.c +++ b/common/include/test-ispowerof2.c @@ -68,5 +68,19 @@ main (void) assert (log_2_bits (0x8000000000000000) == 63); #endif
+ /* Test next power of 2. */ + assert (next_power_of_2 (1) == 1);
...as well as coverage of an input of 0.
Ditto. Thanks, Rich. -- Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones Read my programming and virtualization blog: http://rwmj.wordpress.com virt-p2v converts physical machines to virtual machines. Boot with a live CD or over the network (PXE) and turn machines into KVM guests. http://libguestfs.org/virt-v2v
On 5/16/23 14:29, Eric Blake wrote:
On Tue, May 16, 2023 at 01:12:17PM +0100, Richard W.M. Jones wrote:
It takes a 64 bit integer and finds the next power of 2, eg. next_power_of_2 (510) => 512 (2^9)
Taken from https://jameshfisher.com/2018/03/30/round-up-power-2/ with some fixes. --- common/include/ispowerof2.h | 9 +++++++++ common/include/test-ispowerof2.c | 14 ++++++++++++++ 2 files changed, 23 insertions(+)
diff --git a/common/include/ispowerof2.h b/common/include/ispowerof2.h index f067caf07..57ebcc4fd 100644 --- a/common/include/ispowerof2.h +++ b/common/include/ispowerof2.h @@ -59,4 +59,13 @@ log_2_bits (unsigned long v) return SIZEOF_LONG*8 - __builtin_clzl (v) - 1; }
+/* Round up to next power of 2. + * https://jameshfisher.com/2018/03/30/round-up-power-2/ + */ +static inline uint64_t +next_power_of_2 (uint64_t x) +{ + return x == 1 ? 1 : UINT64_C(1) << (64 - __builtin_clzll (x-1));
1ULL is generally shorter spelling for a 64-bit unsigned '1' than UINT64_C(1). On the other hand, it is not necessarily the same type, as some 64-bit platforms ahave uint64_t as 'unsigned long' instead of 'unsigned long long'; so being explicit avoids mental gyrations on deciphering whether the compiler has unexpected type promotion gotchas, so I like your spelling.
I think the mental gyrations stay with us, just in reverse: __builtin_clzll() takes an "unsigned long long", but we're passing it a uint64_t. :) We might want to add: STATIC_ASSERT ( __builtin_types_compatible_p (unsigned long long, uint64_t), _ull_is_uint64 ); or something like that. Laszlo
next_power_of_2 (0) results in:
1ULL << (64 - __builtin_clzll (-1) 1ULL << (64 - 0) 1ULL << 64
which is undefined behavior. I'd prefer 'x <= 1 ? x : ...' to give us well-defined behavior...
+} + #endif /* NBDKIT_ISPOWEROF2_H */ diff --git a/common/include/test-ispowerof2.c b/common/include/test-ispowerof2.c index 9620192f0..fe37c4a32 100644 --- a/common/include/test-ispowerof2.c +++ b/common/include/test-ispowerof2.c @@ -68,5 +68,19 @@ main (void) assert (log_2_bits (0x8000000000000000) == 63); #endif
+ /* Test next power of 2. */ + assert (next_power_of_2 (1) == 1);
...as well as coverage of an input of 0.
+ assert (next_power_of_2 (3) == 4); + assert (next_power_of_2 (8) == 8); + assert (next_power_of_2 (9) == 16); + assert (next_power_of_2 (0xffff) == 0x10000); + assert (next_power_of_2 (0x10000) == 0x10000); + assert (next_power_of_2 (UINT64_C ( 0xffffffff)) == 0x100000000); + assert (next_power_of_2 (UINT64_C (0x100000000)) == 0x100000000); + assert (next_power_of_2 (UINT64_C (0x200000001)) == 0x400000000); + assert (next_power_of_2 (UINT64_C (0x6ffffffff)) == 0x800000000); + assert (next_power_of_2 (UINT64_C (0x700000001)) == 0x800000000); + assert (next_power_of_2 (UINT64_C (0x800000000)) == 0x800000000); + exit (EXIT_SUCCESS); } -- 2.39.2
Returns a fully allocated disk containing all 0xff (all ones), or another byte of your choice. --- plugins/data/nbdkit-data-plugin.pod | 1 + plugins/full/nbdkit-full-plugin.pod | 1 + plugins/null/nbdkit-null-plugin.pod | 1 + plugins/ones/nbdkit-ones-plugin.pod | 74 +++++++ plugins/pattern/nbdkit-pattern-plugin.pod | 4 +- plugins/random/nbdkit-random-plugin.pod | 1 + .../nbdkit-sparse-random-plugin.pod | 1 + plugins/zero/nbdkit-zero-plugin.pod | 1 + configure.ac | 2 + plugins/ones/Makefile.am | 70 +++++++ tests/Makefile.am | 4 + plugins/ones/ones.c | 191 ++++++++++++++++++ tests/test-ones.sh | 53 +++++ 13 files changed, 403 insertions(+), 1 deletion(-) diff --git a/plugins/data/nbdkit-data-plugin.pod b/plugins/data/nbdkit-data-plugin.pod index cec1af7f7..46daa859e 100644 --- a/plugins/data/nbdkit-data-plugin.pod +++ b/plugins/data/nbdkit-data-plugin.pod @@ -404,6 +404,7 @@ L<nbdkit-plugin(3)>, L<nbdkit-info-plugin(1)>, L<nbdkit-memory-plugin(1)>, L<nbdkit-null-plugin(1)>, +L<nbdkit-ones-plugin(1)>, L<nbdkit-partitioning-plugin(1)>, L<nbdkit-pattern-plugin(1)>, L<nbdkit-random-plugin(1)>, diff --git a/plugins/full/nbdkit-full-plugin.pod b/plugins/full/nbdkit-full-plugin.pod index 5664aa2da..18c86a327 100644 --- a/plugins/full/nbdkit-full-plugin.pod +++ b/plugins/full/nbdkit-full-plugin.pod @@ -65,6 +65,7 @@ L<nbdkit(1)>, L<nbdkit-plugin(3)>, L<nbdkit-error-filter(1)>, L<nbdkit-null-plugin(1)>, +L<nbdkit-ones-plugin(1)>, L<nbdkit-pattern-plugin(1)>, L<nbdkit-random-plugin(1)>. L<nbdkit-sparse-random-plugin(1)>, diff --git a/plugins/null/nbdkit-null-plugin.pod b/plugins/null/nbdkit-null-plugin.pod index 27fe68746..c71dc2c6f 100644 --- a/plugins/null/nbdkit-null-plugin.pod +++ b/plugins/null/nbdkit-null-plugin.pod @@ -55,6 +55,7 @@ C<nbdkit-null-plugin> first appeared in nbdkit 1.2. L<nbdkit(1)>, L<nbdkit-plugin(3)>, L<nbdkit-full-plugin(1)>, +L<nbdkit-ones-plugin(1)>, L<nbdkit-pattern-plugin(1)>, L<nbdkit-random-plugin(1)>. L<nbdkit-sparse-random-plugin(1)>, diff --git a/plugins/ones/nbdkit-ones-plugin.pod b/plugins/ones/nbdkit-ones-plugin.pod new file mode 100644 index 000000000..83137f608 --- /dev/null +++ b/plugins/ones/nbdkit-ones-plugin.pod @@ -0,0 +1,74 @@ +=head1 NAME + +nbdkit-ones-plugin - nbdkit plugin filled with repeated 0xff or other bytes + +=head1 SYNOPSIS + + nbdkit ones [[size=]SIZE] [byte=N] + +=head1 DESCRIPTION + +C<nbdkit-ones-plugin> is a plugin for L<nbdkit(1)>. Any read returns +a repeating pattern of C<0xff> (all ones) bytes, or another repeating +byte if you use the C<byte=>N parameter. Everything written to the +virtual device is discarded. + +Most NBD consumers will be very confused by this device. It is mainly +useful for testing. L<nbdkit-data-plugin(1)> can be used to create a +modifiable RAM disk initialized with fixed data. + +=head1 PARAMETERS + +=over 4 + +=item B<byte=>N + +Set the repeating byte to C<N>. The default is C<0xff> (all ones). + +=item [B<size=>]SIZE + +Specify the virtual size of the disk image. + +This parameter is optional. If omitted then a zero-sized device is +created. + +C<size=> is a magic config key and may be omitted in most cases. +See L<nbdkit(1)/Magic parameters>. + +=back + +=head1 FILES + +=over 4 + +=item F<$plugindir/nbdkit-ones-plugin.so> + +The plugin. + +Use C<nbdkit --dump-config> to find the location of C<$plugindir>. + +=back + +=head1 VERSION + +C<nbdkit-ones-plugin> first appeared in nbdkit 1.36. + +=head1 SEE ALSO + +L<nbdkit(1)>, +L<nbdkit-plugin(3)>, +L<nbdkit-data-plugin(1)>, +L<nbdkit-full-plugin(1)>, +L<nbdkit-null-plugin(1)>, +L<nbdkit-pattern-plugin(1)>, +L<nbdkit-random-plugin(1)>. +L<nbdkit-sparse-random-plugin(1)>, +L<nbdkit-zero-plugin(1)>. + +=head1 AUTHORS + +Richard W.M. Jones + +=head1 COPYRIGHT + +Copyright Red Hat diff --git a/plugins/pattern/nbdkit-pattern-plugin.pod b/plugins/pattern/nbdkit-pattern-plugin.pod index c5d4f0d36..f4ae324ed 100644 --- a/plugins/pattern/nbdkit-pattern-plugin.pod +++ b/plugins/pattern/nbdkit-pattern-plugin.pod @@ -11,7 +11,8 @@ nbdkit-pattern-plugin - plugin to serve a fixed pattern of data for testing C<nbdkit-pattern-plugin> is a plugin for L<nbdkit(1)> which serves a fixed pattern of data, read only. This is used for testing nbdkit filters and NBD clients. To create test disks filled with other -repeated patterns use L<nbdkit-data-plugin(1)> instead. +repeated patterns use L<nbdkit-data-plugin(1)> or +L<nbdkit-ones-plugin(1)> instead. The fixed pattern is the offset, as a 64 bit big endian integer, every 8 bytes. In hexadecimal this looks like: @@ -88,6 +89,7 @@ L<nbdkit-plugin(3)>, L<nbdkit-data-plugin(1)>, L<nbdkit-full-plugin(1)>, L<nbdkit-null-plugin(1)>, +L<nbdkit-ones-plugin(1)>, L<nbdkit-offset-filter(1)>, L<nbdkit-random-plugin(1)>, L<nbdkit-sparse-random-plugin(1)>, diff --git a/plugins/random/nbdkit-random-plugin.pod b/plugins/random/nbdkit-random-plugin.pod index 040d86bfc..0d6da8d5f 100644 --- a/plugins/random/nbdkit-random-plugin.pod +++ b/plugins/random/nbdkit-random-plugin.pod @@ -76,6 +76,7 @@ L<nbdkit-plugin(3)>, L<nbdkit-data-plugin(1)>, L<nbdkit-full-plugin(1)>, L<nbdkit-null-plugin(1)>, +L<nbdkit-ones-plugin(1)>, L<nbdkit-pattern-plugin(1)>, L<nbdkit-sparse-random-plugin(1)>, L<nbdkit-zero-plugin(1)>, diff --git a/plugins/sparse-random/nbdkit-sparse-random-plugin.pod b/plugins/sparse-random/nbdkit-sparse-random-plugin.pod index 03e98ee16..5636e76c4 100644 --- a/plugins/sparse-random/nbdkit-sparse-random-plugin.pod +++ b/plugins/sparse-random/nbdkit-sparse-random-plugin.pod @@ -110,6 +110,7 @@ L<nbdkit-plugin(3)>, L<nbdkit-data-plugin(1)>, L<nbdkit-full-plugin(1)>, L<nbdkit-null-plugin(1)>, +L<nbdkit-ones-plugin(1)>, L<nbdkit-pattern-plugin(1)>, L<nbdkit-random-plugin(1)>, L<nbdkit-zero-plugin(1)>, diff --git a/plugins/zero/nbdkit-zero-plugin.pod b/plugins/zero/nbdkit-zero-plugin.pod index 03544ad6e..2ac846027 100644 --- a/plugins/zero/nbdkit-zero-plugin.pod +++ b/plugins/zero/nbdkit-zero-plugin.pod @@ -37,6 +37,7 @@ L<nbdkit-plugin(3)>, L<nbdkit-data-plugin(1)>, L<nbdkit-full-plugin(1)>, L<nbdkit-null-plugin(1)>, +L<nbdkit-ones-plugin(1)>, L<nbdkit-pattern-plugin(1)>, L<nbdkit-random-plugin(1)>, L<nbdkit-sparse-random-plugin(1)>. diff --git a/configure.ac b/configure.ac index dafddcc29..310de7ac1 100644 --- a/configure.ac +++ b/configure.ac @@ -95,6 +95,7 @@ non_lang_plugins="\ nbd \ null \ ondemand \ + ones \ partitioning \ pattern \ random \ @@ -1500,6 +1501,7 @@ AC_CONFIG_FILES([Makefile plugins/null/Makefile plugins/ocaml/Makefile plugins/ondemand/Makefile + plugins/ones/Makefile plugins/partitioning/Makefile plugins/pattern/Makefile plugins/perl/Makefile diff --git a/plugins/ones/Makefile.am b/plugins/ones/Makefile.am new file mode 100644 index 000000000..9f8cbc4e2 --- /dev/null +++ b/plugins/ones/Makefile.am @@ -0,0 +1,70 @@ +# 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-ones-plugin.pod + +plugin_LTLIBRARIES = nbdkit-ones-plugin.la + +nbdkit_ones_plugin_la_SOURCES = \ + ones.c \ + $(top_srcdir)/include/nbdkit-plugin.h \ + $(NULL) + +nbdkit_ones_plugin_la_CPPFLAGS = \ + -I$(top_srcdir)/include \ + -I$(top_builddir)/include \ + $(NULL) +nbdkit_ones_plugin_la_CFLAGS = $(WARNINGS_CFLAGS) +nbdkit_ones_plugin_la_LIBADD = \ + $(IMPORT_LIBRARY_ON_WINDOWS) \ + $(NULL) +nbdkit_ones_plugin_la_LDFLAGS = \ + -module -avoid-version -shared $(NO_UNDEFINED_ON_WINDOWS) \ + $(NULL) +if USE_LINKER_SCRIPT +nbdkit_ones_plugin_la_LDFLAGS += \ + -Wl,--version-script=$(top_srcdir)/plugins/plugins.syms +endif + +if HAVE_POD + +man_MANS = nbdkit-ones-plugin.1 +CLEANFILES += $(man_MANS) + +nbdkit-ones-plugin.1: nbdkit-ones-plugin.pod \ + $(top_builddir)/podwrapper.pl + $(PODWRAPPER) --section=1 --man $@ \ + --html $(top_builddir)/html/$@.html \ + $< + +endif HAVE_POD diff --git a/tests/Makefile.am b/tests/Makefile.am index 3c8123f45..3ae13d660 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -955,6 +955,10 @@ EXTRA_DIST += \ test-ondemand-locking.sh \ $(NULL) +# ones plugin test. +TESTS += test-ones.sh +EXTRA_DIST += test-ones.sh + # partitioning plugin test. TESTS += \ test-partitioning1.sh \ diff --git a/plugins/ones/ones.c b/plugins/ones/ones.c new file mode 100644 index 000000000..2ff1ed028 --- /dev/null +++ b/plugins/ones/ones.c @@ -0,0 +1,191 @@ +/* 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 <stdint.h> +#include <string.h> +#include <errno.h> + +#define NBDKIT_API_VERSION 2 + +#include <nbdkit-plugin.h> + +/* The size of disk in bytes (initialized by size=<SIZE> parameter). */ +static int64_t size = 0; + +/* Repeating byte. */ +static uint8_t byte = 0xff; + +static int +ones_config (const char *key, const char *value) +{ + int64_t r; + + if (strcmp (key, "size") == 0) { + r = nbdkit_parse_size (value); + if (r == -1) + return -1; + size = r; + } + else if (strcmp (key, "byte") == 0) { + if (nbdkit_parse_uint8_t ("byte", value, &byte) == -1) + return -1; + } + else { + nbdkit_error ("unknown parameter '%s'", key); + return -1; + } + + return 0; +} + +#define ones_config_help \ + "byte=<BYTE> Repeating byte to use (default: 0xff).\n" \ + "size=<SIZE> Size of the backing disk." + +/* Create the per-connection handle. */ +static void * +ones_open (int readonly) +{ + return NBDKIT_HANDLE_NOT_NEEDED; +} + +#define THREAD_MODEL NBDKIT_THREAD_MODEL_PARALLEL + +/* Get the disk size. */ +static int64_t +ones_get_size (void *handle) +{ + return size; +} + +/* Serves the same data over multiple connections. */ +static int +ones_can_multi_conn (void *handle) +{ + return 1; +} + +/* Cache. */ +static int +ones_can_cache (void *handle) +{ + /* Everything is already in memory, returning this without + * implementing .cache lets nbdkit do the correct no-op. + */ + return NBDKIT_CACHE_NATIVE; +} + +/* Read data. */ +static int +ones_pread (void *handle, void *buf, uint32_t count, uint64_t offset, + uint32_t flags) +{ + memset (buf, byte, count); + return 0; +} + +/* Write data. */ +static int +ones_pwrite (void *handle, const void *buf, uint32_t count, uint64_t offset, + uint32_t flags) +{ + /* nothing */ + return 0; +} + +/* Write zeroes. */ +static int +ones_zero (void *handle, uint32_t count, uint64_t offset, uint32_t flags) +{ + /* nothing */ + return 0; +} + +/* Flush is a no-op, so advertise native FUA support */ +static int +ones_can_fua (void *handle) +{ + return NBDKIT_FUA_NATIVE; +} + +/* Trim. */ +static int +ones_trim (void *handle, uint32_t count, uint64_t offset, uint32_t flags) +{ + /* nothing */ + return 0; +} + +/* Nothing is persistent, so flush is trivially supported */ +static int +ones_flush (void *handle, uint32_t flags) +{ + return 0; +} + +/* Extents. */ +static int +ones_extents (void *handle, uint32_t count, uint64_t offset, uint32_t flags, + struct nbdkit_extents *extents) +{ + /* Return a fully allocated data extent covering the entire disk. */ + return nbdkit_add_extent (extents, 0, size, 0); +} + +static struct nbdkit_plugin plugin = { + .name = "ones", + .version = PACKAGE_VERSION, + .config = ones_config, + .config_help = ones_config_help, + .magic_config_key = "size", + .open = ones_open, + .get_size = ones_get_size, + .can_multi_conn = ones_can_multi_conn, + .can_cache = ones_can_cache, + .pread = ones_pread, + .pwrite = ones_pwrite, + .zero = ones_zero, + .trim = ones_trim, + .can_fua = ones_can_fua, + .flush = ones_flush, + .extents = ones_extents, + /* In this plugin, errno is preserved properly along error return + * paths from failed system calls. + */ + .errno_is_preserved = 1, +}; + +NBDKIT_REGISTER_PLUGIN (plugin) diff --git a/tests/test-ones.sh b/tests/test-ones.sh new file mode 100755 index 000000000..1a2b22caf --- /dev/null +++ b/tests/test-ones.sh @@ -0,0 +1,53 @@ +#!/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. + +source ./functions.sh +set -e +set -x + +requires_plugin ones +requires_nbdsh_uri +requires_nbdinfo + +# Check the disk contains 0xff by default. +nbdkit -U - ones 1024 --run ' +nbdsh -u "$uri" -c "assert (h.pread(1024,0) == b\"\\xff\"*1024)" +' + +# Change the byte. +nbdkit -U - ones 1024 byte=0x5a --run ' +nbdsh -u "$uri" -c "assert (h.pread(1024,0) == b\"\\x5a\"*1024)" +' + +# Check the disk is fully allocated. +nbdkit -U - ones 1G --run 'nbdinfo --map "$uri"' | \ + grep -E '0[[:space:]]+1073741824[[:space:]]+0[[:space:]]+data' -- 2.39.2
On Tue, May 16, 2023 at 01:12:18PM +0100, Richard W.M. Jones wrote:
Returns a fully allocated disk containing all 0xff (all ones), or another byte of your choice. --- +=item B<byte=>N + +Set the repeating byte to C<N>. The default is C<0xff> (all ones).
Maybe worth mentioning that the zero plugin is more efficient than 'ones byte=0'. Otherwise looks correct, and while it probably won't be the most frequently used plugin, I can see its utility as being more efficient than the corresponding use of data plugin in read-only mode with a disk pre-initialized to a repetition of a given byte. -- Eric Blake, Principal Software Engineer Red Hat, Inc. +1-919-301-3266 Virtualization: qemu.org | libvirt.org
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 | 159 ++++++++++++ configure.ac | 2 + filters/evil/Makefile.am | 77 ++++++ tests/Makefile.am | 14 + filters/evil/evil.c | 353 ++++++++++++++++++++++++++ tests/test-evil-cosmic.sh | 76 ++++++ tests/test-evil-stuck-high-bits.sh | 86 +++++++ tests/test-evil-stuck-low-bits.sh | 79 ++++++ tests/test-evil-stuck-wires.sh | 85 +++++++ 10 files changed, 935 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..5100117ab --- /dev/null +++ b/filters/evil/nbdkit-evil-filter.pod @@ -0,0 +1,159 @@ +=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' + +=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 + +=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..ca4fc6b4e 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -1598,6 +1598,20 @@ EXTRA_DIST += \ test-error-triggered.sh \ $(NULL) +# evil filter test. +TESTS += \ + test-evil-cosmic.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-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..e961f6861 --- /dev/null +++ b/filters/evil/evil.c @@ -0,0 +1,353 @@ +/* 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 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; + +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. + */ + block_size = next_power_of_2 ((uint64_t) (100. / evil_probability)); + + return 0; +} + +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; +} + +static void +corrupt_buffer (uint8_t *buf, uint32_t count, uint64_t offset_in_block, + struct random_state *rs, enum corruption_type ct) +{ + if (evil_probability == 0) + /* No corruption, and avoids a divide by zero below. */ + return; + + uint64_t offs, intvl, i, rand; + const uint64_t dinvp = (uint64_t) (2.0 * (1.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) % dinvp; + + /* 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); + } + } +} + +/* 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 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..00f09ac7a --- /dev/null +++ b/tests/test-evil-cosmic.sh @@ -0,0 +1,76 @@ +#!/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 + +# Make sure these are the coreutils versions to avoid surprises. +requires od --version +requires sort --version +requires uniq --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' + +# This will give an approximate count of the number of set bits. + +zbytes="$( od -A n -w1 -v -t x1 < $f | sort | uniq -c | + $SED -n -E -e 's/([0-9]+)[[:space:]]+00[[:space:]]*$/\1/p' )" +nzbits=$(( 10000000 - zbytes )); # looks wrong but actually correct ... + +if [ $nzbits -lt 20 ] || [ $nzbits -gt 180 ]; then + echo "ERROR: $0: unexpected number of non-zero bits: $nzbits" + echo " (expecting about 100)" + exit 1 +fi diff --git a/tests/test-evil-stuck-high-bits.sh b/tests/test-evil-stuck-high-bits.sh new file mode 100755 index 000000000..8f6db2ea0 --- /dev/null +++ b/tests/test-evil-stuck-high-bits.sh @@ -0,0 +1,86 @@ +#!/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 + +# 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. +buf1 = h.pread(1000, 1000) +assert(buf1 == buf[1000:2000]) + +buf1 = h.pread(10000, 999) +assert(buf1 == buf[999:10999]) +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..3b0a48af7 --- /dev/null +++ b/tests/test-evil-stuck-low-bits.sh @@ -0,0 +1,79 @@ +#!/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 + +# 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. +buf1 = h.pread(1000, 32*1024*1024 + 1000) +assert(buf1 == buf[1000:2000]) + +buf1 = h.pread(10000, 32*1024*1024 + 999) +assert(buf1 == buf[999:10999]) +EOF diff --git a/tests/test-evil-stuck-wires.sh b/tests/test-evil-stuck-wires.sh new file mode 100755 index 000000000..c79a009fc --- /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 are 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 Tue, May 16, 2023 at 01:12:19PM +0100, Richard W.M. Jones wrote:
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 | 159 ++++++++++++ configure.ac | 2 + filters/evil/Makefile.am | 77 ++++++ tests/Makefile.am | 14 + filters/evil/evil.c | 353 ++++++++++++++++++++++++++ tests/test-evil-cosmic.sh | 76 ++++++ tests/test-evil-stuck-high-bits.sh | 86 +++++++ tests/test-evil-stuck-low-bits.sh | 79 ++++++ tests/test-evil-stuck-wires.sh | 85 +++++++ 10 files changed, 935 insertions(+)
Interesting idea. Might also be interesting to see how this filter behaves with qemu's quorum device (that is, feed two or more copies of the same block source, one or both through nbdkit's evil filter, into qemu's quorum to see if those corruptions are flagged).
+++ b/filters/evil/nbdkit-evil-filter.pod @@ -0,0 +1,159 @@ +=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.
That's actually a cool description for something so evil!
+ +=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
Makes sense in that the sparse portions of a file don't read from the underlying storage and therefore don't get the stuck read effects (assuming the metadata itself was not also corrupted by stuck bits when determining where the sparse portions of the file were). Of course, the more physically realistic we make the filter, the more complicated it gets.
+++ b/filters/evil/evil.c
+ +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) {
Do we want strcasecmp on these? Do we want to allow _ as a synonym to -?
+ 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);
Do we want to explicitly support 0 for control purposes (no errors, but testing the effect of the filter as a passthrough)? Right now, you permit the probability...
+ +/* 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.
Is '**' the intended operator in these two comments (exponentiation, rather than multiplication)? [1]
+ * We jump forwards, corrupt that bit, and repeat until we reach + * the end of the block.
...but 2**(1/0) is either going to result in infinity or NaN,...
+ * + * "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. + */ + block_size = next_power_of_2 ((uint64_t) (100. / evil_probability));
...and I'm worried that your block_size computation reaches a point where it does not do what we want if the probably gets too close to zero. Even if it is not division by zero, division by a subnormal float can easily produce overflow to infinity, which converts to UINT64_MAX, and next_power_of_2(UINT64_MAX) was untested in patch 3's unit tests, but appears like it will be '1 << (64 - 64)' == 1, which isn't really desirable.
+ + return 0; +} + +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; +} + +static void +corrupt_buffer (uint8_t *buf, uint32_t count, uint64_t offset_in_block, + struct random_state *rs, enum corruption_type ct) +{ + if (evil_probability == 0) + /* No corruption, and avoids a divide by zero below. */ + return;
Okay, you are trying to avoid division by zero elsewhere, but this avoidance may occur too late after get_ready has already settled on a block size.
+ + uint64_t offs, intvl, i, rand; + const uint64_t dinvp = (uint64_t) (2.0 * (1.0 / evil_probability));
[1] Ah, I see - you did mean multiplication, not exponentiation. Like you commented elsewhere, it is not quite a true uniform distribution, but certainly seems sane enough for the intent.
+ + 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) % dinvp; + + /* 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); + } + } +} + +/* 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; + }
Thanks to the ability to set a fixed seed, you can write unit tests that the different bit corruption behaviors are indeed repeatable regardless of client access size or offset.
+++ b/tests/test-evil-cosmic.sh
+ +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.
I have not closely inspected the math yet to see if there's an obvious bias (treat this as a first-pass quick review looking for obvious code/shell bugs, as opposed to more insidious deep analysis bugs). But that comment does mean we probably ought to double-check things prior to v2.
+ +export f +nbdkit -U - null 10000000 \ + --filter=evil --filter=noextents \ + evil=cosmic-rays evil-probability=1/800000 \ + --run 'nbdcopy "$uri" $f' + +# This will give an approximate count of the number of set bits. + +zbytes="$( od -A n -w1 -v -t x1 < $f | sort | uniq -c | + $SED -n -E -e 's/([0-9]+)[[:space:]]+00[[:space:]]*$/\1/p' )" +nzbits=$(( 10000000 - zbytes )); # looks wrong but actually correct ...
Interesting computation!
+ +if [ $nzbits -lt 20 ] || [ $nzbits -gt 180 ]; then + echo "ERROR: $0: unexpected number of non-zero bits: $nzbits" + echo " (expecting about 100)" + exit 1 +fi
And seems like a safe enough fudge factor that we are unlikely to get false negative CI runs.
diff --git a/tests/test-evil-stuck-high-bits.sh b/tests/test-evil-stuck-high-bits.sh new file mode 100755 index 000000000..8f6db2ea0 --- /dev/null +++ b/tests/test-evil-stuck-high-bits.sh @@ -0,0 +1,86 @@
+# 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
Interesting change to count by embedded python instead of shell code.
+ +# 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. +buf1 = h.pread(1000, 1000) +assert(buf1 == buf[1000:2000]) + +buf1 = h.pread(10000, 999) +assert(buf1 == buf[999:10999])
Should we also assert that there is at least one stuck bit in those two ranges, and/or pick a different or larger range to improve the chances of that being the case?
+++ b/tests/test-evil-stuck-wires.sh
+ +# 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 are we are always reading
s/are we are/since we are/
+# 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) +
Overall looks like an interesting idea for a filter. -- Eric Blake, Principal Software Engineer Red Hat, Inc. +1-919-301-3266 Virtualization: qemu.org | libvirt.org
On Tue, May 16, 2023 at 10:55:25AM -0500, Eric Blake wrote:
+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) {
Do we want strcasecmp on these? Do we want to allow _ as a synonym to -?
We're a bit random about this. There are a few places where we use ascii_strcasecmp, but mostly we use strcmp ... [...]
+ /* 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. + */ + block_size = next_power_of_2 ((uint64_t) (100. / evil_probability));
...and I'm worried that your block_size computation reaches a point where it does not do what we want if the probably gets too close to zero. Even if it is not division by zero, division by a subnormal float can easily produce overflow to infinity, which converts to UINT64_MAX, and next_power_of_2(UINT64_MAX) was untested in patch 3's unit tests, but appears like it will be '1 << (64 - 64)' == 1, which isn't really desirable.
Yes this is definitely a bug. I meant to avoid divide by zero, and did in one place, but not everywhere. I think it's worthwhile allowing the probability to be zero, not least because it avoids a special case for the user. However I will need to add a test to make sure I've avoided all the problems. Also as you say very small but non-zero probabilities can make block_size blow up. Let me fix all of that & add tests.
+ + uint64_t offs, intvl, i, rand; + const uint64_t dinvp = (uint64_t) (2.0 * (1.0 / evil_probability));
[1] Ah, I see - you did mean multiplication, not exponentiation. Like you commented elsewhere, it is not quite a true uniform distribution, but certainly seems sane enough for the intent.
I will clarify the comment.
+++ b/tests/test-evil-cosmic.sh
+ +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.
I have not closely inspected the math yet to see if there's an obvious bias (treat this as a first-pass quick review looking for obvious code/shell bugs, as opposed to more insidious deep analysis bugs). But that comment does mean we probably ought to double-check things prior to v2.
Interestingly the other tests are nicely distributed around the expected values, it's just this one test where things are out of whack. I'll add a bit of debugging to the interval calculation etc to see if I can see what's going on.
+export f +nbdkit -U - null 10000000 \ + --filter=evil --filter=noextents \ + evil=cosmic-rays evil-probability=1/800000 \ + --run 'nbdcopy "$uri" $f' + +# This will give an approximate count of the number of set bits. + +zbytes="$( od -A n -w1 -v -t x1 < $f | sort | uniq -c | + $SED -n -E -e 's/([0-9]+)[[:space:]]+00[[:space:]]*$/\1/p' )" +nzbits=$(( 10000000 - zbytes )); # looks wrong but actually correct ...
Interesting computation!
I can probably change this to use Python code. Because I wanted to use nbdcopy (to allow the filter to be hit by multiple threads), I wasn't using nbdsh, so Python wasn't immediately available ...
+# 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. +buf1 = h.pread(1000, 1000) +assert(buf1 == buf[1000:2000]) + +buf1 = h.pread(10000, 999) +assert(buf1 == buf[999:10999])
Should we also assert that there is at least one stuck bit in those two ranges, and/or pick a different or larger range to improve the chances of that being the case?
So I think you mean pick a range where we know there is a stuck bit before doing the read + assert. I will see. With a 1:800,000 chance, it's not likely the ranges as written would have stuck bits so we're comparing zeroes ...
+++ b/tests/test-evil-stuck-wires.sh
+ +# 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 are we are always reading
s/are we are/since we are/
Will fix.
Overall looks like an interesting idea for a filter.
Thanks, Rich. -- Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones Read my programming and virtualization blog: http://rwmj.wordpress.com nbdkit - Flexible, fast NBD server with plugins https://gitlab.com/nbdkit/nbdkit
On Tue, May 16, 2023 at 05:24:58PM +0100, Richard W.M. Jones wrote:
+ +# If we read subsets they should match the contents of the buffer. +buf1 = h.pread(1000, 1000) +assert(buf1 == buf[1000:2000]) + +buf1 = h.pread(10000, 999) +assert(buf1 == buf[999:10999])
Should we also assert that there is at least one stuck bit in those two ranges, and/or pick a different or larger range to improve the chances of that being the case?
So I think you mean pick a range where we know there is a stuck bit before doing the read + assert. I will see. With a 1:800,000 chance, it's not likely the ranges as written would have stuck bits so we're comparing zeroes ...
Engineering tradeoffs - we can run a test with a pinned seed to deterministically know where the stuck bits will be, but it has to be separate from tests where we want the pseudo-random behavior to differ between runs but still demonstrate that our approximations are getting around the ratio of set bits that we expected. -- Eric Blake, Principal Software Engineer Red Hat, Inc. +1-919-301-3266 Virtualization: qemu.org | libvirt.org
On 5/16/23 14:12, Richard W.M. Jones wrote:
+/* 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.
This is a binomial distribution (in the example, n=10^6, p=10^(-4)): https://en.wikipedia.org/wiki/Binomial_distribution The expected value is E = n*p = 10^2, so the comment looks correct in that regard. There is a different interpretation for "we expect" as well. Namely, the "mode" -- the most probable outcome, the number of corrupted bits we're most probably going to see. That's a different concept <https://en.wikipedia.org/wiki/Mode_(statistics)>. However, per the WP article, for the binomial distribution, it is essentially the same. Namely, the WP article says, for this distribution, the mode M (an integer) is given uniquely by (n + 1) * p - 1 <= M < (n + 1) * p [1] if ((n + 1) * p) is *not* an integer, and the M1 and M2 (equally probable, integer) modes M1 = (n + 1) * p [2] M2 = (n + 1) * p - 1 [3] if ((n + 1) * p) *is* an integer. Now,if we distribute the multiplications over the addends (break the parens open), we get: n * p + p - 1 <= M < n * p + p [1] M1 = n * p + p [2] M2 = n * p + p - 1 [3] But for the binomial distribution, E = n * p, so we can substitute (also rewriting +(p-1) as -(1-p) in [1]): E - (1 - p) <= M < E + p [1] M1 = E + p [2] M2 = E + p - 1 [3] Using the values from the code comment: n = 1,000,000 p = 0.000,1 E = n * p = 100 (n + 1) * p = 100.000,1 --> not an integer, so [1] applies: E - (1 - p) <= M < E + p [1] 99.000,1 <= M < 100.000,1 Therefore the mode M is 100 -- it equals the expected value E, for the particular "n" and "p" values! In general, they need not be equal. (For example, the mode(s) are always integers, but E need not be:if we change n to 1,000,001 then E is 100.0001, which is clearly impossible to interpret as a number of corrupted bits. It's effectively an average, but never directly produced by the distribution as a value.) Either way, my point is that M, M1 and M2 (from [1], [2], [3]) are very close to E in the general case too, so the "we expect" language applies even when we interpret it as "mode", not as "expected value".
+ * + * 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.
Two points: (1) I figure the idea is that the "average distance" will be 1/p bits -- the expected value being (0 + 2*(1/p))/2 == 1/p -- so we expect this "average distance" to fit n/(1/p) = n*p times in the block size. This looks sane, but I'm unequipped to make any arguments about "expected value". According to wikipedia, this is the Irwin-Hall distribution <https://en.wikipedia.org/wiki/Irwin%E2%80%93Hall_distribution>: "the sum of a number of independent random variables, each having a uniform distribution". The individual random variables need to follow continuous (not discrete) uniform distributions though, so I don't know if Irwin-Hall "applies" here at all. Wikipedia says that, as "n" increases -- that is, as we sample our underlying uniform U(0, 1) distribution more and more times, and add up the results --, the distribution of the sum (= the Irwin-Hall distribution) approximates a Normal distribution, with both the epxected value and the mode being (s/2), where "s" is the number of samples (variables) summed. I don't know what happens if we scale the underlying U(0, 1) distribution's domain by 2/p, so that it becomes U(0, 2/p). I guess we'd *hope* that the expected value of the sum scales similarly, to: E = s/2 * 2/p = s/p Because in that case, we coul wish for the expected value (and mode) of the sum of the jumps to match our block size, that is: E = s/p = n or put differently, s = n*p Meaning that we'd expect having to sum as many "samples", i.e. having to take as many "jumps", in the average case, as n*p is (= 100 jumps with our numbers). But this is entirely hand-waving; I don't know if this holds up at all! (2) I think the interval as written is off-by-one. The left hand side (0) should indeed be inclusive, but the RHS 2*(1/p) should be *excluded*. We're supposed to have 20,000 integers in the set, from 0 to 19,999 inclusive.
+ * + * "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. + */ + block_size = next_power_of_2 ((uint64_t) (100. / evil_probability)); + + return 0; +} + +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; +} + +static void +corrupt_buffer (uint8_t *buf, uint32_t count, uint64_t offset_in_block, + struct random_state *rs, enum corruption_type ct) +{ + if (evil_probability == 0) + /* No corruption, and avoids a divide by zero below. */ + return; + + uint64_t offs, intvl, i, rand; + const uint64_t dinvp = (uint64_t) (2.0 * (1.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) % dinvp; + + /* 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); + } + } +} + +/* 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 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..00f09ac7a --- /dev/null +++ b/tests/test-evil-cosmic.sh @@ -0,0 +1,76 @@ +#!/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 + +# Make sure these are the coreutils versions to avoid surprises. +requires od --version +requires sort --version +requires uniq --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' + +# This will give an approximate count of the number of set bits. + +zbytes="$( od -A n -w1 -v -t x1 < $f | sort | uniq -c | + $SED -n -E -e 's/([0-9]+)[[:space:]]+00[[:space:]]*$/\1/p' )" +nzbits=$(( 10000000 - zbytes )); # looks wrong but actually correct ...
Some explanation on this would be nice. Laszlo
+ +if [ $nzbits -lt 20 ] || [ $nzbits -gt 180 ]; then + echo "ERROR: $0: unexpected number of non-zero bits: $nzbits" + echo " (expecting about 100)" + exit 1 +fi diff --git a/tests/test-evil-stuck-high-bits.sh b/tests/test-evil-stuck-high-bits.sh new file mode 100755 index 000000000..8f6db2ea0 --- /dev/null +++ b/tests/test-evil-stuck-high-bits.sh @@ -0,0 +1,86 @@ +#!/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 + +# 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. +buf1 = h.pread(1000, 1000) +assert(buf1 == buf[1000:2000]) + +buf1 = h.pread(10000, 999) +assert(buf1 == buf[999:10999]) +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..3b0a48af7 --- /dev/null +++ b/tests/test-evil-stuck-low-bits.sh @@ -0,0 +1,79 @@ +#!/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 + +# 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. +buf1 = h.pread(1000, 32*1024*1024 + 1000) +assert(buf1 == buf[1000:2000]) + +buf1 = h.pread(10000, 32*1024*1024 + 999) +assert(buf1 == buf[999:10999]) +EOF diff --git a/tests/test-evil-stuck-wires.sh b/tests/test-evil-stuck-wires.sh new file mode 100755 index 000000000..c79a009fc --- /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 are 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
On Wed, May 17, 2023 at 03:28:11PM +0200, Laszlo Ersek wrote:
On 5/16/23 14:12, Richard W.M. Jones wrote:
+/* 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.
This is a binomial distribution (in the example, n=10^6, p=10^(-4)):
https://en.wikipedia.org/wiki/Binomial_distribution
The expected value is E = n*p = 10^2, so the comment looks correct in that regard.
There is a different interpretation for "we expect" as well. Namely, the "mode" -- the most probable outcome, the number of corrupted bits we're most probably going to see. That's a different concept <https://en.wikipedia.org/wiki/Mode_(statistics)>. However, per the WP article, for the binomial distribution, it is essentially the same.
Namely, the WP article says, for this distribution, the mode M (an integer) is given uniquely by
(n + 1) * p - 1 <= M < (n + 1) * p [1]
if ((n + 1) * p) is *not* an integer, and the M1 and M2 (equally probable, integer) modes
M1 = (n + 1) * p [2] M2 = (n + 1) * p - 1 [3]
if ((n + 1) * p) *is* an integer.
Now,if we distribute the multiplications over the addends (break the parens open), we get:
n * p + p - 1 <= M < n * p + p [1] M1 = n * p + p [2] M2 = n * p + p - 1 [3]
But for the binomial distribution, E = n * p, so we can substitute (also rewriting +(p-1) as -(1-p) in [1]):
E - (1 - p) <= M < E + p [1] M1 = E + p [2] M2 = E + p - 1 [3]
Using the values from the code comment:
n = 1,000,000 p = 0.000,1 E = n * p = 100
(n + 1) * p = 100.000,1 --> not an integer, so [1] applies:
E - (1 - p) <= M < E + p [1] 99.000,1 <= M < 100.000,1
Therefore the mode M is 100 -- it equals the expected value E, for the particular "n" and "p" values!
In general, they need not be equal. (For example, the mode(s) are always integers, but E need not be:if we change n to 1,000,001 then E is 100.0001, which is clearly impossible to interpret as a number of corrupted bits. It's effectively an average, but never directly produced by the distribution as a value.)
Either way, my point is that M, M1 and M2 (from [1], [2], [3]) are very close to E in the general case too, so the "we expect" language applies even when we interpret it as "mode", not as "expected value".
+ * + * 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.
Two points:
(1) I figure the idea is that the "average distance" will be 1/p bits -- the expected value being (0 + 2*(1/p))/2 == 1/p -- so we expect this "average distance" to fit n/(1/p) = n*p times in the block size.
This looks sane, but I'm unequipped to make any arguments about "expected value".
According to wikipedia, this is the Irwin-Hall distribution <https://en.wikipedia.org/wiki/Irwin%E2%80%93Hall_distribution>: "the sum of a number of independent random variables, each having a uniform distribution". The individual random variables need to follow continuous (not discrete) uniform distributions though, so I don't know if Irwin-Hall "applies" here at all.
Wikipedia says that, as "n" increases -- that is, as we sample our underlying uniform U(0, 1) distribution more and more times, and add up the results --, the distribution of the sum (= the Irwin-Hall distribution) approximates a Normal distribution, with both the epxected value and the mode being (s/2), where "s" is the number of samples (variables) summed.
I don't know what happens if we scale the underlying U(0, 1) distribution's domain by 2/p, so that it becomes U(0, 2/p). I guess we'd *hope* that the expected value of the sum scales similarly, to:
E = s/2 * 2/p = s/p
Because in that case, we coul wish for the expected value (and mode) of the sum of the jumps to match our block size, that is:
E = s/p = n
or put differently,
s = n*p
Meaning that we'd expect having to sum as many "samples", i.e. having to take as many "jumps", in the average case, as n*p is (= 100 jumps with our numbers).
But this is entirely hand-waving; I don't know if this holds up at all!
Yes I don't think the bit picking method I chose gets the right distribution exactly. However it has the advantage of being (a) reproducible without needing to store any state except for the small random number generator state, and (b) easy enough to implement.
(2) I think the interval as written is off-by-one. The left hand side (0) should indeed be inclusive, but the RHS 2*(1/p) should be *excluded*. We're supposed to have 20,000 integers in the set, from 0 to 19,999 inclusive.
This is actually what we use - I'll update the comment.
+# This will give an approximate count of the number of set bits. + +zbytes="$( od -A n -w1 -v -t x1 < $f | sort | uniq -c | + $SED -n -E -e 's/([0-9]+)[[:space:]]+00[[:space:]]*$/\1/p' )" +nzbits=$(( 10000000 - zbytes )); # looks wrong but actually correct ...
Some explanation on this would be nice.
In v2 I killed this completely and use some Python code instead. (That didn't fix the bias I was observing in this test, and nor did adding lots of debugging, so I still don't understand that.) Rich. -- Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones Read my programming and virtualization blog: http://rwmj.wordpress.com virt-top is 'top' for virtual machines. Tiny program with many powerful monitoring features, net stats, disk stats, logging, etc. http://people.redhat.com/~rjones/virt-top
participants (3)
-
Eric Blake -
Laszlo Ersek -
Richard W.M. Jones