Using tracing to jump out of a loop causes the Python object stack to overflow

[GoogleCodeExporter]

Run attached script (preferably under a debug build)

It should print out "jumping from line 4 to line 1" 10000 times and then
exit cleanly.
Under a debug build it crashes like this:
0: jumping from line 4 to line 1
1: jumping from line 4 to line 1
Assertion failed: STACK_LEVEL() <= co->co_stacksize, file
..\Python\eval.cc, line 2548

I suspect this is related to r663 and frame_setlineno not having the
blockstack information with which to reset the stack pointer.

Original issue reported on code.google.com by abbeyj on 20 Nov 2009 at 2:44

Attachments:

• tr.py

[GoogleCodeExporter]

I'll try to take a look at this this weekend.

Original comment by collinw on 21 Nov 2009 at 1:24

• Changed state: Accepted
• Added labels: Release-2009Q4

[GoogleCodeExporter]

I've been thinking about a possible way to address this.  Lets say we changed 
things
so that the stack effect of every opcode was fixed.  This would have a couple of
advantages:
(1) The max stack size for a code object could be determined exactly instead of 
the
conservative estimate now used by stackdepth() / opcode_stack_effect()
(2) The stack level for a given instruction would always be the same, 
independent of
the execution path taken to arrive there so it could be determined by a static
analysis of the bytecode.

I have a proof-of-concept patch to do this and it seems to work.  The changes 
are
mostly to WITH_CLEANUP and END_FINALLY.  Pseudo-exceptions are padded to three 
stack
slots with Py_None so that they take the same amount of space as real 
exceptions.

I think it should then be easy to handle jumping with f_lineno.  Say that the 
stack
level at an instruction 'x' is SL(x).  Then we can jump from instruction A to
instruction C if and only if:
(a) SL(A) >= SL(C)
(b) every instruction 'x' between A and C has SL(x) >= SL(C)

For condition (a): we clearly can't jump from A to C if SL(A) < SL(C) because we
don't have enough items on the stack.  We can jump if SL(A) >= SL(C) by just 
throwing
away any unneeded items off the top of the stack.  

For condition (b): we don't want to do the jump even if the stack levels at the 
start
and end are compatible but the stack level fell in between.  This would mean 
that
some existing value got popped off and was replaced by something we can't 
predict. 
For example:

for i in [1]:  # SL = 0
  z = 2        # SL = 1
for j in [3]:  # SL = 0
  z = 4        # SL = 1

Jumping from line 2 to line 4 would satisfy condition (a) but doing the jump 
would
leave the wrong iterator on the stack.

Note that we only care about relative stack levels in this computation, so, as 
an
optimization, one could avoid computing the stack level of A (which would 
involve
looking at all the instructions before A).

Are there any cases I'm not thinking about that would trip this scheme up?

Another nice benefit is that this might allow llvm_compile / llvm_fbuilder to 
move
most of the stack pointer calculations from run-time to compile-time but I'm 
not sure
if that's worthwhile.

Original comment by abbeyj on 22 Nov 2009 at 8:05

[GoogleCodeExporter]

The proof-of-concept patch I mentioned earlier is available here:
http://codereview.appspot.com/157148

Original comment by abbeyj on 24 Nov 2009 at 5:10