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}