classification
Title: increase parser stack limit
Type: enhancement Stage:
Components: Versions: Python 2.6
process
Status: closed Resolution: accepted
Dependencies: Superseder:
Assigned To: gvanrossum Nosy List: christian.heimes, facundobatista, fijal, georg.brandl, gvanrossum, schmir
Priority: normal Keywords:

Created on 2008-01-21 10:08 by schmir, last changed 2008-02-23 13:19 by christian.heimes. This issue is now closed.

Files
File name Uploaded Description Edit
up-maxstack.txt schmir, 2008-01-21 10:15 up MAXSTACK to 5000
up-maxstack+tests.txt schmir, 2008-01-22 08:35 up MAXSTACK to 1500. added some tests
stack.h fijal, 2008-01-22 08:57 stack size handler.
Messages (16)
msg61379 - (view) Author: Ralf Schmitt (schmir) Date: 2008-01-21 10:08
The parser can handle nested structures only up to a certain limit.
The limit is currently reached around 33 deeply nested lists, which is a
bit too low.

This patch increases that limit by a factor of 10.

see http://bugs.python.org/issue215555 for further discussion.
msg61392 - (view) Author: Georg Brandl (georg.brandl) * (Python committer) Date: 2008-01-21 13:39
Guido, is the 10-fold increase okay?
msg61395 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2008-01-21 14:03
10-fold is very progressive. Let's be a bit more conservative for
platforms with a small stack size (e.g. *BSD and mobile phones). A
parser stack limit of about 1500 would still allow roughly 100 deeply
nested lists.
msg61432 - (view) Author: Guido van Rossum (gvanrossum) * (Python committer) Date: 2008-01-21 18:16
I don't know what common stack sizes are any more.  Even on the same
platform, the main thread may have a different stack size than other
threads.  

Would it make sense to make this limit more platform-dependent?

I guess really good would be a way to handle C stack overflows more
gracefully, but that's for another era.

All said, let's try a 3x increase, *and* have a unittest that pushes the
limits to the max (both a case that is one short of the limit and a case
that is over the limit, and is expected to raise an exception).
msg61438 - (view) Author: Facundo Batista (facundobatista) * (Python committer) Date: 2008-01-21 18:45
Ralf, could you please submit the unit test that Guido suggested? Please
change also the 10x to 3x.

We could then apply this, :)

Thank you very much!
msg61487 - (view) Author: Ralf Schmitt (schmir) Date: 2008-01-22 08:35
yes, here it is. I've added the tests to Lib/test/test_parser.
BTW, is it possible to trigger a segfault by constructing a parser.st
object and calling compile on it?
msg61488 - (view) Author: Ralf Schmitt (schmir) Date: 2008-01-22 08:37
one more. this program seems to leak memory:

x=1000
e="["*x+"]"*x
while 1:
    try:
        eval(e)
    except MemoryError:
        pass
msg61489 - (view) Author: Maciek Fijalkowski (fijal) Date: 2008-01-22 08:43
Attached file that handles stack overflow slightly better (from pypy).
It really measures stack size, not some arbitrary limit of python calls.
Yes, this have slightly bigger overhead than just passing around number,
but as a side effect solves Lib/test/crashers/recursion_limit_too_high.py
msg61490 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2008-01-22 08:55
Maciek Fijalkowski wrote:
> Maciek Fijalkowski added the comment:
> 
> Attached file that handles stack overflow slightly better (from pypy).
> It really measures stack size, not some arbitrary limit of python calls.
> Yes, this have slightly bigger overhead than just passing around number,
> but as a side effect solves Lib/test/crashers/recursion_limit_too_high.py

Where is the file?
msg61491 - (view) Author: Maciek Fijalkowski (fijal) Date: 2008-01-22 08:57
Wuaaa, sorry
msg61500 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2008-01-22 11:20
Maciek Fijalkowski wrote:
> Wuaaa, sorry
> 
> Added file: http://bugs.python.org/file9259/stack.h

Can you provide a working patch, please? The file doesn't explain how it
should be plugged into the parser. What's the license of the file? We
can't just add code from another project.
msg61501 - (view) Author: Maciek Fijalkowski (fijal) Date: 2008-01-22 11:29
PyPy is all MIT, no problem at license. This should not be plugged into 
the parser, this is not a patch (especially not a patch for the parser). 
This file is rather to illustrate possible solution to solve the problem 
of sys.setrecursionlimit not being a robust solution, but just a quick 
hack. Instead of having a counter (which is sometimes too big, sometimes 
too small, depending on amount of C code in between the stack checks), 
it provides a way of measuring the size of a stack actually used. The 
idea is to store the address of local variable somewhere in the 
beginning and compare it to addresses of local variables in consecutive 
calls to LL_stack_too_big (all stored per-thread). This seems to be a 
better solution (ie pypy does not segfault on any of Lib/test/crashers, 
particularly not on ones involving unevident C infinite loop). Yes, it 
has some performance penalty (hard to tell exactly what without trying).

Hum, this indeed might be not a best place to have such discussion, what 
about moving this to another, more general issue?

Cheers,
fijal

:.
msg61502 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2008-01-22 11:47
Maciek Fijalkowski wrote:
> Hum, this indeed might be not a best place to have such discussion, what 
> about moving this to another, more general issue?

Ah! :) It took me a while to understand your intention but now I get
you! The python-dev mailing list is probably a better place than the bug
tracker.

Christian
msg62181 - (view) Author: Ralf Schmitt (schmir) Date: 2008-02-07 20:59
when I set the the stack size to 128kb on a 64bit linux with ulimit -s
128, the tests still pass (default stack size is 8192 kb).

However the following fails at recursion level 180 with a segfault:
def f(count):
    print count
    f(count+1)
f(0)

If I set the stack size to 96k, the interpreter cannot even start that
script. So this change should be pretty safe to not overwrite stack
boundaries.

Anything else I can do to get this in?
msg62720 - (view) Author: Facundo Batista (facundobatista) * (Python committer) Date: 2008-02-23 12:03
Applied in r60974.

Maciek, please push that alternative way of handling this limit on
python-dev, that could lead to a better handling in the future.

But, so far, we have a limit a little upper, and tested.

Thank you all!
msg62726 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2008-02-23 13:19
For the record:
I had to decrease the level to 93. The test in test_parser didn't pass
with 99 levels.
History
Date User Action Args
2008-02-23 13:19:01christian.heimessetmessages: + msg62726
2008-02-23 12:03:12facundobatistasetstatus: open -> closed
resolution: accepted
messages: + msg62720
2008-02-07 20:59:33schmirsetmessages: + msg62181
2008-01-22 11:47:07christian.heimessetmessages: + msg61502
2008-01-22 11:29:05fijalsetmessages: + msg61501
2008-01-22 11:20:20christian.heimessetmessages: + msg61500
2008-01-22 08:57:47fijalsetfiles: + stack.h
messages: + msg61491
2008-01-22 08:55:15christian.heimessetmessages: + msg61490
2008-01-22 08:43:42fijalsetnosy: + fijal
messages: + msg61489
2008-01-22 08:37:35schmirsetmessages: + msg61488
2008-01-22 08:35:44schmirsetfiles: + up-maxstack+tests.txt
messages: + msg61487
2008-01-21 18:45:06facundobatistasetnosy: + facundobatista
messages: + msg61438
2008-01-21 18:16:10gvanrossumsetmessages: + msg61432
2008-01-21 14:03:14christian.heimessetpriority: normal
nosy: + christian.heimes
messages: + msg61395
2008-01-21 13:39:59georg.brandlsetassignee: gvanrossum
messages: + msg61392
nosy: + georg.brandl, gvanrossum
2008-01-21 10:15:52schmirsetfiles: + up-maxstack.txt
versions: + Python 2.6
2008-01-21 10:08:59schmircreate