2 * Copyright (c) 2012 Nicira, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at:
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
19 #include "token-bucket.h"
21 #include "poll-loop.h"
26 /* Initializes 'tb' to accumulate 'rate' tokens per millisecond, with a
27 * maximum of 'burst' tokens.
29 * The token bucket is initially full.
31 * It may be more convenient to use TOKEN_BUCKET_INIT. */
33 token_bucket_init(struct token_bucket *tb,
34 unsigned int rate, unsigned int burst)
39 tb->last_fill = LLONG_MIN;
42 /* Changes 'tb' to accumulate 'rate' tokens per millisecond, with a maximum of
45 * 'tb' must already have been initialized with TOKEN_BUCKET_INIT or
46 * token_bucket_init(). */
48 token_bucket_set(struct token_bucket *tb,
49 unsigned int rate, unsigned int burst)
53 if (burst > tb->tokens) {
58 /* Attempts to remove 'n' tokens from 'tb'. Returns true if successful, false
59 * if 'tb' contained fewer than 'n' tokens (and thus 'n' tokens could not be
62 token_bucket_withdraw(struct token_bucket *tb, unsigned int n)
65 long long int now = time_msec();
66 if (now > tb->last_fill) {
67 unsigned long long int elapsed_ull
68 = (unsigned long long int) now - tb->last_fill;
69 unsigned int elapsed = MIN(UINT_MAX, elapsed_ull);
70 unsigned int add = sat_mul(tb->rate, elapsed);
71 unsigned int tokens = sat_add(tb->tokens, add);
72 tb->tokens = MIN(tokens, tb->burst);
85 /* Causes the poll loop to wake up when at least 'n' tokens will be available
86 * for withdrawal from 'tb'. */
88 token_bucket_wait(struct token_bucket *tb, unsigned int n)
90 if (tb->tokens >= n) {
91 poll_immediate_wake();
93 unsigned int need = n - tb->tokens;
94 poll_timer_wait_until(tb->last_fill + need / tb->rate + 1);