Skip to content

data race between lock free list reads and heapq #135557

New issue
New issue
Closed
Closed
data race between lock free list reads and heapq#135557
Assignees
kumaraditya303
Labels
extension-modulesC modules in the Modules dirtopic-free-threadingtype-bugAn unexpected behavior, bug, or error
@kumaraditya303

Description

@kumaraditya303
kumaraditya303
opened on Jun 16, 2025 · edited by bedevere-app
Contributor

Reproducer:

import heapq

l = []


def writer():
    while True:
        heapq.heappush(l, 1)
        heapq.heappop(l)

def reader():
    while True:
        try:
            l[0]
        except IndexError:
            pass

def main():
    import threading

    threads = []
    for _ in range(10):
        t1 = threading.Thread(target=writer)
        t2 = threading.Thread(target=reader)
        threads.append(t1)
        threads.append(t2)
        t1.start()
        t2.start()

    for t in threads:
        t.join()

main()

TSAN data race on current main:

==================
WARNING: ThreadSanitizer: data race (pid=32935)
  Write of size 8 at 0x7f90240300f8 by thread T3:
    #0 PyList_SET_ITEM /home/realkumaraditya/cpython/./Include/cpython/listobject.h:47:26 (_heapq.cpython-315t-x86_64-linux-gnu.so+0x43fc) (BuildId: d2d0e185522b78f855f3798fbcc693ee0dba06e3)
    #1 heappop_internal /home/realkumaraditya/cpython/./Modules/_heapqmodule.c:175:5 (_heapq.cpython-315t-x86_64-linux-gnu.so+0x43fc)
    #2 _heapq_heappop_impl /home/realkumaraditya/cpython/./Modules/_heapqmodule.c:197:12 (_heapq.cpython-315t-x86_64-linux-gnu.so+0x2ae7) (BuildId: d2d0e185522b78f855f3798fbcc693ee0dba06e3)
    #3 _heapq_heappop /home/realkumaraditya/cpython/./Modules/clinic/_heapqmodule.c.h:68:20 (_heapq.cpython-315t-x86_64-linux-gnu.so+0x2ae7)
    #4 cfunction_vectorcall_O /home/realkumaraditya/cpython/Objects/methodobject.c:537:24 (python+0x2a2d0a) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #5 _PyObject_VectorcallTstate /home/realkumaraditya/cpython/./Include/internal/pycore_call.h:169:11 (python+0x1f61b3) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #6 PyObject_Vectorcall /home/realkumaraditya/cpython/Objects/call.c:327:12 (python+0x1f61b3)
    #7 _PyEval_EvalFrameDefault /home/realkumaraditya/cpython/Python/generated_cases.c.h:1629:35 (python+0x404042) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #8 _PyEval_EvalFrame /home/realkumaraditya/cpython/./Include/internal/pycore_ceval.h:119:16 (python+0x3ff030) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #9 _PyEval_Vector /home/realkumaraditya/cpython/Python/ceval.c:1975:12 (python+0x3ff030)
    #10 _PyFunction_Vectorcall /home/realkumaraditya/cpython/Objects/call.c (python+0x1f680f) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #11 _PyObject_VectorcallTstate /home/realkumaraditya/cpython/./Include/internal/pycore_call.h:169:11 (python+0x1fb226) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #12 method_vectorcall /home/realkumaraditya/cpython/Objects/classobject.c:72:20 (python+0x1fb226)
    #13 _PyObject_VectorcallTstate /home/realkumaraditya/cpython/./Include/internal/pycore_call.h:169:11 (python+0x457ac1) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #14 context_run /home/realkumaraditya/cpython/Python/context.c:728:29 (python+0x457ac1)
    #15 method_vectorcall_FASTCALL_KEYWORDS /home/realkumaraditya/cpython/Objects/descrobject.c:421:24 (python+0x20f499) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #16 _PyObject_VectorcallTstate /home/realkumaraditya/cpython/./Include/internal/pycore_call.h:169:11 (python+0x1f61b3) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #17 PyObject_Vectorcall /home/realkumaraditya/cpython/Objects/call.c:327:12 (python+0x1f61b3)
    #18 _PyEval_EvalFrameDefault /home/realkumaraditya/cpython/Python/generated_cases.c.h:1629:35 (python+0x404042) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #19 _PyEval_EvalFrame /home/realkumaraditya/cpython/./Include/internal/pycore_ceval.h:119:16 (python+0x3ff030) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #20 _PyEval_Vector /home/realkumaraditya/cpython/Python/ceval.c:1975:12 (python+0x3ff030)
    #21 _PyFunction_Vectorcall /home/realkumaraditya/cpython/Objects/call.c (python+0x1f680f) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #22 _PyObject_VectorcallTstate /home/realkumaraditya/cpython/./Include/internal/pycore_call.h:169:11 (python+0x1fb226) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #23 method_vectorcall /home/realkumaraditya/cpython/Objects/classobject.c:72:20 (python+0x1fb226)
    #24 _PyVectorcall_Call /home/realkumaraditya/cpython/Objects/call.c:273:16 (python+0x1f64a9) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #25 _PyObject_Call /home/realkumaraditya/cpython/Objects/call.c:348:16 (python+0x1f64a9)
    #26 PyObject_Call /home/realkumaraditya/cpython/Objects/call.c:373:12 (python+0x1f6515) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #27 thread_run /home/realkumaraditya/cpython/./Modules/_threadmodule.c:373:21 (python+0x5ad102) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #28 pythread_wrapper /home/realkumaraditya/cpython/Python/thread_pthread.h:232:5 (python+0x5047c7) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)

  Previous atomic read of size 8 at 0x7f90240300f8 by thread T2:
    #0 _Py_atomic_load_ptr /home/realkumaraditya/cpython/./Include/cpython/pyatomic_gcc.h:300:18 (python+0x24bbb8) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #1 _Py_TryXGetRef /home/realkumaraditya/cpython/./Include/internal/pycore_object.h:632:23 (python+0x24bbb8)
    #2 list_get_item_ref /home/realkumaraditya/cpython/Objects/listobject.c:366:22 (python+0x24bbb8)
    #3 _PyList_GetItemRef /home/realkumaraditya/cpython/Objects/listobject.c:417:12 (python+0x24bd1e) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #4 _PyEval_EvalFrameDefault /home/realkumaraditya/cpython/Python/generated_cases.c.h:736:35 (python+0x401216) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #5 _PyEval_EvalFrame /home/realkumaraditya/cpython/./Include/internal/pycore_ceval.h:119:16 (python+0x3ff030) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #6 _PyEval_Vector /home/realkumaraditya/cpython/Python/ceval.c:1975:12 (python+0x3ff030)
    #7 _PyFunction_Vectorcall /home/realkumaraditya/cpython/Objects/call.c (python+0x1f680f) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #8 _PyObject_VectorcallTstate /home/realkumaraditya/cpython/./Include/internal/pycore_call.h:169:11 (python+0x1fb226) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #9 method_vectorcall /home/realkumaraditya/cpython/Objects/classobject.c:72:20 (python+0x1fb226)
    #10 _PyObject_VectorcallTstate /home/realkumaraditya/cpython/./Include/internal/pycore_call.h:169:11 (python+0x457ac1) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #11 context_run /home/realkumaraditya/cpython/Python/context.c:728:29 (python+0x457ac1)
    #12 method_vectorcall_FASTCALL_KEYWORDS /home/realkumaraditya/cpython/Objects/descrobject.c:421:24 (python+0x20f499) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #13 _PyObject_VectorcallTstate /home/realkumaraditya/cpython/./Include/internal/pycore_call.h:169:11 (python+0x1f61b3) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #14 PyObject_Vectorcall /home/realkumaraditya/cpython/Objects/call.c:327:12 (python+0x1f61b3)
    #15 _PyEval_EvalFrameDefault /home/realkumaraditya/cpython/Python/generated_cases.c.h:1629:35 (python+0x404042) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #16 _PyEval_EvalFrame /home/realkumaraditya/cpython/./Include/internal/pycore_ceval.h:119:16 (python+0x3ff030) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #17 _PyEval_Vector /home/realkumaraditya/cpython/Python/ceval.c:1975:12 (python+0x3ff030)
    #18 _PyFunction_Vectorcall /home/realkumaraditya/cpython/Objects/call.c (python+0x1f680f) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #19 _PyObject_VectorcallTstate /home/realkumaraditya/cpython/./Include/internal/pycore_call.h:169:11 (python+0x1fb226) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #20 method_vectorcall /home/realkumaraditya/cpython/Objects/classobject.c:72:20 (python+0x1fb226)
    #21 _PyVectorcall_Call /home/realkumaraditya/cpython/Objects/call.c:273:16 (python+0x1f64a9) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #22 _PyObject_Call /home/realkumaraditya/cpython/Objects/call.c:348:16 (python+0x1f64a9)
    #23 PyObject_Call /home/realkumaraditya/cpython/Objects/call.c:373:12 (python+0x1f6515) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #24 thread_run /home/realkumaraditya/cpython/./Modules/_threadmodule.c:373:21 (python+0x5ad102) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #25 pythread_wrapper /home/realkumaraditya/cpython/Python/thread_pthread.h:232:5 (python+0x5047c7) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)

  Thread T3 'Thread-3 (push)' (tid=32945, running) created by main thread at:
    #0 pthread_create <null> (python+0xe21ef) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #1 do_start_joinable_thread /home/realkumaraditya/cpython/Python/thread_pthread.h:279:14 (python+0x5038a8) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #2 PyThread_start_joinable_thread /home/realkumaraditya/cpython/Python/thread_pthread.h:321:9 (python+0x5036ca) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #3 ThreadHandle_start /home/realkumaraditya/cpython/./Modules/_threadmodule.c:459:9 (python+0x5acc97) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #4 do_start_new_thread /home/realkumaraditya/cpython/./Modules/_threadmodule.c:1869:9 (python+0x5acc97)
    #5 thread_PyThread_start_joinable_thread /home/realkumaraditya/cpython/./Modules/_threadmodule.c:1984:14 (python+0x5aba61) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #6 cfunction_call /home/realkumaraditya/cpython/Objects/methodobject.c:565:18 (python+0x2a34f7) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #7 _PyObject_MakeTpCall /home/realkumaraditya/cpython/Objects/call.c:242:18 (python+0x1f5661) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #8 _PyObject_VectorcallTstate /home/realkumaraditya/cpython/./Include/internal/pycore_call.h:167:16 (python+0x1f6271) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #9 PyObject_Vectorcall /home/realkumaraditya/cpython/Objects/call.c:327:12 (python+0x1f6271)
    #10 _PyEval_EvalFrameDefault /home/realkumaraditya/cpython/Python/generated_cases.c.h:3245:35 (python+0x40a1e0) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #11 _PyEval_EvalFrame /home/realkumaraditya/cpython/./Include/internal/pycore_ceval.h:119:16 (python+0x3feb6f) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #12 _PyEval_Vector /home/realkumaraditya/cpython/Python/ceval.c:1975:12 (python+0x3feb6f)
    #13 PyEval_EvalCode /home/realkumaraditya/cpython/Python/ceval.c:866:21 (python+0x3feb6f)
    #14 run_eval_code_obj /home/realkumaraditya/cpython/Python/pythonrun.c:1365:12 (python+0x4e12dc) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #15 run_mod /home/realkumaraditya/cpython/Python/pythonrun.c:1436:19 (python+0x4e12dc)
    #16 pyrun_file /home/realkumaraditya/cpython/Python/pythonrun.c:1293:15 (python+0x4dc83e) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #17 _PyRun_SimpleFileObject /home/realkumaraditya/cpython/Python/pythonrun.c:521:13 (python+0x4dc83e)
    #18 _PyRun_AnyFileObject /home/realkumaraditya/cpython/Python/pythonrun.c:81:15 (python+0x4dbf98) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #19 pymain_run_file_obj /home/realkumaraditya/cpython/Modules/main.c:410:15 (python+0x52215f) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #20 pymain_run_file /home/realkumaraditya/cpython/Modules/main.c:429:15 (python+0x52215f)
    #21 pymain_run_python /home/realkumaraditya/cpython/Modules/main.c:691:21 (python+0x521488) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #22 Py_RunMain /home/realkumaraditya/cpython/Modules/main.c:772:5 (python+0x521488)
    #23 pymain_main /home/realkumaraditya/cpython/Modules/main.c:802:12 (python+0x5219f8) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #24 Py_BytesMain /home/realkumaraditya/cpython/Modules/main.c:826:12 (python+0x521a7b) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #25 main /home/realkumaraditya/cpython/./Programs/python.c:15:12 (python+0x1607fb) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)

  Thread T2 'Thread-2 (pop)' (tid=32944, running) created by main thread at:
    #0 pthread_create <null> (python+0xe21ef) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #1 do_start_joinable_thread /home/realkumaraditya/cpython/Python/thread_pthread.h:279:14 (python+0x5038a8) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #2 PyThread_start_joinable_thread /home/realkumaraditya/cpython/Python/thread_pthread.h:321:9 (python+0x5036ca) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #3 ThreadHandle_start /home/realkumaraditya/cpython/./Modules/_threadmodule.c:459:9 (python+0x5acc97) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #4 do_start_new_thread /home/realkumaraditya/cpython/./Modules/_threadmodule.c:1869:9 (python+0x5acc97)
    #5 thread_PyThread_start_joinable_thread /home/realkumaraditya/cpython/./Modules/_threadmodule.c:1984:14 (python+0x5aba61) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #6 cfunction_call /home/realkumaraditya/cpython/Objects/methodobject.c:565:18 (python+0x2a34f7) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #7 _PyObject_MakeTpCall /home/realkumaraditya/cpython/Objects/call.c:242:18 (python+0x1f5661) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #8 _PyObject_VectorcallTstate /home/realkumaraditya/cpython/./Include/internal/pycore_call.h:167:16 (python+0x1f6271) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #9 PyObject_Vectorcall /home/realkumaraditya/cpython/Objects/call.c:327:12 (python+0x1f6271)
    #10 _PyEval_EvalFrameDefault /home/realkumaraditya/cpython/Python/generated_cases.c.h:3245:35 (python+0x40a1e0) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #11 _PyEval_EvalFrame /home/realkumaraditya/cpython/./Include/internal/pycore_ceval.h:119:16 (python+0x3feb6f) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #12 _PyEval_Vector /home/realkumaraditya/cpython/Python/ceval.c:1975:12 (python+0x3feb6f)
    #13 PyEval_EvalCode /home/realkumaraditya/cpython/Python/ceval.c:866:21 (python+0x3feb6f)
    #14 run_eval_code_obj /home/realkumaraditya/cpython/Python/pythonrun.c:1365:12 (python+0x4e12dc) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #15 run_mod /home/realkumaraditya/cpython/Python/pythonrun.c:1436:19 (python+0x4e12dc)
    #16 pyrun_file /home/realkumaraditya/cpython/Python/pythonrun.c:1293:15 (python+0x4dc83e) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #17 _PyRun_SimpleFileObject /home/realkumaraditya/cpython/Python/pythonrun.c:521:13 (python+0x4dc83e)
    #18 _PyRun_AnyFileObject /home/realkumaraditya/cpython/Python/pythonrun.c:81:15 (python+0x4dbf98) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #19 pymain_run_file_obj /home/realkumaraditya/cpython/Modules/main.c:410:15 (python+0x52215f) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #20 pymain_run_file /home/realkumaraditya/cpython/Modules/main.c:429:15 (python+0x52215f)
    #21 pymain_run_python /home/realkumaraditya/cpython/Modules/main.c:691:21 (python+0x521488) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #22 Py_RunMain /home/realkumaraditya/cpython/Modules/main.c:772:5 (python+0x521488)
    #23 pymain_main /home/realkumaraditya/cpython/Modules/main.c:802:12 (python+0x5219f8) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #24 Py_BytesMain /home/realkumaraditya/cpython/Modules/main.c:826:12 (python+0x521a7b) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)
    #25 main /home/realkumaraditya/cpython/./Programs/python.c:15:12 (python+0x1607fb) (BuildId: 957e91b4c4b85547a8053d7d39b3c2228cdefcde)

SUMMARY: ThreadSanitizer: data race /home/realkumaraditya/cpython/./Include/cpython/listobject.h:47:26 in PyList_SET_ITEM
==================

In #135036 the heapq module was made thread safe but it still uses non atomic writes so it races with lock free reads in list.

Linked PRs

Activity

kumaraditya303
added
type-bugAn unexpected behavior, bug, or error
topic-free-threading
on Jun 16, 2025
bedevere-app
mentioned this on Jun 17, 2025
kumaraditya303

kumaraditya303 commented on Jun 17, 2025

@kumaraditya303
kumaraditya303
on Jun 17, 2025
ContributorAuthor

I think there are two ways to fix it:

  • use atomic writes which is the simpler approach but will have lesser performance because of atomics
  • set the size of list to 0 before mutating it like its done for list.sort so that lock free reads will get IndexError until the the operation in complete, presumably this will have better perf as no need for atomic writes. This seems better but there is a change in behavior so shouldn't be backported.

cc @colesbury

colesbury

colesbury commented on Jun 17, 2025

@colesbury
colesbury
on Jun 17, 2025
Contributor

Atomic writes seems like the best approach to me. Relaxed atomics should be fine and won't have any performance difference (compiles to plain stores), but even the overhead of _Py_atomic_store_ssize (seq-cst) is unlikely to be noticeable in this context.

kumaraditya303
self-assigned this
on Jun 17, 2025
picnixz
added
interpreter-core(Objects, Python, Grammar, and Parser dirs)
extension-modulesC modules in the Modules dir
and removed
interpreter-core(Objects, Python, Grammar, and Parser dirs)
on Jun 19, 2025
kumaraditya303
added a commit that references this issue on Jun 21, 2025

gh-135557: use atomic stores in `heapq` operations in free-threading (#…

13cac83
miss-islington
added a commit that references this issue on Jun 21, 2025

pythongh-135557: use atomic stores in `heapq` operations in free-thre…

753cec2
bedevere-app
mentioned this on Jun 21, 2025
kumaraditya303
closed this as completedon Jun 21, 2025
kumaraditya303
added a commit that references this issue on Jun 21, 2025

[3.14] gh-135557: use atomic stores in `heapq` operations in free-thr…

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

Metadata

Metadata

Assignees

Labels

extension-modulesC modules in the Modules dirtopic-free-threadingtype-bugAn unexpected behavior, bug, or error

Projects

No projects

Milestone

No milestone

Relationships

None yet

    Development

    No branches or pull requests

      Participants

      @colesbury@picnixz@kumaraditya303

      Issue actions
        data race between lock free list reads and heapq · Issue #135557 · python/cpython