| 1 | #ifndef __NET_SCHED_CODEL_IMPL_H
|
| 2 | #define __NET_SCHED_CODEL_IMPL_H
|
| 3 |
|
| 4 | |
| 5 | * Codel - The Controlled-Delay Active Queue Management algorithm
|
| 6 | *
|
| 7 | * Copyright (C) 2011-2012 Kathleen Nichols <[email protected]>
|
| 8 | * Copyright (C) 2011-2012 Van Jacobson <[email protected]>
|
| 9 | * Copyright (C) 2012 Michael D. Taht <[email protected]>
|
| 10 | * Copyright (C) 2012,2015 Eric Dumazet <[email protected]>
|
| 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 | |
| 45 | * =========================================
|
| 46 | * Source : Kathleen Nichols and Van Jacobson
|
| 47 | * http://queue.acm.org/detail.cfm?id=2209336
|
| 48 | *
|
| 49 | * Implemented on linux by Dave Taht and Eric Dumazet
|
| 50 |
|
| 51 |
|
| 52 | static void codel_params_init(struct codel_params *params)
|
| 53 | {
|
| 54 | params->interval = MS2TIME(100);
|
| 55 | params->target = MS2TIME(5);
|
| 56 | params->ce_threshold = CODEL_DISABLED_THRESHOLD;
|
| 57 | params->ecn = false;
|
| 58 | }
|
| 59 |
|
| 60 | static void codel_vars_init(struct codel_vars *vars)
|
| 61 | {
|
| 62 | memset(vars, 0, sizeof(*vars));
|
| 63 | }
|
| 64 |
|
| 65 | static void codel_stats_init(struct codel_stats *stats)
|
| 66 | {
|
| 67 | stats->maxpacket = 0;
|
| 68 | }
|
| 69 |
|
| 70 | |
| 71 | * http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Iterative_methods_for_reciprocal_square_roots
|
| 72 | * new_invsqrt = (invsqrt / 2) * (3 - count * invsqrt^2)
|
| 73 | *
|
| 74 | * Here, invsqrt is a fixed point number (< 1.0), 32bit mantissa, aka Q0.32
|
| 75 |
|
| 76 | static void codel_Newton_step(struct codel_vars *vars)
|
| 77 | {
|
| 78 | u32 invsqrt = ((u32)vars->rec_inv_sqrt) << REC_INV_SQRT_SHIFT;
|
| 79 | u32 invsqrt2 = ((u64)invsqrt * invsqrt) >> 32;
|
| 80 | u64 val = (3LL << 32) - ((u64)vars->count * invsqrt2);
|
| 81 |
|
| 82 | val >>= 2;
|
| 83 | val = (val * invsqrt) >> (32 - 2 + 1);
|
| 84 |
|
| 85 | vars->rec_inv_sqrt = val >> REC_INV_SQRT_SHIFT;
|
| 86 | }
|
| 87 |
|
| 88 | |
| 89 | * CoDel control_law is t + interval/sqrt(count)
|
| 90 | * We maintain in rec_inv_sqrt the reciprocal value of sqrt(count) to avoid
|
| 91 | * both sqrt() and divide operation.
|
| 92 |
|
| 93 | static codel_time_t codel_control_law(codel_time_t t,
|
| 94 | codel_time_t interval,
|
| 95 | u32 rec_inv_sqrt)
|
| 96 | {
|
| 97 | return t + reciprocal_scale(interval, rec_inv_sqrt << REC_INV_SQRT_SHIFT);
|
| 98 | }
|
| 99 |
|
| 100 | static bool codel_should_drop(const struct sk_buff *skb,
|
| 101 | void *ctx,
|
| 102 | struct codel_vars *vars,
|
| 103 | struct codel_params *params,
|
| 104 | struct codel_stats *stats,
|
| 105 | codel_skb_len_t skb_len_func,
|
| 106 | codel_skb_time_t skb_time_func,
|
| 107 | u32 *backlog,
|
| 108 | codel_time_t now)
|
| 109 | {
|
| 110 | bool ok_to_drop;
|
| 111 | u32 skb_len;
|
| 112 |
|
| 113 | if (!skb) {
|
| 114 | vars->first_above_time = 0;
|
| 115 | return false;
|
| 116 | }
|
| 117 |
|
| 118 | skb_len = skb_len_func(skb);
|
| 119 | vars->ldelay = now - skb_time_func(skb);
|
| 120 |
|
| 121 | if (unlikely(skb_len > stats->maxpacket))
|
| 122 | stats->maxpacket = skb_len;
|
| 123 |
|
| 124 | if (codel_time_before(vars->ldelay, params->target) ||
|
| 125 | *backlog <= params->mtu) {
|
| 126 |
|
| 127 | vars->first_above_time = 0;
|
| 128 | return false;
|
| 129 | }
|
| 130 | ok_to_drop = false;
|
| 131 | if (vars->first_above_time == 0) {
|
| 132 | |
| 133 | * for at least interval we'll say it's ok to drop
|
| 134 |
|
| 135 | vars->first_above_time = now + params->interval;
|
| 136 | } else if (codel_time_after(now, vars->first_above_time)) {
|
| 137 | ok_to_drop = true;
|
| 138 | }
|
| 139 | return ok_to_drop;
|
| 140 | }
|
| 141 |
|
| 142 | static struct sk_buff *codel_dequeue(void *ctx,
|
| 143 | u32 *backlog,
|
| 144 | struct codel_params *params,
|
| 145 | struct codel_vars *vars,
|
| 146 | struct codel_stats *stats,
|
| 147 | codel_skb_len_t skb_len_func,
|
| 148 | codel_skb_time_t skb_time_func,
|
| 149 | codel_skb_drop_t drop_func,
|
| 150 | codel_skb_dequeue_t dequeue_func)
|
| 151 | {
|
| 152 | struct sk_buff *skb = dequeue_func(vars, ctx);
|
| 153 | codel_time_t now;
|
| 154 | bool drop;
|
| 155 |
|
| 156 | if (!skb) {
|
| 157 | vars->dropping = false;
|
| 158 | return skb;
|
| 159 | }
|
| 160 | now = codel_get_time();
|
| 161 | drop = codel_should_drop(skb, ctx, vars, params, stats,
|
| 162 | skb_len_func, skb_time_func, backlog, now);
|
| 163 | if (vars->dropping) {
|
| 164 | if (!drop) {
|
| 165 |
|
| 166 | vars->dropping = false;
|
| 167 | } else if (codel_time_after_eq(now, vars->drop_next)) {
|
| 168 | |
| 169 | * packet and dequeue the next. The dequeue might
|
| 170 | * take us out of dropping state.
|
| 171 | * If not, schedule the next drop.
|
| 172 | * A large backlog might result in drop rates so high
|
| 173 | * that the next drop should happen now,
|
| 174 | * hence the while loop.
|
| 175 |
|
| 176 | while (vars->dropping &&
|
| 177 | codel_time_after_eq(now, vars->drop_next)) {
|
| 178 | vars->count++; |
| 179 | * since there is no more divide
|
| 180 |
|
| 181 | codel_Newton_step(vars);
|
| 182 | if (params->ecn && INET_ECN_set_ce(skb)) {
|
| 183 | stats->ecn_mark++;
|
| 184 | vars->drop_next =
|
| 185 | codel_control_law(vars->drop_next,
|
| 186 | params->interval,
|
| 187 | vars->rec_inv_sqrt);
|
| 188 | goto end;
|
| 189 | }
|
| 190 | stats->drop_len += skb_len_func(skb);
|
| 191 | drop_func(skb, ctx);
|
| 192 | stats->drop_count++;
|
| 193 | skb = dequeue_func(vars, ctx);
|
| 194 | if (!codel_should_drop(skb, ctx,
|
| 195 | vars, params, stats,
|
| 196 | skb_len_func,
|
| 197 | skb_time_func,
|
| 198 | backlog, now)) {
|
| 199 |
|
| 200 | vars->dropping = false;
|
| 201 | } else {
|
| 202 |
|
| 203 | vars->drop_next =
|
| 204 | codel_control_law(vars->drop_next,
|
| 205 | params->interval,
|
| 206 | vars->rec_inv_sqrt);
|
| 207 | }
|
| 208 | }
|
| 209 | }
|
| 210 | } else if (drop) {
|
| 211 | u32 delta;
|
| 212 |
|
| 213 | if (params->ecn && INET_ECN_set_ce(skb)) {
|
| 214 | stats->ecn_mark++;
|
| 215 | } else {
|
| 216 | stats->drop_len += skb_len_func(skb);
|
| 217 | drop_func(skb, ctx);
|
| 218 | stats->drop_count++;
|
| 219 |
|
| 220 | skb = dequeue_func(vars, ctx);
|
| 221 | drop = codel_should_drop(skb, ctx, vars, params,
|
| 222 | stats, skb_len_func,
|
| 223 | skb_time_func, backlog, now);
|
| 224 | }
|
| 225 | vars->dropping = true;
|
| 226 | |
| 227 | * assume that the drop rate that controlled the queue on the
|
| 228 | * last cycle is a good starting point to control it now.
|
| 229 |
|
| 230 | delta = vars->count - vars->lastcount;
|
| 231 | if (delta > 1 &&
|
| 232 | codel_time_before(now - vars->drop_next,
|
| 233 | 16 * params->interval)) {
|
| 234 | vars->count = delta;
|
| 235 | |
| 236 | * is not very precise :
|
| 237 | * Next Newton steps will correct it quadratically.
|
| 238 |
|
| 239 | codel_Newton_step(vars);
|
| 240 | } else {
|
| 241 | vars->count = 1;
|
| 242 | vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT;
|
| 243 | }
|
| 244 | vars->lastcount = vars->count;
|
| 245 | vars->drop_next = codel_control_law(now, params->interval,
|
| 246 | vars->rec_inv_sqrt);
|
| 247 | }
|
| 248 | end:
|
| 249 | if (skb && codel_time_after(vars->ldelay, params->ce_threshold) &&
|
| 250 | INET_ECN_set_ce(skb))
|
| 251 | stats->ce_mark++;
|
| 252 | return skb;
|
| 253 | }
|
| 254 |
|
| 255 | #endif
|