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__ */