include/net/codel.h

   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                               unsigned int *backlog,
 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         *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             *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                                      u32 *backlog)
 254 {
 255         struct sk_buff *skb = dequeue_func(vars, sch);
 256         codel_time_t now;
 257         bool drop;
 258
 259         if (!skb) {
 260                 vars->dropping = false;
 261                 return skb;
 262         }
 263         now = codel_get_time();
 264         drop = codel_should_drop(skb, backlog, vars, params, stats, now);
 265         if (vars->dropping) {
 266                 if (!drop) {
 267                         /* sojourn time below target - leave dropping state */
 268                         vars->dropping = false;
 269                 } else if (codel_time_after_eq(now, vars->drop_next)) {
 270                         /* It's time for the next drop. Drop the current
 271                          * packet and dequeue the next. The dequeue might
 272                          * take us out of dropping state.
 273                          * If not, schedule the next drop.
 274                          * A large backlog might result in drop rates so high
 275                          * that the next drop should happen now,
 276                          * hence the while loop.
 277                          */
 278                         while (vars->dropping &&
 279                                codel_time_after_eq(now, vars->drop_next)) {
 280                                 vars->count++; /* dont care of possible wrap
 281                                                 * since there is no more divide
 282                                                 */
 283                                 codel_Newton_step(vars);
 284                                 if (params->ecn && INET_ECN_set_ce(skb)) {
 285                                         stats->ecn_mark++;
 286                                         vars->drop_next =
 287                                                 codel_control_law(vars->drop_next,
 288                                                                   params->interval,
 289                                                                   vars->rec_inv_sqrt);
 290                                         goto end;
 291                                 }
 292                                 qdisc_drop(skb, sch);
 293                                 stats->drop_count++;
 294                                 skb = dequeue_func(vars, sch);
 295                                 if (!codel_should_drop(skb, backlog,
 296                                                        vars, params, stats, now)) {
 297                                         /* leave dropping state */
 298                                         vars->dropping = false;
 299                                 } else {
 300                                         /* and schedule the next drop */
 301                                         vars->drop_next =
 302                                                 codel_control_law(vars->drop_next,
 303                                                                   params->interval,
 304                                                                   vars->rec_inv_sqrt);
 305                                 }
 306                         }
 307                 }
 308         } else if (drop) {
 309                 if (params->ecn && INET_ECN_set_ce(skb)) {
 310                         stats->ecn_mark++;
 311                 } else {
 312                         qdisc_drop(skb, sch);
 313                         stats->drop_count++;
 314
 315                         skb = dequeue_func(vars, sch);
 316                         drop = codel_should_drop(skb, backlog, vars, params,
 317                                                  stats, now);
 318                 }
 319                 vars->dropping = true;
 320                 /* if min went above target close to when we last went below it
 321                  * assume that the drop rate that controlled the queue on the
 322                  * last cycle is a good starting point to control it now.
 323                  */
 324                 if (codel_time_before(now - vars->drop_next,
 325                                       16 * params->interval)) {
 326                         vars->count = (vars->count - vars->lastcount) | 1;
 327                         /* we dont care if rec_inv_sqrt approximation
 328                          * is not very precise :
 329                          * Next Newton steps will correct it quadratically.
 330                          */
 331                         codel_Newton_step(vars);
 332                 } else {
 333                         vars->count = 1;
 334                         vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
 335                 }
 336                 vars->lastcount = vars->count;
 337                 vars->drop_next = codel_control_law(now, params->interval,
 338                                                     vars->rec_inv_sqrt);
 339         }
 340 end:
 341         return skb;
 342 }
 343 #endif