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 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 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 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 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 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 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 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