tor_async_utils/bw_pool/refiller.rs
1//! The refiller code that is the [`BandwidthRefiller`] is a public entity that needs to
2//! run into its own task and refill the associated [`super::BandwidthPool`] and serve
3//! any refill requests pending on the pool to be replenished.
4//!
5//! # Driving a pool
6//!
7//! The refiller must live in its own task that owns the clock and the rate. Simply call
8//! [`BandwidthRefiller::run`] into a spawned task. It builds a token bucket from the given
9//! rate + burst and a [`tor_rtcompat::SleepProvider`].
10//!
11//! # Example
12//!
13//! ```ignore
14//! let (pool, refiller) = BandwidthPool::new(capacity, min_grant);
15//! let config = TokenBucketConfig { rate, bucket_max: capacity };
16//! runtime.spawn(refiller.run(runtime.clone(), config))?;
17//! ```
18
19use futures::StreamExt as _;
20use futures::channel::mpsc;
21use std::num::NonZero;
22use std::sync::Arc;
23
24use tor_basic_utils::token_bucket::{TokenBucket, TokenBucketConfig};
25use tor_rtcompat::SleepProvider;
26
27use super::bucket::AtomicTokenBucket;
28use super::reusable_oneshot;
29
30/// A bandwidth request sent on the queue to the [`BandwidthRefiller`].
31///
32/// The amount of tokens wanted is fixed for the lifetime of a request and is only read
33/// by the refiller and thus why is travels along the waiter.
34pub(super) type BwRequest = (u64, reusable_oneshot::Sender<NonZero<u64>>);
35
36/// A bandwidth refiller is in charge of refilling the associated
37/// [`super::BandwidthPool`] and processing any pending refill requests that were enqueued
38/// by the pool.
39///
40/// There is exactly one refiller per pool as it owns the receiving end of the request
41/// channel. The channel is a FIFO of waiters.
42///
43/// Dropping it closes the pool which makes queued and new acquirers fail with
44/// [`super::BwPoolError::PoolClosed`].
45#[derive(Debug)]
46pub struct BandwidthRefiller {
47 /// The shared token bucket which comes from the [`super::BandwidthPool`].
48 bucket: Arc<AtomicTokenBucket>,
49 /// Receiving end of the request channel
50 rx: mpsc::UnboundedReceiver<BwRequest>,
51 /// A single request we have taken off the channel to inspect but cannot yet fund. If
52 /// only mpsc channels had an "is_empty()".
53 ///
54 /// This is populated by the [`Self::wait`] function
55 head: Option<BwRequest>,
56 /// Tokens that have been drained out of the fast-path bucket or handed in via
57 /// [`Self::refill_and_serve`] but not yet distributed.
58 ///
59 /// If anything is left at the end of the refill loop, it is published back in the
60 /// main pool fast path.
61 held: u64,
62}
63
64impl BandwidthRefiller {
65 /// Constructor.
66 pub(super) fn new(
67 bucket: Arc<AtomicTokenBucket>,
68 rx: mpsc::UnboundedReceiver<BwRequest>,
69 ) -> Self {
70 Self {
71 bucket,
72 rx,
73 head: None,
74 held: 0,
75 }
76 }
77
78 /// Start the refiller main loop. This should be run in its own task as it is
79 /// blocking until the bandwidth pool closes.
80 ///
81 /// Using the given [`SleepProvider`], we drive the refill with it along side a
82 /// [`TokenBucket`] that is built at the start with the given `config`.
83 ///
84 /// This waits on new request that comes in when the fast-path is depleted that is a
85 /// request waiting for a refill. Once a request is received, a refill is triggered
86 /// and then the loop sleeps until the needed deficit is available.
87 ///
88 /// As an example, if the queue has a request for 10 tokens but only 5 are available
89 /// in the pool after an immediate refill, we will sleep the exact time it takes to
90 /// get another 5 tokens. Then, it goes on to the next request and so on until the
91 /// queue is empty.
92 ///
93 /// Keen observer will notice that once a request is received, the refiller will have
94 /// to empty the entire queue before the fast path could even see 1 token added back
95 /// by a refill. That is because each iteration of the loop sleeps the exact amount
96 /// of time to fulfill the pending request.
97 ///
98 /// Returns when the pool is closed or if the config rate is zero.
99 pub async fn run<SP: SleepProvider>(mut self, sleep: SP, rate: u64) {
100 let config = TokenBucketConfig {
101 rate,
102 bucket_max: self.bucket.capacity(),
103 };
104 let mut bucket = TokenBucket::new(&config, sleep.now());
105 // Start empty. The pool's first start full. This avoids adding a second burst to
106 // the pool after the fast path is depleted.
107 let _ = bucket.drain_all();
108
109 loop {
110 // Wait on the "doorbell" that is a pending request wanting tokens.
111 if !self.wait().await {
112 // The pool is closed.
113 return;
114 }
115
116 // Serve the queue. Sleep for the deficit until queue is empty.
117 loop {
118 // Refill the bucket with what we can.
119 bucket.refill(sleep.now());
120 // This will reserve all available tokens from the pool so the fast-path
121 // ends up empty and then starts serving queued requests. We use all
122 // token from the TokenBucket as well.
123 //
124 // If everyone is served and we still have tokens, they are put back
125 // in the fast path.
126 match self.refill_and_serve(bucket.drain_all()) {
127 // We served everyone, fast-path has the surplus if any. Go back to
128 // the doorbell.
129 None => break,
130 // The pending request wants `deficit` amount of tokens, wait for that
131 // exact value.
132 Some(deficit) => match bucket.tokens_available_at(deficit) {
133 Ok(at) => {
134 let d = at.saturating_duration_since(sleep.now());
135 sleep.sleep(d).await;
136 }
137 // Zero rate. We can never fulfill that request so error else we
138 // are stuck. The deficit is never above the burst.
139 Err(_) => return,
140 },
141 }
142 }
143 }
144 }
145
146 /// Wait until at least one bandwidth request is queued.
147 ///
148 /// Returns `true` once a request is received or `false` if the pool has been closed
149 /// meaning the tx end is closed.
150 ///
151 /// Returns `true` immediately if a request is already held as the head.
152 ///
153 /// This should only be used as a "doorbell" that is indicating someone is at the
154 /// door with a request rather than waiting for the next request. One should use
155 /// `Self::serve` for that.
156 #[cfg_attr(feature = "bench", visibility::make(pub))]
157 pub(crate) async fn wait(&mut self) -> bool {
158 // Avoid overwriting an existing request.
159 if self.head.is_some() {
160 return true;
161 }
162 match self.rx.next().await {
163 Some(req) => {
164 self.head = Some(req);
165 true
166 }
167 None => false,
168 }
169 }
170
171 /// Add `tokens` to the pool and then serve all pending requests if any.
172 ///
173 /// The very first thing that this function does is drain the pool's fast path tokens
174 /// in order to reserve its current balance for the waiting queue.
175 ///
176 /// Any surplus left will be put back into the pool's fast path.
177 ///
178 /// Returns `None` if no one is left waiting indicating the pool is now idle and
179 /// [`Self::wait`] can be safely used to get notified of a new request.
180 ///
181 /// Returns `Some(deficit)` if an acquirer is still waiting where `deficit` is how
182 /// many more tokens are needed before it can be served. The caller can use this to
183 /// decide how long to wait before the next refill.
184 #[cfg_attr(feature = "bench", visibility::make(pub))]
185 pub(crate) fn refill_and_serve(&mut self, tokens: u64) -> Option<u64> {
186 let capacity = self.bucket.capacity();
187
188 // Reclaim tokens sitting in the fast path.
189 let reclaimed = self.bucket.drain();
190 self.held = self
191 .held
192 .saturating_add(reclaimed)
193 .saturating_add(tokens)
194 .min(capacity);
195
196 // Serve the request queue with the token we are holding.
197 self.serve(capacity);
198
199 // If we still have a head, report its deficit, else publish the remaining tokens
200 // in the pool's fast path. We use the snapshot capacity here so it is the same
201 // value used for the serve.
202 //
203 // The clamp matters as an unclamped deficit could be above the burst and our
204 // caller would then never be able to wait for it.
205 match &self.head {
206 Some((needed, _)) => Some((*needed).min(capacity).saturating_sub(self.held)),
207 None => {
208 self.publish_held();
209 None
210 }
211 }
212 }
213
214 /// Serve pending requests with the token we are holding.
215 ///
216 /// The given `capacity` is essentially the maximum we can give a single request.
217 ///
218 /// If we have a token deficit, the head is updated with the latest request that we
219 /// can't serve which indicates the caller we are in deficit.
220 fn serve(&mut self, capacity: u64) {
221 loop {
222 let (wanted, waiter) = match self.head.take() {
223 Some(req) => req,
224 None => match self.rx.try_recv() {
225 Ok(req) => req,
226 // Channel is empty or closed. We are done.
227 Err(_) => return,
228 },
229 };
230
231 // DO NOT REMOVE THIS
232 //
233 // A queued request is sent as asked so this clamp is the only thing capping
234 // the slow path. We can never hold more than the burst and so a larger
235 // request would sit in the queue forever.
236 let needed = wanted.min(capacity);
237 if needed > self.held {
238 // Unable to permit this request, keep it for next round.
239 self.head = Some((wanted, waiter));
240 return;
241 }
242
243 // Commit the permit first and then wake. If the waker (acquirer) was torn
244 // down, or is later torn down after we grant the tokens, the grant is
245 // forfeited but that is a documented limitation.
246 self.held -= needed;
247 // Grant what we took which could be a clamped value.
248 waiter.send(NonZero::new(needed).expect("BW request is 0 tokens"));
249 }
250 }
251
252 /// Publish any held surplus back to the fast-path.
253 fn publish_held(&mut self) {
254 self.bucket.refill(self.held);
255 self.held = 0;
256 }
257}
258
259#[cfg(test)]
260mod test {
261 // @@ begin test lint list maintained by maint/add_warning @@
262 #![allow(clippy::bool_assert_comparison)]
263 #![allow(clippy::clone_on_copy)]
264 #![allow(clippy::dbg_macro)]
265 #![allow(clippy::mixed_attributes_style)]
266 #![allow(clippy::print_stderr)]
267 #![allow(clippy::print_stdout)]
268 #![allow(clippy::single_char_pattern)]
269 #![allow(clippy::unwrap_used)]
270 #![allow(clippy::unchecked_time_subtraction)]
271 #![allow(clippy::useless_vec)]
272 #![allow(clippy::needless_pass_by_value)]
273 #![allow(clippy::string_slice)] // See arti#2571
274 //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
275
276 use super::*;
277
278 use futures::FutureExt as _;
279 use futures::task::{ArcWake, waker};
280 use std::sync::atomic::{AtomicUsize, Ordering};
281
282 /// Minimum partial grant used by the tests.
283 const MIN_GRANT: u64 = 10;
284
285 /// Build a new drained refiller of `capacity` and the request channel sender used to
286 /// enqueue requests.
287 fn drained_refiller(capacity: u64) -> (mpsc::UnboundedSender<BwRequest>, BandwidthRefiller) {
288 let (tx, rx) = mpsc::unbounded();
289 let bucket = Arc::new(AtomicTokenBucket::new(capacity, MIN_GRANT));
290 assert_eq!(bucket.claim(capacity), Some(capacity)); // the bucket starts full; empty it
291 (tx, BandwidthRefiller::new(bucket, rx))
292 }
293
294 /// Enqueue a request for `needed` tokens.
295 ///
296 /// Return its waiter so the test can observe the grant.
297 fn enqueue(
298 tx: &mpsc::UnboundedSender<BwRequest>,
299 needed: u64,
300 ) -> reusable_oneshot::Receiver<NonZero<u64>> {
301 let mut receiver = reusable_oneshot::Receiver::new();
302 let sender = receiver.new_sender().unwrap();
303 tx.unbounded_send((needed, sender)).unwrap();
304 receiver
305 }
306
307 /// A waker that counts how many times it is woken.
308 #[derive(Default)]
309 struct WakeCount(AtomicUsize);
310
311 impl ArcWake for WakeCount {
312 fn wake_by_ref(arc_self: &Arc<Self>) {
313 arc_self.0.fetch_add(1, Ordering::SeqCst);
314 }
315 }
316
317 /// Helper to check if a number of tokens was granted
318 /// (if the receiver was sent some value).
319 fn is_granted(receiver: &mut reusable_oneshot::Receiver<NonZero<u64>>) -> bool {
320 receiver.try_recv().unwrap().is_some()
321 }
322
323 #[test]
324 fn deficit() {
325 let (tx, mut r) = drained_refiller(100);
326 let mut w = enqueue(&tx, 50);
327
328 // Partial refills which report the shrinking deficit. No grant as we don't have
329 // enough.
330 assert_eq!(r.refill_and_serve(20), Some(30));
331 assert_eq!(r.refill_and_serve(20), Some(10));
332 assert!(!is_granted(&mut w));
333
334 // Last refill before reaching what is needed.
335 assert_eq!(r.refill_and_serve(10), None);
336 assert!(is_granted(&mut w));
337 }
338
339 #[test]
340 fn serve_fifo() {
341 let (tx, mut r) = drained_refiller(100);
342 // Enqueue two acquirers.
343 let mut a = enqueue(&tx, 30);
344 let mut b = enqueue(&tx, 30);
345
346 // Refill with 40 tokens, A should be granted wanting 30.
347 assert_eq!(r.refill_and_serve(40), Some(20));
348 assert!(is_granted(&mut a));
349 // Not granted, 10 remains for B with a 20 deficit.
350 assert!(!is_granted(&mut b));
351 assert_eq!(r.bucket.available(), 0);
352 // Refill the deficit and B should be granted.
353 assert_eq!(r.refill_and_serve(20), None);
354 assert!(is_granted(&mut b));
355 }
356
357 #[test]
358 fn reclaim_fast_path() {
359 // The bucket holds 40 tokens that a failed fast-path attempt for 50 could not claim.
360 let (tx, rx) = mpsc::unbounded();
361 let bucket = Arc::new(AtomicTokenBucket::new(100, MIN_GRANT));
362 assert_eq!(bucket.claim(60), Some(60));
363 // Pool has 40 now. Enqueue a request for 50.
364 let mut r = BandwidthRefiller::new(Arc::clone(&bucket), rx);
365 let mut w = enqueue(&tx, 50);
366
367 // A refill of 0 should take those 40 from the fast path and put them in the
368 // refiller held reserve returning a deficit of 10 to grant the request of 50.
369 assert_eq!(r.refill_and_serve(0), Some(10));
370 assert_eq!(bucket.available(), 0);
371 // Refill 20 more, the request should be granted and 10 should be put in the fast
372 // path.
373 assert_eq!(r.refill_and_serve(20), None);
374 assert!(is_granted(&mut w));
375 assert_eq!(bucket.available(), 10);
376 }
377
378 #[test]
379 fn wake_on_permit() {
380 let (tx, mut r) = drained_refiller(100);
381 let mut w = enqueue(&tx, 50);
382 let wake_counter = Arc::new(WakeCount::default());
383
384 // Poll once with a custom waker to register that waker.
385 let waker = waker(Arc::clone(&wake_counter));
386 let mut context = std::task::Context::from_waker(&waker);
387 let pinned = std::pin::pin!(w.recv().unwrap());
388 let _ = pinned.poll(&mut context);
389
390 // Not enough to wake the waiter. Request wants 50 so deficit is now 30.
391 assert_eq!(r.refill_and_serve(20), Some(30));
392 assert_eq!(wake_counter.0.load(Ordering::SeqCst), 0);
393 // Refills with the deficit, the waker should wake up and be granted.
394 assert_eq!(r.refill_and_serve(30), None);
395 assert_eq!(wake_counter.0.load(Ordering::SeqCst), 1);
396 assert!(is_granted(&mut w));
397 }
398
399 #[test]
400 fn wait_doorbell() {
401 let (tx, mut r) = drained_refiller(100);
402
403 // Nothing queued: wait() pends.
404 assert_eq!(r.wait().now_or_never(), None);
405
406 // A request rings the doorbell; it is taken as the head and served by
407 // the following refill.
408 let mut w = enqueue(&tx, 10);
409 assert_eq!(r.wait().now_or_never(), Some(true));
410 assert_eq!(r.refill_and_serve(10), None);
411 assert!(is_granted(&mut w));
412 // All senders gone, wait() should report that nothing is there.
413 drop(tx);
414 assert_eq!(r.wait().now_or_never(), Some(false));
415 }
416}