From patchwork Fri Apr 22 12:15:59 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Michal Kazior X-Patchwork-Id: 613574 X-Patchwork-Delegate: davem@davemloft.net Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 3qrvgH0mpNz9t4h for ; Fri, 22 Apr 2016 22:14:19 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=tieto.com header.i=@tieto.com header.b=b/c9814p; dkim-atps=neutral Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752059AbcDVMOR (ORCPT ); Fri, 22 Apr 2016 08:14:17 -0400 Received: from mail-lf0-f53.google.com ([209.85.215.53]:34618 "EHLO mail-lf0-f53.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751911AbcDVMOO (ORCPT ); Fri, 22 Apr 2016 08:14:14 -0400 Received: by mail-lf0-f53.google.com with SMTP id j11so78077292lfb.1 for ; Fri, 22 Apr 2016 05:14:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=tieto.com; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=bhh3oW5JJISLsZTAWZck7UhNVFw56R+Nm3LMWAgNS+s=; b=b/c9814pv75IdmrTlPnAS9Ur5JmtOfcrvubFSKuNO0mCp/K+U+P3E7i2qLWnal5Z6D BC90vmRuxNyLQuZz8FqsjBYeGIGsIceDRyOjvYGcYtuaNQ0VZibm8IG5Jg3do6JaCFst Z4Jr2AvploJrE7h7gpvX+wC/i6NjN3fiZvv24= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=bhh3oW5JJISLsZTAWZck7UhNVFw56R+Nm3LMWAgNS+s=; b=XHvSoTvjZzItxg2aJc/rAGNIEahoxNtC15Q4fC7RwqDytt4gLQfYERLJx1Q/o8t9cY YJxVO7jvdx7ngkPjVHvtZiqix4RGX7pNzo5BdlTUzvEzU4zQGyIW7R3h1A7nDoqKyteU tqsdRjHEghPijTw1nBo3AWK6WXXRSTaBEgsjzLyZ+XgcHRciNOyqIm5qwxwHeVhYxYYV pOlhyXES/BQCrrwylOhJgY0+Ut74yNLR7ppVOmm0Rh3++qV8S0X5ioBwxTfKaaM5zlWy Qpeg+fHvDn0yk0+nRVygvbkoMV5gvOyoTgroRtZInvnovZyaiq0Z+8S0e3uabOck732A 3jsA== X-Gm-Message-State: AOPr4FUgmqC2+J5IhxMVAk2kj8Yd4zPiYA2IMNWmv3aymucfDsEPi1N4/tdwy02BKseVA4Hnc4p01GWJkGTzgMguY7cD4jkq9AJlb3k0BUXT/olNXRsbx3p7wiEqr+DHXC+zSklYd65kzIQWYtLDbyKGPzGevUvFlrUst02Xn5wCvETe39RjxKg2BVOY X-Received: by 10.25.169.73 with SMTP id s70mr7654994lfe.141.1461327252244; Fri, 22 Apr 2016 05:14:12 -0700 (PDT) Received: from localhost.localdomain ([91.198.246.10]) by smtp.gmail.com with ESMTPSA id uo2sm513748lbb.31.2016.04.22.05.14.10 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Fri, 22 Apr 2016 05:14:11 -0700 (PDT) From: Michal Kazior To: netdev@vger.kernel.org Cc: davem@davemloft.net, johannes@sipsolutions.net, Michal Kazior Subject: [PATCH 2/2] codel: split into multiple files Date: Fri, 22 Apr 2016 14:15:59 +0200 Message-Id: <1461327359-21646-3-git-send-email-michal.kazior@tieto.com> X-Mailer: git-send-email 2.1.4 In-Reply-To: <1461327359-21646-1-git-send-email-michal.kazior@tieto.com> References: <1461327359-21646-1-git-send-email-michal.kazior@tieto.com> X-DomainID: tieto.com Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org It was impossible to include codel.h for the purpose of having access to codel_params or codel_vars structure definitions and using them for embedding in other more complex structures. This splits allows codel.h itself to be treated like any other header file while codel_qdisc.h and codel_impl.h contain function definitions with logic that was previously in codel.h. This copies over copyrights and doesn't involve code changes other than adding a few additional include directives to net/sched/sch*codel.c. Signed-off-by: Michal Kazior --- include/net/codel.h | 223 ---------------------------------------- include/net/codel_impl.h | 255 ++++++++++++++++++++++++++++++++++++++++++++++ include/net/codel_qdisc.h | 73 +++++++++++++ net/sched/sch_codel.c | 2 + net/sched/sch_fq_codel.c | 2 + 5 files changed, 332 insertions(+), 223 deletions(-) create mode 100644 include/net/codel_impl.h create mode 100644 include/net/codel_qdisc.h diff --git a/include/net/codel.h b/include/net/codel.h index 06ac687b4909..a6e428f80135 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,212 +155,10 @@ struct codel_stats { #define CODEL_DISABLED_THRESHOLD INT_MAX -static void codel_params_init(struct codel_params *params) -{ - params->interval = MS2TIME(100); - params->target = MS2TIME(5); - 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); -} - 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, void *ctx); -static bool codel_should_drop(const struct sk_buff *skb, - void *ctx, - struct codel_vars *vars, - struct codel_params *params, - struct codel_stats *stats, - codel_skb_len_t skb_len_func, - codel_skb_time_t skb_time_func, - u32 *backlog, - codel_time_t now) -{ - bool ok_to_drop; - u32 skb_len; - - if (!skb) { - vars->first_above_time = 0; - return false; - } - - skb_len = skb_len_func(skb); - vars->ldelay = now - skb_time_func(skb); - - if (unlikely(skb_len > stats->maxpacket)) - stats->maxpacket = skb_len; - - if (codel_time_before(vars->ldelay, params->target) || - *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; -} - -static struct sk_buff *codel_dequeue(void *ctx, - u32 *backlog, - struct codel_params *params, - struct codel_vars *vars, - struct codel_stats *stats, - codel_skb_len_t skb_len_func, - codel_skb_time_t skb_time_func, - codel_skb_drop_t drop_func, - codel_skb_dequeue_t dequeue_func) -{ - struct sk_buff *skb = dequeue_func(vars, ctx); - codel_time_t now; - bool drop; - - if (!skb) { - vars->dropping = false; - return skb; - } - now = codel_get_time(); - drop = codel_should_drop(skb, ctx, vars, params, stats, - skb_len_func, skb_time_func, backlog, 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 += skb_len_func(skb); - drop_func(skb, ctx); - stats->drop_count++; - skb = dequeue_func(vars, ctx); - if (!codel_should_drop(skb, ctx, - vars, params, stats, - skb_len_func, - skb_time_func, - backlog, 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 += skb_len_func(skb); - drop_func(skb, ctx); - stats->drop_count++; - - skb = dequeue_func(vars, ctx); - drop = codel_should_drop(skb, ctx, vars, params, - stats, skb_len_func, - skb_time_func, backlog, 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 diff --git a/include/net/codel_impl.h b/include/net/codel_impl.h new file mode 100644 index 000000000000..d289b91dcd65 --- /dev/null +++ b/include/net/codel_impl.h @@ -0,0 +1,255 @@ +#ifndef __NET_SCHED_CODEL_IMPL_H +#define __NET_SCHED_CODEL_IMPL_H + +/* + * Codel - The Controlled-Delay Active Queue Management algorithm + * + * Copyright (C) 2011-2012 Kathleen Nichols + * Copyright (C) 2011-2012 Van Jacobson + * Copyright (C) 2012 Michael D. Taht + * Copyright (C) 2012,2015 Eric Dumazet + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions, and the following disclaimer, + * without modification. + * 2. 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. + * 3. The names of the authors may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * Alternatively, provided that this notice is retained in full, this + * software may be distributed under the terms of the GNU General + * Public License ("GPL") version 2, in which case the provisions of the + * GPL apply INSTEAD OF those given above. + * + * 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. + * + */ + +/* Controlling Queue Delay (CoDel) algorithm + * ========================================= + * Source : Kathleen Nichols and Van Jacobson + * http://queue.acm.org/detail.cfm?id=2209336 + * + * Implemented on linux by Dave Taht and Eric Dumazet + */ + +static void codel_params_init(struct codel_params *params) +{ + params->interval = MS2TIME(100); + params->target = MS2TIME(5); + 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, + void *ctx, + struct codel_vars *vars, + struct codel_params *params, + struct codel_stats *stats, + codel_skb_len_t skb_len_func, + codel_skb_time_t skb_time_func, + u32 *backlog, + codel_time_t now) +{ + bool ok_to_drop; + u32 skb_len; + + if (!skb) { + vars->first_above_time = 0; + return false; + } + + skb_len = skb_len_func(skb); + vars->ldelay = now - skb_time_func(skb); + + if (unlikely(skb_len > stats->maxpacket)) + stats->maxpacket = skb_len; + + if (codel_time_before(vars->ldelay, params->target) || + *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; +} + +static struct sk_buff *codel_dequeue(void *ctx, + u32 *backlog, + struct codel_params *params, + struct codel_vars *vars, + struct codel_stats *stats, + codel_skb_len_t skb_len_func, + codel_skb_time_t skb_time_func, + codel_skb_drop_t drop_func, + codel_skb_dequeue_t dequeue_func) +{ + struct sk_buff *skb = dequeue_func(vars, ctx); + codel_time_t now; + bool drop; + + if (!skb) { + vars->dropping = false; + return skb; + } + now = codel_get_time(); + drop = codel_should_drop(skb, ctx, vars, params, stats, + skb_len_func, skb_time_func, backlog, 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 += skb_len_func(skb); + drop_func(skb, ctx); + stats->drop_count++; + skb = dequeue_func(vars, ctx); + if (!codel_should_drop(skb, ctx, + vars, params, stats, + skb_len_func, + skb_time_func, + backlog, 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 += skb_len_func(skb); + drop_func(skb, ctx); + stats->drop_count++; + + skb = dequeue_func(vars, ctx); + drop = codel_should_drop(skb, ctx, vars, params, + stats, skb_len_func, + skb_time_func, backlog, 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 diff --git a/include/net/codel_qdisc.h b/include/net/codel_qdisc.h new file mode 100644 index 000000000000..8144d9cd2908 --- /dev/null +++ b/include/net/codel_qdisc.h @@ -0,0 +1,73 @@ +#ifndef __NET_SCHED_CODEL_QDISC_H +#define __NET_SCHED_CODEL_QDISC_H + +/* + * Codel - The Controlled-Delay Active Queue Management algorithm + * + * Copyright (C) 2011-2012 Kathleen Nichols + * Copyright (C) 2011-2012 Van Jacobson + * Copyright (C) 2012 Michael D. Taht + * Copyright (C) 2012,2015 Eric Dumazet + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions, and the following disclaimer, + * without modification. + * 2. 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. + * 3. The names of the authors may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * Alternatively, provided that this notice is retained in full, this + * software may be distributed under the terms of the GNU General + * Public License ("GPL") version 2, in which case the provisions of the + * GPL apply INSTEAD OF those given above. + * + * 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. + * + */ + +/* Controlling Queue Delay (CoDel) algorithm + * ========================================= + * Source : Kathleen Nichols and Van Jacobson + * http://queue.acm.org/detail.cfm?id=2209336 + * + * Implemented on linux by Dave Taht and Eric Dumazet + */ + +/* 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(); +} + +#endif diff --git a/net/sched/sch_codel.c b/net/sched/sch_codel.c index 512a94abe351..dddf3bb65a32 100644 --- a/net/sched/sch_codel.c +++ b/net/sched/sch_codel.c @@ -49,6 +49,8 @@ #include #include #include +#include +#include #define DEFAULT_CODEL_LIMIT 1000 diff --git a/net/sched/sch_fq_codel.c b/net/sched/sch_fq_codel.c index dcf7266e6901..a5e420b3d4ab 100644 --- a/net/sched/sch_fq_codel.c +++ b/net/sched/sch_fq_codel.c @@ -24,6 +24,8 @@ #include #include #include +#include +#include /* Fair Queue CoDel. *