32 Concurrency support library [thread]

32.11 Safe reclamation [saferecl]

32.11.1 General [saferecl.general]

Subclause [saferecl] contains safe-reclamation techniques, which are most frequently used to straightforwardly resolve access-deletion races.

32.11.2 Read-copy update (RCU) [saferecl.rcu]

32.11.2.1 General [saferecl.rcu.general]

RCU is a synchronization mechanism that can be used for linked data structures that are frequently read, but seldom updated.

RCU does not provide mutual exclusion, but instead allows the user to schedule specified actions such as deletion at some later time.

A class type T is rcu-protectable if it has exactly one base class of type rcu_obj_base<T, D> for some D, and that base is public and non-virtual, and it has no base classes of type rcu_obj_base<X, Y> for any other combination X, Y.

An object is rcu-protectable if it is of rcu-protectable type.

An invocation of unlock U on an rcu_domain dom corresponds to an invocation of lock L on dom if L is sequenced before U and either

(3.1)
no other invocation of lock on dom is sequenced after L and before U, or
(3.2)
every invocation of unlock U2 on dom such that L is sequenced before U2 and U2 is sequenced before U corresponds to an invocation of lock L2 on dom such that L is sequenced before L2 and L2 is sequenced before U2.

[Note 1:

This pairs nested locks and unlocks on a given domain in each thread.

— end note]

A region of RCU protection on a domain dom starts with a lock L on dom and ends with its corresponding unlock U.

Given a region of RCU protection R on a domain dom and given an evaluation E that scheduled another evaluation F in dom, if E does not strongly happen before the start of R, the end of R strongly happens before evaluating F.

The evaluation of a scheduled evaluation is potentially concurrent with any other scheduled evaluation.

Each scheduled evaluation is evaluated at most once.

32.11.2.2 Header <rcu> synopsis [rcu.syn]

🔗

namespace std { // [saferecl.rcu.base], class template rcu_obj_base template<class T, class D = default_delete<T>> class rcu_obj_base; // [saferecl.rcu.domain], class rcu_domain class rcu_domain; // [saferecl.rcu.domain.func], non-member functions rcu_domain& rcu_default_domain() noexcept; void rcu_synchronize(rcu_domain& dom = rcu_default_domain()) noexcept; void rcu_barrier(rcu_domain& dom = rcu_default_domain()) noexcept; template<class T, class D = default_delete<T>> void rcu_retire(T* p, D d = D(), rcu_domain& dom = rcu_default_domain()); }

32.11.2.3 Class template rcu_obj_base [saferecl.rcu.base]

Objects of type T to be protected by RCU inherit from a specialization rcu_obj_base<T, D> for some D.

namespace std { template<class T, class D = default_delete<T>> class rcu_obj_base { public: void retire(D d = D(), rcu_domain& dom = rcu_default_domain()) noexcept; protected: rcu_obj_base() = default; rcu_obj_base(const rcu_obj_base&) = default; rcu_obj_base(rcu_obj_base&&) = default; rcu_obj_base& operator=(const rcu_obj_base&) = default; rcu_obj_base& operator=(rcu_obj_base&&) = default; ~rcu_obj_base() = default; private: D deleter; // exposition only }; }

The behavior of a program that adds specializations for rcu_obj_base is undefined.

T may be an incomplete type.

It shall be complete before any member of the resulting specialization of rcu_obj_base is referenced.

D shall be a function object type ([function.objects]) for which, given a value d of type D and a value ptr of type T*, the expression d(ptr) is valid.

D shall meet the requirements for Cpp17DefaultConstructible and Cpp17MoveAssignable.

If D is trivially copyable, all specializations of rcu_obj_base<T, D> are trivially copyable.

🔗

void retire(D d = D(), rcu_domain& dom = rcu_default_domain()) noexcept;

Mandates: T is an rcu-protectable type.

Preconditions: *this is a base class subobject of an object x of type T.

The member function rcu_obj_base<T, D>::retire was not invoked on x before.

The assignment to deleter does not exit via an exception.

Effects: Evaluates deleter = std::move(d) and schedules the evaluation of the expression deleter(
addressof(x)) in the domain dom; the behavior is undefined if that evaluation exits via an exception.

May invoke scheduled evaluations in dom.

[Note 1:

If such evaluations acquire resources held across any invocation of retire on dom, deadlock can occur.

— end note]

32.11.2.4 Class rcu_domain [saferecl.rcu.domain]

32.11.2.4.1 General [saferecl.rcu.domain.general]

namespace std { class rcu_domain { public: rcu_domain(const rcu_domain&) = delete; rcu_domain& operator=(const rcu_domain&) = delete; void lock() noexcept; bool try_lock() noexcept; void unlock() noexcept; }; }

This class meets the requirements of Cpp17Lockable ([thread.req.lockable.req]) and provides regions of RCU protection.

[Example 1: std::scoped_lock<rcu_domain> rlock(rcu_default_domain()); — end example]

The functions lock and unlock establish (possibly nested) regions of RCU protection.

32.11.2.4.2 Member functions [saferecl.rcu.domain.members]

🔗

void lock() noexcept;

Effects: Opens a region of RCU protection.

Remarks: Calls to lock do not introduce a data race ([intro.races]) involving *this.

🔗

bool try_lock() noexcept;

Effects: Equivalent to lock().

Returns: true.

🔗

void unlock() noexcept;

Preconditions: A call to lock that opened an unclosed region of RCU protection is sequenced before the call to unlock.

Effects: Closes the unclosed region of RCU protection that was most recently opened.

May invoke scheduled evaluations in *this.

[Note 1:

If such evaluations acquire resources held across any invocation of unlock on *this, deadlock can occur.

— end note]

Remarks: Calls to unlock do not introduce a data race involving *this.

[Note 2:

Evaluation of scheduled evaluations can still cause a data race.

— end note]

32.11.2.4.3 Non-member functions [saferecl.rcu.domain.func]

🔗

rcu_domain& rcu_default_domain() noexcept;

Returns: A reference to a static-duration object of type rcu_domain.

A reference to the same object is returned every time this function is called.

🔗

void rcu_synchronize(rcu_domain& dom = rcu_default_domain()) noexcept;

Effects: If the call to rcu_synchronize does not strongly happen before the lock opening an RCU protection region R on dom, blocks until the unlock closing R happens.

Synchronization: The unlock closing R strongly happens before the return from rcu_synchronize.

🔗

void rcu_barrier(rcu_domain& dom = rcu_default_domain()) noexcept;

Effects: May evaluate any scheduled evaluations in dom.

For any evaluation that happens before the call to rcu_barrier and that schedules an evaluation E in dom, blocks until E has been evaluated.

Synchronization: The evaluation of any such E strongly happens before the return from rcu_barrier.

[Note 1:

A call to rcu_barrier does not imply a call to rcu_synchronize and vice versa.

— end note]

🔗

template<class T, class D = default_delete<T>>
void rcu_retire(T* p, D d = D(), rcu_domain& dom = rcu_default_domain());

Mandates: is_move_constructible_v<D> is true and the expression d(p) is well-formed.

Preconditions: D meets the Cpp17MoveConstructible and Cpp17Destructible requirements.

Effects: May allocate memory.

It is unspecified whether the memory allocation is performed by invoking operator new.

Initializes an object d1 of type D from std::move(d).

Schedules the evaluation of d1(p) in the domain dom; the behavior is undefined if that evaluation exits via an exception.

May invoke scheduled evaluations in dom.

[Note 2:

If rcu_retire exits via an exception, no evaluation is scheduled.

— end note]

Throws: bad_alloc or any exception thrown by the initialization of d1.

[Note 3:

If scheduled evaluations acquire resources held across any invocation of rcu_retire on dom, deadlock can occur.

— end note]

32.11.3 Hazard pointers [saferecl.hp]

32.11.3.1 General [saferecl.hp.general]

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.

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.

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.

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.

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.

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]

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]

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

32.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 }; }

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.

The behavior of a program that adds specializations for hazard_pointer_obj_base is undefined.

D shall meet the requirements for Cpp17DefaultConstructible and Cpp17MoveAssignable.

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;

Mandates: T is a hazard-protectable type.

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.

Effects: Move-assigns d to deleter, thereby setting it as the deleter of x, then retires x.

May reclaim possibly-reclaimable objects.

32.11.3.4 Class hazard_pointer [saferecl.hp.holder]

32.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(); 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; }; }

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]

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

🔗

hazard_pointer() noexcept;

Postconditions: *this is empty.

🔗

hazard_pointer(hazard_pointer&& other) noexcept;

Postconditions: If other is empty, *this is empty.

Otherwise, *this owns the hazard pointer originally owned by other; other is empty.

🔗

~hazard_pointer();

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;

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.

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.

Returns: *this.

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

🔗

bool empty() const noexcept;

Returns: true if and only if *this is empty.

🔗

template<class T> T* protect(const atomic<T*>& src) noexcept;

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;

Mandates: T is a hazard-protectable type.

Preconditions: *this is not empty.

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().

Returns: old == ptr.

🔗

template<class T> void reset_protection(const T* ptr) noexcept;

Mandates: T is a hazard-protectable type.

Preconditions: *this is not empty.

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.

Complexity: Constant.

🔗

void reset_protection(nullptr_t = nullptr) noexcept;

Preconditions: *this is not empty.

Postconditions: The hazard pointer owned by *this is unassociated.

Complexity: Constant.

🔗

void swap(hazard_pointer& other) noexcept;

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]

Complexity: Constant.

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

🔗

hazard_pointer make_hazard_pointer();

Effects: Constructs a hazard pointer.

Returns: A hazard_pointer object that owns the newly-constructed hazard pointer.

Throws: May throw bad_alloc if memory for the hazard pointer could not be allocated.

🔗

void swap(hazard_pointer& a, hazard_pointer& b) noexcept;

Effects: Equivalent to a.swap(b).