1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2010-2014 Intel Corporation
3 */
4
5 #ifndef __RTE_RED_H_INCLUDED__
6 #define __RTE_RED_H_INCLUDED__
7
8 #ifdef __cplusplus
9 extern "C" {
10 #endif
11
12 /**
13 * @file
14 * RTE Random Early Detection (RED)
15 *
16 *
17 ***/
18
19 #include <stdint.h>
20 #include <limits.h>
21 #include <rte_debug.h>
22 #include <rte_cycles.h>
23 #include <rte_branch_prediction.h>
24
25 #define RTE_RED_SCALING 10 /**< Fraction size for fixed-point */
26 #define RTE_RED_S (1 << 22) /**< Packet size multiplied by number of leaf queues */
27 #define RTE_RED_MAX_TH_MAX 1023 /**< Max threshold limit in fixed point format */
28 #define RTE_RED_WQ_LOG2_MIN 1 /**< Min inverse filter weight value */
29 #define RTE_RED_WQ_LOG2_MAX 12 /**< Max inverse filter weight value */
30 #define RTE_RED_MAXP_INV_MIN 1 /**< Min inverse mark probability value */
31 #define RTE_RED_MAXP_INV_MAX 255 /**< Max inverse mark probability value */
32 #define RTE_RED_2POW16 (1<<16) /**< 2 power 16 */
33 #define RTE_RED_INT16_NBITS (sizeof(uint16_t) * CHAR_BIT)
34 #define RTE_RED_WQ_LOG2_NUM (RTE_RED_WQ_LOG2_MAX - RTE_RED_WQ_LOG2_MIN + 1)
35
36 /**
37 * Externs
38 *
39 */
40 extern uint32_t rte_red_rand_val;
41 extern uint32_t rte_red_rand_seed;
42 extern uint16_t rte_red_log2_1_minus_Wq[RTE_RED_WQ_LOG2_NUM];
43 extern uint16_t rte_red_pow2_frac_inv[16];
44
45 /**
46 * RED configuration parameters passed by user
47 *
48 */
49 struct rte_red_params {
50 uint16_t min_th; /**< Minimum threshold for queue (max_th) */
51 uint16_t max_th; /**< Maximum threshold for queue (max_th) */
52 uint16_t maxp_inv; /**< Inverse of packet marking probability maximum value (maxp = 1 / maxp_inv) */
53 uint16_t wq_log2; /**< Negated log2 of queue weight (wq = 1 / (2 ^ wq_log2)) */
54 };
55
56 /**
57 * RED configuration parameters
58 */
59 struct rte_red_config {
60 uint32_t min_th; /**< min_th scaled in fixed-point format */
61 uint32_t max_th; /**< max_th scaled in fixed-point format */
62 uint32_t pa_const; /**< Precomputed constant value used for pa calculation (scaled in fixed-point format) */
63 uint8_t maxp_inv; /**< maxp_inv */
64 uint8_t wq_log2; /**< wq_log2 */
65 };
66
67 /**
68 * RED run-time data
69 */
70 struct rte_red {
71 uint32_t avg; /**< Average queue size (avg), scaled in fixed-point format */
72 uint32_t count; /**< Number of packets since last marked packet (count) */
73 uint64_t q_time; /**< Start of the queue idle time (q_time) */
74 };
75
76 /**
77 * @brief Initialises run-time data
78 *
79 * @param red [in,out] data pointer to RED runtime data
80 *
81 * @return Operation status
82 * @retval 0 success
83 * @retval !0 error
84 */
85 int
86 rte_red_rt_data_init(struct rte_red *red);
87
88 /**
89 * @brief Configures a single RED configuration parameter structure.
90 *
91 * @param red_cfg [in,out] config pointer to a RED configuration parameter structure
92 * @param wq_log2 [in] log2 of the filter weight, valid range is:
93 * RTE_RED_WQ_LOG2_MIN <= wq_log2 <= RTE_RED_WQ_LOG2_MAX
94 * @param min_th [in] queue minimum threshold in number of packets
95 * @param max_th [in] queue maximum threshold in number of packets
96 * @param maxp_inv [in] inverse maximum mark probability
97 *
98 * @return Operation status
99 * @retval 0 success
100 * @retval !0 error
101 */
102 int
103 rte_red_config_init(struct rte_red_config *red_cfg,
104 const uint16_t wq_log2,
105 const uint16_t min_th,
106 const uint16_t max_th,
107 const uint16_t maxp_inv);
108
109 /**
110 * @brief Generate random number for RED
111 *
112 * Implementation based on:
113 * http://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor/
114 *
115 * 10 bit shift has been found through empirical tests (was 16).
116 *
117 * @return Random number between 0 and (2^22 - 1)
118 */
119 static inline uint32_t
rte_fast_rand(void)120 rte_fast_rand(void)
121 {
122 rte_red_rand_seed = (214013 * rte_red_rand_seed) + 2531011;
123 return rte_red_rand_seed >> 10;
124 }
125
126 /**
127 * @brief calculate factor to scale average queue size when queue
128 * becomes empty
129 *
130 * @param wq_log2 [in] where EWMA filter weight wq = 1/(2 ^ wq_log2)
131 * @param m [in] exponent in the computed value (1 - wq) ^ m
132 *
133 * @return computed value
134 * @retval ((1 - wq) ^ m) scaled in fixed-point format
135 */
136 static inline uint16_t
__rte_red_calc_qempty_factor(uint8_t wq_log2,uint16_t m)137 __rte_red_calc_qempty_factor(uint8_t wq_log2, uint16_t m)
138 {
139 uint32_t n = 0;
140 uint32_t f = 0;
141
142 /**
143 * Basic math tells us that:
144 * a^b = 2^(b * log2(a) )
145 *
146 * in our case:
147 * a = (1-Wq)
148 * b = m
149 * Wq = 1/ (2^log2n)
150 *
151 * So we are computing this equation:
152 * factor = 2 ^ ( m * log2(1-Wq))
153 *
154 * First we are computing:
155 * n = m * log2(1-Wq)
156 *
157 * To avoid dealing with signed numbers log2 values are positive
158 * but they should be negative because (1-Wq) is always < 1.
159 * Contents of log2 table values are also scaled for precision.
160 */
161
162 n = m * rte_red_log2_1_minus_Wq[wq_log2 - RTE_RED_WQ_LOG2_MIN];
163
164 /**
165 * The tricky part is computing 2^n, for this I split n into
166 * integer part and fraction part.
167 * f - is fraction part of n
168 * n - is integer part of original n
169 *
170 * Now using basic math we compute 2^n:
171 * 2^(f+n) = 2^f * 2^n
172 * 2^f - we use lookup table
173 * 2^n - can be replaced with bit shift right operations
174 */
175
176 f = (n >> 6) & 0xf;
177 n >>= 10;
178
179 if (n < RTE_RED_SCALING)
180 return (uint16_t) ((rte_red_pow2_frac_inv[f] + (1 << (n - 1))) >> n);
181
182 return 0;
183 }
184
185 /**
186 * @brief Updates queue average in condition when queue is empty
187 *
188 * Note: packet is never dropped in this particular case.
189 *
190 * @param red_cfg [in] config pointer to a RED configuration parameter structure
191 * @param red [in,out] data pointer to RED runtime data
192 * @param time [in] current time stamp
193 *
194 * @return Operation status
195 * @retval 0 enqueue the packet
196 * @retval 1 drop the packet based on max threshold criterion
197 * @retval 2 drop the packet based on mark probability criterion
198 */
199 static inline int
rte_red_enqueue_empty(const struct rte_red_config * red_cfg,struct rte_red * red,const uint64_t time)200 rte_red_enqueue_empty(const struct rte_red_config *red_cfg,
201 struct rte_red *red,
202 const uint64_t time)
203 {
204 uint64_t time_diff = 0, m = 0;
205
206 RTE_ASSERT(red_cfg != NULL);
207 RTE_ASSERT(red != NULL);
208
209 red->count ++;
210
211 /**
212 * We compute avg but we don't compare avg against
213 * min_th or max_th, nor calculate drop probability
214 */
215 time_diff = time - red->q_time;
216
217 /**
218 * m is the number of packets that might have arrived while the queue was empty.
219 * In this case we have time stamps provided by scheduler in byte units (bytes
220 * transmitted on network port). Such time stamp translates into time units as
221 * port speed is fixed but such approach simplifies the code.
222 */
223 m = time_diff / RTE_RED_S;
224
225 /**
226 * Check that m will fit into 16-bit unsigned integer
227 */
228 if (m >= RTE_RED_2POW16) {
229 red->avg = 0;
230 } else {
231 red->avg = (red->avg >> RTE_RED_SCALING) * __rte_red_calc_qempty_factor(red_cfg->wq_log2, (uint16_t) m);
232 }
233
234 return 0;
235 }
236
237 /**
238 * Drop probability (Sally Floyd and Van Jacobson):
239 *
240 * pb = (1 / maxp_inv) * (avg - min_th) / (max_th - min_th)
241 * pa = pb / (2 - count * pb)
242 *
243 *
244 * (1 / maxp_inv) * (avg - min_th)
245 * ---------------------------------
246 * max_th - min_th
247 * pa = -----------------------------------------------
248 * count * (1 / maxp_inv) * (avg - min_th)
249 * 2 - -----------------------------------------
250 * max_th - min_th
251 *
252 *
253 * avg - min_th
254 * pa = -----------------------------------------------------------
255 * 2 * (max_th - min_th) * maxp_inv - count * (avg - min_th)
256 *
257 *
258 * We define pa_const as: pa_const = 2 * (max_th - min_th) * maxp_inv. Then:
259 *
260 *
261 * avg - min_th
262 * pa = -----------------------------------
263 * pa_const - count * (avg - min_th)
264 */
265
266 /**
267 * @brief make a decision to drop or enqueue a packet based on mark probability
268 * criteria
269 *
270 * @param red_cfg [in] config pointer to structure defining RED parameters
271 * @param red [in,out] data pointer to RED runtime data
272 *
273 * @return operation status
274 * @retval 0 enqueue the packet
275 * @retval 1 drop the packet
276 */
277 static inline int
__rte_red_drop(const struct rte_red_config * red_cfg,struct rte_red * red)278 __rte_red_drop(const struct rte_red_config *red_cfg, struct rte_red *red)
279 {
280 uint32_t pa_num = 0; /* numerator of drop-probability */
281 uint32_t pa_den = 0; /* denominator of drop-probability */
282 uint32_t pa_num_count = 0;
283
284 pa_num = (red->avg - red_cfg->min_th) >> (red_cfg->wq_log2);
285
286 pa_num_count = red->count * pa_num;
287
288 if (red_cfg->pa_const <= pa_num_count)
289 return 1;
290
291 pa_den = red_cfg->pa_const - pa_num_count;
292
293 /* If drop, generate and save random number to be used next time */
294 if (unlikely((rte_red_rand_val % pa_den) < pa_num)) {
295 rte_red_rand_val = rte_fast_rand();
296
297 return 1;
298 }
299
300 /* No drop */
301 return 0;
302 }
303
304 /**
305 * @brief Decides if new packet should be enqueued or dropped in queue non-empty case
306 *
307 * @param red_cfg [in] config pointer to a RED configuration parameter structure
308 * @param red [in,out] data pointer to RED runtime data
309 * @param q [in] current queue size (measured in packets)
310 *
311 * @return Operation status
312 * @retval 0 enqueue the packet
313 * @retval 1 drop the packet based on max threshold criterion
314 * @retval 2 drop the packet based on mark probability criterion
315 */
316 static inline int
rte_red_enqueue_nonempty(const struct rte_red_config * red_cfg,struct rte_red * red,const unsigned q)317 rte_red_enqueue_nonempty(const struct rte_red_config *red_cfg,
318 struct rte_red *red,
319 const unsigned q)
320 {
321 RTE_ASSERT(red_cfg != NULL);
322 RTE_ASSERT(red != NULL);
323
324 /**
325 * EWMA filter (Sally Floyd and Van Jacobson):
326 * avg = (1 - wq) * avg + wq * q
327 * avg = avg + q * wq - avg * wq
328 *
329 * We select: wq = 2^(-n). Let scaled version of avg be: avg_s = avg * 2^(N+n). We get:
330 * avg_s = avg_s + q * 2^N - avg_s * 2^(-n)
331 *
332 * By using shift left/right operations, we get:
333 * avg_s = avg_s + (q << N) - (avg_s >> n)
334 * avg_s += (q << N) - (avg_s >> n)
335 */
336
337 /* avg update */
338 red->avg += (q << RTE_RED_SCALING) - (red->avg >> red_cfg->wq_log2);
339
340 /* avg < min_th: do not mark the packet */
341 if (red->avg < red_cfg->min_th) {
342 red->count ++;
343 return 0;
344 }
345
346 /* min_th <= avg < max_th: mark the packet with pa probability */
347 if (red->avg < red_cfg->max_th) {
348 if (!__rte_red_drop(red_cfg, red)) {
349 red->count ++;
350 return 0;
351 }
352
353 red->count = 0;
354 return 2;
355 }
356
357 /* max_th <= avg: always mark the packet */
358 red->count = 0;
359 return 1;
360 }
361
362 /**
363 * @brief Decides if new packet should be enqueued or dropped
364 * Updates run time data based on new queue size value.
365 * Based on new queue average and RED configuration parameters
366 * gives verdict whether to enqueue or drop the packet.
367 *
368 * @param red_cfg [in] config pointer to a RED configuration parameter structure
369 * @param red [in,out] data pointer to RED runtime data
370 * @param q [in] updated queue size in packets
371 * @param time [in] current time stamp
372 *
373 * @return Operation status
374 * @retval 0 enqueue the packet
375 * @retval 1 drop the packet based on max threshold criteria
376 * @retval 2 drop the packet based on mark probability criteria
377 */
378 static inline int
rte_red_enqueue(const struct rte_red_config * red_cfg,struct rte_red * red,const unsigned q,const uint64_t time)379 rte_red_enqueue(const struct rte_red_config *red_cfg,
380 struct rte_red *red,
381 const unsigned q,
382 const uint64_t time)
383 {
384 RTE_ASSERT(red_cfg != NULL);
385 RTE_ASSERT(red != NULL);
386
387 if (q != 0) {
388 return rte_red_enqueue_nonempty(red_cfg, red, q);
389 } else {
390 return rte_red_enqueue_empty(red_cfg, red, time);
391 }
392 }
393
394 /**
395 * @brief Callback to records time that queue became empty
396 *
397 * @param red [in,out] data pointer to RED runtime data
398 * @param time [in] current time stamp
399 */
400 static inline void
rte_red_mark_queue_empty(struct rte_red * red,const uint64_t time)401 rte_red_mark_queue_empty(struct rte_red *red, const uint64_t time)
402 {
403 red->q_time = time;
404 }
405
406 #ifdef __cplusplus
407 }
408 #endif
409
410 #endif /* __RTE_RED_H_INCLUDED__ */
411