VNFs/DPPD-PROX/token_time.h

   1 /*
   2 // Copyright (c) 2010-2017 Intel Corporation
   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 #ifndef _TOKEN_TIME_H_
  18 #define _TOKEN_TIME_H_
  19
  20 #include <rte_cycles.h>
  21 #include <math.h>
  22
  23 #include "prox_assert.h"
  24
  25 struct token_time_cfg {
  26         uint64_t bpp;
  27         uint64_t period;
  28         uint64_t bytes_max;
  29 };
  30
  31 struct token_time {
  32         uint64_t tsc_last;
  33         uint64_t tsc_last_bytes;
  34         uint64_t bytes_now;
  35         struct token_time_cfg cfg;
  36 };
  37
  38 /* Convert a given fractional bytes per period into bpp with as
  39    minimal loss of accuracy. */
  40 static struct token_time_cfg token_time_cfg_create(double frac, uint64_t period, uint64_t bytes_max)
  41 {
  42         struct token_time_cfg ret;
  43
  44         /* Since period is expressed in units of cycles and it is in
  45            most cases set to 1 second (which means its value is <=
  46            3*10^9) and 2^64/10^9 > 6148914691 > 2^32). This means that
  47            at most, period and frac will be doubled 32 times by the
  48            following algorithm. Hence, the total error introduced by
  49            the chosen values for bpp and period will be between 0 and
  50            1/2^33. Note that since there are more operations that
  51            can't overflow, the actual accuracy will probably be
  52            lower. */
  53
  54         /* The reason to limit period by UINT64_MAX/(uint64_t)frac is
  55            that at run-time, the token_time_update function will
  56            multiply a number that is <= period with bpp. In addition,
  57            the token_time_tsc_until function will multiply at most
  58            bytes_max with period so make sure that can't overflow. */
  59
  60         while (period < UINT64_MAX/2 && frac != floor(frac) &&
  61                (frac < 2.0f || period < UINT64_MAX/4/(uint64_t)frac) &&
  62                (bytes_max == UINT64_MAX || period < UINT64_MAX/2/bytes_max)) {
  63                 period *= 2;
  64                 frac *= 2;
  65         }
  66
  67         ret.bpp = floor(frac + 0.5);
  68         ret.period = period;
  69         ret.bytes_max = bytes_max;
  70
  71         return ret;
  72 }
  73
  74 static void token_time_update(struct token_time *tt, uint64_t tsc)
  75 {
  76         uint64_t new_bytes;
  77         uint64_t t_diff = tsc - tt->tsc_last;
  78
  79         /* Since the rate is expressed in tt->bpp, i.e. bytes per
  80            period, counters can only be incremented/decremented
  81            accurately every period cycles. */
  82
  83         /* If the last update was more than a period ago, the update
  84            can be performed accurately. */
  85         if (t_diff > tt->cfg.period) {
  86                 /* First add remaining tokens in the last period that
  87                    was added partially. */
  88                 new_bytes = tt->cfg.bpp - tt->tsc_last_bytes;
  89                 tt->tsc_last_bytes = 0;
  90                 tt->bytes_now += new_bytes;
  91                 t_diff -= tt->cfg.period;
  92                 tt->tsc_last += tt->cfg.period;
  93
  94                 /* If now it turns out that more periods have elapsed,
  95                    add the bytes for those periods directly. */
  96                 if (t_diff > tt->cfg.period) {
  97                         uint64_t periods = t_diff/tt->cfg.period;
  98
  99                         tt->bytes_now += periods * tt->cfg.bpp;
 100                         t_diff -= tt->cfg.period * periods;
 101                         tt->tsc_last += tt->cfg.period * periods;
 102                 }
 103         }
 104
 105         /* At this point, t_diff will be guaranteed to be less
 106            than tt->cfg.period. */
 107         new_bytes = t_diff * tt->cfg.bpp/tt->cfg.period - tt->tsc_last_bytes;
 108         tt->tsc_last_bytes += new_bytes;
 109         tt->bytes_now += new_bytes;
 110         if (tt->bytes_now > tt->cfg.bytes_max)
 111                 tt->bytes_now = tt->cfg.bytes_max;
 112 }
 113
 114 static void token_time_set_bpp(struct token_time *tt, uint64_t bpp)
 115 {
 116         tt->cfg.bpp = bpp;
 117 }
 118
 119 static void token_time_init(struct token_time *tt, const struct token_time_cfg *cfg)
 120 {
 121         tt->cfg = *cfg;
 122 }
 123
 124 static void token_time_reset(struct token_time *tt, uint64_t tsc, uint64_t bytes_now)
 125 {
 126         tt->tsc_last = tsc;
 127         tt->bytes_now = bytes_now;
 128         tt->tsc_last_bytes = 0;
 129 }
 130
 131 static void token_time_reset_full(struct token_time *tt, uint64_t tsc)
 132 {
 133         token_time_reset(tt, tsc, tt->cfg.bytes_max);
 134 }
 135
 136 static int token_time_take(struct token_time *tt, uint64_t bytes)
 137 {
 138         if (bytes > tt->bytes_now)
 139                 return -1;
 140         tt->bytes_now -= bytes;
 141         return 0;
 142 }
 143
 144 static void token_time_take_clamp(struct token_time *tt, uint64_t bytes)
 145 {
 146         if (bytes > tt->bytes_now)
 147                 tt->bytes_now = 0;
 148         else
 149                 tt->bytes_now -= bytes;
 150 }
 151
 152 static uint64_t token_time_tsc_until(const struct token_time *tt, uint64_t bytes)
 153 {
 154         if (tt->bytes_now >= bytes)
 155                 return 0;
 156
 157         return (bytes - tt->bytes_now) * tt->cfg.period / tt->cfg.bpp;
 158 }
 159
 160 static uint64_t token_time_tsc_until_full(const struct token_time *tt)
 161 {
 162         return token_time_tsc_until(tt, tt->cfg.bytes_max);
 163 }
 164
 165 #endif /* _TOKEN_TIME_H_ */