google-deepmind / google-deepmind/tree
Free-threaded (no-GIL) use-after-free: borrowed dict key from PyDict_Next used across __hash__/__eq__ in assert_same_structure
- Dominant language
- Python
- Stars
- 1k
- Forks
- 73
- PR merge metrics
- No merged PRs in 30d
Description
On a free-threaded build (`3.14t`), `tree.assert_same_structure` can dereference a freed `PyObject*` when the compared structures are dicts that another thread mutates concurrently. It reproduces as SIGSEGV / SIGTRAP; under the GIL it is clean.
### Site
`tree/tree.cc:552` on current `master`:
```c
while (PyDict_Next(o1, &pos, &key, nullptr)) { // key is a borrowed reference
if (PyDict_GetItem(o2, key) == nullptr) { // runs key.__hash__ / __eq__
```
`o1` and `o2` are the two caller-supplied structures. `key` is borrowed from `o1`, and `PyDict_GetItem(o2, key)` calls `key`'s `__hash__` and `__eq__`. If those are Python (e.g. a `str` subclass), the lookup leaves C while holding the borrowed `key`. Another thread mutating `o1` at that moment can drop `key`'s last reference and free it. Two documented hazards stack: `PyDict_Next` is itself unsafe against concurrent mutation, and the key it returns is borrowed.
The same borrowed-`PyDict_GetItem` shape is at `tree.cc:283` (with a comment already noting the borrow); I have not exercised that path.
### Exposure
dm-tree is built with pybind11, which declares the module `Py_MOD_GIL_NOT_USED` by default on a free-threaded build. So on a stock free-threaded interpreter `import tree` leaves the GIL **disabled** - no `PYTHON_GIL=0` override is needed to reach this - while the module has not been made free-threading-safe.
### Measured
`python3.14.0rc1t`, 8 comparer threads calling `assert_same_structure(a, b)` while 3 mutator threads replace keys in `a`; keys are a `str` subclass so `__hash__` is real Python. 4000 rounds, 10 runs per arm:
| arm | result |
|---|---|
| free-threaded | **10/10 crash** (SIGSEGV 4, SIGTRAP 6) |
| control - no mutator thread | clean 10/10 |
| control - mutator touches a decoy dict, not the compared one | clean 10/10 |
| same script, GIL build (3.14) | clean 10/10 |
Both controls matter: without the first, concurrent comparison alone could be blamed; without the second, generic thread pressure could be.
Reproducer (ft_dmtree.py)
```python
"""dm-tree `tree.cc:552` — borrowed key from PyDict_Next used across arbitrary Python.
while (PyDict_Next(o1, &pos, &key, nullptr)) { /* key is borrowed */
if (PyDict_GetItem(o2, key) == nullptr) { /* runs __hash__/__eq__ */
`o1` and `o2` are the two structures the caller passed to
`tree.assert_same_structure`. Under Py_GIL_DISABLED another thread mutating `o1`
can free the borrowed `key` while the lookup in `o2` is running user code.
Two hazards stacked: PyDict_Next itself is documented as unsafe against
concurrent mutation, and the key it hands back is borrowed.
Keys here are a str subclass whose __hash__ is real Python, so the lookup in `o2`
genuinely leaves C.
"""
import gc
import sys
import threading
import tree
N_CMP, N_MUT, ROUNDS, SIZE = 8, 3, 4000, 32
class Key(str):
"""A str subclass: __hash__ goes through Python, so PyDict_GetItem leaves C."""
__slots__ = ()
def __hash__(self):
return str.__hash__(self)
def main():
print(f"py={sys.version.split()[0]}{sys.abiflags} "
f"gil={getattr(sys, '_is_gil_enabled', lambda: True)()}", flush=True)
a = {Key(f"k{i}"): i for i in range(SIZE)}
b = {Key(f"k{i}"): i for i in range(SIZE)}
stop = threading.Event()
barrier = threading.Barrier(N_CMP + N_MUT + 1)
done = [0] * N_CMP
def comparer(t):
barrier.wait()
n = 0
for _ in range(ROUNDS):
try:
tree.assert_same_structure(a, b)
except Exception:
pass
n += 1
done[t] = n
def mutator():
barrier.wait()
i = 0
while not stop.is_set():
k = Key(f"k{i % SIZE}")
a[k] = i # replace: the old Key object loses its last ref
i += 1
cs = [threading.Thread(target=comparer, args=(t,)) for t in range(N_CMP)]
ms = [threading.Thread(target=mutator) for _ in range(N_MUT)]
gc.disable()
for t in cs + ms:
t.start()
barrier.wait()
for t in cs:
t.join()
stop.set()
for t in ms:
t.join()
gc.enable()
print(f"clean: {sum(done)} comparisons", flush=True)
return 0
if __name__ == "__main__":
raise SystemExit(main())
```
The two controls are one-line variants: control A removes the mutator threads; control B points the mutators at a separate decoy dict instead of `a`.
### A possible fix
Matching what CPython added for exactly this: take a strong reference to the key for the duration of the lookup - `PyDict_GetItemRef` / `Py_NewRef(key)` around the `PyDict_GetItem`, or wrap the walk in a critical section on `o1`.
### Not claimed
No severity - whether an application shares a structure across threads while calling `assert_same_structure` is application-specific. No exploitability - the observed faults are consistent with the mechanism and I did not build a primitive.
Contributor guide
Research direction
Start at tree/tree.cc:552 and inspect the related borrowed PyDict_GetItem path at tree.cc:283, then run the supplied ft_dmtree.py reproducer on a free-threaded build. Compare the relevant Python C API reference and concurrency guarantees before choosing the ownership or synchronization approach. Done means the free-threaded stress case remains clean and regression coverage exercises the affected path.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp, python
- Domain
- backend
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 52/100