From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wi0-f175.google.com (mail-wi0-f175.google.com [209.85.212.175]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority" (verified OK)) by huchra.bufferbloat.net (Postfix) with ESMTPS id 04B53201B20 for ; Sat, 12 May 2012 06:32:20 -0700 (PDT) Received: by wibhn6 with SMTP id hn6so997644wib.10 for ; Sat, 12 May 2012 06:32:17 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=subject:from:to:cc:content-type:date:message-id:mime-version :x-mailer:content-transfer-encoding; bh=pTb2wtVz1WoPdSROpTzgAJmpI8kr0UTfXyqVEMnomGk=; b=bV4xUggoFhpYZtQaDIftRCr92dx5pmaYrZbpVjwKTbtbFD25OYO99TQGMEbZ53AbIZ nvpQpPV0LRpS0GjMrcH0HZJIREOibiv2Hl4+8yEVCgmFjob5qQRSIlWeYTZ2GFD39K6R w3+RtVDJMsRZyKrgZe1kBGmNbhG5DWu9YYPvtlXCNeZQfxnjrpfd/foFk3ZHPiQwRWCG Az5fkmRkGsUZ//FEFG/77llZ5f8cb0AqcFrReg2emQ+8SxfKVXozyDFz1tqlcUlGR1U7 rLraiUUFS8l2ggHCOl4PJsUZJTZpBQbbmHeYAskusSmcEQ7IHouSFtiZzdaER5rmW3JC gs4w== Received: by 10.180.107.101 with SMTP id hb5mr4406290wib.7.1336829537380; Sat, 12 May 2012 06:32:17 -0700 (PDT) Received: from [172.28.131.74] ([74.125.122.49]) by mx.google.com with ESMTPS id z3sm19547549wix.0.2012.05.12.06.32.14 (version=SSLv3 cipher=OTHER); Sat, 12 May 2012 06:32:16 -0700 (PDT) From: Eric Dumazet To: David Miller Content-Type: text/plain; charset="UTF-8" Date: Sat, 12 May 2012 15:32:13 +0200 Message-ID: <1336829533.31653.1108.camel@edumazet-glaptop> Mime-Version: 1.0 X-Mailer: Evolution 2.28.3 Content-Transfer-Encoding: 7bit X-Mailman-Approved-At: Sat, 12 May 2012 08:05:33 -0700 Cc: Dave Taht , Nandita Dukkipati , netdev , codel@lists.bufferbloat.net, Yuchung Cheng , Stephen Hemminger , Matt Mathis Subject: [Codel] [PATCH net-next] codel: use Newton method instead of sqrt() and divides X-BeenThere: codel@lists.bufferbloat.net X-Mailman-Version: 2.1.13 Precedence: list List-Id: CoDel AQM discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 12 May 2012 13:32:21 -0000 From: Eric Dumazet As Van pointed out, interval/sqrt(count) can be implemented using multiplies only. http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Iterative_methods_for_reciprocal_square_roots This patch implements the Newton method and reciprocal divide. Total cost is 15 cycles instead of 120 on my Corei5 machine (64bit kernel). There is a small 'error' for count values < 5, but we don't really care. I reuse a hole in struct codel_vars : - pack the dropping boolean into one bit - use 31bit to store the reciprocal value of sqrt(count). Suggested-by: Van Jacobson Signed-off-by: Eric Dumazet Cc: Dave Taht Cc: Kathleen Nichols Cc: Tom Herbert Cc: Matt Mathis Cc: Yuchung Cheng Cc: Nandita Dukkipati Cc: Stephen Hemminger --- include/net/codel.h | 68 ++++++++++++++++++++++-------------------- 1 file changed, 37 insertions(+), 31 deletions(-) diff --git a/include/net/codel.h b/include/net/codel.h index bce2cef..bd8747c 100644 --- a/include/net/codel.h +++ b/include/net/codel.h @@ -46,6 +46,7 @@ #include #include #include +#include /* Controlling Queue Delay (CoDel) algorithm * ========================================= @@ -123,6 +124,7 @@ struct codel_params { * entered dropping state * @lastcount: count at entry to dropping state * @dropping: set to true if in dropping state + * @rec_inv_sqrt: reciprocal value of sqrt(count) >> 1 * @first_above_time: when we went (or will go) continuously above target * for interval * @drop_next: time to drop next packet, or when we dropped last @@ -131,7 +133,8 @@ struct codel_params { struct codel_vars { u32 count; u32 lastcount; - bool dropping; + bool dropping:1; + u32 rec_inv_sqrt:31; codel_time_t first_above_time; codel_time_t drop_next; codel_time_t ldelay; @@ -158,11 +161,7 @@ static void codel_params_init(struct codel_params *params) static void codel_vars_init(struct codel_vars *vars) { - vars->drop_next = 0; - vars->first_above_time = 0; - vars->dropping = false; /* exit dropping state */ - vars->count = 0; - vars->lastcount = 0; + memset(vars, 0, sizeof(*vars)); } static void codel_stats_init(struct codel_stats *stats) @@ -170,38 +169,37 @@ static void codel_stats_init(struct codel_stats *stats) stats->maxpacket = 256; } -/* return interval/sqrt(x) with good precision - * relies on int_sqrt(unsigned long x) kernel implementation +/* + * 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), 31bit mantissa) */ -static u32 codel_inv_sqrt(u32 _interval, u32 _x) +static void codel_Newton_step(struct codel_vars *vars) { - u64 interval = _interval; - unsigned long x = _x; + u32 invsqrt = vars->rec_inv_sqrt; + u32 invsqrt2 = ((u64)invsqrt * invsqrt) >> 31; + u64 val = (3LL << 31) - ((u64)vars->count * invsqrt2); - /* Scale operands for max precision */ - -#if BITS_PER_LONG == 64 - x <<= 32; /* On 64bit arches, we can prescale x by 32bits */ - interval <<= 16; -#endif + val = (val * invsqrt) >> 32; - while (x < (1UL << (BITS_PER_LONG - 2))) { - x <<= 2; - interval <<= 1; - } - do_div(interval, int_sqrt(x)); - return (u32)interval; + vars->rec_inv_sqrt = val; } +/* + * 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 count) + u32 rec_inv_sqrt) { - return t + codel_inv_sqrt(interval, count); + return t + reciprocal_divide(interval, rec_inv_sqrt << 1); } -static bool codel_should_drop(struct sk_buff *skb, +static bool codel_should_drop(const struct sk_buff *skb, unsigned int *backlog, struct codel_vars *vars, struct codel_params *params, @@ -274,14 +272,16 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch, */ while (vars->dropping && codel_time_after_eq(now, vars->drop_next)) { - if (++vars->count == 0) /* avoid zero divides */ - vars->count = ~0U; + 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->count); + vars->rec_inv_sqrt); goto end; } qdisc_drop(skb, sch); @@ -296,7 +296,7 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch, vars->drop_next = codel_control_law(vars->drop_next, params->interval, - vars->count); + vars->rec_inv_sqrt); } } } @@ -319,12 +319,18 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch, if (codel_time_before(now - vars->drop_next, 16 * params->interval)) { vars->count = (vars->count - vars->lastcount) | 1; + /* 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 = 0x7fffffff; } vars->lastcount = vars->count; vars->drop_next = codel_control_law(now, params->interval, - vars->count); + vars->rec_inv_sqrt); } end: return skb;