Branch data     Line data    Source code

       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                 :            : /**
       9                 :            :  * @file
      10                 :            :  * RTE Random Early Detection (RED)
      11                 :            :  */
      12                 :            : 
      13                 :            : #include <stdint.h>
      14                 :            : #include <limits.h>
      15                 :            : #include <rte_debug.h>
      16                 :            : #include <rte_cycles.h>
      17                 :            : #include <rte_branch_prediction.h>
      18                 :            : 
      19                 :            : #ifdef __cplusplus
      20                 :            : extern "C" {
      21                 :            : #endif
      22                 :            : 
      23                 :            : #define RTE_RED_SCALING                     10         /**< Fraction size for fixed-point */
      24                 :            : #define RTE_RED_S                           (1 << 22)  /**< Packet size multiplied by number of leaf queues */
      25                 :            : #define RTE_RED_MAX_TH_MAX                  1023       /**< Max threshold limit in fixed point format */
      26                 :            : #define RTE_RED_WQ_LOG2_MIN                 1          /**< Min inverse filter weight value */
      27                 :            : #define RTE_RED_WQ_LOG2_MAX                 12         /**< Max inverse filter weight value */
      28                 :            : #define RTE_RED_MAXP_INV_MIN                1          /**< Min inverse mark probability value */
      29                 :            : #define RTE_RED_MAXP_INV_MAX                255        /**< Max inverse mark probability value */
      30                 :            : #define RTE_RED_2POW16                      (1<<16)    /**< 2 power 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                 :            : 
      34                 :            : /**
      35                 :            :  * Externs
      36                 :            :  */
      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                 :            : 
      42                 :            : /**
      43                 :            :  * RED configuration parameters passed by user
      44                 :            :  */
      45                 :            : struct rte_red_params {
      46                 :            :         uint16_t min_th;   /**< Minimum threshold for queue (max_th) */
      47                 :            :         uint16_t max_th;   /**< Maximum threshold for queue (max_th) */
      48                 :            :         uint16_t maxp_inv; /**< Inverse of packet marking probability maximum value (maxp = 1 / maxp_inv) */
      49                 :            :         uint16_t wq_log2;  /**< Negated log2 of queue weight (wq = 1 / (2 ^ wq_log2)) */
      50                 :            : };
      51                 :            : 
      52                 :            : /**
      53                 :            :  * RED configuration parameters
      54                 :            :  */
      55                 :            : struct rte_red_config {
      56                 :            :         uint32_t min_th;   /**< min_th scaled in fixed-point format */
      57                 :            :         uint32_t max_th;   /**< max_th scaled in fixed-point format */
      58                 :            :         uint32_t pa_const; /**< Precomputed constant value used for pa calculation (scaled in fixed-point format) */
      59                 :            :         uint8_t maxp_inv;  /**< maxp_inv */
      60                 :            :         uint8_t wq_log2;   /**< wq_log2 */
      61                 :            : };
      62                 :            : 
      63                 :            : /**
      64                 :            :  * RED run-time data
      65                 :            :  */
      66                 :            : struct rte_red {
      67                 :            :         uint32_t avg;      /**< Average queue size (avg), scaled in fixed-point format */
      68                 :            :         uint32_t count;    /**< Number of packets since last marked packet (count) */
      69                 :            :         uint64_t q_time;   /**< Start of the queue idle time (q_time) */
      70                 :            : };
      71                 :            : 
      72                 :            : /**
      73                 :            :  * @brief Initialises run-time data
      74                 :            :  *
      75                 :            :  * @param red [in,out] data pointer to RED runtime data
      76                 :            :  *
      77                 :            :  * @return Operation status
      78                 :            :  * @retval 0 success
      79                 :            :  * @retval !0 error
      80                 :            :  */
      81                 :            : int
      82                 :            : rte_red_rt_data_init(struct rte_red *red);
      83                 :            : 
      84                 :            : /**
      85                 :            :  * @brief Configures a single RED configuration parameter structure.
      86                 :            :  *
      87                 :            :  * @param red_cfg [in,out] config pointer to a RED configuration parameter structure
      88                 :            :  * @param wq_log2 [in]  log2 of the filter weight, valid range is:
      89                 :            :  *             RTE_RED_WQ_LOG2_MIN <= wq_log2 <= RTE_RED_WQ_LOG2_MAX
      90                 :            :  * @param min_th [in] queue minimum threshold in number of packets
      91                 :            :  * @param max_th [in] queue maximum threshold in number of packets
      92                 :            :  * @param maxp_inv [in] inverse maximum mark probability
      93                 :            :  *
      94                 :            :  * @return Operation status
      95                 :            :  * @retval 0 success
      96                 :            :  * @retval !0 error
      97                 :            :  */
      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                 :            : 
     105                 :            : /**
     106                 :            :  * @brief Generate random number for RED
     107                 :            :  *
     108                 :            :  * Implementation based on:
     109                 :            :  * http://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor/
     110                 :            :  *
     111                 :            :  * 10 bit shift has been found through empirical tests (was 16).
     112                 :            :  *
     113                 :            :  * @return Random number between 0 and (2^22 - 1)
     114                 :            :  */
     115                 :            : static inline uint32_t
     116                 :            : rte_fast_rand(void)
     117                 :            : {
     118                 :          0 :         rte_red_rand_seed = (214013 * rte_red_rand_seed) + 2531011;
     119                 :          0 :         return rte_red_rand_seed >> 10;
     120                 :            : }
     121                 :            : 
     122                 :            : /**
     123                 :            :  * @brief calculate factor to scale average queue size when queue
     124                 :            :  *        becomes empty
     125                 :            :  *
     126                 :            :  * @param wq_log2 [in] where EWMA filter weight wq = 1/(2 ^ wq_log2)
     127                 :            :  * @param m [in] exponent in the computed value (1 - wq) ^ m
     128                 :            :  *
     129                 :            :  * @return computed value
     130                 :            :  * @retval ((1 - wq) ^ m) scaled in fixed-point format
     131                 :            :  */
     132                 :            : static inline uint16_t
     133                 :            : __rte_red_calc_qempty_factor(uint8_t wq_log2, uint16_t m)
     134                 :            : {
     135                 :            :         uint32_t n = 0;
     136                 :            :         uint32_t f = 0;
     137                 :            : 
     138                 :            :         /**
     139                 :            :          * Basic math tells us that:
     140                 :            :          *   a^b = 2^(b * log2(a) )
     141                 :            :          *
     142                 :            :          * in our case:
     143                 :            :          *   a = (1-Wq)
     144                 :            :          *   b = m
     145                 :            :          *  Wq = 1/ (2^log2n)
     146                 :            :          *
     147                 :            :          * So we are computing this equation:
     148                 :            :          *   factor = 2 ^ ( m * log2(1-Wq))
     149                 :            :          *
     150                 :            :          * First we are computing:
     151                 :            :          *    n = m * log2(1-Wq)
     152                 :            :          *
     153                 :            :          * To avoid dealing with signed numbers log2 values are positive
     154                 :            :          * but they should be negative because (1-Wq) is always < 1.
     155                 :            :          * Contents of log2 table values are also scaled for precision.
     156                 :            :          */
     157                 :            : 
     158                 :          0 :         n = m * rte_red_log2_1_minus_Wq[wq_log2 - RTE_RED_WQ_LOG2_MIN];
     159                 :            : 
     160                 :            :         /**
     161                 :            :          * The tricky part is computing 2^n, for this I split n into
     162                 :            :          * integer part and fraction part.
     163                 :            :          *   f - is fraction part of n
     164                 :            :          *   n - is integer part of original n
     165                 :            :          *
     166                 :            :          * Now using basic math we compute 2^n:
     167                 :            :          *   2^(f+n) = 2^f * 2^n
     168                 :            :          *   2^f - we use lookup table
     169                 :            :          *   2^n - can be replaced with bit shift right operations
     170                 :            :          */
     171                 :            : 
     172                 :          0 :         f = (n >> 6) & 0xf;
     173                 :          0 :         n >>= 10;
     174                 :            : 
     175                 :          0 :         if (n < RTE_RED_SCALING)
     176                 :          0 :                 return (uint16_t) ((rte_red_pow2_frac_inv[f] + (1 << (n - 1))) >> n);
     177                 :            : 
     178                 :            :         return 0;
     179                 :            : }
     180                 :            : 
     181                 :            : /**
     182                 :            :  * @brief Updates queue average in condition when queue is empty
     183                 :            :  *
     184                 :            :  * Note: packet is never dropped in this particular case.
     185                 :            :  *
     186                 :            :  * @param red_cfg [in] config pointer to a RED configuration parameter structure
     187                 :            :  * @param red [in,out] data pointer to RED runtime data
     188                 :            :  * @param time [in] current time stamp
     189                 :            :  *
     190                 :            :  * @return Operation status
     191                 :            :  * @retval 0 enqueue the packet
     192                 :            :  * @retval 1 drop the packet based on max threshold criterion
     193                 :            :  * @retval 2 drop the packet based on mark probability criterion
     194                 :            :  */
     195                 :            : static inline int
     196                 :          0 : 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                 :          0 :         red->count ++;
     206                 :            : 
     207                 :            :         /**
     208                 :            :          * We compute avg but we don't compare avg against
     209                 :            :          *  min_th or max_th, nor calculate drop probability
     210                 :            :          */
     211                 :          0 :         time_diff = time - red->q_time;
     212                 :            : 
     213                 :            :         /**
     214                 :            :          * m is the number of packets that might have arrived while the queue was empty.
     215                 :            :          * In this case we have time stamps provided by scheduler in byte units (bytes
     216                 :            :          * transmitted on network port). Such time stamp translates into time units as
     217                 :            :          * port speed is fixed but such approach simplifies the code.
     218                 :            :          */
     219                 :          0 :         m = time_diff / RTE_RED_S;
     220                 :            : 
     221                 :            :         /**
     222                 :            :          * Check that m will fit into 16-bit unsigned integer
     223                 :            :          */
     224         [ #  # ]:          0 :         if (m >= RTE_RED_2POW16) {
     225                 :          0 :                 red->avg = 0;
     226                 :            :         } else {
     227         [ #  # ]:          0 :                 red->avg = (red->avg >> RTE_RED_SCALING) * __rte_red_calc_qempty_factor(red_cfg->wq_log2, (uint16_t) m);
     228                 :            :         }
     229                 :            : 
     230                 :          0 :         return 0;
     231                 :            : }
     232                 :            : 
     233                 :            : /**
     234                 :            :  *  Drop probability (Sally Floyd and Van Jacobson):
     235                 :            :  *
     236                 :            :  *     pb = (1 / maxp_inv) * (avg - min_th) / (max_th - min_th)
     237                 :            :  *     pa = pb / (2 - count * pb)
     238                 :            :  *
     239                 :            :  *
     240                 :            :  *                 (1 / maxp_inv) * (avg - min_th)
     241                 :            :  *                ---------------------------------
     242                 :            :  *                         max_th - min_th
     243                 :            :  *     pa = -----------------------------------------------
     244                 :            :  *                count * (1 / maxp_inv) * (avg - min_th)
     245                 :            :  *           2 - -----------------------------------------
     246                 :            :  *                          max_th - min_th
     247                 :            :  *
     248                 :            :  *
     249                 :            :  *                                  avg - min_th
     250                 :            :  *     pa = -----------------------------------------------------------
     251                 :            :  *           2 * (max_th - min_th) * maxp_inv - count * (avg - min_th)
     252                 :            :  *
     253                 :            :  *
     254                 :            :  *  We define pa_const as: pa_const =  2 * (max_th - min_th) * maxp_inv. Then:
     255                 :            :  *
     256                 :            :  *
     257                 :            :  *                     avg - min_th
     258                 :            :  *     pa = -----------------------------------
     259                 :            :  *           pa_const - count * (avg - min_th)
     260                 :            :  */
     261                 :            : 
     262                 :            : /**
     263                 :            :  * @brief make a decision to drop or enqueue a packet based on mark probability
     264                 :            :  *        criteria
     265                 :            :  *
     266                 :            :  * @param red_cfg [in] config pointer to structure defining RED parameters
     267                 :            :  * @param red [in,out] data pointer to RED runtime data
     268                 :            :  *
     269                 :            :  * @return operation status
     270                 :            :  * @retval 0 enqueue the packet
     271                 :            :  * @retval 1 drop the packet
     272                 :            :  */
     273                 :            : static inline int
     274                 :          0 : __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                 :          0 :         pa_num = (red->avg - red_cfg->min_th) >> (red_cfg->wq_log2);
     281                 :            : 
     282                 :          0 :         pa_num_count = red->count * pa_num;
     283                 :            : 
     284         [ #  # ]:          0 :         if (red_cfg->pa_const <= pa_num_count)
     285                 :            :                 return 1;
     286                 :            : 
     287                 :          0 :         pa_den = red_cfg->pa_const - pa_num_count;
     288                 :            : 
     289                 :            :         /* If drop, generate and save random number to be used next time */
     290         [ #  # ]:          0 :         if (unlikely((rte_red_rand_val % pa_den) < pa_num)) {
     291                 :          0 :                 rte_red_rand_val = rte_fast_rand();
     292                 :            : 
     293                 :          0 :                 return 1;
     294                 :            :         }
     295                 :            : 
     296                 :            :         /* No drop */
     297                 :            :         return 0;
     298                 :            : }
     299                 :            : 
     300                 :            : /**
     301                 :            :  * @brief Decides if new packet should be enqueued or dropped in queue non-empty case
     302                 :            :  *
     303                 :            :  * @param red_cfg [in] config pointer to a RED configuration parameter structure
     304                 :            :  * @param red [in,out] data pointer to RED runtime data
     305                 :            :  * @param q [in] current queue size (measured in packets)
     306                 :            :  *
     307                 :            :  * @return Operation status
     308                 :            :  * @retval 0 enqueue the packet
     309                 :            :  * @retval 1 drop the packet based on max threshold criterion
     310                 :            :  * @retval 2 drop the packet based on mark probability criterion
     311                 :            :  */
     312                 :            : static inline int
     313                 :          0 : rte_red_enqueue_nonempty(const struct rte_red_config *red_cfg,
     314                 :            :         struct rte_red *red,
     315                 :            :         const unsigned q)
     316                 :            : {
     317                 :            :         RTE_ASSERT(red_cfg != NULL);
     318                 :            :         RTE_ASSERT(red != NULL);
     319                 :            : 
     320                 :            :         /**
     321                 :            :         * EWMA filter (Sally Floyd and Van Jacobson):
     322                 :            :         *    avg = (1 - wq) * avg + wq * q
     323                 :            :         *    avg = avg + q * wq - avg * wq
     324                 :            :         *
     325                 :            :         * We select: wq = 2^(-n). Let scaled version of avg be: avg_s = avg * 2^(N+n). We get:
     326                 :            :         *    avg_s = avg_s + q * 2^N - avg_s * 2^(-n)
     327                 :            :         *
     328                 :            :         * By using shift left/right operations, we get:
     329                 :            :         *    avg_s = avg_s + (q << N) - (avg_s >> n)
     330                 :            :         *    avg_s += (q << N) - (avg_s >> n)
     331                 :            :         */
     332                 :            : 
     333                 :            :         /* avg update */
     334                 :          0 :         red->avg += (q << RTE_RED_SCALING) - (red->avg >> red_cfg->wq_log2);
     335                 :            : 
     336                 :            :         /* avg < min_th: do not mark the packet  */
     337         [ #  # ]:          0 :         if (red->avg < red_cfg->min_th) {
     338                 :          0 :                 red->count ++;
     339                 :          0 :                 return 0;
     340                 :            :         }
     341                 :            : 
     342                 :            :         /* min_th <= avg < max_th: mark the packet with pa probability */
     343         [ #  # ]:          0 :         if (red->avg < red_cfg->max_th) {
     344         [ #  # ]:          0 :                 if (!__rte_red_drop(red_cfg, red)) {
     345                 :          0 :                         red->count ++;
     346                 :          0 :                         return 0;
     347                 :            :                 }
     348                 :            : 
     349                 :          0 :                 red->count = 0;
     350                 :          0 :                 return 2;
     351                 :            :         }
     352                 :            : 
     353                 :            :         /* max_th <= avg: always mark the packet */
     354                 :          0 :         red->count = 0;
     355                 :          0 :         return 1;
     356                 :            : }
     357                 :            : 
     358                 :            : /**
     359                 :            :  * @brief Decides if new packet should be enqueued or dropped
     360                 :            :  * Updates run time data based on new queue size value.
     361                 :            :  * Based on new queue average and RED configuration parameters
     362                 :            :  * gives verdict whether to enqueue or drop the packet.
     363                 :            :  *
     364                 :            :  * @param red_cfg [in] config pointer to a RED configuration parameter structure
     365                 :            :  * @param red [in,out] data pointer to RED runtime data
     366                 :            :  * @param q [in] updated queue size in packets
     367                 :            :  * @param time [in] current time stamp
     368                 :            :  *
     369                 :            :  * @return Operation status
     370                 :            :  * @retval 0 enqueue the packet
     371                 :            :  * @retval 1 drop the packet based on max threshold criteria
     372                 :            :  * @retval 2 drop the packet based on mark probability criteria
     373                 :            :  */
     374                 :            : static inline int
     375                 :          0 : 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         [ #  # ]:          0 :         if (q != 0) {
     384                 :          0 :                 return rte_red_enqueue_nonempty(red_cfg, red, q);
     385                 :            :         } else {
     386                 :          0 :                 return rte_red_enqueue_empty(red_cfg, red, time);
     387                 :            :         }
     388                 :            : }
     389                 :            : 
     390                 :            : /**
     391                 :            :  * @brief Callback to records time that queue became empty
     392                 :            :  *
     393                 :            :  * @param red [in,out] data pointer to RED runtime data
     394                 :            :  * @param time [in] current time stamp
     395                 :            :  */
     396                 :            : static inline void
     397                 :            : rte_red_mark_queue_empty(struct rte_red *red, const uint64_t time)
     398                 :            : {
     399                 :          0 :         red->q_time = time;
     400                 :          0 : }
     401                 :            : 
     402                 :            : #ifdef __cplusplus
     403                 :            : }
     404                 :            : #endif
     405                 :            : 
     406                 :            : #endif /* __RTE_RED_H_INCLUDED__ */