]>
Commit | Line | Data |
---|---|---|
97bb1c57 AF |
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 |