aio-libs / multidict / 34678490892

87%

push

github

Make __contains__ lock-free with reader-counted table retirement (#1441)

<!-- Thank you for your contribution! -->

## What do these changes do?

First slice of the lock-free read path deferred out of #1438: instead
of a critical section, `__contains__` now protects itself with a
reader-counted table retirement scheme, and the hash table a lock-free
reader might still be walking is kept alive until it's safe to free.

Two counters, gated entirely behind `Py_GIL_DISABLED`:

- `MultiDictObject.active_readers`: a coarse "some lock-free reader is
  in flight on this object" gate, bumped before a reader ever
  dereferences a keys table and dropped once it's done
  (`_md_reader_enter()`/`_md_reader_exit()`).
- `htkeys_t.readers`: a per-table count, advisory only, used purely as
  a defensive assertion once the coarse gate is already known closed.
  It is not itself load-bearing for safety: an embedded refcount can't
  safely announce "about to use this" without a bootstrap hazard,
  since the increment itself would dereference memory that might
  already be freed by the time it runs.

`_md_retire()`/`_md_drain_retired()`: a resize/shrink/clear no longer
frees the outgoing table immediately, only once `active_readers` reads
0 at a point synchronized (`seq_cst` on both the `md->keys` swap and
the `active_readers` ops -- anything weaker leaves a real,
architecture-dependent race, the same shape as Dekker's algorithm). A
table that can't be freed yet moves to a per-object retired list and
is freed opportunistically the next time the object resizes.

`_md_shrink()` gets a second implementation under `Py_GIL_DISABLED`:
the existing one compacts the currently-published table in place,
which races a lock-free reader walking the very memory being
rewritten. The free-threaded version reuses `_md_resize()` at the
current size instead (build a new table, swap, retire the old one),
which already has the right shape; the GIL build keeps the original
in-place version unc... (continued)

642 of 1284 branches covered (50.0%)

Branch coverage included in aggregate %.

75 of 75 new or added lines in 1 file covered. (100.0%)

4505 of 4731 relevant lines covered (95.22%)

1.9 hits per line