classification
Title: deeply nested filter segfaults
Type: crash Stage: needs patch
Components: Extension Modules, Interpreter Core Versions: Python 3.4, Python 3.3, Python 2.7
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: alex, amaury.forgeotdarc, arigo, benjamin.peterson, ezio.melotti, georg.brandl, python-dev, rhettinger, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2012-02-14 15:58 by alex, last changed 2013-10-13 17:55 by georg.brandl.

Files
File name Uploaded Description Edit
iter_recursion.patch serhiy.storchaka, 2013-03-19 18:39 review
Messages (20)
msg153344 - (view) Author: Alex Gaynor (alex) * (Python committer) Date: 2012-02-14 15:58
http://paste.pocoo.org/show/550884/ will reliably segfault Python3 on all platforms (similar versions for Python2 using itertools work)
msg153353 - (view) Author: Armin Rigo (arigo) * (Python committer) Date: 2012-02-14 17:11
The issue is a stack exhaustion.  Examples can be trivially made for any iterator that takes another iterator as argument: itertools.takewhile(), zip() in Python3, etc. etc.

It's just one of many places where CPython does a recursion without checking the recursion depth.  CPython still works, based on the resonable assumption that doing such a recursion here is obscure.

Someone seriously bored could start with some C-based callgraph builder; or alternatively use PyPy, which finds such recursions automatically in its own source, and compare all places where a recursion check is inserted with the corresponding place in CPython.  There are a large number of them (761, not counting the JIT), so be patient :-(
msg175242 - (view) Author: Alex Gaynor (alex) * (Python committer) Date: 2012-11-09 14:46
Since the paste is dead:

i = filter(bool, range(5))
for _ in range(1000000):
    i = filter(bool, i)

for p in i:
    print(p)
msg184631 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-03-19 13:28
I'm trying to solve this issue (it seemed easy), but the bug is worse than expected. Python crashed even without iteration at all.

it = 'abracadabra'
for _ in range(1000000):
    it = filter(bool, it)

del it

And fixing a recursive deallocator is more harder than iterator.

What can we do if a deallocator raises RuntimeError due to maximum recursion depth exceeded.
msg184632 - (view) Author: Amaury Forgeot d'Arc (amaury.forgeotdarc) * (Python committer) Date: 2013-03-19 13:33
Py_TRASHCAN_SAFE_BEGIN/Py_TRASHCAN_SAFE_END macros can help:
http://hg.python.org/cpython/file/57c6435ca03b/Python/traceback.c#l44
msg184633 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-03-19 13:37
Thank you. Now I understand why this issue not happened with containers.
msg184660 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-03-19 18:39
Here is a patch which adds recursion limit checks to builtin and itertools recursive iterators.
msg185140 - (view) Author: Amaury Forgeot d'Arc (amaury.forgeotdarc) * (Python committer) Date: 2013-03-24 15:43
- The tests with "range(1000000)" seems to duplicate those with recursion limit.
- zip_iter should would be simpler with a "goto error;"

LGTM otherwise.
msg186141 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-04-06 17:22
> - The tests with "range(1000000)" seems to duplicate those with recursion limit.

Oh, I forgot to remove old tests when had moved them to special test class.

> - zip_iter should would be simpler with a "goto error;"

Indeed. Thank you.
msg186143 - (view) Author: Roundup Robot (python-dev) Date: 2013-04-06 18:21
New changeset aaaf36026511 by Serhiy Storchaka in branch '3.3':
Issue #14010: Fix a crash when iterating or deleting deeply nested filters
http://hg.python.org/cpython/rev/aaaf36026511

New changeset 846bd418aee5 by Serhiy Storchaka in branch 'default':
Issue #14010: Fix a crash when iterating or deleting deeply nested filters
http://hg.python.org/cpython/rev/846bd418aee5
msg186144 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2013-04-06 18:56
This patch didn't have my sign-off.  Applying it was premature.  It is a somewhat heavy handed fix that slows all the common cases at the expense of an exotic case.
msg186145 - (view) Author: Roundup Robot (python-dev) Date: 2013-04-06 19:04
New changeset d17d10c84d27 by Serhiy Storchaka in branch '2.7':
Issue #14010: Fix a crash when iterating or deleting deeply nested filters
http://hg.python.org/cpython/rev/d17d10c84d27
msg186147 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-04-06 19:09
Oh, shame on me. Do I have to immediately revert patches or wait for your post-commit review?
msg186153 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2013-04-06 19:31
I would appreciate it if you would please revert this patch.  

We need to search for a solution that isn't as fine grained (i.e. not doing increments, decrements, and tests on every single call to iter_next).  Ideally, the checks can be confined to the iterator constructor and to dealloc.  Or you could try to create some general purpose stack overflow protection that periodically makes sure there is enough stack remaining for C Python to function correctly.
msg186156 - (view) Author: Amaury Forgeot d'Arc (amaury.forgeotdarc) * (Python committer) Date: 2013-04-06 19:42
> Or you could try to create some general purpose stack overflow
> protection that periodically makes sure there is enough stack remaining
> for C Python to function correctly.

Isn't it exactly what Py_EnterRecursiveCall does?
msg186157 - (view) Author: Benjamin Peterson (benjamin.peterson) * (Python committer) Date: 2013-04-06 19:43
It has no notion of how big the C stack is.

2013/4/6 Amaury Forgeot d'Arc <report@bugs.python.org>:
>
> Amaury Forgeot d'Arc added the comment:
>
>> Or you could try to create some general purpose stack overflow
>> protection that periodically makes sure there is enough stack remaining
>> for C Python to function correctly.
>
> Isn't it exactly what Py_EnterRecursiveCall does?
>
> ----------
>
> _______________________________________
> Python tracker <report@bugs.python.org>
> <http://bugs.python.org/issue14010>
> _______________________________________
msg186158 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2013-04-06 19:54
> Isn't it exactly what Py_EnterRecursiveCall does?

No, it isn't.  Py_EnterRecursiveCall() counts calls and measures depth.  It is sprinked all over the source code, everywhere a potentially recursive call could be made.  

Instead, it would be nice if the interpreter could monitor the actual stack size and take appropriate actions when it is running low on space.  The would save us from putting in expensive fine grained checks throughout the source code.
msg186159 - (view) Author: Roundup Robot (python-dev) Date: 2013-04-06 19:58
New changeset e07e6d828150 by Serhiy Storchaka in branch '2.7':
Revert a premature patch for issue #14010 (changeset d17d10c84d27).
http://hg.python.org/cpython/rev/e07e6d828150

New changeset 7b75f0bd9a5e by Serhiy Storchaka in branch '3.3':
Revert a premature patch for issue #14010 (changeset aaaf36026511).
http://hg.python.org/cpython/rev/7b75f0bd9a5e

New changeset 504eed5a82a3 by Serhiy Storchaka in branch 'default':
Revert a premature patch for issue #14010 (changeset 846bd418aee5).
http://hg.python.org/cpython/rev/504eed5a82a3
msg186161 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-04-06 20:03
I apologize for my negligence.
msg199738 - (view) Author: Georg Brandl (georg.brandl) * (Python committer) Date: 2013-10-13 17:55
See issue14507 for another instance of this in starmap().
History
Date User Action Args
2013-10-13 17:55:33georg.brandlsetnosy: + georg.brandl
messages: + msg199738
2013-10-13 17:55:16georg.brandllinkissue14507 superseder
2013-04-06 20:03:42serhiy.storchakasetmessages: + msg186161
stage: commit review -> needs patch
2013-04-06 19:58:41python-devsetmessages: + msg186159
2013-04-06 19:54:30rhettingersetmessages: + msg186158
2013-04-06 19:43:38benjamin.petersonsetmessages: + msg186157
2013-04-06 19:42:47amaury.forgeotdarcsetmessages: + msg186156
2013-04-06 19:31:09rhettingersetmessages: + msg186153
2013-04-06 19:09:39serhiy.storchakasetmessages: + msg186147
stage: patch review -> commit review
2013-04-06 19:04:58python-devsetmessages: + msg186145
2013-04-06 18:56:39rhettingersetmessages: + msg186144
2013-04-06 18:21:30python-devsetnosy: + python-dev
messages: + msg186143
2013-04-06 17:22:39serhiy.storchakasetmessages: + msg186141
versions: - Python 3.2
2013-03-24 16:21:03rhettingersetassignee: rhettinger
2013-03-24 15:43:53amaury.forgeotdarcsetmessages: + msg185140
2013-03-19 18:39:03serhiy.storchakasetfiles: + iter_recursion.patch

components: + Extension Modules

keywords: + patch
nosy: + rhettinger
messages: + msg184660
stage: needs patch -> patch review
2013-03-19 13:37:05serhiy.storchakasetmessages: + msg184633
2013-03-19 13:33:00amaury.forgeotdarcsetnosy: + amaury.forgeotdarc
messages: + msg184632
2013-03-19 13:28:33serhiy.storchakasetmessages: + msg184631
2013-02-26 10:40:16serhiy.storchakalinkissue17300 superseder
2013-02-26 10:30:02ezio.melottisetnosy: + serhiy.storchaka

versions: - Python 2.6, Python 3.1
2012-11-09 14:46:42alexsetmessages: + msg175242
2012-02-14 17:11:20arigosetnosy: + arigo
messages: + msg153353
2012-02-14 16:20:23ezio.melottisetnosy: + ezio.melotti

type: crash
stage: needs patch
2012-02-14 15:58:25alexcreate