diff options
Diffstat (limited to 'lib/librte_sched/rte_red.h')
| -rw-r--r-- | lib/librte_sched/rte_red.h | 453 |
1 files changed, 453 insertions, 0 deletions
diff --git a/lib/librte_sched/rte_red.h b/lib/librte_sched/rte_red.h new file mode 100644 index 00000000..7f9ac901 --- /dev/null +++ b/lib/librte_sched/rte_red.h @@ -0,0 +1,453 @@ +/*- + * BSD LICENSE + * + * Copyright(c) 2010-2014 Intel Corporation. All rights reserved. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Intel Corporation nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __RTE_RED_H_INCLUDED__ +#define __RTE_RED_H_INCLUDED__ + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * @file + * RTE Random Early Detection (RED) + * + * + ***/ + +#include <stdint.h> +#include <limits.h> +#include <rte_common.h> +#include <rte_debug.h> +#include <rte_cycles.h> +#include <rte_branch_prediction.h> + +#define RTE_RED_SCALING 10 /**< Fraction size for fixed-point */ +#define RTE_RED_S (1 << 22) /**< Packet size multiplied by number of leaf queues */ +#define RTE_RED_MAX_TH_MAX 1023 /**< Max threshold limit in fixed point format */ +#define RTE_RED_WQ_LOG2_MIN 1 /**< Min inverse filter weight value */ +#define RTE_RED_WQ_LOG2_MAX 12 /**< Max inverse filter weight value */ +#define RTE_RED_MAXP_INV_MIN 1 /**< Min inverse mark probability value */ +#define RTE_RED_MAXP_INV_MAX 255 /**< Max inverse mark probability value */ +#define RTE_RED_2POW16 (1<<16) /**< 2 power 16 */ +#define RTE_RED_INT16_NBITS (sizeof(uint16_t) * CHAR_BIT) +#define RTE_RED_WQ_LOG2_NUM (RTE_RED_WQ_LOG2_MAX - RTE_RED_WQ_LOG2_MIN + 1) + +#ifdef RTE_RED_DEBUG + +#define RTE_RED_ASSERT(exp) \ +if (!(exp)) { \ + rte_panic("line%d\tassert \"" #exp "\" failed\n", __LINE__); \ +} + +#else + +#define RTE_RED_ASSERT(exp) do { } while(0) + +#endif /* RTE_RED_DEBUG */ + +/** + * Externs + * + */ +extern uint32_t rte_red_rand_val; +extern uint32_t rte_red_rand_seed; +extern uint16_t rte_red_log2_1_minus_Wq[RTE_RED_WQ_LOG2_NUM]; +extern uint16_t rte_red_pow2_frac_inv[16]; + +/** + * RED configuration parameters passed by user + * + */ +struct rte_red_params { + uint16_t min_th; /**< Minimum threshold for queue (max_th) */ + uint16_t max_th; /**< Maximum threshold for queue (max_th) */ + uint16_t maxp_inv; /**< Inverse of packet marking probability maximum value (maxp = 1 / maxp_inv) */ + uint16_t wq_log2; /**< Negated log2 of queue weight (wq = 1 / (2 ^ wq_log2)) */ +}; + +/** + * RED configuration parameters + */ +struct rte_red_config { + uint32_t min_th; /**< min_th scaled in fixed-point format */ + uint32_t max_th; /**< max_th scaled in fixed-point format */ + uint32_t pa_const; /**< Precomputed constant value used for pa calculation (scaled in fixed-point format) */ + uint8_t maxp_inv; /**< maxp_inv */ + uint8_t wq_log2; /**< wq_log2 */ +}; + +/** + * RED run-time data + */ +struct rte_red { + uint32_t avg; /**< Average queue size (avg), scaled in fixed-point format */ + uint32_t count; /**< Number of packets since last marked packet (count) */ + uint64_t q_time; /**< Start of the queue idle time (q_time) */ +}; + +/** + * @brief Initialises run-time data + * + * @param red [in,out] data pointer to RED runtime data + * + * @return Operation status + * @retval 0 success + * @retval !0 error + */ +int +rte_red_rt_data_init(struct rte_red *red); + +/** + * @brief Configures a single RED configuration parameter structure. + * + * @param red_cfg [in,out] config pointer to a RED configuration parameter structure + * @param wq_log2 [in] log2 of the filter weight, valid range is: + * RTE_RED_WQ_LOG2_MIN <= wq_log2 <= RTE_RED_WQ_LOG2_MAX + * @param min_th [in] queue minimum threshold in number of packets + * @param max_th [in] queue maximum threshold in number of packets + * @param maxp_inv [in] inverse maximum mark probability + * + * @return Operation status + * @retval 0 success + * @retval !0 error + */ +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); + +/** + * @brief Generate random number for RED + * + * Implemenetation based on: + * http://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor/ + * + * 10 bit shift has been found through empirical tests (was 16). + * + * @return Random number between 0 and (2^22 - 1) + */ +static inline uint32_t +rte_fast_rand(void) +{ + rte_red_rand_seed = (214013 * rte_red_rand_seed) + 2531011; + return rte_red_rand_seed >> 10; +} + +/** + * @brief calculate factor to scale average queue size when queue + * becomes empty + * + * @param wq_log2 [in] where EWMA filter weight wq = 1/(2 ^ wq_log2) + * @param m [in] exponent in the computed value (1 - wq) ^ m + * + * @return computed value + * @retval ((1 - wq) ^ m) scaled in fixed-point format + */ +static inline uint16_t +__rte_red_calc_qempty_factor(uint8_t wq_log2, uint16_t m) +{ + uint32_t n = 0; + uint32_t f = 0; + + /** + * Basic math tells us that: + * a^b = 2^(b * log2(a) ) + * + * in our case: + * a = (1-Wq) + * b = m + * Wq = 1/ (2^log2n) + * + * So we are computing this equation: + * factor = 2 ^ ( m * log2(1-Wq)) + * + * First we are computing: + * n = m * log2(1-Wq) + * + * To avoid dealing with signed numbers log2 values are positive + * but they should be negative because (1-Wq) is always < 1. + * Contents of log2 table values are also scaled for precision. + */ + + n = m * rte_red_log2_1_minus_Wq[wq_log2 - RTE_RED_WQ_LOG2_MIN]; + + /** + * The tricky part is computing 2^n, for this I split n into + * integer part and fraction part. + * f - is fraction part of n + * n - is integer part of original n + * + * Now using basic math we compute 2^n: + * 2^(f+n) = 2^f * 2^n + * 2^f - we use lookup table + * 2^n - can be replaced with bit shift right oeprations + */ + + f = (n >> 6) & 0xf; + n >>= 10; + + if (n < RTE_RED_SCALING) + return (uint16_t) ((rte_red_pow2_frac_inv[f] + (1 << (n - 1))) >> n); + + return 0; +} + +/** + * @brief Updates queue average in condition when queue is empty + * + * Note: packet is never dropped in this particular case. + * + * @param red_cfg [in] config pointer to a RED configuration parameter structure + * @param red [in,out] data pointer to RED runtime data + * @param time [in] current time stamp + * + * @return Operation status + * @retval 0 enqueue the packet + * @retval 1 drop the packet based on max threshold criterion + * @retval 2 drop the packet based on mark probability criterion + */ +static inline int +rte_red_enqueue_empty(const struct rte_red_config *red_cfg, + struct rte_red *red, + const uint64_t time) +{ + uint64_t time_diff = 0, m = 0; + + RTE_RED_ASSERT(red_cfg != NULL); + RTE_RED_ASSERT(red != NULL); + + red->count ++; + + /** + * We compute avg but we don't compare avg against + * min_th or max_th, nor calculate drop probability + */ + time_diff = time - red->q_time; + + /** + * m is the number of packets that might have arrived while the queue was empty. + * In this case we have time stamps provided by scheduler in byte units (bytes + * transmitted on network port). Such time stamp translates into time units as + * port speed is fixed but such approach simplifies the code. + */ + m = time_diff / RTE_RED_S; + + /** + * Check that m will fit into 16-bit unsigned integer + */ + if (m >= RTE_RED_2POW16) { + red->avg = 0; + } else { + red->avg = (red->avg >> RTE_RED_SCALING) * __rte_red_calc_qempty_factor(red_cfg->wq_log2, (uint16_t) m); + } + + return 0; +} + +/** + * Drop probability (Sally Floyd and Van Jacobson): + * + * pb = (1 / maxp_inv) * (avg - min_th) / (max_th - min_th) + * pa = pb / (2 - count * pb) + * + * + * (1 / maxp_inv) * (avg - min_th) + * --------------------------------- + * max_th - min_th + * pa = ----------------------------------------------- + * count * (1 / maxp_inv) * (avg - min_th) + * 2 - ----------------------------------------- + * max_th - min_th + * + * + * avg - min_th + * pa = ----------------------------------------------------------- + * 2 * (max_th - min_th) * maxp_inv - count * (avg - min_th) + * + * + * We define pa_const as: pa_const = 2 * (max_th - min_th) * maxp_inv. Then: + * + * + * avg - min_th + * pa = ----------------------------------- + * pa_const - count * (avg - min_th) + */ + +/** + * @brief make a decision to drop or enqueue a packet based on mark probability + * criteria + * + * @param red_cfg [in] config pointer to structure defining RED parameters + * @param red [in,out] data pointer to RED runtime data + * + * @return operation status + * @retval 0 enqueue the packet + * @retval 1 drop the packet + */ +static inline int +__rte_red_drop(const struct rte_red_config *red_cfg, struct rte_red *red) +{ + uint32_t pa_num = 0; /* numerator of drop-probability */ + uint32_t pa_den = 0; /* denominator of drop-probability */ + uint32_t pa_num_count = 0; + + pa_num = (red->avg - red_cfg->min_th) >> (red_cfg->wq_log2); + + pa_num_count = red->count * pa_num; + + if (red_cfg->pa_const <= pa_num_count) + return 1; + + pa_den = red_cfg->pa_const - pa_num_count; + + /* If drop, generate and save random number to be used next time */ + if (unlikely((rte_red_rand_val % pa_den) < pa_num)) { + rte_red_rand_val = rte_fast_rand(); + + return 1; + } + + /* No drop */ + return 0; +} + +/** + * @brief Decides if new packet should be enqeued or dropped in queue non-empty case + * + * @param red_cfg [in] config pointer to a RED configuration parameter structure + * @param red [in,out] data pointer to RED runtime data + * @param q [in] current queue size (measured in packets) + * + * @return Operation status + * @retval 0 enqueue the packet + * @retval 1 drop the packet based on max threshold criterion + * @retval 2 drop the packet based on mark probability criterion + */ +static inline int +rte_red_enqueue_nonempty(const struct rte_red_config *red_cfg, + struct rte_red *red, + const unsigned q) +{ + RTE_RED_ASSERT(red_cfg != NULL); + RTE_RED_ASSERT(red != NULL); + + /** + * EWMA filter (Sally Floyd and Van Jacobson): + * avg = (1 - wq) * avg + wq * q + * avg = avg + q * wq - avg * wq + * + * We select: wq = 2^(-n). Let scaled version of avg be: avg_s = avg * 2^(N+n). We get: + * avg_s = avg_s + q * 2^N - avg_s * 2^(-n) + * + * By using shift left/right operations, we get: + * avg_s = avg_s + (q << N) - (avg_s >> n) + * avg_s += (q << N) - (avg_s >> n) + */ + + /* avg update */ + red->avg += (q << RTE_RED_SCALING) - (red->avg >> red_cfg->wq_log2); + + /* avg < min_th: do not mark the packet */ + if (red->avg < red_cfg->min_th) { + red->count ++; + return 0; + } + + /* min_th <= avg < max_th: mark the packet with pa probability */ + if (red->avg < red_cfg->max_th) { + if (!__rte_red_drop(red_cfg, red)) { + red->count ++; + return 0; + } + + red->count = 0; + return 2; + } + + /* max_th <= avg: always mark the packet */ + red->count = 0; + return 1; +} + +/** + * @brief Decides if new packet should be enqeued or dropped + * Updates run time data based on new queue size value. + * Based on new queue average and RED configuration parameters + * gives verdict whether to enqueue or drop the packet. + * + * @param red_cfg [in] config pointer to a RED configuration parameter structure + * @param red [in,out] data pointer to RED runtime data + * @param q [in] updated queue size in packets + * @param time [in] current time stamp + * + * @return Operation status + * @retval 0 enqueue the packet + * @retval 1 drop the packet based on max threshold criteria + * @retval 2 drop the packet based on mark probability criteria + */ +static inline int +rte_red_enqueue(const struct rte_red_config *red_cfg, + struct rte_red *red, + const unsigned q, + const uint64_t time) +{ + RTE_RED_ASSERT(red_cfg != NULL); + RTE_RED_ASSERT(red != NULL); + + if (q != 0) { + return rte_red_enqueue_nonempty(red_cfg, red, q); + } else { + return rte_red_enqueue_empty(red_cfg, red, time); + } +} + +/** + * @brief Callback to records time that queue became empty + * + * @param red [in,out] data pointer to RED runtime data + * @param time [in] current time stamp + */ +static inline void +rte_red_mark_queue_empty(struct rte_red *red, const uint64_t time) +{ + red->q_time = time; +} + +#ifdef __cplusplus +} +#endif + +#endif /* __RTE_RED_H_INCLUDED__ */ |