DPDK  24.07.0
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 
17 #include <stdint.h>
18 #include <limits.h>
19 #include <rte_debug.h>
20 #include <rte_cycles.h>
21 #include <rte_branch_prediction.h>
22 
23 #define RTE_RED_SCALING 10
24 #define RTE_RED_S (1 << 22)
25 #define RTE_RED_MAX_TH_MAX 1023
26 #define RTE_RED_WQ_LOG2_MIN 1
27 #define RTE_RED_WQ_LOG2_MAX 12
28 #define RTE_RED_MAXP_INV_MIN 1
29 #define RTE_RED_MAXP_INV_MAX 255
30 #define RTE_RED_2POW16 (1<<16)
31 #define RTE_RED_INT16_NBITS (sizeof(uint16_t) * CHAR_BIT)
32 #define RTE_RED_WQ_LOG2_NUM (RTE_RED_WQ_LOG2_MAX - RTE_RED_WQ_LOG2_MIN + 1)
33 
37 extern uint32_t rte_red_rand_val;
38 extern uint32_t rte_red_rand_seed;
39 extern uint16_t rte_red_log2_1_minus_Wq[RTE_RED_WQ_LOG2_NUM];
40 extern uint16_t rte_red_pow2_frac_inv[16];
41 
46  uint16_t min_th;
47  uint16_t max_th;
48  uint16_t maxp_inv;
49  uint16_t wq_log2;
50 };
51 
56  uint32_t min_th;
57  uint32_t max_th;
58  uint32_t pa_const;
59  uint8_t maxp_inv;
60  uint8_t wq_log2;
61 };
62 
66 struct rte_red {
67  uint32_t avg;
68  uint32_t count;
69  uint64_t q_time;
70 };
71 
81 int
82 rte_red_rt_data_init(struct rte_red *red);
83 
98 int
99 rte_red_config_init(struct rte_red_config *red_cfg,
100  const uint16_t wq_log2,
101  const uint16_t min_th,
102  const uint16_t max_th,
103  const uint16_t maxp_inv);
104 
115 static inline uint32_t
117 {
118  rte_red_rand_seed = (214013 * rte_red_rand_seed) + 2531011;
119  return rte_red_rand_seed >> 10;
120 }
121 
132 static inline uint16_t
134 {
135  uint32_t n = 0;
136  uint32_t f = 0;
137 
158  n = m * rte_red_log2_1_minus_Wq[wq_log2 - RTE_RED_WQ_LOG2_MIN];
159 
172  f = (n >> 6) & 0xf;
173  n >>= 10;
174 
175  if (n < RTE_RED_SCALING)
176  return (uint16_t) ((rte_red_pow2_frac_inv[f] + (1 << (n - 1))) >> n);
177 
178  return 0;
179 }
180 
195 static inline int
196 rte_red_enqueue_empty(const struct rte_red_config *red_cfg,
197  struct rte_red *red,
198  const uint64_t time)
199 {
200  uint64_t time_diff = 0, m = 0;
201 
202  RTE_ASSERT(red_cfg != NULL);
203  RTE_ASSERT(red != NULL);
204 
205  red->count ++;
206 
211  time_diff = time - red->q_time;
212 
219  m = time_diff / RTE_RED_S;
220 
224  if (m >= RTE_RED_2POW16) {
225  red->avg = 0;
226  } else {
227  red->avg = (red->avg >> RTE_RED_SCALING) * __rte_red_calc_qempty_factor(red_cfg->wq_log2, (uint16_t) m);
228  }
229 
230  return 0;
231 }
232 
273 static inline int
274 __rte_red_drop(const struct rte_red_config *red_cfg, struct rte_red *red)
275 {
276  uint32_t pa_num = 0; /* numerator of drop-probability */
277  uint32_t pa_den = 0; /* denominator of drop-probability */
278  uint32_t pa_num_count = 0;
279 
280  pa_num = (red->avg - red_cfg->min_th) >> (red_cfg->wq_log2);
281 
282  pa_num_count = red->count * pa_num;
283 
284  if (red_cfg->pa_const <= pa_num_count)
285  return 1;
286 
287  pa_den = red_cfg->pa_const - pa_num_count;
288 
289  /* If drop, generate and save random number to be used next time */
290  if (unlikely((rte_red_rand_val % pa_den) < pa_num)) {
291  rte_red_rand_val = rte_fast_rand();
292 
293  return 1;
294  }
295 
296  /* No drop */
297  return 0;
298 }
299 
312 static inline int
314  struct rte_red *red,
315  const unsigned q)
316 {
317  RTE_ASSERT(red_cfg != NULL);
318  RTE_ASSERT(red != NULL);
319 
333  /* avg update */
334  red->avg += (q << RTE_RED_SCALING) - (red->avg >> red_cfg->wq_log2);
335 
336  /* avg < min_th: do not mark the packet */
337  if (red->avg < red_cfg->min_th) {
338  red->count ++;
339  return 0;
340  }
341 
342  /* min_th <= avg < max_th: mark the packet with pa probability */
343  if (red->avg < red_cfg->max_th) {
344  if (!__rte_red_drop(red_cfg, red)) {
345  red->count ++;
346  return 0;
347  }
348 
349  red->count = 0;
350  return 2;
351  }
352 
353  /* max_th <= avg: always mark the packet */
354  red->count = 0;
355  return 1;
356 }
357 
374 static inline int
375 rte_red_enqueue(const struct rte_red_config *red_cfg,
376  struct rte_red *red,
377  const unsigned q,
378  const uint64_t time)
379 {
380  RTE_ASSERT(red_cfg != NULL);
381  RTE_ASSERT(red != NULL);
382 
383  if (q != 0) {
384  return rte_red_enqueue_nonempty(red_cfg, red, q);
385  } else {
386  return rte_red_enqueue_empty(red_cfg, red, time);
387  }
388 }
389 
396 static inline void
397 rte_red_mark_queue_empty(struct rte_red *red, const uint64_t time)
398 {
399  red->q_time = time;
400 }
401 
402 #ifdef __cplusplus
403 }
404 #endif
405 
406 #endif /* __RTE_RED_H_INCLUDED__ */
#define RTE_RED_SCALING
Definition: rte_red.h:23
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:397
static uint32_t rte_fast_rand(void)
Generate random number for RED.
Definition: rte_red.h:116
uint32_t avg
Definition: rte_red.h:67
uint16_t max_th
Definition: rte_red.h:47
#define RTE_RED_2POW16
Definition: rte_red.h:30
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:274
uint32_t max_th
Definition: rte_red.h:57
uint32_t rte_red_rand_val
#define RTE_RED_S
Definition: rte_red.h:24
uint32_t pa_const
Definition: rte_red.h:58
uint16_t min_th
Definition: rte_red.h:46
#define unlikely(x)
uint16_t wq_log2
Definition: rte_red.h:49
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:196
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:133
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 enqueued or dropped in queue non-empty case.
Definition: rte_red.h:313
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 enqueued or dropped Updates run time data based on new queue size val...
Definition: rte_red.h:375
int rte_red_rt_data_init(struct rte_red *red)
Initialises run-time data.
uint32_t min_th
Definition: rte_red.h:56
uint16_t maxp_inv
Definition: rte_red.h:48
uint32_t count
Definition: rte_red.h:68
uint64_t q_time
Definition: rte_red.h:69
#define RTE_RED_WQ_LOG2_MIN
Definition: rte_red.h:26
uint8_t maxp_inv
Definition: rte_red.h:59
uint8_t wq_log2
Definition: rte_red.h:60