deeply nested itertools objects segfault

[alex]

BPO	14010
Nosy	@arigo, @birkenfeld, @rhettinger, @amauryfa, @benjaminp, @ezio-melotti, @alex, @serhiy-storchaka
Files	iter_recursion.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2019-08-24.04:43:08.908>
created_at = <Date 2012-02-14.15:58:25.896>
labels = ['extension-modules', 'interpreter-core', 'type-crash']
title = 'deeply nested itertools objects segfault'
updated_at = <Date 2019-08-24.04:43:08.907>
user = 'https://github.com/alex'

bugs.python.org fields:

activity = <Date 2019-08-24.04:43:08.907>
actor = 'rhettinger'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2019-08-24.04:43:08.908>
closer = 'rhettinger'
components = ['Extension Modules', 'Interpreter Core']
creation = <Date 2012-02-14.15:58:25.896>
creator = 'alex'
dependencies = []
files = ['29483']
hgrepos = []
issue_num = 14010
keywords = ['patch']
message_count = 25.0
messages = ['153344', '153353', '175242', '184631', '184632', '184633', '184660', '185140', '186141', '186143', '186144', '186145', '186147', '186153', '186156', '186157', '186158', '186159', '186161', '199738', '231490', '231535', '246594', '293208', '350347']
nosy_count = 9.0
nosy_names = ['arigo', 'georg.brandl', 'rhettinger', 'amaury.forgeotdarc', 'benjamin.peterson', 'ezio.melotti', 'alex', 'python-dev', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'wont fix'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue14010'
versions = ['Python 2.7', 'Python 3.3', 'Python 3.4', 'Python 3.5', 'Python 3.6']

[alex]

http://paste.pocoo.org/show/550884/ will reliably segfault Python3 on all platforms (similar versions for Python2 using itertools work)

[arigo]

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 :-(

[alex]

Since the paste is dead:

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

for p in i:
 print(p)

[serhiy-storchaka]

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.

[amauryfa]

Py_TRASHCAN_SAFE_BEGIN/Py_TRASHCAN_SAFE_END macros can help:
http://hg.python.org/cpython/file/57c6435ca03b/Python/traceback.c#l44

[serhiy-storchaka]

Thank you. Now I understand why this issue not happened with containers.

[serhiy-storchaka]

Here is a patch which adds recursion limit checks to builtin and itertools recursive iterators.

[amauryfa]

• The tests with "range(1000000)" seems to duplicate those with recursion limit.
• zip_iter should would be simpler with a "goto error;"

LGTM otherwise.

[serhiy-storchaka]

• 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.

[python-dev]

New changeset aaaf36026511 by Serhiy Storchaka in branch '3.3':
Issue bpo-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 bpo-14010: Fix a crash when iterating or deleting deeply nested filters
http://hg.python.org/cpython/rev/846bd418aee5

[rhettinger]

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.