Skip to main content

tor_async_utils/bw_pool/
bucket.rs

1//! An atomic and shareable token bucket BUT with one caveat, it is without the clock component
2//! that is the refill is not taking into account any rate or time tracking.
3//!
4//! This [`AtomicTokenBucket`] is used within a [`super::BandwidthPool`] to keep track of the
5//! available bandwidth.
6//!
7//! It is refilled through an entity, the [`super::BandwidthRefiller`], which is owned by an
8//! independent task built to refill this bucket at the appropriate time.
9//!
10//! See the [`super`] documentation for more information on how these objects interact with each
11//! other.
12
13// TODO MSRV 1.95: Remove this, and use try_update instead of fetch_update.
14#![allow(deprecated)]
15
16use std::sync::atomic::{AtomicU64, Ordering};
17
18/// The atomic token bucket minus the clock component.
19///
20/// This is lock-free and the owner needs to refill it with a specific number of tokens it wants to
21/// be distributed across many actors.
22#[derive(Debug)]
23pub(super) struct AtomicTokenBucket {
24    /// Every access to these counters is with [`Ordering::Relaxed`] as they don't
25    /// protect any outside data and so we only care about the atomicity action on the
26    /// counter.
27
28    /// The current token count.
29    available: AtomicU64,
30    /// The maximum number of tokens the bucket may hold a.k.a the burst.
31    ///
32    /// This is atomic because it can be set during runtime. For instance, a config
33    /// option reconfigure of a bandwidth rate.
34    capacity: u64,
35    /// The smallest partial claim the bucket grants.
36    ///
37    /// Below it, the bucket is considered empty on claims.
38    min_grant: u64,
39}
40
41impl AtomicTokenBucket {
42    /// A new bucket capped at `capacity` tokens that never grants a partial claim below
43    /// `min_grant` tokens.
44    ///
45    /// It starts full.
46    pub(super) fn new(capacity: u64, min_grant: u64) -> Self {
47        AtomicTokenBucket {
48            available: AtomicU64::new(capacity),
49            capacity,
50            min_grant,
51        }
52    }
53
54    /// Claim up to `tokens` from the bucket.
55    ///
56    /// This is a partial claim: if the bucket holds less than `tokens`, everything it
57    /// holds is claimed as long as it is at least the minimum grant. The minimum grant is
58    /// lowered to `tokens` or the capacity if smaller.
59    ///
60    /// Return `None` if something is not right as in `tokens` is 0 or below `min_grant`
61    /// or above the pool capacity. In other words, the caller should be aware that
62    /// something wrong happened.
63    ///
64    /// Return `Some(0)` indicate that the pool is empty or disabled. This tells the
65    /// caller to come back safely where `None` would indicate the caller to change
66    /// something to its original request.
67    ///
68    /// Returns `Some(claimed)` with the number of tokens now granted to the caller. Note
69    /// that `claimed` can be lower than `tokens` hence why the caller needs to use that
70    /// value and not what it asked for.
71    #[must_use]
72    pub(super) fn claim(&self, tokens: u64) -> Option<u64> {
73        // Never claim a zero amount.
74        if tokens == 0 {
75            return None;
76        }
77        // Never below min_grant and the pool capacity. Hard limit at 1 token.
78        let floor = self.min_grant.min(tokens).min(self.capacity).max(1);
79
80        // NOTE: fetch_update() is deprecated in 1.99.0 and replaced by try_update()
81        // starting in 1.95.0. Our current MSRV is 1.89.0.
82        //
83        // Relaxed: only the atomic subtract matters, the counter gates no other memory.
84        self.available
85            .fetch_update(Ordering::Relaxed, Ordering::Relaxed, |cur| {
86                (cur >= floor).then(|| cur.saturating_sub(tokens))
87            })
88            .ok()
89            .map(|prev| prev.min(tokens))
90    }
91
92    /// Add `tokens` to the bucket which is capped at the capacity.
93    ///
94    /// We use a CAS loop (Compare-And-Swap) because we need to cap the refill to the internal
95    /// capacity atomically. A fetch_add + fetch_sub is not possible in order to refill atomically
96    /// because of this race:
97    ///
98    /// ```text
99    ///   capacity = 100, available = 90:
100    ///     refill: fetch_add(50)  -> available = 140 (above capacity)
101    ///     claim:  fetch_sub(140) -> available = 0   (illegal claim, above capacity)
102    ///     refill: fetch_sub(40)  -> available underflows (adjust overshoot too late)
103    /// ```
104    ///
105    /// Any tokens that overshoot the capacity are forfeited.
106    ///
107    /// Finally, the CAS loop is considered ok because the refill is not in the fast path and
108    /// should work most of the time on the first iteration.
109    pub(super) fn refill(&self, tokens: u64) {
110        if tokens == 0 {
111            return;
112        }
113
114        // NOTE: fetch_update() is deprecated in 1.99.0 and replaced by try_update()
115        // starting in 1.95.0. Our current MSRV is 1.89.0.
116        //
117        // Relaxed: only the atomic add matters, the counter gates no other memory.
118        let _ = self
119            .available
120            .fetch_update(Ordering::Relaxed, Ordering::Relaxed, |cur| {
121                Some(cur.saturating_add(tokens).min(self.capacity))
122            });
123    }
124
125    /// Take every token out of the bucket and return the amount.
126    pub(super) fn drain(&self) -> u64 {
127        // Relaxed: only the atomic exchange matters, the counter gates no other memory.
128        self.available.swap(0, Ordering::Relaxed)
129    }
130
131    /// Return the capacity.
132    pub(super) fn capacity(&self) -> u64 {
133        self.capacity
134    }
135
136    /// Return the available balance.
137    #[cfg(test)]
138    pub(super) fn available(&self) -> u64 {
139        // Relaxed: we only need the current value of the counter.
140        self.available.load(Ordering::Relaxed)
141    }
142}
143
144#[cfg(test)]
145mod test {
146    // @@ begin test lint list maintained by maint/add_warning @@
147    #![allow(clippy::bool_assert_comparison)]
148    #![allow(clippy::clone_on_copy)]
149    #![allow(clippy::dbg_macro)]
150    #![allow(clippy::mixed_attributes_style)]
151    #![allow(clippy::print_stderr)]
152    #![allow(clippy::print_stdout)]
153    #![allow(clippy::single_char_pattern)]
154    #![allow(clippy::unwrap_used)]
155    #![allow(clippy::unchecked_time_subtraction)]
156    #![allow(clippy::useless_vec)]
157    #![allow(clippy::needless_pass_by_value)]
158    #![allow(clippy::string_slice)] // See arti#2571
159    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
160
161    use super::*;
162
163    /// Minimum partial grant used by the tests.
164    const MIN_GRANT: u64 = 10;
165
166    #[test]
167    fn claim_and_refill() {
168        let b = AtomicTokenBucket::new(100, MIN_GRANT);
169        assert_eq!(b.available(), 100);
170        assert_eq!(b.capacity(), 100);
171
172        assert_eq!(b.claim(60), Some(60));
173        // Only 40 left. Partial claim takes them all.
174        assert_eq!(b.claim(50), Some(40));
175        assert_eq!(b.available(), 0);
176        assert_eq!(b.claim(1), None);
177
178        // Refill is capped at capacity.
179        b.refill(1000);
180        assert_eq!(b.available(), 100);
181    }
182
183    #[test]
184    fn claim_above_capacity() {
185        let b = AtomicTokenBucket::new(100, MIN_GRANT);
186
187        // A claim above the burst gets what the bucket holds and is not refused.
188        assert_eq!(b.claim(1000), Some(100));
189        assert_eq!(b.available(), 0);
190
191        // Same when the bucket is partially filled.
192        b.refill(50);
193        assert_eq!(b.claim(1000), Some(50));
194        assert_eq!(b.available(), 0);
195    }
196
197    #[test]
198    fn claim_min_grant() {
199        let b = AtomicTokenBucket::new(100, MIN_GRANT);
200        assert_eq!(b.claim(95), Some(95));
201        // Now 5 tokens remains and MIN_GRANT is higher.
202
203        // Below the minimum grant, a partial claim gets nothing.
204        assert_eq!(b.claim(50), None);
205        assert_eq!(b.available(), 5);
206
207        // A claim below the minimum grant is granted in full.
208        assert_eq!(b.claim(5), Some(5));
209        assert_eq!(b.available(), 0);
210
211        // A capacity below the minimum grant still grants partial claims.
212        let b = AtomicTokenBucket::new(5, MIN_GRANT);
213        assert_eq!(b.claim(50), Some(5));
214    }
215
216    #[test]
217    fn drain() {
218        let b = AtomicTokenBucket::new(100, MIN_GRANT);
219        assert_eq!(b.claim(90), Some(90)); // 10 tokens left
220
221        assert_eq!(b.drain(), 10);
222        assert_eq!(b.available(), 0);
223
224        // Draining an empty bucket takes nothing.
225        assert_eq!(b.drain(), 0);
226    }
227}