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}