src/patches/linux-3.2-codel/0002-codel-use-Newton-method-instead-of-sqrt-and-divides.patch

   1 From: Eric Dumazet <edumazet@google.com>
   2 Date: Sat, 12 May 2012 03:32:13 +0000
   3 Subject: [PATCH 2/7] codel: use Newton method instead of sqrt() and divides
   4
   5 commit 536edd67109df5e0cdb2c4ee759e9bade7976367 upstream.
   6
   7 As Van pointed out, interval/sqrt(count) can be implemented using
   8 multiplies only.
   9
  10 http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Iterative_methods_for_reciprocal_square_roots
  11
  12 This patch implements the Newton method and reciprocal divide.
  13
  14 Total cost is 15 cycles instead of 120 on my Corei5 machine (64bit
  15 kernel).
  16
  17 There is a small 'error' for count values < 5, but we don't really care.
  18
  19 I reuse a hole in struct codel_vars :
  20  - pack the dropping boolean into one bit
  21  - use 31bit to store the reciprocal value of sqrt(count).
  22
  23 Suggested-by: Van Jacobson <van@pollere.net>
  24 Signed-off-by: Eric Dumazet <edumazet@google.com>
  25 Cc: Dave Taht <dave.taht@bufferbloat.net>
  26 Cc: Kathleen Nichols <nichols@pollere.com>
  27 Cc: Tom Herbert <therbert@google.com>
  28 Cc: Matt Mathis <mattmathis@google.com>
  29 Cc: Yuchung Cheng <ycheng@google.com>
  30 Cc: Nandita Dukkipati <nanditad@google.com>
  31 Cc: Stephen Hemminger <shemminger@vyatta.com>
  32 Signed-off-by: David S. Miller <davem@davemloft.net>
  33 ---
  34  include/net/codel.h |   68 ++++++++++++++++++++++++++++-----------------------
  35  1 file changed, 37 insertions(+), 31 deletions(-)
  36
  37 diff --git a/include/net/codel.h b/include/net/codel.h
  38 index bce2cef..bd8747c 100644
  39 --- a/include/net/codel.h
  40 +++ b/include/net/codel.h
  41 @@ -46,6 +46,7 @@
  42  #include <linux/skbuff.h>
  43  #include <net/pkt_sched.h>
  44  #include <net/inet_ecn.h>
  45 +#include <linux/reciprocal_div.h>
  46
  47  /* Controlling Queue Delay (CoDel) algorithm
  48   * =========================================
  49 @@ -123,6 +124,7 @@ struct codel_params {
  50   *                     entered dropping state
  51   * @lastcount:         count at entry to dropping state
  52   * @dropping:          set to true if in dropping state
  53 + * @rec_inv_sqrt:      reciprocal value of sqrt(count) >> 1
  54   * @first_above_time:  when we went (or will go) continuously above target
  55   *                     for interval
  56   * @drop_next:         time to drop next packet, or when we dropped last
  57 @@ -131,7 +133,8 @@ struct codel_params {
  58  struct codel_vars {
  59         u32             count;
  60         u32             lastcount;
  61 -       bool            dropping;
  62 +       bool            dropping:1;
  63 +       u32             rec_inv_sqrt:31;
  64         codel_time_t    first_above_time;
  65         codel_time_t    drop_next;
  66         codel_time_t    ldelay;
  67 @@ -158,11 +161,7 @@ static void codel_params_init(struct codel_params *params)
  68
  69  static void codel_vars_init(struct codel_vars *vars)
  70  {
  71 -       vars->drop_next = 0;
  72 -       vars->first_above_time = 0;
  73 -       vars->dropping = false; /* exit dropping state */
  74 -       vars->count = 0;
  75 -       vars->lastcount = 0;
  76 +       memset(vars, 0, sizeof(*vars));
  77  }
  78
  79  static void codel_stats_init(struct codel_stats *stats)
  80 @@ -170,38 +169,37 @@ static void codel_stats_init(struct codel_stats *stats)
  81         stats->maxpacket = 256;
  82  }
  83
  84 -/* return interval/sqrt(x) with good precision
  85 - * relies on int_sqrt(unsigned long x) kernel implementation
  86 +/*
  87 + * http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Iterative_methods_for_reciprocal_square_roots
  88 + * new_invsqrt = (invsqrt / 2) * (3 - count * invsqrt^2)
  89 + *
  90 + * Here, invsqrt is a fixed point number (< 1.0), 31bit mantissa)
  91   */
  92 -static u32 codel_inv_sqrt(u32 _interval, u32 _x)
  93 +static void codel_Newton_step(struct codel_vars *vars)
  94  {
  95 -       u64 interval = _interval;
  96 -       unsigned long x = _x;
  97 +       u32 invsqrt = vars->rec_inv_sqrt;
  98 +       u32 invsqrt2 = ((u64)invsqrt * invsqrt) >> 31;
  99 +       u64 val = (3LL << 31) - ((u64)vars->count * invsqrt2);
 100
 101 -       /* Scale operands for max precision */
 102 -
 103 -#if BITS_PER_LONG == 64
 104 -       x <<= 32; /* On 64bit arches, we can prescale x by 32bits */
 105 -       interval <<= 16;
 106 -#endif
 107 +       val = (val * invsqrt) >> 32;
 108
 109 -       while (x < (1UL << (BITS_PER_LONG - 2))) {
 110 -               x <<= 2;
 111 -               interval <<= 1;
 112 -       }
 113 -       do_div(interval, int_sqrt(x));
 114 -       return (u32)interval;
 115 +       vars->rec_inv_sqrt = val;
 116  }
 117
 118 +/*
 119 + * CoDel control_law is t + interval/sqrt(count)
 120 + * We maintain in rec_inv_sqrt the reciprocal value of sqrt(count) to avoid
 121 + * both sqrt() and divide operation.
 122 + */
 123  static codel_time_t codel_control_law(codel_time_t t,
 124                                       codel_time_t interval,
 125 -                                     u32 count)
 126 +                                     u32 rec_inv_sqrt)
 127  {
 128 -       return t + codel_inv_sqrt(interval, count);
 129 +       return t + reciprocal_divide(interval, rec_inv_sqrt << 1);
 130  }
 131
 132
 133 -static bool codel_should_drop(struct sk_buff *skb,
 134 +static bool codel_should_drop(const struct sk_buff *skb,
 135                               unsigned int *backlog,
 136                               struct codel_vars *vars,
 137                               struct codel_params *params,
 138 @@ -274,14 +272,16 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch,
 139                          */
 140                         while (vars->dropping &&
 141                                codel_time_after_eq(now, vars->drop_next)) {
 142 -                               if (++vars->count == 0) /* avoid zero divides */
 143 -                                       vars->count = ~0U;
 144 +                               vars->count++; /* dont care of possible wrap
 145 +                                               * since there is no more divide
 146 +                                               */
 147 +                               codel_Newton_step(vars);
 148                                 if (params->ecn && INET_ECN_set_ce(skb)) {
 149                                         stats->ecn_mark++;
 150                                         vars->drop_next =
 151                                                 codel_control_law(vars->drop_next,
 152                                                                   params->interval,
 153 -                                                                 vars->count);
 154 +                                                                 vars->rec_inv_sqrt);
 155                                         goto end;
 156                                 }
 157                                 qdisc_drop(skb, sch);
 158 @@ -296,7 +296,7 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch,
 159                                         vars->drop_next =
 160                                                 codel_control_law(vars->drop_next,
 161                                                                   params->interval,
 162 -                                                                 vars->count);
 163 +                                                                 vars->rec_inv_sqrt);
 164                                 }
 165                         }
 166                 }
 167 @@ -319,12 +319,18 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch,
 168                 if (codel_time_before(now - vars->drop_next,
 169                                       16 * params->interval)) {
 170                         vars->count = (vars->count - vars->lastcount) | 1;
 171 +                       /* we dont care if rec_inv_sqrt approximation
 172 +                        * is not very precise :
 173 +                        * Next Newton steps will correct it quadratically.
 174 +                        */
 175 +                       codel_Newton_step(vars);
 176                 } else {
 177                         vars->count = 1;
 178 +                       vars->rec_inv_sqrt = 0x7fffffff;
 179                 }
 180                 vars->lastcount = vars->count;
 181                 vars->drop_next = codel_control_law(now, params->interval,
 182 -                                                   vars->count);
 183 +                                                   vars->rec_inv_sqrt);
 184         }
 185  end:
 186         return skb;
 187 --
 188 1.7.10
 189