Segfaults in cypari2 when running out of stack during deep object deallocation

[embray]

Since cypari2-2 (#26442), the __dealloc__ for Gen may cause deep (but finite) recursions, causing a stack overflow. This happens in particular on Cygwin which has a smallish stack by default (and maybe it also uses more stack space?) but it can be provoked easily on other systems too with

pari.allocatemem(2^28); L = [pari(i) for i in range(2^20)]; x = pari.Pi(); del L; del x

For reference, this is the test failure on Cygwin:

sage -t --long src/sage/rings/number_field/totallyreal.pyx
**********************************************************************
File "src/sage/rings/number_field/totallyreal.pyx", line 243, in sage.rings.number_field.totallyreal.?
Failed example:
    len(enumerate_totallyreal_fields_prim(2,2**15)) # long time
Exception raised:
    Traceback (most recent call last):
      File "/home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 671, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 1095, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.rings.number_field.totallyreal.?[3]>", line 1, in <module>
        len(enumerate_totallyreal_fields_prim(Integer(2),Integer(2)**Integer(15))) # long time
      File "sage/misc/lazy_import.pyx", line 354, in sage.misc.lazy_import.LazyImport.__call__ (build/cythonized/sage/misc/lazy_import.c:3683)
        return self.get_object()(*args, **kwds)
      File "sage/rings/number_field/totallyreal.pyx", line 393, in sage.rings.number_field.totallyreal.enumerate_totallyreal_fields_prim (build/cythonized/sage/rings/number_field/totallyreal.c:5753)
        ng = <pari_gen>((<pari_gen>(pari([nf,zk]))).polredabs())
      File "cypari2/auto_gen.pxi", line 22098, in cypari2.gen.Gen_base.polredabs
      File "cypari2/stack.pyx", line 156, in cypari2.stack.new_gen
      File "cypari2/stack.pyx", line 194, in cypari2.stack.new_gen_noclear
      File "cypari2/stack.pyx", line 128, in cypari2.stack.move_gens_to_heap
    SignalError: Segmentation fault

It turns out that CPython's "trashcan" mechanism was precisely designed to solve this problem. So we added support upstream in Cython for @cython.trashcan and then use that in cypari2. While we're at it, we upgrade to the latest Cython release

Tarball: ​https://files.pythonhosted.org/packages/e0/31/4a166556f92c469d8291d4b03a187f325c773c330fffc1e798bf83d947f2/Cython-0.29.5.tar.gz

Upstream tickets:

• ​https://github.com/cython/cython/pull/2842
• ​https://github.com/sagemath/cypari2/pull/77

[embray]

I have no further information to add at this point, but CC-ing you in case anything about this is obvious to you.

[jdemeyer]

Are these problems reproducible? Do they occur when running the tests individually?

It would also be good to know the precise value of the pari stack size (pari.default("parisizemax")). Does changing the value of sizemax in src/sage/libs/pari/__init__.py affect the crashes?

[embray]

It's completely reproducible and deterministic, at least when running the test suite. I haven't tried putting together a simpler way to reproduce it. But it was definitely introduced by #26442, and it's caused by an infinite recursion, apparently, in remove_from_pari_stack():

#17155 0x0000000398b9e477 in __pyx_pw_4sage_4misc_11lazy_import_10LazyImport_17__call__ ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/sage/misc/lazy_import.dll
(gdb)
#17154 0x0000000398b915fd in __Pyx_PyObject_Call ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/sage/misc/lazy_import.dll
(gdb)
#17153 0x00000003933faf4a in __pyx_pw_4sage_5rings_12number_field_11totallyreal_3enumerate_totallyreal_fields_prim ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/sage/rings/number_field/totallyreal.dll
(gdb)
#17152 0x00000003933e47d5 in __Pyx_PyObject_CallOneArg ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/sage/rings/number_field/totallyreal.dll
(gdb)
#17151 0x00000003933e2a36 in __Pyx__PyObject_CallOneArg ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/sage/rings/number_field/totallyreal.dll
(gdb)
#17150 0x000000039881394c in __Pyx_CyFunction_CallAsMethod ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/sage/misc/persist.dll
(gdb)
#17149 0x00000003b277220e in __pyx_pw_7cypari2_3gen_8Gen_base_1255polredabs ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/cypari2/gen.dll
(gdb)
#17148 0x00000003b26a2eb9 in __pyx_pf_7cypari2_3gen_8Gen_base_1254polredabs ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/cypari2/gen.dll
(gdb)
#17147 0x00000003b1c69540 in __pyx_f_7cypari2_5stack_new_gen ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/cypari2/stack.dll
#17147 0x00000003b1c69540 in __pyx_f_7cypari2_5stack_new_gen ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/cypari2/stack.dll
(gdb) 
#17146 0x00000003b1c68871 in __pyx_f_7cypari2_5stack_new_gen_noclear ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/cypari2/stack.dll
(gdb) 
#17145 0x00000003b1c67dc8 in __pyx_f_7cypari2_5stack_move_gens_to_heap ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/cypari2/stack.dll
(gdb) 
#17144 0x00000003b1c6693d in __pyx_f_7cypari2_5stack_remove_from_pari_stack ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/cypari2/stack.dll
(gdb) 
#17143 0x00000003b2692095 in __pyx_tp_dealloc_7cypari2_3gen_Gen ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/cypari2/gen.dll
(gdb) 
#17142 0x00000003b1c6693d in __pyx_f_7cypari2_5stack_remove_from_pari_stack ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/cypari2/stack.dll
(gdb) 
#17141 0x00000003b2692095 in __pyx_tp_dealloc_7cypari2_3gen_Gen ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/cypari2/gen.dll
...

[jdemeyer]

Would it be possible to check if it's an infinite recursion or just a very deep recursion, for example by increasing the process stack size (if this is possible on Cygwin)? GC is known to introduce deep-but-finite recursions (the Python trashcan mechanism was invented to deal with that).

[jdemeyer]

Confirmed on Linux with ulimit -s 1000 (1MB stack size).

[jdemeyer]

Digging deep in the CPython trashcan mechanism...

[jdemeyer]

Ideally, this would be fixed by Cython upstream in ​https://github.com/cython/cython/pull/2842

[embray]

This all seems interesting and I want to take a closer look. But fixing this issue obviously cannot rely, at least in the short term, on both a patch to CPython and a new feature in Cython. That begins to feel like there must be a simpler approach by just reworking how cypari2 is handling these deallocations.

[jdemeyer]

Just for the record: the fix does not depend on the CPython patch. The CPython patch is meant to fix an issue in the trashcan when subclassing is involved. But the trashcan would work without that patch.

[jdemeyer]

And yes, this could be fixed without any Cython patch but I'd rather not bother.

[embray]

Regardless, it's quite an integration hassle to depend on a new feature in Cython which does not exist yet, and a new release of Cython, in order to build this in such a way that it does not easily cause stack overflows. I'd rather revert the upgrade to cypari2 until this can be resolved.

[embray]

Replying to jdemeyer:

Just for the record: the fix does not depend on the CPython patch. The CPython patch is meant to fix an issue in the trashcan when subclassing is involved. But the trashcan would work without that patch.

It depends on what you mean by "subclassing is involved". In this case subclassing is involved, as Gen is a subclass of Gen_base. But maybe this is not what you mean, as there is no subclassing at the Python level (currently), and Gen_base does not implement a custom tp_dealloc, nor use the "trashcan" mechanism. So I don't think the issue is immediately in effect here, but I wanted to be sure about that. It's not obvious.

[jdemeyer]

Would it be possible (as interim work-around) to run Sage with a larger stack size (ulimit -s 8192 for example)?

[jdemeyer]

With "subclassing is involved", I mean more precisely a class inheriting from a base class, where the base class uses the trashcan. This is broken in CPython (for example, for subclasses of list) but that bug is unrelated to this ticket here.

[embray]

I did a build of Python 2 with a 16 MB stack for the Python executable, and it fixed some of the segfaulting tests, but not others. E.g.

$ ./sage -t --long src/sage/libs/libecm.pyx
too many failed tests, not using stored timings
Running doctests with ID 2019-02-18-14-30-03-ccffc1e9.
Git branch: HEAD
Using --optional=dochtml,mpir,python2,sage
Doctesting 1 file.
sage -t --long src/sage/libs/libecm.pyx
**********************************************************************
File "src/sage/libs/libecm.pyx", line 111, in sage.libs.libecm.ecmfactor
Failed example:
    N.is_prime()
Exception raised:
    Traceback (most recent call last):
      File "/home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 671, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 1086, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.libs.libecm.ecmfactor[8]>", line 1, in <module>
        N.is_prime()
      File "sage/rings/integer.pyx", line 5129, in sage.rings.integer.Integer.is_prime (build/cythonized/sage/rings/integer.c:32101)
        return self.__pari__().isprime()
      File "cypari2/gen.pyx", line 2077, in cypari2.gen.Gen.isprime
    SignalError: Segmentation fault
**********************************************************************
1 item had failures:
   1 of  21 in sage.libs.libecm.ecmfactor
    [28 tests, 1 failure, 1.53 s]

Among others. What should the stack size be so that this doesn't blow up? 16MB seems like plenty...

[embray]

Replying to jdemeyer:

With "subclassing is involved", I mean more precisely a class inheriting from a base class, where the base class uses the trashcan. This is broken in CPython (for example, for subclasses of list) but that bug is unrelated to this ticket here.

I see that now. Would a class that uses @cython.trashcan have the same problem if it were subclassed? Or does your implementation take care of working around that bug?

[embray]

Replying to jdemeyer:

Would it be possible (as interim work-around) to run Sage with a larger stack size (ulimit -s 8192 for example)?

Setting ulimit -s doesn't work on Cygwin: You have to actually link executables with a fixed maximum stack size, which is a field in the binary's headers. In this case it should suffice to link the python interpreter executable with a large enough stack that it at least doesn't crash on the tests. That would be acceptable to me as a temporary workaround. But I've gone now up to 32 MB and it's still crashing. I wonder if there is something else at play here.

[embray]

Changed title since this does not just affect Cygwin.

[jdemeyer]

On Linux (at least the laptop that I'm writing this on), the default stack size is 8MB. So either programs under Cygwin use much more stack or there is indeed something else.

[jdemeyer]

Replying to embray:

Or does your implementation take care of working around that bug?

The current Cython PR uses the same code that I proposed to CPython. So yes, it works around that bug.

[jdemeyer]

The Cython PR is merged.

[jdemeyer]

I created a new branch for cypari2 to use the trashcan (and other new Cython features): ​https://github.com/sagemath/cypari2/pull/77

[jdemeyer]

This is essentially fixed upstream, both in Cython and in cypari2 (the latter is WIP but should be fixed soon).

The question is what should be done in Sage right now. I see 3 possibilities:

1. Do nothing for now and wait until a new version of Cython and cypari2 is released (the latter is easy since I'm the maintainer of cypari2).

2. Apply patches to both Cython and cypari2 in Sage.

3. Somehow work around the issue in a different way.

I prefer 2 since it properly fixes the actual problem. I believe that these patches are acceptable for distributions since they don't change doctest output of anything in Sage on Linux.

[embray]

Replying to jdemeyer:

On Linux (at least the laptop that I'm writing this on), the default stack size is 8MB. So either programs under Cygwin use much more stack or there is indeed something else.

Just to compare I compiled / ran this little program on Linux and Windows:

#include <stdio.h>


void recurse() {
    static int depth = 0;
    char c;
    printf("recursion depth: %d; stack at: %p\n", depth, &c);
    depth += 1;
    recurse();
}


int main(void) {
    recurse();
    return 0;
}

The major difference, between minor calling convention details, is that on Linux the recurse function has the preamble:

  40052d:       55                      push   %rbp
  40052e:       48 89 e5                mov    %rsp,%rbp
  400531:       48 83 ec 10             sub    $0x10,%rsp

whereas on Windows it begins:

   1004010e0:   55                      push   %rbp
   1004010e1:   48 89 e5                mov    %rsp,%rbp
   1004010e4:   48 83 ec 30             sub    $0x30,%rsp

where the extra 32 bytes reserved on the stack are a requirement of the Microsoft x64 calling convention. And indeed, when I run the program on both systems with the stack limit set to 2MB, the Linux version was able to get just a little over 2 times deeper before overflowing.

That's just a trivial example though; not sure exactly how the numbers shake out with Gen.__dealloc__()/remove_from_pari_stack() recursions. I would think the difference would e less extreme in that case.

So, 32MB should have been more than enough, and yet it wasn't. I'll try once more with 64 MB just out of curiosity, but then I'll check if it's something else that's wrong...

[jdemeyer]

With optimization level did you compile with? There might be a difference between -O0 and -O3.

[embray]

It's with -O3 by default, so that shouldn't be it. I'm still getting segfaults even with the stack set to 64MB. Let me confirm whether it's actually using all those 64MB, and then I'll see if there's something else going on here...

[embray]

Replying to jdemeyer:

This is essentially fixed upstream, both in Cython and in cypari2 (the latter is WIP but should be fixed soon).

The question is what should be done in Sage right now. I see 3 possibilities:

1. Do nothing for now and wait until a new version of Cython and cypari2 is released (the latter is easy since I'm the maintainer of cypari2).

2. Apply patches to both Cython and cypari2 in Sage.

3. Somehow work around the issue in a different way.

I prefer 2 since it properly fixes the actual problem. I believe that these patches are acceptable for distributions since they don't change doctest output of anything in Sage on Linux.

I'll see if it fixes the problem here, and if so I can accept option 2 as well.

[embray]

Okay, right. Increasing the stack size did appear to fix the crash in a few tests, such as

sage -t --long src/sage/rings/number_field/totallyreal.pyx

which now works, but did not with a smaller stack.

However, I'm still getting segfaults in Gen.isprime like

File "src/sage/libs/libecm.pyx", line 111, in sage.libs.libecm.ecmfactor
Failed example:
    N.is_prime()
Exception raised:
    Traceback (most recent call last):
      File "/home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 671, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 1086, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.libs.libecm.ecmfactor[8]>", line 1, in <module>
        N.is_prime()
      File "sage/rings/integer.pyx", line 5129, in sage.rings.integer.Integer.is_prime (build/cythonized/sage/rings/integer.c:32101)
        return self.__pari__().isprime()
      File "cypari2/gen.pyx", line 2077, in cypari2.gen.Gen.isprime
    SignalError: Segmentation fault

this appears to be a totally separate issue from the stack overflow issue. Here's the "interesting" part of the stack trace. I'll have to build a debug version of PARI to find out more:

Program received signal SIGSEGV, Segmentation fault.
0x00000003b598daf4 in red_montgomery ()
   from /home/embray/src/sagemath/sage/local/lib/libpari-gmp.dll
(gdb) where
#0  0x00000003b598daf4 in red_montgomery ()
   from /home/embray/src/sagemath/sage/local/lib/libpari-gmp.dll
#1  0x00000003b5bd482f in gen_pow_i ()
   from /home/embray/src/sagemath/sage/local/lib/libpari-gmp.dll
#2  0x00000003b5b58d1e in Fp_pow ()
   from /home/embray/src/sagemath/sage/local/lib/libpari-gmp.dll
#3  0x00000003b5e77644 in pl831 ()
   from /home/embray/src/sagemath/sage/local/lib/libpari-gmp.dll
#4  0x00000003b5e7a8f4 in BPSW_isprime.part.15 ()
   from /home/embray/src/sagemath/sage/local/lib/libpari-gmp.dll
#5  0x00000003b5e7acb2 in isprime ()
   from /home/embray/src/sagemath/sage/local/lib/libpari-gmp.dll
#6  0x00000003b5d0d4cf in map_proto_lG ()
   from /home/embray/src/sagemath/sage/local/lib/libpari-gmp.dll
#7  0x00000003b269a455 in __pyx_pf_7cypari2_3gen_3Gen_118isprime.isra.124 ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/cypari2/gen.dll
#8  0x00000003b277765f in __pyx_pw_7cypari2_3gen_3Gen_119isprime ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/cypari2/gen.dll
#9  0x000000039881394c in __Pyx_CyFunction_CallAsMethod ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/sage/misc/persist.dll
#10 0x0000000393e55486 in __Pyx__PyObject_CallOneArg ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/sage/rings/integer.dll
#11 0x0000000393e645c5 in __Pyx_PyObject_CallOneArg ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/sage/rings/integer.dll
#12 0x0000000393e6bccc in __pyx_pw_4sage_5rings_7integer_7Integer_203is_prime
    ()
   from /home/embray/src/sagemath/sage/local/lib/python2.7/site-packages/sage/rings/integer.dll
#13 0x00000003c1548bfa in PyEval_EvalFrameEx ()
   from /home/embray/src/sagemath/sage/local/bin/libpython2.7.dll

I will probably open a new ticket for this since it seems to be a separate issue. Nevertheless I've never seen this bug before the cypari2 upgrade, so if you have any ideas...

[jdemeyer]

You could try pari(2^127 - 1).isprime() in Sage and see whether that crashes.

[embray]

I mean yes, that example crashes outside the test suite as well.

[jdemeyer]

And in GP? Run ./sage --gp and then

isprime(2^127 - 1)

[embray]

It works in plain GP.

[embray]

I get 5 or 6 test module segfaulting, all in Gen.isprime, so there's something specifically odd about that function more than others (or maybe it's just that it's used very commonly)?

I don't get any segfaults anywhere else.

[jdemeyer]

Replying to jdemeyer:

You could try pari(2^127 - 1).isprime() in Sage and see whether that crashes.

What about pari.isprime(2^127 - 1)?

[jdemeyer]

And also try pari("isprime(2^127 - 1)")

[jdemeyer]

And pari("2^127 - 1").isprime()

[jdemeyer]

New commits:

​4569a83	Cython 0.29.5; add trashcan patch
​b6ea17e	cypari2: use trashcan for Gen

[embray]

I'm a little confused by the attached tarball. Is a Cython upgrade needed for this, or just applying the patch?

[jdemeyer]

Replying to embray:

Is a Cython upgrade needed for this

No, only the patch is needed. But I thought that it would make sense to upgrade from 0.29.2 to 0.29.5 while we're updating Cython anyway.

[embray]

I've confirmed to my satisfaction that this does fix the recursion depth issue with deallocations. The isprime segfault persists, but appears to be orthogonal so I'll open a separate ticket for that.

I just want to do one run of the full test suite to ensure that no other new failures occur, but otherwise this LGTM.

[embray]

Opened #27335 for the Gen.isprime bug.

[embray]

I just upgraded my Linux build to 8.7.beta5 and now I'm getting this crash in tons of places, even with

$ ulimit -s
8192

without even having to try. I will try rebasing this ticket on 8.7.beta5 and resuming...

I'm pretty satisfied now that it works on Cygwin as well.

[slelievre]

Adding "upgrade" to keywords so release manager knows to upload tarball.

[nbruin]

(this comment is only triggered by the mention of cython.trashcan -- your expertise with it here may be useful elsewhere!)

I know of at least one place where cpython's trashcan is necessary in sagelib: for entries in MonoDict and TripleDict in sage/structure/coerce_dict.pyx. There we use extract_mono_cell and extract_triple_cell to move the relevant references to a fresh tuple and then rely on the trashcan mechanism for the deletion of tuples to avoid stack overflow. That means we are incurring the penalty of allocating an extra tuple there for deletion. If cython now exposes a way of participating in the trashcan directly, it may be worth moving that code over as well.

[jdemeyer]

For the sake of supporting distributions, we should wait until Cython 3.0 is actually released before we use @cython.trashcan in the Sage library.

[embray]

Replying to jdemeyer:

For the sake of supporting distributions, we should wait until Cython 3.0 is actually released before we use @cython.trashcan in the Sage library.

I agree, but how does that impact cypari2 which is a dependency of Sage anyways?

[jdemeyer]

Replying to embray:

I agree, but how does that impact cypari2 which is a dependency of Sage anyways?

This ticket adds patches for both cypari2 and Cython. Distros will probably add patches to neither. Both are acceptable.