A full collection while a cache holds its lock freezes the process

[Malkiz223]

Cache operations take an internal lock, and __traverse__ takes that same lock. So whenever Python code runs while the lock is held, a full garbage collection starting in that window deadlocks. The frozen thread keeps the GIL, so the whole process stops, not just that thread, and Ctrl-C does not help: the process has to be killed.

#67 was one case of this, the setdefault_with factory, and #68 fixed it by calling the factory with the lock released. The reproductions below demonstrate two more mechanisms: dropping a value, and comparing keys.

Each script below runs as it is. Everything is measured on 6.2.6 and Python 3.13.

1. A value's finalizer, minimal

import gc

import cachebox


class Boom:
    def __del__(self):
        gc.collect()  # only makes the collection certain; any allocation can start one


cache = cachebox.LRUCache(1)
cache['a'] = Boom()

print('cachebox', cachebox.__version__)
print('evicting "a", which drops Boom and runs its finalizer ...', flush=True)

cache['b'] = 'value'

print('returned:', cache['b'])

It prints the second line and never comes back.

2. The same thing without asking for a collection

The finalizer here is an ordinary one, and the collections happen in another thread, the way a long running process does them on its own.

import gc
import threading
import time

import cachebox


class Value:
    def __init__(self, number):
        self.number = number

    def __del__(self):
        {'value': self.number, 'message': 'dropped'}  # allocates, like asyncio.Future.__del__


collections_done = 0
stop = False


def collect_forever():
    global collections_done

    while not stop:
        gc.collect()
        collections_done += 1
        time.sleep(0.01)


cache = cachebox.LRUCache(1000)
threading.Thread(target=collect_forever, daemon=True).start()

print('cachebox', cachebox.__version__, flush=True)
print('inserting; every insert past the first 1000 evicts a value ...', flush=True)

deadline = time.time() + 20
inserted = 0

while time.time() < deadline:
    inserted += 1
    cache[inserted] = Value(inserted)

stop = True
print(f'finished: {inserted} inserts, {collections_done} collections', flush=True)

This freezes, usually within a second. With cachetools.LRUCache in place of cachebox.LRUCache the same script runs to the end: about 13 million inserts and 664 collections.

3. A value from the standard library, with no finalizer written anywhere

import asyncio
import gc
import threading
import time

import cachebox

loop = asyncio.new_event_loop()
collections_done = 0
stop = False


def collect_forever():
    global collections_done

    while not stop:
        gc.collect()
        collections_done += 1
        time.sleep(0.01)


cache = cachebox.LRUCache(1000)
threading.Thread(target=collect_forever, daemon=True).start()

print('cachebox', cachebox.__version__, flush=True)
print('inserting futures whose exception nobody retrieves ...', flush=True)

deadline = time.time() + 20
inserted = 0

while time.time() < deadline:
    inserted += 1
    future = loop.create_future()
    future.set_exception(ValueError('nobody retrieves this'))
    cache[inserted] = future

stop = True
print(f'finished: {inserted} inserts, {collections_done} collections', flush=True)

A coroutine nobody awaits does the same thing, for the same reason: it warns when it is dropped.

values	cachebox 6.2.6	cachetools 7.1.7
a class with an ordinary __del__	freezes	~13 million inserts, 664 collections
a future carrying an unretrieved exception	freezes	~0.7 million inserts, 1514 collections
a coroutine never awaited	freezes	~7.7 million inserts, 647 collections
a plain object with no finalizer	~59 million inserts, fine	fine

Eviction is only the shortest way to show it. A value is also dropped with the lock held by replacement via update(), by drain(), by clear(), by the expiry sweep of a TTLCache, and on the error path of an insert the cache rejects. (pop, popitem and __delitem__ are fine: they hand the removed value out and it is dropped after the lock is released.)

4. A key whose __eq__ runs during a probe

__eq__ is called while the table is being walked, so the same window opens there. With more than one thread the Python code under the lock does not even need to allocate: the lookup thread loses the GIL inside __eq__, the collecting thread blocks on the cache lock inside __traverse__ while still holding the GIL, and the two wait for each other forever.

import gc
import threading
import time

import cachebox


class Key:
    def __init__(self, name):
        self.name = name

    def __hash__(self):
        return 42  # same hash for every key, so lookups have to call __eq__

    def __eq__(self, other):
        # the sleep only widens the window for the demo; the window itself
        # opens at every bytecode boundary of any Python __eq__
        time.sleep(0.2)
        return self.name == other.name


cache = cachebox.Cache(0)
cache[Key('a')] = 1


def full_gc_from_another_thread():
    time.sleep(0.05)
    print('other thread: starting a full collection ...', flush=True)
    gc.collect()
    print('other thread: collection finished', flush=True)


threading.Thread(target=full_gc_from_another_thread, daemon=True).start()

print('cachebox', cachebox.__version__, flush=True)
print('main thread: looking up a colliding key ...', flush=True)
print('got:', cache.get(Key('b')), flush=True)

__hash__ is fine, I checked: the hash is computed before the lock is taken. getsizeof is fine on the insert path for the same reason, but on the setdefault and update paths it runs with the lock held, and a collection inside it freezes the same way.

The fix

__traverse__ is the only place that has to wait for a busy lock: if it stops waiting - try the lock, and when it is busy, report nothing on this pass - every deadlock above is gone. Skipping a pass is safe for the collector: the cache and its contents are treated as reachable this time, and the next pass sees them again. And a busy lock means some thread is in the middle of a cache operation, so it holds a reference to the cache anyway, and nothing collectable is being missed.

Two adjacent sharp edges need no collector at all and are closed alongside. A __del__ that reaches into the same cache it is stored in deadlocked because values used to be dropped while the lock is held: removal sites now park removed values, and they are dropped right after the lock is released - the way #68 already runs the factory without the lock. And update(), setdefault() and setdefault_with() used to run Python - the iterable, getsizeof - with the lock held: they now do that work first, without the lock.

A few more spots I found but do not fix here. __eq__ still runs under the lock - a key's during a probe, values' when comparing two caches - and so does the repr() of keys and values while the cache itself is being formatted. The __traverse__ piece already makes them safe from the collector, so on their own they hang nobody. Two deadlocks do remain reproducible: an __eq__ that reaches into the same cache it belongs to, and two threads comparing two caches in opposite orders. Both take deliberately written code; I leave them as a known limit.