classification
Title: (very) long list of elif causes segfault
Type: crash Stage:
Components: Interpreter Core Versions: Python 3.1, Python 3.2, Python 3.3
process
Status: closed Resolution: duplicate
Dependencies: Superseder: stack overflow evaluating eval("()" * 30000)
View: 5765
Assigned To: Nosy List: alexis.d, benjamin.peterson, brett.cannon, christian.heimes, jcea, lemburg, mark.dickinson, ncoghlan, serhiy.storchaka
Priority: normal Keywords:

Created on 2012-11-21 23:41 by alexis.d, last changed 2012-11-23 03:16 by benjamin.peterson. This issue is now closed.

Files
File name Uploaded Description Edit
elif_segfault.py alexis.d, 2012-11-21 23:41
Messages (11)
msg176081 - (view) Author: Alexis Daboville (alexis.d) * Date: 2012-11-21 23:41
Hi,

It looks like using a very long list of elif makes CPython segfault. You can try it with the attached file, which looks like this:

if False:
   pass
elif False:
   pass
   # thousands of elifs
elif False:
   pass

$ python elif_segfault.py
Segmentation fault.

CPython versions tested:
3.x (all segfaults):
3.1 on Debian
3.2 on Arch Linux
3.3 on Windows

2.6 on Debian: segfaults with a longer list of elifs than the one in the attached file.

The PyPy behaviour seems better: it raises 'RuntimeError: maximum recursion depth exceeded'.

A possible cause (if I understood <http://greentreesnakes.readthedocs.org/en/latest/nodes.html#If> well) is that there are no elif nodes in the AST, elif are just plain ifs which are stored recursively in the else part of the previous if.

(I'm not sure if that's an issue as it's not a real use case, but it makes CPython segfault and I was advised on #python-fr to report it anyway.)
msg176082 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2012-11-21 23:50
Nice catch! How did you notice the issue? I hope you didn't use thousands of elifs in some code. It's going to perform horrible slow with O(n).

I'll see if we can fix the problem easily. As this is clearly a pathological case I consider a patch as "nice to have" and not as "required". Nobody sane write a elif chain with nearly 25 thousands elif. ;)
msg176083 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2012-11-21 23:53
Interesting, a debug build of Python doesn't segfault.

$ 3.3/python elif_segfault.py 
RuntimeError: maximum recursion depth exceeded during compilation
[41897 refs]
$ python3.3 elif_segfault.py
Speicherzugriffsfehler (Speicherabzug geschrieben)

Backtrace:
#0  0x00000000004cfd9c in _Py_Mangle (privateobj=<error reading variable: Cannot access memory at address 0x7fff3769afd8>, 
    ident=<error reading variable: Cannot access memory at address 0x7fff3769afd0>) at Python/compile.c:207
#1  0x0000000000509225 in symtable_add_def (st=0x7fe146388860, name=0x7fe14647f450, flag=16) at Python/symtable.c:955
#2  0x000000000050ba59 in symtable_visit_expr (st=0x7fe146388860, e=0x23ea600) at Python/symtable.c:1370
#3  0x000000000050a52c in symtable_visit_stmt (st=0x7fe146388860, s=0x23ea690) at Python/symtable.c:1158
#4  0x000000000050a632 in symtable_visit_stmt (st=0x7fe146388860, s=0x23ea778) at Python/symtable.c:1161
#5  0x000000000050a632 in symtable_visit_stmt (st=0x7fe146388860, s=0x23ea860) at Python/symtable.c:1161
msg176084 - (view) Author: Alexis Daboville (alexis.d) * Date: 2012-11-21 23:57
I had the feeling that there was a possible issue when reading how elifs were represented in the AST. I'm not insane enough to write so many elifs in a real program ;).

I totally agree on the 'nice to have' part rather than 'required'.
msg176100 - (view) Author: Marc-Andre Lemburg (lemburg) * (Python committer) Date: 2012-11-22 08:06
On 22.11.2012 00:41, Alexis Daboville wrote:
> 
> A possible cause (if I understood <http://greentreesnakes.readthedocs.org/en/latest/nodes.html#If> well) is that there are no elif nodes in the AST, elif are just plain ifs which are stored recursively in the else part of the previous if.

This is likely the cause. It's possible that the Python compiler
uses too much stack space, causing the stack to underrun, if
the default recursion limit is too high.

You should be able to check this by setting the recursion limit to
a lower value:

http://docs.python.org/3/library/sys.html?highlight=setrecursion#sys.setrecursionlimit

It defaults to 1000.

-- 
Marc-Andre Lemburg
eGenix.com

Professional Python Services directly from the Source  (#1, Nov 22 2012)
>>> Python Projects, Consulting and Support ...   http://www.egenix.com/
>>> mxODBC.Zope/Plone.Database.Adapter ...       http://zope.egenix.com/
>>> mxODBC, mxDateTime, mxTextTools ...        http://python.egenix.com/
________________________________________________________________________

::: Try our new mxODBC.Connect Python Database Interface for free ! ::::

   eGenix.com Software, Skills and Services GmbH  Pastor-Loeh-Str.48
    D-40764 Langenfeld, Germany. CEO Dipl.-Math. Marc-Andre Lemburg
           Registered at Amtsgericht Duesseldorf: HRB 46611
               http://www.egenix.com/company/contact/
msg176102 - (view) Author: Alexis Daboville (alexis.d) * Date: 2012-11-22 09:26
I don't think it can be "fixed" with sys.setrecursionlimit for a few reasons:

* I think the issue arises when the AST is built. Otherwise if we put code before the if it would execute. But that's not the case (try putting a print('hello') before the if and it won't print anything).
  - This also means that you cannot directly call sys.setrecursionlimit in the file with the elifs.
  - Though we can set recursion limit using a second file which will then import the elifs file: I tried with different limits and CPython still crash in the same way (and always with the same number of elifs, roughly, because I didn't binary search for the exact amount of elifs).
  - sys.setrecursionlimit controls the stack size of the running Python program, while here we break C stack directly before running Python bytecode.
* When recursion limit is hit, an exception is raised, there's no segfault:
>>> def f():
...     f()
...
>>> f()
# plenty of omitted lines
RuntimeError: maximum recursion depth exceeded
>>>
* Having a RuntimeError raised would be nice, though 'maximum recursion depth exceeded' may not be the best possible error message as from a 'Python user' POV there's no recursion here.

---

A possible solution would be, I guess, to store elifs as excepts are stored. Instead of storing elifs recursively, the else part would just contain a list of if nodes (and if there is a else, well just store an if True node).

Though I don't know how difficult it would be to implement that, or if it's likely to break a lot of things which relies on ifs/elifs to be stored that way.
msg176103 - (view) Author: Marc-Andre Lemburg (lemburg) * (Python committer) Date: 2012-11-22 09:59
On 22.11.2012 10:26, Alexis Daboville wrote:
> 
> Alexis Daboville added the comment:
> 
> I don't think it can be "fixed" with sys.setrecursionlimit for a few reasons:

I think you misunderstood. The suggestion was to use the sys
function to check whether the segfault is indeed caused by
the stack and where a more suitable would be.

In order to check this, you need to set a new limit and then
compile the example script. If this results in a RuntimeError
instead of a segfault for some new value of the limit, we'd
know that the problem is caused by the stack use of the compiler.

> * I think the issue arises when the AST is built. Otherwise if we put code before the if it would execute. But that's not the case (try putting a print('hello') before the if and it won't print anything).
>   - This also means that you cannot directly call sys.setrecursionlimit in the file with the elifs.
>   - Though we can set recursion limit using a second file which will then import the elifs file: I tried with different limits and CPython still crash in the same way (and always with the same number of elifs, roughly, because I didn't binary search for the exact amount of elifs).
>   - sys.setrecursionlimit controls the stack size of the running Python program, while here we break C stack directly before running Python bytecode.

It is also used by the compiler. From symtable.c:

/* When compiling the use of C stack is probably going to be a lot
   lighter than when executing Python code but still can overflow
   and causing a Python crash if not checked (e.g. eval("()"*300000)).
   Using the current recursion limit for the compiler seems too
   restrictive (it caused at least one test to fail) so a factor is
   used to allow deeper recursion when compiling an expression.

   Using a scaling factor means this should automatically adjust when
   the recursion limit is adjusted for small or large C stack allocations.
*/
#define COMPILER_STACK_FRAME_SCALE 3

We may have to adjust that scaling factor.

> * When recursion limit is hit, an exception is raised, there's no segfault:
>>>> def f():
> ...     f()
> ...
>>>> f()
> # plenty of omitted lines
> RuntimeError: maximum recursion depth exceeded
>>>>
> * Having a RuntimeError raised would be nice, though 'maximum recursion depth exceeded' may not be the best possible error message as from a 'Python user' POV there's no recursion here.

You should be seeing "maximum recursion depth exceeded during compilation"
if the RuntimeError is generated by the compiler - as Christian did for
debug builds.

-- 
Marc-Andre Lemburg
eGenix.com

Professional Python Services directly from the Source  (#1, Nov 22 2012)
>>> Python Projects, Consulting and Support ...   http://www.egenix.com/
>>> mxODBC.Zope/Plone.Database.Adapter ...       http://zope.egenix.com/
>>> mxODBC, mxDateTime, mxTextTools ...        http://python.egenix.com/
________________________________________________________________________

::: Try our new mxODBC.Connect Python Database Interface for free ! ::::

   eGenix.com Software, Skills and Services GmbH  Pastor-Loeh-Str.48
    D-40764 Langenfeld, Germany. CEO Dipl.-Math. Marc-Andre Lemburg
           Registered at Amtsgericht Duesseldorf: HRB 46611
               http://www.egenix.com/company/contact/
msg176104 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2012-11-22 10:53
> I think the issue arises when the AST is built.

It's occurring when generating a code object from the AST, after the AST is built:

Python 3.3.0+ (3.3:bf1bf3bf3fe2, Nov 22 2012, 10:45:24) 
[GCC 4.2.1 (Apple Inc. build 5664)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> code = "el".join(['if False: pass\n']*10000)
>>> import ast
>>> tree = ast.parse(code)
>>> code_obj = compile(tree, 'noname.py', 'exec')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: maximum recursion depth exceeded during compilation

I don't know why you're getting a segfault rather than the above RuntimeError, though: on my machine this goes straight from working to the RuntimeError:

>>> code = "el".join(['if False: pass\n']*2996)
>>> code_obj = compile(ast.parse(code), 'noname.py', 'exec')
>>> code = "el".join(['if False: pass\n']*2997)
>>> code_obj = compile(ast.parse(code), 'noname.py', 'exec')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: maximum recursion depth exceeded during compilation

Crys: do you still see the segfault if COMPILER_STACK_FRAME_SCALE is #define'd to be 2 rather than 3?
msg176111 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-11-22 16:15
This may be a duplicate of issue5765.
msg176113 - (view) Author: Marc-Andre Lemburg (lemburg) * (Python committer) Date: 2012-11-22 16:38
On 22.11.2012 17:15, Serhiy Storchaka wrote:
> 
> This may be a duplicate of issue5765.

It's certainly similar, but this ticket is not about expressions,
it's about statements that are meant to be repeated often, so
in a way less artificial :-)

It would be interesting to see whether the scaling factor 3 is
small enough to catch this case as well.

-- 
Marc-Andre Lemburg
eGenix.com

Professional Python Services directly from the Source  (#1, Nov 22 2012)
>>> Python Projects, Consulting and Support ...   http://www.egenix.com/
>>> mxODBC.Zope/Plone.Database.Adapter ...       http://zope.egenix.com/
>>> mxODBC, mxDateTime, mxTextTools ...        http://python.egenix.com/
________________________________________________________________________

::: Try our new mxODBC.Connect Python Database Interface for free ! ::::

   eGenix.com Software, Skills and Services GmbH  Pastor-Loeh-Str.48
    D-40764 Langenfeld, Germany. CEO Dipl.-Math. Marc-Andre Lemburg
           Registered at Amtsgericht Duesseldorf: HRB 46611
               http://www.egenix.com/company/contact/
msg176118 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2012-11-22 18:28
I'm unable to reproduce the issue with 3.3 and default head. With v3.3.0 the script causes a segfault. I guess Serhiy has a point, the fix for #5765 also fixes this issue.
History
Date User Action Args
2012-11-23 03:16:51benjamin.petersonsetstatus: open -> closed
2012-11-22 18:36:44serhiy.storchakasetnosy: + ncoghlan
2012-11-22 18:28:21christian.heimessetmessages: + msg176118
2012-11-22 16:38:15lemburgsetmessages: + msg176113
2012-11-22 16:22:49brett.cannonsetnosy: + brett.cannon
2012-11-22 16:15:50serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg176111
resolution: duplicate

superseder: stack overflow evaluating eval("()" * 30000)
2012-11-22 10:53:45mark.dickinsonsetnosy: + mark.dickinson
messages: + msg176104
2012-11-22 09:59:38lemburgsetmessages: + msg176103
2012-11-22 09:26:29alexis.dsetmessages: + msg176102
2012-11-22 08:06:05lemburgsetnosy: + lemburg
messages: + msg176100
2012-11-22 07:15:36pitrousetnosy: + benjamin.peterson
2012-11-22 01:23:56jceasetnosy: + jcea
2012-11-21 23:57:18alexis.dsetmessages: + msg176084
2012-11-21 23:53:53christian.heimessetmessages: + msg176083
2012-11-21 23:50:51christian.heimessetnosy: + christian.heimes
messages: + msg176082
2012-11-21 23:42:32alexis.dsettype: crash
components: + Interpreter Core
2012-11-21 23:41:01alexis.dcreate