1//! `futures::task::AtomicWaker` extracted into its own crate.
2//!
3//! # Features
4//!
5//! This crate adds a feature, `portable-atomic`, which uses a polyfill
6//! from the [`portable-atomic`] crate in order to provide functionality
7//! to targets without atomics. See the [`README`] for the [`portable-atomic`]
8//! crate for more information on how to use it.
9//!
10//! [`portable-atomic`]: https://crates.io/crates/portable-atomic
11//! [`README`]: https://github.com/taiki-e/portable-atomic/blob/main/README.md#optional-cfg
12
13#![no_std]
14#![doc(
15 html_favicon_url = "https://raw.githubusercontent.com/smol-rs/smol/master/assets/images/logo_fullsize_transparent.png"
16)]
17#![doc(
18 html_logo_url = "https://raw.githubusercontent.com/smol-rs/smol/master/assets/images/logo_fullsize_transparent.png"
19)]
20
21use core::cell::UnsafeCell;
22use core::fmt;
23use core::sync::atomic::Ordering::{AcqRel, Acquire, Release};
24use core::task::Waker;
25
26#[cfg(not(feature = "portable-atomic"))]
27use core::sync::atomic::AtomicUsize;
28#[cfg(feature = "portable-atomic")]
29use portable_atomic::AtomicUsize;
30
31/// A synchronization primitive for task wakeup.
32///
33/// Sometimes the task interested in a given event will change over time.
34/// An `AtomicWaker` can coordinate concurrent notifications with the consumer
35/// potentially "updating" the underlying task to wake up. This is useful in
36/// scenarios where a computation completes in another thread and wants to
37/// notify the consumer, but the consumer is in the process of being migrated to
38/// a new logical task.
39///
40/// Consumers should call `register` before checking the result of a computation
41/// and producers should call `wake` after producing the computation (this
42/// differs from the usual `thread::park` pattern). It is also permitted for
43/// `wake` to be called **before** `register`. This results in a no-op.
44///
45/// A single `AtomicWaker` may be reused for any number of calls to `register` or
46/// `wake`.
47///
48/// # Memory ordering
49///
50/// Calling `register` "acquires" all memory "released" by calls to `wake`
51/// before the call to `register`. Later calls to `wake` will wake the
52/// registered waker (on contention this wake might be triggered in `register`).
53///
54/// For concurrent calls to `register` (should be avoided) the ordering is only
55/// guaranteed for the winning call.
56///
57/// # Examples
58///
59/// Here is a simple example providing a `Flag` that can be signalled manually
60/// when it is ready.
61///
62/// ```
63/// use futures::future::Future;
64/// use futures::task::{Context, Poll, AtomicWaker};
65/// use std::sync::Arc;
66/// use std::sync::atomic::AtomicBool;
67/// use std::sync::atomic::Ordering::Relaxed;
68/// use std::pin::Pin;
69///
70/// struct Inner {
71/// waker: AtomicWaker,
72/// set: AtomicBool,
73/// }
74///
75/// #[derive(Clone)]
76/// struct Flag(Arc<Inner>);
77///
78/// impl Flag {
79/// pub fn new() -> Self {
80/// Flag(Arc::new(Inner {
81/// waker: AtomicWaker::new(),
82/// set: AtomicBool::new(false),
83/// }))
84/// }
85///
86/// pub fn signal(&self) {
87/// self.0.set.store(true, Relaxed);
88/// self.0.waker.wake();
89/// }
90/// }
91///
92/// impl Future for Flag {
93/// type Output = ();
94///
95/// fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<()> {
96/// // quick check to avoid registration if already done.
97/// if self.0.set.load(Relaxed) {
98/// return Poll::Ready(());
99/// }
100///
101/// self.0.waker.register(cx.waker());
102///
103/// // Need to check condition **after** `register` to avoid a race
104/// // condition that would result in lost notifications.
105/// if self.0.set.load(Relaxed) {
106/// Poll::Ready(())
107/// } else {
108/// Poll::Pending
109/// }
110/// }
111/// }
112/// ```
113pub struct AtomicWaker {
114 state: AtomicUsize,
115 waker: UnsafeCell<Option<Waker>>,
116}
117
118// `AtomicWaker` is a multi-consumer, single-producer transfer cell. The cell
119// stores a `Waker` value produced by calls to `register` and many threads can
120// race to take the waker (to wake it) by calling `wake`.
121//
122// If a new `Waker` instance is produced by calling `register` before an
123// existing one is consumed, then the existing one is overwritten.
124//
125// While `AtomicWaker` is single-producer, the implementation ensures memory
126// safety. In the event of concurrent calls to `register`, there will be a
127// single winner whose waker will get stored in the cell. The losers will not
128// have their tasks woken. As such, callers should ensure to add synchronization
129// to calls to `register`.
130//
131// The implementation uses a single `AtomicUsize` value to coordinate access to
132// the `Waker` cell. There are two bits that are operated on independently.
133// These are represented by `REGISTERING` and `WAKING`.
134//
135// The `REGISTERING` bit is set when a producer enters the critical section. The
136// `WAKING` bit is set when a consumer enters the critical section. Neither bit
137// being set is represented by `WAITING`.
138//
139// A thread obtains an exclusive lock on the waker cell by transitioning the
140// state from `WAITING` to `REGISTERING` or `WAKING`, depending on the operation
141// the thread wishes to perform. When this transition is made, it is guaranteed
142// that no other thread will access the waker cell.
143//
144// # Registering
145//
146// On a call to `register`, an attempt to transition the state from WAITING to
147// REGISTERING is made. On success, the caller obtains a lock on the waker cell.
148//
149// If the lock is obtained, then the thread sets the waker cell to the waker
150// provided as an argument. Then it attempts to transition the state back from
151// `REGISTERING` -> `WAITING`.
152//
153// If this transition is successful, then the registering process is complete
154// and the next call to `wake` will observe the waker.
155//
156// If the transition fails, then there was a concurrent call to `wake` that was
157// unable to access the waker cell (due to the registering thread holding the
158// lock). To handle this, the registering thread removes the waker it just set
159// from the cell and calls `wake` on it. This call to wake represents the
160// attempt to wake by the other thread (that set the `WAKING` bit). The state is
161// then transitioned from `REGISTERING | WAKING` back to `WAITING`. This
162// transition must succeed because, at this point, the state cannot be
163// transitioned by another thread.
164//
165// # Waking
166//
167// On a call to `wake`, an attempt to transition the state from `WAITING` to
168// `WAKING` is made. On success, the caller obtains a lock on the waker cell.
169//
170// If the lock is obtained, then the thread takes ownership of the current value
171// in the waker cell, and calls `wake` on it. The state is then transitioned
172// back to `WAITING`. This transition must succeed as, at this point, the state
173// cannot be transitioned by another thread.
174//
175// If the thread is unable to obtain the lock, the `WAKING` bit is still. This
176// is because it has either been set by the current thread but the previous
177// value included the `REGISTERING` bit **or** a concurrent thread is in the
178// `WAKING` critical section. Either way, no action must be taken.
179//
180// If the current thread is the only concurrent call to `wake` and another
181// thread is in the `register` critical section, when the other thread **exits**
182// the `register` critical section, it will observe the `WAKING` bit and handle
183// the wake itself.
184//
185// If another thread is in the `wake` critical section, then it will handle
186// waking the task.
187//
188// # A potential race (is safely handled).
189//
190// Imagine the following situation:
191//
192// * Thread A obtains the `wake` lock and wakes a task.
193//
194// * Before thread A releases the `wake` lock, the woken task is scheduled.
195//
196// * Thread B attempts to wake the task. In theory this should result in the
197// task being woken, but it cannot because thread A still holds the wake lock.
198//
199// This case is handled by requiring users of `AtomicWaker` to call `register`
200// **before** attempting to observe the application state change that resulted
201// in the task being awoken. The wakers also change the application state before
202// calling wake.
203//
204// Because of this, the waker will do one of two things.
205//
206// 1) Observe the application state change that Thread B is woken for. In this
207// case, it is OK for Thread B's wake to be lost.
208//
209// 2) Call register before attempting to observe the application state. Since
210// Thread A still holds the `wake` lock, the call to `register` will result
211// in the task waking itself and get scheduled again.
212
213/// Idle state
214const WAITING: usize = 0;
215
216/// A new waker value is being registered with the `AtomicWaker` cell.
217const REGISTERING: usize = 0b01;
218
219/// The waker currently registered with the `AtomicWaker` cell is being woken.
220const WAKING: usize = 0b10;
221
222impl AtomicWaker {
223 /// Create an `AtomicWaker`.
224 pub const fn new() -> Self {
225 // Make sure that task is Sync
226 trait AssertSync: Sync {}
227 impl AssertSync for Waker {}
228
229 AtomicWaker {
230 state: AtomicUsize::new(WAITING),
231 waker: UnsafeCell::new(None),
232 }
233 }
234
235 /// Registers the waker to be notified on calls to `wake`.
236 ///
237 /// The new task will take place of any previous tasks that were registered
238 /// by previous calls to `register`. Any calls to `wake` that happen after
239 /// a call to `register` (as defined by the memory ordering rules), will
240 /// notify the `register` caller's task and deregister the waker from future
241 /// notifications. Because of this, callers should ensure `register` gets
242 /// invoked with a new `Waker` **each** time they require a wakeup.
243 ///
244 /// It is safe to call `register` with multiple other threads concurrently
245 /// calling `wake`. This will result in the `register` caller's current
246 /// task being notified once.
247 ///
248 /// This function is safe to call concurrently, but this is generally a bad
249 /// idea. Concurrent calls to `register` will attempt to register different
250 /// tasks to be notified. One of the callers will win and have its task set,
251 /// but there is no guarantee as to which caller will succeed.
252 ///
253 /// # Examples
254 ///
255 /// Here is how `register` is used when implementing a flag.
256 ///
257 /// ```
258 /// use futures::future::Future;
259 /// use futures::task::{Context, Poll, AtomicWaker};
260 /// use std::sync::atomic::AtomicBool;
261 /// use std::sync::atomic::Ordering::Relaxed;
262 /// use std::pin::Pin;
263 ///
264 /// struct Flag {
265 /// waker: AtomicWaker,
266 /// set: AtomicBool,
267 /// }
268 ///
269 /// impl Future for Flag {
270 /// type Output = ();
271 ///
272 /// fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<()> {
273 /// // Register **before** checking `set` to avoid a race condition
274 /// // that would result in lost notifications.
275 /// self.waker.register(cx.waker());
276 ///
277 /// if self.set.load(Relaxed) {
278 /// Poll::Ready(())
279 /// } else {
280 /// Poll::Pending
281 /// }
282 /// }
283 /// }
284 /// ```
285 pub fn register(&self, waker: &Waker) {
286 match self
287 .state
288 .compare_exchange(WAITING, REGISTERING, Acquire, Acquire)
289 .unwrap_or_else(|x| x)
290 {
291 WAITING => {
292 unsafe {
293 // Locked acquired, update the waker cell
294
295 // Avoid cloning the waker if the old waker will awaken the same task.
296 match &*self.waker.get() {
297 Some(old_waker) if old_waker.will_wake(waker) => (),
298 _ => *self.waker.get() = Some(waker.clone()),
299 }
300
301 // Release the lock. If the state transitioned to include
302 // the `WAKING` bit, this means that at least one wake has
303 // been called concurrently.
304 //
305 // Start by assuming that the state is `REGISTERING` as this
306 // is what we just set it to. If this holds, we know that no
307 // other writes were performed in the meantime, so there is
308 // nothing to acquire, only release. In case of concurrent
309 // wakers, we need to acquire their releases, so success needs
310 // to do both.
311 let res = self
312 .state
313 .compare_exchange(REGISTERING, WAITING, AcqRel, Acquire);
314
315 match res {
316 Ok(_) => {
317 // memory ordering: acquired self.state during CAS
318 // - if previous wakes went through it syncs with
319 // their final release (`fetch_and`)
320 // - if there was no previous wake the next wake
321 // will wake us, no sync needed.
322 }
323 Err(actual) => {
324 // This branch can only be reached if at least one
325 // concurrent thread called `wake`. In this
326 // case, `actual` **must** be `REGISTERING |
327 // `WAKING`.
328 debug_assert_eq!(actual, REGISTERING | WAKING);
329
330 // Take the waker to wake once the atomic operation has
331 // completed.
332 let waker = (*self.waker.get()).take().unwrap();
333
334 // We need to return to WAITING state (clear our lock and
335 // concurrent WAKING flag). This needs to acquire all
336 // WAKING fetch_or releases and it needs to release our
337 // update to self.waker, so we need a `swap` operation.
338 self.state.swap(WAITING, AcqRel);
339
340 // memory ordering: we acquired the state for all
341 // concurrent wakes, but future wakes might still
342 // need to wake us in case we can't make progress
343 // from the pending wakes.
344 //
345 // So we simply schedule to come back later (we could
346 // also simply leave the registration in place above).
347 waker.wake();
348 }
349 }
350 }
351 }
352 WAKING => {
353 // Currently in the process of waking the task, i.e.,
354 // `wake` is currently being called on the old task handle.
355 //
356 // memory ordering: we acquired the state for all
357 // concurrent wakes, but future wakes might still
358 // need to wake us in case we can't make progress
359 // from the pending wakes.
360 //
361 // So we simply schedule to come back later (we
362 // could also spin here trying to acquire the lock
363 // to register).
364 waker.wake_by_ref();
365 }
366 state => {
367 // In this case, a concurrent thread is holding the
368 // "registering" lock. This probably indicates a bug in the
369 // caller's code as racing to call `register` doesn't make much
370 // sense.
371 //
372 // memory ordering: don't care. a concurrent register() is going
373 // to succeed and provide proper memory ordering.
374 //
375 // We just want to maintain memory safety. It is ok to drop the
376 // call to `register`.
377 debug_assert!(state == REGISTERING || state == REGISTERING | WAKING);
378 }
379 }
380 }
381
382 /// Calls `wake` on the last `Waker` passed to `register`.
383 ///
384 /// If `register` has not been called yet, then this does nothing.
385 pub fn wake(&self) {
386 if let Some(waker) = self.take() {
387 waker.wake();
388 }
389 }
390
391 /// Returns the last `Waker` passed to `register`, so that the user can wake it.
392 ///
393 ///
394 /// Sometimes, just waking the AtomicWaker is not fine grained enough. This allows the user
395 /// to take the waker and then wake it separately, rather than performing both steps in one
396 /// atomic action.
397 ///
398 /// If a waker has not been registered, this returns `None`.
399 pub fn take(&self) -> Option<Waker> {
400 // AcqRel ordering is used in order to acquire the value of the `task`
401 // cell as well as to establish a `release` ordering with whatever
402 // memory the `AtomicWaker` is associated with.
403 match self.state.fetch_or(WAKING, AcqRel) {
404 WAITING => {
405 // The waking lock has been acquired.
406 let waker = unsafe { (*self.waker.get()).take() };
407
408 // Release the lock
409 self.state.fetch_and(!WAKING, Release);
410
411 waker
412 }
413 state => {
414 // There is a concurrent thread currently updating the
415 // associated task.
416 //
417 // Nothing more to do as the `WAKING` bit has been set. It
418 // doesn't matter if there are concurrent registering threads or
419 // not.
420 //
421 debug_assert!(
422 state == REGISTERING || state == REGISTERING | WAKING || state == WAKING
423 );
424 None
425 }
426 }
427 }
428}
429
430impl Default for AtomicWaker {
431 fn default() -> Self {
432 AtomicWaker::new()
433 }
434}
435
436impl fmt::Debug for AtomicWaker {
437 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
438 write!(f, "AtomicWaker")
439 }
440}
441
442unsafe impl Send for AtomicWaker {}
443unsafe impl Sync for AtomicWaker {}
444