Branch data     Line data    Source code

       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 "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                 :          0 : token_bucket_init(struct token_bucket *tb,
      34                 :            :                   unsigned int rate, unsigned int burst)
      35                 :            : {
      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                 :          0 : token_bucket_set(struct token_bucket *tb,
      49                 :            :                  unsigned int rate, unsigned int burst)
      50                 :            : {
      51                 :          0 :     tb->rate = rate;
      52                 :          0 :     tb->burst = burst;
      53         [ #  # ]:          0 :     if (burst < tb->tokens) {
      54                 :          0 :         tb->tokens = burst;
      55                 :            :     }
      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                 :     106888 : token_bucket_withdraw(struct token_bucket *tb, unsigned int n)
      63                 :            : {
      64         [ +  + ]:     106888 :     if (tb->tokens < n) {
      65                 :      59706 :         long long int now = time_msec();
      66         [ +  + ]:      59706 :         if (now > tb->last_fill) {
      67                 :      14715 :             unsigned long long int elapsed_ull
      68                 :      14715 :                 = (unsigned long long int) now - tb->last_fill;
      69                 :      14715 :             unsigned int elapsed = MIN(UINT_MAX, elapsed_ull);
      70                 :      14715 :             unsigned int add = sat_mul(tb->rate, elapsed);
      71                 :      14715 :             unsigned int tokens = sat_add(tb->tokens, add);
      72                 :      14715 :             tb->tokens = MIN(tokens, tb->burst);
      73                 :      14715 :             tb->last_fill = now;
      74                 :            :         }
      75                 :            : 
      76         [ +  + ]:      59706 :         if (tb->tokens < n) {
      77                 :      56926 :             return false;
      78                 :            :         }
      79                 :            :     }
      80                 :            : 
      81                 :      49962 :     tb->tokens -= n;
      82                 :      49962 :     return true;
      83                 :            : }
      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                 :          0 : token_bucket_wait(struct token_bucket *tb, unsigned int n)
      89                 :            : {
      90         [ #  # ]:          0 :     if (tb->tokens >= n) {
      91                 :          0 :         poll_immediate_wake();
      92                 :            :     } else {
      93                 :          0 :         unsigned int need = n - tb->tokens;
      94                 :          0 :         poll_timer_wait_until(tb->last_fill + need / tb->rate + 1);
      95                 :            :     }
      96                 :          0 : }