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 18 : fn default() -> Self {
22 18 : Self {
23 18 : inner: Default::default(),
24 18 : initializers: AtomicUsize::new(0),
25 18 : }
26 18 : }
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 526 : fn default() -> Self {
40 526 : Self {
41 526 : init_semaphore: Arc::new(Semaphore::new(1)),
42 526 : value: None,
43 526 : }
44 526 : }
45 : }
46 :
47 : impl<T> OnceCell<T> {
48 : /// Creates an already initialized `OnceCell` with the given value.
49 1574 : pub fn new(value: T) -> Self {
50 1574 : let sem = Semaphore::new(1);
51 1574 : sem.close();
52 1574 : Self {
53 1574 : inner: Mutex::new(Inner {
54 1574 : init_semaphore: Arc::new(sem),
55 1574 : value: Some(value),
56 1574 : }),
57 1574 : initializers: AtomicUsize::new(0),
58 1574 : }
59 1574 : }
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 238 : pub async fn get_or_init<F, Fut, E>(&self, factory: F) -> Result<Guard<'_, T>, E>
68 238 : where
69 238 : F: FnOnce(InitPermit) -> Fut,
70 238 : Fut: std::future::Future<Output = Result<(T, InitPermit), E>>,
71 238 : {
72 : loop {
73 40 : let sem = {
74 240 : let guard = self.inner.lock().unwrap();
75 240 : if guard.value.is_some() {
76 200 : return Ok(Guard(guard));
77 40 : }
78 40 : guard.init_semaphore.clone()
79 : };
80 :
81 : {
82 38 : let permit = {
83 : // increment the count for the duration of queued
84 40 : let _guard = CountWaitingInitializers::start(self);
85 40 : sem.acquire().await
86 : };
87 :
88 38 : let Ok(permit) = permit else {
89 2 : let guard = self.inner.lock().unwrap();
90 2 : if !Arc::ptr_eq(&sem, &guard.init_semaphore) {
91 : // there was a take_and_deinit in between
92 2 : 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 36 : permit.forget();
102 36 : }
103 36 :
104 36 : let permit = InitPermit(sem);
105 36 : let (value, _permit) = factory(permit).await?;
106 :
107 14 : let guard = self.inner.lock().unwrap();
108 14 :
109 14 : return Ok(Self::set0(value, guard));
110 : }
111 234 : }
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 212091 : 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 20 : let sem = {
121 212091 : let guard = self.inner.lock().unwrap();
122 212091 : if guard.value.is_some() {
123 212071 : return Ok(Guard(guard));
124 20 : }
125 20 : guard.init_semaphore.clone()
126 : };
127 :
128 : {
129 20 : let permit = {
130 : // increment the count for the duration of queued
131 20 : let _guard = CountWaitingInitializers::start(self);
132 20 : sem.acquire().await
133 : };
134 :
135 20 : 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 20 : permit.forget();
149 20 : }
150 20 :
151 20 : let permit = InitPermit(sem);
152 20 : return Err(permit);
153 : }
154 212091 : }
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 28 : pub fn set(&self, value: T, _permit: InitPermit) -> Guard<'_, T> {
163 28 : let guard = self.inner.lock().unwrap();
164 28 :
165 28 : // cannot assert that this permit is for self.inner.semaphore, but we can assert it cannot
166 28 : // give more permits right now.
167 28 : if guard.init_semaphore.try_acquire().is_ok() {
168 0 : drop(guard);
169 0 : panic!("permit is of wrong origin");
170 28 : }
171 28 :
172 28 : Self::set0(value, guard)
173 28 : }
174 :
175 42 : fn set0(value: T, mut guard: std::sync::MutexGuard<'_, Inner<T>>) -> Guard<'_, T> {
176 42 : if guard.value.is_some() {
177 0 : drop(guard);
178 0 : unreachable!("we won permit, must not be initialized");
179 42 : }
180 42 : guard.value = Some(value);
181 42 : guard.init_semaphore.close();
182 42 : Guard(guard)
183 42 : }
184 :
185 : /// Returns a guard to an existing initialized value, if any.
186 120 : pub fn get(&self) -> Option<Guard<'_, T>> {
187 120 : let guard = self.inner.lock().unwrap();
188 120 : if guard.value.is_some() {
189 104 : Some(Guard(guard))
190 : } else {
191 16 : None
192 : }
193 120 : }
194 :
195 : /// Like [`Guard::take_and_deinit`], but will return `None` if this OnceCell was never
196 : /// initialized.
197 476 : pub fn take_and_deinit(&mut self) -> Option<(T, InitPermit)> {
198 476 : let inner = self.inner.get_mut().unwrap();
199 476 :
200 476 : inner.take_and_deinit()
201 476 : }
202 :
203 : /// Return the number of [`Self::get_or_init`] calls waiting for initialization to complete.
204 30 : pub fn initializer_count(&self) -> usize {
205 30 : self.initializers.load(Ordering::Relaxed)
206 30 : }
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 60 : fn start(target: &'a OnceCell<T>) -> Self {
215 60 : target.initializers.fetch_add(1, Ordering::Relaxed);
216 60 : CountWaitingInitializers(target)
217 60 : }
218 : }
219 :
220 : impl<'a, T> Drop for CountWaitingInitializers<'a, T> {
221 60 : fn drop(&mut self) {
222 60 : self.0.initializers.fetch_sub(1, Ordering::Relaxed);
223 60 : }
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 292 : fn deref(&self) -> &Self::Target {
235 292 : self.0
236 292 : .value
237 292 : .as_ref()
238 292 : .expect("guard is not created unless value has been initialized")
239 292 : }
240 : }
241 :
242 : impl<T> std::ops::DerefMut for Guard<'_, T> {
243 212081 : fn deref_mut(&mut self) -> &mut Self::Target {
244 212081 : self.0
245 212081 : .value
246 212081 : .as_mut()
247 212081 : .expect("guard is not created unless value has been initialized")
248 212081 : }
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 38 : pub fn take_and_deinit(mut self) -> (T, InitPermit) {
257 38 : self.0
258 38 : .take_and_deinit()
259 38 : .expect("guard is not created unless value has been initialized")
260 38 : }
261 : }
262 :
263 : impl<T> Inner<T> {
264 514 : pub fn take_and_deinit(&mut self) -> Option<(T, InitPermit)> {
265 514 : let value = self.value.take()?;
266 :
267 508 : let mut swapped = Inner::default();
268 508 : let sem = swapped.init_semaphore.clone();
269 508 : // acquire and forget right away, moving the control over to InitPermit
270 508 : sem.try_acquire().expect("we just created this").forget();
271 508 : let permit = InitPermit(sem);
272 508 : std::mem::swap(self, &mut swapped);
273 508 : Some((value, permit))
274 514 : }
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 564 : fn drop(&mut self) {
291 564 : assert_eq!(
292 564 : self.0.available_permits(),
293 : 0,
294 0 : "InitPermit should only exist as the unique permit"
295 : );
296 564 : self.0.add_permits(1);
297 564 : }
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 2 : async fn many_initializers() {
313 2 : #[derive(Default, Debug)]
314 2 : struct Counters {
315 2 : factory_got_to_run: AtomicUsize,
316 2 : future_polled: AtomicUsize,
317 2 : winners: AtomicUsize,
318 2 : }
319 2 :
320 2 : let initializers = 100;
321 2 :
322 2 : let cell = Arc::new(OnceCell::default());
323 2 : let counters = Arc::new(Counters::default());
324 2 : let barrier = Arc::new(tokio::sync::Barrier::new(initializers + 1));
325 2 :
326 2 : let mut js = tokio::task::JoinSet::new();
327 200 : for i in 0..initializers {
328 200 : js.spawn({
329 200 : let cell = cell.clone();
330 200 : let counters = counters.clone();
331 200 : let barrier = barrier.clone();
332 200 :
333 200 : async move {
334 200 : barrier.wait().await;
335 200 : let won = {
336 200 : let g = cell
337 200 : .get_or_init(|permit| {
338 2 : counters.factory_got_to_run.fetch_add(1, Ordering::Relaxed);
339 2 : async {
340 2 : counters.future_polled.fetch_add(1, Ordering::Relaxed);
341 2 : Ok::<_, Infallible>((i, permit))
342 2 : }
343 200 : })
344 2 : .await
345 200 : .unwrap();
346 200 :
347 200 : *g == i
348 200 : };
349 200 :
350 200 : if won {
351 2 : counters.winners.fetch_add(1, Ordering::Relaxed);
352 198 : }
353 200 : }
354 200 : });
355 200 : }
356 2 :
357 2 : barrier.wait().await;
358 2 :
359 202 : while let Some(next) = js.join_next().await {
360 200 : next.expect("no panics expected");
361 200 : }
362 2 :
363 2 : let mut counters = Arc::try_unwrap(counters).unwrap();
364 2 :
365 2 : assert_eq!(*counters.factory_got_to_run.get_mut(), 1);
366 2 : assert_eq!(*counters.future_polled.get_mut(), 1);
367 2 : assert_eq!(*counters.winners.get_mut(), 1);
368 2 : }
369 :
370 : #[tokio::test(start_paused = true)]
371 2 : async fn reinit_waits_for_deinit() {
372 2 : // with the tokio::time paused, we will "sleep" for 1s while holding the reinitialization
373 2 : let sleep_for = Duration::from_secs(1);
374 2 : let initial = 42;
375 2 : let reinit = 1;
376 2 : let cell = Arc::new(OnceCell::new(initial));
377 2 :
378 2 : let deinitialization_started = Arc::new(tokio::sync::Barrier::new(2));
379 2 :
380 2 : let jh = tokio::spawn({
381 2 : let cell = cell.clone();
382 2 : let deinitialization_started = deinitialization_started.clone();
383 2 : async move {
384 2 : let (answer, _permit) = cell.get().expect("initialized to value").take_and_deinit();
385 2 : assert_eq!(answer, initial);
386 2 :
387 2 : deinitialization_started.wait().await;
388 2 : tokio::time::sleep(sleep_for).await;
389 2 : }
390 2 : });
391 2 :
392 2 : deinitialization_started.wait().await;
393 2 :
394 2 : let started_at = tokio::time::Instant::now();
395 2 : cell.get_or_init(|permit| async { Ok::<_, Infallible>((reinit, permit)) })
396 2 : .await
397 2 : .unwrap();
398 2 :
399 2 : let elapsed = started_at.elapsed();
400 2 : assert!(
401 2 : elapsed >= sleep_for,
402 2 : "initialization should had taken at least the time time slept with permit"
403 2 : );
404 2 :
405 2 : jh.await.unwrap();
406 2 :
407 2 : assert_eq!(*cell.get().unwrap(), reinit);
408 2 : }
409 :
410 : #[test]
411 2 : fn reinit_with_deinit_permit() {
412 2 : let cell = Arc::new(OnceCell::new(42));
413 2 :
414 2 : let (mol, permit) = cell.get().unwrap().take_and_deinit();
415 2 : cell.set(5, permit);
416 2 : assert_eq!(*cell.get().unwrap(), 5);
417 :
418 2 : let (five, permit) = cell.get().unwrap().take_and_deinit();
419 2 : assert_eq!(5, five);
420 2 : cell.set(mol, permit);
421 2 : assert_eq!(*cell.get().unwrap(), 42);
422 2 : }
423 :
424 : #[tokio::test]
425 2 : async fn initialization_attemptable_until_ok() {
426 2 : let cell = OnceCell::default();
427 2 :
428 22 : for _ in 0..10 {
429 20 : cell.get_or_init(|_permit| async { Err("whatever error") })
430 2 : .await
431 20 : .unwrap_err();
432 2 : }
433 2 :
434 2 : let g = cell
435 2 : .get_or_init(|permit| async { Ok::<_, Infallible>(("finally success", permit)) })
436 2 : .await
437 2 : .unwrap();
438 2 : assert_eq!(*g, "finally success");
439 2 : }
440 :
441 : #[tokio::test]
442 2 : async fn initialization_is_cancellation_safe() {
443 2 : let cell = OnceCell::default();
444 2 :
445 2 : let barrier = tokio::sync::Barrier::new(2);
446 2 :
447 2 : let initializer = cell.get_or_init(|permit| async {
448 2 : barrier.wait().await;
449 2 : futures::future::pending::<()>().await;
450 2 :
451 2 : Ok::<_, Infallible>(("never reached", permit))
452 2 : });
453 2 :
454 2 : tokio::select! {
455 2 : _ = initializer => { unreachable!("cannot complete; stuck in pending().await") },
456 2 : _ = barrier.wait() => {}
457 2 : };
458 2 :
459 2 : // now initializer is dropped
460 2 :
461 2 : assert!(cell.get().is_none());
462 2 :
463 2 : let g = cell
464 2 : .get_or_init(|permit| async { Ok::<_, Infallible>(("now initialized", permit)) })
465 2 : .await
466 2 : .unwrap();
467 2 : assert_eq!(*g, "now initialized");
468 2 : }
469 :
470 : #[tokio::test(start_paused = true)]
471 2 : async fn reproduce_init_take_deinit_race() {
472 4 : init_take_deinit_scenario(|cell, factory| {
473 4 : Box::pin(async {
474 13 : cell.get_or_init(factory).await.unwrap();
475 4 : })
476 4 : })
477 8 : .await;
478 2 : }
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 2 : async fn init_take_deinit_scenario<F>(init_way: F)
488 2 : where
489 2 : F: for<'a> Fn(
490 2 : &'a OnceCell<&'static str>,
491 2 : BoxedInitFunction<&'static str, Infallible>,
492 2 : ) -> Pin<Box<dyn Future<Output = ()> + 'a>>,
493 2 : {
494 2 : let cell = OnceCell::default();
495 2 :
496 2 : // acquire the init_semaphore only permit to drive initializing tasks in order to waiting
497 2 : // on the same semaphore.
498 2 : let permit = cell
499 2 : .inner
500 2 : .lock()
501 2 : .unwrap()
502 2 : .init_semaphore
503 2 : .clone()
504 2 : .try_acquire_owned()
505 2 : .unwrap();
506 2 :
507 2 : let mut t1 = pin!(init_way(
508 2 : &cell,
509 2 : Box::new(|permit| Box::pin(async move { Ok(("t1", permit)) })),
510 2 : ));
511 2 :
512 2 : let mut t2 = pin!(init_way(
513 2 : &cell,
514 2 : Box::new(|permit| Box::pin(async move { Ok(("t2", permit)) })),
515 2 : ));
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 2 : drop(permit);
532 2 : t2.await;
533 :
534 2 : let (s, permit) = { cell.get().unwrap().take_and_deinit() };
535 2 : 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 2 : drop(permit);
546 2 : t1.await;
547 :
548 2 : assert_eq!("t1", *cell.get().unwrap());
549 2 : }
550 :
551 : #[tokio::test(start_paused = true)]
552 2 : async fn detached_init_smoke() {
553 2 : let target = OnceCell::default();
554 2 :
555 2 : let Err(permit) = target.get_or_init_detached().await else {
556 2 : unreachable!("it is not initialized")
557 2 : };
558 2 :
559 2 : tokio::time::timeout(
560 2 : std::time::Duration::from_secs(3600 * 24 * 7 * 365),
561 2 : target.get_or_init(|permit2| async { Ok::<_, Infallible>((11, permit2)) }),
562 2 : )
563 2 : .await
564 2 : .expect_err("should timeout since we are already holding the permit");
565 2 :
566 2 : target.set(42, permit);
567 2 :
568 2 : let (_answer, permit) = {
569 2 : let guard = target
570 2 : .get_or_init(|permit| async { Ok::<_, Infallible>((11, permit)) })
571 2 : .await
572 2 : .unwrap();
573 2 :
574 2 : assert_eq!(*guard, 42);
575 2 :
576 2 : guard.take_and_deinit()
577 2 : };
578 2 :
579 2 : assert!(target.get().is_none());
580 2 :
581 2 : target.set(11, permit);
582 2 :
583 2 : assert_eq!(*target.get().unwrap(), 11);
584 2 : }
585 :
586 : #[tokio::test]
587 2 : async fn take_and_deinit_on_mut() {
588 2 : use std::convert::Infallible;
589 2 :
590 2 : let mut target = OnceCell::<u32>::default();
591 2 : assert!(target.take_and_deinit().is_none());
592 2 :
593 2 : target
594 2 : .get_or_init(|permit| async move { Ok::<_, Infallible>((42, permit)) })
595 2 : .await
596 2 : .unwrap();
597 2 :
598 2 : let again = target.take_and_deinit();
599 2 : assert!(matches!(again, Some((42, _))), "{again:?}");
600 2 :
601 2 : assert!(target.take_and_deinit().is_none());
602 2 : }
603 : }
|
