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> |
10 | * Copyright (C) 2012,2015 Eric Dumazet <edumazet@google.com> |
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 | |
48 | /* Controlling Queue Delay (CoDel) algorithm |
49 | * ========================================= |
50 | * Source : Kathleen Nichols and Van Jacobson |
51 | * http://queue.acm.org/detail.cfm?id=2209336 |
52 | * |
53 | * Implemented on linux by Dave Taht and Eric Dumazet |
54 | */ |
55 | |
56 | |
57 | /* CoDel uses a 1024 nsec clock, encoded in u32 |
58 | * This gives a range of 2199 seconds, because of signed compares |
59 | */ |
60 | typedef u32 codel_time_t; |
61 | typedef s32 codel_tdiff_t; |
62 | #define CODEL_SHIFT 10 |
63 | #define MS2TIME(a) ((a * NSEC_PER_MSEC) >> CODEL_SHIFT) |
64 | |
65 | static inline codel_time_t codel_get_time(void) |
66 | { |
67 | u64 ns = ktime_get_ns(); |
68 | |
69 | return ns >> CODEL_SHIFT; |
70 | } |
71 | |
72 | /* Dealing with timer wrapping, according to RFC 1982, as desc in wikipedia: |
73 | * https://en.wikipedia.org/wiki/Serial_number_arithmetic#General_Solution |
74 | * codel_time_after(a,b) returns true if the time a is after time b. |
75 | */ |
76 | #define codel_time_after(a, b) \ |
77 | (typecheck(codel_time_t, a) && \ |
78 | typecheck(codel_time_t, b) && \ |
79 | ((s32)((a) - (b)) > 0)) |
80 | #define codel_time_before(a, b) codel_time_after(b, a) |
81 | |
82 | #define codel_time_after_eq(a, b) \ |
83 | (typecheck(codel_time_t, a) && \ |
84 | typecheck(codel_time_t, b) && \ |
85 | ((s32)((a) - (b)) >= 0)) |
86 | #define codel_time_before_eq(a, b) codel_time_after_eq(b, a) |
87 | |
88 | static inline u32 codel_time_to_us(codel_time_t val) |
89 | { |
90 | u64 valns = ((u64)val << CODEL_SHIFT); |
91 | |
92 | do_div(valns, NSEC_PER_USEC); |
93 | return (u32)valns; |
94 | } |
95 | |
96 | /** |
97 | * struct codel_params - contains codel parameters |
98 | * @target: target queue size (in time units) |
99 | * @ce_threshold: threshold for marking packets with ECN CE |
100 | * @interval: width of moving time window |
101 | * @mtu: device mtu, or minimal queue backlog in bytes. |
102 | * @ecn: is Explicit Congestion Notification enabled |
103 | * @ce_threshold_selector: apply ce_threshold to packets matching this value |
104 | * in the diffserv/ECN byte of the IP header |
105 | * @ce_threshold_mask: mask to apply to ce_threshold_selector comparison |
106 | */ |
107 | struct codel_params { |
108 | codel_time_t target; |
109 | codel_time_t ce_threshold; |
110 | codel_time_t interval; |
111 | u32 mtu; |
112 | bool ecn; |
113 | u8 ce_threshold_selector; |
114 | u8 ce_threshold_mask; |
115 | }; |
116 | |
117 | /** |
118 | * struct codel_vars - contains codel variables |
119 | * @count: how many drops we've done since the last time we |
120 | * entered dropping state |
121 | * @lastcount: count at entry to dropping state |
122 | * @dropping: set to true if in dropping state |
123 | * @rec_inv_sqrt: reciprocal value of sqrt(count) >> 1 |
124 | * @first_above_time: when we went (or will go) continuously above target |
125 | * for interval |
126 | * @drop_next: time to drop next packet, or when we dropped last |
127 | * @ldelay: sojourn time of last dequeued packet |
128 | */ |
129 | struct codel_vars { |
130 | u32 count; |
131 | u32 lastcount; |
132 | bool dropping; |
133 | u16 rec_inv_sqrt; |
134 | codel_time_t first_above_time; |
135 | codel_time_t drop_next; |
136 | codel_time_t ldelay; |
137 | }; |
138 | |
139 | #define REC_INV_SQRT_BITS (8 * sizeof(u16)) /* or sizeof_in_bits(rec_inv_sqrt) */ |
140 | /* needed shift to get a Q0.32 number from rec_inv_sqrt */ |
141 | #define REC_INV_SQRT_SHIFT (32 - REC_INV_SQRT_BITS) |
142 | |
143 | /** |
144 | * struct codel_stats - contains codel shared variables and stats |
145 | * @maxpacket: largest packet we've seen so far |
146 | * @drop_count: temp count of dropped packets in dequeue() |
147 | * @drop_len: bytes of dropped packets in dequeue() |
148 | * @ecn_mark: number of packets we ECN marked instead of dropping |
149 | * @ce_mark: number of packets CE marked because sojourn time was above ce_threshold |
150 | */ |
151 | struct codel_stats { |
152 | u32 maxpacket; |
153 | u32 drop_count; |
154 | u32 drop_len; |
155 | u32 ecn_mark; |
156 | u32 ce_mark; |
157 | }; |
158 | |
159 | #define CODEL_DISABLED_THRESHOLD INT_MAX |
160 | |
161 | typedef u32 (*codel_skb_len_t)(const struct sk_buff *skb); |
162 | typedef codel_time_t (*codel_skb_time_t)(const struct sk_buff *skb); |
163 | typedef void (*codel_skb_drop_t)(struct sk_buff *skb, void *ctx); |
164 | typedef struct sk_buff * (*codel_skb_dequeue_t)(struct codel_vars *vars, |
165 | void *ctx); |
166 | |
167 | #endif |
168 | |