Repository navigation
a == b and a.update(b) deadlock when another thread does the same with the arguments swapped #118
Description
a == b on one thread and b == a on another can deadlock, and so can a.update(b) with b.update(a). It happens on both the GIL and the free-threaded builds (6.2.9, Python 3.13 and 3.14t, 3 of 3 runs each):
import sys
import threading
import cachebox
sys.setswitchinterval(1e-6)
class Key:
def __init__(self, v):
self.v = v
def __hash__(self):
return self.v
def __eq__(self, other):
return self.v == other.v
a, b = cachebox.LRUCache(0), cachebox.LRUCache(0)
for i in range(1000):
a[Key(i)] = i
b[Key(i)] = i
def compare(x, y):
for _ in range(1000):
x == y # x.update(y) hangs the same way
t1 = threading.Thread(target=compare, args=(a, b))
t2 = threading.Thread(target=compare, args=(b, a))
t1.start()
t2.start()
t1.join()
t2.join()
print("ok")With one thread it finishes in under 0.1 s; with two it never prints ok. On 3.14t it also hangs with plain int keys. On the GIL build it needs keys whose __hash__/__eq__ are Python code, so the GIL can switch while a lock is held.
The two locks are taken in argument order:
__eq__/__ne__lockself, thenother(e.g.src/pyclasses/lrucache.rs,policy_py_attachedtwice).update(other_cache)holdsself's lock for the wholeWrapped::extend, and iteratingother.items()takesother's lock on every step.
So thread 1 holds a and waits for b while thread 2 holds b and waits for a.
Possible fixes: lock the two caches in a fixed order (e.g. by address) in __eq__/__ne__, and in update either copy the other cache's items before taking self's lock or lock both in the same fixed order. Which would you prefer? I can send a PR.
Activity
awolverp commentedon Oct 29, 2026
Thanks again
Locking two caches in a fixed order is the better solution
greenclaw commentedon Oct 29, 2026
Thanks! The fixed order for
__eq__/__ne__is in #122.For
updatea fixed order doesn't work:a.update(b)keepsa's lock while it iteratesb.items(), and every step of that iterator takesb's lock, so locking both up front would block onba second time. The root cause there is thatupdateruns the caller's iteration (and__hash__,getsizeof) while holding the lock, which also hangs on a single thread:insertalready builds the handle (hash,getsizeof) before taking the lock.updatecould do the same for its whole input: collect the handles first, then take the lock once and insert them. That fixes both the two-thread case and this one, at the cost of a temporary list of the new entries. Would that be OK as a separate PR?fix: lock two caches in address order in __eq__ and __ne__ (#118)
awolverp commentedon Oct 29, 2026
Yes I'd appreciate that. You're right. Of course, when the input is a list, set, or tuple, there's no need for a temporary list, but for the others, it is needed.
greenclaw commentedon Oct 29, 2026
fix is open as separate pr
fix: build the handles for update() before taking the cache lock (#118)