libgcc: Fix up __divmodbitint4 [PR114755]
Checks
Commit Message
Hi!
The following testcase aborts on aarch64-linux but does not on x86_64-linux.
In both cases there is UB in the __divmodbitint4 implemenetation.
When the divisor is negative with most significant limb (even when partial)
all ones, has at least 2 limbs and the second most significant limb has the
most significant bit clear, when this number is negated, it will have 0
in the most significant limb.
Already in the PR114397 r14-9592 fix I was dealing with such divisors, but
thought the problem is only if because of that un < vn doesn't imply the
quotient is 0 and remainder u.
But as this testcase shows, the problem is with such divisors always.
What happens is that we use __builtin_clz* on the most significant limb,
and assume it will not be 0 because that is UB for the builtins.
Normally the most significant limb of the divisor shouldn't be 0, as
guaranteed by the bitint_reduce_prec e.g. for the positive numbers, unless
the divisor is just 0 (but for vn == 1 we have special cases).
The following patch moves the handling of this corner case a few lines
earlier before the un < vn check, because adjusting the vn later is harder.
Bootstrapped/regtested on x86_64-linux and i686-linux, plus tested with
make check-gcc -j32 -k GCC_TEST_RUN_EXPENSIVE=1 RUNTESTFLAGS="GCC_TEST_RUN_EXPENSIVE=1 dg.exp='*bitint* pr112673.c builtin-stdc-bit-*.c pr112566-2.c pr112511.c' dg-torture.exp=*bitint* dfp.exp=*bitint*"
on aarch64-linux, ok for trunk?
2024-04-18 Jakub Jelinek <jakub@redhat.com>
PR libgcc/114755
* libgcc2.c (__divmodbitint4): Perform the decrement on negative
v with most significant limb all ones and the second least
significant limb with most significant bit clear always, regardless of
un < vn.
* gcc.dg/torture/bitint-69.c: New test.
Jakub
Comments
On Thu, 18 Apr 2024, Jakub Jelinek wrote:
> Hi!
>
> The following testcase aborts on aarch64-linux but does not on x86_64-linux.
> In both cases there is UB in the __divmodbitint4 implemenetation.
> When the divisor is negative with most significant limb (even when partial)
> all ones, has at least 2 limbs and the second most significant limb has the
> most significant bit clear, when this number is negated, it will have 0
> in the most significant limb.
> Already in the PR114397 r14-9592 fix I was dealing with such divisors, but
> thought the problem is only if because of that un < vn doesn't imply the
> quotient is 0 and remainder u.
> But as this testcase shows, the problem is with such divisors always.
> What happens is that we use __builtin_clz* on the most significant limb,
> and assume it will not be 0 because that is UB for the builtins.
> Normally the most significant limb of the divisor shouldn't be 0, as
> guaranteed by the bitint_reduce_prec e.g. for the positive numbers, unless
> the divisor is just 0 (but for vn == 1 we have special cases).
>
> The following patch moves the handling of this corner case a few lines
> earlier before the un < vn check, because adjusting the vn later is harder.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, plus tested with
> make check-gcc -j32 -k GCC_TEST_RUN_EXPENSIVE=1 RUNTESTFLAGS="GCC_TEST_RUN_EXPENSIVE=1 dg.exp='*bitint* pr112673.c builtin-stdc-bit-*.c pr112566-2.c pr112511.c' dg-torture.exp=*bitint* dfp.exp=*bitint*"
> on aarch64-linux, ok for trunk?
OK.
Thanks,
Richard.
> 2024-04-18 Jakub Jelinek <jakub@redhat.com>
>
> PR libgcc/114755
> * libgcc2.c (__divmodbitint4): Perform the decrement on negative
> v with most significant limb all ones and the second least
> significant limb with most significant bit clear always, regardless of
> un < vn.
>
> * gcc.dg/torture/bitint-69.c: New test.
>
> --- libgcc/libgcc2.c.jj 2024-03-21 13:07:43.629886730 +0100
> +++ libgcc/libgcc2.c 2024-04-17 19:00:55.453691368 +0200
> @@ -1705,69 +1705,62 @@ __divmodbitint4 (UBILtype *q, SItype qpr
> USItype rn = ((USItype) rprec + W_TYPE_SIZE - 1) / W_TYPE_SIZE;
> USItype up = auprec % W_TYPE_SIZE;
> USItype vp = avprec % W_TYPE_SIZE;
> + /* If vprec < 0 and the top limb of v is all ones and the second most
> + significant limb has most significant bit clear, then just decrease
> + vn/avprec/vp, because after negation otherwise v2 would have most
> + significant limb clear. */
> + if (vprec < 0
> + && ((v[BITINT_END (0, vn - 1)] | (vp ? ((UWtype) -1 << vp) : 0))
> + == (UWtype) -1)
> + && vn > 1
> + && (Wtype) v[BITINT_END (1, vn - 2)] >= 0)
> + {
> + vp = 0;
> + --vn;
> +#if __LIBGCC_BITINT_ORDER__ == __ORDER_BIG_ENDIAN__
> + ++v;
> +#endif
> + }
> if (__builtin_expect (un < vn, 0))
> {
> - /* If abs(v) > abs(u), then q is 0 and r is u.
> - Unfortunately un < vn doesn't always mean abs(v) > abs(u).
> - If uprec > 0 and vprec < 0 and vn == un + 1, if the
> - top limb of v is all ones and the second most significant
> - limb has most significant bit clear, then just decrease
> - vn/avprec/vp and continue, after negation both numbers
> - will have the same number of limbs. */
> - if (un + 1 == vn
> - && uprec >= 0
> - && vprec < 0
> - && ((v[BITINT_END (0, vn - 1)] | (vp ? ((UWtype) -1 << vp) : 0))
> - == (UWtype) -1)
> - && (Wtype) v[BITINT_END (1, vn - 2)] >= 0)
> - {
> - vp = 0;
> - --vn;
> + /* q is 0 and r is u. */
> + if (q)
> + __builtin_memset (q, 0, qn * sizeof (UWtype));
> + if (r == NULL)
> + return;
> #if __LIBGCC_BITINT_ORDER__ == __ORDER_BIG_ENDIAN__
> - ++v;
> + r += rn - 1;
> + u += un - 1;
> #endif
> + if (up)
> + --un;
> + if (rn < un)
> + un = rn;
> + for (rn -= un; un; --un)
> + {
> + *r = *u;
> + r += BITINT_INC;
> + u += BITINT_INC;
> }
> - else
> + if (!rn)
> + return;
> + if (up)
> {
> - /* q is 0 and r is u. */
> - if (q)
> - __builtin_memset (q, 0, qn * sizeof (UWtype));
> - if (r == NULL)
> + if (uprec > 0)
> + *r = *u & (((UWtype) 1 << up) - 1);
> + else
> + *r = *u | ((UWtype) -1 << up);
> + r += BITINT_INC;
> + if (!--rn)
> return;
> -#if __LIBGCC_BITINT_ORDER__ == __ORDER_BIG_ENDIAN__
> - r += rn - 1;
> - u += un - 1;
> -#endif
> - if (up)
> - --un;
> - if (rn < un)
> - un = rn;
> - for (rn -= un; un; --un)
> - {
> - *r = *u;
> - r += BITINT_INC;
> - u += BITINT_INC;
> - }
> - if (!rn)
> - return;
> - if (up)
> - {
> - if (uprec > 0)
> - *r = *u & (((UWtype) 1 << up) - 1);
> - else
> - *r = *u | ((UWtype) -1 << up);
> - r += BITINT_INC;
> - if (!--rn)
> - return;
> - }
> - UWtype c = uprec < 0 ? (UWtype) -1 : (UWtype) 0;
> - for (; rn; --rn)
> - {
> - *r = c;
> - r += BITINT_INC;
> - }
> - return;
> }
> + UWtype c = uprec < 0 ? (UWtype) -1 : (UWtype) 0;
> + for (; rn; --rn)
> + {
> + *r = c;
> + r += BITINT_INC;
> + }
> + return;
> }
> USItype qn2 = un - vn + 1;
> if (qn >= qn2)
> --- gcc/testsuite/gcc.dg/torture/bitint-69.c.jj 2024-04-17 19:09:34.165521448 +0200
> +++ gcc/testsuite/gcc.dg/torture/bitint-69.c 2024-04-17 19:10:25.343814139 +0200
> @@ -0,0 +1,26 @@
> +/* PR libgcc/114755 */
> +/* { dg-do run { target bitint } } */
> +/* { dg-options "-std=c23" } */
> +/* { dg-skip-if "" { ! run_expensive_tests } { "*" } { "-O0" "-O2" } } */
> +/* { dg-skip-if "" { ! run_expensive_tests } { "-flto" } { "" } } */
> +
> +#if __BITINT_MAXWIDTH__ >= 255
> +_BitInt(65)
> +foo (void)
> +{
> + _BitInt(255) a = 0x040404040404040404040404wb;
> + _BitInt(65) b = -0xffffffffffffffffwb;
> + _BitInt(65) r = a % b;
> + return r;
> +}
> +#endif
> +
> +int
> +main ()
> +{
> +#if __BITINT_MAXWIDTH__ >= 255
> + _BitInt(65) x = foo ();
> + if (x != 0x0404040408080808wb)
> + __builtin_abort ();
> +#endif
> +}
>
> Jakub
>
>
On Thu, 18 Apr 2024 at 09:37, Jakub Jelinek <jakub@redhat.com> wrote:
>
> Hi!
>
> The following testcase aborts on aarch64-linux but does not on x86_64-linux.
> In both cases there is UB in the __divmodbitint4 implemenetation.
> When the divisor is negative with most significant limb (even when partial)
> all ones, has at least 2 limbs and the second most significant limb has the
> most significant bit clear, when this number is negated, it will have 0
> in the most significant limb.
> Already in the PR114397 r14-9592 fix I was dealing with such divisors, but
> thought the problem is only if because of that un < vn doesn't imply the
> quotient is 0 and remainder u.
> But as this testcase shows, the problem is with such divisors always.
> What happens is that we use __builtin_clz* on the most significant limb,
> and assume it will not be 0 because that is UB for the builtins.
> Normally the most significant limb of the divisor shouldn't be 0, as
> guaranteed by the bitint_reduce_prec e.g. for the positive numbers, unless
> the divisor is just 0 (but for vn == 1 we have special cases).
Just curious: could this have been caught by ubsan? (I don't know if
it knows about clz)
Thanks,
Christophe
>
> The following patch moves the handling of this corner case a few lines
> earlier before the un < vn check, because adjusting the vn later is harder.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, plus tested with
> make check-gcc -j32 -k GCC_TEST_RUN_EXPENSIVE=1 RUNTESTFLAGS="GCC_TEST_RUN_EXPENSIVE=1 dg.exp='*bitint* pr112673.c builtin-stdc-bit-*.c pr112566-2.c pr112511.c' dg-torture.exp=*bitint* dfp.exp=*bitint*"
> on aarch64-linux, ok for trunk?
>
> 2024-04-18 Jakub Jelinek <jakub@redhat.com>
>
> PR libgcc/114755
> * libgcc2.c (__divmodbitint4): Perform the decrement on negative
> v with most significant limb all ones and the second least
> significant limb with most significant bit clear always, regardless of
> un < vn.
>
> * gcc.dg/torture/bitint-69.c: New test.
>
> --- libgcc/libgcc2.c.jj 2024-03-21 13:07:43.629886730 +0100
> +++ libgcc/libgcc2.c 2024-04-17 19:00:55.453691368 +0200
> @@ -1705,69 +1705,62 @@ __divmodbitint4 (UBILtype *q, SItype qpr
> USItype rn = ((USItype) rprec + W_TYPE_SIZE - 1) / W_TYPE_SIZE;
> USItype up = auprec % W_TYPE_SIZE;
> USItype vp = avprec % W_TYPE_SIZE;
> + /* If vprec < 0 and the top limb of v is all ones and the second most
> + significant limb has most significant bit clear, then just decrease
> + vn/avprec/vp, because after negation otherwise v2 would have most
> + significant limb clear. */
> + if (vprec < 0
> + && ((v[BITINT_END (0, vn - 1)] | (vp ? ((UWtype) -1 << vp) : 0))
> + == (UWtype) -1)
> + && vn > 1
> + && (Wtype) v[BITINT_END (1, vn - 2)] >= 0)
> + {
> + vp = 0;
> + --vn;
> +#if __LIBGCC_BITINT_ORDER__ == __ORDER_BIG_ENDIAN__
> + ++v;
> +#endif
> + }
> if (__builtin_expect (un < vn, 0))
> {
> - /* If abs(v) > abs(u), then q is 0 and r is u.
> - Unfortunately un < vn doesn't always mean abs(v) > abs(u).
> - If uprec > 0 and vprec < 0 and vn == un + 1, if the
> - top limb of v is all ones and the second most significant
> - limb has most significant bit clear, then just decrease
> - vn/avprec/vp and continue, after negation both numbers
> - will have the same number of limbs. */
> - if (un + 1 == vn
> - && uprec >= 0
> - && vprec < 0
> - && ((v[BITINT_END (0, vn - 1)] | (vp ? ((UWtype) -1 << vp) : 0))
> - == (UWtype) -1)
> - && (Wtype) v[BITINT_END (1, vn - 2)] >= 0)
> - {
> - vp = 0;
> - --vn;
> + /* q is 0 and r is u. */
> + if (q)
> + __builtin_memset (q, 0, qn * sizeof (UWtype));
> + if (r == NULL)
> + return;
> #if __LIBGCC_BITINT_ORDER__ == __ORDER_BIG_ENDIAN__
> - ++v;
> + r += rn - 1;
> + u += un - 1;
> #endif
> + if (up)
> + --un;
> + if (rn < un)
> + un = rn;
> + for (rn -= un; un; --un)
> + {
> + *r = *u;
> + r += BITINT_INC;
> + u += BITINT_INC;
> }
> - else
> + if (!rn)
> + return;
> + if (up)
> {
> - /* q is 0 and r is u. */
> - if (q)
> - __builtin_memset (q, 0, qn * sizeof (UWtype));
> - if (r == NULL)
> + if (uprec > 0)
> + *r = *u & (((UWtype) 1 << up) - 1);
> + else
> + *r = *u | ((UWtype) -1 << up);
> + r += BITINT_INC;
> + if (!--rn)
> return;
> -#if __LIBGCC_BITINT_ORDER__ == __ORDER_BIG_ENDIAN__
> - r += rn - 1;
> - u += un - 1;
> -#endif
> - if (up)
> - --un;
> - if (rn < un)
> - un = rn;
> - for (rn -= un; un; --un)
> - {
> - *r = *u;
> - r += BITINT_INC;
> - u += BITINT_INC;
> - }
> - if (!rn)
> - return;
> - if (up)
> - {
> - if (uprec > 0)
> - *r = *u & (((UWtype) 1 << up) - 1);
> - else
> - *r = *u | ((UWtype) -1 << up);
> - r += BITINT_INC;
> - if (!--rn)
> - return;
> - }
> - UWtype c = uprec < 0 ? (UWtype) -1 : (UWtype) 0;
> - for (; rn; --rn)
> - {
> - *r = c;
> - r += BITINT_INC;
> - }
> - return;
> }
> + UWtype c = uprec < 0 ? (UWtype) -1 : (UWtype) 0;
> + for (; rn; --rn)
> + {
> + *r = c;
> + r += BITINT_INC;
> + }
> + return;
> }
> USItype qn2 = un - vn + 1;
> if (qn >= qn2)
> --- gcc/testsuite/gcc.dg/torture/bitint-69.c.jj 2024-04-17 19:09:34.165521448 +0200
> +++ gcc/testsuite/gcc.dg/torture/bitint-69.c 2024-04-17 19:10:25.343814139 +0200
> @@ -0,0 +1,26 @@
> +/* PR libgcc/114755 */
> +/* { dg-do run { target bitint } } */
> +/* { dg-options "-std=c23" } */
> +/* { dg-skip-if "" { ! run_expensive_tests } { "*" } { "-O0" "-O2" } } */
> +/* { dg-skip-if "" { ! run_expensive_tests } { "-flto" } { "" } } */
> +
> +#if __BITINT_MAXWIDTH__ >= 255
> +_BitInt(65)
> +foo (void)
> +{
> + _BitInt(255) a = 0x040404040404040404040404wb;
> + _BitInt(65) b = -0xffffffffffffffffwb;
> + _BitInt(65) r = a % b;
> + return r;
> +}
> +#endif
> +
> +int
> +main ()
> +{
> +#if __BITINT_MAXWIDTH__ >= 255
> + _BitInt(65) x = foo ();
> + if (x != 0x0404040408080808wb)
> + __builtin_abort ();
> +#endif
> +}
>
> Jakub
>
On Thu, Apr 18, 2024 at 11:25:43AM +0200, Christophe Lyon wrote:
> On Thu, 18 Apr 2024 at 09:37, Jakub Jelinek <jakub@redhat.com> wrote:
> > The following testcase aborts on aarch64-linux but does not on x86_64-linux.
> > In both cases there is UB in the __divmodbitint4 implemenetation.
> > When the divisor is negative with most significant limb (even when partial)
> > all ones, has at least 2 limbs and the second most significant limb has the
> > most significant bit clear, when this number is negated, it will have 0
> > in the most significant limb.
> > Already in the PR114397 r14-9592 fix I was dealing with such divisors, but
> > thought the problem is only if because of that un < vn doesn't imply the
> > quotient is 0 and remainder u.
> > But as this testcase shows, the problem is with such divisors always.
> > What happens is that we use __builtin_clz* on the most significant limb,
> > and assume it will not be 0 because that is UB for the builtins.
> > Normally the most significant limb of the divisor shouldn't be 0, as
> > guaranteed by the bitint_reduce_prec e.g. for the positive numbers, unless
> > the divisor is just 0 (but for vn == 1 we have special cases).
>
> Just curious: could this have been caught by ubsan? (I don't know if
> it knows about clz)
ubsan does instrument clz, I don't remember right now if even libgcc is
built with -fsanitize=undefined during bootstrap-ubsan, if it is, it
probably should (but we didn't have this test in the testsuite).
Jakub
@@ -1705,69 +1705,62 @@ __divmodbitint4 (UBILtype *q, SItype qpr
USItype rn = ((USItype) rprec + W_TYPE_SIZE - 1) / W_TYPE_SIZE;
USItype up = auprec % W_TYPE_SIZE;
USItype vp = avprec % W_TYPE_SIZE;
+ /* If vprec < 0 and the top limb of v is all ones and the second most
+ significant limb has most significant bit clear, then just decrease
+ vn/avprec/vp, because after negation otherwise v2 would have most
+ significant limb clear. */
+ if (vprec < 0
+ && ((v[BITINT_END (0, vn - 1)] | (vp ? ((UWtype) -1 << vp) : 0))
+ == (UWtype) -1)
+ && vn > 1
+ && (Wtype) v[BITINT_END (1, vn - 2)] >= 0)
+ {
+ vp = 0;
+ --vn;
+#if __LIBGCC_BITINT_ORDER__ == __ORDER_BIG_ENDIAN__
+ ++v;
+#endif
+ }
if (__builtin_expect (un < vn, 0))
{
- /* If abs(v) > abs(u), then q is 0 and r is u.
- Unfortunately un < vn doesn't always mean abs(v) > abs(u).
- If uprec > 0 and vprec < 0 and vn == un + 1, if the
- top limb of v is all ones and the second most significant
- limb has most significant bit clear, then just decrease
- vn/avprec/vp and continue, after negation both numbers
- will have the same number of limbs. */
- if (un + 1 == vn
- && uprec >= 0
- && vprec < 0
- && ((v[BITINT_END (0, vn - 1)] | (vp ? ((UWtype) -1 << vp) : 0))
- == (UWtype) -1)
- && (Wtype) v[BITINT_END (1, vn - 2)] >= 0)
- {
- vp = 0;
- --vn;
+ /* q is 0 and r is u. */
+ if (q)
+ __builtin_memset (q, 0, qn * sizeof (UWtype));
+ if (r == NULL)
+ return;
#if __LIBGCC_BITINT_ORDER__ == __ORDER_BIG_ENDIAN__
- ++v;
+ r += rn - 1;
+ u += un - 1;
#endif
+ if (up)
+ --un;
+ if (rn < un)
+ un = rn;
+ for (rn -= un; un; --un)
+ {
+ *r = *u;
+ r += BITINT_INC;
+ u += BITINT_INC;
}
- else
+ if (!rn)
+ return;
+ if (up)
{
- /* q is 0 and r is u. */
- if (q)
- __builtin_memset (q, 0, qn * sizeof (UWtype));
- if (r == NULL)
+ if (uprec > 0)
+ *r = *u & (((UWtype) 1 << up) - 1);
+ else
+ *r = *u | ((UWtype) -1 << up);
+ r += BITINT_INC;
+ if (!--rn)
return;
-#if __LIBGCC_BITINT_ORDER__ == __ORDER_BIG_ENDIAN__
- r += rn - 1;
- u += un - 1;
-#endif
- if (up)
- --un;
- if (rn < un)
- un = rn;
- for (rn -= un; un; --un)
- {
- *r = *u;
- r += BITINT_INC;
- u += BITINT_INC;
- }
- if (!rn)
- return;
- if (up)
- {
- if (uprec > 0)
- *r = *u & (((UWtype) 1 << up) - 1);
- else
- *r = *u | ((UWtype) -1 << up);
- r += BITINT_INC;
- if (!--rn)
- return;
- }
- UWtype c = uprec < 0 ? (UWtype) -1 : (UWtype) 0;
- for (; rn; --rn)
- {
- *r = c;
- r += BITINT_INC;
- }
- return;
}
+ UWtype c = uprec < 0 ? (UWtype) -1 : (UWtype) 0;
+ for (; rn; --rn)
+ {
+ *r = c;
+ r += BITINT_INC;
+ }
+ return;
}
USItype qn2 = un - vn + 1;
if (qn >= qn2)
@@ -0,0 +1,26 @@
+/* PR libgcc/114755 */
+/* { dg-do run { target bitint } } */
+/* { dg-options "-std=c23" } */
+/* { dg-skip-if "" { ! run_expensive_tests } { "*" } { "-O0" "-O2" } } */
+/* { dg-skip-if "" { ! run_expensive_tests } { "-flto" } { "" } } */
+
+#if __BITINT_MAXWIDTH__ >= 255
+_BitInt(65)
+foo (void)
+{
+ _BitInt(255) a = 0x040404040404040404040404wb;
+ _BitInt(65) b = -0xffffffffffffffffwb;
+ _BitInt(65) r = a % b;
+ return r;
+}
+#endif
+
+int
+main ()
+{
+#if __BITINT_MAXWIDTH__ >= 255
+ _BitInt(65) x = foo ();
+ if (x != 0x0404040408080808wb)
+ __builtin_abort ();
+#endif
+}