DPDK  19.11.14
rte_red.h
Go to the documentation of this file.
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 
19 #include <stdint.h>
20 #include <limits.h>
21 #include <rte_common.h>
22 #include <rte_debug.h>
23 #include <rte_cycles.h>
24 #include <rte_branch_prediction.h>
25 
26 #define RTE_RED_SCALING 10
27 #define RTE_RED_S (1 << 22)
28 #define RTE_RED_MAX_TH_MAX 1023
29 #define RTE_RED_WQ_LOG2_MIN 1
30 #define RTE_RED_WQ_LOG2_MAX 12
31 #define RTE_RED_MAXP_INV_MIN 1
32 #define RTE_RED_MAXP_INV_MAX 255
33 #define RTE_RED_2POW16 (1<<16)
34 #define RTE_RED_INT16_NBITS (sizeof(uint16_t) * CHAR_BIT)
35 #define RTE_RED_WQ_LOG2_NUM (RTE_RED_WQ_LOG2_MAX - RTE_RED_WQ_LOG2_MIN + 1)
36 
41 extern uint32_t rte_red_rand_val;
42 extern uint32_t rte_red_rand_seed;
43 extern uint16_t rte_red_log2_1_minus_Wq[RTE_RED_WQ_LOG2_NUM];
44 extern uint16_t rte_red_pow2_frac_inv[16];
45 
51  uint16_t min_th;
52  uint16_t max_th;
53  uint16_t maxp_inv;
54  uint16_t wq_log2;
55 };
56 
61  uint32_t min_th;
62  uint32_t max_th;
63  uint32_t pa_const;
64  uint8_t maxp_inv;
65  uint8_t wq_log2;
66 };
67 
71 struct rte_red {
72  uint32_t avg;
73  uint32_t count;
74  uint64_t q_time;
75 };
76 
86 int
87 rte_red_rt_data_init(struct rte_red *red);
88 
103 int
104 rte_red_config_init(struct rte_red_config *red_cfg,
105  const uint16_t wq_log2,
106  const uint16_t min_th,
107  const uint16_t max_th,
108  const uint16_t maxp_inv);
109 
120 static inline uint32_t
122 {
123  rte_red_rand_seed = (214013 * rte_red_rand_seed) + 2531011;
124  return rte_red_rand_seed >> 10;
125 }
126 
137 static inline uint16_t
139 {
140  uint32_t n = 0;
141  uint32_t f = 0;
142 
163  n = m * rte_red_log2_1_minus_Wq[wq_log2 - RTE_RED_WQ_LOG2_MIN];
164 
177  f = (n >> 6) & 0xf;
178  n >>= 10;
179 
180  if (n < RTE_RED_SCALING)
181  return (uint16_t) ((rte_red_pow2_frac_inv[f] + (1 << (n - 1))) >> n);
182 
183  return 0;
184 }
185 
200 static inline int
201 rte_red_enqueue_empty(const struct rte_red_config *red_cfg,
202  struct rte_red *red,
203  const uint64_t time)
204 {
205  uint64_t time_diff = 0, m = 0;
206 
207  RTE_ASSERT(red_cfg != NULL);
208  RTE_ASSERT(red != NULL);
209 
210  red->count ++;
211 
216  time_diff = time - red->q_time;
217 
224  m = time_diff / RTE_RED_S;
225 
229  if (m >= RTE_RED_2POW16) {
230  red->avg = 0;
231  } else {
232  red->avg = (red->avg >> RTE_RED_SCALING) * __rte_red_calc_qempty_factor(red_cfg->wq_log2, (uint16_t) m);
233  }
234 
235  return 0;
236 }
237 
278 static inline int
279 __rte_red_drop(const struct rte_red_config *red_cfg, struct rte_red *red)
280 {
281  uint32_t pa_num = 0; /* numerator of drop-probability */
282  uint32_t pa_den = 0; /* denominator of drop-probability */
283  uint32_t pa_num_count = 0;
284 
285  pa_num = (red->avg - red_cfg->min_th) >> (red_cfg->wq_log2);
286 
287  pa_num_count = red->count * pa_num;
288 
289  if (red_cfg->pa_const <= pa_num_count)
290  return 1;
291 
292  pa_den = red_cfg->pa_const - pa_num_count;
293 
294  /* If drop, generate and save random number to be used next time */
295  if (unlikely((rte_red_rand_val % pa_den) < pa_num)) {
296  rte_red_rand_val = rte_fast_rand();
297 
298  return 1;
299  }
300 
301  /* No drop */
302  return 0;
303 }
304 
317 static inline int
319  struct rte_red *red,
320  const unsigned q)
321 {
322  RTE_ASSERT(red_cfg != NULL);
323  RTE_ASSERT(red != NULL);
324 
338  /* avg update */
339  red->avg += (q << RTE_RED_SCALING) - (red->avg >> red_cfg->wq_log2);
340 
341  /* avg < min_th: do not mark the packet */
342  if (red->avg < red_cfg->min_th) {
343  red->count ++;
344  return 0;
345  }
346 
347  /* min_th <= avg < max_th: mark the packet with pa probability */
348  if (red->avg < red_cfg->max_th) {
349  if (!__rte_red_drop(red_cfg, red)) {
350  red->count ++;
351  return 0;
352  }
353 
354  red->count = 0;
355  return 2;
356  }
357 
358  /* max_th <= avg: always mark the packet */
359  red->count = 0;
360  return 1;
361 }
362 
379 static inline int
380 rte_red_enqueue(const struct rte_red_config *red_cfg,
381  struct rte_red *red,
382  const unsigned q,
383  const uint64_t time)
384 {
385  RTE_ASSERT(red_cfg != NULL);
386  RTE_ASSERT(red != NULL);
387 
388  if (q != 0) {
389  return rte_red_enqueue_nonempty(red_cfg, red, q);
390  } else {
391  return rte_red_enqueue_empty(red_cfg, red, time);
392  }
393 }
394 
401 static inline void
402 rte_red_mark_queue_empty(struct rte_red *red, const uint64_t time)
403 {
404  red->q_time = time;
405 }
406 
407 #ifdef __cplusplus
408 }
409 #endif
410 
411 #endif /* __RTE_RED_H_INCLUDED__ */
#define RTE_RED_SCALING
Definition: rte_red.h:26
static void rte_red_mark_queue_empty(struct rte_red *red, const uint64_t time)
Callback to records time that queue became empty.
Definition: rte_red.h:402
static uint32_t rte_fast_rand(void)
Generate random number for RED.
Definition: rte_red.h:121
uint32_t avg
Definition: rte_red.h:72
uint16_t max_th
Definition: rte_red.h:52
#define RTE_RED_2POW16
Definition: rte_red.h:33
static int __rte_red_drop(const struct rte_red_config *red_cfg, struct rte_red *red)
make a decision to drop or enqueue a packet based on mark probability criteria
Definition: rte_red.h:279
uint32_t max_th
Definition: rte_red.h:62
uint32_t rte_red_rand_val
#define RTE_RED_S
Definition: rte_red.h:27
uint32_t pa_const
Definition: rte_red.h:63
uint16_t min_th
Definition: rte_red.h:51
#define unlikely(x)
uint16_t wq_log2
Definition: rte_red.h:54
int rte_red_config_init(struct rte_red_config *red_cfg, const uint16_t wq_log2, const uint16_t min_th, const uint16_t max_th, const uint16_t maxp_inv)
Configures a single RED configuration parameter structure.
static int rte_red_enqueue_empty(const struct rte_red_config *red_cfg, struct rte_red *red, const uint64_t time)
Updates queue average in condition when queue is empty.
Definition: rte_red.h:201
static uint16_t __rte_red_calc_qempty_factor(uint8_t wq_log2, uint16_t m)
calculate factor to scale average queue size when queue becomes empty
Definition: rte_red.h:138
static int rte_red_enqueue_nonempty(const struct rte_red_config *red_cfg, struct rte_red *red, const unsigned q)
Decides if new packet should be enqeued or dropped in queue non-empty case.
Definition: rte_red.h:318
static int rte_red_enqueue(const struct rte_red_config *red_cfg, struct rte_red *red, const unsigned q, const uint64_t time)
Decides if new packet should be enqeued or dropped Updates run time data based on new queue size valu...
Definition: rte_red.h:380
int rte_red_rt_data_init(struct rte_red *red)
Initialises run-time data.
uint32_t min_th
Definition: rte_red.h:61
uint16_t maxp_inv
Definition: rte_red.h:53
uint32_t count
Definition: rte_red.h:73
uint64_t q_time
Definition: rte_red.h:74
#define RTE_RED_WQ_LOG2_MIN
Definition: rte_red.h:29
uint8_t maxp_inv
Definition: rte_red.h:64
uint8_t wq_log2
Definition: rte_red.h:65