double_checked_cell_async/
lib.rs

1// Copyright 2017-2018 Niklas Fiekas <niklas.fiekas@backscattering.de>
2//
3// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
4// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
5// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
6// option. This file may not be copied, modified, or distributed
7// except according to those terms.
8
9//! A thread-safe lazily initialized cell using double-checked locking.
10//!
11//! Provides a memory location that can be safely shared between threads and
12//! initialized at most once. Once the cell is initialized it becomes
13//! immutable.
14//!
15//! You can only initialize a `DoubleCheckedCell<T>` once, but then it is
16//! more efficient than a `Mutex<Option<T>>`.
17//!
18//! # Examples
19//!
20//! ```
21//! # #[tokio::main]
22//! # async fn main() -> Result<(), Box<dyn std::error::Error>> {
23//! use double_checked_cell::DoubleCheckedCell;
24//! use futures::future::ready;
25//!
26//! let cell = DoubleCheckedCell::new();
27//!
28//! // The cell starts uninitialized.
29//! assert_eq!(cell.get().await, None);
30//!
31//! // Perform potentially expensive initialization.
32//! let value = cell.get_or_init(async { 21 + 21 }).await;
33//! assert_eq!(*value, 42);
34//! assert_eq!(cell.get().await, Some(&42));
35//!
36//! // The cell is already initialized.
37//! let value = cell.get_or_init(async { unreachable!() }).await;
38//! assert_eq!(*value, 42);
39//! assert_eq!(cell.get().await, Some(&42));
40//! # Ok(())
41//! # }
42//! ```
43//!
44//! # Errors
45//!
46//! `DoubleCheckedCell` supports fallible initialization.
47//!
48//! ```
49//! # #[tokio::main]
50//! # async fn main() -> Result<(), Box<dyn std::error::Error>> {
51//! use tokio::fs::File;
52//! use tokio::prelude::*;
53//! use double_checked_cell::DoubleCheckedCell;
54//!
55//! let cell = DoubleCheckedCell::new();
56//!
57//! let contents: Result<_, tokio::io::Error> = cell.get_or_try_init(async {
58//!     let mut file = File::open("not-found.txt").await?;
59//!     let mut contents = String::new();
60//!     file.read_to_string(&mut contents).await?;
61//!     Ok(contents)
62//! }).await;
63//!
64//! // File not found.
65//! assert!(contents.is_err());
66//!
67//! // Cell remains uninitialized for now.
68//! assert_eq!(cell.get().await, None);
69//! # Ok(())
70//! # }
71//! ```
72//!
73//! # Unwind safety
74//!
75//! If an initialization closure panics, the `DoubleCheckedCell` remains
76//! uninitialized, however the `catch_unwind` future combinator currently can't be
77//! applied to the futures returned from `get_or_init` and `get_or_try_init`.
78
79#![doc(html_root_url = "https://docs.rs/async-double-checked-cell/0.1.0")]
80#![warn(missing_debug_implementations)]
81
82use std::cell::UnsafeCell;
83use std::future::Future;
84use std::panic::RefUnwindSafe;
85use std::sync::atomic::{AtomicBool, Ordering};
86
87use futures_util::future::ready;
88use futures_util::FutureExt;
89use futures_util::lock::Mutex;
90use unreachable::UncheckedOptionExt;
91use void::ResultVoidExt;
92
93/// A thread-safe lazily initialized cell.
94///
95/// The cell is immutable once it is initialized.
96/// See the [module-level documentation](index.html) for more.
97#[derive(Debug)]
98pub struct DoubleCheckedCell<T> {
99    value: UnsafeCell<Option<T>>,
100    initialized: AtomicBool,
101    lock: Mutex<()>,
102}
103
104impl<T> Default for DoubleCheckedCell<T> {
105    fn default() -> DoubleCheckedCell<T> {
106        DoubleCheckedCell::new()
107    }
108}
109
110impl<T> DoubleCheckedCell<T> {
111    /// Creates a new uninitialized `DoubleCheckedCell`.
112    ///
113    /// # Examples
114    ///
115    /// ```
116    /// # #[tokio::main]
117    /// # async fn main() -> Result<(), Box<dyn std::error::Error>> {
118    /// use double_checked_cell::DoubleCheckedCell;
119    ///
120    /// let cell = DoubleCheckedCell::<u32>::new();
121    /// assert_eq!(cell.get().await, None);
122    /// # Ok(())
123    /// # }
124    /// ```
125    pub fn new() -> DoubleCheckedCell<T> {
126        DoubleCheckedCell {
127            value: UnsafeCell::new(None),
128            initialized: AtomicBool::new(false),
129            lock: Mutex::new(()),
130        }
131    }
132
133    /// Borrows the value if the cell is initialized.
134    ///
135    /// # Examples
136    ///
137    /// ```
138    /// # #[tokio::main]
139    /// # async fn main() -> Result<(), Box<dyn std::error::Error>> {
140    /// use double_checked_cell::DoubleCheckedCell;
141    ///
142    /// let cell = DoubleCheckedCell::from("hello");
143    /// assert_eq!(cell.get().await, Some(&"hello"));
144    /// # Ok(())
145    /// # }
146    /// ```
147    pub async fn get(&self) -> Option<&T> {
148        self.get_or_try_init(ready(Err(()))).await.ok()
149    }
150
151    /// Borrows the value if the cell is initialized or initializes it from
152    /// a closure.
153    ///
154    /// # Panics
155    ///
156    /// Panics or deadlocks when trying to access the cell from the
157    /// initilization closure.
158    ///
159    ///
160    /// # Examples
161    ///
162    /// ```
163    /// # #[tokio::main]
164    /// # async fn main() -> Result<(), Box<dyn std::error::Error>> {
165    /// use double_checked_cell::DoubleCheckedCell;
166    /// use futures::future::ready;
167    ///
168    /// let cell = DoubleCheckedCell::new();
169    ///
170    /// // Initialize the cell.
171    /// let value = cell.get_or_init(async { 1 + 2 }).await;
172    /// assert_eq!(*value, 3);
173    ///
174    /// // The cell is now immutable.
175    /// let value = cell.get_or_init(async { 42 }).await;
176    /// assert_eq!(*value, 3);
177    /// # Ok(())
178    /// # }
179    /// ```
180    pub async fn get_or_init<Fut>(&self, init: Fut) -> &T
181    where
182        Fut: Future<Output = T>
183    {
184        self.get_or_try_init(init.map(Ok)).await.void_unwrap()
185    }
186
187    /// Borrows the value if the cell is initialized or attempts to initialize
188    /// it from a closure.
189    ///
190    /// # Errors
191    ///
192    /// Forwards any error from the closure if the cell is not yet initialized.
193    /// The cell then remains uninitialized.
194    ///
195    /// # Panics
196    ///
197    /// Panics or deadlocks when trying to access the cell from the
198    /// initilization closure.
199    ///
200    /// # Examples
201    ///
202    /// ```
203    /// # #[tokio::main]
204    /// # async fn main() -> Result<(), Box<dyn std::error::Error>> {
205    /// use double_checked_cell::DoubleCheckedCell;
206    /// use futures::future::ready;
207    ///
208    /// let cell = DoubleCheckedCell::new();
209    ///
210    /// let result = cell.get_or_try_init(async { "not an integer".parse() }).await;
211    /// assert!(result.is_err());
212    ///
213    /// let result = cell.get_or_try_init(async { "42".parse() }).await;
214    /// assert_eq!(result, Ok(&42));
215    ///
216    /// let result = cell.get_or_try_init(async { "irrelevant".parse() }).await;
217    /// assert_eq!(result, Ok(&42));
218    /// # Ok(())
219    /// # }
220    /// ```
221    pub async fn get_or_try_init<Fut, E>(&self, init: Fut) -> Result<&T, E>
222    where
223        Fut: Future<Output = Result<T, E>>
224    {
225        // Safety comes down to the double checked locking here. All other
226        // borrowing methods are implemented by calling this.
227
228        if !self.initialized.load(Ordering::Acquire) {
229            // Lock the internal mutex.
230            let _lock = self.lock.lock().await;
231
232            if !self.initialized.load(Ordering::Relaxed) {
233                // We claim that it is safe to make a mutable reference to
234                // `self.value` because no other references exist. The only
235                // places that could have taken another reference are
236                // (A) and (B).
237                //
238                // We will be the only one holding a mutable reference, because
239                // we are holding a mutex. The mutex guard lives longer
240                // than the reference taken at (A).
241                //
242                // No thread could have reached (B) yet, because that implies
243                // the cell is already initialized. When we last checked the
244                // cell was not yet initialized, and no one else could have
245                // initialized it, because that requires holding the mutex.
246                {
247                    let result = init.await?;
248
249                    // Consider all possible control flows:
250                    // - init returns Ok(T)
251                    // - init returns Err(E)
252                    // - init recursively tries to initialize the cell
253                    // - init panics
254                    let value = unsafe { &mut *self.value.get() }; // (A)
255                    value.replace(result);
256                }
257
258                self.initialized.store(true, Ordering::Release);
259            }
260        }
261
262        // The cell is now guaranteed to be initialized.
263
264        // We claim that it is safe to take a shared reference of `self.value`.
265        // The only place that could have created a conflicting mutable
266        // reference is (A). But no one can be in that scope while the cell
267        // is already initialized.
268        let value = unsafe { &*self.value.get() }; // (B)
269
270        // Value is guaranteed to be initialized.
271        Ok(unsafe { value.as_ref().unchecked_unwrap() })
272    }
273
274    /// Unwraps the value.
275    ///
276    /// # Examples
277    ///
278    /// ```
279    /// # #[tokio::main]
280    /// # async fn main() -> Result<(), Box<dyn std::error::Error>> {
281    /// use double_checked_cell::DoubleCheckedCell;
282    ///
283    /// let cell = DoubleCheckedCell::from(42);
284    /// let contents = cell.into_inner();
285    /// assert_eq!(contents, Some(42));
286    /// # Ok(())
287    /// # }
288    /// ```
289    pub fn into_inner(self) -> Option<T> {
290        // into_inner() is actually unconditionally safe:
291        // https://github.com/rust-lang/rust/issues/35067
292        #[allow(unused_unsafe)]
293        unsafe { self.value.into_inner() }
294    }
295}
296
297impl<T> From<T> for DoubleCheckedCell<T> {
298    fn from(t: T) -> DoubleCheckedCell<T> {
299        DoubleCheckedCell {
300            value: UnsafeCell::new(Some(t)),
301            initialized: AtomicBool::new(true),
302            lock: Mutex::new(()),
303        }
304    }
305}
306
307// Can DoubleCheckedCell<T> be Sync?
308//
309// The internal state of the DoubleCheckedCell is only mutated while holding
310// a mutex, so we only need to consider T.
311//
312// We need T: Send, because we can share a DoubleCheckedCell with another
313// thread, initialize it there and unpack it on the original thread.
314// We trivially need T: Sync, because a reference to the contents can be
315// retrieved on multiple threads.
316unsafe impl<T: Send + Sync> Sync for DoubleCheckedCell<T> {}
317
318// A panic during initialization will leave the cell in a valid, uninitialized
319// state.
320impl<T> RefUnwindSafe for DoubleCheckedCell<T> {}
321
322#[cfg(test)]
323mod tests {
324    use std::rc::Rc;
325    use std::sync::Arc;
326    use std::sync::atomic::AtomicUsize;
327
328    use futures_util::future::join_all;
329
330    use super::*;
331
332    #[tokio::test]
333    async fn test_drop() {
334        let rc = Rc::new(true);
335        assert_eq!(Rc::strong_count(&rc), 1);
336
337        {
338            let cell = DoubleCheckedCell::new();
339            cell.get_or_init(ready(rc.clone())).await;
340
341            assert_eq!(Rc::strong_count(&rc), 2);
342        }
343
344        assert_eq!(Rc::strong_count(&rc), 1);
345    }
346
347    #[tokio::test(threaded_scheduler)]
348    async fn test_threading() {
349        let n = Arc::new(AtomicUsize::new(0));
350        let cell = Arc::new(DoubleCheckedCell::new());
351
352        let join_handles = (0..1000).map(|_| {
353            let n = n.clone();
354            let cell = cell.clone();
355            tokio::task::spawn(async move {
356                let value = cell.get_or_init(async {
357                    n.fetch_add(1, Ordering::Relaxed);
358                    true
359                }).await;
360
361                assert!(*value);
362            })
363        }).collect::<Vec<_>>();
364        join_all(join_handles).await;
365
366        assert_eq!(n.load(Ordering::SeqCst), 1);
367    }
368
369    #[test]
370    fn test_sync_send() {
371        fn assert_sync<T: Sync>(_: T) {}
372        fn assert_send<T: Send>(_: T) {}
373
374        assert_sync(DoubleCheckedCell::<usize>::new());
375        assert_send(DoubleCheckedCell::<usize>::new());
376        let cell = DoubleCheckedCell::<usize>::new();
377        assert_send(cell.get_or_init(async { 1 }));
378    }
379
380    struct _AssertObjectSafe(Box<DoubleCheckedCell<usize>>);
381}