tmp/tmp0zqew4md/{from.md → to.md}
RENAMED
|
@@ -0,0 +1,85 @@
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 1 |
+
#### General <a id="saferecl.hp.general">[[saferecl.hp.general]]</a>
|
| 2 |
+
|
| 3 |
+
A hazard pointer is a single-writer multi-reader pointer that can be
|
| 4 |
+
owned by at most one thread at any time. Only the owner of the hazard
|
| 5 |
+
pointer can set its value, while any number of threads may read its
|
| 6 |
+
value. The owner thread sets the value of a hazard pointer to point to
|
| 7 |
+
an object in order to indicate to concurrent threads—which may delete
|
| 8 |
+
such an object—that the object is not yet safe to delete.
|
| 9 |
+
|
| 10 |
+
A class type `T` is *hazard-protectable* if it has exactly one base
|
| 11 |
+
class of type `hazard_pointer_obj_base<T, D>` for some `D`, that base is
|
| 12 |
+
public and non-virtual, and it has no base classes of type
|
| 13 |
+
`hazard_pointer_obj_base<T2, D2>` for any other combination `T2`, `D2`.
|
| 14 |
+
An object is *hazard-protectable* if it is of hazard-protectable type.
|
| 15 |
+
|
| 16 |
+
The time span between creation and destruction of a hazard pointer h is
|
| 17 |
+
partitioned into a series of *protection epochs*; in each protection
|
| 18 |
+
epoch, h either is *associated with* a hazard-protectable object, or is
|
| 19 |
+
*unassociated*. Upon creation, a hazard pointer is unassociated.
|
| 20 |
+
Changing the association (possibly to the same object) initiates a new
|
| 21 |
+
protection epoch and ends the preceding one.
|
| 22 |
+
|
| 23 |
+
An object `x` of hazard-protectable type `T` is *retired* with a deleter
|
| 24 |
+
of type `D` when the member function
|
| 25 |
+
`hazard_pointer_obj_base<T, D>::retire` is invoked on `x`. Any given
|
| 26 |
+
object `x` shall be retired at most once.
|
| 27 |
+
|
| 28 |
+
A retired object `x` is *reclaimed* by invoking its deleter with a
|
| 29 |
+
pointer to `x`; the behavior is undefined if that invocation exits via
|
| 30 |
+
an exception.
|
| 31 |
+
|
| 32 |
+
A hazard-protectable object `x` is *possibly-reclaimable* with respect
|
| 33 |
+
to an evaluation A if
|
| 34 |
+
|
| 35 |
+
- `x` is not reclaimed; and
|
| 36 |
+
- `x` is retired in an evaluation R and A does not happen before R; and
|
| 37 |
+
- for all hazard pointers h and for every protection epoch E of h during
|
| 38 |
+
which h is associated with `x`:
|
| 39 |
+
- if the beginning of E happens before R, the end of E strongly
|
| 40 |
+
happens before A; and
|
| 41 |
+
- if E began by an evaluation of `try_protect` with argument `src`,
|
| 42 |
+
label its atomic load operation L. If there exists an atomic
|
| 43 |
+
modification B on `src` such that L observes a modification that is
|
| 44 |
+
modification-ordered before B, and B happens before `x` is retired,
|
| 45 |
+
the end of E strongly happens before A. \[*Note 1*: In typical use,
|
| 46 |
+
a store to `src` sequenced before retiring `x` will be such an
|
| 47 |
+
atomic operation B. — *end note*]
|
| 48 |
+
|
| 49 |
+
\[*Note 2*: The latter two conditions convey the informal notion that
|
| 50 |
+
a protection epoch that began before retiring `x`, as implied either
|
| 51 |
+
by the happens-before relation or the coherence order of some source,
|
| 52 |
+
delays the reclamation of `x`. — *end note*]
|
| 53 |
+
|
| 54 |
+
The number of possibly-reclaimable objects has an unspecified bound.
|
| 55 |
+
|
| 56 |
+
[*Note 3*: The bound can be a function of the number of hazard
|
| 57 |
+
pointers, the number of threads that retire objects, and the number of
|
| 58 |
+
threads that use hazard pointers. — *end note*]
|
| 59 |
+
|
| 60 |
+
[*Example 1*:
|
| 61 |
+
|
| 62 |
+
The following example shows how hazard pointers allow updates to be
|
| 63 |
+
carried out in the presence of concurrent readers. The object of type
|
| 64 |
+
`hazard_pointer` in `print_name` protects the object `*ptr` from being
|
| 65 |
+
reclaimed by `ptr->retire` until the end of the protection epoch.
|
| 66 |
+
|
| 67 |
+
``` cpp
|
| 68 |
+
struct Name : public hazard_pointer_obj_base<Name> { /* details */ };
|
| 69 |
+
atomic<Name*> name;
|
| 70 |
+
// called often and in parallel!
|
| 71 |
+
void print_name() {
|
| 72 |
+
hazard_pointer h = make_hazard_pointer();
|
| 73 |
+
Name* ptr = h.protect(name); // Protection epoch starts
|
| 74 |
+
// ... safe to access *ptr
|
| 75 |
+
} // Protection epoch ends.
|
| 76 |
+
|
| 77 |
+
// called rarely, but possibly concurrently with print_name
|
| 78 |
+
void update_name(Name* new_name) {
|
| 79 |
+
Name* ptr = name.exchange(new_name);
|
| 80 |
+
ptr->retire();
|
| 81 |
+
}
|
| 82 |
+
```
|
| 83 |
+
|
| 84 |
+
— *end example*]
|
| 85 |
+
|