compat: PTR_RET is backported in RHEL6.7
[~emulex/for-vlad/old/compat.git] / include / net / codel.h
1 #include <linux/version.h>
2
3 #if (LINUX_VERSION_CODE >= KERNEL_VERSION(3,5,0))
4 #include_next <net/codel.h>
5 #else
6
7 #ifndef __NET_SCHED_CODEL_H
8 #define __NET_SCHED_CODEL_H
9
10 /*
11  * Codel - The Controlled-Delay Active Queue Management algorithm
12  *
13  *  Copyright (C) 2011-2012 Kathleen Nichols <nichols@pollere.com>
14  *  Copyright (C) 2011-2012 Van Jacobson <van@pollere.net>
15  *  Copyright (C) 2012 Michael D. Taht <dave.taht@bufferbloat.net>
16  *  Copyright (C) 2012 Eric Dumazet <edumazet@google.com>
17  *
18  * Redistribution and use in source and binary forms, with or without
19  * modification, are permitted provided that the following conditions
20  * are met:
21  * 1. Redistributions of source code must retain the above copyright
22  *    notice, this list of conditions, and the following disclaimer,
23  *    without modification.
24  * 2. Redistributions in binary form must reproduce the above copyright
25  *    notice, this list of conditions and the following disclaimer in the
26  *    documentation and/or other materials provided with the distribution.
27  * 3. The names of the authors may not be used to endorse or promote products
28  *    derived from this software without specific prior written permission.
29  *
30  * Alternatively, provided that this notice is retained in full, this
31  * software may be distributed under the terms of the GNU General
32  * Public License ("GPL") version 2, in which case the provisions of the
33  * GPL apply INSTEAD OF those given above.
34  *
35  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
36  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
37  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
38  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
39  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
40  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
41  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
42  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
43  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
44  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
45  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
46  * DAMAGE.
47  *
48  */
49
50 #include <linux/types.h>
51 #include <linux/ktime.h>
52 #include <linux/skbuff.h>
53 #include <net/pkt_sched.h>
54 #include <net/inet_ecn.h>
55 #include <linux/reciprocal_div.h>
56
57 /* Controlling Queue Delay (CoDel) algorithm
58  * =========================================
59  * Source : Kathleen Nichols and Van Jacobson
60  * http://queue.acm.org/detail.cfm?id=2209336
61  *
62  * Implemented on linux by Dave Taht and Eric Dumazet
63  */
64
65
66 /* CoDel uses a 1024 nsec clock, encoded in u32
67  * This gives a range of 2199 seconds, because of signed compares
68  */
69 typedef u32 codel_time_t;
70 typedef s32 codel_tdiff_t;
71 #define CODEL_SHIFT 10
72 #define MS2TIME(a) ((a * NSEC_PER_MSEC) >> CODEL_SHIFT)
73
74 static inline codel_time_t codel_get_time(void)
75 {
76         u64 ns = ktime_to_ns(ktime_get());
77
78         return ns >> CODEL_SHIFT;
79 }
80
81 #define codel_time_after(a, b)          ((s32)(a) - (s32)(b) > 0)
82 #define codel_time_after_eq(a, b)       ((s32)(a) - (s32)(b) >= 0)
83 #define codel_time_before(a, b)         ((s32)(a) - (s32)(b) < 0)
84 #define codel_time_before_eq(a, b)      ((s32)(a) - (s32)(b) <= 0)
85
86 /* Qdiscs using codel plugin must use codel_skb_cb in their own cb[] */
87 struct codel_skb_cb {
88         codel_time_t enqueue_time;
89 };
90
91 static struct codel_skb_cb *get_codel_cb(const struct sk_buff *skb)
92 {
93         qdisc_cb_private_validate(skb, sizeof(struct codel_skb_cb));
94 #if (LINUX_VERSION_CODE <= KERNEL_VERSION(2,6,37))
95         return (struct codel_skb_cb *)qdisc_skb_cb((struct sk_buff *) skb)->data;
96 #else
97         return (struct codel_skb_cb *)qdisc_skb_cb(skb)->data;
98 #endif
99 }
100
101 static codel_time_t codel_get_enqueue_time(const struct sk_buff *skb)
102 {
103         return get_codel_cb(skb)->enqueue_time;
104 }
105
106 static void codel_set_enqueue_time(struct sk_buff *skb)
107 {
108         get_codel_cb(skb)->enqueue_time = codel_get_time();
109 }
110
111 static inline u32 codel_time_to_us(codel_time_t val)
112 {
113         u64 valns = ((u64)val << CODEL_SHIFT);
114
115         do_div(valns, NSEC_PER_USEC);
116         return (u32)valns;
117 }
118
119 /**
120  * struct codel_params - contains codel parameters
121  * @target:     target queue size (in time units)
122  * @interval:   width of moving time window
123  * @ecn:        is Explicit Congestion Notification enabled
124  */
125 struct codel_params {
126         codel_time_t    target;
127         codel_time_t    interval;
128         bool            ecn;
129 };
130
131 /**
132  * struct codel_vars - contains codel variables
133  * @count:              how many drops we've done since the last time we
134  *                      entered dropping state
135  * @lastcount:          count at entry to dropping state
136  * @dropping:           set to true if in dropping state
137  * @rec_inv_sqrt:       reciprocal value of sqrt(count) >> 1
138  * @first_above_time:   when we went (or will go) continuously above target
139  *                      for interval
140  * @drop_next:          time to drop next packet, or when we dropped last
141  * @ldelay:             sojourn time of last dequeued packet
142  */
143 struct codel_vars {
144         u32             count;
145         u32             lastcount;
146         bool            dropping;
147         u16             rec_inv_sqrt;
148         codel_time_t    first_above_time;
149         codel_time_t    drop_next;
150         codel_time_t    ldelay;
151 };
152
153 #define REC_INV_SQRT_BITS (8 * sizeof(u16)) /* or sizeof_in_bits(rec_inv_sqrt) */
154 /* needed shift to get a Q0.32 number from rec_inv_sqrt */
155 #define REC_INV_SQRT_SHIFT (32 - REC_INV_SQRT_BITS)
156
157 /**
158  * struct codel_stats - contains codel shared variables and stats
159  * @maxpacket:  largest packet we've seen so far
160  * @drop_count: temp count of dropped packets in dequeue()
161  * ecn_mark:    number of packets we ECN marked instead of dropping
162  */
163 struct codel_stats {
164         u32             maxpacket;
165         u32             drop_count;
166         u32             ecn_mark;
167 };
168
169 static void codel_params_init(struct codel_params *params)
170 {
171         params->interval = MS2TIME(100);
172         params->target = MS2TIME(5);
173         params->ecn = false;
174 }
175
176 static void codel_vars_init(struct codel_vars *vars)
177 {
178         memset(vars, 0, sizeof(*vars));
179 }
180
181 static void codel_stats_init(struct codel_stats *stats)
182 {
183         stats->maxpacket = 256;
184 }
185
186 /*
187  * http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Iterative_methods_for_reciprocal_square_roots
188  * new_invsqrt = (invsqrt / 2) * (3 - count * invsqrt^2)
189  *
190  * Here, invsqrt is a fixed point number (< 1.0), 32bit mantissa, aka Q0.32
191  */
192 static void codel_Newton_step(struct codel_vars *vars)
193 {
194         u32 invsqrt = ((u32)vars->rec_inv_sqrt) << REC_INV_SQRT_SHIFT;
195         u32 invsqrt2 = ((u64)invsqrt * invsqrt) >> 32;
196         u64 val = (3LL << 32) - ((u64)vars->count * invsqrt2);
197
198         val >>= 2; /* avoid overflow in following multiply */
199         val = (val * invsqrt) >> (32 - 2 + 1);
200
201         vars->rec_inv_sqrt = val >> REC_INV_SQRT_SHIFT;
202 }
203
204 /*
205  * CoDel control_law is t + interval/sqrt(count)
206  * We maintain in rec_inv_sqrt the reciprocal value of sqrt(count) to avoid
207  * both sqrt() and divide operation.
208  */
209 static codel_time_t codel_control_law(codel_time_t t,
210                                       codel_time_t interval,
211                                       u32 rec_inv_sqrt)
212 {
213         return t + reciprocal_divide(interval, rec_inv_sqrt << REC_INV_SQRT_SHIFT);
214 }
215
216
217 static bool codel_should_drop(const struct sk_buff *skb,
218                               struct Qdisc *sch,
219                               struct codel_vars *vars,
220                               struct codel_params *params,
221                               struct codel_stats *stats,
222                               codel_time_t now)
223 {
224         bool ok_to_drop;
225
226         if (!skb) {
227                 vars->first_above_time = 0;
228                 return false;
229         }
230
231         vars->ldelay = now - codel_get_enqueue_time(skb);
232 #if (LINUX_VERSION_CODE <= KERNEL_VERSION(2,6,37))
233         sch->qstats.backlog -= qdisc_pkt_len((struct sk_buff *)skb);
234 #else
235         sch->qstats.backlog -= qdisc_pkt_len(skb);
236 #endif
237
238 #if (LINUX_VERSION_CODE <= KERNEL_VERSION(2,6,37))
239         if (unlikely(qdisc_pkt_len((struct sk_buff *)skb) > stats->maxpacket))
240                 stats->maxpacket = qdisc_pkt_len((struct sk_buff *)skb);
241 #else
242         if (unlikely(qdisc_pkt_len(skb) > stats->maxpacket))
243                 stats->maxpacket = qdisc_pkt_len(skb);
244 #endif
245
246         if (codel_time_before(vars->ldelay, params->target) ||
247             sch->qstats.backlog <= stats->maxpacket) {
248                 /* went below - stay below for at least interval */
249                 vars->first_above_time = 0;
250                 return false;
251         }
252         ok_to_drop = false;
253         if (vars->first_above_time == 0) {
254                 /* just went above from below. If we stay above
255                  * for at least interval we'll say it's ok to drop
256                  */
257                 vars->first_above_time = now + params->interval;
258         } else if (codel_time_after(now, vars->first_above_time)) {
259                 ok_to_drop = true;
260         }
261         return ok_to_drop;
262 }
263
264 typedef struct sk_buff * (*codel_skb_dequeue_t)(struct codel_vars *vars,
265                                                 struct Qdisc *sch);
266
267 static struct sk_buff *codel_dequeue(struct Qdisc *sch,
268                                      struct codel_params *params,
269                                      struct codel_vars *vars,
270                                      struct codel_stats *stats,
271                                      codel_skb_dequeue_t dequeue_func)
272 {
273         struct sk_buff *skb = dequeue_func(vars, sch);
274         codel_time_t now;
275         bool drop;
276
277         if (!skb) {
278                 vars->dropping = false;
279                 return skb;
280         }
281         now = codel_get_time();
282         drop = codel_should_drop(skb, sch, vars, params, stats, now);
283         if (vars->dropping) {
284                 if (!drop) {
285                         /* sojourn time below target - leave dropping state */
286                         vars->dropping = false;
287                 } else if (codel_time_after_eq(now, vars->drop_next)) {
288                         /* It's time for the next drop. Drop the current
289                          * packet and dequeue the next. The dequeue might
290                          * take us out of dropping state.
291                          * If not, schedule the next drop.
292                          * A large backlog might result in drop rates so high
293                          * that the next drop should happen now,
294                          * hence the while loop.
295                          */
296                         while (vars->dropping &&
297                                codel_time_after_eq(now, vars->drop_next)) {
298                                 vars->count++; /* dont care of possible wrap
299                                                 * since there is no more divide
300                                                 */
301                                 codel_Newton_step(vars);
302                                 if (params->ecn && INET_ECN_set_ce(skb)) {
303                                         stats->ecn_mark++;
304                                         vars->drop_next =
305                                                 codel_control_law(vars->drop_next,
306                                                                   params->interval,
307                                                                   vars->rec_inv_sqrt);
308                                         goto end;
309                                 }
310                                 qdisc_drop(skb, sch);
311                                 stats->drop_count++;
312                                 skb = dequeue_func(vars, sch);
313                                 if (!codel_should_drop(skb, sch,
314                                                        vars, params, stats, now)) {
315                                         /* leave dropping state */
316                                         vars->dropping = false;
317                                 } else {
318                                         /* and schedule the next drop */
319                                         vars->drop_next =
320                                                 codel_control_law(vars->drop_next,
321                                                                   params->interval,
322                                                                   vars->rec_inv_sqrt);
323                                 }
324                         }
325                 }
326         } else if (drop) {
327                 if (params->ecn && INET_ECN_set_ce(skb)) {
328                         stats->ecn_mark++;
329                 } else {
330                         qdisc_drop(skb, sch);
331                         stats->drop_count++;
332
333                         skb = dequeue_func(vars, sch);
334                         drop = codel_should_drop(skb, sch, vars, params,
335                                                  stats, now);
336                 }
337                 vars->dropping = true;
338                 /* if min went above target close to when we last went below it
339                  * assume that the drop rate that controlled the queue on the
340                  * last cycle is a good starting point to control it now.
341                  */
342                 if (codel_time_before(now - vars->drop_next,
343                                       16 * params->interval)) {
344                         vars->count = (vars->count - vars->lastcount) | 1;
345                         /* we dont care if rec_inv_sqrt approximation
346                          * is not very precise :
347                          * Next Newton steps will correct it quadratically.
348                          */
349                         codel_Newton_step(vars);
350                 } else {
351                         vars->count = 1;
352                         vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
353                 }
354                 vars->lastcount = vars->count;
355                 vars->drop_next = codel_control_law(now, params->interval,
356                                                     vars->rec_inv_sqrt);
357         }
358 end:
359         return skb;
360 }
361 #endif
362 #endif