-
Tony Finch authored
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 (with no barriers), and fits well into a libuv loop. More recent hybrid SMR algorithms do not appear to have enough benefits to justify the extra complexity.
5b246e6c