Skip to main content

tor_async_utils/
bw_pool.rs

1//! A shared token pool with a lock-free fast path and FIFO waiting queue.
2//!
3//! [`BandwidthPool`] is a set of tokens that many tasks can draw from concurrently
4//! representing a bandwidth [`Permit`]. Deciding how many tokens become available and
5//! when is the job of the [`BandwidthRefiller`] which should be run in a task that has a
6//! reference to the pool's token bucket.
7//!
8//! # Pool
9//!
10//! The pool holds the bandwidth token balance (bucket) available for any
11//! [`BandwidthAcquirer`] to attempt to acquire concurrently.
12//!
13//! The [`BandwidthPool`] can be shared between an arbitrary amount of tasks and each
14//! task needs to get a [`BandwidthAcquirer`] from the [`BandwidthPool::new_acquirer`]
15//! method.
16//!
17//! The acquirer is designed to be allocated once and reused throughout the owner object
18//! lifetime, thereby reducing the number of allocations needed at runtime.
19//!
20//! In order to be granted permission to use a certain number of tokens, the task needs
21//! to call [`BandwidthAcquirer::poll_acquire`] with the number of tokens it wants. It
22//! has to be called in the context of a task so it can be woken up once it is granted.
23//!
24//! ## Acquisition Mechanism
25//!
26//! The pool design is that there is a so called fast-path that is meant to allow a
27//! thundering herd to attempt to acquire tokens in an atomic way as long as the pool has
28//! available tokens.
29//!
30//! Once the pool is empty, new acquire requests go into a FIFO queue for fairness and
31//! are served as the pool gets refilled by the [`BandwidthRefiller`] task.
32//!
33//! A [`Permit`] is handed out once the full requested amount has been deducted from the
34//! pool as in available. The permit holds the granted tokens and the holder claims what
35//! it actually uses with [`Permit::claim`] (or [`Permit::claim_all`]). Whatever is left
36//! unclaimed in the permit is refunded to the pool when it is dropped.
37//!
38//! ## Refund
39//!
40//! Refunded tokens always go back to the fast-path pool where they are immediately
41//! available. A newcomer can acquire them while another request is queued but before
42//! the [`BandwidthRefiller`] drains the pool. This favors keeping the fast path busy
43//! over strict fairness between the fast path and the waiting queue.
44//!
45//! ## Teardown
46//!
47//! There is deliberately no cancellation mechanism for a queued request. If a
48//! [`BandwidthAcquirer`] is torn down while its request is queued, the refiller will
49//! eventually fund that request anyway, record the grant, and wake a task that no
50//! longer exists. The granted tokens are simply forfeited.
51//!
52//! This is a considered trade-off and we believe in the context of a Tor relay, losing a
53//! grant is not significant at all in the large picture of available bandwidth. The
54//! trade-off allows us to reduce a lot of complexity.
55
56mod bucket;
57mod refiller;
58mod reusable_oneshot;
59
60use futures::channel::mpsc;
61use std::num::NonZero;
62use std::sync::Arc;
63use std::task::{Context, Poll};
64use tracing::warn;
65
66use crate::bw_pool::bucket::AtomicTokenBucket;
67use crate::bw_pool::refiller::BwRequest;
68
69// Public export as the outside world needs this.
70pub use crate::bw_pool::refiller::BandwidthRefiller;
71
72/// Error returned by this module.
73#[derive(Clone, Debug, thiserror::Error)]
74#[non_exhaustive]
75pub enum BwPoolError {
76    /// Over permit claim.
77    #[error("Permit's claim() exceeds the granted tokens")]
78    ClaimExceedsGrant,
79    /// The bandwidth pool is closed.
80    #[error("bandwidth pool is closed")]
81    PoolClosed,
82    /// A request that can only be granted zero tokens.
83    #[error("bandwidth request of zero tokens")]
84    ZeroTokens,
85    /// An internal error.
86    #[error("Internal error")]
87    Bug(&'static str),
88}
89
90/// Proof that the requested number of tokens were granted.
91///
92/// If dropped, any remaining tokens will be refunded hence why there is a reference to
93/// the shared bucket.
94#[derive(Debug)]
95#[must_use = "a Permit are tokens that have already been deducted"]
96pub struct Permit {
97    /// The bucket the unclaimed tokens are refunded to when this permit is dropped.
98    bucket: Arc<AtomicTokenBucket>,
99    /// How many granted tokens this permit still has.
100    ///
101    /// Lowered by the claim methods. What is left is refunded on drop.
102    granted: u64,
103}
104
105impl Permit {
106    /// Construct a permit granting `granted` tokens.
107    ///
108    /// We keep a reference to the bucket for a refund if any.
109    fn new(bucket: Arc<AtomicTokenBucket>, granted: u64) -> Self {
110        Self { bucket, granted }
111    }
112
113    /// Claim `tokens` from this permit.
114    ///
115    /// Returns true if the permit had at least `tokens` that are now claimed. Else,
116    /// return false and nothing is claimed as in the caller is trying to use more
117    /// than it was granted.
118    pub fn claim(&mut self, tokens: u64) -> Result<(), BwPoolError> {
119        match self.granted.checked_sub(tokens) {
120            Some(left) => {
121                self.granted = left;
122                Ok(())
123            }
124            None => Err(BwPoolError::ClaimExceedsGrant),
125        }
126    }
127
128    /// Claim everything this permit holds.
129    pub fn claim_all(&mut self) {
130        let r = self.claim(self.granted);
131        debug_assert!(r.is_ok());
132    }
133
134    /// How many tokens this permit still has granted a.k.a available.
135    pub fn granted(&self) -> u64 {
136        self.granted
137    }
138}
139
140impl Drop for Permit {
141    fn drop(&mut self) {
142        // Refund into the shared pool. Note that the refund will have a no-op on the
143        // shared counters if the granted value is zero.
144        self.bucket.refill(self.granted);
145    }
146}
147
148/// A reusable bandwidth acquirer that is designed for an async context (poll).
149///
150/// The main entry point is [`Self::poll_acquire`] used within the context of a task
151/// which, if rate limited, the task gets woken up when the bandwidth usage is granted.
152#[derive(Debug)]
153pub struct BandwidthAcquirer {
154    /// The shared waiter. Reused for every acquire.
155    waiter: reusable_oneshot::Receiver<NonZero<u64>>,
156    /// The bandwidth pool attached to this acquirer.
157    pool: BandwidthPool,
158}
159
160impl BandwidthAcquirer {
161    /// Create a reusable [`BandwidthAcquirer`] for the given `pool`.
162    ///
163    /// This is the only allocation an acquirer makes. It can only be called from
164    /// [`BandwidthPool::new_acquirer`].
165    ///
166    /// The number of tokens to acquire is chosen per [`Self::poll_acquire`] call.
167    fn new(pool: BandwidthPool) -> Self {
168        Self {
169            waiter: reusable_oneshot::Receiver::new(),
170            pool,
171        }
172    }
173
174    /// Build the [`Permit`].
175    ///
176    /// This sets the `in-flight` to false and takes the granted tokens out of the waiter,
177    /// resetting it, as we now hand them to the permit.
178    fn grant_permit(&mut self, granted: u64) -> Permit {
179        Permit::new(Arc::clone(&self.pool.bucket), granted)
180    }
181
182    /// Poll to take `tokens` tokens from the pool, async waiting if the pool is dry.
183    ///
184    /// The number of `tokens` is per call so the same acquirer can request a different
185    /// amount each time.
186    ///
187    /// If the request is in flight, the `tokens` argument is ignored and the originally
188    /// requested amount is used. Only when a [`Permit`] is emitted that a new `tokens`
189    /// value can be used.
190    ///
191    /// A request above the pool capacity is clamped to it rather than refused. The
192    /// emitted [`Permit`] then holds less than what was asked and so the caller must use
193    /// [`Permit::granted`] rather than assume it got `tokens`.
194    ///
195    /// Returns a [`BwPoolError::PoolClosed`] error if the [`BandwidthRefiller`] has been
196    /// dropped.
197    ///
198    /// Returns a [`BwPoolError::ZeroTokens`] error if `tokens` is zero.
199    pub fn poll_acquire(
200        &mut self,
201        cx: &mut Context<'_>,
202        tokens: u64,
203    ) -> Poll<Result<Permit, BwPoolError>> {
204        // If we can't get a new sender, then we have a request in flight.
205        if let Some(sender_guarantee) = self.waiter.guarantee_new_sender() {
206            // No request in flight. This is the fast path! The thundering herd is allowed,
207            // that is, all tasks race to this and their fairness is sub-contracted to their
208            // task scheduler.
209            //
210            // An under-utilized relay with bandwidth limitation will hit this path most
211            // of the time.
212            //
213            // The fast path is deliberately not gated by queued requests. But there is a
214            // fairness race that we accept:
215            //
216            //      task A: fail the fast path and enqueue
217            //      permit: drop and refund enough tokens
218            //      task B: claim the refund before the refiller sees queued task A
219            //
220            // Task B has jumped task A.
221            //
222            // This is OK because the refiller drains the global bucket before serving
223            // the queue and the refill are never done directly into that bucket.
224            // Instead, it keeps it locally until all enqueued requests have been served.
225            // And so, letting B use the refund(s) keeps the pool active without breaking
226            // the rate/burst limits.
227            //
228            // This prevents a slow enqueuing on one CPU to not block the fast path on
229            // another CPU. This logic also applies for a slow refiller task. We
230            // essentially compromise almost-strict fairness for high throughput.
231            //
232            // For the case of a relay, in normal operations, we expect the write side to
233            // rarely have refunds and so this race would be rare. On the read side,
234            // refunds are much more likely to happen because as a relay we don't know
235            // exactly how many bytes we should expect at every recv().
236            if let Some(permit) = self.pool.try_acquire(tokens) {
237                return Poll::Ready(Ok(permit));
238            }
239
240            // We want to get a sender just before we enqueue the request.
241            let sender = sender_guarantee.into_sender();
242
243            // Enqueue the request as it is not in flight and our bw pool is depleted.
244            // This is where the caller gets to wait on bw availability and the refilling
245            // process is triggered.
246            match self.enqueue_request(tokens, sender) {
247                // We've enqueued the request, but we also need to poll() the waiter at least once
248                // to register the waker. We do this below.
249                Ok(()) => {}
250                Err(e) => {
251                    // Failed to enqueue the request, so the sender should have been dropped.
252                    // Let's make sure that the waiter is aware of this.
253                    match self.waiter.try_recv() {
254                        // The waiter is effectively reset now that it has informed us about
255                        // the dropped sender.
256                        Err(reusable_oneshot::RecvError::SenderDropped) => {}
257                        // We shouldn't ever get any of these return values.
258                        Ok(Some(_)) | Ok(None) | Err(reusable_oneshot::RecvError::NoSender) => {
259                            warn!("Unexpected return val from `waiter.try_recv()`; ignoring");
260                        }
261                    }
262                    // Return the original error.
263                    return Poll::Ready(Err(e));
264                }
265            };
266        }
267
268        let recv_fut = match self.waiter.recv() {
269            Ok(x) => x,
270            Err(reusable_oneshot::NoSender) => {
271                // There's no sender so we won't ever receive a result.
272                // This shouldn't happen since we created the sender above if there wasn't one.
273                return Poll::Ready(Err(BwPoolError::Bug("recv() returned `NoSender`")));
274            }
275        };
276
277        // Register our current waker and check if we were granted.
278        match std::pin::pin!(recv_fut).poll(cx) {
279            Poll::Ready(Ok(granted)) => Poll::Ready(Ok(self.grant_permit(granted.get()))),
280            Poll::Ready(Err(reusable_oneshot::SenderDropped)) => {
281                // The refiller is gone; nobody will ever serve us.
282                Poll::Ready(Err(BwPoolError::PoolClosed))
283            }
284            Poll::Pending => Poll::Pending,
285        }
286    }
287
288    /// Enqueue a request for `tokens` tokens that is NOT in flight.
289    ///
290    /// The amount is sent as it was asked. Clamping it to the pool capacity is the
291    /// refiller's job as it is the one holding the tokens by the time this is served.
292    /// The clamping is localized to the refiller for correctness.
293    ///
294    /// Return a [`BwPoolError::PoolClosed`] error if the refiller is gone.
295    ///
296    /// Return a [`BwPoolError::ZeroTokens`] error if `tokens` is zero.
297    fn enqueue_request(
298        &mut self,
299        tokens: u64,
300        sender: reusable_oneshot::Sender<NonZero<u64>>,
301    ) -> Result<(), BwPoolError> {
302        // Never enqueue a request for zero tokens.
303        if tokens == 0 {
304            return Err(BwPoolError::ZeroTokens);
305        }
306
307        // Send the requested amount along with the waiter. The amount never changes for
308        // the lifetime of the request so it doesn't need to live in the shared waiter.
309        //
310        // Notice, this is the only dynamic allocation in this path because it is sent on
311        // an unbounded MPSC queue.
312        if self.pool.requests.unbounded_send((tokens, sender)).is_err() {
313            // The refiller is gone, the pool is closed.
314            return Err(BwPoolError::PoolClosed);
315        }
316        Ok(())
317    }
318}
319
320/// A shareable bandwidth pool.
321///
322/// Use [`Self::share`] to give it to each task requiring bandwidth limitation.
323///
324/// [`Clone`] is deliberately not implemented so that handing this around can not be
325/// mistaken for creating a second pool with its own bandwidth. There is exactly one pool
326/// per [`Self::new`] call.
327///
328/// Each task needs to hold a [`BandwidthAcquirer`] in order to request bandwidth permits
329/// from this pool.
330#[derive(Debug)]
331pub struct BandwidthPool {
332    /// The shared token bucket the fast path claims from.
333    bucket: Arc<AtomicTokenBucket>,
334    /// Ingress for acquirers that failed the fast path.
335    ///
336    /// Sending a [`BwRequest`] here both enqueues it and wakes the
337    /// [`BandwidthRefiller`]
338    ///
339    /// Unbounded because we never want an acquirer's enqueue to block. the number of
340    /// in-flight requests is bounded by the number of acquirers.
341    requests: mpsc::UnboundedSender<BwRequest>,
342}
343
344impl BandwidthPool {
345    /// Create a new pool that can hold up to `capacity` tokens, and its associated
346    /// refiller [`BandwidthRefiller`] that needs to be run in its own task.
347    ///
348    /// The pool starts full and `capacity` tokens are immediately available to the fast
349    /// path.
350    ///
351    /// The fast path never grants a partial [`Permit`] below `min_grant` tokens.
352    pub fn new(capacity: NonZero<u64>, min_grant: u64) -> (BandwidthPool, BandwidthRefiller) {
353        let (tx, rx) = mpsc::unbounded();
354        let bucket = Arc::new(AtomicTokenBucket::new(capacity.get(), min_grant));
355        let pool = BandwidthPool {
356            bucket: Arc::clone(&bucket),
357            requests: tx,
358        };
359        let refiller = BandwidthRefiller::new(bucket, rx);
360        (pool, refiller)
361    }
362
363    /// Return another [`BandwidthPool`] that is the same as this one.
364    ///
365    /// The tokens are not duplicated, this is so you can share the pool with other
366    /// tasks/objects.
367    pub fn share(&self) -> BandwidthPool {
368        BandwidthPool {
369            bucket: Arc::clone(&self.bucket),
370            requests: self.requests.clone(),
371        }
372    }
373
374    /// Return a new [`BandwidthAcquirer`] associated to this pool.
375    ///
376    /// The number of tokens to acquire is chosen per
377    /// [`BandwidthAcquirer::poll_acquire`] call, so a single acquirer can be reused for
378    /// requests of different sizes.
379    ///
380    /// It is through an acquirer that one can get permission to use bandwidth. See
381    /// [`BandwidthAcquirer::poll_acquire`].
382    pub fn new_acquirer(&self) -> BandwidthAcquirer {
383        BandwidthAcquirer::new(self.share())
384    }
385
386    /// The maximum number of tokens this pool can hold (its burst).
387    pub fn capacity(&self) -> u64 {
388        self.bucket.capacity()
389    }
390
391    /// Try to take `tokens` from the pool without waiting.
392    ///
393    /// The claim is partial: if the pool holds less than `tokens`, the permit gets
394    /// everything it holds. The caller learns what it got with [`Permit::granted`].
395    ///
396    /// Returns `Some(permit)` if there were tokens available right now, or `None` if the
397    /// bucket is empty.
398    ///
399    /// This never blocks and never enqueues. It is the fast path that the other
400    /// acquisition methods use first.
401    fn try_acquire(&self, tokens: u64) -> Option<Permit> {
402        let granted = self.bucket.claim(tokens)?;
403        Some(Permit::new(Arc::clone(&self.bucket), granted))
404    }
405
406    /// Unit tests helper: async acquire wrapping a throwaway [`BandwidthAcquirer`].
407    #[cfg(test)]
408    async fn acquire(&self, tokens: u64) -> Result<Permit, BwPoolError> {
409        if let Some(permit) = self.try_acquire(tokens) {
410            return Ok(permit);
411        }
412        let mut acquirer = BandwidthAcquirer::new(self.share());
413        std::future::poll_fn(|cx| acquirer.poll_acquire(cx, tokens)).await
414    }
415
416    /// Unit tests helper: The number of tokens currently available to the fast path.
417    #[cfg(test)]
418    pub(crate) fn available(&self) -> u64 {
419        self.bucket.available()
420    }
421}
422
423#[cfg(test)]
424mod test {
425    // @@ begin test lint list maintained by maint/add_warning @@
426    #![allow(clippy::bool_assert_comparison)]
427    #![allow(clippy::clone_on_copy)]
428    #![allow(clippy::dbg_macro)]
429    #![allow(clippy::mixed_attributes_style)]
430    #![allow(clippy::print_stderr)]
431    #![allow(clippy::print_stdout)]
432    #![allow(clippy::single_char_pattern)]
433    #![allow(clippy::unwrap_used)]
434    #![allow(clippy::unchecked_time_subtraction)]
435    #![allow(clippy::useless_vec)]
436    #![allow(clippy::needless_pass_by_value)]
437    #![allow(clippy::string_slice)] // See arti#2571
438    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
439
440    use super::*;
441
442    use std::future::Future;
443    use std::pin::pin;
444
445    use futures::FutureExt as _;
446    use futures::task::noop_waker_ref;
447
448    /// Minimum partial grant.
449    const MIN_GRANT: u64 = 10;
450
451    /// A `Context` backed by a no-op waker, for deterministic manual polling.
452    ///
453    /// This is a trick so we don't rely on wakeups as grants are committed by a call to
454    /// refill_and_serve() into the waiter's grant flag. So a second poll observes it.
455    fn noop_cx() -> Context<'static> {
456        Context::from_waker(noop_waker_ref())
457    }
458
459    /// Build a [`BandwidthPool`] and drain it so 0 tokens are available.
460    fn drained_pool(cap: u64) -> (BandwidthPool, BandwidthRefiller) {
461        let (pool, refiller) = BandwidthPool::new(NonZero::new(cap).unwrap(), MIN_GRANT);
462        let mut permit = pool.try_acquire(cap).expect("a fresh pool starts full");
463        permit.claim_all();
464        (pool, refiller)
465    }
466
467    /// Expect `poll` to be a granted permit and claim all so the drop refunds zero.
468    fn expect_granted(poll: Poll<Result<Permit, BwPoolError>>) {
469        match poll {
470            Poll::Ready(Ok(mut permit)) => permit.claim_all(),
471            other => panic!("expected a granted permit, got {other:?}"),
472        }
473    }
474
475    #[test]
476    fn fast_path() {
477        let (pool, _refiller) = BandwidthPool::new(NonZero::new(100).unwrap(), MIN_GRANT);
478        assert_eq!(pool.available(), 100);
479
480        let mut permit = pool.acquire(40).now_or_never().unwrap().unwrap();
481        permit.claim_all();
482        drop(permit);
483        assert_eq!(pool.available(), 60);
484
485        let mut permit = pool.try_acquire(60).unwrap();
486        permit.claim_all();
487        drop(permit);
488        assert_eq!(pool.available(), 0);
489
490        // Nothing left. This should block and the fast path returns nothing.
491        assert!(pool.try_acquire(1).is_none());
492        assert!(pool.acquire(1).now_or_never().is_none());
493    }
494
495    #[test]
496    fn acquirer() {
497        let (pool, mut refiller) = drained_pool(100);
498
499        // Dummy context so we can poll without a wakeup.
500        let mut cx = noop_cx();
501        let mut a = pin!(pool.acquire(30));
502        // No tokens, it should be pending.
503        assert!(a.as_mut().poll(&mut cx).is_pending());
504
505        // Refill to serve it fully.
506        assert_eq!(refiller.refill_and_serve(30), None);
507        expect_granted(a.as_mut().poll(&mut cx));
508    }
509
510    #[test]
511    fn acquirer_reuse() {
512        let (pool, mut refiller) = drained_pool(100);
513
514        // Dummy context so we can poll without a wakeup.
515        let mut cx = noop_cx();
516        let mut acquirer = BandwidthAcquirer::new(pool.share());
517
518        // First blocked acquire through the acquirer.
519        assert!(acquirer.poll_acquire(&mut cx, 30).is_pending());
520        assert_eq!(refiller.refill_and_serve(30), None);
521        expect_granted(acquirer.poll_acquire(&mut cx, 30));
522
523        // The same acquirer is reusable with a different amount. No new allocation.
524        assert!(acquirer.poll_acquire(&mut cx, 50).is_pending());
525        assert_eq!(refiller.refill_and_serve(50), None);
526        expect_granted(acquirer.poll_acquire(&mut cx, 50));
527    }
528
529    #[test]
530    fn refill_newcomer() {
531        let (pool, mut refiller) = drained_pool(100);
532
533        // Dummy context so we can poll without a wakeup.
534        let mut cx = noop_cx();
535        // Enqueue 30 for A then 50 for B.
536        let mut a = pin!(pool.acquire(30));
537        assert!(a.as_mut().poll(&mut cx).is_pending());
538        let mut b = pin!(pool.acquire(50));
539        assert!(b.as_mut().poll(&mut cx).is_pending());
540
541        // Refill of 40: serves A and keeps 10 reserved for B meaning a deficit of 40.
542        assert_eq!(refiller.refill_and_serve(40), Some(40));
543        expect_granted(a.as_mut().poll(&mut cx));
544        assert!(b.as_mut().poll(&mut cx).is_pending());
545
546        // The 10 reserved tokens are NOT visible to the fast path meaning a newcomer
547        // cannot barge ahead of B (deficit of 40 to serve it).
548        assert_eq!(pool.available(), 0);
549        let mut c = pin!(pool.acquire(5));
550        assert!(c.as_mut().poll(&mut cx).is_pending());
551
552        // Second refill of 40 plus held was 10 which is 50 that B needs.
553        assert_eq!(refiller.refill_and_serve(40), Some(5)); // C is the head and 5 is the deficit.
554        expect_granted(b.as_mut().poll(&mut cx));
555        assert!(c.as_mut().poll(&mut cx).is_pending());
556
557        // And finally C.
558        assert_eq!(refiller.refill_and_serve(5), None);
559        expect_granted(c.as_mut().poll(&mut cx));
560    }
561
562    #[test]
563    fn refill_idle() {
564        let (pool, mut refiller) = drained_pool(100);
565
566        // No acquirers. Refill with a large value keeps it cap to the pool capacity.
567        assert_eq!(refiller.refill_and_serve(1000), None);
568        assert_eq!(pool.available(), 100);
569        assert_eq!(pool.capacity(), 100);
570
571        // Fast path is fine.
572        assert!(pool.try_acquire(100).is_some());
573    }
574
575    #[test]
576    fn close_pool() {
577        // Acquire fails once closed and the bucket is dry.
578        let (pool, refiller) = drained_pool(100);
579        drop(refiller);
580        assert!(pool.try_acquire(1).is_none());
581        assert!(matches!(
582            pool.acquire(10).now_or_never(),
583            Some(Err(BwPoolError::PoolClosed)),
584        ));
585
586        // A blocked acquirer is woken with PoolClosed when the refiller drops.
587        let (pool, refiller) = drained_pool(100);
588        // Dummy context so we can poll without a wakeup.
589        let mut cx = noop_cx();
590        let mut a = pin!(pool.acquire(10));
591        assert!(a.as_mut().poll(&mut cx).is_pending());
592        drop(refiller);
593        assert!(matches!(
594            a.as_mut().poll(&mut cx),
595            Poll::Ready(Err(BwPoolError::PoolClosed)),
596        ));
597
598        let (pool, mut refiller) = BandwidthPool::new(NonZero::new(100).unwrap(), MIN_GRANT);
599        drop(pool);
600        // No senders left, wait should report closure.
601        assert_eq!(refiller.wait().now_or_never(), Some(false));
602    }
603
604    #[test]
605    fn refiller_wait() {
606        let (pool, mut refiller) = drained_pool(100);
607
608        // Dummy context so we can poll without a wakeup.
609        let mut cx = noop_cx();
610        // Idle: nobody waiting so wait() is pending.
611        {
612            let mut wait_fut = pin!(refiller.wait());
613            assert!(wait_fut.as_mut().poll(&mut cx).is_pending());
614        }
615
616        // A blocked acquire enqueues a request (and wakes the refiller)...
617        let mut a = pin!(pool.acquire(10));
618        assert!(a.as_mut().poll(&mut cx).is_pending());
619
620        // wait() now completes and having taken the request as the head.
621        {
622            let mut wait_fut = pin!(refiller.wait());
623            assert!(matches!(wait_fut.as_mut().poll(&mut cx), Poll::Ready(true)));
624        }
625
626        // And refilling serves the head.
627        assert_eq!(refiller.refill_and_serve(10), None);
628        expect_granted(a.as_mut().poll(&mut cx));
629    }
630
631    #[test]
632    fn permit_claim() {
633        let (pool, _refiller) = BandwidthPool::new(NonZero::new(100).unwrap(), MIN_GRANT);
634
635        // Grab 40 and drop. Should be fully refunded.
636        let permit = pool.try_acquire(40).unwrap();
637        assert_eq!(pool.available(), 60);
638        drop(permit);
639        assert_eq!(pool.available(), 100);
640
641        // Claims are cumulative.
642        let mut permit = pool.try_acquire(40).unwrap();
643        // Can't over claim.
644        assert!(matches!(
645            permit.claim(41),
646            Err(BwPoolError::ClaimExceedsGrant),
647        ));
648        assert!(permit.claim(10).is_ok());
649        assert!(permit.claim(20).is_ok());
650        // Over claiming by one.
651        assert!(matches!(
652            permit.claim(11),
653            Err(BwPoolError::ClaimExceedsGrant),
654        ));
655        // 10 remains unclaimed now (claimed: 30, unclaimed: 10, pool: 60)
656        drop(permit);
657        // Refund the 10 left, pool is now 70.
658        assert_eq!(pool.available(), 70);
659
660        // Get what remains.
661        let mut permit = pool.try_acquire(70).unwrap();
662        // A fully claimed permit refunds nothing.
663        permit.claim_all();
664        drop(permit);
665        assert_eq!(pool.available(), 0);
666    }
667
668    #[test]
669    fn refund_newcomer() {
670        let (pool, mut refiller) = BandwidthPool::new(NonZero::new(100).unwrap(), MIN_GRANT);
671        let mut cx = noop_cx();
672
673        // Get 60 on the fast path and only use 10 so we keep holding 50.
674        let mut permit_hold = pool.try_acquire(60).unwrap();
675        assert!(permit_hold.claim(10).is_ok());
676        // Drain the rest so the pool is empty.
677        let mut drain = pool.try_acquire(40).unwrap();
678        drain.claim_all();
679        drop(drain);
680        assert_eq!(pool.available(), 0);
681
682        // Task A acquires 50 but gets queued because pool is empty.
683        let mut a = pin!(pool.acquire(50));
684        assert!(a.as_mut().poll(&mut cx).is_pending());
685
686        // Drop permit which refunds 50 to the fast-path balance. A newcomer can claim
687        // the refund even though A is already queued.
688        drop(permit_hold);
689        assert_eq!(pool.available(), 50);
690        let mut newcomer = pool.try_acquire(50).unwrap();
691        newcomer.claim_all();
692        drop(newcomer);
693        assert_eq!(pool.available(), 0);
694
695        // A remains queued and is served by subsequent refills.
696        assert_eq!(refiller.refill_and_serve(10), Some(40));
697        assert!(a.as_mut().poll(&mut cx).is_pending());
698        assert_eq!(refiller.refill_and_serve(40), None);
699        expect_granted(a.as_mut().poll(&mut cx));
700        assert_eq!(pool.available(), 0);
701    }
702}