Skip to content

data race between lock free list reads and heapq #135557

New issue
New issue
Open
Open
data race between lock free list reads and heapq#135557
Labels
topic-free-threadingtype-bugAn unexpected behavior, bug, or error
@kumaraditya303

Description

@kumaraditya303
kumaraditya303
opened on Jun 16, 2025

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    topic-free-threadingtype-bugAn unexpected behavior, bug, or error

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions