This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

classification
Title: deeply nested itertools objects segfault
Type: crash Stage: resolved
Components: Extension Modules, Interpreter Core Versions: Python 3.6, Python 3.3, Python 3.4, Python 3.5, Python 2.7
process
Status: closed Resolution: wont fix
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 2022-04-11 14:57 by admin. This issue is now closed.

Files
File name Uploaded Description Edit
iter_recursion.patch serhiy.storchaka, 2013-03-19 18:39 review
Messages (25)
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) (Python triager) 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) (Python triager) 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) (Python triager) 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().
msg231490 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2014-11-21 19:07
See issue22911 for another instance of this in chain.from_iterable().
msg231535 - (view) Author: Ethan Furman (ethan.furman) * (Python committer) Date: 2014-11-22 22:05
From Terry Reedy in issue22920:
------------------------------
Ian Kelly (python-list, version unspecified) got "Segmentation fault (core dumped)".  With 2.7, 3.4.2, 3.5, I get same in interactive interpreter, the Windows "python has stopped working" box from console, or subprocess hang with Idle.
msg246594 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-07-11 04:52
See issue24606 for another instance of this in map().
msg293208 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-05-07 18:45
See issue30297 for yet one instance of this in starmap().
msg350347 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-08-24 04:43
[Armin]
> 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.

I agree with that assessment and am going to close this as something we can live with (or least have lived with successfully for a long time).  AFAICT, this situation doesn't arise in practical code.

It is possible to slow down the language by adding a variant of recursion checks to every call to an iterator.  But this just makes the language pay a code complexity cost and performance cost for something that doesn't really affect real users.  People typically choose itertools for their speed (otherwise, plain generators can be clearer).  We shouldn't work against the needs of those users.

A robust, clean, and performant solution wouldn't be easy but would likely involve some general purpose stack overflow protection that periodically makes sure there is enough stack remaining for C Python to function correctly.
History
Date User Action Args
2022-04-11 14:57:26adminsetgithub: 58218
2019-08-24 04:43:08rhettingersetstatus: open -> closed
resolution: wont fix
messages: + msg350347

stage: needs patch -> resolved
2018-01-28 03:22:14ppperrysettitle: deeply nested filter segfaults -> deeply nested itertools objects segfault
2017-05-07 18:45:58serhiy.storchakasetmessages: + msg293208
2017-05-07 18:44:05serhiy.storchakalinkissue30297 superseder
2015-10-17 06:58:28serhiy.storchakalinkissue25429 superseder
2015-07-21 07:04:02ethan.furmansetnosy: - ethan.furman
2015-07-11 04:52:32serhiy.storchakasetmessages: + msg246594
versions: + Python 3.6
2015-07-11 04:50:56serhiy.storchakalinkissue24606 superseder
2014-11-22 22:05:11ethan.furmansetnosy: + ethan.furman

messages: + msg231535
versions: + Python 3.5
2014-11-22 22:03:50ethan.furmanlinkissue22920 superseder
2014-11-21 19:08:29serhiy.storchakalinkissue22911 superseder
2014-11-21 19:07:42serhiy.storchakasetmessages: + msg231490
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