Stack overflow on GC of deeply nested filter()

[YaoJiayi]

Crash report

The in-built function filter() crashes as the following:

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

Error messages

Segmentation fault (core dumped)

Your environment

• CPython versions tested on: Python 3.9.12
• Operating system and architecture: Linux hx-rs4810gs 5.15.0-57-generic 63~20.04.1-Ubuntu SMP Wed Nov 30 13:40:16 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux

Linked PRs

• gh-102356: Add trashcan macros to filter object dealloc #102426
• [3.11] gh-102356: Add thrashcan macros to filter object dealloc (GH-102426) #102435
• [3.10] gh-102356: Add thrashcan macros to filter object dealloc (GH-102426) #102436

[zware]

I can't reproduce this crash either, much like yesterday's gh-102329. I think you're going to need to be much more specific about your environment, where the python you're using came from, and as many other details as you can share before your crashes start making sense to anyone else. I was wrong; see below.

[pochmann]

Reproduced in 3.10.6 with this, which does print the 'done' and then segfaults:

i = filter(None, ())
for _ in range(1000000):
    i = filter(None, i)
print('done')

Attempt This Online! (click "Execute" there to watch it crash after 1-2 seconds)

[terryjreedy]

This executes on Windows 10 with 3.12.0a5 in both IDLE and 3.12.0a5+ REPL built yesterday. About a minute in REPL and faster in IDLE. Result:

>>> i
<filter object at 0x000002427CA6BBB0>

This bashes the compiler pretty hard, but we got a new parser-compiler in 3.10. Some of the nesting limits have since been removed. This should be closed unless someone reproduces with the last release or later repository build.

[zware]

Ok, turns out I can reproduce, but the segfault happens during cleanup, not immediately.

@pablogsal, this looks like something in your area.

[terryjreedy]

For me, does not crash in REPL close or file run with installed or built debug binary. (Debug runs 2-3 minutes instead of 5 secs.)

f:\dev\3x>python
Running Debug|x64 interpreter...
Python 3.12.0a5+ (heads/main-dirty:2f62a5da94, Mar  1 2023, 13:54:38) [MSC v.1932 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> i=filter(bool, range(10_000_000))
>>> for _ in range(10_000_000):
...     i = filter(bool, i)
...
>>> i
<filter object at 0x00000222491EBD90>
>>> quit()

f:\dev\3x>python f:/dev/tem/tem.py
Running Debug|x64 interpreter...
done

f:\dev\3x>py -3.12 f:/dev/tem/tem.py  # Same with 3.11.2
done

f:\dev\3x>

[JelleZijlstra]

I was able to reproduce with 3.11.2 on Linux. The backtrace starts:

Program received signal SIGSEGV, Segmentation fault.
filter_dealloc (lz=0xffffdb2c79d0) at Python/bltinmodule.c:557
557     {
(gdb) bt
#0  filter_dealloc (lz=0xffffdb2c79d0) at Python/bltinmodule.c:557
#1  0x0000aaaaaad335f0 in Py_DECREF (op=<optimized out>) at ./Include/object.h:538
#2  Py_XDECREF (op=<optimized out>) at ./Include/object.h:602
#3  filter_dealloc (lz=0xffffdb2c7a00) at Python/bltinmodule.c:560
#4  0x0000aaaaaad335f0 in Py_DECREF (op=<optimized out>) at ./Include/object.h:538
#5  Py_XDECREF (op=<optimized out>) at ./Include/object.h:602
#6  filter_dealloc (lz=0xffffdb2c7a30) at Python/bltinmodule.c:560
#7  0x0000aaaaaad335f0 in Py_DECREF (op=<optimized out>) at ./Include/object.h:538
#8  Py_XDECREF (op=<optimized out>) at ./Include/object.h:602
#9  filter_dealloc (lz=0xffffdb2c7a60) at Python/bltinmodule.c:560
#10 0x0000aaaaaad335f0 in Py_DECREF (op=<optimized out>) at ./Include/object.h:538
#11 Py_XDECREF (op=<optimized out>) at ./Include/object.h:602
#12 filter_dealloc (lz=0xffffdb2c7a90) at Python/bltinmodule.c:560
#13 0x0000aaaaaad335f0 in Py_DECREF (op=<optimized out>) at ./Include/object.h:538

Seems like it segfaults because all the filter objects are decrefing each other recursively, overflowing the stack. For me it segfaulted after well over 10k calls, but of course the exact number will be system dependent.

[sweeneyde]

I think many objects have this property.

>>> from itertools import pairwise
>>> x = "foobar"
>>> for _ in range(10**6):
...     x = pairwise(x)
...
>>> del x
(crashes)

It also works for enumerate, and some other itertools. Interestingly, repeating x = map(abs, x) doesn't crash anything, since internally, map stores a tuple of iterators, and tuples use the TRASHCAN mechanism.

I'm not sure whether or not the TRASHCAN mechanism is worth adding to all these cases to protect against artificially nested objects like this.

[sweeneyde]

This is similar to #87053, where deallocating a different deeply-nested web of objects causes a similar C stack overflow.

#89060 might fix this across the board.

[pablogsal]

I am taking a look at this, even if we apply #89060 we probably will need to backport so we need to solve the old fashion way. I am also mentoring someone and this can be a good bug to fix so it may take a bit more time to get a PR done.