crash when deleting one pair from tee()

[PyryP]

BPO	13454
Nosy	@birkenfeld, @rhettinger, @amauryfa, @pitrou, @vstinner, @ezio-melotti, @serhiy-storchaka
Files	itertools_tee_nonrecursive_clear.patch itertools_tee_nonrecursive_clear_2.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/serhiy-storchaka'
closed_at = <Date 2013-01-25.11:36:17.711>
created_at = <Date 2011-11-22.16:10:44.540>
labels = ['extension-modules', 'type-crash']
title = 'crash when deleting one pair from tee()'
updated_at = <Date 2013-01-26.09:56:33.793>
user = 'https://bugs.python.org/PyryP'

bugs.python.org fields:

activity = <Date 2013-01-26.09:56:33.793>
actor = 'python-dev'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2013-01-25.11:36:17.711>
closer = 'serhiy.storchaka'
components = ['Extension Modules']
creation = <Date 2011-11-22.16:10:44.540>
creator = 'PyryP'
dependencies = []
files = ['27578', '28467']
hgrepos = []
issue_num = 13454
keywords = ['patch', 'needs review']
message_count = 14.0
messages = ['148124', '148125', '148126', '148127', '172890', '172905', '172916', '174473', '178324', '178370', '178399', '179466', '180568', '180649']
nosy_count = 9.0
nosy_names = ['georg.brandl', 'rhettinger', 'amaury.forgeotdarc', 'pitrou', 'vstinner', 'ezio.melotti', 'python-dev', 'PyryP', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue13454'
versions = ['Python 2.7', 'Python 3.2', 'Python 3.3', 'Python 3.4']

[PyryP]

Running the following results in a Segmentation fault on Ubuntu 11.10 64-bit with both python and python3.

from itertools import *
c = count()
a,b = tee(c)
for i in range(10000000):
 next(a)
del(b)

[vstinner]

tee() uses a linked-list of teedataobject. This list is destroyed by recursive calls to teedataobject_dealloc().

Extract of the gdb trace:

#5 0x08171a8e in teedataobject_clear (tdo=0xad21b394) at ./Modules/itertoolsmodule.c:412
#6 0x08171b39 in teedataobject_dealloc (tdo=0xad21b394) at ./Modules/itertoolsmodule.c:421
#7 0x0805ed3d in _Py_Dealloc (op=<itertools.tee_dataobject at remote 0xad21b394>) at Objects/object.c:1676
#8 0x08171b16 in teedataobject_clear (tdo=0xad21b274) at ./Modules/itertoolsmodule.c:413
#9 0x08171b39 in teedataobject_dealloc (tdo=0xad21b274) at ./Modules/itertoolsmodule.c:421
#10 0x0805ed3d in _Py_Dealloc (op=<itertools.tee_dataobject at remote 0xad21b274>) at Objects/object.c:1676
#11 0x08171b16 in teedataobject_clear (tdo=0xad21b154) at ./Modules/itertoolsmodule.c:413
#12 0x08171b39 in teedataobject_dealloc (tdo=0xad21b154) at ./Modules/itertoolsmodule.c:421
#13 0x0805ed3d in _Py_Dealloc (op=<itertools.tee_dataobject at remote 0xad21b154>) at Objects/object.c:1676
#14 0x08171b16 in teedataobject_clear (tdo=0xad21b034) at ./Modules/itertoolsmodule.c:413
#15 0x08171b39 in teedataobject_dealloc (tdo=0xad21b034) at ./Modules/itertoolsmodule.c:421
#16 0x0805ed3d in _Py_Dealloc (op=<itertools.tee_dataobject at remote 0xad21b034>) at Objects/object.c:1676
#17 0x08171b16 in teedataobject_clear (tdo=0xad292ed4) at ./Modules/itertoolsmodule.c:413
#18 0x08171b39 in teedataobject_dealloc (tdo=0xad292ed4) at ./Modules/itertoolsmodule.c:421
#19 0x0805ed3d in _Py_Dealloc (op=<itertools.tee_dataobject at remote 0xad292ed4>) at Objects/object.c:1676
#20 0x08171b16 in teedataobject_clear (tdo=0xad292db4) at ./Modules/itertoolsmodule.c:413
#21 0x08171b39 in teedataobject_dealloc (tdo=0xad292db4) at ./Modules/itertoolsmodule.c:421
#22 0x0805ed3d in _Py_Dealloc (op=<itertools.tee_dataobject at remote 0xad292db4>) at Objects/object.c:1676
#23 0x08171b16 in teedataobject_clear (tdo=0xad292c94) at ./Modules/itertoolsmodule.c:413

[ezio-melotti]

Confirmed on py3k, it doesn't seem to happen with smaller values.

[amauryfa]

Also, a check for NULL would not hurt in tee_next():

diff -r 1e0e821d2626 Modules/itertoolsmodule.c
--- a/Modules/itertoolsmodule.c	Fri Nov 04 22:17:45 2011 +0100
+++ b/Modules/itertoolsmodule.c	Tue Nov 22 17:24:42 2011 +0100
@@ -475,6 +475,8 @@
 
     if (to->index >= LINKCELLS) {
         link = teedataobject_jumplink(to->dataobj);
+        if (link == NULL)
+            return NULL;
         Py_DECREF(to->dataobj);
         to->dataobj = (teedataobject *)link;
         to->index = 0;

[serhiy-storchaka]

Here is a patch (tests included). Thank Pyry for report, Victor and Amaury for analysis.

Maybe I picked up the poor names for iterators? May be exhausted and unexhausted would be better? Feel free to correct me.

[pitrou]

Serhiy, I only see a test in your patch, no actual modification to itertools.

[serhiy-storchaka]

Oh, I worked on it in a different directory. Fortunately I found a temporary copy and I do not have to write all code again. Sorry.

[serhiy-storchaka]

Please review.

[serhiy-storchaka]

Ping.

[birkenfeld]

The patch replaces a

 Py_CLEAR(tdo->nextlink)

with a construct that does, basically, something like this several times:

 Py_DECREF(tdo->nextlink)
 tdo->nextlink

which is what leads to the issues that Py_CLEAR is supposed to prevent. Therefore I think this patch is not correct.

[serhiy-storchaka]

Good point. Here is updated patch.

[serhiy-storchaka]

If no one objects I will commit this next week.

[python-dev]

New changeset f7e14a1af609 by Serhiy Storchaka in branch '3.2':
Issue bpo-13454: Fix a crash when deleting an iterator created by itertools.tee()
http://hg.python.org/cpython/rev/f7e14a1af609

New changeset eff2a7346243 by Serhiy Storchaka in branch '3.3':
Issue bpo-13454: Fix a crash when deleting an iterator created by itertools.tee()
http://hg.python.org/cpython/rev/eff2a7346243

New changeset 02d7a127fdfb by Serhiy Storchaka in branch 'default':
Issue bpo-13454: Fix a crash when deleting an iterator created by itertools.tee()
http://hg.python.org/cpython/rev/02d7a127fdfb

New changeset 62f2d3f6015e by Serhiy Storchaka in branch '2.7':
Issue bpo-13454: Fix a crash when deleting an iterator created by itertools.tee()
http://hg.python.org/cpython/rev/62f2d3f6015e

[python-dev]

New changeset 4ee8d38398d4 by Serhiy Storchaka in branch '2.7':
Optimize the test for issue bpo-13454.
http://hg.python.org/cpython/rev/4ee8d38398d4

New changeset d391b2849a51 by Serhiy Storchaka in branch '3.2':
Optimize the test for issue bpo-13454.
http://hg.python.org/cpython/rev/d391b2849a51

New changeset 2258b4d89c9f by Serhiy Storchaka in branch '3.3':
Optimize the test for issue bpo-13454.
http://hg.python.org/cpython/rev/2258b4d89c9f

New changeset 1f57fb5e1e8e by Serhiy Storchaka in branch 'default':
Optimize the test for issue bpo-13454.
http://hg.python.org/cpython/rev/1f57fb5e1e8e