Skip to main content

objectstore_service/concurrency/
limiter.rs

1//! Simple and priority-based FIFO concurrency limiters.
2
3use std::collections::BTreeMap;
4use std::future::Future;
5use std::io;
6use std::mem::DropGuard;
7use std::num::NonZeroU32;
8use std::sync::{Arc, Mutex, PoisonError};
9use std::task::Poll;
10use std::time::Duration;
11
12use bytes::Bytes;
13use futures_util::{Stream, stream};
14use tokio::sync::{OwnedSemaphorePermit, Semaphore, oneshot};
15
16use crate::error::{ErrorKind, Result};
17use crate::stream::PayloadStream;
18
19const METRICS_EMITTER_INTERVAL: Duration = Duration::from_secs(1);
20
21/// Owned permit, released on drop.
22#[derive(Debug)]
23pub struct Permit {
24    _inner: PermitInner,
25}
26
27#[derive(Debug)]
28enum PermitInner {
29    Semaphore { _permit: OwnedSemaphorePermit },
30    Priority { _permit: PriorityPermit },
31}
32
33impl Permit {
34    fn semaphore(permit: OwnedSemaphorePermit) -> Self {
35        Self {
36            _inner: PermitInner::Semaphore { _permit: permit },
37        }
38    }
39
40    fn priority(state: Arc<Mutex<PriorityState>>) -> Self {
41        Self {
42            _inner: PermitInner::Priority {
43                _permit: PriorityPermit { state },
44            },
45        }
46    }
47
48    /// Wraps `stream` so that it holds this permit until EOF, the first error, or stream drop.
49    ///
50    /// Returns an unboxed stream; call `.boxed()` if a [`PayloadStream`] is needed.
51    pub fn guard_stream(self, stream: PayloadStream) -> impl Stream<Item = io::Result<Bytes>> {
52        // Tuple field order ensures the stream drops before its permit.
53        let mut guarded = Some((stream, self));
54        stream::poll_fn(move |cx| {
55            let Some((stream, _)) = guarded.as_mut() else {
56                return Poll::Ready(None);
57            };
58            let result = stream.as_mut().poll_next(cx);
59            if matches!(result, Poll::Ready(None | Some(Err(_)))) {
60                guarded.take();
61            }
62            result
63        })
64    }
65}
66
67/// Snapshot of permits in use by a simple limiter.
68#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
69pub struct LimiterStats {
70    /// Permits currently in use.
71    pub in_use: u32,
72}
73
74/// Shared interval loop for the metric emitters.
75async fn run_emitter<S, F, Fut>(mut snapshot: impl FnMut() -> S, mut emit: F) -> !
76where
77    F: FnMut(S) -> Fut,
78    Fut: Future<Output = ()>,
79{
80    let mut ticker = tokio::time::interval(METRICS_EMITTER_INTERVAL);
81    loop {
82        ticker.tick().await;
83        emit(snapshot()).await;
84    }
85}
86
87/// Limits concurrent operations with FIFO queuing and a configurable wait timeout.
88#[derive(Clone, Debug)]
89pub struct Limiter {
90    semaphore: Arc<Semaphore>,
91    queue: Option<Arc<Semaphore>>,
92    capacity: u32,
93    timeout: Duration,
94}
95
96impl Limiter {
97    /// Creates a FIFO limiter with the given capacity, wait timeout, and queue limit.
98    pub fn new(capacity: NonZeroU32, timeout: Duration, max_queue_size: Option<u32>) -> Self {
99        let capacity = capacity.get();
100        Self {
101            semaphore: Arc::new(Semaphore::new(capacity as usize)),
102            queue: max_queue_size.map(|size| Arc::new(Semaphore::new(size as usize))),
103            capacity,
104            timeout,
105        }
106    }
107
108    /// Acquires capacity within the configured timeout, preserving FIFO order.
109    ///
110    /// Returns [`ErrorKind::AtCapacity`] when the queue is full or the wait times out.
111    /// Dropping the future releases its queue slot and any assigned permit.
112    pub async fn acquire(&self) -> Result<Permit> {
113        if let Ok(permit) = self.semaphore.clone().try_acquire_owned() {
114            return Ok(Permit::semaphore(permit));
115        }
116        if self.timeout.is_zero() {
117            return Err(ErrorKind::AtCapacity.into());
118        }
119        let _queued = self
120            .queue
121            .as_ref()
122            .map(|queue| queue.try_acquire())
123            .transpose()
124            .map_err(|_| ErrorKind::AtCapacity)?;
125        let permit = tokio::time::timeout(self.timeout, self.semaphore.clone().acquire_owned())
126            .await
127            .map_err(|_| ErrorKind::AtCapacity)?
128            .map_err(|_| ErrorKind::AtCapacity)?;
129        Ok(Permit::semaphore(permit))
130    }
131
132    /// Returns the current number of permits in use.
133    pub fn stats(&self) -> LimiterStats {
134        LimiterStats {
135            in_use: self.capacity - self.semaphore.available_permits() as u32,
136        }
137    }
138
139    /// Passes this limiter's stats to `emit` immediately and once per second thereafter.
140    pub async fn run_emitter<F, Fut>(&self, emit: F) -> !
141    where
142        F: FnMut(LimiterStats) -> Fut,
143        Fut: Future<Output = ()>,
144    {
145        run_emitter(|| self.stats(), emit).await
146    }
147}
148
149/// Priority for an acquisition from [`PriorityLimiter`].
150#[derive(Clone, Copy, Debug, Eq, PartialEq)]
151pub enum Priority {
152    /// Normal priority.
153    Normal,
154    /// High priority, always served before queued normal-priority acquisitions.
155    High,
156}
157
158/// Snapshot of permits in use and queued acquisitions by priority.
159#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
160pub struct PriorityLimiterStats {
161    /// Permits currently in use.
162    pub in_use: u32,
163    /// Normal-priority acquisitions waiting in the queue.
164    pub waiting_normal: usize,
165    /// High-priority acquisitions waiting in the queue.
166    pub waiting_high: usize,
167}
168
169/// Limits concurrent operations with high-priority admission and FIFO within each priority.
170///
171/// Each priority has its own wait timeout and optional queue limit; execution capacity is shared.
172/// A released permit goes directly to the oldest high-priority waiter, or else to the oldest
173/// normal-priority waiter, so sustained high-priority traffic can starve normal-priority waiters.
174#[derive(Clone, Debug)]
175pub struct PriorityLimiter {
176    normal_timeout: Duration,
177    high_timeout: Option<Duration>,
178    max_normal_queue_size: Option<u32>,
179    max_high_queue_size: Option<u32>,
180    capacity: u32,
181    state: Arc<Mutex<PriorityState>>,
182}
183
184impl PriorityLimiter {
185    /// Creates a priority limiter with shared capacity and separate timeouts and queue limits.
186    /// Pass `None` as the high-priority timeout to wait without a deadline.
187    pub fn new(
188        capacity: NonZeroU32,
189        normal_timeout: Duration,
190        high_timeout: impl Into<Option<Duration>>,
191        max_normal_queue_size: Option<u32>,
192        max_high_queue_size: Option<u32>,
193    ) -> Self {
194        Self {
195            normal_timeout,
196            high_timeout: high_timeout.into(),
197            max_normal_queue_size,
198            max_high_queue_size,
199            capacity: capacity.get(),
200            state: Arc::new(Mutex::new(PriorityState {
201                free: capacity.get(),
202                next_id: 0,
203                normal_queue: WaiterQueue::new(),
204                high_queue: WaiterQueue::new(),
205            })),
206        }
207    }
208
209    /// Acquires capacity within the timeout configured for the given priority.
210    ///
211    /// Returns [`ErrorKind::AtCapacity`] when this priority's queue is full or the wait times out.
212    /// Dropping the future releases its queue slot and any assigned permit.
213    pub async fn acquire(&self, priority: Priority) -> Result<Permit> {
214        let (timeout, max_queue_size) = match priority {
215            Priority::Normal => (Some(self.normal_timeout), self.max_normal_queue_size),
216            Priority::High => (self.high_timeout, self.max_high_queue_size),
217        };
218
219        let (_entry, receiver) = {
220            let mut state = self.state.lock().unwrap_or_else(PoisonError::into_inner);
221            // A free permit implies that nobody is queued, so taking it overtakes no one.
222            if state.free > 0 {
223                state.free -= 1;
224                return Ok(Permit::priority(self.state.clone()));
225            }
226            if timeout == Some(Duration::ZERO) {
227                return Err(ErrorKind::AtCapacity.into());
228            }
229            let id = state.next_id;
230            let queue = state.queue(priority);
231            if max_queue_size.is_some_and(|max| queue.len() >= max as usize) {
232                return Err(ErrorKind::AtCapacity.into());
233            }
234            let (sender, receiver) = oneshot::channel();
235            queue.insert(id, sender);
236            state.next_id += 1;
237
238            // Leaves the queue on timeout or cancellation. A no-op once a permit was handed over.
239            let entry = DropGuard::new(id, move |id| {
240                let mut state = self.state.lock().unwrap_or_else(PoisonError::into_inner);
241                state.queue(priority).remove(&id);
242            });
243            (entry, receiver)
244        };
245
246        // A permit sent after a timeout or cancellation is dropped with the receiver, which passes
247        // its slot on to the next waiter.
248        let received = match timeout {
249            Some(timeout) => tokio::time::timeout(timeout, receiver)
250                .await
251                .map_err(|_| ErrorKind::AtCapacity)?,
252            None => receiver.await,
253        };
254        received.map_err(|_| ErrorKind::AtCapacity.into())
255    }
256
257    /// Returns a snapshot of permits in use and queued acquisitions.
258    pub fn stats(&self) -> PriorityLimiterStats {
259        let state = self.state.lock().unwrap_or_else(PoisonError::into_inner);
260        PriorityLimiterStats {
261            in_use: self.capacity - state.free,
262            waiting_normal: state.normal_queue.len(),
263            waiting_high: state.high_queue.len(),
264        }
265    }
266
267    /// Passes this limiter's stats to `emit` immediately and once per second thereafter.
268    pub async fn run_emitter<F, Fut>(&self, emit: F) -> !
269    where
270        F: FnMut(PriorityLimiterStats) -> Fut,
271        Fut: Future<Output = ()>,
272    {
273        run_emitter(|| self.stats(), emit).await
274    }
275}
276
277/// Waiters keyed by arrival order, each holding the channel its permit is delivered on.
278type WaiterQueue = BTreeMap<u64, oneshot::Sender<Permit>>;
279
280// A permit is either free or owned by exactly one `Permit`. On release, `PriorityPermit` hands
281// its slot directly to the next waiter instead of returning it to `free`, so a waiter never has
282// to race newcomers for it and every waiter can be admitted without waiting for another one.
283#[derive(Debug)]
284struct PriorityState {
285    free: u32,
286    next_id: u64,
287    normal_queue: WaiterQueue,
288    high_queue: WaiterQueue,
289}
290
291impl PriorityState {
292    fn queue(&mut self, priority: Priority) -> &mut WaiterQueue {
293        match priority {
294            Priority::Normal => &mut self.normal_queue,
295            Priority::High => &mut self.high_queue,
296        }
297    }
298
299    fn pop_next_waiter(&mut self) -> Option<oneshot::Sender<Permit>> {
300        let (_, sender) = self
301            .high_queue
302            .pop_first()
303            .or_else(|| self.normal_queue.pop_first())?;
304        Some(sender)
305    }
306}
307
308/// One slot of a [`PriorityLimiter`], handed to the next waiter or freed on drop.
309#[derive(Debug)]
310struct PriorityPermit {
311    state: Arc<Mutex<PriorityState>>,
312}
313
314impl Drop for PriorityPermit {
315    fn drop(&mut self) {
316        let mut state = self.state.lock().unwrap_or_else(PoisonError::into_inner);
317        let Some(sender) = state.pop_next_waiter() else {
318            state.free += 1;
319            return;
320        };
321        // Unlock before sending: if the waiter is gone, `send` returns the permit, and dropping
322        // it re-enters this function.
323        drop(state);
324        let _ = sender.send(Permit::priority(self.state.clone()));
325    }
326}
327
328#[cfg(test)]
329mod tests {
330    use super::*;
331    use futures_util::{StreamExt, poll};
332    use std::sync::atomic::{AtomicBool, Ordering};
333
334    const TIMEOUT: Duration = Duration::from_secs(1);
335
336    #[tokio::test(start_paused = true)]
337    async fn emitter_reports_current_limiter_usage() {
338        let priority = PriorityLimiter::new(NonZeroU32::MIN, TIMEOUT, TIMEOUT, None, None);
339        let simple = Limiter::new(NonZeroU32::MIN, Duration::ZERO, None);
340        let priority_permit = priority.acquire(Priority::Normal).await.unwrap();
341        let simple_permit = simple.acquire().await.unwrap();
342        let (priority_sender, mut priority_receiver) = tokio::sync::mpsc::unbounded_channel();
343        let (simple_sender, mut simple_receiver) = tokio::sync::mpsc::unbounded_channel();
344        let priority_emitter = priority.run_emitter(|stats| {
345            priority_sender.send(stats).unwrap();
346            std::future::ready(())
347        });
348        let simple_emitter = simple.run_emitter(|stats| {
349            simple_sender.send(stats).unwrap();
350            std::future::ready(())
351        });
352        tokio::pin!(priority_emitter, simple_emitter);
353        assert!(poll!(&mut priority_emitter).is_pending());
354        assert!(poll!(&mut simple_emitter).is_pending());
355        assert_eq!(priority_receiver.try_recv().unwrap().in_use, 1);
356        assert_eq!(simple_receiver.try_recv().unwrap().in_use, 1);
357
358        drop(priority_permit);
359        drop(simple_permit);
360        tokio::time::advance(Duration::from_secs(1)).await;
361        assert!(poll!(&mut priority_emitter).is_pending());
362        assert!(poll!(&mut simple_emitter).is_pending());
363        assert_eq!(
364            priority_receiver.try_recv().unwrap(),
365            PriorityLimiterStats::default()
366        );
367        assert_eq!(simple_receiver.try_recv().unwrap(), LimiterStats::default());
368    }
369
370    #[tokio::test(start_paused = true)]
371    async fn stream_retains_then_releases_at_terminal_item() {
372        for error in [false, true] {
373            let limiter = Limiter::new(NonZeroU32::MIN, Duration::ZERO, None);
374            let mut step = 0;
375            let source = stream::poll_fn(move |_| {
376                step += 1;
377                match step {
378                    1 => Poll::Ready(Some(Ok(Bytes::from_static(b"data")))),
379                    2 => Poll::Pending,
380                    3 if error => Poll::Ready(Some(Err(io::Error::other("original")))),
381                    3 => Poll::Ready(None),
382                    _ => panic!("polled after terminal item"),
383                }
384            })
385            .boxed();
386            let mut guarded = limiter.acquire().await.unwrap().guard_stream(source);
387            assert_eq!(
388                guarded.next().await.unwrap().unwrap(),
389                Bytes::from_static(b"data")
390            );
391            assert_eq!(limiter.stats().in_use, 1);
392            assert!(poll!(guarded.next()).is_pending());
393            assert_eq!(limiter.stats().in_use, 1);
394            let terminal = guarded.next().await;
395            if error {
396                assert_eq!(terminal.unwrap().unwrap_err().to_string(), "original");
397            } else {
398                assert!(terminal.is_none());
399            }
400            assert_eq!(limiter.stats().in_use, 0);
401            assert!(guarded.next().await.is_none());
402        }
403    }
404
405    #[tokio::test(start_paused = true)]
406    async fn stream_drop_releases_after_stream() {
407        struct PendingStream {
408            dropped: Arc<AtomicBool>,
409            limiter: Limiter,
410        }
411        impl Stream for PendingStream {
412            type Item = io::Result<Bytes>;
413            fn poll_next(
414                self: std::pin::Pin<&mut Self>,
415                _: &mut std::task::Context<'_>,
416            ) -> Poll<Option<Self::Item>> {
417                Poll::Pending
418            }
419        }
420        impl Drop for PendingStream {
421            fn drop(&mut self) {
422                assert_eq!(self.limiter.stats().in_use, 1);
423                self.dropped.store(true, Ordering::Relaxed);
424            }
425        }
426        let limiter = Limiter::new(NonZeroU32::MIN, Duration::ZERO, None);
427        let dropped = Arc::new(AtomicBool::new(false));
428        let source = PendingStream {
429            dropped: dropped.clone(),
430            limiter: limiter.clone(),
431        }
432        .boxed();
433        let mut guarded = limiter.acquire().await.unwrap().guard_stream(source);
434        assert!(poll!(guarded.next()).is_pending());
435        drop(guarded);
436        assert!(dropped.load(Ordering::Relaxed));
437        assert_eq!(limiter.stats().in_use, 0);
438    }
439
440    #[tokio::test(start_paused = true)]
441    async fn simple_limiter_queue_limits_and_cleanup() {
442        let immediate = Limiter::new(NonZeroU32::MIN, Duration::ZERO, None);
443        let held = immediate.acquire().await.unwrap();
444        assert_eq!(
445            immediate.acquire().await.unwrap_err().kind(),
446            ErrorKind::AtCapacity
447        );
448        drop(held);
449
450        for max_queue_size in [None, Some(0), Some(1)] {
451            let limiter = Limiter::new(NonZeroU32::MIN, TIMEOUT, max_queue_size);
452            let held = limiter.acquire().await.unwrap();
453            let before = tokio::time::Instant::now();
454            let mut waiting = Box::pin(limiter.acquire());
455            if max_queue_size == Some(0) {
456                assert_eq!(waiting.await.unwrap_err().kind(), ErrorKind::AtCapacity);
457                assert_eq!(tokio::time::Instant::now(), before);
458                drop(held);
459                continue;
460            }
461            assert!(poll!(&mut waiting).is_pending());
462            if max_queue_size == Some(1) {
463                assert_eq!(
464                    limiter.acquire().await.unwrap_err().kind(),
465                    ErrorKind::AtCapacity
466                );
467                assert_eq!(tokio::time::Instant::now(), before);
468            }
469            // Cancellation must free the queue slot for another waiter.
470            drop(waiting);
471            let mut timed_out = Box::pin(limiter.acquire());
472            assert!(poll!(&mut timed_out).is_pending());
473            tokio::time::advance(TIMEOUT).await;
474            assert_eq!(timed_out.await.unwrap_err().kind(), ErrorKind::AtCapacity);
475            // A timeout must also free the queue slot.
476            let mut next = Box::pin(limiter.acquire());
477            assert!(poll!(&mut next).is_pending());
478            drop(held);
479            drop(next.await.unwrap());
480            assert_eq!(limiter.stats().in_use, 0);
481        }
482    }
483
484    fn priority_limiter(capacity: u32) -> PriorityLimiter {
485        PriorityLimiter::new(
486            NonZeroU32::new(capacity).unwrap(),
487            TIMEOUT,
488            TIMEOUT,
489            None,
490            None,
491        )
492    }
493
494    #[tokio::test(start_paused = true)]
495    async fn priority_fifo_and_handoff_accounting() {
496        let limiter = priority_limiter(1);
497        let held = limiter.acquire(Priority::Normal).await.unwrap();
498        let mut normal1 = Box::pin(limiter.acquire(Priority::Normal));
499        let mut normal2 = Box::pin(limiter.acquire(Priority::Normal));
500        let mut high1 = Box::pin(limiter.acquire(Priority::High));
501        let mut high2 = Box::pin(limiter.acquire(Priority::High));
502        assert!(poll!(&mut normal1).is_pending());
503        assert!(poll!(&mut normal2).is_pending());
504        assert!(poll!(&mut high1).is_pending());
505        assert!(poll!(&mut high2).is_pending());
506        assert_eq!(
507            limiter.stats(),
508            PriorityLimiterStats {
509                in_use: 1,
510                waiting_normal: 2,
511                waiting_high: 2
512            }
513        );
514        // The slot goes straight to the oldest high-priority waiter.
515        drop(held);
516        assert_eq!(
517            limiter.stats(),
518            PriorityLimiterStats {
519                in_use: 1,
520                waiting_normal: 2,
521                waiting_high: 1
522            }
523        );
524        // A newcomer cannot take the slot assigned to a waiter that has not woken up yet.
525        let clone = limiter.clone();
526        let mut newcomer = Box::pin(clone.acquire(Priority::Normal));
527        assert!(poll!(&mut newcomer).is_pending());
528        // Normal waiters must wait for all high-priority acquisitions to finish.
529        assert!(poll!(&mut normal1).is_pending());
530        assert!(poll!(&mut high2).is_pending());
531        drop(high1.await.unwrap());
532        assert!(poll!(&mut normal1).is_pending());
533        drop(high2.await.unwrap());
534        // Normal waiters are then served in arrival order.
535        assert!(poll!(&mut normal2).is_pending());
536        assert!(poll!(&mut newcomer).is_pending());
537        drop(normal1.await.unwrap());
538        assert!(poll!(&mut newcomer).is_pending());
539        drop(normal2.await.unwrap());
540        drop(newcomer.await.unwrap());
541        assert_eq!(limiter.stats(), PriorityLimiterStats::default());
542    }
543
544    #[tokio::test(start_paused = true)]
545    async fn released_slots_admit_all_waiters_at_once() {
546        let limiter = priority_limiter(3);
547        let mut held = Vec::new();
548        for _ in 0..3 {
549            held.push(limiter.acquire(Priority::Normal).await.unwrap());
550        }
551        let mut waiters: Vec<_> = (0..3)
552            .map(|_| Box::pin(limiter.acquire(Priority::Normal)))
553            .collect();
554        for waiter in &mut waiters {
555            assert!(poll!(waiter).is_pending());
556        }
557        drop(held);
558        // Every waiter owns a slot before any of them is polled again.
559        assert_eq!(
560            limiter.stats(),
561            PriorityLimiterStats {
562                in_use: 3,
563                waiting_normal: 0,
564                waiting_high: 0
565            }
566        );
567        for waiter in &mut waiters {
568            assert!(poll!(waiter).is_ready());
569        }
570        assert_eq!(limiter.stats(), PriorityLimiterStats::default());
571    }
572
573    #[tokio::test(start_paused = true)]
574    async fn high_priority_can_wait_without_a_deadline_or_queue_limit() {
575        let limiter = PriorityLimiter::new(NonZeroU32::MIN, TIMEOUT, None, Some(1), None);
576        let held = limiter.acquire(Priority::Normal).await.unwrap();
577        let mut high1 = Box::pin(limiter.acquire(Priority::High));
578        let mut high2 = Box::pin(limiter.acquire(Priority::High));
579        let mut normal = Box::pin(limiter.acquire(Priority::Normal));
580        assert!(poll!(&mut high1).is_pending());
581        assert!(poll!(&mut high2).is_pending());
582        assert!(poll!(&mut normal).is_pending());
583        assert_eq!(
584            limiter.acquire(Priority::Normal).await.unwrap_err().kind(),
585            ErrorKind::AtCapacity
586        );
587
588        tokio::time::advance(TIMEOUT * 2).await;
589        assert_eq!(normal.await.unwrap_err().kind(), ErrorKind::AtCapacity);
590        assert!(poll!(&mut high1).is_pending());
591        assert!(poll!(&mut high2).is_pending());
592        drop(held);
593        drop(high1.await.unwrap());
594        drop(high2.await.unwrap());
595    }
596
597    #[tokio::test(start_paused = true)]
598    async fn cancelled_waiter_leaves_queue() {
599        for priority in [Priority::Normal, Priority::High] {
600            let limiter = PriorityLimiter::new(NonZeroU32::MIN, TIMEOUT, TIMEOUT, Some(1), Some(1));
601            let held = limiter.acquire(Priority::Normal).await.unwrap();
602            let mut cancelled = Box::pin(limiter.acquire(priority));
603            assert!(poll!(&mut cancelled).is_pending());
604            assert_eq!(
605                limiter.acquire(priority).await.unwrap_err().kind(),
606                ErrorKind::AtCapacity
607            );
608            let other_priority = match priority {
609                Priority::Normal => Priority::High,
610                Priority::High => Priority::Normal,
611            };
612            // Filling one queue must not prevent admission to the other queue.
613            let mut other = Box::pin(limiter.acquire(other_priority));
614            assert!(poll!(&mut other).is_pending());
615            drop(cancelled);
616            let mut next = Box::pin(limiter.acquire(priority));
617            assert!(poll!(&mut next).is_pending());
618            drop(other);
619            drop(held);
620            drop(next.await.unwrap());
621            assert_eq!(limiter.stats(), PriorityLimiterStats::default());
622        }
623    }
624
625    #[tokio::test(start_paused = true)]
626    async fn cancelled_after_grant_passes_slot_on() {
627        let limiter = PriorityLimiter::new(NonZeroU32::MIN, TIMEOUT, TIMEOUT, Some(2), Some(1));
628        let held = limiter.acquire(Priority::Normal).await.unwrap();
629        let mut cancelled = Box::pin(limiter.acquire(Priority::Normal));
630        let mut next = Box::pin(limiter.acquire(Priority::Normal));
631        assert!(poll!(&mut cancelled).is_pending());
632        assert!(poll!(&mut next).is_pending());
633
634        // The slot is handed to `cancelled`, which is dropped before receiving it.
635        drop(held);
636        drop(cancelled);
637        drop(next.await.unwrap());
638        assert_eq!(limiter.stats(), PriorityLimiterStats::default());
639        // Both normal queue slots must be available after cancellation and completion.
640        let held = limiter.acquire(Priority::Normal).await.unwrap();
641        let mut first = Box::pin(limiter.acquire(Priority::Normal));
642        let mut second = Box::pin(limiter.acquire(Priority::Normal));
643        let mut high = Box::pin(limiter.acquire(Priority::High));
644        assert!(poll!(&mut first).is_pending());
645        assert!(poll!(&mut second).is_pending());
646        assert!(poll!(&mut high).is_pending());
647        drop((first, second, high, held));
648    }
649
650    #[tokio::test(start_paused = true)]
651    async fn timeouts_remove_waiters() {
652        for timeout in [Duration::ZERO, TIMEOUT] {
653            for priority in [Priority::Normal, Priority::High] {
654                let queue_limit = if timeout.is_zero() { None } else { Some(0) };
655                let (normal_timeout, high_timeout, normal_queue, high_queue) = match priority {
656                    Priority::Normal => (timeout, TIMEOUT, queue_limit, Some(1)),
657                    Priority::High => (TIMEOUT, timeout, Some(1), queue_limit),
658                };
659                let immediate = PriorityLimiter::new(
660                    NonZeroU32::MIN,
661                    normal_timeout,
662                    high_timeout,
663                    normal_queue,
664                    high_queue,
665                );
666                let held = immediate.acquire(priority).await.unwrap();
667                let before = tokio::time::Instant::now();
668                assert_eq!(
669                    immediate.acquire(priority).await.unwrap_err().kind(),
670                    ErrorKind::AtCapacity
671                );
672                assert_eq!(tokio::time::Instant::now(), before);
673                let other_priority = match priority {
674                    Priority::Normal => Priority::High,
675                    Priority::High => Priority::Normal,
676                };
677                let mut other = Box::pin(immediate.acquire(other_priority));
678                assert!(poll!(&mut other).is_pending());
679                drop(other);
680                drop(held);
681            }
682        }
683
684        for priority in [Priority::Normal, Priority::High] {
685            let (normal_timeout, high_timeout, other_priority) = match priority {
686                Priority::Normal => (TIMEOUT / 2, TIMEOUT, Priority::High),
687                Priority::High => (TIMEOUT, TIMEOUT / 2, Priority::Normal),
688            };
689            let limiter = PriorityLimiter::new(
690                NonZeroU32::MIN,
691                normal_timeout,
692                high_timeout,
693                Some(1),
694                Some(1),
695            );
696            let held = limiter.acquire(Priority::Normal).await.unwrap();
697            let mut waiting = Box::pin(limiter.acquire(priority));
698            let mut other = Box::pin(limiter.acquire(other_priority));
699            assert!(poll!(&mut waiting).is_pending());
700            assert!(poll!(&mut other).is_pending());
701            tokio::time::advance(TIMEOUT / 2).await;
702            assert_eq!(waiting.await.unwrap_err().kind(), ErrorKind::AtCapacity);
703            // The other priority's longer timeout has not elapsed.
704            assert!(poll!(&mut other).is_pending());
705            assert_eq!(limiter.stats().in_use, 1);
706            drop(other);
707            let mut retry = Box::pin(limiter.acquire(priority));
708            assert!(poll!(&mut retry).is_pending());
709            drop(held);
710            drop(retry.await.unwrap());
711            assert_eq!(limiter.stats(), PriorityLimiterStats::default());
712        }
713    }
714
715    /// Races releases against timeouts and cancellations on several threads, including
716    /// cancellation after a permit is handed over. Not guaranteed to hit every race on each
717    /// run, but checks that no slot is ever lost or returned twice.
718    #[tokio::test(flavor = "multi_thread", worker_threads = 4)]
719    async fn concurrent_releases_timeouts_and_cancellations_keep_accounting() {
720        const CAPACITY: u32 = 4;
721        let limiter = PriorityLimiter::new(
722            NonZeroU32::new(CAPACITY).unwrap(),
723            Duration::from_millis(2),
724            Duration::from_millis(2),
725            Some(CAPACITY),
726            Some(CAPACITY),
727        );
728
729        let tasks: Vec<_> = (0..200)
730            .map(|task| {
731                let limiter = limiter.clone();
732                tokio::spawn(async move {
733                    for round in 0..20 {
734                        let priority = if (task + round) % 2 == 0 {
735                            Priority::Normal
736                        } else {
737                            Priority::High
738                        };
739                        let acquire = limiter.acquire(priority);
740                        if (task + round) % 3 == 0 {
741                            // Cancel from outside, possibly right as a slot is handed over.
742                            let _ = tokio::time::timeout(Duration::from_millis(1), acquire).await;
743                        } else if let Ok(permit) = acquire.await {
744                            // Hold long enough for waiters to queue up and time out.
745                            tokio::time::sleep(Duration::from_millis(1)).await;
746                            drop(permit);
747                        }
748                    }
749                })
750            })
751            .collect();
752        for task in tasks {
753            task.await.unwrap();
754        }
755
756        assert_eq!(limiter.stats(), PriorityLimiterStats::default());
757        let mut permits = Vec::new();
758        for _ in 0..CAPACITY {
759            permits.push(limiter.acquire(Priority::Normal).await.unwrap());
760        }
761    }
762}