• Tony Finch's avatar
    QSBR: safe memory reclamation for lock-free data structures · 5b246e6c
    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
    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.