Skip to main content

karyon_core/async_util/
condvar.rs

1use std::{
2    collections::HashMap,
3    future::Future,
4    pin::Pin,
5    task::{Context, Poll, Waker},
6};
7
8use parking_lot::Mutex;
9
10use crate::async_runtime::lock::MutexGuard;
11
12/// Id of a task waiting on a CondVar.
13type WaiterId = u64;
14
15/// CondVar is an async version of <https://doc.rust-lang.org/std/sync/struct.Condvar.html>
16///
17/// # Example
18///
19///```
20/// use std::sync::Arc;
21///
22/// use karyon_core::async_util::CondVar;
23/// use karyon_core::async_runtime::{spawn, lock::Mutex};
24///
25///  async {
26///     
27///     let val = Arc::new(Mutex::new(false));
28///     let condvar = Arc::new(CondVar::new());
29///
30///     spawn({
31///         let val = val.clone();
32///         let condvar = condvar.clone();
33///         async move {
34///             let mut val = val.lock().await;
35///
36///             // While the boolean flag is false, wait for a signal.
37///             while !*val {
38///                 val = condvar.wait(val).await;
39///             }
40///
41///             // ...
42///         }
43///     });
44///
45///     spawn({
46///         let condvar = condvar.clone();
47///         async move {
48///             let mut val = val.lock().await;
49///
50///             // While the boolean flag is false, wait for a signal.
51///             while !*val {
52///                 val = condvar.wait(val).await;
53///             }
54///
55///             // ...
56///         }
57///     });
58///     
59///     // Wake up all waiting tasks on this condvar
60///     condvar.broadcast();
61///  };
62///
63/// ```
64pub struct CondVar {
65    inner: Mutex<Wakers>,
66}
67
68impl CondVar {
69    /// Creates a new CondVar
70    pub fn new() -> Self {
71        Self {
72            inner: Mutex::new(Wakers::new()),
73        }
74    }
75
76    /// Blocks the current task until this condition variable receives a notification.
77    pub async fn wait<'a, T>(&self, g: MutexGuard<'a, T>) -> MutexGuard<'a, T> {
78        #[cfg(feature = "smol")]
79        let m = MutexGuard::source(&g);
80        #[cfg(feature = "tokio")]
81        let m = MutexGuard::mutex(&g);
82
83        CondVarAwait::new(self, g).await;
84
85        m.lock().await
86    }
87
88    /// Wakes up one blocked task waiting on this condvar.
89    pub fn signal(&self) {
90        self.inner.lock().wake(true);
91    }
92
93    /// Wakes up all blocked tasks waiting on this condvar.
94    pub fn broadcast(&self) {
95        self.inner.lock().wake(false);
96    }
97}
98
99impl Default for CondVar {
100    fn default() -> Self {
101        Self::new()
102    }
103}
104
105/// Future returned by `CondVar::wait`, resolves once the task is signaled.
106struct CondVarAwait<'a, T> {
107    /// Waiter id, set while the task is in the waker list.
108    id: Option<WaiterId>,
109    condvar: &'a CondVar,
110    /// Held until the first poll, then released.
111    guard: Option<MutexGuard<'a, T>>,
112}
113
114impl<'a, T> CondVarAwait<'a, T> {
115    fn new(condvar: &'a CondVar, guard: MutexGuard<'a, T>) -> Self {
116        Self {
117            condvar,
118            guard: Some(guard),
119            id: None,
120        }
121    }
122}
123
124impl<T> Future for CondVarAwait<'_, T> {
125    type Output = ();
126
127    fn poll(mut self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
128        let mut inner = self.condvar.inner.lock();
129
130        match self.guard.take() {
131            Some(_) => {
132                // The first poll registers the waker and releases the
133                // MutexGuard.
134                self.id = Some(inner.put(Some(cx.waker().clone())));
135                Poll::Pending
136            }
137            None => {
138                // Return Ready if it has already been polled and removed
139                // from the waker list.
140                if self.id.is_none() {
141                    return Poll::Ready(());
142                }
143
144                let i = self.id.as_ref().unwrap();
145                let waker_op = match inner.wakers.get_mut(i) {
146                    Some(wk) => wk,
147                    None => {
148                        self.id = None;
149                        return Poll::Ready(());
150                    }
151                };
152
153                // `None` means the waker was taken by signal or broadcast.
154                match waker_op {
155                    Some(wk) => {
156                        // This will prevent cloning again
157                        if !wk.will_wake(cx.waker()) {
158                            wk.clone_from(cx.waker());
159                        }
160                        Poll::Pending
161                    }
162                    None => {
163                        inner.delete(i);
164                        self.id = None;
165                        Poll::Ready(())
166                    }
167                }
168            }
169        }
170    }
171}
172
173impl<T> Drop for CondVarAwait<'_, T> {
174    fn drop(&mut self) {
175        if let Some(id) = self.id {
176            let mut inner = self.condvar.inner.lock();
177            // Already signaled but cancelled before waking up, so pass the
178            // signal on to another waiter.
179            if let Some(None) = inner.wakers.remove(&id) {
180                inner.wake(true);
181            }
182        }
183    }
184}
185
186/// Wakers is a helper struct to store the task wakers
187struct Wakers {
188    /// Waiting tasks. `None` means signaled but not woken up yet.
189    wakers: HashMap<WaiterId, Option<Waker>>,
190    /// Next waiter id, only grows so ids never collide.
191    next_id: WaiterId,
192}
193
194impl Wakers {
195    fn new() -> Self {
196        Self {
197            wakers: HashMap::new(),
198            next_id: 0,
199        }
200    }
201
202    /// Adds a waker and returns its id.
203    /// Called with the CondVar lock held, so ids are never handed out twice.
204    /// A u64 does not overflow in practice.
205    fn put(&mut self, waker: Option<Waker>) -> WaiterId {
206        let id = self.next_id;
207        self.next_id += 1;
208        self.wakers.insert(id, waker);
209        id
210    }
211
212    fn delete(&mut self, id: &WaiterId) -> Option<Option<Waker>> {
213        self.wakers.remove(id)
214    }
215
216    /// Wakes one waiter if `signal` is true, otherwise all of them.
217    /// Waiters already signaled are skipped.
218    fn wake(&mut self, signal: bool) {
219        for wk in self.wakers.values_mut() {
220            match wk.take() {
221                Some(w) => {
222                    w.wake();
223                    if signal {
224                        break;
225                    }
226                }
227                None => continue,
228            }
229        }
230    }
231}
232
233#[cfg(test)]
234mod tests {
235    use std::{
236        collections::VecDeque,
237        sync::{
238            Arc,
239            atomic::{AtomicBool, AtomicUsize, Ordering},
240        },
241        task::Wake,
242    };
243
244    use crate::async_runtime::{block_on, lock::Mutex, spawn};
245
246    use super::*;
247
248    // The tests below demonstrate a solution to a problem in the Wikipedia
249    // explanation of condition variables:
250    // https://en.wikipedia.org/wiki/Monitor_(synchronization)#Solving_the_bounded_producer/consumer_problem.
251
252    struct Flag(AtomicBool);
253
254    impl Wake for Flag {
255        fn wake(self: Arc<Self>) {
256            self.0.store(true, Ordering::Relaxed);
257        }
258    }
259
260    struct Queue {
261        items: VecDeque<String>,
262        max_len: usize,
263    }
264    impl Queue {
265        fn new(max_len: usize) -> Self {
266            Self {
267                items: VecDeque::new(),
268                max_len,
269            }
270        }
271
272        fn is_full(&self) -> bool {
273            self.items.len() == self.max_len
274        }
275
276        fn is_empty(&self) -> bool {
277            self.items.is_empty()
278        }
279    }
280
281    #[test]
282    fn test_condvar_signal() {
283        block_on(async {
284            let number_of_tasks = 30;
285
286            let queue = Arc::new(Mutex::new(Queue::new(5)));
287            let condvar_full = Arc::new(CondVar::new());
288            let condvar_empty = Arc::new(CondVar::new());
289
290            let _producer1 = spawn({
291                let queue = queue.clone();
292                let condvar_full = condvar_full.clone();
293                let condvar_empty = condvar_empty.clone();
294                async move {
295                    for i in 1..number_of_tasks {
296                        // Lock queue mtuex
297                        let mut queue = queue.lock().await;
298
299                        // Check if the queue is non-full
300                        while queue.is_full() {
301                            // Release queue mutex and sleep
302                            queue = condvar_full.wait(queue).await;
303                        }
304
305                        queue.items.push_back(format!("task {i}"));
306
307                        // Wake up the consumer
308                        condvar_empty.signal();
309                    }
310                }
311            });
312
313            let task_consumed = Arc::new(AtomicUsize::new(0));
314
315            let consumer = spawn({
316                let queue = queue.clone();
317                let task_consumed = task_consumed.clone();
318                async move {
319                    for _ in 1..number_of_tasks {
320                        // Lock queue mtuex
321                        let mut queue = queue.lock().await;
322
323                        // Check if the queue is non-empty
324                        while queue.is_empty() {
325                            // Release queue mutex and sleep
326                            queue = condvar_empty.wait(queue).await;
327                        }
328
329                        let _ = queue.items.pop_front().unwrap();
330
331                        task_consumed.fetch_add(1, Ordering::Relaxed);
332
333                        // Do something
334
335                        // Wake up the producer
336                        condvar_full.signal();
337                    }
338                }
339            });
340
341            let _ = consumer.await;
342            assert!(queue.lock().await.is_empty());
343            assert_eq!(task_consumed.load(Ordering::Relaxed), 29);
344        });
345    }
346
347    #[test]
348    fn test_condvar_broadcast() {
349        block_on(async {
350            let tasks = 30;
351
352            let queue = Arc::new(Mutex::new(Queue::new(5)));
353            let condvar = Arc::new(CondVar::new());
354
355            let _producer1 = spawn({
356                let queue = queue.clone();
357                let condvar = condvar.clone();
358                async move {
359                    for i in 1..tasks {
360                        // Lock queue mtuex
361                        let mut queue = queue.lock().await;
362
363                        // Check if the queue is non-full
364                        while queue.is_full() {
365                            // Release queue mutex and sleep
366                            queue = condvar.wait(queue).await;
367                        }
368
369                        queue.items.push_back(format!("producer1: task {i}"));
370
371                        // Wake up all producer and consumer tasks
372                        condvar.broadcast();
373                    }
374                }
375            });
376
377            let _producer2 = spawn({
378                let queue = queue.clone();
379                let condvar = condvar.clone();
380                async move {
381                    for i in 1..tasks {
382                        // Lock queue mtuex
383                        let mut queue = queue.lock().await;
384
385                        // Check if the queue is non-full
386                        while queue.is_full() {
387                            // Release queue mutex and sleep
388                            queue = condvar.wait(queue).await;
389                        }
390
391                        queue.items.push_back(format!("producer2: task {i}"));
392
393                        // Wake up all producer and consumer tasks
394                        condvar.broadcast();
395                    }
396                }
397            });
398
399            let task_consumed = Arc::new(AtomicUsize::new(0));
400
401            let consumer = spawn({
402                let queue = queue.clone();
403                let task_consumed = task_consumed.clone();
404                async move {
405                    for _ in 1..((tasks * 2) - 1) {
406                        {
407                            // Lock queue mutex
408                            let mut queue = queue.lock().await;
409
410                            // Check if the queue is non-empty
411                            while queue.is_empty() {
412                                // Release queue mutex and sleep
413                                queue = condvar.wait(queue).await;
414                            }
415
416                            let _ = queue.items.pop_front().unwrap();
417
418                            task_consumed.fetch_add(1, Ordering::Relaxed);
419
420                            // Do something
421
422                            // Wake up all producer and consumer tasks
423                            condvar.broadcast();
424                        }
425                    }
426                }
427            });
428
429            let _ = consumer.await;
430            assert!(queue.lock().await.is_empty());
431            assert_eq!(task_consumed.load(Ordering::Relaxed), 58);
432        });
433    }
434
435    #[test]
436    fn test_condvar_drop_signaled_waiter() {
437        block_on(async {
438            let m1 = Mutex::new(());
439            let m2 = Mutex::new(());
440            let condvar = CondVar::new();
441
442            let f1 = Arc::new(Flag(AtomicBool::new(false)));
443            let f2 = Arc::new(Flag(AtomicBool::new(false)));
444            let w1 = Waker::from(f1.clone());
445            let w2 = Waker::from(f2.clone());
446
447            let mut a1 = Box::pin(CondVarAwait::new(&condvar, m1.lock().await));
448            let mut a2 = Box::pin(CondVarAwait::new(&condvar, m2.lock().await));
449            assert!(a1.as_mut().poll(&mut Context::from_waker(&w1)).is_pending());
450            assert!(a2.as_mut().poll(&mut Context::from_waker(&w2)).is_pending());
451
452            // Wake exactly one waiter.
453            condvar.signal();
454            let first = f1.0.load(Ordering::Relaxed);
455            assert_ne!(first, f2.0.load(Ordering::Relaxed));
456
457            // Cancel the chosen waiter, the other one must wake up.
458            if first {
459                drop(a1);
460                assert!(f2.0.load(Ordering::Relaxed));
461                assert!(a2.as_mut().poll(&mut Context::from_waker(&w2)).is_ready());
462            } else {
463                drop(a2);
464                assert!(f1.0.load(Ordering::Relaxed));
465                assert!(a1.as_mut().poll(&mut Context::from_waker(&w1)).is_ready());
466            }
467        });
468    }
469}