| Message ID | ZiDNhDlxlT48dU2i@tucnak |
|---|---|
| State | New |
| Headers | show |
| Series | libgcc: Fix up __divmodbitint4 [PR114755] | expand |
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
--- 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 +}