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