Line data Source code
1 : use std::sync::atomic::{AtomicUsize, Ordering};
2 : use std::sync::{Arc, Mutex, MutexGuard};
3 :
4 : use tokio::sync::Semaphore;
5 :
6 : /// Custom design like [`tokio::sync::OnceCell`] but using [`OwnedSemaphorePermit`] instead of
7 : /// `SemaphorePermit`.
8 : ///
9 : /// Allows use of `take` which does not require holding an outer mutex guard
10 : /// for the duration of initialization.
11 : ///
12 : /// Has no unsafe, builds upon [`tokio::sync::Semaphore`] and [`std::sync::Mutex`].
13 : ///
14 : /// [`OwnedSemaphorePermit`]: tokio::sync::OwnedSemaphorePermit
15 : pub struct OnceCell<T> {
16 : inner: Mutex<Inner<T>>,
17 : initializers: AtomicUsize,
18 : }
19 :
20 : impl<T> Default for OnceCell<T> {
21 : /// Create new uninitialized [`OnceCell`].
22 22 : fn default() -> Self {
23 22 : Self {
24 22 : inner: Default::default(),
25 22 : initializers: AtomicUsize::new(0),
26 22 : }
27 22 : }
28 : }
29 :
30 : /// Semaphore is the current state:
31 : /// - open semaphore means the value is `None`, not yet initialized
32 : /// - closed semaphore means the value has been initialized
33 : #[derive(Debug)]
34 : struct Inner<T> {
35 : init_semaphore: Arc<Semaphore>,
36 : value: Option<T>,
37 : }
38 :
39 : impl<T> Default for Inner<T> {
40 1533 : fn default() -> Self {
41 1533 : Self {
42 1533 : init_semaphore: Arc::new(Semaphore::new(1)),
43 1533 : value: None,
44 1533 : }
45 1533 : }
46 : }
47 :
48 : impl<T> OnceCell<T> {
49 : /// Creates an already initialized `OnceCell` with the given value.
50 3862 : pub fn new(value: T) -> Self {
51 3862 : let sem = Semaphore::new(1);
52 3862 : sem.close();
53 3862 : Self {
54 3862 : inner: Mutex::new(Inner {
55 3862 : init_semaphore: Arc::new(sem),
56 3862 : value: Some(value),
57 3862 : }),
58 3862 : initializers: AtomicUsize::new(0),
59 3862 : }
60 3862 : }
61 :
62 : /// Returns a guard to an existing initialized value, or uniquely initializes the value before
63 : /// returning the guard.
64 : ///
65 : /// Initializing might wait on any existing [`Guard::take_and_deinit`] deinitialization.
66 : ///
67 : /// Initialization is panic-safe and cancellation-safe.
68 119 : pub async fn get_or_init<F, Fut, E>(&self, factory: F) -> Result<Guard<'_, T>, E>
69 119 : where
70 119 : F: FnOnce(InitPermit) -> Fut,
71 119 : Fut: std::future::Future<Output = Result<(T, InitPermit), E>>,
72 119 : {
73 : loop {
74 20 : let sem = {
75 120 : let guard = self.inner.lock().unwrap();
76 120 : if guard.value.is_some() {
77 100 : return Ok(Guard(guard));
78 20 : }
79 20 : guard.init_semaphore.clone()
80 : };
81 :
82 : {
83 19 : let permit = {
84 : // increment the count for the duration of queued
85 20 : let _guard = CountWaitingInitializers::start(self);
86 20 : sem.acquire().await
87 : };
88 :
89 19 : let Ok(permit) = permit else {
90 1 : let guard = self.inner.lock().unwrap();
91 1 : if !Arc::ptr_eq(&sem, &guard.init_semaphore) {
92 : // there was a take_and_deinit in between
93 1 : continue;
94 0 : }
95 0 : assert!(
96 0 : guard.value.is_some(),
97 0 : "semaphore got closed, must be initialized"
98 : );
99 0 : return Ok(Guard(guard));
100 : };
101 :
102 18 : permit.forget();
103 18 : }
104 18 :
105 18 : let permit = InitPermit(sem);
106 18 : let (value, _permit) = factory(permit).await?;
107 :
108 7 : let guard = self.inner.lock().unwrap();
109 7 :
110 7 : return Ok(Self::set0(value, guard));
111 : }
112 117 : }
113 :
114 : /// Returns a guard to an existing initialized value, or returns an unique initialization
115 : /// permit which can be used to initialize this `OnceCell` using `OnceCell::set`.
116 480749 : pub async fn get_or_init_detached(&self) -> Result<Guard<'_, T>, InitPermit> {
117 : // It looks like OnceCell::get_or_init could be implemented using this method instead of
118 : // duplication. However, that makes the future be !Send due to possibly holding on to the
119 : // MutexGuard over an await point.
120 : loop {
121 57 : let sem = {
122 480749 : let guard = self.inner.lock().unwrap();
123 480749 : if guard.value.is_some() {
124 480692 : return Ok(Guard(guard));
125 57 : }
126 57 : guard.init_semaphore.clone()
127 : };
128 :
129 : {
130 57 : let permit = {
131 : // increment the count for the duration of queued
132 57 : let _guard = CountWaitingInitializers::start(self);
133 57 : sem.acquire().await
134 : };
135 :
136 57 : let Ok(permit) = permit else {
137 0 : let guard = self.inner.lock().unwrap();
138 0 : if !Arc::ptr_eq(&sem, &guard.init_semaphore) {
139 : // there was a take_and_deinit in between
140 0 : continue;
141 0 : }
142 0 : assert!(
143 0 : guard.value.is_some(),
144 0 : "semaphore got closed, must be initialized"
145 : );
146 0 : return Ok(Guard(guard));
147 : };
148 :
149 57 : permit.forget();
150 57 : }
151 57 :
152 57 : let permit = InitPermit(sem);
153 57 : return Err(permit);
154 : }
155 1 : }
156 :
157 : /// Assuming a permit is held after previous call to [`Guard::take_and_deinit`], it can be used
158 : /// to complete initializing the inner value.
159 : ///
160 : /// # Panics
161 : ///
162 : /// If the inner has already been initialized.
163 64 : pub fn set(&self, value: T, _permit: InitPermit) -> Guard<'_, T> {
164 64 : let guard = self.inner.lock().unwrap();
165 64 :
166 64 : // cannot assert that this permit is for self.inner.semaphore, but we can assert it cannot
167 64 : // give more permits right now.
168 64 : if guard.init_semaphore.try_acquire().is_ok() {
169 0 : drop(guard);
170 0 : panic!("permit is of wrong origin");
171 64 : }
172 64 :
173 64 : Self::set0(value, guard)
174 64 : }
175 :
176 71 : fn set0(value: T, mut guard: std::sync::MutexGuard<'_, Inner<T>>) -> Guard<'_, T> {
177 71 : if guard.value.is_some() {
178 0 : drop(guard);
179 0 : unreachable!("we won permit, must not be initialized");
180 71 : }
181 71 : guard.value = Some(value);
182 71 : guard.init_semaphore.close();
183 71 : Guard(guard)
184 71 : }
185 :
186 : /// Returns a guard to an existing initialized value, if any.
187 508 : pub fn get(&self) -> Option<Guard<'_, T>> {
188 508 : let guard = self.inner.lock().unwrap();
189 508 : if guard.value.is_some() {
190 358 : Some(Guard(guard))
191 : } else {
192 150 : None
193 : }
194 11 : }
195 :
196 : /// Like [`Guard::take_and_deinit`], but will return `None` if this OnceCell was never
197 : /// initialized.
198 1424 : pub fn take_and_deinit(&mut self) -> Option<(T, InitPermit)> {
199 1424 : let inner = self.inner.get_mut().unwrap();
200 1424 :
201 1424 : inner.take_and_deinit()
202 1424 : }
203 :
204 : /// Return the number of [`Self::get_or_init`] calls waiting for initialization to complete.
205 108 : pub fn initializer_count(&self) -> usize {
206 108 : self.initializers.load(Ordering::Relaxed)
207 108 : }
208 : }
209 :
210 : /// DropGuard counter for queued tasks waiting to initialize, mainly accessible for the
211 : /// initializing task for example at the end of initialization.
212 : struct CountWaitingInitializers<'a, T>(&'a OnceCell<T>);
213 :
214 : impl<'a, T> CountWaitingInitializers<'a, T> {
215 77 : fn start(target: &'a OnceCell<T>) -> Self {
216 77 : target.initializers.fetch_add(1, Ordering::Relaxed);
217 77 : CountWaitingInitializers(target)
218 77 : }
219 : }
220 :
221 : impl<T> Drop for CountWaitingInitializers<'_, T> {
222 77 : fn drop(&mut self) {
223 77 : self.0.initializers.fetch_sub(1, Ordering::Relaxed);
224 77 : }
225 : }
226 :
227 : /// Uninteresting guard object to allow short-lived access to inspect or clone the held,
228 : /// initialized value.
229 : #[derive(Debug)]
230 : pub struct Guard<'a, T>(MutexGuard<'a, Inner<T>>);
231 :
232 : impl<T> std::ops::Deref for Guard<'_, T> {
233 : type Target = T;
234 :
235 437 : fn deref(&self) -> &Self::Target {
236 437 : self.0
237 437 : .value
238 437 : .as_ref()
239 437 : .expect("guard is not created unless value has been initialized")
240 437 : }
241 : }
242 :
243 : impl<T> std::ops::DerefMut for Guard<'_, T> {
244 480712 : fn deref_mut(&mut self) -> &mut Self::Target {
245 480712 : self.0
246 480712 : .value
247 480712 : .as_mut()
248 480712 : .expect("guard is not created unless value has been initialized")
249 480712 : }
250 : }
251 :
252 : impl<T> Guard<'_, T> {
253 : /// Take the current value, and a new permit for it's deinitialization.
254 : ///
255 : /// The permit will be on a semaphore part of the new internal value, and any following
256 : /// [`OnceCell::get_or_init`] will wait on it to complete.
257 93 : pub fn take_and_deinit(mut self) -> (T, InitPermit) {
258 93 : self.0
259 93 : .take_and_deinit()
260 93 : .expect("guard is not created unless value has been initialized")
261 93 : }
262 : }
263 :
264 : impl<T> Inner<T> {
265 1517 : pub fn take_and_deinit(&mut self) -> Option<(T, InitPermit)> {
266 1517 : let value = self.value.take()?;
267 :
268 1511 : let mut swapped = Inner::default();
269 1511 : let sem = swapped.init_semaphore.clone();
270 1511 : // acquire and forget right away, moving the control over to InitPermit
271 1511 : sem.try_acquire().expect("we just created this").forget();
272 1511 : let permit = InitPermit(sem);
273 1511 : std::mem::swap(self, &mut swapped);
274 1511 : Some((value, permit))
275 8 : }
276 : }
277 :
278 : /// Type held by OnceCell (de)initializing task.
279 : ///
280 : /// On drop, this type will return the permit.
281 : pub struct InitPermit(Arc<tokio::sync::Semaphore>);
282 :
283 : impl std::fmt::Debug for InitPermit {
284 0 : fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
285 0 : let ptr = Arc::as_ptr(&self.0) as *const ();
286 0 : f.debug_tuple("InitPermit").field(&ptr).finish()
287 0 : }
288 : }
289 :
290 : impl Drop for InitPermit {
291 1586 : fn drop(&mut self) {
292 1586 : assert_eq!(
293 1586 : self.0.available_permits(),
294 : 0,
295 0 : "InitPermit should only exist as the unique permit"
296 : );
297 1586 : self.0.add_permits(1);
298 1586 : }
299 : }
300 :
301 : #[cfg(test)]
302 : mod tests {
303 : use std::convert::Infallible;
304 : use std::pin::{Pin, pin};
305 : use std::time::Duration;
306 :
307 : use futures::Future;
308 :
309 : use super::*;
310 :
311 : #[tokio::test]
312 1 : async fn many_initializers() {
313 1 : #[derive(Default, Debug)]
314 1 : struct Counters {
315 1 : factory_got_to_run: AtomicUsize,
316 1 : future_polled: AtomicUsize,
317 1 : winners: AtomicUsize,
318 1 : }
319 1 :
320 1 : let initializers = 100;
321 1 :
322 1 : let cell = Arc::new(OnceCell::default());
323 1 : let counters = Arc::new(Counters::default());
324 1 : let barrier = Arc::new(tokio::sync::Barrier::new(initializers + 1));
325 1 :
326 1 : let mut js = tokio::task::JoinSet::new();
327 100 : for i in 0..initializers {
328 100 : js.spawn({
329 100 : let cell = cell.clone();
330 100 : let counters = counters.clone();
331 100 : let barrier = barrier.clone();
332 100 :
333 100 : async move {
334 100 : barrier.wait().await;
335 100 : let won = {
336 100 : let g = cell
337 100 : .get_or_init(|permit| {
338 1 : counters.factory_got_to_run.fetch_add(1, Ordering::Relaxed);
339 1 : async {
340 1 : counters.future_polled.fetch_add(1, Ordering::Relaxed);
341 1 : Ok::<_, Infallible>((i, permit))
342 1 : }
343 100 : })
344 100 : .await
345 100 : .unwrap();
346 100 :
347 100 : *g == i
348 100 : };
349 100 :
350 100 : if won {
351 1 : counters.winners.fetch_add(1, Ordering::Relaxed);
352 99 : }
353 100 : }
354 100 : });
355 100 : }
356 1 :
357 1 : barrier.wait().await;
358 1 :
359 101 : while let Some(next) = js.join_next().await {
360 100 : next.expect("no panics expected");
361 100 : }
362 1 :
363 1 : let mut counters = Arc::try_unwrap(counters).unwrap();
364 1 :
365 1 : assert_eq!(*counters.factory_got_to_run.get_mut(), 1);
366 1 : assert_eq!(*counters.future_polled.get_mut(), 1);
367 1 : assert_eq!(*counters.winners.get_mut(), 1);
368 1 : }
369 :
370 : #[tokio::test(start_paused = true)]
371 1 : async fn reinit_waits_for_deinit() {
372 1 : // with the tokio::time paused, we will "sleep" for 1s while holding the reinitialization
373 1 : let sleep_for = Duration::from_secs(1);
374 1 : let initial = 42;
375 1 : let reinit = 1;
376 1 : let cell = Arc::new(OnceCell::new(initial));
377 1 :
378 1 : let deinitialization_started = Arc::new(tokio::sync::Barrier::new(2));
379 1 :
380 1 : let jh = tokio::spawn({
381 1 : let cell = cell.clone();
382 1 : let deinitialization_started = deinitialization_started.clone();
383 1 : async move {
384 1 : let (answer, _permit) = cell.get().expect("initialized to value").take_and_deinit();
385 1 : assert_eq!(answer, initial);
386 1 :
387 1 : deinitialization_started.wait().await;
388 1 : tokio::time::sleep(sleep_for).await;
389 1 : }
390 1 : });
391 1 :
392 1 : deinitialization_started.wait().await;
393 1 :
394 1 : let started_at = tokio::time::Instant::now();
395 1 : cell.get_or_init(|permit| async { Ok::<_, Infallible>((reinit, permit)) })
396 1 : .await
397 1 : .unwrap();
398 1 :
399 1 : let elapsed = started_at.elapsed();
400 1 : assert!(
401 1 : elapsed >= sleep_for,
402 1 : "initialization should had taken at least the time time slept with permit"
403 1 : );
404 1 :
405 1 : jh.await.unwrap();
406 1 :
407 1 : assert_eq!(*cell.get().unwrap(), reinit);
408 1 : }
409 :
410 : #[test]
411 1 : fn reinit_with_deinit_permit() {
412 1 : let cell = Arc::new(OnceCell::new(42));
413 1 :
414 1 : let (mol, permit) = cell.get().unwrap().take_and_deinit();
415 1 : cell.set(5, permit);
416 1 : assert_eq!(*cell.get().unwrap(), 5);
417 :
418 1 : let (five, permit) = cell.get().unwrap().take_and_deinit();
419 1 : assert_eq!(5, five);
420 1 : cell.set(mol, permit);
421 1 : assert_eq!(*cell.get().unwrap(), 42);
422 1 : }
423 :
424 : #[tokio::test]
425 1 : async fn initialization_attemptable_until_ok() {
426 1 : let cell = OnceCell::default();
427 1 :
428 11 : for _ in 0..10 {
429 10 : cell.get_or_init(|_permit| async { Err("whatever error") })
430 10 : .await
431 10 : .unwrap_err();
432 1 : }
433 1 :
434 1 : let g = cell
435 1 : .get_or_init(|permit| async { Ok::<_, Infallible>(("finally success", permit)) })
436 1 : .await
437 1 : .unwrap();
438 1 : assert_eq!(*g, "finally success");
439 1 : }
440 :
441 : #[tokio::test]
442 1 : async fn initialization_is_cancellation_safe() {
443 1 : let cell = OnceCell::default();
444 1 :
445 1 : let barrier = tokio::sync::Barrier::new(2);
446 1 :
447 1 : let initializer = cell.get_or_init(|permit| async {
448 1 : barrier.wait().await;
449 1 : futures::future::pending::<()>().await;
450 1 :
451 1 : Ok::<_, Infallible>(("never reached", permit))
452 1 : });
453 1 :
454 1 : tokio::select! {
455 1 : _ = initializer => { unreachable!("cannot complete; stuck in pending().await") },
456 1 : _ = barrier.wait() => {}
457 1 : };
458 1 :
459 1 : // now initializer is dropped
460 1 :
461 1 : assert!(cell.get().is_none());
462 1 :
463 1 : let g = cell
464 1 : .get_or_init(|permit| async { Ok::<_, Infallible>(("now initialized", permit)) })
465 1 : .await
466 1 : .unwrap();
467 1 : assert_eq!(*g, "now initialized");
468 1 : }
469 :
470 : #[tokio::test(start_paused = true)]
471 1 : async fn reproduce_init_take_deinit_race() {
472 2 : init_take_deinit_scenario(|cell, factory| {
473 2 : Box::pin(async {
474 2 : cell.get_or_init(factory).await.unwrap();
475 2 : })
476 2 : })
477 1 : .await;
478 1 : }
479 :
480 : type BoxedInitFuture<T, E> = Pin<Box<dyn Future<Output = Result<(T, InitPermit), E>>>>;
481 : type BoxedInitFunction<T, E> = Box<dyn Fn(InitPermit) -> BoxedInitFuture<T, E>>;
482 :
483 : /// Reproduce an assertion failure.
484 : ///
485 : /// This has interesting generics to be generic between `get_or_init` and `get_mut_or_init`.
486 : /// We currently only have one, but the structure is kept.
487 1 : async fn init_take_deinit_scenario<F>(init_way: F)
488 1 : where
489 1 : F: for<'a> Fn(
490 1 : &'a OnceCell<&'static str>,
491 1 : BoxedInitFunction<&'static str, Infallible>,
492 1 : ) -> Pin<Box<dyn Future<Output = ()> + 'a>>,
493 1 : {
494 1 : let cell = OnceCell::default();
495 1 :
496 1 : // acquire the init_semaphore only permit to drive initializing tasks in order to waiting
497 1 : // on the same semaphore.
498 1 : let permit = cell
499 1 : .inner
500 1 : .lock()
501 1 : .unwrap()
502 1 : .init_semaphore
503 1 : .clone()
504 1 : .try_acquire_owned()
505 1 : .unwrap();
506 1 :
507 1 : let mut t1 = pin!(init_way(
508 1 : &cell,
509 1 : Box::new(|permit| Box::pin(async move { Ok(("t1", permit)) })),
510 1 : ));
511 1 :
512 1 : let mut t2 = pin!(init_way(
513 1 : &cell,
514 1 : Box::new(|permit| Box::pin(async move { Ok(("t2", permit)) })),
515 1 : ));
516 1 :
517 1 : // drive t2 first to the init_semaphore -- the timeout will be hit once t2 future can
518 1 : // no longer make progress
519 1 : tokio::select! {
520 1 : _ = &mut t2 => unreachable!("it cannot get permit"),
521 1 : _ = tokio::time::sleep(Duration::from_secs(3600 * 24 * 7 * 365)) => {}
522 1 : }
523 1 :
524 1 : // followed by t1 in the init_semaphore
525 1 : tokio::select! {
526 1 : _ = &mut t1 => unreachable!("it cannot get permit"),
527 1 : _ = tokio::time::sleep(Duration::from_secs(3600 * 24 * 7 * 365)) => {}
528 1 : }
529 1 :
530 1 : // now let t2 proceed and initialize
531 1 : drop(permit);
532 1 : t2.await;
533 :
534 1 : let (s, permit) = { cell.get().unwrap().take_and_deinit() };
535 1 : assert_eq!("t2", s);
536 :
537 : // now originally t1 would see the semaphore it has as closed. it cannot yet get a permit from
538 : // the new one.
539 1 : tokio::select! {
540 1 : _ = &mut t1 => unreachable!("it cannot get permit"),
541 1 : _ = tokio::time::sleep(Duration::from_secs(3600 * 24 * 7 * 365)) => {}
542 1 : }
543 1 :
544 1 : // only now we get to initialize it
545 1 : drop(permit);
546 1 : t1.await;
547 :
548 1 : assert_eq!("t1", *cell.get().unwrap());
549 1 : }
550 :
551 : #[tokio::test(start_paused = true)]
552 1 : async fn detached_init_smoke() {
553 1 : let target = OnceCell::default();
554 1 :
555 1 : let Err(permit) = target.get_or_init_detached().await else {
556 1 : unreachable!("it is not initialized")
557 1 : };
558 1 :
559 1 : tokio::time::timeout(
560 1 : std::time::Duration::from_secs(3600 * 24 * 7 * 365),
561 1 : target.get_or_init(|permit2| async { Ok::<_, Infallible>((11, permit2)) }),
562 1 : )
563 1 : .await
564 1 : .expect_err("should timeout since we are already holding the permit");
565 1 :
566 1 : target.set(42, permit);
567 1 :
568 1 : let (_answer, permit) = {
569 1 : let guard = target
570 1 : .get_or_init(|permit| async { Ok::<_, Infallible>((11, permit)) })
571 1 : .await
572 1 : .unwrap();
573 1 :
574 1 : assert_eq!(*guard, 42);
575 1 :
576 1 : guard.take_and_deinit()
577 1 : };
578 1 :
579 1 : assert!(target.get().is_none());
580 1 :
581 1 : target.set(11, permit);
582 1 :
583 1 : assert_eq!(*target.get().unwrap(), 11);
584 1 : }
585 :
586 : #[tokio::test]
587 1 : async fn take_and_deinit_on_mut() {
588 1 : use std::convert::Infallible;
589 1 :
590 1 : let mut target = OnceCell::<u32>::default();
591 1 : assert!(target.take_and_deinit().is_none());
592 1 :
593 1 : target
594 1 : .get_or_init(|permit| async move { Ok::<_, Infallible>((42, permit)) })
595 1 : .await
596 1 : .unwrap();
597 1 :
598 1 : let again = target.take_and_deinit();
599 1 : assert!(matches!(again, Some((42, _))), "{again:?}");
600 1 :
601 1 : assert!(target.take_and_deinit().is_none());
602 1 : }
603 : }
|
