Tuesday, May 2, 2017

Hazard Eras - Non-Blocking Memory Reclamation

We are proud to present Hazard Eras, a new memory reclamation technique that is lock-free/wait-free. Hazard Eras uses the same API as Hazard Pointers but can be up to 5x faster.
A brief announcement will appear in SPAA 2017:
https://spaa.acm.org/2017/program.html

The full paper can be obtained here:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/papers/hazarderas-2017.pdf

Hazard Eras uses just atomics and the Memory Model, which means it is easily portable across a multitude of architectures. It's kind of an hybrid between epoch-based and pointer-based memory reclamation, but unlike previous approaches, Hazard Eras is non-blocking, i.e. lock-free, and in some cases even wait-free (just like Hazard Pointers it depends on how it's used).

2 comments:

  1. I see your implementation uses tid as index. Here are some practical questions.
    How do you deal with the situation where number of threads
    is dynamic?
    How do you map thread ids to sized-array index without collisions?

    ReplyDelete
    Replies
    1. Hi Xinjing,

      We wanted to show the simplest possible implementation so we went with tid.

      It is relatively easy to change it to a variable number of threads, just use the same technique that Hazard Pointers uses where instead of an array with one entry per thread, there is a linked list with one node per thread. Each node has an "active" flag that the reader threads use to register themselves with a CAS. The address of the node can then be kept in a control block structure (like HP does it) or a thread-local variable.
      Registration with this mechanism is wait-free bounded because the number of threads is bounded, thus implying that the insertion of a new node can fail at most a bounded number of times.
      See Fig. 4 of the Hazard Pointers paper http://researchweb.watson.ibm.com/people/m/michael/ieeetpds-2004.pdf
      or the folly implementation by Maged Michael himself:
      https://github.com/facebook/folly/blob/master/folly/experimental/hazptr/hazptr-impl.h#L219

      Btw, if it was me, I would use an array of size MAX_THREADS (assuming some bound is known for the maximum number of simultaneous threads in the application), where each entry in the array has MAX_ERAS hazard era entries (64 bit atomic integers) and one entry for the "active" (atomic boolean) which is used by the readers to CAS to make the reservation. When the CAS succeeds, the index of the reserved entry in the array can be kept on a thread-local variable.
      By having an array instead of a linked list you get better scan speed for the reclaimer threads, at the cost of using more memory... memory is cheap, right? ;)

      Delete