Skip to content

Stack overflow on GC of deeply nested filter() #102356

Closed
Closed
Stack overflow on GC of deeply nested filter()#102356
Assignees
pablogsal
Labels
3.10 (EOL)end of life3.11only security fixes3.12only security fixestype-crashA hard crash of the interpreter, possibly with a core dump

Description

@YaoJiayi
YaoJiayi
opened on Mar 1, 2023

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

Activity

  1. YaoJiayi
    added
    type-crashA hard crash of the interpreter, possibly with a core dump
    on Mar 1, 2023

  2. zware commented on Mar 1, 2023

    @zware
    zware
    on Mar 1, 2023
    Member

    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.

  3. pochmann commented on Mar 1, 2023

    @pochmann
    pochmann
    on Mar 1, 2023
    Contributor

    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)

  4. terryjreedy commented on Mar 1, 2023

    @terryjreedy
    terryjreedy
    on Mar 1, 2023
    Member

    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.

  5. zware commented on Mar 1, 2023

    @zware
    zware
    on Mar 1, 2023
    Member

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

    @pablogsal, this looks like something in your area.

  6. zware
    added
    3.11only security fixes
    3.10 (EOL)end of life
    3.12only security fixes
    on Mar 1, 2023

  7. terryjreedy commented on Mar 1, 2023

    @terryjreedy
    terryjreedy
    on Mar 1, 2023
    Member

    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>

  8. JelleZijlstra commented on Mar 1, 2023

    @JelleZijlstra
    JelleZijlstra
    on Mar 1, 2023
    Member

    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.

  9. sweeneyde commented on Mar 1, 2023

    @sweeneyde
    sweeneyde
    on Mar 1, 2023
    Member

    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.

  10. sweeneyde commented on Mar 1, 2023

    @sweeneyde
    sweeneyde
    on Mar 1, 2023
    Member

    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.

  11. JelleZijlstra
    changed the title [-]Function filter() produces segmentation fault[/-] [+]Segmentation fault on deeply nested filter()[/+] on Mar 2, 2023
  12. JelleZijlstra
    changed the title [-]Segmentation fault on deeply nested filter()[/-] [+]Stack overflow on GC of deeply nested filter()[/+] on Mar 2, 2023

  13. pablogsal commented on Mar 3, 2023

    @pablogsal
    pablogsal
    on Mar 3, 2023
    Member

    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.

  14. pablogsal
    self-assigned this
    on Mar 3, 2023
  15. pablogsal
    added a commit that references this issue on Mar 5, 2023

    gh-102356: Add thrashcan macros to filter object dealloc (#102426)

    66aa78c
  16. miss-islington
    added 4 commits that reference this issue on Mar 5, 2023

    pythongh-102356: Add thrashcan macros to filter object dealloc (pytho…

    060e8ac

    pythongh-102356: Add thrashcan macros to filter object dealloc (pytho…

    05ac895

    gh-102356: Add thrashcan macros to filter object dealloc (GH-102426)

    d4a04e5

    gh-102356: Add thrashcan macros to filter object dealloc (GH-102426)

    63fd954
  17. pablogsal
    closed this as completedon Mar 5, 2023

  18. pablogsal commented on Mar 6, 2023

    @pablogsal
    pablogsal
    on Mar 6, 2023
    Member

    This is fixed now and will be available on the next bugfix release of the interpreters

  19. hugovk
    added a commit that references this issue on Mar 6, 2023

    pythongh-102356: Add thrashcan macros to filter object dealloc (pytho…

    028b26a
  20. carljm
    added 2 commits that reference this issue on Mar 6, 2023

    Merge branch 'main' into nodeaddict

    33dda2a

    Merge branch 'main' into inlinecomp2

    ecb313c
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

3.10 (EOL)end of life3.11only security fixes3.12only security fixestype-crashA hard crash of the interpreter, possibly with a core dump

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions