Tor  0.4.7.0-alpha-dev
Macros | Functions
token_bucket.c File Reference

Functions to use and manipulate token buckets, used for rate-limiting on connections and globally. More...

#include "lib/evloop/token_bucket.h"
#include "lib/log/util_bug.h"
#include "lib/intmath/cmp.h"
#include "lib/time/compat_time.h"
#include <string.h>

Go to the source code of this file.

Functions

void token_bucket_cfg_init (token_bucket_cfg_t *cfg, uint32_t rate, uint32_t burst)
 
void token_bucket_raw_reset (token_bucket_raw_t *bucket, const token_bucket_cfg_t *cfg)
 
void token_bucket_raw_adjust (token_bucket_raw_t *bucket, const token_bucket_cfg_t *cfg)
 
int token_bucket_raw_refill_steps (token_bucket_raw_t *bucket, const token_bucket_cfg_t *cfg, const uint32_t elapsed)
 
int token_bucket_raw_dec (token_bucket_raw_t *bucket, ssize_t n)
 
STATIC uint32_t rate_per_sec_to_rate_per_step (uint32_t rate)
 
void token_bucket_rw_init (token_bucket_rw_t *bucket, uint32_t rate, uint32_t burst, uint32_t now_ts)
 
void token_bucket_rw_adjust (token_bucket_rw_t *bucket, uint32_t rate, uint32_t burst)
 
void token_bucket_rw_reset (token_bucket_rw_t *bucket, uint32_t now_ts)
 
int token_bucket_rw_refill (token_bucket_rw_t *bucket, uint32_t now_ts)
 
int token_bucket_rw_dec_read (token_bucket_rw_t *bucket, ssize_t n)
 
int token_bucket_rw_dec_write (token_bucket_rw_t *bucket, ssize_t n)
 
int token_bucket_rw_dec (token_bucket_rw_t *bucket, ssize_t n_read, ssize_t n_written)
 
void token_bucket_ctr_init (token_bucket_ctr_t *bucket, uint32_t rate, uint32_t burst, uint32_t now_ts)
 
void token_bucket_ctr_adjust (token_bucket_ctr_t *bucket, uint32_t rate, uint32_t burst)
 
void token_bucket_ctr_reset (token_bucket_ctr_t *bucket, uint32_t now_ts)
 
void token_bucket_ctr_refill (token_bucket_ctr_t *bucket, uint32_t now_ts)
 

Detailed Description

Functions to use and manipulate token buckets, used for rate-limiting on connections and globally.

Tor uses these token buckets to keep track of bandwidth usage, and sometimes other things too.

There are two layers of abstraction here: "raw" token buckets, in which all the pieces are decoupled, and "read-write" token buckets, which combine all the moving parts into one.

Token buckets may become negative.

Definition in file token_bucket.c.

Function Documentation

◆ rate_per_sec_to_rate_per_step()

STATIC uint32_t rate_per_sec_to_rate_per_step ( uint32_t  rate)

Convert a rate in bytes per second to a rate in bytes per step

Definition at line 116 of file token_bucket.c.

Referenced by token_bucket_rw_adjust().

◆ token_bucket_cfg_init()

void token_bucket_cfg_init ( token_bucket_cfg_t cfg,
uint32_t  rate,
uint32_t  burst 
)

Set the rate and burst value in a token_bucket_cfg.

Note that the rate value is in arbitrary units, but those units will determine the units of token_bucket_raw_dec(), token_bucket_raw_refill, and so on.

Definition at line 36 of file token_bucket.c.

Referenced by token_bucket_ctr_adjust(), and token_bucket_rw_adjust().

◆ token_bucket_ctr_adjust()

void token_bucket_ctr_adjust ( token_bucket_ctr_t bucket,
uint32_t  rate,
uint32_t  burst 
)

Change the configured rate and burst of the given token bucket object in bucket.

Definition at line 276 of file token_bucket.c.

Referenced by token_bucket_ctr_init().

◆ token_bucket_ctr_init()

void token_bucket_ctr_init ( token_bucket_ctr_t bucket,
uint32_t  rate,
uint32_t  burst,
uint32_t  now_ts 
)

Initialize a token bucket in bucket, set up to allow rate per second, with a maximum burst of burst. The bucket is created such that now_ts is the current timestamp. The bucket starts out full.

Definition at line 265 of file token_bucket.c.

◆ token_bucket_ctr_refill()

void token_bucket_ctr_refill ( token_bucket_ctr_t bucket,
uint32_t  now_ts 
)

Refill bucket as appropriate, given that the current timestamp is now_ts.

Definition at line 294 of file token_bucket.c.

◆ token_bucket_ctr_reset()

void token_bucket_ctr_reset ( token_bucket_ctr_t bucket,
uint32_t  now_ts 
)

Reset bucket to be full, as of timestamp now_ts.

Definition at line 285 of file token_bucket.c.

Referenced by token_bucket_ctr_init().

◆ token_bucket_raw_adjust()

void token_bucket_raw_adjust ( token_bucket_raw_t bucket,
const token_bucket_cfg_t cfg 
)

Adust a preexisting token bucket to respect the new configuration cfg, by decreasing its current level if needed.

Definition at line 64 of file token_bucket.c.

Referenced by token_bucket_ctr_adjust(), and token_bucket_rw_adjust().

◆ token_bucket_raw_dec()

int token_bucket_raw_dec ( token_bucket_raw_t bucket,
ssize_t  n 
)

Decrement a provided bucket by n units. Note that n must be nonnegative.

Definition at line 104 of file token_bucket.c.

Referenced by token_bucket_rw_dec_read(), and token_bucket_rw_dec_write().

◆ token_bucket_raw_refill_steps()

int token_bucket_raw_refill_steps ( token_bucket_raw_t bucket,
const token_bucket_cfg_t cfg,
const uint32_t  elapsed 
)

Given an amount of elapsed time units, and a bucket configuration cfg, refill the level of bucket accordingly. Note that the units of time in elapsed must correspond to those used to set the rate in cfg, or the result will be illogical.

Definition at line 77 of file token_bucket.c.

Referenced by token_bucket_ctr_refill(), and token_bucket_rw_refill().

◆ token_bucket_raw_reset()

void token_bucket_raw_reset ( token_bucket_raw_t bucket,
const token_bucket_cfg_t cfg 
)

Initialize a raw token bucket and its associated timestamp to the "full" state, according to cfg.

Definition at line 54 of file token_bucket.c.

Referenced by token_bucket_ctr_reset(), and token_bucket_rw_reset().

◆ token_bucket_rw_adjust()

void token_bucket_rw_adjust ( token_bucket_rw_t bucket,
uint32_t  rate,
uint32_t  burst 
)

Change the configured rate (in bytes per second) and burst (in bytes) for the token bucket in *bucket.

Definition at line 152 of file token_bucket.c.

Referenced by connection_bucket_adjust(), connection_or_update_token_buckets_helper(), and token_bucket_rw_init().

◆ token_bucket_rw_dec()

int token_bucket_rw_dec ( token_bucket_rw_t bucket,
ssize_t  n_read,
ssize_t  n_written 
)

As token_bucket_rw_dec_read and token_bucket_rw_dec_write, in a single operation. Return a bitmask of TB_READ and TB_WRITE to indicate which buckets became empty.

Definition at line 249 of file token_bucket.c.

◆ token_bucket_rw_dec_read()

int token_bucket_rw_dec_read ( token_bucket_rw_t bucket,
ssize_t  n 
)

Decrement the read token bucket in bucket by n bytes.

Return true if the bucket was nonempty and became empty; return false otherwise.

Definition at line 224 of file token_bucket.c.

Referenced by token_bucket_rw_dec().

◆ token_bucket_rw_dec_write()

int token_bucket_rw_dec_write ( token_bucket_rw_t bucket,
ssize_t  n 
)

Decrement the write token bucket in bucket by n bytes.

Return true if the bucket was nonempty and became empty; return false otherwise.

Definition at line 237 of file token_bucket.c.

◆ token_bucket_rw_init()

void token_bucket_rw_init ( token_bucket_rw_t bucket,
uint32_t  rate,
uint32_t  burst,
uint32_t  now_ts 
)

Initialize a token bucket in *bucket, set up to allow rate bytes per second, with a maximum burst of burst bytes. The bucket is created such that now_ts is the current timestamp. The bucket starts out full.

Definition at line 137 of file token_bucket.c.

Referenced by connection_bucket_init().

◆ token_bucket_rw_refill()

int token_bucket_rw_refill ( token_bucket_rw_t bucket,
uint32_t  now_ts 
)

Refill bucket as appropriate, given that the current timestamp is now_ts.

Return a bitmask containing TB_READ iff read bucket was empty and became nonempty, and TB_WRITE iff the write bucket was empty and became nonempty.

Definition at line 183 of file token_bucket.c.

Referenced by connection_bucket_refill_single().

◆ token_bucket_rw_reset()

void token_bucket_rw_reset ( token_bucket_rw_t bucket,
uint32_t  now_ts 
)

Reset bucket to be full, as of timestamp now_ts.

Definition at line 167 of file token_bucket.c.

Referenced by connection_or_update_token_buckets_helper(), and token_bucket_rw_init().