GeezerVison is showing github.com — `list.remove` is not atomic for non trivial `__eq__` comparisons · Issue #148259 · python/cpython
list.remove is not atomic for non trivial __eq__ comparisons #148259
Labels interpreter-core(Objects, Python, Grammar, and Parser dirs)(Objects, Python, Grammar, and Parser dirs)topic-free-threadingtriagedThe issue has been accepted as valid by a triager.The issue has been accepted as valid by a triager.type-bugAn unexpected behavior, bug, or errorAn unexpected behavior, bug, or error DescriptionBug report
Bug
I found a race condition on the free-threaded build at 72eca2af59043c78647b0e6be3777a947ea9ef0f happening in list.remove.
The long story short is if whatever PyObject_RichCompareBool does releases the GIL, the critical section no longer protects the list's state from other threads, which may then mutate the list and result in the wrong item being removed later.
This is the current code for list.remove with comments around the problematic logic.
static PyObject *
list_remove_impl(PyListObject *self, PyObject *value)
{
Py_ssize_t i;
for (i = 0; i < Py_SIZE(self); i++) {
// read the contents under lock
PyObject *obj = self->ob_item[i];
Py_INCREF(obj);
// this may release the GIL, suspending the critical section
int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
Py_DECREF(obj);
// it is possible that obj (which we want to remove) isn't at
// position i anymore as other threads may have mutated
// the list...
if (cmp > 0) {
// ... but we still remove it!
if (list_ass_slice_lock_held(self, i, i+1, NULL) == 0)
Py_RETURN_NONE;
return NULL;
}
}
...
}I'm not sure whether a crash can occur from that race condition (e.g. i is the position of the last element in the list and another thread pops the last element), but regardless I think there's a correctness issue with that race condition.
It's a bit hard to come up with a reproducer due to the race condition happening under pretty specific circumstances but I can try to make (or generate) one if needed.
Possible fixes
The simplest thing I can think of is re-comparing ob_item[i] with obj after PyObject_RichCompareBool has returned to make sure the state of the list, at least as far as this specific item's position is concerned, hasn't changed, and raising a RuntimeError if not.
Alternatively, I looked at other containers and it seems like deque has a state field which is incremented every time a mutating operation is done on it; if the state value changes in an unexpected manner during mutations, it raises a RuntimeError (I don't think list has anything like that currently).
I already have a branch in my fork that implements the former "fix", but I'm also open to working on the latter if there's interest in it.
CPython versions tested on:
CPython main branch
Operating systems tested on:
macOS
Linked PRs
ActivityShrey-N commented on Apr 10, 2026 Hiya I have confirmed this race condition in the free threaded build. Your draft fix correctly identifies the need for re verification but introduces a reference leak for every element that doesn't match the search value.
If you want I can open a PR shortly with a fix that handles the reference counting correctly across all paths and raises a RuntimeError if a mutation is detected KowalskiThomas commented on Apr 10, 2026 ContributorAuthor More actions Thanks for looking into it! I'll have a look at the leak, thanks for reporting. Reacted by Shrey Naithani Shrey-N commented on Apr 10, 2026 No problem! If you're able to open your fork as a draft PR, I would be happy to jump in and help you refine the implementation and fix those leaks :) colesbury commented on Apr 10, 2026 Thank you for the bug report. This is longstanding behavior of list.remove -- it's not specific to free threading. The PyObject_RichCompareBool() can release the GIL (for GIL-enabled Python) or the list's lock (in free threading). Either way, it's the same effect.
@KowalskiThomas - please open a PR with the change from your branch. I'm generally hesitant to change longstanding behavior like this because it risks introducing regressions that are more troublesome than the original limitations, but this might be narrowly scoped enough. Reacted by Maurycy Pawłowski-Wieroński changed the title [-]Race condition in `list.remove` under free-threading[/-] [+]`list.remove` is not atomic for non trivial `__eq__` comparisons[/+] on Apr 10, 2026KowalskiThomas commented on Apr 11, 2026 ContributorAuthor More actions Thanks, I'll open the PR after I get a chance to look into the leaked reference thingy (should be tomorrow!)
I'm generally hesitant to change longstanding behavior like this because it risks introducing regressions that are more troublesome than the original limitations
Just for my own interest, do you have examples? My understanding is that here, we either have the exception raised when the list is mutated while we iterate through it, or we have nothing at all happening but we end up with an incorrect result (silently).
As far as I can tell, as a user I'd definitely prefer the exception (which is clear and actionable) over the very confusing bug -- am I missing something or is that case not a good example maybe?
Thank you! KowalskiThomas commented on Apr 12, 2026 ContributorAuthor More actions @Shrey-N I checked multiple times, but I'm not seeing the reference leak you mentioned 🤔 On top of that, as far as I can tell, my changes have the same semantics memory-wise/refcount-wise than existing branches right after my added code, and I'd assume they don't have reference leaks. Could you confirm what the leak is? KowalskiThomas commented on Apr 12, 2026 ContributorAuthor More actions I opened issue #148442 which is a similar race condition -- posting about it here because I'm curious whether this would fall under the "might cause other problems" umbrella or not. colesbury commented on Apr 13, 2026
Just for my own interest, do you have examples? My understanding is that here, we either have the exception raised when the list is mutated while we iterate through it, or we have nothing at all happening but we end up with an incorrect result (silently).
As far as I can tell, as a user I'd definitely prefer the exception (which is clear and actionable) over the very confusing bug -- am I missing something or is that case not a good example maybe?
For example, I think adding a mutation counter like deque's state field wouldn't be appropriate here because it would risk breaking existing code that happens to work. One thread calling list.remove() and another calling list.append() isn't subject to this problem, but would trigger modification errors with a mutation counter.
The backwards compatibility concerns here typically trump "better" APIs or concerns about confusing bugs. KowalskiThomas commented on Apr 13, 2026 ContributorAuthor More actions Thanks a lot for the example, that makes a lot of sense to me 🙇 serhiy-storchaka commented on Apr 15, 2026 Lets look at precedence in set.remove, set.discard, dict.__delitem__, dict.pop. I wrote test for dict and set:
- if the key/element was concurrently deleted, you get a KeyError
- if the key/element was concurrently replaced with an equal key/element, that new key/element will be deleted
- if the key/element was concurrently replaced with a non-equal key/element (but with the same hash), you get a KeyError and that new key/element will remain the dict/set
It looks like if the found key/element was removed, the lookup starts again.
If we are going to change the current list behavior, it should be made similar to dict and set, i.e. restart the search if the found item was removed during comparison. Although I am not sure that we should change it.
The difference between the list and hash tables is that the order of a hash table after deletion or insertion is not predicable. You can see some pattern for small integer keys, but it will fail for large integers or for non-integer keys, or just in the next Python release. KowalskiThomas commented on Apr 17, 2026 ContributorAuthor More actions Thanks for looking into this and for the pointers! Definitely agree that behaviours should converge where possible across standard containers. The latest comments on the PR (#148440) go in that direction as well, suggesting this might be worth formalising as a PEP (which makes sense to me).
For completeness' sake, I initially thought the RuntimeError might be the right thing to do because deque (which is more akin to a list than list is to dict/set):
|
if (start_state != deque->state) { |
|
PyErr_SetString(PyExc_IndexError, |
|
"deque mutated during iteration"); |
|
return NULL; |
|
} |
But yeah, open to any options of course. As I pointed out in my PR comment, my point with this issue/PR is mostly to eliminate a possible behaviour that would be pretty confusing from a user's standpoint; I really don't have a strong opinion on how it should be removed (retrying, failing explicitly, or something else).
MetadataMetadatainterpreter-core(Objects, Python, Grammar, and Parser dirs)(Objects, Python, Grammar, and Parser dirs)topic-free-threadingtriagedThe issue has been accepted as valid by a triager.The issue has been accepted as valid by a triager.type-bugAn unexpected behavior, bug, or errorAn unexpected behavior, bug, or error DevelopmentNo branches or pull requestsIssue actions
|