How to cause stack overflow and heap overflow in python

Question

I am trying to understand how python manages stack and heap. So I wanted to do some "bad" programming and cause a stack overflow and heap overflow. What I don't understand is why strings for example go to stack while all others go to heap. Is it just agreement of the designers? Are the examples correct? From what I have read everything in python is generated in heap since its object oriented, right?

EDITED: I suppose that stack in languages like C have a fixed length but in python even the stack is dynamically allocated as Anycorn said in his answer. Thats why I also get full memory if I try both a large string (on stack) or a list (on heap). If i am wrong please correct me. Thanks

From http://docs.python.org/c-api/memory.html

Memory management in Python involves a private heap containing all Python objects and data structures. The management of this private heap is ensured internally by the Python memory manager. The Python memory manager has different components which deal with various dynamic storage management aspects, like sharing, segmentation, preallocation or caching.

At the lowest level, a raw memory allocator ensures that there is enough room in the private heap for storing all Python-related data by interacting with the memory manager of the operating system. On top of the raw memory allocator, several object-specific allocators operate on the same heap and implement distinct memory management policies adapted to the peculiarities of every object type.

Here are some examples. You can copy paste them in Python official visualizer but with smaller values cause it wont run...

For stack overflow:

import time
word = "test "
x = word*1000000000
time.sleep(10)
print ("this message wont appear if stack overflow has occurred!") 

I get

x = word*1000000000
MemoryError

If I delete one zero it runs. I get max memory usage when I use x = word*500000000 So I can't make a stack overflow because even the stack is dynamically allocated?

For heap overflow:

i = 10000
test_list = [0]
while i > 0 :
    test_list [:0] = test_list #insert a copy of itself at the beginning
    i -= 1

Now what I don't understand is how the garbage collector kicks in the programs.Does it run on both stack and heap since they are both dynamically allocated? Is it due to O/S memory manager? What do those things tell us about the characterization of python programming language? Does this justify the term "dynamic language" or "interpreted"? Sorry for the long question but i just need to clarify some things in my mind. Thanks in advance!

EDITED
I've found what i was looking for: You can cause a 'real' stack overflow if you call sys.setrecursionlimit(N) with a value of N larger than your system can actually handle and then try to recurse to that depth. At some point your system will run out of stack space and the Python interpreter will crash.

Answer 1

You can cause a stack overflow quite easily in python, as in any other language, by building an infinately recursive funcion. This is easier in python as it doesn't actually have to do anything at all other than be recursive.

>>> def foo():
...     return foo()
... 

>>> foo()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  .......
  File "<stdin>", line 2, in foo
RuntimeError: maximum recursion depth exceeded
>>> 

As for the heap, that is managed by a garbage collector. You can allocate lots of objects and eventually run out of heap space and Python will raise a MemoryError, but it's going to take a fair amount of time. You actually did that with your 'stack overflow' example in the question. You stored a reference to a string on the stack, this string took up all the free memory available to the process. As a rule of thumb, Python stores a reference to a heap structure on the stack for any value that it can't guarantee the size of.

As for how it all works, from the fist example you can see that python has a built-in limit to the depth of the call stack that it will not exceed. The amount of memory available for heap space is defined by the OS however and will depend upon many factors.

These are should be the appropriate parts of the python docs for infomation on the errors themselves:

• http://docs.python.org/release/3.2.3/library/exceptions.html#RuntimeError
• http://docs.python.org/release/3.2.3/library/exceptions.html#MemoryError

Answer 2

please correct me if wrong:

As far as I know, when it comes to actual stack implementation, the python stack (in the default distribution) is actually based in the heap memory (memory allocated with malloc). So you cannot cause the stack overflow, but you can run out of memory. The computer slowdown you seen is because memory is being swapped to disk, very slow procedure.

generally, you have no idea how the interpreted/byte-compiled language implements its stack, but most like it is not implemented in the stack memory, so you cannot cause stack overflow. it is possible to implement Python using alloca, but why?

Cf. CPython - Internally, what is stored on the stack and heap?

Try the same experiment with compiled language, C++, Fortran, etc. which compiles to machine code.