classification
Title: Stack overflow with large program
Type: crash Stage: patch review
Components: Interpreter Core, Windows Versions: Python 3.7
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: Nosy List: Wheerd, benjamin.peterson, brett.cannon, eryksun, jkloth, ncoghlan, ned.deily, paul.moore, pitrou, scoder, serhiy.storchaka, steve.dower, terry.reedy, tim.golden, zach.ware
Priority: normal Keywords:

Created on 2017-08-03 08:10 by Wheerd, last changed 2017-08-30 12:53 by ned.deily.

Files
File name Uploaded Description Edit
generated.zip Wheerd, 2017-08-04 14:29
Pull Requests
URL Status Linked Edit
PR 3015 open serhiy.storchaka, 2017-08-07 13:50
Messages (21)
msg299689 - (view) Author: Manuel Krebber (Wheerd) * Date: 2017-08-03 08:10
With a pattern matching library I am generating some Python code that matches patterns. For a very big pattern set I generate a Python file which is about 20MB and has ~300K LOC. When I try to execute the file with Python 3.6.2 on Windows 10 (64bit), the interpreter crashes. I do not have the Python source locally, but I could get it if necessary. The crash is because of a stack overflow when calling dfs() in compile.c. I can attach you the program, but it needs some dependencies which currently are only availiable via some Github repos.

I will try to split the ig file into multiple smaller ones, but I thought you might want to know about an interpreter crash.
msg299695 - (view) Author: Stefan Behnel (scoder) * Date: 2017-08-03 10:08
1) Is this reproducible?

2) Getting a crash in compile.c indicates that this is happening at parse/compile time and not when your Python code is executing. Can you confirm that? Does it generate a .pyc file on import that would indicate a successful byte code compilation? If it's a compiler issue, then the dependencies won't actually matter.

2) Is the code position where the crash happens (in dfs()) predictable, or does it vary across multiple runs?

3) Does this appear to be specific to Windows, or can you reproduce it on other platforms, too?

And yes, seeing the file would be helpful. Could you at least compress it and make it available on the web somewhere for now?
msg299696 - (view) Author: Manuel Krebber (Wheerd) * Date: 2017-08-03 10:31
1) Yes.
2) A .pyc file was not generated.
3) It is always the same location where the error occurs.
4) It did not crash on the linux machine that I tested it on.

I have tried to split the code up into multiple files, but it still crashes. I have uploaded the file to http://wheerd.de/generated.zip
If you want I can also provide the code with multiple files.
msg299732 - (view) Author: Stefan Behnel (scoder) * Date: 2017-08-04 06:39
I've looked at the file and it contains a huge amount of deeply nested if-statements. Given that parsers and compilers are typically recursive, I can well imagine that this is a problem, and my guess is that it's most likely just the different C level stack sizes, stack configurations and C compiler dependent stack allocation per function call that makes a difference for the platforms you tested. It would probably also crash on Linux, just for an even larger program.

I'm actually not in the position to decide if something should be done about this, so I'm asking in Antoine for a comment.
msg299749 - (view) Author: Stefan Behnel (scoder) * Date: 2017-08-04 14:24
Regarding the user side of the problem, you might(!) be able to work around the crash by merging nested if-conditions into and-expressions if they have no elif/else. That's also why the split into multiple files doesn't help, it's the depth of the nesting and the overall code complexity that strike here, not the total length of the program.

Side note: just for fun, I compiled your file with Cython. It took a few minutes and then generated a 1.1 GB C file :D - hadn't seen it do that before. That's 31MB xz compressed. I was sure it would crash my C compiler if I tried to compile that, but since processing time and renewable energy are cheap these days, I gave it a try. Now "gcc -O3" is still working on it after 7 hours, currently using some 8.5 GB of RAM. It's probably worth first recompiling gcc itself with proper C compiler flags next time...
msg299750 - (view) Author: Manuel Krebber (Wheerd) * Date: 2017-08-04 14:29
I have already tried to reduce the nesting, but it still crashes. I have to admit that ~20 levels of nesting are still quite a lot. But I am surprised that so few levels of nesting already are a problem for the parser... I have attached the generated code with reduced nesting.
msg299752 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2017-08-04 15:01
I'm not an expert in the compiler myself.
msg299772 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2017-08-05 04:34
We know that compile has undocumented size limits of various sorts that are usually more than sufficient for normal human written code but which can be overwhelmed by machine-generated code.  We do not regard this as a bug.  However, 20 levels of if-nesting should not be a problem unless, say, you are recursively calling such a function.

How are you running python, on what machine?  What do you mean by 'crash'?  Are you running python from a console/terminal, so that there is someplace for tracebacks and exceptions to be displayed?  What does 'It did not crash' mean, versus the 'crash' label above?

Have you tried increasing the recursion limit with sys.setrecursionlimit.  The default for me is 1000.  I have used 10000.  On multi-gigabyte machines, 100000 might even work. 

Instead of directly running your code, have you tried a driver program that reads your code (one file at a time) into a string and then compiles it with compile()?  You might somehow get a better error message, or in any case, find out which of the separate files fail.
msg299775 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-08-05 05:09
I concur with Stefan. Some parts of the compiler are recursive. The crash is expected for enough complex programs, and the size of C stack is platform depended. There are few hard-coded limits (MAXINDENT, CO_MAXBLOCKS) that may prevent the crash by converting it to exception, but they don't take role in this case (MAXINDENT is too large (100), and CO_MAXBLOCKS limits only the level of nested "for" and "try" blocks).

sys.setrecursionlimit doesn't have relation to C stack.

Increasing the size of C stack on Windows can solve this issue for this particular case.
msg299776 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2017-08-05 11:46
By the way, since you're using Python 3, you can probably workaround this issue by delegating some of the work to helper functions using `yield from`.
msg299804 - (view) Author: Manuel Krebber (Wheerd) * Date: 2017-08-06 16:23
@Serhiy That would require me to compile Python myself though, right? Is there a reason why the limit is only for try/for and not for if?

@Antoine Well, the goal is to be able to generate Python 2 compatible code . I will try to split the code into more functions and see if that helps...
msg299805 - (view) Author: Jeremy Kloth (jkloth) * Date: 2017-08-06 17:27
Using master to debug, the (first) offending part of the generated file is the get_match_iter() function.  The problem is not that there is too much nesting, rather it is simply the fact of too many if's period.

Simple testing at the command prompt (using master debug build) reveals the limit for just ifs is around 25000 (on Windows x64).  The actual limit is going to depend on the stack usage (debug/release/version of the C runtime).

To verify:

  exec('if a: b = 1\n' * 25150)

causes exceptions on my box.  The precise limit will vary somewhat.
msg299808 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2017-08-06 18:12
>   exec('if a: b = 1\n' * 25150)

I need to increase it to 200000 and it fails with a stack overflow in dfs() here (git master on Ubuntu 16.04 in pydebug mode).
msg299849 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-08-07 13:59
PR 3015 gets rid of recursion for normal control flow in the compiler. This fixes a stack overflow for this case.
msg299850 - (view) Author: Jeremy Kloth (jkloth) * Date: 2017-08-07 14:52
The PR resolved the stack overflow in dfs(), however it now fails in the stackdepth() routine (technically, the stackdepth_walk() helper).
msg299870 - (view) Author: Brett Cannon (brett.cannon) * (Python committer) Date: 2017-08-07 21:07
One fix at a time. 😉

On Mon, Aug 7, 2017, 07:52 Jeremy Kloth, <report@bugs.python.org> wrote:

>
> Jeremy Kloth added the comment:
>
> The PR resolved the stack overflow in dfs(), however it now fails in the
> stackdepth() routine (technically, the stackdepth_walk() helper).
>
> ----------
>
> _______________________________________
> Python tracker <report@bugs.python.org>
> <http://bugs.python.org/issue31113>
> _______________________________________
>
msg299876 - (view) Author: Eryk Sun (eryksun) * Date: 2017-08-07 23:37
Here are a couple of workarounds for the crash in Windows.

The default stack reservation size is a field in the PE/COFF header, which you can edit using editbin.exe, e.g.:

    editbin /stack:[size_in_bytes] "path\to\python.exe"

The distributed python.exe has a 20000000 byte stack reservation. I changed it to 3 MiB and was able to run generated.py. You can also pre-compile it on a thread with a larger stack, e.g.:

    >>> import threading
    >>> from compileall import compile_file
    >>> threading.stack_size(2**20 * 3)
    0
    >>> t = threading.Thread(target=compile_file, args=('generated.py',))
    >>> t.start()
    >>> Compiling 'generated.py'...
msg299896 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-08-08 05:09
> The PR resolved the stack overflow in dfs(), however it now fails in the stackdepth() routine (technically, the stackdepth_walk() helper).

Indeed. The compiler crashes for longer sequences on Linux too. I'm trying to rewrite stackdepth_walk() too, but it is much harder.
msg299937 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-08-08 16:47
Updated patch makes stackdepth() not consuming the C stack for recursion. The new code is not strictly equivalent to the old code, but I think they should produce the same results in common cases (the existing stack depth calculation algorithm is not free from bugs, see issue24340).

Since this change is not trivial, I think it should be made it only in master. In maintained versions it is safer to change build options on Windows to produce the executable with larger stack.
msg301023 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-08-30 12:26
Ned, Benjamin, what do you think about backporting this change to 3.6 and 2.7? On one hand, the change is not trivial and looks like a new feature. On other hand, this can be considered as a platform specific bug, the compiler works with a large generated code on Linux, but crashes on Windows.

I don't know how to increase the stack size on Windows, but if it is an option, it looks preferable to me on 2.7 and 3.6.
msg301025 - (view) Author: Ned Deily (ned.deily) * (Python committer) Date: 2017-08-30 12:53
I agree with Antoine's comment on the PR: this seems like this should only go into 3.7.  From the description here, it sounds like this is an edge-case problem that hasn't come up before as an issue.  Let's do the right thing in master (for 3.7) and try to come up with a workaround for 3.6.x (like increasing the stack size).  And doing that does not prevent us from deciding later to backport to 3.6.x once we have some experience with the changes in master.
History
Date User Action Args
2017-08-30 12:53:22ned.deilysetmessages: + msg301025
2017-08-30 12:26:17serhiy.storchakasetnosy: + ned.deily
messages: + msg301023
2017-08-08 16:48:08yselivanovsetnosy: - yselivanov
2017-08-08 16:47:44serhiy.storchakasetstage: patch review
messages: + msg299937
versions: + Python 3.7, - Python 3.6
2017-08-08 10:11:05hayposetnosy: - haypo
2017-08-08 05:09:30serhiy.storchakasetmessages: + msg299896
2017-08-07 23:37:08eryksunsetnosy: + eryksun
messages: + msg299876
2017-08-07 21:07:36brett.cannonsetmessages: + msg299870
2017-08-07 14:52:25jklothsetmessages: + msg299850
2017-08-07 13:59:04serhiy.storchakasetmessages: + msg299849
2017-08-07 13:50:36serhiy.storchakasetpull_requests: + pull_request3048
2017-08-06 18:12:14pitrousetnosy: + haypo
2017-08-06 18:12:01pitrousetmessages: + msg299808
2017-08-06 17:27:25jklothsetnosy: + jkloth
messages: + msg299805
2017-08-06 16:23:42Wheerdsetmessages: + msg299804
2017-08-05 11:46:42pitrousetmessages: + msg299776
2017-08-05 05:09:29serhiy.storchakasetmessages: + msg299775
2017-08-05 04:34:15terry.reedysetnosy: + terry.reedy
messages: + msg299772
2017-08-04 15:01:52pitrousetnosy: + brett.cannon, ncoghlan, benjamin.peterson, serhiy.storchaka, yselivanov
messages: + msg299752
2017-08-04 14:29:36Wheerdsetfiles: + generated.zip

messages: + msg299750
2017-08-04 14:24:48scodersetmessages: + msg299749
2017-08-04 06:39:13scodersetnosy: + pitrou
messages: + msg299732
2017-08-03 10:31:26Wheerdsetmessages: + msg299696
2017-08-03 10:08:23scodersetnosy: + scoder
messages: + msg299695
2017-08-03 08:10:51Wheerdcreate