1 // Each `Once` has one word of atomic state, and this state is CAS'd on to
2 // determine what to do. There are four possible state of a `Once`:
4 // * Incomplete - no initialization has run yet, and no thread is currently
6 // * Poisoned - some thread has previously attempted to initialize the Once, but
7 // it panicked, so the Once is now poisoned. There are no other
8 // threads currently accessing this Once.
9 // * Running - some thread is currently attempting to run initialization. It may
10 // succeed, so all future threads need to wait for it to finish.
11 // Note that this state is accompanied with a payload, described
13 // * Complete - initialization has completed and all future calls should finish
16 // With 4 states we need 2 bits to encode this, and we use the remaining bits
17 // in the word we have allocated as a queue of threads waiting for the thread
18 // responsible for entering the RUNNING state. This queue is just a linked list
19 // of Waiter nodes which is monotonically increasing in size. Each node is
20 // allocated on the stack, and whenever the running closure finishes it will
21 // consume the entire queue and notify all waiters they should try again.
23 // You'll find a few more details in the implementation, but that's the gist of
27 // When running `Once` we deal with multiple atomics:
28 // `Once.state_and_queue` and an unknown number of `Waiter.signaled`.
29 // * `state_and_queue` is used (1) as a state flag, (2) for synchronizing the
30 // result of the `Once`, and (3) for synchronizing `Waiter` nodes.
31 // - At the end of the `call` function we have to make sure the result
32 // of the `Once` is acquired. So every load which can be the only one to
33 // load COMPLETED must have at least acquire ordering, which means all
35 // - `WaiterQueue::drop` is the only place that may store COMPLETED, and
36 // must do so with release ordering to make the result available.
37 // - `wait` inserts `Waiter` nodes as a pointer in `state_and_queue`, and
38 // needs to make the nodes available with release ordering. The load in
39 // its `compare_exchange` can be relaxed because it only has to compare
40 // the atomic, not to read other data.
41 // - `WaiterQueue::drop` must see the `Waiter` nodes, so it must load
42 // `state_and_queue` with acquire ordering.
43 // - There is just one store where `state_and_queue` is used only as a
44 // state flag, without having to synchronize data: switching the state
45 // from INCOMPLETE to RUNNING in `call`. This store can be Relaxed,
46 // but the read has to be Acquire because of the requirements mentioned
48 // * `Waiter.signaled` is both used as a flag, and to protect a field with
49 // interior mutability in `Waiter`. `Waiter.thread` is changed in
50 // `WaiterQueue::drop` which then sets `signaled` with release ordering.
51 // After `wait` loads `signaled` with acquire ordering and sees it is true,
52 // it needs to see the changes to drop the `Waiter` struct correctly.
53 // * There is one place where the two atomics `Once.state_and_queue` and
54 // `Waiter.signaled` come together, and might be reordered by the compiler or
55 // processor. Because both use acquire ordering such a reordering is not
56 // allowed, so no need for `SeqCst`.
58 use crate::cell
::Cell
;
61 use crate::sync
as public
;
62 use crate::sync
::atomic
::{AtomicBool, AtomicPtr, Ordering}
;
63 use crate::thread
::{self, Thread}
;
68 state_and_queue
: AtomicPtr
<Masked
>,
71 pub struct OnceState
{
73 set_state_on_drop_to
: Cell
<*mut Masked
>,
76 // Four states that a Once can be in, encoded into the lower bits of
77 // `state_and_queue` in the Once structure.
78 const INCOMPLETE
: usize = 0x0;
79 const POISONED
: usize = 0x1;
80 const RUNNING
: usize = 0x2;
81 const COMPLETE
: usize = 0x3;
83 // Mask to learn about the state. All other bits are the queue of waiters if
84 // this is in the RUNNING state.
85 const STATE_MASK
: usize = 0x3;
87 // Representation of a node in the linked list of waiters, used while in the
89 // Note: `Waiter` can't hold a mutable pointer to the next thread, because then
90 // `wait` would both hand out a mutable reference to its `Waiter` node, and keep
91 // a shared reference to check `signaled`. Instead we hold shared references and
92 // use interior mutability.
93 #[repr(align(4))] // Ensure the two lower bits are free to use as state bits.
95 thread
: Cell
<Option
<Thread
>>,
100 // Head of a linked list of waiters.
101 // Every node is a struct on the stack of a waiting thread.
102 // Will wake up the waiters when it gets dropped, i.e. also on panic.
103 struct WaiterQueue
<'a
> {
104 state_and_queue
: &'a AtomicPtr
<Masked
>,
105 set_state_on_drop_to
: *mut Masked
,
110 pub const fn new() -> Once
{
111 Once { state_and_queue: AtomicPtr::new(ptr::invalid_mut(INCOMPLETE)) }
115 pub fn is_completed(&self) -> bool
{
116 // An `Acquire` load is enough because that makes all the initialization
117 // operations visible to us, and, this being a fast path, weaker
118 // ordering helps with performance. This `Acquire` synchronizes with
119 // `Release` operations on the slow path.
120 self.state_and_queue
.load(Ordering
::Acquire
).addr() == COMPLETE
123 // This is a non-generic function to reduce the monomorphization cost of
124 // using `call_once` (this isn't exactly a trivial or small implementation).
126 // Additionally, this is tagged with `#[cold]` as it should indeed be cold
127 // and it helps let LLVM know that calls to this function should be off the
128 // fast path. Essentially, this should help generate more straight line code
131 // Finally, this takes an `FnMut` instead of a `FnOnce` because there's
132 // currently no way to take an `FnOnce` and call it via virtual dispatch
133 // without some allocation overhead.
136 pub fn call(&self, ignore_poisoning
: bool
, init
: &mut dyn FnMut(&public
::OnceState
)) {
137 let mut state_and_queue
= self.state_and_queue
.load(Ordering
::Acquire
);
139 match state_and_queue
.addr() {
141 POISONED
if !ignore_poisoning
=> {
142 // Panic to propagate the poison.
143 panic
!("Once instance has previously been poisoned");
145 POISONED
| INCOMPLETE
=> {
146 // Try to register this thread as the one RUNNING.
147 let exchange_result
= self.state_and_queue
.compare_exchange(
149 ptr
::invalid_mut(RUNNING
),
153 if let Err(old
) = exchange_result
{
154 state_and_queue
= old
;
157 // `waiter_queue` will manage other waiting threads, and
158 // wake them up on drop.
159 let mut waiter_queue
= WaiterQueue
{
160 state_and_queue
: &self.state_and_queue
,
161 set_state_on_drop_to
: ptr
::invalid_mut(POISONED
),
163 // Run the initialization function, letting it know if we're
165 let init_state
= public
::OnceState
{
167 poisoned
: state_and_queue
.addr() == POISONED
,
168 set_state_on_drop_to
: Cell
::new(ptr
::invalid_mut(COMPLETE
)),
172 waiter_queue
.set_state_on_drop_to
= init_state
.inner
.set_state_on_drop_to
.get();
176 // All other values must be RUNNING with possibly a
177 // pointer to the waiter queue in the more significant bits.
178 assert
!(state_and_queue
.addr() & STATE_MASK
== RUNNING
);
179 wait(&self.state_and_queue
, state_and_queue
);
180 state_and_queue
= self.state_and_queue
.load(Ordering
::Acquire
);
187 fn wait(state_and_queue
: &AtomicPtr
<Masked
>, mut current_state
: *mut Masked
) {
188 // Note: the following code was carefully written to avoid creating a
189 // mutable reference to `node` that gets aliased.
191 // Don't queue this thread if the status is no longer running,
192 // otherwise we will not be woken up.
193 if current_state
.addr() & STATE_MASK
!= RUNNING
{
197 // Create the node for our current thread.
199 thread
: Cell
::new(Some(thread
::current())),
200 signaled
: AtomicBool
::new(false),
201 next
: current_state
.with_addr(current_state
.addr() & !STATE_MASK
) as *const Waiter
,
203 let me
= &node
as *const Waiter
as *const Masked
as *mut Masked
;
205 // Try to slide in the node at the head of the linked list, making sure
206 // that another thread didn't just replace the head of the linked list.
207 let exchange_result
= state_and_queue
.compare_exchange(
209 me
.with_addr(me
.addr() | RUNNING
),
213 if let Err(old
) = exchange_result
{
218 // We have enqueued ourselves, now lets wait.
219 // It is important not to return before being signaled, otherwise we
220 // would drop our `Waiter` node and leave a hole in the linked list
221 // (and a dangling reference). Guard against spurious wakeups by
222 // reparking ourselves until we are signaled.
223 while !node
.signaled
.load(Ordering
::Acquire
) {
224 // If the managing thread happens to signal and unpark us before we
225 // can park ourselves, the result could be this thread never gets
226 // unparked. Luckily `park` comes with the guarantee that if it got
227 // an `unpark` just before on an unparked thread it does not park.
234 #[stable(feature = "std_debug", since = "1.16.0")]
235 impl fmt
::Debug
for Once
{
236 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
237 f
.debug_struct("Once").finish_non_exhaustive()
241 impl Drop
for WaiterQueue
<'_
> {
243 // Swap out our state with however we finished.
244 let state_and_queue
=
245 self.state_and_queue
.swap(self.set_state_on_drop_to
, Ordering
::AcqRel
);
247 // We should only ever see an old state which was RUNNING.
248 assert_eq
!(state_and_queue
.addr() & STATE_MASK
, RUNNING
);
250 // Walk the entire linked list of waiters and wake them up (in lifo
251 // order, last to register is first to wake up).
253 // Right after setting `node.signaled = true` the other thread may
254 // free `node` if there happens to be has a spurious wakeup.
255 // So we have to take out the `thread` field and copy the pointer to
258 state_and_queue
.with_addr(state_and_queue
.addr() & !STATE_MASK
) as *const Waiter
;
259 while !queue
.is_null() {
260 let next
= (*queue
).next
;
261 let thread
= (*queue
).thread
.take().unwrap();
262 (*queue
).signaled
.store(true, Ordering
::Release
);
263 // ^- FIXME (maybe): This is another case of issue #55005
264 // `store()` has a potentially dangling ref to `signaled`.
274 pub fn is_poisoned(&self) -> bool
{
279 pub fn poison(&self) {
280 self.set_state_on_drop_to
.set(ptr
::invalid_mut(POISONED
));