src/patches/linux-3.2-codel/0006-codel-use-u16-field-instead-of-31bits-for-rec_inv_sq.patch

   1 From: Eric Dumazet <eric.dumazet@gmail.com>
   2 Date: Sat, 12 May 2012 21:23:23 +0000
   3 Subject: [PATCH 6/7] codel: use u16 field instead of 31bits for rec_inv_sqrt
   4
   5 commit 6ff272c9ad65eda219cd975b9da2dbc31cc812ee upstream.
   6
   7 David pointed out gcc might generate poor code with 31bit fields.
   8
   9 Using u16 is more than enough and permits a better code output.
  10
  11 Also make the code intent more readable using constants, fixed point arithmetic
  12 not being trivial for everybody.
  13
  14 Suggested-by: David Miller <davem@davemloft.net>
  15 Signed-off-by: Eric Dumazet <edumazet@google.com>
  16 Signed-off-by: David S. Miller <davem@davemloft.net>
  17 ---
  18  include/net/codel.h |   25 +++++++++++++++----------
  19  1 file changed, 15 insertions(+), 10 deletions(-)
  20
  21 diff --git a/include/net/codel.h b/include/net/codel.h
  22 index bd8747c..7546517 100644
  23 --- a/include/net/codel.h
  24 +++ b/include/net/codel.h
  25 @@ -133,13 +133,17 @@ struct codel_params {
  26  struct codel_vars {
  27         u32             count;
  28         u32             lastcount;
  29 -       bool            dropping:1;
  30 -       u32             rec_inv_sqrt:31;
  31 +       bool            dropping;
  32 +       u16             rec_inv_sqrt;
  33         codel_time_t    first_above_time;
  34         codel_time_t    drop_next;
  35         codel_time_t    ldelay;
  36  };
  37
  38 +#define REC_INV_SQRT_BITS (8 * sizeof(u16)) /* or sizeof_in_bits(rec_inv_sqrt) */
  39 +/* needed shift to get a Q0.32 number from rec_inv_sqrt */
  40 +#define REC_INV_SQRT_SHIFT (32 - REC_INV_SQRT_BITS)
  41 +
  42  /**
  43   * struct codel_stats - contains codel shared variables and stats
  44   * @maxpacket: largest packet we've seen so far
  45 @@ -173,17 +177,18 @@ static void codel_stats_init(struct codel_stats *stats)
  46   * http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Iterative_methods_for_reciprocal_square_roots
  47   * new_invsqrt = (invsqrt / 2) * (3 - count * invsqrt^2)
  48   *
  49 - * Here, invsqrt is a fixed point number (< 1.0), 31bit mantissa)
  50 + * Here, invsqrt is a fixed point number (< 1.0), 32bit mantissa, aka Q0.32
  51   */
  52  static void codel_Newton_step(struct codel_vars *vars)
  53  {
  54 -       u32 invsqrt = vars->rec_inv_sqrt;
  55 -       u32 invsqrt2 = ((u64)invsqrt * invsqrt) >> 31;
  56 -       u64 val = (3LL << 31) - ((u64)vars->count * invsqrt2);
  57 +       u32 invsqrt = ((u32)vars->rec_inv_sqrt) << REC_INV_SQRT_SHIFT;
  58 +       u32 invsqrt2 = ((u64)invsqrt * invsqrt) >> 32;
  59 +       u64 val = (3LL << 32) - ((u64)vars->count * invsqrt2);
  60
  61 -       val = (val * invsqrt) >> 32;
  62 +       val >>= 2; /* avoid overflow in following multiply */
  63 +       val = (val * invsqrt) >> (32 - 2 + 1);
  64
  65 -       vars->rec_inv_sqrt = val;
  66 +       vars->rec_inv_sqrt = val >> REC_INV_SQRT_SHIFT;
  67  }
  68
  69  /*
  70 @@ -195,7 +200,7 @@ static codel_time_t codel_control_law(codel_time_t t,
  71                                       codel_time_t interval,
  72                                       u32 rec_inv_sqrt)
  73  {
  74 -       return t + reciprocal_divide(interval, rec_inv_sqrt << 1);
  75 +       return t + reciprocal_divide(interval, rec_inv_sqrt << REC_INV_SQRT_SHIFT);
  76  }
  77
  78
  79 @@ -326,7 +331,7 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch,
  80                         codel_Newton_step(vars);
  81                 } else {
  82                         vars->count = 1;
  83 -                       vars->rec_inv_sqrt = 0x7fffffff;
  84 +                       vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
  85                 }
  86                 vars->lastcount = vars->count;
  87                 vars->drop_next = codel_control_law(now, params->interval,
  88 --
  89 1.7.10
  90