DPDK  16.11.11
rte_red.h
Go to the documentation of this file.
1 /*-
2  * BSD LICENSE
3  *
4  * Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright
12  * notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above copyright
14  * notice, this list of conditions and the following disclaimer in
15  * the documentation and/or other materials provided with the
16  * distribution.
17  * * Neither the name of Intel Corporation nor the names of its
18  * contributors may be used to endorse or promote products derived
19  * from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32  */
33 
34 #ifndef __RTE_RED_H_INCLUDED__
35 #define __RTE_RED_H_INCLUDED__
36 
37 #ifdef __cplusplus
38 extern "C" {
39 #endif
40 
48 #include <stdint.h>
49 #include <limits.h>
50 #include <rte_common.h>
51 #include <rte_debug.h>
52 #include <rte_cycles.h>
53 #include <rte_branch_prediction.h>
54 
55 #define RTE_RED_SCALING 10
56 #define RTE_RED_S (1 << 22)
57 #define RTE_RED_MAX_TH_MAX 1023
58 #define RTE_RED_WQ_LOG2_MIN 1
59 #define RTE_RED_WQ_LOG2_MAX 12
60 #define RTE_RED_MAXP_INV_MIN 1
61 #define RTE_RED_MAXP_INV_MAX 255
62 #define RTE_RED_2POW16 (1<<16)
63 #define RTE_RED_INT16_NBITS (sizeof(uint16_t) * CHAR_BIT)
64 #define RTE_RED_WQ_LOG2_NUM (RTE_RED_WQ_LOG2_MAX - RTE_RED_WQ_LOG2_MIN + 1)
65 
70 extern uint32_t rte_red_rand_val;
71 extern uint32_t rte_red_rand_seed;
72 extern uint16_t rte_red_log2_1_minus_Wq[RTE_RED_WQ_LOG2_NUM];
73 extern uint16_t rte_red_pow2_frac_inv[16];
74 
80  uint16_t min_th;
81  uint16_t max_th;
82  uint16_t maxp_inv;
83  uint16_t wq_log2;
84 };
85 
90  uint32_t min_th;
91  uint32_t max_th;
92  uint32_t pa_const;
93  uint8_t maxp_inv;
94  uint8_t wq_log2;
95 };
96 
100 struct rte_red {
101  uint32_t avg;
102  uint32_t count;
103  uint64_t q_time;
104 };
105 
115 int
116 rte_red_rt_data_init(struct rte_red *red);
117 
132 int
133 rte_red_config_init(struct rte_red_config *red_cfg,
134  const uint16_t wq_log2,
135  const uint16_t min_th,
136  const uint16_t max_th,
137  const uint16_t maxp_inv);
138 
149 static inline uint32_t
151 {
152  rte_red_rand_seed = (214013 * rte_red_rand_seed) + 2531011;
153  return rte_red_rand_seed >> 10;
154 }
155 
166 static inline uint16_t
167 __rte_red_calc_qempty_factor(uint8_t wq_log2, uint16_t m)
168 {
169  uint32_t n = 0;
170  uint32_t f = 0;
171 
192  n = m * rte_red_log2_1_minus_Wq[wq_log2 - RTE_RED_WQ_LOG2_MIN];
193 
206  f = (n >> 6) & 0xf;
207  n >>= 10;
208 
209  if (n < RTE_RED_SCALING)
210  return (uint16_t) ((rte_red_pow2_frac_inv[f] + (1 << (n - 1))) >> n);
211 
212  return 0;
213 }
214 
229 static inline int
230 rte_red_enqueue_empty(const struct rte_red_config *red_cfg,
231  struct rte_red *red,
232  const uint64_t time)
233 {
234  uint64_t time_diff = 0, m = 0;
235 
236  RTE_ASSERT(red_cfg != NULL);
237  RTE_ASSERT(red != NULL);
238 
239  red->count ++;
240 
245  time_diff = time - red->q_time;
246 
253  m = time_diff / RTE_RED_S;
254 
258  if (m >= RTE_RED_2POW16) {
259  red->avg = 0;
260  } else {
261  red->avg = (red->avg >> RTE_RED_SCALING) * __rte_red_calc_qempty_factor(red_cfg->wq_log2, (uint16_t) m);
262  }
263 
264  return 0;
265 }
266 
307 static inline int
308 __rte_red_drop(const struct rte_red_config *red_cfg, struct rte_red *red)
309 {
310  uint32_t pa_num = 0; /* numerator of drop-probability */
311  uint32_t pa_den = 0; /* denominator of drop-probability */
312  uint32_t pa_num_count = 0;
313 
314  pa_num = (red->avg - red_cfg->min_th) >> (red_cfg->wq_log2);
315 
316  pa_num_count = red->count * pa_num;
317 
318  if (red_cfg->pa_const <= pa_num_count)
319  return 1;
320 
321  pa_den = red_cfg->pa_const - pa_num_count;
322 
323  /* If drop, generate and save random number to be used next time */
324  if (unlikely((rte_red_rand_val % pa_den) < pa_num)) {
325  rte_red_rand_val = rte_fast_rand();
326 
327  return 1;
328  }
329 
330  /* No drop */
331  return 0;
332 }
333 
346 static inline int
348  struct rte_red *red,
349  const unsigned q)
350 {
351  RTE_ASSERT(red_cfg != NULL);
352  RTE_ASSERT(red != NULL);
353 
367  /* avg update */
368  red->avg += (q << RTE_RED_SCALING) - (red->avg >> red_cfg->wq_log2);
369 
370  /* avg < min_th: do not mark the packet */
371  if (red->avg < red_cfg->min_th) {
372  red->count ++;
373  return 0;
374  }
375 
376  /* min_th <= avg < max_th: mark the packet with pa probability */
377  if (red->avg < red_cfg->max_th) {
378  if (!__rte_red_drop(red_cfg, red)) {
379  red->count ++;
380  return 0;
381  }
382 
383  red->count = 0;
384  return 2;
385  }
386 
387  /* max_th <= avg: always mark the packet */
388  red->count = 0;
389  return 1;
390 }
391 
408 static inline int
409 rte_red_enqueue(const struct rte_red_config *red_cfg,
410  struct rte_red *red,
411  const unsigned q,
412  const uint64_t time)
413 {
414  RTE_ASSERT(red_cfg != NULL);
415  RTE_ASSERT(red != NULL);
416 
417  if (q != 0) {
418  return rte_red_enqueue_nonempty(red_cfg, red, q);
419  } else {
420  return rte_red_enqueue_empty(red_cfg, red, time);
421  }
422 }
423 
430 static inline void
431 rte_red_mark_queue_empty(struct rte_red *red, const uint64_t time)
432 {
433  red->q_time = time;
434 }
435 
436 #ifdef __cplusplus
437 }
438 #endif
439 
440 #endif /* __RTE_RED_H_INCLUDED__ */
#define RTE_RED_SCALING
Definition: rte_red.h:55
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:431
static uint32_t rte_fast_rand(void)
Generate random number for RED.
Definition: rte_red.h:150
uint32_t avg
Definition: rte_red.h:101
uint16_t max_th
Definition: rte_red.h:81
#define RTE_RED_2POW16
Definition: rte_red.h:62
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:308
uint32_t max_th
Definition: rte_red.h:91
uint32_t rte_red_rand_val
#define RTE_RED_S
Definition: rte_red.h:56
uint32_t pa_const
Definition: rte_red.h:92
uint16_t min_th
Definition: rte_red.h:80
#define unlikely(x)
uint16_t wq_log2
Definition: rte_red.h:83
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:230
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:167
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:347
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:409
int rte_red_rt_data_init(struct rte_red *red)
Initialises run-time data.
uint32_t min_th
Definition: rte_red.h:90
uint16_t maxp_inv
Definition: rte_red.h:82
uint32_t count
Definition: rte_red.h:102
uint64_t q_time
Definition: rte_red.h:103
#define RTE_RED_WQ_LOG2_MIN
Definition: rte_red.h:58
uint8_t maxp_inv
Definition: rte_red.h:93
uint8_t wq_log2
Definition: rte_red.h:94