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