Deallocating highly nested list can cause stack overflow on Alpine Linux (musl)

[vstinner]

Bug report

Bug description:

Example:

import threading

def run_thread(func, *args):
    thread = threading.Thread(target=func, args=args)
    thread.start()
    thread.join()

def producer(results):
    L = [None, None]
    for i in range(5_000):
        L = [i, L]
    results.append(L)

def consumer(results):
    L = results.pop()
    L = None

threading.stack_size(1024*1024)

results = []
run_thread(producer, results)
run_thread(consumer, results)

Example on Alpine Linux (Python linked to musl), Python uses a stack size of 1 MiB:

~/cpython # ./python bug.py 
Segmentation fault (core dumped)

gdb traceback, _Py_MergeZeroLocalRefcount() calls _Py_MergeZeroLocalRefcount() in a loop:

Thread 3 "Thread-2 (consu" received signal SIGSEGV, Segmentation fault.
[Switching to LWP 30901]
0x00005594970a5b41 in _Py_Dealloc (op=0x0) at Objects/object.c:3291
3291	{
(gdb) where
#0  0x00005594970a5b41 in _Py_Dealloc (op=0x0) at Objects/object.c:3291
#1  0x00005594970a054a in _Py_MergeZeroLocalRefcount (op=0x200041aa8d0) at Objects/object.c:444
#2  0x0000559497051010 in Py_DECREF (filename=0x55949745644c "./Include/refcount.h", lineno=520, op=0x200041aa8d0) at ./Include/refcount.h:359
#3  0x000055949705107d in Py_XDECREF (op=0x200041aa8d0) at ./Include/refcount.h:520
#4  0x0000559497054266 in list_dealloc (self=0x200041aa930) at Objects/listobject.c:567
#5  0x00005594970a5c35 in _Py_Dealloc (op=0x200041aa930) at Objects/object.c:3319
#6  0x00005594970a054a in _Py_MergeZeroLocalRefcount (op=0x200041aa930) at Objects/object.c:444
#7  0x0000559497051010 in Py_DECREF (filename=0x55949745644c "./Include/refcount.h", lineno=520, op=0x200041aa930) at ./Include/refcount.h:359
#8  0x000055949705107d in Py_XDECREF (op=0x200041aa930) at ./Include/refcount.h:520
#9  0x0000559497054266 in list_dealloc (self=0x200041aa990) at Objects/listobject.c:567
#10 0x00005594970a5c35 in _Py_Dealloc (op=0x200041aa990) at Objects/object.c:3319
#11 0x00005594970a054a in _Py_MergeZeroLocalRefcount (op=0x200041aa990) at Objects/object.c:444
#12 0x0000559497051010 in Py_DECREF (filename=0x55949745644c "./Include/refcount.h", lineno=520, op=0x200041aa990) at ./Include/refcount.h:359
#13 0x000055949705107d in Py_XDECREF (op=0x200041aa990) at ./Include/refcount.h:520
#14 0x0000559497054266 in list_dealloc (self=0x200041aa9f0) at Objects/listobject.c:567
#15 0x00005594970a5c35 in _Py_Dealloc (op=0x200041aa9f0) at Objects/object.c:3319
#16 0x00005594970a054a in _Py_MergeZeroLocalRefcount (op=0x200041aa9f0) at Objects/object.c:444
#17 0x0000559497051010 in Py_DECREF (filename=0x55949745644c "./Include/refcount.h", lineno=520, op=0x200041aa9f0) at ./Include/refcount.h:359
#18 0x000055949705107d in Py_XDECREF (op=0x200041aa9f0) at ./Include/refcount.h:520
#19 0x0000559497054266 in list_dealloc (self=0x200041aaa50) at Objects/listobject.c:567
#20 0x00005594970a5c35 in _Py_Dealloc (op=0x200041aaa50) at Objects/object.c:3319
#21 0x00005594970a054a in _Py_MergeZeroLocalRefcount (op=0x200041aaa50) at Objects/object.c:444
#22 0x0000559497051010 in Py_DECREF (filename=0x55949745644c "./Include/refcount.h", lineno=520, op=0x200041aaa50) at ./Include/refcount.h:359
#23 0x000055949705107d in Py_XDECREF (op=0x200041aaa50) at ./Include/refcount.h:520
#24 0x0000559497054266 in list_dealloc (self=0x200041aaab0) at Objects/listobject.c:567
#25 0x00005594970a5c35 in _Py_Dealloc (op=0x200041aaab0) at Objects/object.c:3319
#26 0x00005594970a054a in _Py_MergeZeroLocalRefcount (op=0x200041aaab0) at Objects/object.c:444
...

CPython versions tested on:

CPython main branch

Operating systems tested on:

Linux

Linked PRs

• gh-151546: Fix stack limits on musl #151548

[vstinner]

The issue can be reproduced on Linux with Python linked to the glibc.

Apply the following patch:

diff --git a/Python/ceval.c b/Python/ceval.c
index a9b31affca9..8d7c68ea8e1 100644
--- a/Python/ceval.c
+++ b/Python/ceval.c
@@ -141,8 +141,7 @@ hardware_stack_limits(uintptr_t *base, uintptr_t *top, uintptr_t sp)
     /// XXX musl supports HAVE_PTHRED_GETATTR_NP, but the resulting stack size
     /// (on alpine at least) is much smaller than expected and imposes undue limits
     /// compared to the old stack size estimation.  (We assume musl is not glibc.)
-#  if defined(HAVE_PTHREAD_GETATTR_NP) && !defined(_AIX) && \
-        !defined(__NetBSD__) && (defined(__GLIBC__) || !defined(__linux__))
+#  if 0
     size_t stack_size, guard_size;
     void *stack_addr;
     pthread_attr_t attr;

And build Python with ./configure --with-pydebug --disable-gil CFLAGS="-O0" LDFLAGS="-Wl,-z,stack-size=1048576".

Example:

$ ./python bug.py 
Segmentation fault         (core dumped) ./python bug.py

[vstinner]

_Py_Dealloc() has a generic mechanism to avoid stack overflow:

void
_Py_Dealloc(PyObject *op)
{
    PyTypeObject *type = Py_TYPE(op);
    unsigned long gc_flag = type->tp_flags & Py_TPFLAGS_HAVE_GC;
    PyThreadState *tstate = _PyThreadState_GET();
    intptr_t margin = _Py_RecursionLimit_GetMargin(tstate);
    if (margin < 2 && gc_flag) {
        _PyTrash_thread_deposit_object(tstate, (PyObject *)op);
        return;
    }

    ...
}

_Py_RecursionLimit_GetMargin() relies on tstate->c_stack_soft_limit which is set by _Py_InitializeRecursionLimits().

If Python is built with the glibc, pthread_getattr_np() is used to get pthread_attr_getguardsize() and pthread_attr_getstack(). But when Python is built with musl, a fallback is used and it seems like the fallback doesn't compute stack limits properly. My Python/ceval.c patch above disables glibc code path to also use the fallback on glibc.

[vstinner]

Ah, I can also reproduce the bug without Free Threading. I updated the issue title to mention musl instead.

[vstinner]

gdb traceback on a default Python (with GIL), list_dealloc() calls list_dealloc() in a loop:

Thread 3 "Thread-2 (consu" received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0x7fffe99ff6c0 (LWP 504875)]
0x000000000071b410 in _PyObject_GC_IS_TRACKED (op=<error reading variable: Cannot access memory at address 0x7fffe98fffe8>) at ./Include/internal/pycore_gc.h:73
73	static inline int _PyObject_GC_IS_TRACKED(PyObject *op) {
Missing rpms, try: dnf --enablerepo='*debug*' install glibc-debuginfo-2.43-6.fc44.x86_64
(gdb) where
#0  0x000000000071b410 in _PyObject_GC_IS_TRACKED (op=<error reading variable: Cannot access memory at address 0x7fffe98fffe8>) at ./Include/internal/pycore_gc.h:73
#1  0x000000000071b680 in _PyObject_GC_UNTRACK (filename=0x9427a8 "Python/gc.c", lineno=1954, op=0x7fffe9a65400) at ./Include/internal/pycore_gc.h:254
#2  0x000000000071f0ef in PyObject_GC_UnTrack (op_raw=0x7fffe9a65400) at Python/gc.c:1954
#3  0x000000000051be6b in list_dealloc (self=0x7fffe9a65400) at Objects/listobject.c:559

#4  0x00000000005619b1 in _Py_Dealloc (op=0x7fffe9a65400) at Objects/object.c:3319
#5  0x0000000000519d37 in Py_DECREF (filename=0x8ca48c "./Include/refcount.h", lineno=520, op=0x7fffe9a65400) at ./Include/refcount.h:410
#6  0x0000000000519d87 in Py_XDECREF (op=0x7fffe9a65400) at ./Include/refcount.h:520
#7  0x000000000051bea8 in list_dealloc (self=0x7fffe9a65450) at Objects/listobject.c:567

#8  0x00000000005619b1 in _Py_Dealloc (op=0x7fffe9a65450) at Objects/object.c:3319
#9  0x0000000000519d37 in Py_DECREF (filename=0x8ca48c "./Include/refcount.h", lineno=520, op=0x7fffe9a65450) at ./Include/refcount.h:410
#10 0x0000000000519d87 in Py_XDECREF (op=0x7fffe9a65450) at ./Include/refcount.h:520
#11 0x000000000051bea8 in list_dealloc (self=0x7fffe9a654a0) at Objects/listobject.c:567

#12 0x00000000005619b1 in _Py_Dealloc (op=0x7fffe9a654a0) at Objects/object.c:3319
#13 0x0000000000519d37 in Py_DECREF (filename=0x8ca48c "./Include/refcount.h", lineno=520, op=0x7fffe9a654a0) at ./Include/refcount.h:410
#14 0x0000000000519d87 in Py_XDECREF (op=0x7fffe9a654a0) at ./Include/refcount.h:520
#15 0x000000000051bea8 in list_dealloc (self=0x7fffe9a654f0) at Objects/listobject.c:567

#16 0x00000000005619b1 in _Py_Dealloc (op=0x7fffe9a654f0) at Objects/object.c:3319
#17 0x0000000000519d37 in Py_DECREF (filename=0x8ca48c "./Include/refcount.h", lineno=520, op=0x7fffe9a654f0) at ./Include/refcount.h:410
#18 0x0000000000519d87 in Py_XDECREF (op=0x7fffe9a654f0) at ./Include/refcount.h:520
#19 0x000000000051bea8 in list_dealloc (self=0x7fffe9a65540) at Objects/listobject.c:567

#20 0x00000000005619b1 in _Py_Dealloc (op=0x7fffe9a65540) at Objects/object.c:3319
#21 0x0000000000519d37 in Py_DECREF (filename=0x8ca48c "./Include/refcount.h", lineno=520, op=0x7fffe9a65540) at ./Include/refcount.h:410
#22 0x0000000000519d87 in Py_XDECREF (op=0x7fffe9a65540) at ./Include/refcount.h:520
#23 0x000000000051bea8 in list_dealloc (self=0x7fffe9a65590) at Objects/listobject.c:567
...

[vstinner]

The reproducer comes from test_concurrent_tee_supports_concurrent_consumers() of test_threading: see issue gh-151542.