1 /* Copyright (c) 2018-2021, The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
6 * \brief Functions to use and manipulate token buckets, used for
7 * rate-limiting on connections and globally.
9 * Tor uses these token buckets to keep track of bandwidth usage, and
10 * sometimes other things too.
12 * There are two layers of abstraction here: "raw" token buckets, in which all
13 * the pieces are decoupled, and "read-write" token buckets, which combine all
14 * the moving parts into one.
16 * Token buckets may become negative.
19 #define TOKEN_BUCKET_PRIVATE
21 #include "lib/evloop/token_bucket.h"
22 #include "lib/log/util_bug.h"
23 #include "lib/intmath/cmp.h"
24 #include "lib/time/compat_time.h"
29 * Set the <b>rate</b> and <b>burst</b> value in a token_bucket_cfg.
31 * Note that the <b>rate</b> value is in arbitrary units, but those units will
32 * determine the units of token_bucket_raw_dec(), token_bucket_raw_refill, and
36 token_bucket_cfg_init(token_bucket_cfg_t
*cfg
,
40 tor_assert_nonfatal(rate
> 0);
41 tor_assert_nonfatal(burst
> 0);
42 if (burst
> TOKEN_BUCKET_MAX_BURST
)
43 burst
= TOKEN_BUCKET_MAX_BURST
;
50 * Initialize a raw token bucket and its associated timestamp to the "full"
51 * state, according to <b>cfg</b>.
54 token_bucket_raw_reset(token_bucket_raw_t
*bucket
,
55 const token_bucket_cfg_t
*cfg
)
57 bucket
->bucket
= cfg
->burst
;
61 * Adust a preexisting token bucket to respect the new configuration
62 * <b>cfg</b>, by decreasing its current level if needed. */
64 token_bucket_raw_adjust(token_bucket_raw_t
*bucket
,
65 const token_bucket_cfg_t
*cfg
)
67 bucket
->bucket
= MIN(bucket
->bucket
, cfg
->burst
);
71 * Given an amount of <b>elapsed</b> time units, and a bucket configuration
72 * <b>cfg</b>, refill the level of <b>bucket</b> accordingly. Note that the
73 * units of time in <b>elapsed</b> must correspond to those used to set the
74 * rate in <b>cfg</b>, or the result will be illogical.
77 token_bucket_raw_refill_steps(token_bucket_raw_t
*bucket
,
78 const token_bucket_cfg_t
*cfg
,
79 const uint32_t elapsed
)
81 const int was_empty
= (bucket
->bucket
<= 0);
82 /* The casts here prevent an underflow.
84 * Note that even if the bucket value is negative, subtracting it from
85 * "burst" will still produce a correct result. If this result is
86 * ridiculously high, then the "elapsed > gap / rate" check below
88 const size_t gap
= ((size_t)cfg
->burst
) - ((size_t)bucket
->bucket
);
90 if (elapsed
> gap
/ cfg
->rate
) {
91 bucket
->bucket
= cfg
->burst
;
93 bucket
->bucket
+= cfg
->rate
* elapsed
;
96 return was_empty
&& bucket
->bucket
> 0;
100 * Decrement a provided bucket by <b>n</b> units. Note that <b>n</b>
101 * must be nonnegative.
104 token_bucket_raw_dec(token_bucket_raw_t
*bucket
,
109 const int becomes_empty
= bucket
->bucket
> 0 && n
>= bucket
->bucket
;
111 return becomes_empty
;
114 /** Convert a rate in bytes per second to a rate in bytes per step */
116 rate_per_sec_to_rate_per_step(uint32_t rate
)
119 The precise calculation we'd want to do is
121 (rate / 1000) * to_approximate_msec(TICKS_PER_STEP). But to minimize
122 rounding error, we do it this way instead, and divide last.
124 uint64_t units
= (uint64_t) rate
* TICKS_PER_STEP
;
125 uint32_t val
= (uint32_t)
126 (monotime_coarse_stamp_units_to_approx_msec(units
) / 1000);
127 return val
? val
: 1;
131 * Initialize a token bucket in *<b>bucket</b>, set up to allow <b>rate</b>
132 * bytes per second, with a maximum burst of <b>burst</b> bytes. The bucket
133 * is created such that <b>now_ts</b> is the current timestamp. The bucket
137 token_bucket_rw_init(token_bucket_rw_t
*bucket
,
142 memset(bucket
, 0, sizeof(token_bucket_rw_t
));
143 token_bucket_rw_adjust(bucket
, rate
, burst
);
144 token_bucket_rw_reset(bucket
, now_ts
);
148 * Change the configured rate (in bytes per second) and burst (in bytes)
149 * for the token bucket in *<b>bucket</b>.
152 token_bucket_rw_adjust(token_bucket_rw_t
*bucket
,
156 token_bucket_cfg_init(&bucket
->cfg
,
157 rate_per_sec_to_rate_per_step(rate
),
159 token_bucket_raw_adjust(&bucket
->read_bucket
, &bucket
->cfg
);
160 token_bucket_raw_adjust(&bucket
->write_bucket
, &bucket
->cfg
);
164 * Reset <b>bucket</b> to be full, as of timestamp <b>now_ts</b>.
167 token_bucket_rw_reset(token_bucket_rw_t
*bucket
,
170 token_bucket_raw_reset(&bucket
->read_bucket
, &bucket
->cfg
);
171 token_bucket_raw_reset(&bucket
->write_bucket
, &bucket
->cfg
);
172 bucket
->last_refilled_at_timestamp
= now_ts
;
176 * Refill <b>bucket</b> as appropriate, given that the current timestamp
179 * Return a bitmask containing TB_READ iff read bucket was empty and became
180 * nonempty, and TB_WRITE iff the write bucket was empty and became nonempty.
183 token_bucket_rw_refill(token_bucket_rw_t
*bucket
,
186 const uint32_t elapsed_ticks
=
187 (now_ts
- bucket
->last_refilled_at_timestamp
);
188 if (elapsed_ticks
> UINT32_MAX
-(300*1000)) {
189 /* Either about 48 days have passed since the last refill, or the
190 * monotonic clock has somehow moved backwards. (We're looking at you,
191 * Windows.). We accept up to a 5 minute jump backwards as
196 const uint32_t elapsed_steps
= elapsed_ticks
/ TICKS_PER_STEP
;
198 if (!elapsed_steps
) {
199 /* Note that if less than one whole step elapsed, we don't advance the
200 * time in last_refilled_at. That's intentional: we want to make sure
201 * that we add some bytes to it eventually. */
206 if (token_bucket_raw_refill_steps(&bucket
->read_bucket
,
207 &bucket
->cfg
, elapsed_steps
))
209 if (token_bucket_raw_refill_steps(&bucket
->write_bucket
,
210 &bucket
->cfg
, elapsed_steps
))
213 bucket
->last_refilled_at_timestamp
= now_ts
;
218 * Decrement the read token bucket in <b>bucket</b> by <b>n</b> bytes.
220 * Return true if the bucket was nonempty and became empty; return false
224 token_bucket_rw_dec_read(token_bucket_rw_t
*bucket
,
227 return token_bucket_raw_dec(&bucket
->read_bucket
, n
);
231 * Decrement the write token bucket in <b>bucket</b> by <b>n</b> bytes.
233 * Return true if the bucket was nonempty and became empty; return false
237 token_bucket_rw_dec_write(token_bucket_rw_t
*bucket
,
240 return token_bucket_raw_dec(&bucket
->write_bucket
, n
);
244 * As token_bucket_rw_dec_read and token_bucket_rw_dec_write, in a single
245 * operation. Return a bitmask of TB_READ and TB_WRITE to indicate
246 * which buckets became empty.
249 token_bucket_rw_dec(token_bucket_rw_t
*bucket
,
250 ssize_t n_read
, ssize_t n_written
)
253 if (token_bucket_rw_dec_read(bucket
, n_read
))
255 if (token_bucket_rw_dec_write(bucket
, n_written
))
260 /** Initialize a token bucket in <b>bucket</b>, set up to allow <b>rate</b>
261 * per second, with a maximum burst of <b>burst</b>. The bucket is created
262 * such that <b>now_ts</b> is the current timestamp. The bucket starts out
265 token_bucket_ctr_init(token_bucket_ctr_t
*bucket
, uint32_t rate
,
266 uint32_t burst
, uint32_t now_ts
)
268 memset(bucket
, 0, sizeof(token_bucket_ctr_t
));
269 token_bucket_ctr_adjust(bucket
, rate
, burst
);
270 token_bucket_ctr_reset(bucket
, now_ts
);
273 /** Change the configured rate and burst of the given token bucket object in
276 token_bucket_ctr_adjust(token_bucket_ctr_t
*bucket
, uint32_t rate
,
279 token_bucket_cfg_init(&bucket
->cfg
, rate
, burst
);
280 token_bucket_raw_adjust(&bucket
->counter
, &bucket
->cfg
);
283 /** Reset <b>bucket</b> to be full, as of timestamp <b>now_ts</b>. */
285 token_bucket_ctr_reset(token_bucket_ctr_t
*bucket
, uint32_t now_ts
)
287 token_bucket_raw_reset(&bucket
->counter
, &bucket
->cfg
);
288 bucket
->last_refilled_at_timestamp
= now_ts
;
291 /** Refill <b>bucket</b> as appropriate, given that the current timestamp is
294 token_bucket_ctr_refill(token_bucket_ctr_t
*bucket
, uint32_t now_ts
)
296 const uint32_t elapsed_ticks
=
297 (now_ts
- bucket
->last_refilled_at_timestamp
);
298 if (elapsed_ticks
> UINT32_MAX
-(300*1000)) {
299 /* Either about 48 days have passed since the last refill, or the
300 * monotonic clock has somehow moved backwards. (We're looking at you,
301 * Windows.). We accept up to a 5 minute jump backwards as
307 token_bucket_raw_refill_steps(&bucket
->counter
, &bucket
->cfg
,
309 bucket
->last_refilled_at_timestamp
= now_ts
;