[PATCH v2 0/1] Fix qemu_strtosz regression

[PATCH v2 0/1] Fix qemu_strtosz regression

[Richard Henderson]

Supercedes: 20210314234821.1954428-1-richard.henderson@linaro.org
("utils: Use fma in qemu_strtosz")

On second thoughts, using fma isn't the best workaround.

Let's just do some fixed-point arithmetic and compute the exact
result of the multiply.  This makes overflow detection simple
and obvious.

Round up from 0.5, because.  This fixes one testsuite failure
and causes another, so amend the testsuite.


r~


Richard Henderson (1):
  utils: Use fixed-point arithmetic in qemu_strtosz

 tests/unit/test-cutils.c |  2 +-
 util/cutils.c            | 50 ++++++++++++++++++++++++++++------------
 2 files changed, 36 insertions(+), 16 deletions(-)

-- 
2.25.1

[PATCH v2 1/1] utils: Use fixed-point arithmetic in qemu_strtosz

[Richard Henderson]

Once we've parsed the fractional value, extract it into an integral
64-bit fraction.  Perform the scaling with integer arithemetic, and
simplify the overflow detection.

Signed-off-by: Richard Henderson <richard.henderson@linaro.org>
---
 tests/unit/test-cutils.c |  2 +-
 util/cutils.c            | 50 ++++++++++++++++++++++++++++------------
 2 files changed, 36 insertions(+), 16 deletions(-)

diff --git a/tests/unit/test-cutils.c b/tests/unit/test-cutils.c
index bad3a60993..e025b54c05 100644
--- a/tests/unit/test-cutils.c
+++ b/tests/unit/test-cutils.c
@@ -2128,7 +2128,7 @@ static void test_qemu_strtosz_float(void)
     str = "12.345M";
     err = qemu_strtosz(str, &endptr, &res);
     g_assert_cmpint(err, ==, 0);
-    g_assert_cmpint(res, ==, (uint64_t) (12.345 * MiB));
+    g_assert_cmpint(res, ==, (uint64_t) (12.345 * MiB + 0.5));
     g_assert(endptr == str + 7);
 }
 
diff --git a/util/cutils.c b/util/cutils.c
index d89a40a8c3..c442882b88 100644
--- a/util/cutils.c
+++ b/util/cutils.c
@@ -275,10 +275,9 @@ static int do_strtosz(const char *nptr, const char **end,
     int retval;
     const char *endptr, *f;
     unsigned char c;
-    bool mul_required = false, hex = false;
-    uint64_t val;
+    bool hex = false;
+    uint64_t val, valf = 0;
     int64_t mul;
-    double fraction = 0.0;
 
     /* Parse integral portion as decimal. */
     retval = qemu_strtou64(nptr, &endptr, 10, &val);
@@ -308,17 +307,19 @@ static int do_strtosz(const char *nptr, const char **end,
          * without fractional digits.  If we see an exponent, treat
          * the entire input as invalid instead.
          */
+        double fraction;
+
         f = endptr;
         retval = qemu_strtod_finite(f, &endptr, &fraction);
         if (retval) {
-            fraction = 0.0;
             endptr++;
         } else if (memchr(f, 'e', endptr - f) || memchr(f, 'E', endptr - f)) {
             endptr = nptr;
             retval = -EINVAL;
             goto out;
-        } else if (fraction != 0) {
-            mul_required = true;
+        } else {
+            /* Extract into a 64-bit fixed-point fraction. */
+            valf = (uint64_t)(fraction * 0x1p64);
         }
     }
     c = *endptr;
@@ -333,16 +334,35 @@ static int do_strtosz(const char *nptr, const char **end,
         mul = suffix_mul(default_suffix, unit);
         assert(mul > 0);
     }
-    if (mul == 1 && mul_required) {
-        endptr = nptr;
-        retval = -EINVAL;
-        goto out;
+    if (mul == 1) {
+        /* When a fraction is present, a scale is required. */
+        if (valf != 0) {
+            endptr = nptr;
+            retval = -EINVAL;
+            goto out;
+        }
+    } else {
+        uint64_t valh, tmp;
+
+        /* Compute exact result: 64.64 x 64.0 -> 128.64 fixed point */
+        mulu64(&val, &valh, val, mul);
+        mulu64(&valf, &tmp, valf, mul);
+        val += tmp;
+        valh += val < tmp;
+
+        /* Round 0.5 upward. */
+        tmp = valf >> 63;
+        val += tmp;
+        valh += val < tmp;
+
+        /* Report overflow. */
+        if (valh != 0) {
+            retval = -ERANGE;
+            goto out;
+        }
     }
-    if (val > (UINT64_MAX - ((uint64_t) (fraction * mul))) / mul) {
-        retval = -ERANGE;
-        goto out;
-    }
-    *result = val * mul + (uint64_t) (fraction * mul);
+
+    *result = val;
     retval = 0;
 
 out:
-- 
2.25.1

Re: [PATCH v2 1/1] utils: Use fixed-point arithmetic in qemu_strtosz

[Philippe Mathieu-Daudé]

On 3/15/21 4:58 PM, Richard Henderson wrote:
> Once we've parsed the fractional value, extract it into an integral
> 64-bit fraction.  Perform the scaling with integer arithemetic, and

Typo "arithmetic"

> simplify the overflow detection.
> 
> Signed-off-by: Richard Henderson <richard.henderson@linaro.org>
> ---
>  tests/unit/test-cutils.c |  2 +-
>  util/cutils.c            | 50 ++++++++++++++++++++++++++++------------
>  2 files changed, 36 insertions(+), 16 deletions(-)
> 
> diff --git a/tests/unit/test-cutils.c b/tests/unit/test-cutils.c
> index bad3a60993..e025b54c05 100644
> --- a/tests/unit/test-cutils.c
> +++ b/tests/unit/test-cutils.c
> @@ -2128,7 +2128,7 @@ static void test_qemu_strtosz_float(void)
>      str = "12.345M";
>      err = qemu_strtosz(str, &endptr, &res);
>      g_assert_cmpint(err, ==, 0);
> -    g_assert_cmpint(res, ==, (uint64_t) (12.345 * MiB));
> +    g_assert_cmpint(res, ==, (uint64_t) (12.345 * MiB + 0.5));
>      g_assert(endptr == str + 7);
>  }
>  
> diff --git a/util/cutils.c b/util/cutils.c
> index d89a40a8c3..c442882b88 100644
> --- a/util/cutils.c
> +++ b/util/cutils.c
> @@ -275,10 +275,9 @@ static int do_strtosz(const char *nptr, const char **end,
>      int retval;
>      const char *endptr, *f;
>      unsigned char c;
> -    bool mul_required = false, hex = false;
> -    uint64_t val;
> +    bool hex = false;
> +    uint64_t val, valf = 0;
>      int64_t mul;
> -    double fraction = 0.0;
>  
>      /* Parse integral portion as decimal. */
>      retval = qemu_strtou64(nptr, &endptr, 10, &val);
> @@ -308,17 +307,19 @@ static int do_strtosz(const char *nptr, const char **end,
>           * without fractional digits.  If we see an exponent, treat
>           * the entire input as invalid instead.
>           */
> +        double fraction;
> +
>          f = endptr;
>          retval = qemu_strtod_finite(f, &endptr, &fraction);
>          if (retval) {
> -            fraction = 0.0;
>              endptr++;
>          } else if (memchr(f, 'e', endptr - f) || memchr(f, 'E', endptr - f)) {
>              endptr = nptr;
>              retval = -EINVAL;
>              goto out;
> -        } else if (fraction != 0) {
> -            mul_required = true;

I'm glad you removed this float-equal warning:

util/cutils.c: In function ‘do_strtosz’:
util/cutils.c:320:29: error: comparing floating-point with ‘==’ or ‘!=’
is unsafe [-Werror=float-equal]
  320 |         } else if (fraction != 0) {
      |                             ^~
cc1: all warnings being treated as errors

> +        } else {
> +            /* Extract into a 64-bit fixed-point fraction. */
> +            valf = (uint64_t)(fraction * 0x1p64);
>          }
>      }
>      c = *endptr;
> @@ -333,16 +334,35 @@ static int do_strtosz(const char *nptr, const char **end,
>          mul = suffix_mul(default_suffix, unit);
>          assert(mul > 0);
>      }
> -    if (mul == 1 && mul_required) {
> -        endptr = nptr;
> -        retval = -EINVAL;
> -        goto out;
> +    if (mul == 1) {
> +        /* When a fraction is present, a scale is required. */
> +        if (valf != 0) {
> +            endptr = nptr;
> +            retval = -EINVAL;
> +            goto out;
> +        }
> +    } else {
> +        uint64_t valh, tmp;
> +
> +        /* Compute exact result: 64.64 x 64.0 -> 128.64 fixed point */
> +        mulu64(&val, &valh, val, mul);
> +        mulu64(&valf, &tmp, valf, mul);
> +        val += tmp;
> +        valh += val < tmp;
> +
> +        /* Round 0.5 upward. */
> +        tmp = valf >> 63;
> +        val += tmp;
> +        valh += val < tmp;
> +
> +        /* Report overflow. */
> +        if (valh != 0) {
> +            retval = -ERANGE;
> +            goto out;
> +        }
>      }
> -    if (val > (UINT64_MAX - ((uint64_t) (fraction * mul))) / mul) {
> -        retval = -ERANGE;
> -        goto out;
> -    }
> -    *result = val * mul + (uint64_t) (fraction * mul);
> +
> +    *result = val;
>      retval = 0;
>  
>  out:
> 

Re: [PATCH v2 1/1] utils: Use fixed-point arithmetic in qemu_strtosz

[Eric Blake]

On 3/15/21 10:58 AM, Richard Henderson wrote:
> Once we've parsed the fractional value, extract it into an integral
> 64-bit fraction.  Perform the scaling with integer arithemetic, and
> simplify the overflow detection.
> 
> Signed-off-by: Richard Henderson <richard.henderson@linaro.org>
> ---
>  tests/unit/test-cutils.c |  2 +-
>  util/cutils.c            | 50 ++++++++++++++++++++++++++++------------
>  2 files changed, 36 insertions(+), 16 deletions(-)
> 
> diff --git a/tests/unit/test-cutils.c b/tests/unit/test-cutils.c
> index bad3a60993..e025b54c05 100644
> --- a/tests/unit/test-cutils.c
> +++ b/tests/unit/test-cutils.c
> @@ -2128,7 +2128,7 @@ static void test_qemu_strtosz_float(void)
>      str = "12.345M";
>      err = qemu_strtosz(str, &endptr, &res);
>      g_assert_cmpint(err, ==, 0);
> -    g_assert_cmpint(res, ==, (uint64_t) (12.345 * MiB));
> +    g_assert_cmpint(res, ==, (uint64_t) (12.345 * MiB + 0.5));

This tweak makes sense ;)

>      g_assert(endptr == str + 7);
>  }
>  
> diff --git a/util/cutils.c b/util/cutils.c
> index d89a40a8c3..c442882b88 100644
> --- a/util/cutils.c
> +++ b/util/cutils.c
> @@ -275,10 +275,9 @@ static int do_strtosz(const char *nptr, const char **end,
>      int retval;
>      const char *endptr, *f;
>      unsigned char c;
> -    bool mul_required = false, hex = false;
> -    uint64_t val;
> +    bool hex = false;
> +    uint64_t val, valf = 0;
>      int64_t mul;
> -    double fraction = 0.0;
>  
>      /* Parse integral portion as decimal. */
>      retval = qemu_strtou64(nptr, &endptr, 10, &val);
> @@ -308,17 +307,19 @@ static int do_strtosz(const char *nptr, const char **end,
>           * without fractional digits.  If we see an exponent, treat
>           * the entire input as invalid instead.
>           */
> +        double fraction;
> +
>          f = endptr;
>          retval = qemu_strtod_finite(f, &endptr, &fraction);
>          if (retval) {
> -            fraction = 0.0;

dropped, because valf is already 0. Okay.

>              endptr++;
>          } else if (memchr(f, 'e', endptr - f) || memchr(f, 'E', endptr - f)) {
>              endptr = nptr;
>              retval = -EINVAL;
>              goto out;
> -        } else if (fraction != 0) {
> -            mul_required = true;
> +        } else {
> +            /* Extract into a 64-bit fixed-point fraction. */
> +            valf = (uint64_t)(fraction * 0x1p64);

Nice.

>          }
>      }
>      c = *endptr;
> @@ -333,16 +334,35 @@ static int do_strtosz(const char *nptr, const char **end,
>          mul = suffix_mul(default_suffix, unit);
>          assert(mul > 0);
>      }
> -    if (mul == 1 && mul_required) {
> -        endptr = nptr;
> -        retval = -EINVAL;
> -        goto out;
> +    if (mul == 1) {
> +        /* When a fraction is present, a scale is required. */
> +        if (valf != 0) {
> +            endptr = nptr;
> +            retval = -EINVAL;
> +            goto out;
> +        }
> +    } else {
> +        uint64_t valh, tmp;
> +
> +        /* Compute exact result: 64.64 x 64.0 -> 128.64 fixed point */
> +        mulu64(&val, &valh, val, mul);
> +        mulu64(&valf, &tmp, valf, mul);
> +        val += tmp;
> +        valh += val < tmp;
> +
> +        /* Round 0.5 upward. */
> +        tmp = valf >> 63;
> +        val += tmp;
> +        valh += val < tmp;
> +
> +        /* Report overflow. */
> +        if (valh != 0) {
> +            retval = -ERANGE;
> +            goto out;
> +        }

More verbose, but definitely exact.

>      }
> -    if (val > (UINT64_MAX - ((uint64_t) (fraction * mul))) / mul) {
> -        retval = -ERANGE;
> -        goto out;
> -    }
> -    *result = val * mul + (uint64_t) (fraction * mul);
> +
> +    *result = val;
>      retval = 0;
>  
>  out:
> 

Reviewed-by: Eric Blake <eblake@redhat.com>

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3226
Virtualization:  qemu.org | libvirt.org

Re: [PATCH v2 1/1] utils: Use fixed-point arithmetic in qemu_strtosz

[Thomas Huth]

On 15/03/2021 16.58, Richard Henderson wrote:
> Once we've parsed the fractional value, extract it into an integral
> 64-bit fraction.  Perform the scaling with integer arithemetic, and
> simplify the overflow detection.

I've put this patch in my local branch, but I'm still getting a failure in 
the cutils test, this time in the Cirrus-CI with the MinGW build:

  https://cirrus-ci.com/task/5413753530351616?command=test#L543

Is it related or is this a different bug?

  Thomas

Re: [PATCH v2 1/1] utils: Use fixed-point arithmetic in qemu_strtosz

[Eric Blake]

On 3/17/21 2:09 AM, Thomas Huth wrote:
> On 15/03/2021 16.58, Richard Henderson wrote:
>> Once we've parsed the fractional value, extract it into an integral
>> 64-bit fraction.  Perform the scaling with integer arithemetic, and
>> simplify the overflow detection.
> 
> I've put this patch in my local branch, but I'm still getting a failure
> in the cutils test, this time in the Cirrus-CI with the MinGW build:
> 
>  https://cirrus-ci.com/task/5413753530351616?command=test#L543
> 
> Is it related or is this a different bug?

ERROR test-cutils - Bail out!
ERROR:../tests/unit/test-cutils.c:2233:test_qemu_strtosz_trailing:
assertion failed (res == 0): (1024 == 0)

That's testing behavior on:

    str = "0x";
    err = qemu_strtosz(str, &endptr, &res);

which should parse as "0" with a suffix of 'x'.  It is an independent
issue (unrelated to the rounding issues fixed in rth's patch), and
rather appears to be a bug in mingw's libc for strtoull although I have
not actually set up an environment to test that assumption yet.

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3226
Virtualization:  qemu.org | libvirt.org

Re: [PATCH v2 1/1] utils: Use fixed-point arithmetic in qemu_strtosz

[Eric Blake]

On 3/17/21 6:16 AM, Eric Blake wrote:
> On 3/17/21 2:09 AM, Thomas Huth wrote:
>> On 15/03/2021 16.58, Richard Henderson wrote:
>>> Once we've parsed the fractional value, extract it into an integral
>>> 64-bit fraction.  Perform the scaling with integer arithemetic, and
>>> simplify the overflow detection.
>>
>> I've put this patch in my local branch, but I'm still getting a failure
>> in the cutils test, this time in the Cirrus-CI with the MinGW build:
>>
>>  https://cirrus-ci.com/task/5413753530351616?command=test#L543
>>
>> Is it related or is this a different bug?
> 
> ERROR test-cutils - Bail out!
> ERROR:../tests/unit/test-cutils.c:2233:test_qemu_strtosz_trailing:
> assertion failed (res == 0): (1024 == 0)
> 
> That's testing behavior on:
> 
>     str = "0x";
>     err = qemu_strtosz(str, &endptr, &res);
> 
> which should parse as "0" with a suffix of 'x'.  It is an independent
> issue (unrelated to the rounding issues fixed in rth's patch), and
> rather appears to be a bug in mingw's libc for strtoull although I have
> not actually set up an environment to test that assumption yet.

Confirmed:
$ cat foo.c
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>

int main(void)
{
    unsigned long u;
    const char *str = "0x";
    char *end;
    errno = 0;
    u = strtoul(str, &end, 10);
    printf("%lu %s %d\n", u, end, errno);
    errno = 0;
    u = strtoul(str, &end, 16);
    printf("%lu %s %d\n", u, end, errno);

    str = "0xq";
    errno = 0;
    u = strtoul(str, &end, 10);
    printf("%lu %s %d\n", u, end, errno);
    errno = 0;
    u = strtoul(str, &end, 16);
    printf("%lu %s %d\n", u, end, errno);
    return 0;
}
$ gcc -o foo-linux -Wall foo.c
$ x86_64-w64-mingw32-gcc -o foo-mingw -Wall foo.c
$ ./foo-linux
0 x 0
0 x 0
0 xq 0
0 xq 0
$ wine ./foo-mingw 2>/dev/null
0 x 0
0 0x 0
0 xq 0
0 0xq 0

Mingw has a bug (and therefore so do all our qemu_strto* functions) when
parsing "0xgarbage" with a base of 0 or 16, in that it fails to advance
past the leading '0' (which is a valid parse).  Patch coming up.

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3226
Virtualization:  qemu.org | libvirt.org