summaryrefslogtreecommitdiff
path: root/include/net/codel.h
diff options
context:
space:
mode:
authorAndré Fabian Silva Delgado <emulatorman@parabola.nu>2016-09-11 04:34:46 -0300
committerAndré Fabian Silva Delgado <emulatorman@parabola.nu>2016-09-11 04:34:46 -0300
commit863981e96738983919de841ec669e157e6bdaeb0 (patch)
treed6d89a12e7eb8017837c057935a2271290907f76 /include/net/codel.h
parent8dec7c70575785729a6a9e6719a955e9c545bcab (diff)
Linux-libre 4.7.1-gnupck-4.7.1-gnu
Diffstat (limited to 'include/net/codel.h')
-rw-r--r--include/net/codel.h217
1 files changed, 4 insertions, 213 deletions
diff --git a/include/net/codel.h b/include/net/codel.h
index d168aca11..a6e428f80 100644
--- a/include/net/codel.h
+++ b/include/net/codel.h
@@ -87,27 +87,6 @@ static inline codel_time_t codel_get_time(void)
((s32)((a) - (b)) >= 0))
#define codel_time_before_eq(a, b) codel_time_after_eq(b, a)
-/* Qdiscs using codel plugin must use codel_skb_cb in their own cb[] */
-struct codel_skb_cb {
- codel_time_t enqueue_time;
-};
-
-static struct codel_skb_cb *get_codel_cb(const struct sk_buff *skb)
-{
- qdisc_cb_private_validate(skb, sizeof(struct codel_skb_cb));
- return (struct codel_skb_cb *)qdisc_skb_cb(skb)->data;
-}
-
-static codel_time_t codel_get_enqueue_time(const struct sk_buff *skb)
-{
- return get_codel_cb(skb)->enqueue_time;
-}
-
-static void codel_set_enqueue_time(struct sk_buff *skb)
-{
- get_codel_cb(skb)->enqueue_time = codel_get_time();
-}
-
static inline u32 codel_time_to_us(codel_time_t val)
{
u64 valns = ((u64)val << CODEL_SHIFT);
@@ -176,198 +155,10 @@ struct codel_stats {
#define CODEL_DISABLED_THRESHOLD INT_MAX
-static void codel_params_init(struct codel_params *params,
- const struct Qdisc *sch)
-{
- params->interval = MS2TIME(100);
- params->target = MS2TIME(5);
- params->mtu = psched_mtu(qdisc_dev(sch));
- params->ce_threshold = CODEL_DISABLED_THRESHOLD;
- params->ecn = false;
-}
-
-static void codel_vars_init(struct codel_vars *vars)
-{
- memset(vars, 0, sizeof(*vars));
-}
-
-static void codel_stats_init(struct codel_stats *stats)
-{
- stats->maxpacket = 0;
-}
-
-/*
- * http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Iterative_methods_for_reciprocal_square_roots
- * new_invsqrt = (invsqrt / 2) * (3 - count * invsqrt^2)
- *
- * Here, invsqrt is a fixed point number (< 1.0), 32bit mantissa, aka Q0.32
- */
-static void codel_Newton_step(struct codel_vars *vars)
-{
- u32 invsqrt = ((u32)vars->rec_inv_sqrt) << REC_INV_SQRT_SHIFT;
- u32 invsqrt2 = ((u64)invsqrt * invsqrt) >> 32;
- u64 val = (3LL << 32) - ((u64)vars->count * invsqrt2);
-
- val >>= 2; /* avoid overflow in following multiply */
- val = (val * invsqrt) >> (32 - 2 + 1);
-
- vars->rec_inv_sqrt = val >> REC_INV_SQRT_SHIFT;
-}
-
-/*
- * CoDel control_law is t + interval/sqrt(count)
- * We maintain in rec_inv_sqrt the reciprocal value of sqrt(count) to avoid
- * both sqrt() and divide operation.
- */
-static codel_time_t codel_control_law(codel_time_t t,
- codel_time_t interval,
- u32 rec_inv_sqrt)
-{
- return t + reciprocal_scale(interval, rec_inv_sqrt << REC_INV_SQRT_SHIFT);
-}
-
-static bool codel_should_drop(const struct sk_buff *skb,
- struct Qdisc *sch,
- struct codel_vars *vars,
- struct codel_params *params,
- struct codel_stats *stats,
- codel_time_t now)
-{
- bool ok_to_drop;
-
- if (!skb) {
- vars->first_above_time = 0;
- return false;
- }
-
- vars->ldelay = now - codel_get_enqueue_time(skb);
- sch->qstats.backlog -= qdisc_pkt_len(skb);
-
- if (unlikely(qdisc_pkt_len(skb) > stats->maxpacket))
- stats->maxpacket = qdisc_pkt_len(skb);
-
- if (codel_time_before(vars->ldelay, params->target) ||
- sch->qstats.backlog <= params->mtu) {
- /* went below - stay below for at least interval */
- vars->first_above_time = 0;
- return false;
- }
- ok_to_drop = false;
- if (vars->first_above_time == 0) {
- /* just went above from below. If we stay above
- * for at least interval we'll say it's ok to drop
- */
- vars->first_above_time = now + params->interval;
- } else if (codel_time_after(now, vars->first_above_time)) {
- ok_to_drop = true;
- }
- return ok_to_drop;
-}
-
+typedef u32 (*codel_skb_len_t)(const struct sk_buff *skb);
+typedef codel_time_t (*codel_skb_time_t)(const struct sk_buff *skb);
+typedef void (*codel_skb_drop_t)(struct sk_buff *skb, void *ctx);
typedef struct sk_buff * (*codel_skb_dequeue_t)(struct codel_vars *vars,
- struct Qdisc *sch);
+ void *ctx);
-static struct sk_buff *codel_dequeue(struct Qdisc *sch,
- struct codel_params *params,
- struct codel_vars *vars,
- struct codel_stats *stats,
- codel_skb_dequeue_t dequeue_func)
-{
- struct sk_buff *skb = dequeue_func(vars, sch);
- codel_time_t now;
- bool drop;
-
- if (!skb) {
- vars->dropping = false;
- return skb;
- }
- now = codel_get_time();
- drop = codel_should_drop(skb, sch, vars, params, stats, now);
- if (vars->dropping) {
- if (!drop) {
- /* sojourn time below target - leave dropping state */
- vars->dropping = false;
- } else if (codel_time_after_eq(now, vars->drop_next)) {
- /* It's time for the next drop. Drop the current
- * packet and dequeue the next. The dequeue might
- * take us out of dropping state.
- * If not, schedule the next drop.
- * A large backlog might result in drop rates so high
- * that the next drop should happen now,
- * hence the while loop.
- */
- while (vars->dropping &&
- codel_time_after_eq(now, vars->drop_next)) {
- vars->count++; /* dont care of possible wrap
- * since there is no more divide
- */
- codel_Newton_step(vars);
- if (params->ecn && INET_ECN_set_ce(skb)) {
- stats->ecn_mark++;
- vars->drop_next =
- codel_control_law(vars->drop_next,
- params->interval,
- vars->rec_inv_sqrt);
- goto end;
- }
- stats->drop_len += qdisc_pkt_len(skb);
- qdisc_drop(skb, sch);
- stats->drop_count++;
- skb = dequeue_func(vars, sch);
- if (!codel_should_drop(skb, sch,
- vars, params, stats, now)) {
- /* leave dropping state */
- vars->dropping = false;
- } else {
- /* and schedule the next drop */
- vars->drop_next =
- codel_control_law(vars->drop_next,
- params->interval,
- vars->rec_inv_sqrt);
- }
- }
- }
- } else if (drop) {
- u32 delta;
-
- if (params->ecn && INET_ECN_set_ce(skb)) {
- stats->ecn_mark++;
- } else {
- stats->drop_len += qdisc_pkt_len(skb);
- qdisc_drop(skb, sch);
- stats->drop_count++;
-
- skb = dequeue_func(vars, sch);
- drop = codel_should_drop(skb, sch, vars, params,
- stats, now);
- }
- vars->dropping = true;
- /* if min went above target close to when we last went below it
- * assume that the drop rate that controlled the queue on the
- * last cycle is a good starting point to control it now.
- */
- delta = vars->count - vars->lastcount;
- if (delta > 1 &&
- codel_time_before(now - vars->drop_next,
- 16 * params->interval)) {
- vars->count = delta;
- /* we dont care if rec_inv_sqrt approximation
- * is not very precise :
- * Next Newton steps will correct it quadratically.
- */
- codel_Newton_step(vars);
- } else {
- vars->count = 1;
- vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
- }
- vars->lastcount = vars->count;
- vars->drop_next = codel_control_law(now, params->interval,
- vars->rec_inv_sqrt);
- }
-end:
- if (skb && codel_time_after(vars->ldelay, params->ce_threshold) &&
- INET_ECN_set_ce(skb))
- stats->ce_mark++;
- return skb;
-}
#endif