Skip to main content

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}