classification
Title: Type: Stack overflow with large program crash resolved Interpreter Core, Windows Python 3.7
process
Status: Resolution: closed fixed 24340 serhiy.storchaka Wheerd, benjamin.peterson, brett.cannon, eryksun, jkloth, ncoghlan, ned.deily, paul.moore, pitrou, scoder, serhiy.storchaka, snordhausen, steve.dower, terry.reedy, tim.golden, zach.ware normal

Created on 2017-08-03 08:10 by Wheerd, last changed 2018-01-11 19:34 by serhiy.storchaka. This issue is now closed.

Files
generated.zip Wheerd, 2017-08-04 14:29
Pull Requests
PR 3015 merged serhiy.storchaka, 2017-08-07 13:50
Messages (23)
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) * Date: 2017-08-04 15:01
I'm not an expert in the compiler myself.
msg299772 - (view) Author: Terry J. Reedy (terry.reedy) * 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) * 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) * 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) * 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) * 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) * 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.:

>>> from compileall import compile_file
0
>>> t.start()
>>> Compiling 'generated.py'...
msg299896 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * 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) * 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) * 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) * 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.
msg309818 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * Date: 2018-01-11 18:20
New changeset 782d6fe4434381c50e0c7ec94a1ef9c6debbc333 by Serhiy Storchaka in branch 'master':
bpo-31113: Get rid of recursion in the compiler for normal control flow. (#3015)
https://github.com/python/cpython/commit/782d6fe4434381c50e0c7ec94a1ef9c6debbc333

msg309825 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * Date: 2018-01-11 19:34
Thank you for your review Antoine. I have merged the PR since resolving issue24340 allowed to simplify the code for the stack depth calculation.
History
Date User Action Args
2018-01-11 19:34:59serhiy.storchakasetstatus: open -> closed
resolution: fixed
messages: + msg309825

stage: patch review -> resolved
2018-01-11 18:20:19serhiy.storchakasetmessages: + msg309818
2018-01-03 18:24:32serhiy.storchakasetassignee: serhiy.storchaka
dependencies: + co_stacksize estimate can be highly off
2017-12-19 17:13:09snordhausensetnosy: + snordhausen
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:05vstinnersetnosy: - vstinner
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: + vstinner
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