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