Skip to content

data race between lock free list reads and heapq #135557

Description

@kumaraditya303

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

  1. kumaraditya303 commented on Jun 17, 2025

    @kumaraditya303
    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

  2. colesbury commented on Jun 17, 2025

    @colesbury
    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.

  3. added
    interpreter-core(Objects, Python, Grammar, and Parser dirs)
    and removed
    interpreter-core(Objects, Python, Grammar, and Parser dirs)
    on Jun 19, 2025
  4. added a commit that references this issue on Jun 21, 2025
  5. added a commit that references this issue on Jun 21, 2025
  6. added a commit that references this issue on Jun 21, 2025
  7. added a commit that references this issue on Jul 12, 2025
  8. added a commit that references this issue on Aug 4, 2025
  9. added a commit that references this issue on Aug 19, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions