33 Concurrency support library [thread]

33.11 Safe reclamation [saferecl]

33.11.3 Hazard pointers [saferecl.hp]

33.11.3.1 General [saferecl.hp.general]

1
#
A hazard pointer is a single-writer multi-reader pointer that can be owned by at most one thread at any time.
Only the owner of the hazard pointer can set its value, while any number of threads may read its value.
The owner thread sets the value of a hazard pointer to point to an object in order to indicate to concurrent threads—which may delete such an object—that the object is not yet safe to delete.
2
#
A class type T is hazard-protectable if it has exactly one base class of type hazard_pointer_obj_base<T, D> for some D, that base is public and non-virtual, and it has no base classes of type hazard_pointer_obj_base<T2, D2> for any other combination T2, D2.
An object is hazard-protectable if it is of hazard-protectable type.
3
#
The time span between creation and destruction of a hazard pointer h is partitioned into a series of protection epochs; in each protection epoch, h either is associated with a hazard-protectable object, or is unassociated.
Upon creation, a hazard pointer is unassociated.
Changing the association (possibly to the same object) initiates a new protection epoch and ends the preceding one.
4
#
An object x of hazard-protectable type T is retired with a deleter of type D when the member function hazard_pointer_obj_base<T, D>​::​retire is invoked on x.
Any given object x shall be retired at most once.
5
#
A retired object x is reclaimed by invoking its deleter with a pointer to x; the behavior is undefined if that invocation exits via an exception.
6
#
A hazard-protectable object x is possibly-reclaimable with respect to an evaluation A if:
  • (6.1)
    x is not reclaimed; and
  • (6.2)
    x is retired in an evaluation R and A does not happen before R; and
  • (6.3)
    for all hazard pointers h and for every protection epoch E of h during which h is associated with x:
    • (6.3.1)
      if the beginning of E happens before R, the end of E strongly happens before A; and
    • (6.3.2)
      if E began by an evaluation of try_protect with argument src, label its atomic load operation L.
      If there exists an atomic modification B on src such that L observes a modification that is modification-ordered before B, and B happens before x is retired, the end of E strongly happens before A.
      [Note 1: 
      In typical use, a store to src sequenced before retiring x will be such an atomic operation B.
      — end note]
    [Note 2: 
    The latter two conditions convey the informal notion that a protection epoch that began before retiring x, as implied either by the happens-before relation or the coherence order of some source, delays the reclamation of x.
    — end note]
7
#
The number of possibly-reclaimable objects has an unspecified bound.
[Note 3: 
The bound can be a function of the number of hazard pointers, the number of threads that retire objects, and the number of threads that use hazard pointers.
— end note]
[Example 1: 
The following example shows how hazard pointers allow updates to be carried out in the presence of concurrent readers.
The object of type hazard_pointer in print_name protects the object *ptr from being reclaimed by ptr->retire until the end of the protection epoch.
struct Name : public hazard_pointer_obj_base<Name> { /* details */ }; atomic<Name*> name; // called often and in parallel! void print_name() { hazard_pointer h = make_hazard_pointer(); Name* ptr = h.protect(name); // Protection epoch starts // ... safe to access *ptr } // Protection epoch ends. // called rarely, but possibly concurrently with print_name void update_name(Name* new_name) { Name* ptr = name.exchange(new_name); ptr->retire(); } — end example]

33.11.3.2 Header <hazard_pointer> synopsis [hazard.pointer.syn]

🔗
namespace std { // [saferecl.hp.base], class template hazard_pointer_obj_base template<class T, class D = default_delete<T>> class hazard_pointer_obj_base; // [saferecl.hp.holder], class hazard_pointer class hazard_pointer; // [saferecl.hp.holder.nonmem], non-member functions hazard_pointer make_hazard_pointer(); void swap(hazard_pointer&, hazard_pointer&) noexcept; }

33.11.3.3 Class template hazard_pointer_obj_base [saferecl.hp.base]

namespace std { template<class T, class D = default_delete<T>> class hazard_pointer_obj_base { public: void retire(D d = D()) noexcept; protected: hazard_pointer_obj_base() = default; hazard_pointer_obj_base(const hazard_pointer_obj_base&) = default; hazard_pointer_obj_base(hazard_pointer_obj_base&&) = default; hazard_pointer_obj_base& operator=(const hazard_pointer_obj_base&) = default; hazard_pointer_obj_base& operator=(hazard_pointer_obj_base&&) = default; ~hazard_pointer_obj_base() = default; private: D deleter; // exposition only }; }
1
#
D shall be a function object type ([func.require]) for which, given a value d of type D and a value ptr of type T*, the expression d(ptr) is valid.
2
#
The behavior of a program that adds specializations for hazard_pointer_obj_base is undefined.
3
#
D shall meet the requirements for Cpp17DefaultConstructible and Cpp17MoveAssignable.
4
#
T may be an incomplete type.
It shall be complete before any member of the resulting specialization of hazard_pointer_obj_base is referenced.
🔗
void retire(D d = D()) noexcept;
5
#
Mandates: T is a hazard-protectable type.
6
#
Preconditions: *this is a base class subobject of an object x of type T.
x is not retired.
Move-assigning d to deleter does not exit via an exception.
7
#
Effects: Move-assigns d to deleter, thereby setting it as the deleter of x, then retires x.
May reclaim possibly-reclaimable objects.

33.11.3.4 Class hazard_pointer [saferecl.hp.holder]

33.11.3.4.1 General [saferecl.hp.holder.general]

namespace std { class hazard_pointer { public: hazard_pointer() noexcept; hazard_pointer(hazard_pointer&&) noexcept; hazard_pointer& operator=(hazard_pointer&&) noexcept; ~hazard_pointer(); [[nodiscard]] bool empty() const noexcept; template<class T> T* protect(const atomic<T*>& src) noexcept; template<class T> bool try_protect(T*& ptr, const atomic<T*>& src) noexcept; template<class T> void reset_protection(const T* ptr) noexcept; void reset_protection(nullptr_t = nullptr) noexcept; void swap(hazard_pointer&) noexcept; }; }
1
#
An object of type hazard_pointer is either empty or owns a hazard pointer.
Each hazard pointer is owned by exactly one object of type hazard_pointer.
[Note 1: 
An empty hazard_pointer object is different from a hazard_pointer object that owns an unassociated hazard pointer.
An empty hazard_pointer object does not own any hazard pointers.
— end note]

33.11.3.4.2 Constructors, destructor, and assignment [saferecl.hp.holder.ctor]

🔗
hazard_pointer() noexcept;
1
#
Postconditions: *this is empty.
🔗
hazard_pointer(hazard_pointer&& other) noexcept;
2
#
Postconditions: If other is empty, *this is empty.
Otherwise, *this owns the hazard pointer originally owned by other; other is empty.
🔗
~hazard_pointer();
3
#
Effects: If *this is not empty, destroys the hazard pointer owned by *this, thereby ending its current protection epoch.
🔗
hazard_pointer& operator=(hazard_pointer&& other) noexcept;
4
#
Effects: If this == &other is true, no effect.
Otherwise, if *this is not empty, destroys the hazard pointer owned by *this, thereby ending its current protection epoch.
5
#
Postconditions: If other was empty, *this is empty.
Otherwise, *this owns the hazard pointer originally owned by other.
If this != &other is true, other is empty.
6
#
Returns: *this.

33.11.3.4.3 Member functions [saferecl.hp.holder.mem]

🔗
[[nodiscard]] bool empty() const noexcept;
1
#
Returns: true if and only if *this is empty.
🔗
template<class T> T* protect(const atomic<T*>& src) noexcept;
2
#
Effects: Equivalent to: T* ptr = src.load(memory_order::relaxed); while (!try_protect(ptr, src)) {} return ptr;
🔗
template<class T> bool try_protect(T*& ptr, const atomic<T*>& src) noexcept;
3
#
Mandates: T is a hazard-protectable type.
4
#
Preconditions: *this is not empty.
5
#
Effects: Performs the following steps in order:
  • (5.1)
    Initializes a variable old of type T* with the value of ptr.
  • (5.2)
    Evaluates reset_protection(old).
  • (5.3)
    Assigns the value of src.load(memory_order​::​acquire) to ptr.
  • (5.4)
    If old == ptr is false, evaluates reset_protection().
6
#
Returns: old == ptr.
🔗
template<class T> void reset_protection(const T* ptr) noexcept;
7
#
Mandates: T is a hazard-protectable type.
8
#
Preconditions: *this is not empty.
9
#
Effects: If ptr is a null pointer value, invokes reset_protection().
Otherwise, associates the hazard pointer owned by *this with *ptr, thereby ending the current protection epoch.
10
#
Complexity: Constant.
🔗
void reset_protection(nullptr_t = nullptr) noexcept;
11
#
Preconditions: *this is not empty.
12
#
Postconditions: The hazard pointer owned by *this is unassociated.
13
#
Complexity: Constant.
🔗
void swap(hazard_pointer& other) noexcept;
14
#
Effects: Swaps the hazard pointer ownership of this object with that of other.
[Note 1: 
The owned hazard pointers, if any, remain unchanged during the swap and continue to be associated with the respective objects that they were protecting before the swap, if any.
No protection epochs are ended or initiated.
— end note]
15
#
Complexity: Constant.

33.11.3.4.4 Non-member functions [saferecl.hp.holder.nonmem]

🔗
hazard_pointer make_hazard_pointer();
1
#
Effects: Constructs a hazard pointer.
2
#
Returns: A hazard_pointer object that owns the newly-constructed hazard pointer.
3
#
Throws: May throw bad_alloc if memory for the hazard pointer could not be allocated.
🔗
void swap(hazard_pointer& a, hazard_pointer& b) noexcept;
4
#
Effects: Equivalent to a.swap(b).