diff options
Diffstat (limited to 'src/dpdk_lib18/librte_sched/rte_red.h')
| -rwxr-xr-x | src/dpdk_lib18/librte_sched/rte_red.h | 453 |
1 files changed, 0 insertions, 453 deletions
diff --git a/src/dpdk_lib18/librte_sched/rte_red.h b/src/dpdk_lib18/librte_sched/rte_red.h deleted file mode 100755 index 0d8412ff..00000000 --- a/src/dpdk_lib18/librte_sched/rte_red.h +++ /dev/null @@ -1,453 +0,0 @@ -/*- - * 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 [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 [in,out] config pointer to a RED configuration parameter structure - * @param [in] wq_log2 log2 of the filter weight, valid range is: - * RTE_RED_WQ_LOG2_MIN <= wq_log2 <= RTE_RED_WQ_LOG2_MAX - * @param [in] min_th queue minimum threshold in number of packets - * @param [in] max_th queue maximum threshold in number of packets - * @param [in] maxp_inv 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 [in] wq_log2, where EWMA filter weight wq = 1/(2 ^ wq_log2) - * @param [in] m 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 [in] config pointer to a RED configuration parameter structure - * @param [in,out] data pointer to RED runtime data - * @param [in] time 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 [in] config pointer to structure defining RED parameters - * @param [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 [in] config pointer to a RED configuration parameter structure - * @param [in,out] data pointer to RED runtime data - * @param [in] q 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 [in] config pointer to a RED configuration parameter structure - * @param [in,out] data pointer to RED runtime data - * @param [in] q updated queue size in packets - * @param [in] time 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 [in,out] data pointer to RED runtime data - * @param [in] time 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__ */ |