Line data Source code
1 : use std::sync::{
2 : atomic::{AtomicUsize, Ordering},
3 : Arc, Mutex, MutexGuard,
4 : };
5 : use tokio::sync::Semaphore;
6 :
7 : /// Custom design like [`tokio::sync::OnceCell`] but using [`OwnedSemaphorePermit`] instead of
8 : /// `SemaphorePermit`, allowing use of `take` which does not require holding an outer mutex guard
9 : /// for the duration of initialization.
10 : ///
11 : /// Has no unsafe, builds upon [`tokio::sync::Semaphore`] and [`std::sync::Mutex`].
12 : ///
13 : /// [`OwnedSemaphorePermit`]: tokio::sync::OwnedSemaphorePermit
14 : pub struct OnceCell<T> {
15 : inner: Mutex<Inner<T>>,
16 : initializers: AtomicUsize,
17 : }
18 :
19 : impl<T> Default for OnceCell<T> {
20 : /// Create new uninitialized [`OnceCell`].
21 24 : fn default() -> Self {
22 24 : Self {
23 24 : inner: Default::default(),
24 24 : initializers: AtomicUsize::new(0),
25 24 : }
26 24 : }
27 : }
28 :
29 : /// Semaphore is the current state:
30 : /// - open semaphore means the value is `None`, not yet initialized
31 : /// - closed semaphore means the value has been initialized
32 : #[derive(Debug)]
33 : struct Inner<T> {
34 : init_semaphore: Arc<Semaphore>,
35 : value: Option<T>,
36 : }
37 :
38 : impl<T> Default for Inner<T> {
39 1833 : fn default() -> Self {
40 1833 : Self {
41 1833 : init_semaphore: Arc::new(Semaphore::new(1)),
42 1833 : value: None,
43 1833 : }
44 1833 : }
45 : }
46 :
47 : impl<T> OnceCell<T> {
48 : /// Creates an already initialized `OnceCell` with the given value.
49 5174 : pub fn new(value: T) -> Self {
50 5174 : let sem = Semaphore::new(1);
51 5174 : sem.close();
52 5174 : Self {
53 5174 : inner: Mutex::new(Inner {
54 5174 : init_semaphore: Arc::new(sem),
55 5174 : value: Some(value),
56 5174 : }),
57 5174 : initializers: AtomicUsize::new(0),
58 5174 : }
59 5174 : }
60 :
61 : /// Returns a guard to an existing initialized value, or uniquely initializes the value before
62 : /// returning the guard.
63 : ///
64 : /// Initializing might wait on any existing [`Guard::take_and_deinit`] deinitialization.
65 : ///
66 : /// Initialization is panic-safe and cancellation-safe.
67 119 : pub async fn get_or_init<F, Fut, E>(&self, factory: F) -> Result<Guard<'_, T>, E>
68 119 : where
69 119 : F: FnOnce(InitPermit) -> Fut,
70 119 : Fut: std::future::Future<Output = Result<(T, InitPermit), E>>,
71 119 : {
72 : loop {
73 20 : let sem = {
74 120 : let guard = self.inner.lock().unwrap();
75 120 : if guard.value.is_some() {
76 100 : return Ok(Guard(guard));
77 20 : }
78 20 : guard.init_semaphore.clone()
79 : };
80 :
81 : {
82 19 : let permit = {
83 : // increment the count for the duration of queued
84 20 : let _guard = CountWaitingInitializers::start(self);
85 20 : sem.acquire().await
86 : };
87 :
88 19 : let Ok(permit) = permit else {
89 1 : let guard = self.inner.lock().unwrap();
90 1 : if !Arc::ptr_eq(&sem, &guard.init_semaphore) {
91 : // there was a take_and_deinit in between
92 1 : continue;
93 0 : }
94 0 : assert!(
95 0 : guard.value.is_some(),
96 0 : "semaphore got closed, must be initialized"
97 : );
98 0 : return Ok(Guard(guard));
99 : };
100 :
101 18 : permit.forget();
102 18 : }
103 18 :
104 18 : let permit = InitPermit(sem);
105 18 : let (value, _permit) = factory(permit).await?;
106 :
107 7 : let guard = self.inner.lock().unwrap();
108 7 :
109 7 : return Ok(Self::set0(value, guard));
110 : }
111 117 : }
112 :
113 : /// Returns a guard to an existing initialized value, or returns an unique initialization
114 : /// permit which can be used to initialize this `OnceCell` using `OnceCell::set`.
115 640424 : pub async fn get_or_init_detached(&self) -> Result<Guard<'_, T>, InitPermit> {
116 : // It looks like OnceCell::get_or_init could be implemented using this method instead of
117 : // duplication. However, that makes the future be !Send due to possibly holding on to the
118 : // MutexGuard over an await point.
119 : loop {
120 55 : let sem = {
121 640424 : let guard = self.inner.lock().unwrap();
122 640424 : if guard.value.is_some() {
123 640369 : return Ok(Guard(guard));
124 55 : }
125 55 : guard.init_semaphore.clone()
126 : };
127 :
128 : {
129 55 : let permit = {
130 : // increment the count for the duration of queued
131 55 : let _guard = CountWaitingInitializers::start(self);
132 55 : sem.acquire().await
133 : };
134 :
135 55 : let Ok(permit) = permit else {
136 0 : let guard = self.inner.lock().unwrap();
137 0 : if !Arc::ptr_eq(&sem, &guard.init_semaphore) {
138 : // there was a take_and_deinit in between
139 0 : continue;
140 0 : }
141 0 : assert!(
142 0 : guard.value.is_some(),
143 0 : "semaphore got closed, must be initialized"
144 : );
145 0 : return Ok(Guard(guard));
146 : };
147 :
148 55 : permit.forget();
149 55 : }
150 55 :
151 55 : let permit = InitPermit(sem);
152 55 : return Err(permit);
153 : }
154 640424 : }
155 :
156 : /// Assuming a permit is held after previous call to [`Guard::take_and_deinit`], it can be used
157 : /// to complete initializing the inner value.
158 : ///
159 : /// # Panics
160 : ///
161 : /// If the inner has already been initialized.
162 64 : pub fn set(&self, value: T, _permit: InitPermit) -> Guard<'_, T> {
163 64 : let guard = self.inner.lock().unwrap();
164 64 :
165 64 : // cannot assert that this permit is for self.inner.semaphore, but we can assert it cannot
166 64 : // give more permits right now.
167 64 : if guard.init_semaphore.try_acquire().is_ok() {
168 0 : drop(guard);
169 0 : panic!("permit is of wrong origin");
170 64 : }
171 64 :
172 64 : Self::set0(value, guard)
173 64 : }
174 :
175 71 : fn set0(value: T, mut guard: std::sync::MutexGuard<'_, Inner<T>>) -> Guard<'_, T> {
176 71 : if guard.value.is_some() {
177 0 : drop(guard);
178 0 : unreachable!("we won permit, must not be initialized");
179 71 : }
180 71 : guard.value = Some(value);
181 71 : guard.init_semaphore.close();
182 71 : Guard(guard)
183 71 : }
184 :
185 : /// Returns a guard to an existing initialized value, if any.
186 332 : pub fn get(&self) -> Option<Guard<'_, T>> {
187 332 : let guard = self.inner.lock().unwrap();
188 332 : if guard.value.is_some() {
189 294 : Some(Guard(guard))
190 : } else {
191 38 : None
192 : }
193 332 : }
194 :
195 : /// Like [`Guard::take_and_deinit`], but will return `None` if this OnceCell was never
196 : /// initialized.
197 1728 : pub fn take_and_deinit(&mut self) -> Option<(T, InitPermit)> {
198 1728 : let inner = self.inner.get_mut().unwrap();
199 1728 :
200 1728 : inner.take_and_deinit()
201 1728 : }
202 :
203 : /// Return the number of [`Self::get_or_init`] calls waiting for initialization to complete.
204 90 : pub fn initializer_count(&self) -> usize {
205 90 : self.initializers.load(Ordering::Relaxed)
206 90 : }
207 : }
208 :
209 : /// DropGuard counter for queued tasks waiting to initialize, mainly accessible for the
210 : /// initializing task for example at the end of initialization.
211 : struct CountWaitingInitializers<'a, T>(&'a OnceCell<T>);
212 :
213 : impl<'a, T> CountWaitingInitializers<'a, T> {
214 75 : fn start(target: &'a OnceCell<T>) -> Self {
215 75 : target.initializers.fetch_add(1, Ordering::Relaxed);
216 75 : CountWaitingInitializers(target)
217 75 : }
218 : }
219 :
220 : impl<'a, T> Drop for CountWaitingInitializers<'a, T> {
221 75 : fn drop(&mut self) {
222 75 : self.0.initializers.fetch_sub(1, Ordering::Relaxed);
223 75 : }
224 : }
225 :
226 : /// Uninteresting guard object to allow short-lived access to inspect or clone the held,
227 : /// initialized value.
228 : #[derive(Debug)]
229 : pub struct Guard<'a, T>(MutexGuard<'a, Inner<T>>);
230 :
231 : impl<T> std::ops::Deref for Guard<'_, T> {
232 : type Target = T;
233 :
234 363 : fn deref(&self) -> &Self::Target {
235 363 : self.0
236 363 : .value
237 363 : .as_ref()
238 363 : .expect("guard is not created unless value has been initialized")
239 363 : }
240 : }
241 :
242 : impl<T> std::ops::DerefMut for Guard<'_, T> {
243 640399 : fn deref_mut(&mut self) -> &mut Self::Target {
244 640399 : self.0
245 640399 : .value
246 640399 : .as_mut()
247 640399 : .expect("guard is not created unless value has been initialized")
248 640399 : }
249 : }
250 :
251 : impl<'a, T> Guard<'a, T> {
252 : /// Take the current value, and a new permit for it's deinitialization.
253 : ///
254 : /// The permit will be on a semaphore part of the new internal value, and any following
255 : /// [`OnceCell::get_or_init`] will wait on it to complete.
256 89 : pub fn take_and_deinit(mut self) -> (T, InitPermit) {
257 89 : self.0
258 89 : .take_and_deinit()
259 89 : .expect("guard is not created unless value has been initialized")
260 89 : }
261 : }
262 :
263 : impl<T> Inner<T> {
264 1817 : pub fn take_and_deinit(&mut self) -> Option<(T, InitPermit)> {
265 1817 : let value = self.value.take()?;
266 :
267 1809 : let mut swapped = Inner::default();
268 1809 : let sem = swapped.init_semaphore.clone();
269 1809 : // acquire and forget right away, moving the control over to InitPermit
270 1809 : sem.try_acquire().expect("we just created this").forget();
271 1809 : let permit = InitPermit(sem);
272 1809 : std::mem::swap(self, &mut swapped);
273 1809 : Some((value, permit))
274 1817 : }
275 : }
276 :
277 : /// Type held by OnceCell (de)initializing task.
278 : ///
279 : /// On drop, this type will return the permit.
280 : pub struct InitPermit(Arc<tokio::sync::Semaphore>);
281 :
282 : impl std::fmt::Debug for InitPermit {
283 0 : fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
284 0 : let ptr = Arc::as_ptr(&self.0) as *const ();
285 0 : f.debug_tuple("InitPermit").field(&ptr).finish()
286 0 : }
287 : }
288 :
289 : impl Drop for InitPermit {
290 1882 : fn drop(&mut self) {
291 1882 : assert_eq!(
292 1882 : self.0.available_permits(),
293 : 0,
294 0 : "InitPermit should only exist as the unique permit"
295 : );
296 1882 : self.0.add_permits(1);
297 1882 : }
298 : }
299 :
300 : #[cfg(test)]
301 : mod tests {
302 : use futures::Future;
303 :
304 : use super::*;
305 : use std::{
306 : convert::Infallible,
307 : pin::{pin, Pin},
308 : time::Duration,
309 : };
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 1 : .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 1 : .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 4 : cell.get_or_init(factory).await.unwrap();
475 2 : })
476 2 : })
477 4 : .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 :
517 : // drive t2 first to the init_semaphore -- the timeout will be hit once t2 future can
518 : // no longer make progress
519 : tokio::select! {
520 : _ = &mut t2 => unreachable!("it cannot get permit"),
521 : _ = tokio::time::sleep(Duration::from_secs(3600 * 24 * 7 * 365)) => {}
522 : }
523 :
524 : // followed by t1 in the init_semaphore
525 : tokio::select! {
526 : _ = &mut t1 => unreachable!("it cannot get permit"),
527 : _ = tokio::time::sleep(Duration::from_secs(3600 * 24 * 7 * 365)) => {}
528 : }
529 :
530 : // 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 : tokio::select! {
540 : _ = &mut t1 => unreachable!("it cannot get permit"),
541 : _ = tokio::time::sleep(Duration::from_secs(3600 * 24 * 7 * 365)) => {}
542 : }
543 :
544 : // 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 : }
|
