03/08/2020

Brief announcement: Hazard pointer protection of structures with immutable links

Maged M. Michael

Keywords: hazard pointer, concurrent algorithm, safe reclamation

Abstract: The hazard pointer method [4] for safe reclamation is capable of protecting individual dynamic objects, including individual nodes of linked structures. However, on its own, it does not protect the descendants of protected nodes for unconditional traversal.We present a new algorithm that extends the hazard pointer algorithm to support unconditional traversal though immutable links of acyclic structures. It has an important added advantage of allowing the reclamation of nodes at any depth with their ancestors in the same pass over hazard pointers.Achieving these advantages does not incur any extra computing cost in protection operations, which are the common case. A counter is added to each object for holding the number of inbound immutable links. Such counters are updated when setting and clearing immutable links, which can happen at most once per link in the lifetime of an object. The algorithm is implemented and used in the Facebook Folly open-source C++ library [1].

 0
 0
 0
 0
This is an embedded video. Talk and the respective paper are published at PODC 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd

Similar Papers