GR_MUST_SUCCEED - an error in _gr_poly_div_basecase

[Sander80]

Greetings.
There is a reproducible error (with some randomness) with the following stack

#0  0x00007ffff6a1cd2b in raise () from /lib64/libc.so.6
#1  0x00007ffff6a1e3e5 in abort () from /lib64/libc.so.6
#2  0x00007ffff6ee4bfb in flint_abort () at src/generic_files/exception.c:49
#3  0x00007ffff6f5b987 in _nmod_poly_div (Q=0x7fff64006550, A=0x7fff64001260, lenA=lenA@entry=3, B=0x7fff64001280, lenB=lenB@entry=2, mod=...) at src/nmod_poly/div.c:36
#4  0x00007ffff75b50c4 in n_poly_mod_div (Q=Q@entry=0x7fff64002600, A=A@entry=0x7fff64002840, B=B@entry=0x7fff640036d0, ctx=...) at src/n_poly/n_poly_mod.c:332
#5  0x00007ffff7202992 in nmod_mpolyn_gcd_brown_smprime_bivar (G=G@entry=0x7fffe4855d50, Abar=Abar@entry=0x7fffe4855d80, Bbar=Bbar@entry=0x7fffe4855db0, A=A@entry=0x7fffe4855de0, 
    B=B@entry=0x7fffe4855e10, ctx=ctx@entry=0x7fffe4855ea0, Sp=0x7fffe4855e40) at src/nmod_mpoly/mpolyn_gcd_brown.c:95
#6  0x00007ffff72042d4 in nmod_mpolyn_gcd_brown_smprime (G=G@entry=0x7fffe4855d50, Abar=Abar@entry=0x7fffe4855d80, Bbar=Bbar@entry=0x7fffe4855db0, A=A@entry=0x7fffe4855de0, B=B@entry=0x7fffe4855e10, 
    var=1, ctx=0x7fffe4855ea0, I=0x7fffe48567a0, Sp=0x7fffe4855e40) at src/nmod_mpoly/mpolyn_gcd_brown.c:364
#7  0x00007ffff7464af1 in fmpz_mpolyl_gcd_brown (G=G@entry=0x7fffe4856210, Abar=Abar@entry=0x7fffe4856240, Bbar=Bbar@entry=0x7fffe4856270, A=A@entry=0x7fffe48561b0, B=B@entry=0x7fffe48561e0, 
    ctx=ctx@entry=0x7fffe48562a0, I=0x7fffe48567a0) at src/fmpz_mpoly_factor/gcd_brown.c:178
#8  0x00007ffff746585d in _try_brown (G=G@entry=0x7fffe4856d90, Abar=Abar@entry=0x0, Bbar=Bbar@entry=0x0, A=A@entry=0x7fff64004cf0, B=B@entry=0x7fffe4856d00, I=I@entry=0x7fffe48567a0, 
    ctx=0x76ade0 <ratfunc_flint::ctx_wrapper>) at src/fmpz_mpoly_factor/gcd_algo.c:1389
#9  0x00007ffff746b47e in _fmpz_mpoly_gcd_algo_small (G=0x7fffe4856d90, Abar=0x0, Bbar=Bbar@entry=0x0, A=<optimized out>, B=<optimized out>, ctx=ctx@entry=0x76ade0 <ratfunc_flint::ctx_wrapper>, algo=31)
    at src/fmpz_mpoly_factor/gcd_algo.c:1700
#10 0x00007ffff74691b3 in _fmpz_mpoly_gcd_algo (G=0x7fffe4856d90, Abar=Abar@entry=0x0, Bbar=Bbar@entry=0x0, A=A@entry=0x7fff64004cf0, B=B@entry=0x7fffe4856d00, 
    ctx=ctx@entry=0x76ade0 <ratfunc_flint::ctx_wrapper>, algo=31) at src/fmpz_mpoly_factor/gcd_algo.c:1906
#11 0x00007ffff72c23cd in fmpz_mpoly_gcd (G=G@entry=0x7fffe4856d90, A=A@entry=0x7fff64004cf0, B=B@entry=0x7fffe4856d00, ctx=ctx@entry=0x76ade0 <ratfunc_flint::ctx_wrapper>) at src/fmpz_mpoly/gcd.c:43

The crash always happens here

#3  0x00007ffff6f5b987 in _nmod_poly_div (Q=0x7fff64006550, A=0x7fff64001260, lenA=lenA@entry=3, B=0x7fff64001280, lenB=lenB@entry=2, mod=...) at src/nmod_poly/div.c:36
36	            GR_MUST_SUCCEED(_gr_poly_div_basecase(Q, A, lenA, B, lenB, ctx));
(gdb) list
31	    {
32	        gr_ctx_t ctx;
33	        _gr_ctx_init_nmod(ctx, &mod);
34	
35	        if (lenB <= 15 || lenA - lenB <= 15)
36	            GR_MUST_SUCCEED(_gr_poly_div_basecase(Q, A, lenA, B, lenB, ctx));
37	        else
38	            GR_MUST_SUCCEED(_gr_poly_div_newton(Q, A, lenA, B, lenB, ctx));
39	    }
40	}

when lenB = 2 and print *b@lenB returns

{9223372036854775836, 1}

also for the crash to happen a special prime is needed, the prime is generated at frame 7, resulting in

mod = {n = 9223372036854775837, ninv = 18446744073709551500, norm = 0}

The prime is the first number in B plus 1.

We can provide instructions how to build the code to reproduce the crash if needed. But looks like some special case is not handled in _gr_poly_div_basecase

[fredrik-johansson]

This works fine for me:

#include "nmod.h"
#include "nmod_poly.h"

int main()
{
    nmod_t mod;
    mp_limb_t Q[2], A[3], B[2];

    nmod_init(&mod, UWORD(9223372036854775837));

    A[0] = 23;
    A[1] = 34;
    A[2] = 35;

    B[0] = UWORD(9223372036854775836);
    B[1] = 1;

    _nmod_poly_div(Q, A, 3, B, 2, mod);
}

Can you provide a complete code example that triggers the bug?

[Sander80]

A can be different, but for example

print *A@lenA
$34 = {1, 9223372036854775835, 1}

[Sander80]

Thank ypu for a quick reply

git clone https://gitlab.com/feynmanintegrals/fuel.git
git checkout debug
./configure --enable-flint
make dep
make library
make benchmarks
benchmarks/test --calc flint --file all.log --threads 128

I will provide the link to download the file. Giving some explanations first then

[Sander80]

The FUEL (https://arxiv.org/abs/2304.13418) is our universal interface to different libraries. In elementary particle physics we get expressions to be simplified, and they are passed to some simplifier. Initially it was fermat, then we plugged multiple libraries, the best turning out to be flint and symbolica.

make dep - builds flint, the version 3.0.1 now
Why threads 128 - to have a high chance to hit the proper random number. I've seen it with 16 threads too but less rare

[Sander80]

Here is the file with expressions - https://disk.yandex.ru/d/PciCvEASoLJmqA

[Sander80]

With 128 threads it runs in about a second. Either succsesfully or crashes. Need to run multiple times to catch the error.
The code itself is well-tested in different evaluations in elementary particle physics, the crash appeared in only some specific case. We managed to strip the problem away from the physical part already, it is reproducible (but not on all computers!)

[Sander80]

flintLibrary: submodule gmpLibrary mpfrLibrary
ifneq ($(DEP_HAS_FLINT),yes)
        cd extra/flint2 && ./bootstrap.sh
        cd extra/flint2 && automake --force-missing --add-missing || echo "This error is not important"
        cd extra/flint2 && rm -rf autom4te.cache/
        export CXX=$(CCPLUS) && export CC=$(CC) && cd extra/flint2 && ./configure --with-mpfr=`pwd`/../../usr/ --with-gmp-include=`pwd`/../../usr/include --with-gmp-lib=`pwd`/../../usr/include --prefix=`pwd`/../../usr
        $(MAKE) -C extra/flint2
        $(MAKE) -C extra/flint2 install

We build gmp and mpfr, perhaps that's the difference?

And by the way on 3.0.1 there's

In file included from ../usr/include/flint/nmod.h:22:0,
                 from fl.cpp:1:
../usr/include/flint/ulong_extras.h: In function ‘mp_limb_t n_gcd(mp_limb_t, mp_limb_t)’:
../usr/include/flint/ulong_extras.h:92:36: error: ‘mpn_gcd_11’ was not declared in this scope
         res = (x != 1 && y != 1) ? mpn_gcd_11(x, y) : 1;

In this build type. mpn_gcd_11 appears only once in the sources, seems to be a typo (but perhaps fixed later)

[fredrik-johansson]

Could you try with --enable-assert?

And by the way on 3.0.1 there's

In file included from ../usr/include/flint/nmod.h:22:0,
                 from fl.cpp:1:
../usr/include/flint/ulong_extras.h: In function ‘mp_limb_t n_gcd(mp_limb_t, mp_limb_t)’:
../usr/include/flint/ulong_extras.h:92:36: error: ‘mpn_gcd_11’ was not declared in this scope
         res = (x != 1 && y != 1) ? mpn_gcd_11(x, y) : 1;

In this build type. mpn_gcd_11 appears only once in the sources, seems to be a typo (but perhaps fixed later)

Since this errors out, are you using some workaround to get it to compile? If mpn_gcd_11 is used without being declared, the arguments and/or return value may be cast to int which could cause silent wrong values. Normally our configure script should detect whether mpn_gcd_11 is available though.

[Sander80]

As of mpn_gcd_11 error - we did not encounter it in our project.
But I see it only under #ifdef FLINT_WANT_GMP_INTERNALS, and probably that was not the case
I saw this error only now when I tried to compile your code from this discussion.

Could you try with --enable-assert?
Do you mean to rebuild flint with ./configure --enable-assert?

[Sander80]

Adding #include "../usr/include/gmp.h" to your sample fixes the sample

[jodavies]

I can reproduce this with --enable-assert. I don't see any assertion failures. I have the same numbers for print *A@lenA and print *B@lenB as @Sander80 .

[Sander80]

Would perhaps providing more data from GDB on crash help?

[Sander80]

I keep searching for reasons for this not to work properly in intensive multithreaded environment

int __gr_nmod_methods_initialized = 0;
gr_static_method_table __gr_nmod_methods;

But even this things seem to be initialized properly even it multithreaded...

[Sander80]

unless two threads start it at the same time, both enter the condition

    if (!__gr_nmod_methods_initialized)
    {   
    ¦   gr_method_tab_init(__gr_nmod_methods, __gr_nmod_methods_input);
    ¦   __gr_nmod_methods_initialized = 1;
    }   

then one is out and trying to do something, and another goes into gr_method_tab_init and unsets the methods

gr_method_tab_init(gr_funcptr * methods, gr_method_tab_input * tab)
{   
    slong i;
    
    for (i = 0; i < GR_METHOD_TAB_SIZE; i++)
    ¦   methods[i] = (gr_funcptr) gr_not_implemented;

[fredrik-johansson]

Yes, that could be an issue. I see two ways to fix it: either put a mutex in gr_method_tab_init, or modify gr_method_tab_init to first write everything to a temporary array before copying it into the real method table (it shouldn't be a problem if two thread write at the same time if they write the same data).