~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/include/net/codel.h

Version: ~ [ linux-5.11-rc3 ] ~ [ linux-5.10.7 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.89 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.167 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.215 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.251 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.251 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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 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 #include <net/pkt_sched.h>
 48 #include <net/inet_ecn.h>
 49 #include <linux/reciprocal_div.h>
 50 
 51 /* Controlling Queue Delay (CoDel) algorithm
 52  * =========================================
 53  * Source : Kathleen Nichols and Van Jacobson
 54  * http://queue.acm.org/detail.cfm?id=2209336
 55  *
 56  * Implemented on linux by Dave Taht and Eric Dumazet
 57  */
 58 
 59 
 60 /* CoDel uses a 1024 nsec clock, encoded in u32
 61  * This gives a range of 2199 seconds, because of signed compares
 62  */
 63 typedef u32 codel_time_t;
 64 typedef s32 codel_tdiff_t;
 65 #define CODEL_SHIFT 10
 66 #define MS2TIME(a) ((a * NSEC_PER_MSEC) >> CODEL_SHIFT)
 67 
 68 static inline codel_time_t codel_get_time(void)
 69 {
 70         u64 ns = ktime_to_ns(ktime_get());
 71 
 72         return ns >> CODEL_SHIFT;
 73 }
 74 
 75 #define codel_time_after(a, b)          ((s32)(a) - (s32)(b) > 0)
 76 #define codel_time_after_eq(a, b)       ((s32)(a) - (s32)(b) >= 0)
 77 #define codel_time_before(a, b)         ((s32)(a) - (s32)(b) < 0)
 78 #define codel_time_before_eq(a, b)      ((s32)(a) - (s32)(b) <= 0)
 79 
 80 /* Qdiscs using codel plugin must use codel_skb_cb in their own cb[] */
 81 struct codel_skb_cb {
 82         codel_time_t enqueue_time;
 83 };
 84 
 85 static struct codel_skb_cb *get_codel_cb(const struct sk_buff *skb)
 86 {
 87         qdisc_cb_private_validate(skb, sizeof(struct codel_skb_cb));
 88         return (struct codel_skb_cb *)qdisc_skb_cb(skb)->data;
 89 }
 90 
 91 static codel_time_t codel_get_enqueue_time(const struct sk_buff *skb)
 92 {
 93         return get_codel_cb(skb)->enqueue_time;
 94 }
 95 
 96 static void codel_set_enqueue_time(struct sk_buff *skb)
 97 {
 98         get_codel_cb(skb)->enqueue_time = codel_get_time();
 99 }
100 
101 static inline u32 codel_time_to_us(codel_time_t val)
102 {
103         u64 valns = ((u64)val << CODEL_SHIFT);
104 
105         do_div(valns, NSEC_PER_USEC);
106         return (u32)valns;
107 }
108 
109 /**
110  * struct codel_params - contains codel parameters
111  * @target:     target queue size (in time units)
112  * @interval:   width of moving time window
113  * @ecn:        is Explicit Congestion Notification enabled
114  */
115 struct codel_params {
116         codel_time_t    target;
117         codel_time_t    interval;
118         bool            ecn;
119 };
120 
121 /**
122  * struct codel_vars - contains codel variables
123  * @count:              how many drops we've done since the last time we
124  *                      entered dropping state
125  * @lastcount:          count at entry to dropping state
126  * @dropping:           set to true if in dropping state
127  * @rec_inv_sqrt:       reciprocal value of sqrt(count) >> 1
128  * @first_above_time:   when we went (or will go) continuously above target
129  *                      for interval
130  * @drop_next:          time to drop next packet, or when we dropped last
131  * @ldelay:             sojourn time of last dequeued packet
132  */
133 struct codel_vars {
134         u32             count;
135         u32             lastcount;
136         bool            dropping;
137         u16             rec_inv_sqrt;
138         codel_time_t    first_above_time;
139         codel_time_t    drop_next;
140         codel_time_t    ldelay;
141 };
142 
143 #define REC_INV_SQRT_BITS (8 * sizeof(u16)) /* or sizeof_in_bits(rec_inv_sqrt) */
144 /* needed shift to get a Q0.32 number from rec_inv_sqrt */
145 #define REC_INV_SQRT_SHIFT (32 - REC_INV_SQRT_BITS)
146 
147 /**
148  * struct codel_stats - contains codel shared variables and stats
149  * @maxpacket:  largest packet we've seen so far
150  * @drop_count: temp count of dropped packets in dequeue()
151  * ecn_mark:    number of packets we ECN marked instead of dropping
152  */
153 struct codel_stats {
154         u32             maxpacket;
155         u32             drop_count;
156         u32             ecn_mark;
157 };
158 
159 static void codel_params_init(struct codel_params *params)
160 {
161         params->interval = MS2TIME(100);
162         params->target = MS2TIME(5);
163         params->ecn = false;
164 }
165 
166 static void codel_vars_init(struct codel_vars *vars)
167 {
168         memset(vars, 0, sizeof(*vars));
169 }
170 
171 static void codel_stats_init(struct codel_stats *stats)
172 {
173         stats->maxpacket = 256;
174 }
175 
176 /*
177  * http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Iterative_methods_for_reciprocal_square_roots
178  * new_invsqrt = (invsqrt / 2) * (3 - count * invsqrt^2)
179  *
180  * Here, invsqrt is a fixed point number (< 1.0), 32bit mantissa, aka Q0.32
181  */
182 static void codel_Newton_step(struct codel_vars *vars)
183 {
184         u32 invsqrt = ((u32)vars->rec_inv_sqrt) << REC_INV_SQRT_SHIFT;
185         u32 invsqrt2 = ((u64)invsqrt * invsqrt) >> 32;
186         u64 val = (3LL << 32) - ((u64)vars->count * invsqrt2);
187 
188         val >>= 2; /* avoid overflow in following multiply */
189         val = (val * invsqrt) >> (32 - 2 + 1);
190 
191         vars->rec_inv_sqrt = val >> REC_INV_SQRT_SHIFT;
192 }
193 
194 /*
195  * CoDel control_law is t + interval/sqrt(count)
196  * We maintain in rec_inv_sqrt the reciprocal value of sqrt(count) to avoid
197  * both sqrt() and divide operation.
198  */
199 static codel_time_t codel_control_law(codel_time_t t,
200                                       codel_time_t interval,
201                                       u32 rec_inv_sqrt)
202 {
203         return t + reciprocal_divide(interval, rec_inv_sqrt << REC_INV_SQRT_SHIFT);
204 }
205 
206 
207 static bool codel_should_drop(const struct sk_buff *skb,
208                               struct Qdisc *sch,
209                               struct codel_vars *vars,
210                               struct codel_params *params,
211                               struct codel_stats *stats,
212                               codel_time_t now)
213 {
214         bool ok_to_drop;
215 
216         if (!skb) {
217                 vars->first_above_time = 0;
218                 return false;
219         }
220 
221         vars->ldelay = now - codel_get_enqueue_time(skb);
222         sch->qstats.backlog -= qdisc_pkt_len(skb);
223 
224         if (unlikely(qdisc_pkt_len(skb) > stats->maxpacket))
225                 stats->maxpacket = qdisc_pkt_len(skb);
226 
227         if (codel_time_before(vars->ldelay, params->target) ||
228             sch->qstats.backlog <= stats->maxpacket) {
229                 /* went below - stay below for at least interval */
230                 vars->first_above_time = 0;
231                 return false;
232         }
233         ok_to_drop = false;
234         if (vars->first_above_time == 0) {
235                 /* just went above from below. If we stay above
236                  * for at least interval we'll say it's ok to drop
237                  */
238                 vars->first_above_time = now + params->interval;
239         } else if (codel_time_after(now, vars->first_above_time)) {
240                 ok_to_drop = true;
241         }
242         return ok_to_drop;
243 }
244 
245 typedef struct sk_buff * (*codel_skb_dequeue_t)(struct codel_vars *vars,
246                                                 struct Qdisc *sch);
247 
248 static struct sk_buff *codel_dequeue(struct Qdisc *sch,
249                                      struct codel_params *params,
250                                      struct codel_vars *vars,
251                                      struct codel_stats *stats,
252                                      codel_skb_dequeue_t dequeue_func)
253 {
254         struct sk_buff *skb = dequeue_func(vars, sch);
255         codel_time_t now;
256         bool drop;
257 
258         if (!skb) {
259                 vars->dropping = false;
260                 return skb;
261         }
262         now = codel_get_time();
263         drop = codel_should_drop(skb, sch, vars, params, stats, now);
264         if (vars->dropping) {
265                 if (!drop) {
266                         /* sojourn time below target - leave dropping state */
267                         vars->dropping = false;
268                 } else if (codel_time_after_eq(now, vars->drop_next)) {
269                         /* It's time for the next drop. Drop the current
270                          * packet and dequeue the next. The dequeue might
271                          * take us out of dropping state.
272                          * If not, schedule the next drop.
273                          * A large backlog might result in drop rates so high
274                          * that the next drop should happen now,
275                          * hence the while loop.
276                          */
277                         while (vars->dropping &&
278                                codel_time_after_eq(now, vars->drop_next)) {
279                                 vars->count++; /* dont care of possible wrap
280                                                 * since there is no more divide
281                                                 */
282                                 codel_Newton_step(vars);
283                                 if (params->ecn && INET_ECN_set_ce(skb)) {
284                                         stats->ecn_mark++;
285                                         vars->drop_next =
286                                                 codel_control_law(vars->drop_next,
287                                                                   params->interval,
288                                                                   vars->rec_inv_sqrt);
289                                         goto end;
290                                 }
291                                 qdisc_drop(skb, sch);
292                                 stats->drop_count++;
293                                 skb = dequeue_func(vars, sch);
294                                 if (!codel_should_drop(skb, sch,
295                                                        vars, params, stats, now)) {
296                                         /* leave dropping state */
297                                         vars->dropping = false;
298                                 } else {
299                                         /* and schedule the next drop */
300                                         vars->drop_next =
301                                                 codel_control_law(vars->drop_next,
302                                                                   params->interval,
303                                                                   vars->rec_inv_sqrt);
304                                 }
305                         }
306                 }
307         } else if (drop) {
308                 u32 delta;
309 
310                 if (params->ecn && INET_ECN_set_ce(skb)) {
311                         stats->ecn_mark++;
312                 } else {
313                         qdisc_drop(skb, sch);
314                         stats->drop_count++;
315 
316                         skb = dequeue_func(vars, sch);
317                         drop = codel_should_drop(skb, sch, vars, params,
318                                                  stats, now);
319                 }
320                 vars->dropping = true;
321                 /* if min went above target close to when we last went below it
322                  * assume that the drop rate that controlled the queue on the
323                  * last cycle is a good starting point to control it now.
324                  */
325                 delta = vars->count - vars->lastcount;
326                 if (delta > 1 &&
327                     codel_time_before(now - vars->drop_next,
328                                       16 * params->interval)) {
329                         vars->count = delta;
330                         /* we dont care if rec_inv_sqrt approximation
331                          * is not very precise :
332                          * Next Newton steps will correct it quadratically.
333                          */
334                         codel_Newton_step(vars);
335                 } else {
336                         vars->count = 1;
337                         vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
338                 }
339                 vars->lastcount = vars->count;
340                 vars->drop_next = codel_control_law(now, params->interval,
341                                                     vars->rec_inv_sqrt);
342         }
343 end:
344         return skb;
345 }
346 #endif
347 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp