/src/openvswitch/lib/token-bucket.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Copyright (c) 2012 Nicira, Inc. |
3 | | * |
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: |
7 | | * |
8 | | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | | * |
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. |
15 | | */ |
16 | | |
17 | | #include <config.h> |
18 | | |
19 | | #include "openvswitch/token-bucket.h" |
20 | | |
21 | | #include "openvswitch/poll-loop.h" |
22 | | #include "sat-math.h" |
23 | | #include "timeval.h" |
24 | | #include "util.h" |
25 | | |
26 | | /* Initializes 'tb' to accumulate 'rate' tokens per millisecond, with a |
27 | | * maximum of 'burst' tokens. |
28 | | * |
29 | | * The token bucket is initially full. |
30 | | * |
31 | | * It may be more convenient to use TOKEN_BUCKET_INIT. */ |
32 | | void |
33 | | token_bucket_init(struct token_bucket *tb, |
34 | | unsigned int rate, unsigned int burst) |
35 | 0 | { |
36 | 0 | tb->rate = rate; |
37 | 0 | tb->burst = burst; |
38 | 0 | tb->tokens = 0; |
39 | 0 | tb->last_fill = LLONG_MIN; |
40 | 0 | } |
41 | | |
42 | | /* Changes 'tb' to accumulate 'rate' tokens per millisecond, with a maximum of |
43 | | * 'burst' tokens. |
44 | | * |
45 | | * 'tb' must already have been initialized with TOKEN_BUCKET_INIT or |
46 | | * token_bucket_init(). */ |
47 | | void |
48 | | token_bucket_set(struct token_bucket *tb, |
49 | | unsigned int rate, unsigned int burst) |
50 | 0 | { |
51 | 0 | tb->rate = rate; |
52 | 0 | tb->burst = burst; |
53 | 0 | if (burst < tb->tokens) { |
54 | 0 | tb->tokens = burst; |
55 | 0 | } |
56 | 0 | } |
57 | | |
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 |
60 | | * removed) . */ |
61 | | bool |
62 | | token_bucket_withdraw(struct token_bucket *tb, unsigned int n) |
63 | 0 | { |
64 | 0 | if (tb->tokens < n) { |
65 | 0 | long long int now = time_msec(); |
66 | 0 | if (now > tb->last_fill) { |
67 | 0 | unsigned long long int elapsed_ull |
68 | 0 | = (unsigned long long int) now - tb->last_fill; |
69 | 0 | unsigned int elapsed = MIN(UINT_MAX, elapsed_ull); |
70 | 0 | unsigned int add = sat_mul(tb->rate, elapsed); |
71 | 0 | unsigned int tokens = sat_add(tb->tokens, add); |
72 | 0 | tb->tokens = MIN(tokens, tb->burst); |
73 | 0 | tb->last_fill = now; |
74 | 0 | } |
75 | |
|
76 | 0 | if (tb->tokens < n) { |
77 | 0 | return false; |
78 | 0 | } |
79 | 0 | } |
80 | | |
81 | 0 | tb->tokens -= n; |
82 | 0 | return true; |
83 | 0 | } |
84 | | |
85 | | /* Causes the poll loop to wake up when at least 'n' tokens will be available |
86 | | * for withdrawal from 'tb'. */ |
87 | | void |
88 | | token_bucket_wait_at(struct token_bucket *tb, unsigned int n, |
89 | | const char *where) |
90 | 0 | { |
91 | 0 | if (tb->tokens >= n) { |
92 | 0 | poll_immediate_wake_at(where); |
93 | 0 | } else { |
94 | 0 | unsigned int need = n - tb->tokens; |
95 | 0 | poll_timer_wait_until_at(tb->last_fill + need / tb->rate + 1, where); |
96 | 0 | } |
97 | 0 | } |