once_cell/
race.rs

1//! Thread-safe, non-blocking, "first one wins" flavor of `OnceCell`.
2//!
3//! If two threads race to initialize a type from the `race` module, they
4//! don't block, execute initialization function together, but only one of
5//! them stores the result.
6//!
7//! This module does not require `std` feature.
8//!
9//! # Atomic orderings
10//!
11//! All types in this module use `Acquire` and `Release`
12//! [atomic orderings](Ordering) for all their operations. While this is not
13//! strictly necessary for types other than `OnceBox`, it is useful for users as
14//! it allows them to be certain that after `get` or `get_or_init` returns on
15//! one thread, any side-effects caused by the setter thread prior to them
16//! calling `set` or `get_or_init` will be made visible to that thread; without
17//! it, it's possible for it to appear as if they haven't happened yet from the
18//! getter thread's perspective. This is an acceptable tradeoff to make since
19//! `Acquire` and `Release` have very little performance overhead on most
20//! architectures versus `Relaxed`.
21
22#[cfg(not(feature = "portable-atomic"))]
23use core::sync::atomic;
24#[cfg(feature = "portable-atomic")]
25use portable_atomic as atomic;
26
27use atomic::{AtomicPtr, AtomicUsize, Ordering};
28use core::cell::UnsafeCell;
29use core::marker::PhantomData;
30use core::num::NonZeroUsize;
31use core::ptr;
32
33/// A thread-safe cell which can be written to only once.
34#[derive(Default, Debug)]
35pub struct OnceNonZeroUsize {
36    inner: AtomicUsize,
37}
38
39impl OnceNonZeroUsize {
40    /// Creates a new empty cell.
41    #[inline]
42    pub const fn new() -> OnceNonZeroUsize {
43        OnceNonZeroUsize { inner: AtomicUsize::new(0) }
44    }
45
46    /// Gets the underlying value.
47    #[inline]
48    pub fn get(&self) -> Option<NonZeroUsize> {
49        let val = self.inner.load(Ordering::Acquire);
50        NonZeroUsize::new(val)
51    }
52
53    /// Get the reference to the underlying value, without checking if the cell
54    /// is initialized.
55    ///
56    /// # Safety
57    ///
58    /// Caller must ensure that the cell is in initialized state, and that
59    /// the contents are acquired by (synchronized to) this thread.
60    pub unsafe fn get_unchecked(&self) -> NonZeroUsize {
61        #[inline(always)]
62        fn as_const_ptr(r: &AtomicUsize) -> *const usize {
63            use core::mem::align_of;
64
65            let p: *const AtomicUsize = r;
66            // SAFETY: "This type has the same size and bit validity as
67            // the underlying integer type, usize. However, the alignment of
68            // this type is always equal to its size, even on targets where
69            // usize has a lesser alignment."
70            const _ALIGNMENT_COMPATIBLE: () =
71                assert!(align_of::<AtomicUsize>() % align_of::<usize>() == 0);
72            p.cast::<usize>()
73        }
74
75        // TODO(MSRV-1.70): Use `AtomicUsize::as_ptr().cast_const()`
76        // See https://github.com/rust-lang/rust/issues/138246.
77        let p = as_const_ptr(&self.inner);
78
79        // SAFETY: The caller is responsible for ensuring that the value
80        // was initialized and that the contents have been acquired by
81        // this thread. Assuming that, we can assume there will be no
82        // conflicting writes to the value since the value will never
83        // change once initialized. This relies on the statement in
84        // https://doc.rust-lang.org/1.83.0/core/sync/atomic/ that "(A
85        // `compare_exchange` or `compare_exchange_weak` that does not
86        // succeed is not considered a write."
87        let val = unsafe { p.read() };
88
89        // SAFETY: The caller is responsible for ensuring the value is
90        // initialized and thus not zero.
91        unsafe { NonZeroUsize::new_unchecked(val) }
92    }
93
94    /// Sets the contents of this cell to `value`.
95    ///
96    /// Returns `Ok(())` if the cell was empty and `Err(())` if it was
97    /// full.
98    #[inline]
99    pub fn set(&self, value: NonZeroUsize) -> Result<(), ()> {
100        let exchange =
101            self.inner.compare_exchange(0, value.get(), Ordering::AcqRel, Ordering::Acquire);
102        match exchange {
103            Ok(_) => Ok(()),
104            Err(_) => Err(()),
105        }
106    }
107
108    /// Gets the contents of the cell, initializing it with `f` if the cell was
109    /// empty.
110    ///
111    /// If several threads concurrently run `get_or_init`, more than one `f` can
112    /// be called. However, all threads will return the same value, produced by
113    /// some `f`.
114    pub fn get_or_init<F>(&self, f: F) -> NonZeroUsize
115    where
116        F: FnOnce() -> NonZeroUsize,
117    {
118        enum Void {}
119        match self.get_or_try_init(|| Ok::<NonZeroUsize, Void>(f())) {
120            Ok(val) => val,
121            Err(void) => match void {},
122        }
123    }
124
125    /// Gets the contents of the cell, initializing it with `f` if
126    /// the cell was empty. If the cell was empty and `f` failed, an
127    /// error is returned.
128    ///
129    /// If several threads concurrently run `get_or_init`, more than one `f` can
130    /// be called. However, all threads will return the same value, produced by
131    /// some `f`.
132    pub fn get_or_try_init<F, E>(&self, f: F) -> Result<NonZeroUsize, E>
133    where
134        F: FnOnce() -> Result<NonZeroUsize, E>,
135    {
136        let val = self.inner.load(Ordering::Acquire);
137        match NonZeroUsize::new(val) {
138            Some(it) => Ok(it),
139            None => self.init(f),
140        }
141    }
142
143    #[cold]
144    #[inline(never)]
145    fn init<E>(&self, f: impl FnOnce() -> Result<NonZeroUsize, E>) -> Result<NonZeroUsize, E> {
146        let mut val = f()?.get();
147        let exchange = self.inner.compare_exchange(0, val, Ordering::AcqRel, Ordering::Acquire);
148        if let Err(old) = exchange {
149            val = old;
150        }
151        Ok(unsafe { NonZeroUsize::new_unchecked(val) })
152    }
153}
154
155/// A thread-safe cell which can be written to only once.
156#[derive(Default, Debug)]
157pub struct OnceBool {
158    inner: OnceNonZeroUsize,
159}
160
161impl OnceBool {
162    /// Creates a new empty cell.
163    #[inline]
164    pub const fn new() -> OnceBool {
165        OnceBool { inner: OnceNonZeroUsize::new() }
166    }
167
168    /// Gets the underlying value.
169    #[inline]
170    pub fn get(&self) -> Option<bool> {
171        self.inner.get().map(OnceBool::from_usize)
172    }
173
174    /// Sets the contents of this cell to `value`.
175    ///
176    /// Returns `Ok(())` if the cell was empty and `Err(())` if it was
177    /// full.
178    #[inline]
179    pub fn set(&self, value: bool) -> Result<(), ()> {
180        self.inner.set(OnceBool::to_usize(value))
181    }
182
183    /// Gets the contents of the cell, initializing it with `f` if the cell was
184    /// empty.
185    ///
186    /// If several threads concurrently run `get_or_init`, more than one `f` can
187    /// be called. However, all threads will return the same value, produced by
188    /// some `f`.
189    pub fn get_or_init<F>(&self, f: F) -> bool
190    where
191        F: FnOnce() -> bool,
192    {
193        OnceBool::from_usize(self.inner.get_or_init(|| OnceBool::to_usize(f())))
194    }
195
196    /// Gets the contents of the cell, initializing it with `f` if
197    /// the cell was empty. If the cell was empty and `f` failed, an
198    /// error is returned.
199    ///
200    /// If several threads concurrently run `get_or_init`, more than one `f` can
201    /// be called. However, all threads will return the same value, produced by
202    /// some `f`.
203    pub fn get_or_try_init<F, E>(&self, f: F) -> Result<bool, E>
204    where
205        F: FnOnce() -> Result<bool, E>,
206    {
207        self.inner.get_or_try_init(|| f().map(OnceBool::to_usize)).map(OnceBool::from_usize)
208    }
209
210    #[inline]
211    fn from_usize(value: NonZeroUsize) -> bool {
212        value.get() == 1
213    }
214
215    #[inline]
216    fn to_usize(value: bool) -> NonZeroUsize {
217        unsafe { NonZeroUsize::new_unchecked(if value { 1 } else { 2 }) }
218    }
219}
220
221/// A thread-safe cell which can be written to only once.
222pub struct OnceRef<'a, T> {
223    inner: AtomicPtr<T>,
224    ghost: PhantomData<UnsafeCell<&'a T>>,
225}
226
227// TODO: Replace UnsafeCell with SyncUnsafeCell once stabilized
228unsafe impl<'a, T: Sync> Sync for OnceRef<'a, T> {}
229
230impl<'a, T> core::fmt::Debug for OnceRef<'a, T> {
231    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
232        write!(f, "OnceRef({:?})", self.inner)
233    }
234}
235
236impl<'a, T> Default for OnceRef<'a, T> {
237    fn default() -> Self {
238        Self::new()
239    }
240}
241
242impl<'a, T> OnceRef<'a, T> {
243    /// Creates a new empty cell.
244    pub const fn new() -> OnceRef<'a, T> {
245        OnceRef { inner: AtomicPtr::new(ptr::null_mut()), ghost: PhantomData }
246    }
247
248    /// Gets a reference to the underlying value.
249    pub fn get(&self) -> Option<&'a T> {
250        let ptr = self.inner.load(Ordering::Acquire);
251        unsafe { ptr.as_ref() }
252    }
253
254    /// Sets the contents of this cell to `value`.
255    ///
256    /// Returns `Ok(())` if the cell was empty and `Err(value)` if it was
257    /// full.
258    pub fn set(&self, value: &'a T) -> Result<(), ()> {
259        let ptr = value as *const T as *mut T;
260        let exchange =
261            self.inner.compare_exchange(ptr::null_mut(), ptr, Ordering::AcqRel, Ordering::Acquire);
262        match exchange {
263            Ok(_) => Ok(()),
264            Err(_) => Err(()),
265        }
266    }
267
268    /// Gets the contents of the cell, initializing it with `f` if the cell was
269    /// empty.
270    ///
271    /// If several threads concurrently run `get_or_init`, more than one `f` can
272    /// be called. However, all threads will return the same value, produced by
273    /// some `f`.
274    pub fn get_or_init<F>(&self, f: F) -> &'a T
275    where
276        F: FnOnce() -> &'a T,
277    {
278        enum Void {}
279        match self.get_or_try_init(|| Ok::<&'a T, Void>(f())) {
280            Ok(val) => val,
281            Err(void) => match void {},
282        }
283    }
284
285    /// Gets the contents of the cell, initializing it with `f` if
286    /// the cell was empty. If the cell was empty and `f` failed, an
287    /// error is returned.
288    ///
289    /// If several threads concurrently run `get_or_init`, more than one `f` can
290    /// be called. However, all threads will return the same value, produced by
291    /// some `f`.
292    pub fn get_or_try_init<F, E>(&self, f: F) -> Result<&'a T, E>
293    where
294        F: FnOnce() -> Result<&'a T, E>,
295    {
296        let mut ptr = self.inner.load(Ordering::Acquire);
297
298        if ptr.is_null() {
299            // TODO replace with `cast_mut` when MSRV reaches 1.65.0 (also in `set`)
300            ptr = f()? as *const T as *mut T;
301            let exchange = self.inner.compare_exchange(
302                ptr::null_mut(),
303                ptr,
304                Ordering::AcqRel,
305                Ordering::Acquire,
306            );
307            if let Err(old) = exchange {
308                ptr = old;
309            }
310        }
311
312        Ok(unsafe { &*ptr })
313    }
314
315    /// ```compile_fail
316    /// use once_cell::race::OnceRef;
317    ///
318    /// let mut l = OnceRef::new();
319    ///
320    /// {
321    ///     let y = 2;
322    ///     let mut r = OnceRef::new();
323    ///     r.set(&y).unwrap();
324    ///     core::mem::swap(&mut l, &mut r);
325    /// }
326    ///
327    /// // l now contains a dangling reference to y
328    /// eprintln!("uaf: {}", l.get().unwrap());
329    /// ```
330    fn _dummy() {}
331}
332
333#[cfg(feature = "alloc")]
334pub use self::once_box::OnceBox;
335
336#[cfg(feature = "alloc")]
337mod once_box {
338    use super::atomic::{AtomicPtr, Ordering};
339    use core::{marker::PhantomData, ptr};
340
341    use alloc::boxed::Box;
342
343    /// A thread-safe cell which can be written to only once.
344    pub struct OnceBox<T> {
345        inner: AtomicPtr<T>,
346        ghost: PhantomData<Option<Box<T>>>,
347    }
348
349    impl<T> core::fmt::Debug for OnceBox<T> {
350        fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
351            write!(f, "OnceBox({:?})", self.inner.load(Ordering::Relaxed))
352        }
353    }
354
355    impl<T> Default for OnceBox<T> {
356        fn default() -> Self {
357            Self::new()
358        }
359    }
360
361    impl<T> Drop for OnceBox<T> {
362        fn drop(&mut self) {
363            let ptr = *self.inner.get_mut();
364            if !ptr.is_null() {
365                drop(unsafe { Box::from_raw(ptr) })
366            }
367        }
368    }
369
370    impl<T> OnceBox<T> {
371        /// Creates a new empty cell.
372        pub const fn new() -> OnceBox<T> {
373            OnceBox { inner: AtomicPtr::new(ptr::null_mut()), ghost: PhantomData }
374        }
375
376        /// Creates a new cell with the given value.
377        pub fn with_value(value: Box<T>) -> Self {
378            OnceBox { inner: AtomicPtr::new(Box::into_raw(value)), ghost: PhantomData }
379        }
380
381        /// Gets a reference to the underlying value.
382        pub fn get(&self) -> Option<&T> {
383            let ptr = self.inner.load(Ordering::Acquire);
384            if ptr.is_null() {
385                return None;
386            }
387            Some(unsafe { &*ptr })
388        }
389
390        /// Sets the contents of this cell to `value`.
391        ///
392        /// Returns `Ok(())` if the cell was empty and `Err(value)` if it was
393        /// full.
394        pub fn set(&self, value: Box<T>) -> Result<(), Box<T>> {
395            let ptr = Box::into_raw(value);
396            let exchange = self.inner.compare_exchange(
397                ptr::null_mut(),
398                ptr,
399                Ordering::AcqRel,
400                Ordering::Acquire,
401            );
402            if exchange.is_err() {
403                let value = unsafe { Box::from_raw(ptr) };
404                return Err(value);
405            }
406            Ok(())
407        }
408
409        /// Gets the contents of the cell, initializing it with `f` if the cell was
410        /// empty.
411        ///
412        /// If several threads concurrently run `get_or_init`, more than one `f` can
413        /// be called. However, all threads will return the same value, produced by
414        /// some `f`.
415        pub fn get_or_init<F>(&self, f: F) -> &T
416        where
417            F: FnOnce() -> Box<T>,
418        {
419            enum Void {}
420            match self.get_or_try_init(|| Ok::<Box<T>, Void>(f())) {
421                Ok(val) => val,
422                Err(void) => match void {},
423            }
424        }
425
426        /// Gets the contents of the cell, initializing it with `f` if
427        /// the cell was empty. If the cell was empty and `f` failed, an
428        /// error is returned.
429        ///
430        /// If several threads concurrently run `get_or_init`, more than one `f` can
431        /// be called. However, all threads will return the same value, produced by
432        /// some `f`.
433        pub fn get_or_try_init<F, E>(&self, f: F) -> Result<&T, E>
434        where
435            F: FnOnce() -> Result<Box<T>, E>,
436        {
437            let mut ptr = self.inner.load(Ordering::Acquire);
438
439            if ptr.is_null() {
440                let val = f()?;
441                ptr = Box::into_raw(val);
442                let exchange = self.inner.compare_exchange(
443                    ptr::null_mut(),
444                    ptr,
445                    Ordering::AcqRel,
446                    Ordering::Acquire,
447                );
448                if let Err(old) = exchange {
449                    drop(unsafe { Box::from_raw(ptr) });
450                    ptr = old;
451                }
452            };
453            Ok(unsafe { &*ptr })
454        }
455    }
456
457    unsafe impl<T: Sync + Send> Sync for OnceBox<T> {}
458
459    impl<T: Clone> Clone for OnceBox<T> {
460        fn clone(&self) -> Self {
461            match self.get() {
462                Some(value) => OnceBox::with_value(Box::new(value.clone())),
463                None => OnceBox::new(),
464            }
465        }
466    }
467
468    /// ```compile_fail
469    /// struct S(*mut ());
470    /// unsafe impl Sync for S {}
471    ///
472    /// fn share<T: Sync>(_: &T) {}
473    /// share(&once_cell::race::OnceBox::<S>::new());
474    /// ```
475    fn _dummy() {}
476}