Skip to content

QSBR: safe memory reclamation for lock-free data structures

Tony Finch requested to merge fanf-qsbr into main

This "quiescent state based reclamation" module provides support for the qp-trie module in dns/qp. It is a replacement for liburcu, written without reference to the urcu source code, and in fact it works in a significantly different way.

A few specifics of BIND make this variant of QSBR somewhat simpler:

  • We can require that wait-free access to a qp-trie only happens in an isc_loop callback. The loop provides a natural quiescent state, after the callbacks are done, when no qp-trie access occurs.

  • We can dispense with any API like rcu_synchronize(). In practice, it takes far too long to wait for a grace period to elapse for each write to a data structure.

  • We use the idea of "phases" (aka epochs or eras) from EBR to reduce the amount of bookkeeping needed to track memory that is no longer needed, knowing that the qp-trie does most of that work already.

I considered hazard pointers for safe memory reclamation. They have more read-side overhead (updating the hazard pointers) and it wasn't clear to me how to nicely schedule the cleanup work. Another alternative, epoch-based reclamation, is designed for fine-grained lock-free updates, so it needs some rethinking to work well with the heavily read-biased design of the qp-trie. QSBR has the fastest read side of the basic SMR algorithms, and fits well into a libuv loop.

Merge request reports