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}