token_bucket.c File Reference

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

#include "token_bucket.h"
#include "util_bug.h"

Include dependency graph for token_bucket.c:

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)

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.

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

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Here is the caller graph for this function:

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.

Here is the caller graph for this function:

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.

Here is the caller graph for this function:

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.

Here is the caller graph for this function:

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.

Here is the caller graph for this function:

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.

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Here is the call graph for this function:

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.

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Here is the call graph for this function:

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.

Here is the call graph for this function:

Here is the caller graph for this function: