Module bw_pool 

A shared token pool with a lock-free fast path and FIFO waiting queue.

BandwidthPool is a set of tokens that many tasks can draw from concurrently representing a bandwidth Permit. Deciding how many tokens become available and when is the job of the BandwidthRefiller which should be run in a task that has a reference to the pool’s token bucket.

Pool

The pool holds the bandwidth token balance (bucket) available for any BandwidthAcquirer to attempt to acquire concurrently.

The BandwidthPool can be shared between an arbitrary amount of tasks and each task needs to get a BandwidthAcquirer from the BandwidthPool::new_acquirer method.

The acquirer is designed to be allocated once and reused throughout the owner object lifetime, thereby reducing the number of allocations needed at runtime.

In order to be granted permission to use a certain number of tokens, the task needs to call BandwidthAcquirer::poll_acquire with the number of tokens it wants. It has to be called in the context of a task so it can be woken up once it is granted.

Acquisition Mechanism

The pool design is that there is a so called fast-path that is meant to allow a thundering herd to attempt to acquire tokens in an atomic way as long as the pool has available tokens.

Once the pool is empty, new acquire requests go into a FIFO queue for fairness and are served as the pool gets refilled by the BandwidthRefiller task.

A Permit is handed out once the full requested amount has been deducted from the pool as in available. The permit holds the granted tokens and the holder claims what it actually uses with Permit::claim (or Permit::claim_all). Whatever is left unclaimed in the permit is refunded to the pool when it is dropped.

Refund

Refunded tokens always go back to the fast-path pool where they are immediately available. A newcomer can acquire them while another request is queued but before the BandwidthRefiller drains the pool. This favors keeping the fast path busy over strict fairness between the fast path and the waiting queue.

Teardown

There is deliberately no cancellation mechanism for a queued request. If a BandwidthAcquirer is torn down while its request is queued, the refiller will eventually fund that request anyway, record the grant, and wake a task that no longer exists. The granted tokens are simply forfeited.

This is a considered trade-off and we believe in the context of a Tor relay, losing a grant is not significant at all in the large picture of available bandwidth. The trade-off allows us to reduce a lot of complexity.

Modules

bucket 🔒

An atomic and shareable token bucket BUT with one caveat, it is without the clock component that is the refill is not taking into account any rate or time tracking.

refiller 🔒

The refiller code that is the BandwidthRefiller is a public entity that needs to run into its own task and refill the associated super::BandwidthPool and serve any RefillWaiter pending on the pool to be replenished.

Structs

BandwidthAcquirer

A reusable bandwidth acquirer that is designed for an async context (poll).

BandwidthPool

A shareable bandwidth pool.

BandwidthRefiller

A bandwidth refiller is in charge of refilling the associated super::BandwidthPool and processing any pending RefillWaiter that were enqueued by the pool.

Permit

Proof that the requested number of tokens were granted.

Enums

BwPoolError

Error returned by this module.