examples: use new API to create control threads
[dpdk.git] / lib / librte_sched / rte_red.h
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_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         /**< Fraction size for fixed-point */
27 #define RTE_RED_S                           (1 << 22)  /**< Packet size multiplied by number of leaf queues */
28 #define RTE_RED_MAX_TH_MAX                  1023       /**< Max threshold limit in fixed point format */
29 #define RTE_RED_WQ_LOG2_MIN                 1          /**< Min inverse filter weight value */
30 #define RTE_RED_WQ_LOG2_MAX                 12         /**< Max inverse filter weight value */
31 #define RTE_RED_MAXP_INV_MIN                1          /**< Min inverse mark probability value */
32 #define RTE_RED_MAXP_INV_MAX                255        /**< Max inverse mark probability value */
33 #define RTE_RED_2POW16                      (1<<16)    /**< 2 power 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
37 /**
38  * Externs
39  *
40  */
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
46 /**
47  * RED configuration parameters passed by user
48  *
49  */
50 struct rte_red_params {
51         uint16_t min_th;   /**< Minimum threshold for queue (max_th) */
52         uint16_t max_th;   /**< Maximum threshold for queue (max_th) */
53         uint16_t maxp_inv; /**< Inverse of packet marking probability maximum value (maxp = 1 / maxp_inv) */
54         uint16_t wq_log2;  /**< Negated log2 of queue weight (wq = 1 / (2 ^ wq_log2)) */
55 };
56
57 /**
58  * RED configuration parameters
59  */
60 struct rte_red_config {
61         uint32_t min_th;   /**< min_th scaled in fixed-point format */
62         uint32_t max_th;   /**< max_th scaled in fixed-point format */
63         uint32_t pa_const; /**< Precomputed constant value used for pa calculation (scaled in fixed-point format) */
64         uint8_t maxp_inv;  /**< maxp_inv */
65         uint8_t wq_log2;   /**< wq_log2 */
66 };
67
68 /**
69  * RED run-time data
70  */
71 struct rte_red {
72         uint32_t avg;      /**< Average queue size (avg), scaled in fixed-point format */
73         uint32_t count;    /**< Number of packets since last marked packet (count) */
74         uint64_t q_time;   /**< Start of the queue idle time (q_time) */
75 };
76
77 /**
78  * @brief Initialises run-time data
79  *
80  * @param red [in,out] data pointer to RED runtime data
81  *
82  * @return Operation status
83  * @retval 0 success
84  * @retval !0 error
85  */
86 int
87 rte_red_rt_data_init(struct rte_red *red);
88
89 /**
90  * @brief Configures a single RED configuration parameter structure.
91  *
92  * @param red_cfg [in,out] config pointer to a RED configuration parameter structure
93  * @param wq_log2 [in]  log2 of the filter weight, valid range is:
94  *             RTE_RED_WQ_LOG2_MIN <= wq_log2 <= RTE_RED_WQ_LOG2_MAX
95  * @param min_th [in] queue minimum threshold in number of packets
96  * @param max_th [in] queue maximum threshold in number of packets
97  * @param maxp_inv [in] inverse maximum mark probability
98  *
99  * @return Operation status
100  * @retval 0 success
101  * @retval !0 error
102  */
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
110 /**
111  * @brief Generate random number for RED
112  *
113  * Implementation based on:
114  * http://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor/
115  *
116  * 10 bit shift has been found through empirical tests (was 16).
117  *
118  * @return Random number between 0 and (2^22 - 1)
119  */
120 static inline uint32_t
121 rte_fast_rand(void)
122 {
123         rte_red_rand_seed = (214013 * rte_red_rand_seed) + 2531011;
124         return rte_red_rand_seed >> 10;
125 }
126
127 /**
128  * @brief calculate factor to scale average queue size when queue
129  *        becomes empty
130  *
131  * @param wq_log2 [in] where EWMA filter weight wq = 1/(2 ^ wq_log2)
132  * @param m [in] exponent in the computed value (1 - wq) ^ m
133  *
134  * @return computed value
135  * @retval ((1 - wq) ^ m) scaled in fixed-point format
136  */
137 static inline uint16_t
138 __rte_red_calc_qempty_factor(uint8_t wq_log2, uint16_t m)
139 {
140         uint32_t n = 0;
141         uint32_t f = 0;
142
143         /**
144          * Basic math tells us that:
145          *   a^b = 2^(b * log2(a) )
146          *
147          * in our case:
148          *   a = (1-Wq)
149          *   b = m
150          *  Wq = 1/ (2^log2n)
151          *
152          * So we are computing this equation:
153          *   factor = 2 ^ ( m * log2(1-Wq))
154          *
155          * First we are computing:
156          *    n = m * log2(1-Wq)
157          *
158          * To avoid dealing with signed numbers log2 values are positive
159          * but they should be negative because (1-Wq) is always < 1.
160          * Contents of log2 table values are also scaled for precision.
161          */
162
163         n = m * rte_red_log2_1_minus_Wq[wq_log2 - RTE_RED_WQ_LOG2_MIN];
164
165         /**
166          * The tricky part is computing 2^n, for this I split n into
167          * integer part and fraction part.
168          *   f - is fraction part of n
169          *   n - is integer part of original n
170          *
171          * Now using basic math we compute 2^n:
172          *   2^(f+n) = 2^f * 2^n
173          *   2^f - we use lookup table
174          *   2^n - can be replaced with bit shift right operations
175          */
176
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
186 /**
187  * @brief Updates queue average in condition when queue is empty
188  *
189  * Note: packet is never dropped in this particular case.
190  *
191  * @param red_cfg [in] config pointer to a RED configuration parameter structure
192  * @param red [in,out] data pointer to RED runtime data
193  * @param time [in] current time stamp
194  *
195  * @return Operation status
196  * @retval 0 enqueue the packet
197  * @retval 1 drop the packet based on max threshold criterion
198  * @retval 2 drop the packet based on mark probability criterion
199  */
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
212         /**
213          * We compute avg but we don't compare avg against
214          *  min_th or max_th, nor calculate drop probability
215          */
216         time_diff = time - red->q_time;
217
218         /**
219          * m is the number of packets that might have arrived while the queue was empty.
220          * In this case we have time stamps provided by scheduler in byte units (bytes
221          * transmitted on network port). Such time stamp translates into time units as
222          * port speed is fixed but such approach simplifies the code.
223          */
224         m = time_diff / RTE_RED_S;
225
226         /**
227          * Check that m will fit into 16-bit unsigned integer
228          */
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
238 /**
239  *  Drop probability (Sally Floyd and Van Jacobson):
240  *
241  *     pb = (1 / maxp_inv) * (avg - min_th) / (max_th - min_th)
242  *     pa = pb / (2 - count * pb)
243  *
244  *
245  *                 (1 / maxp_inv) * (avg - min_th)
246  *                ---------------------------------
247  *                         max_th - min_th
248  *     pa = -----------------------------------------------
249  *                count * (1 / maxp_inv) * (avg - min_th)
250  *           2 - -----------------------------------------
251  *                          max_th - min_th
252  *
253  *
254  *                                  avg - min_th
255  *     pa = -----------------------------------------------------------
256  *           2 * (max_th - min_th) * maxp_inv - count * (avg - min_th)
257  *
258  *
259  *  We define pa_const as: pa_const =  2 * (max_th - min_th) * maxp_inv. Then:
260  *
261  *
262  *                     avg - min_th
263  *     pa = -----------------------------------
264  *           pa_const - count * (avg - min_th)
265  */
266
267 /**
268  * @brief make a decision to drop or enqueue a packet based on mark probability
269  *        criteria
270  *
271  * @param red_cfg [in] config pointer to structure defining RED parameters
272  * @param red [in,out] data pointer to RED runtime data
273  *
274  * @return operation status
275  * @retval 0 enqueue the packet
276  * @retval 1 drop the packet
277  */
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
305 /**
306  * @brief Decides if new packet should be enqeued or dropped in queue non-empty case
307  *
308  * @param red_cfg [in] config pointer to a RED configuration parameter structure
309  * @param red [in,out] data pointer to RED runtime data
310  * @param q [in] current queue size (measured in packets)
311  *
312  * @return Operation status
313  * @retval 0 enqueue the packet
314  * @retval 1 drop the packet based on max threshold criterion
315  * @retval 2 drop the packet based on mark probability criterion
316  */
317 static inline int
318 rte_red_enqueue_nonempty(const struct rte_red_config *red_cfg,
319         struct rte_red *red,
320         const unsigned q)
321 {
322         RTE_ASSERT(red_cfg != NULL);
323         RTE_ASSERT(red != NULL);
324
325         /**
326         * EWMA filter (Sally Floyd and Van Jacobson):
327         *    avg = (1 - wq) * avg + wq * q
328         *    avg = avg + q * wq - avg * wq
329         *
330         * We select: wq = 2^(-n). Let scaled version of avg be: avg_s = avg * 2^(N+n). We get:
331         *    avg_s = avg_s + q * 2^N - avg_s * 2^(-n)
332         *
333         * By using shift left/right operations, we get:
334         *    avg_s = avg_s + (q << N) - (avg_s >> n)
335         *    avg_s += (q << N) - (avg_s >> n)
336         */
337
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
363 /**
364  * @brief Decides if new packet should be enqeued or dropped
365  * Updates run time data based on new queue size value.
366  * Based on new queue average and RED configuration parameters
367  * gives verdict whether to enqueue or drop the packet.
368  *
369  * @param red_cfg [in] config pointer to a RED configuration parameter structure
370  * @param red [in,out] data pointer to RED runtime data
371  * @param q [in] updated queue size in packets
372  * @param time [in] current time stamp
373  *
374  * @return Operation status
375  * @retval 0 enqueue the packet
376  * @retval 1 drop the packet based on max threshold criteria
377  * @retval 2 drop the packet based on mark probability criteria
378  */
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
395 /**
396  * @brief Callback to records time that queue became empty
397  *
398  * @param red [in,out] data pointer to RED runtime data
399  * @param time [in] current time stamp
400  */
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__ */