rte_red.h

Go to the documentation of this file.

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

#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         
#define RTE_RED_S                           (1 << 22)  
#define RTE_RED_MAX_TH_MAX                  1023       
#define RTE_RED_WQ_LOG2_MIN                 1          
#define RTE_RED_WQ_LOG2_MAX                 12         
#define RTE_RED_MAXP_INV_MIN                1          
#define RTE_RED_MAXP_INV_MAX                255        
#define RTE_RED_2POW16                      (1<<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 */

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

struct rte_red_params {
        uint16_t min_th;   
        uint16_t max_th;   
        uint16_t maxp_inv; 
        uint16_t wq_log2;  
};

struct rte_red_config {
        uint32_t min_th;   
        uint32_t max_th;   
        uint32_t pa_const; 
        uint8_t maxp_inv;  
        uint8_t wq_log2;   
};

struct rte_red {
        uint32_t avg;      
        uint32_t count;    
        uint64_t q_time;   
};

int
rte_red_rt_data_init(struct rte_red *red);

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

static inline uint32_t
rte_fast_rand(void)
{
        rte_red_rand_seed = (214013 * rte_red_rand_seed) + 2531011;
        return (rte_red_rand_seed >> 10);
}

static inline uint16_t
__rte_red_calc_qempty_factor(uint8_t wq_log2, uint16_t m)
{
        uint32_t n = 0;
        uint32_t f = 0;

        n = m * rte_red_log2_1_minus_Wq[wq_log2 - RTE_RED_WQ_LOG2_MIN];

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

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

        time_diff = time - red->q_time;

        m = time_diff / RTE_RED_S;

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

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

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

        /* 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;
}

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);
        }
}

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