Commit | Line | Data |
---|---|---|
76e3cc12 ED |
1 | #ifndef __NET_SCHED_CODEL_H |
2 | #define __NET_SCHED_CODEL_H | |
3 | ||
4 | /* | |
5 | * Codel - The Controlled-Delay Active Queue Management algorithm | |
6 | * | |
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> | |
80ba92fa | 10 | * Copyright (C) 2012,2015 Eric Dumazet <edumazet@google.com> |
76e3cc12 ED |
11 | * |
12 | * Redistribution and use in source and binary forms, with or without | |
13 | * modification, are permitted provided that the following conditions | |
14 | * are met: | |
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. | |
23 | * | |
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. | |
28 | * | |
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 | |
40 | * DAMAGE. | |
41 | * | |
42 | */ | |
43 | ||
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> | |
49 | ||
50 | /* Controlling Queue Delay (CoDel) algorithm | |
51 | * ========================================= | |
52 | * Source : Kathleen Nichols and Van Jacobson | |
53 | * http://queue.acm.org/detail.cfm?id=2209336 | |
54 | * | |
55 | * Implemented on linux by Dave Taht and Eric Dumazet | |
56 | */ | |
57 | ||
58 | ||
59 | /* CoDel uses a 1024 nsec clock, encoded in u32 | |
60 | * This gives a range of 2199 seconds, because of signed compares | |
61 | */ | |
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) | |
66 | ||
67 | static inline codel_time_t codel_get_time(void) | |
68 | { | |
d2de875c | 69 | u64 ns = ktime_get_ns(); |
76e3cc12 ED |
70 | |
71 | return ns >> CODEL_SHIFT; | |
72 | } | |
73 | ||
1ba3aab3 JDB |
74 | /* Dealing with timer wrapping, according to RFC 1982, as desc in wikipedia: |
75 | * https://en.wikipedia.org/wiki/Serial_number_arithmetic#General_Solution | |
76 | * codel_time_after(a,b) returns true if the time a is after time b. | |
77 | */ | |
78 | #define codel_time_after(a, b) \ | |
79 | (typecheck(codel_time_t, a) && \ | |
80 | typecheck(codel_time_t, b) && \ | |
81 | ((s32)((a) - (b)) > 0)) | |
82 | #define codel_time_before(a, b) codel_time_after(b, a) | |
83 | ||
84 | #define codel_time_after_eq(a, b) \ | |
85 | (typecheck(codel_time_t, a) && \ | |
86 | typecheck(codel_time_t, b) && \ | |
87 | ((s32)((a) - (b)) >= 0)) | |
88 | #define codel_time_before_eq(a, b) codel_time_after_eq(b, a) | |
76e3cc12 | 89 | |
76e3cc12 ED |
90 | static inline u32 codel_time_to_us(codel_time_t val) |
91 | { | |
92 | u64 valns = ((u64)val << CODEL_SHIFT); | |
93 | ||
94 | do_div(valns, NSEC_PER_USEC); | |
95 | return (u32)valns; | |
96 | } | |
97 | ||
98 | /** | |
99 | * struct codel_params - contains codel parameters | |
100 | * @target: target queue size (in time units) | |
80ba92fa | 101 | * @ce_threshold: threshold for marking packets with ECN CE |
76e3cc12 | 102 | * @interval: width of moving time window |
a5d28090 | 103 | * @mtu: device mtu, or minimal queue backlog in bytes. |
76e3cc12 ED |
104 | * @ecn: is Explicit Congestion Notification enabled |
105 | */ | |
106 | struct codel_params { | |
107 | codel_time_t target; | |
80ba92fa | 108 | codel_time_t ce_threshold; |
76e3cc12 | 109 | codel_time_t interval; |
a5d28090 | 110 | u32 mtu; |
76e3cc12 ED |
111 | bool ecn; |
112 | }; | |
113 | ||
114 | /** | |
115 | * struct codel_vars - contains codel variables | |
116 | * @count: how many drops we've done since the last time we | |
117 | * entered dropping state | |
118 | * @lastcount: count at entry to dropping state | |
119 | * @dropping: set to true if in dropping state | |
536edd67 | 120 | * @rec_inv_sqrt: reciprocal value of sqrt(count) >> 1 |
76e3cc12 ED |
121 | * @first_above_time: when we went (or will go) continuously above target |
122 | * for interval | |
123 | * @drop_next: time to drop next packet, or when we dropped last | |
124 | * @ldelay: sojourn time of last dequeued packet | |
125 | */ | |
126 | struct codel_vars { | |
127 | u32 count; | |
128 | u32 lastcount; | |
6ff272c9 ED |
129 | bool dropping; |
130 | u16 rec_inv_sqrt; | |
76e3cc12 ED |
131 | codel_time_t first_above_time; |
132 | codel_time_t drop_next; | |
133 | codel_time_t ldelay; | |
134 | }; | |
135 | ||
6ff272c9 ED |
136 | #define REC_INV_SQRT_BITS (8 * sizeof(u16)) /* or sizeof_in_bits(rec_inv_sqrt) */ |
137 | /* needed shift to get a Q0.32 number from rec_inv_sqrt */ | |
138 | #define REC_INV_SQRT_SHIFT (32 - REC_INV_SQRT_BITS) | |
139 | ||
76e3cc12 ED |
140 | /** |
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() | |
2ccccf5f | 144 | * @drop_len: bytes of dropped packets in dequeue() |
76e3cc12 | 145 | * ecn_mark: number of packets we ECN marked instead of dropping |
80ba92fa | 146 | * ce_mark: number of packets CE marked because sojourn time was above ce_threshold |
76e3cc12 ED |
147 | */ |
148 | struct codel_stats { | |
149 | u32 maxpacket; | |
150 | u32 drop_count; | |
2ccccf5f | 151 | u32 drop_len; |
76e3cc12 | 152 | u32 ecn_mark; |
80ba92fa | 153 | u32 ce_mark; |
76e3cc12 ED |
154 | }; |
155 | ||
80ba92fa ED |
156 | #define CODEL_DISABLED_THRESHOLD INT_MAX |
157 | ||
79bdc4c8 MK |
158 | typedef u32 (*codel_skb_len_t)(const struct sk_buff *skb); |
159 | typedef codel_time_t (*codel_skb_time_t)(const struct sk_buff *skb); | |
160 | typedef void (*codel_skb_drop_t)(struct sk_buff *skb, void *ctx); | |
161 | typedef struct sk_buff * (*codel_skb_dequeue_t)(struct codel_vars *vars, | |
162 | void *ctx); | |
163 | ||
76e3cc12 | 164 | #endif |