deeply nested itertools objects segfault

@arigo

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']

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

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

Since the paste is dead:

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

for p in i:
    print(p)

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.

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

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

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

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

LGTM otherwise.

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.

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

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.

See bpo-24606 for another instance of this in map().

See bpo-30297 for yet one instance of this in starmap().

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

~~This was fixed by #132280~~

The stack overflow in dealloc was fixed by #132280, but the general issue remains.
We should fix this.

Navigation Menu

Repository navigation

deeply nested itertools objects segfault #58218

11 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

deeply nested itertools objects segfault #58218

Description

Activity

alex commented on Feb 14, 2012

arigo commented on Feb 14, 2012

alex commented on Nov 9, 2012

serhiy-storchaka commented on Mar 19, 2013

amauryfa commented on Mar 19, 2013

serhiy-storchaka commented on Mar 19, 2013

serhiy-storchaka commented on Mar 19, 2013

amauryfa commented on Mar 24, 2013

serhiy-storchaka commented on Apr 6, 2013

python-dev commented on Apr 6, 2013

rhettinger commented on Apr 6, 2013

11 remaining items

serhiy-storchaka commented on Jul 11, 2015

serhiy-storchaka commented on May 7, 2017

rhettinger commented on Aug 24, 2019

markshannon commented on Jul 29, 2026

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions