1 #ifndef __NET_SCHED_CODEL_H
2 #define __NET_SCHED_CODEL_H
5 * Codel - The Controlled-Delay Active Queue Management algorithm
7 * Copyright (C) 2011-2012 Kathleen Nichols <nichols@pollere.com>
8 * Copyright (C) 2011-2012 Van Jacobson <van@pollere.net>
9 * Copyright (C) 2012 Michael D. Taht <dave.taht@bufferbloat.net>
10 * Copyright (C) 2012 Eric Dumazet <edumazet@google.com>
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions
15 * 1. Redistributions of source code must retain the above copyright
16 * notice, this list of conditions, and the following disclaimer,
17 * without modification.
18 * 2. Redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the distribution.
21 * 3. The names of the authors may not be used to endorse or promote products
22 * derived from this software without specific prior written permission.
24 * Alternatively, provided that this notice is retained in full, this
25 * software may be distributed under the terms of the GNU General
26 * Public License ("GPL") version 2, in which case the provisions of the
27 * GPL apply INSTEAD OF those given above.
29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
30 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
31 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
32 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
33 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
34 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
35 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
36 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
37 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
38 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
39 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
44 #include <linux/types.h>
45 #include <linux/ktime.h>
46 #include <linux/skbuff.h>
47 #include <net/pkt_sched.h>
48 #include <net/inet_ecn.h>
50 /* Controlling Queue Delay (CoDel) algorithm
51 * =========================================
52 * Source : Kathleen Nichols and Van Jacobson
53 * http://queue.acm.org/detail.cfm?id=2209336
55 * Implemented on linux by Dave Taht and Eric Dumazet
59 /* CoDel uses a 1024 nsec clock, encoded in u32
60 * This gives a range of 2199 seconds, because of signed compares
62 typedef u32 codel_time_t
;
63 typedef s32 codel_tdiff_t
;
64 #define CODEL_SHIFT 10
65 #define MS2TIME(a) ((a * NSEC_PER_MSEC) >> CODEL_SHIFT)
67 static inline codel_time_t
codel_get_time(void)
69 u64 ns
= ktime_to_ns(ktime_get());
71 return ns
>> CODEL_SHIFT
;
74 #define codel_time_after(a, b) ((s32)(a) - (s32)(b) > 0)
75 #define codel_time_after_eq(a, b) ((s32)(a) - (s32)(b) >= 0)
76 #define codel_time_before(a, b) ((s32)(a) - (s32)(b) < 0)
77 #define codel_time_before_eq(a, b) ((s32)(a) - (s32)(b) <= 0)
79 /* Qdiscs using codel plugin must use codel_skb_cb in their own cb[] */
81 codel_time_t enqueue_time
;
84 static struct codel_skb_cb
*get_codel_cb(const struct sk_buff
*skb
)
86 qdisc_cb_private_validate(skb
, sizeof(struct codel_skb_cb
));
87 return (struct codel_skb_cb
*)qdisc_skb_cb(skb
)->data
;
90 static codel_time_t
codel_get_enqueue_time(const struct sk_buff
*skb
)
92 return get_codel_cb(skb
)->enqueue_time
;
95 static void codel_set_enqueue_time(struct sk_buff
*skb
)
97 get_codel_cb(skb
)->enqueue_time
= codel_get_time();
100 static inline u32
codel_time_to_us(codel_time_t val
)
102 u64 valns
= ((u64
)val
<< CODEL_SHIFT
);
104 do_div(valns
, NSEC_PER_USEC
);
109 * struct codel_params - contains codel parameters
110 * @target: target queue size (in time units)
111 * @interval: width of moving time window
112 * @ecn: is Explicit Congestion Notification enabled
114 struct codel_params
{
116 codel_time_t interval
;
121 * struct codel_vars - contains codel variables
122 * @count: how many drops we've done since the last time we
123 * entered dropping state
124 * @lastcount: count at entry to dropping state
125 * @dropping: set to true if in dropping state
126 * @first_above_time: when we went (or will go) continuously above target
128 * @drop_next: time to drop next packet, or when we dropped last
129 * @ldelay: sojourn time of last dequeued packet
135 codel_time_t first_above_time
;
136 codel_time_t drop_next
;
141 * struct codel_stats - contains codel shared variables and stats
142 * @maxpacket: largest packet we've seen so far
143 * @drop_count: temp count of dropped packets in dequeue()
144 * ecn_mark: number of packets we ECN marked instead of dropping
152 static void codel_params_init(struct codel_params
*params
)
154 params
->interval
= MS2TIME(100);
155 params
->target
= MS2TIME(5);
159 static void codel_vars_init(struct codel_vars
*vars
)
162 vars
->first_above_time
= 0;
163 vars
->dropping
= false; /* exit dropping state */
168 static void codel_stats_init(struct codel_stats
*stats
)
170 stats
->maxpacket
= 256;
173 /* return interval/sqrt(x) with good precision
174 * relies on int_sqrt(unsigned long x) kernel implementation
176 static u32
codel_inv_sqrt(u32 _interval
, u32 _x
)
178 u64 interval
= _interval
;
179 unsigned long x
= _x
;
181 /* Scale operands for max precision */
183 #if BITS_PER_LONG == 64
184 x
<<= 32; /* On 64bit arches, we can prescale x by 32bits */
188 while (x
< (1UL << (BITS_PER_LONG
- 2))) {
192 do_div(interval
, int_sqrt(x
));
193 return (u32
)interval
;
196 static codel_time_t
codel_control_law(codel_time_t t
,
197 codel_time_t interval
,
200 return t
+ codel_inv_sqrt(interval
, count
);
204 static bool codel_should_drop(struct sk_buff
*skb
,
205 unsigned int *backlog
,
206 struct codel_vars
*vars
,
207 struct codel_params
*params
,
208 struct codel_stats
*stats
,
214 vars
->first_above_time
= 0;
218 vars
->ldelay
= now
- codel_get_enqueue_time(skb
);
219 *backlog
-= qdisc_pkt_len(skb
);
221 if (unlikely(qdisc_pkt_len(skb
) > stats
->maxpacket
))
222 stats
->maxpacket
= qdisc_pkt_len(skb
);
224 if (codel_time_before(vars
->ldelay
, params
->target
) ||
225 *backlog
<= stats
->maxpacket
) {
226 /* went below - stay below for at least interval */
227 vars
->first_above_time
= 0;
231 if (vars
->first_above_time
== 0) {
232 /* just went above from below. If we stay above
233 * for at least interval we'll say it's ok to drop
235 vars
->first_above_time
= now
+ params
->interval
;
236 } else if (codel_time_after(now
, vars
->first_above_time
)) {
242 typedef struct sk_buff
* (*codel_skb_dequeue_t
)(struct codel_vars
*vars
,
245 static struct sk_buff
*codel_dequeue(struct Qdisc
*sch
,
246 struct codel_params
*params
,
247 struct codel_vars
*vars
,
248 struct codel_stats
*stats
,
249 codel_skb_dequeue_t dequeue_func
,
252 struct sk_buff
*skb
= dequeue_func(vars
, sch
);
257 vars
->dropping
= false;
260 now
= codel_get_time();
261 drop
= codel_should_drop(skb
, backlog
, vars
, params
, stats
, now
);
262 if (vars
->dropping
) {
264 /* sojourn time below target - leave dropping state */
265 vars
->dropping
= false;
266 } else if (codel_time_after_eq(now
, vars
->drop_next
)) {
267 /* It's time for the next drop. Drop the current
268 * packet and dequeue the next. The dequeue might
269 * take us out of dropping state.
270 * If not, schedule the next drop.
271 * A large backlog might result in drop rates so high
272 * that the next drop should happen now,
273 * hence the while loop.
275 while (vars
->dropping
&&
276 codel_time_after_eq(now
, vars
->drop_next
)) {
277 if (++vars
->count
== 0) /* avoid zero divides */
279 if (params
->ecn
&& INET_ECN_set_ce(skb
)) {
282 codel_control_law(vars
->drop_next
,
287 qdisc_drop(skb
, sch
);
289 skb
= dequeue_func(vars
, sch
);
290 if (!codel_should_drop(skb
, backlog
,
291 vars
, params
, stats
, now
)) {
292 /* leave dropping state */
293 vars
->dropping
= false;
295 /* and schedule the next drop */
297 codel_control_law(vars
->drop_next
,
304 if (params
->ecn
&& INET_ECN_set_ce(skb
)) {
307 qdisc_drop(skb
, sch
);
310 skb
= dequeue_func(vars
, sch
);
311 drop
= codel_should_drop(skb
, backlog
, vars
, params
,
314 vars
->dropping
= true;
315 /* if min went above target close to when we last went below it
316 * assume that the drop rate that controlled the queue on the
317 * last cycle is a good starting point to control it now.
319 if (codel_time_before(now
- vars
->drop_next
,
320 16 * params
->interval
)) {
321 vars
->count
= (vars
->count
- vars
->lastcount
) | 1;
325 vars
->lastcount
= vars
->count
;
326 vars
->drop_next
= codel_control_law(now
, params
->interval
,