gh-116738: Make _heapq module thread-safe #135036
Conversation
|
All commit authors signed the Contributor License Agreement. |
There was a problem hiding this comment.
There is a lot of duplication in tests because of min/max heaps, why not organize with subtests?
Also for testing the heap, it is probably best to reuse the existing methods from test_heapq
cpython/Lib/test/test_heapq.py
Lines 106 to 116 in 0558275
|
The Modules/_heapqmodule.c change looks good to me. I haven't looked through the tests yet. I don't think should change the implementation to avoid borrowed references: I'd rather keep the change small and limited to the thread safety fix rather than try to "clean" things up, and I'm not really convinced that avoiding borrowed references here would make things better. @yoney - would you please add add a NEWS entry via blurb. You can use |
Ok, but we should definitely do this in a follow-up (possibly only for 3.15). There are definitely some things here that aren't safe. For example: lastelt = PyList_GET_ITEM(heap, n-1) ;
Py_INCREF(lastelt);
if (PyList_SetSlice(heap, n-1, n, NULL)) {
Py_DECREF(lastelt);
return NULL;
}
n--;
if (!n)
return lastelt;
returnitem = PyList_GET_ITEM(heap, 0);A finalizer could either release the critical section or explicitly clear the list, which could cause that There's also some incredibly horrible things going on, like this: returnitem = PyList_GET_ITEM(heap, 0);
PyList_SET_ITEM(heap, 0, lastelt);
|
@ZeroIntensity I agree that there are things we should follow up on. I initially tried to address some of them as part of the free-threading change, but it introduces complexity to the review and makes the free-threading change harder to review, so I decided to follow up on those issues separately. |
Misc/NEWS.d/next/Core_and_Builtins/2025-06-02-13-57-40.gh-issue-116738.ycJsL8.rst
Outdated
Show resolved
Hide resolved
@StanFromIreland Thank you so much for your review! I've already refactored the code and moved some repeated parts into separate functions while addressing the other comments. I'm not sure if subtests will provide more code reuse here. What do you think? |
Modules/_heapqmodule.c
Outdated
| if (PyList_Append(heap, item)) | ||
| // In a free-threaded build, the heap is locked at this point. | ||
| // Therefore, calling _PyList_AppendTakeRef() is safe and no overhead. | ||
| if (_PyList_AppendTakeRef((PyListObject *)heap, Py_XNewRef(item))) |
There was a problem hiding this comment.
Wait, why is this now XNewRef? item can never be NULL.
There was a problem hiding this comment.
I wasn't sure about "item can never be NULL" and in the previous version, PyList_Append() had a NULL check. That's why I thought this would be safe. However, _PyList_AppendTakeRef() expects a non-NULL value for item so it doesn't really make it safer.
Can I assume that "item can never be NULL" because _heapq_heappush_impl() is called from clinic-generated code?
There was a problem hiding this comment.
I think it might be possible for item to be NULL if you vectorcall this from a C extension? If we want to mirror the previous implementation we should add a check that item is not NULL:
if (newitem == NULL) {
PyErr_BadInternalCall();
return NULL
}There was a problem hiding this comment.
I think it might be possible for item to be NULL if you vectorcall this from a C extension?
Well, that would definitely be the user's fault--you can't pass NULL to a vectorcall arg. I think adding the NULL check here is additional work that isn't necessary. We don't do this for anything else that uses AC, right?
There was a problem hiding this comment.
I think adding the NULL check here is additional work that isn't necessary. We don't do this for anything else that uses AC, right?
The previous implementation that used PyList_Append performed the NULL check (in PyList_Append). If we want to match the existing behavior we should include the NULL check here as well. I would err on the side of being conservative and include it unless we are guaranteed to never see a NULL item (for example if something higher up in the call stack already checks for it).
There was a problem hiding this comment.
@mpage @ZeroIntensity
Thank you!
I've added the NULL check, which aligns better with the previous version. However, if we decide that we can assume the value cannot be NULL, I can remove it.
Modules/_heapqmodule.c
Outdated
| if (PyList_Append(heap, item)) | ||
| // In a free-threaded build, the heap is locked at this point. | ||
| // Therefore, calling _PyList_AppendTakeRef() is safe and no overhead. | ||
| if (_PyList_AppendTakeRef((PyListObject *)heap, Py_XNewRef(item))) |
There was a problem hiding this comment.
I think it might be possible for item to be NULL if you vectorcall this from a C extension? If we want to mirror the previous implementation we should add a check that item is not NULL:
if (newitem == NULL) {
PyErr_BadInternalCall();
return NULL
}
This uses critical sections to make heapq methods that update the heap thread-safe when the GIL is disabled. This is accomplished by using the @critical_section clinic directive.
cc: @mpage @colesbury