Eric Dumazet | 76e3cc1 | 2012-05-10 07:51:25 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Codel - The Controlled-Delay Active Queue Management algorithm |
| 3 | * |
| 4 | * Copyright (C) 2011-2012 Kathleen Nichols <nichols@pollere.com> |
| 5 | * Copyright (C) 2011-2012 Van Jacobson <van@pollere.net> |
| 6 | * |
| 7 | * Implemented on linux by : |
| 8 | * Copyright (C) 2012 Michael D. Taht <dave.taht@bufferbloat.net> |
Eric Dumazet | 80ba92f | 2015-05-08 15:05:12 -0700 | [diff] [blame] | 9 | * Copyright (C) 2012,2015 Eric Dumazet <edumazet@google.com> |
Eric Dumazet | 76e3cc1 | 2012-05-10 07:51:25 +0000 | [diff] [blame] | 10 | * |
| 11 | * Redistribution and use in source and binary forms, with or without |
| 12 | * modification, are permitted provided that the following conditions |
| 13 | * are met: |
| 14 | * 1. Redistributions of source code must retain the above copyright |
| 15 | * notice, this list of conditions, and the following disclaimer, |
| 16 | * without modification. |
| 17 | * 2. Redistributions in binary form must reproduce the above copyright |
| 18 | * notice, this list of conditions and the following disclaimer in the |
| 19 | * documentation and/or other materials provided with the distribution. |
| 20 | * 3. The names of the authors may not be used to endorse or promote products |
| 21 | * derived from this software without specific prior written permission. |
| 22 | * |
| 23 | * Alternatively, provided that this notice is retained in full, this |
| 24 | * software may be distributed under the terms of the GNU General |
| 25 | * Public License ("GPL") version 2, in which case the provisions of the |
| 26 | * GPL apply INSTEAD OF those given above. |
| 27 | * |
| 28 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 29 | * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 30 | * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 31 | * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 32 | * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 33 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| 34 | * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 35 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 36 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 37 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| 38 | * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH |
| 39 | * DAMAGE. |
| 40 | * |
| 41 | */ |
| 42 | |
| 43 | #include <linux/module.h> |
| 44 | #include <linux/slab.h> |
| 45 | #include <linux/types.h> |
| 46 | #include <linux/kernel.h> |
| 47 | #include <linux/errno.h> |
| 48 | #include <linux/skbuff.h> |
Geert Uytterhoeven | ce5b4b9 | 2012-05-14 09:47:05 +0000 | [diff] [blame] | 49 | #include <linux/prefetch.h> |
Eric Dumazet | 76e3cc1 | 2012-05-10 07:51:25 +0000 | [diff] [blame] | 50 | #include <net/pkt_sched.h> |
| 51 | #include <net/codel.h> |
| 52 | |
| 53 | |
| 54 | #define DEFAULT_CODEL_LIMIT 1000 |
| 55 | |
| 56 | struct codel_sched_data { |
| 57 | struct codel_params params; |
| 58 | struct codel_vars vars; |
| 59 | struct codel_stats stats; |
| 60 | u32 drop_overlimit; |
| 61 | }; |
| 62 | |
| 63 | /* This is the specific function called from codel_dequeue() |
| 64 | * to dequeue a packet from queue. Note: backlog is handled in |
| 65 | * codel, we dont need to reduce it here. |
| 66 | */ |
Michal Kazior | 79bdc4c | 2016-04-22 14:15:58 +0200 | [diff] [blame^] | 67 | static struct sk_buff *dequeue_func(struct codel_vars *vars, void *ctx) |
Eric Dumazet | 76e3cc1 | 2012-05-10 07:51:25 +0000 | [diff] [blame] | 68 | { |
Michal Kazior | 79bdc4c | 2016-04-22 14:15:58 +0200 | [diff] [blame^] | 69 | struct Qdisc *sch = ctx; |
Eric Dumazet | 76e3cc1 | 2012-05-10 07:51:25 +0000 | [diff] [blame] | 70 | struct sk_buff *skb = __skb_dequeue(&sch->q); |
| 71 | |
Michal Kazior | 79bdc4c | 2016-04-22 14:15:58 +0200 | [diff] [blame^] | 72 | if (skb) |
| 73 | sch->qstats.backlog -= qdisc_pkt_len(skb); |
| 74 | |
Eric Dumazet | 76e3cc1 | 2012-05-10 07:51:25 +0000 | [diff] [blame] | 75 | prefetch(&skb->end); /* we'll need skb_shinfo() */ |
| 76 | return skb; |
| 77 | } |
| 78 | |
Michal Kazior | 79bdc4c | 2016-04-22 14:15:58 +0200 | [diff] [blame^] | 79 | static void drop_func(struct sk_buff *skb, void *ctx) |
| 80 | { |
| 81 | struct Qdisc *sch = ctx; |
| 82 | |
| 83 | qdisc_drop(skb, sch); |
| 84 | } |
| 85 | |
Eric Dumazet | 76e3cc1 | 2012-05-10 07:51:25 +0000 | [diff] [blame] | 86 | static struct sk_buff *codel_qdisc_dequeue(struct Qdisc *sch) |
| 87 | { |
| 88 | struct codel_sched_data *q = qdisc_priv(sch); |
| 89 | struct sk_buff *skb; |
| 90 | |
Michal Kazior | 79bdc4c | 2016-04-22 14:15:58 +0200 | [diff] [blame^] | 91 | skb = codel_dequeue(sch, &sch->qstats.backlog, &q->params, &q->vars, |
| 92 | &q->stats, qdisc_pkt_len, codel_get_enqueue_time, |
| 93 | drop_func, dequeue_func); |
Eric Dumazet | 865ec55 | 2012-05-16 04:39:09 +0000 | [diff] [blame] | 94 | |
WANG Cong | 2ccccf5 | 2016-02-25 14:55:01 -0800 | [diff] [blame] | 95 | /* We cant call qdisc_tree_reduce_backlog() if our qlen is 0, |
Eric Dumazet | 76e3cc1 | 2012-05-10 07:51:25 +0000 | [diff] [blame] | 96 | * or HTB crashes. Defer it for next round. |
| 97 | */ |
| 98 | if (q->stats.drop_count && sch->q.qlen) { |
WANG Cong | 2ccccf5 | 2016-02-25 14:55:01 -0800 | [diff] [blame] | 99 | qdisc_tree_reduce_backlog(sch, q->stats.drop_count, q->stats.drop_len); |
Eric Dumazet | 76e3cc1 | 2012-05-10 07:51:25 +0000 | [diff] [blame] | 100 | q->stats.drop_count = 0; |
WANG Cong | 2ccccf5 | 2016-02-25 14:55:01 -0800 | [diff] [blame] | 101 | q->stats.drop_len = 0; |
Eric Dumazet | 76e3cc1 | 2012-05-10 07:51:25 +0000 | [diff] [blame] | 102 | } |
| 103 | if (skb) |
| 104 | qdisc_bstats_update(sch, skb); |
| 105 | return skb; |
| 106 | } |
| 107 | |
| 108 | static int codel_qdisc_enqueue(struct sk_buff *skb, struct Qdisc *sch) |
| 109 | { |
| 110 | struct codel_sched_data *q; |
| 111 | |
| 112 | if (likely(qdisc_qlen(sch) < sch->limit)) { |
| 113 | codel_set_enqueue_time(skb); |
| 114 | return qdisc_enqueue_tail(skb, sch); |
| 115 | } |
| 116 | q = qdisc_priv(sch); |
| 117 | q->drop_overlimit++; |
| 118 | return qdisc_drop(skb, sch); |
| 119 | } |
| 120 | |
| 121 | static const struct nla_policy codel_policy[TCA_CODEL_MAX + 1] = { |
| 122 | [TCA_CODEL_TARGET] = { .type = NLA_U32 }, |
| 123 | [TCA_CODEL_LIMIT] = { .type = NLA_U32 }, |
| 124 | [TCA_CODEL_INTERVAL] = { .type = NLA_U32 }, |
| 125 | [TCA_CODEL_ECN] = { .type = NLA_U32 }, |
Eric Dumazet | 80ba92f | 2015-05-08 15:05:12 -0700 | [diff] [blame] | 126 | [TCA_CODEL_CE_THRESHOLD]= { .type = NLA_U32 }, |
Eric Dumazet | 76e3cc1 | 2012-05-10 07:51:25 +0000 | [diff] [blame] | 127 | }; |
| 128 | |
| 129 | static int codel_change(struct Qdisc *sch, struct nlattr *opt) |
| 130 | { |
| 131 | struct codel_sched_data *q = qdisc_priv(sch); |
| 132 | struct nlattr *tb[TCA_CODEL_MAX + 1]; |
WANG Cong | 2ccccf5 | 2016-02-25 14:55:01 -0800 | [diff] [blame] | 133 | unsigned int qlen, dropped = 0; |
Eric Dumazet | 76e3cc1 | 2012-05-10 07:51:25 +0000 | [diff] [blame] | 134 | int err; |
| 135 | |
| 136 | if (!opt) |
| 137 | return -EINVAL; |
| 138 | |
| 139 | err = nla_parse_nested(tb, TCA_CODEL_MAX, opt, codel_policy); |
| 140 | if (err < 0) |
| 141 | return err; |
| 142 | |
| 143 | sch_tree_lock(sch); |
| 144 | |
| 145 | if (tb[TCA_CODEL_TARGET]) { |
| 146 | u32 target = nla_get_u32(tb[TCA_CODEL_TARGET]); |
| 147 | |
| 148 | q->params.target = ((u64)target * NSEC_PER_USEC) >> CODEL_SHIFT; |
| 149 | } |
| 150 | |
Eric Dumazet | 80ba92f | 2015-05-08 15:05:12 -0700 | [diff] [blame] | 151 | if (tb[TCA_CODEL_CE_THRESHOLD]) { |
| 152 | u64 val = nla_get_u32(tb[TCA_CODEL_CE_THRESHOLD]); |
| 153 | |
| 154 | q->params.ce_threshold = (val * NSEC_PER_USEC) >> CODEL_SHIFT; |
| 155 | } |
| 156 | |
Eric Dumazet | 76e3cc1 | 2012-05-10 07:51:25 +0000 | [diff] [blame] | 157 | if (tb[TCA_CODEL_INTERVAL]) { |
| 158 | u32 interval = nla_get_u32(tb[TCA_CODEL_INTERVAL]); |
| 159 | |
| 160 | q->params.interval = ((u64)interval * NSEC_PER_USEC) >> CODEL_SHIFT; |
| 161 | } |
| 162 | |
| 163 | if (tb[TCA_CODEL_LIMIT]) |
| 164 | sch->limit = nla_get_u32(tb[TCA_CODEL_LIMIT]); |
| 165 | |
| 166 | if (tb[TCA_CODEL_ECN]) |
| 167 | q->params.ecn = !!nla_get_u32(tb[TCA_CODEL_ECN]); |
| 168 | |
| 169 | qlen = sch->q.qlen; |
| 170 | while (sch->q.qlen > sch->limit) { |
| 171 | struct sk_buff *skb = __skb_dequeue(&sch->q); |
| 172 | |
WANG Cong | 2ccccf5 | 2016-02-25 14:55:01 -0800 | [diff] [blame] | 173 | dropped += qdisc_pkt_len(skb); |
John Fastabend | 25331d6 | 2014-09-28 11:53:29 -0700 | [diff] [blame] | 174 | qdisc_qstats_backlog_dec(sch, skb); |
Eric Dumazet | 76e3cc1 | 2012-05-10 07:51:25 +0000 | [diff] [blame] | 175 | qdisc_drop(skb, sch); |
| 176 | } |
WANG Cong | 2ccccf5 | 2016-02-25 14:55:01 -0800 | [diff] [blame] | 177 | qdisc_tree_reduce_backlog(sch, qlen - sch->q.qlen, dropped); |
Eric Dumazet | 76e3cc1 | 2012-05-10 07:51:25 +0000 | [diff] [blame] | 178 | |
| 179 | sch_tree_unlock(sch); |
| 180 | return 0; |
| 181 | } |
| 182 | |
| 183 | static int codel_init(struct Qdisc *sch, struct nlattr *opt) |
| 184 | { |
| 185 | struct codel_sched_data *q = qdisc_priv(sch); |
| 186 | |
| 187 | sch->limit = DEFAULT_CODEL_LIMIT; |
| 188 | |
Michal Kazior | 79bdc4c | 2016-04-22 14:15:58 +0200 | [diff] [blame^] | 189 | codel_params_init(&q->params); |
Eric Dumazet | 76e3cc1 | 2012-05-10 07:51:25 +0000 | [diff] [blame] | 190 | codel_vars_init(&q->vars); |
| 191 | codel_stats_init(&q->stats); |
Michal Kazior | 79bdc4c | 2016-04-22 14:15:58 +0200 | [diff] [blame^] | 192 | q->params.mtu = psched_mtu(qdisc_dev(sch)); |
Eric Dumazet | 76e3cc1 | 2012-05-10 07:51:25 +0000 | [diff] [blame] | 193 | |
| 194 | if (opt) { |
| 195 | int err = codel_change(sch, opt); |
| 196 | |
| 197 | if (err) |
| 198 | return err; |
| 199 | } |
| 200 | |
| 201 | if (sch->limit >= 1) |
| 202 | sch->flags |= TCQ_F_CAN_BYPASS; |
| 203 | else |
| 204 | sch->flags &= ~TCQ_F_CAN_BYPASS; |
| 205 | |
| 206 | return 0; |
| 207 | } |
| 208 | |
| 209 | static int codel_dump(struct Qdisc *sch, struct sk_buff *skb) |
| 210 | { |
| 211 | struct codel_sched_data *q = qdisc_priv(sch); |
| 212 | struct nlattr *opts; |
| 213 | |
| 214 | opts = nla_nest_start(skb, TCA_OPTIONS); |
| 215 | if (opts == NULL) |
| 216 | goto nla_put_failure; |
| 217 | |
| 218 | if (nla_put_u32(skb, TCA_CODEL_TARGET, |
| 219 | codel_time_to_us(q->params.target)) || |
| 220 | nla_put_u32(skb, TCA_CODEL_LIMIT, |
| 221 | sch->limit) || |
| 222 | nla_put_u32(skb, TCA_CODEL_INTERVAL, |
| 223 | codel_time_to_us(q->params.interval)) || |
| 224 | nla_put_u32(skb, TCA_CODEL_ECN, |
| 225 | q->params.ecn)) |
| 226 | goto nla_put_failure; |
Eric Dumazet | 80ba92f | 2015-05-08 15:05:12 -0700 | [diff] [blame] | 227 | if (q->params.ce_threshold != CODEL_DISABLED_THRESHOLD && |
| 228 | nla_put_u32(skb, TCA_CODEL_CE_THRESHOLD, |
| 229 | codel_time_to_us(q->params.ce_threshold))) |
| 230 | goto nla_put_failure; |
Eric Dumazet | 76e3cc1 | 2012-05-10 07:51:25 +0000 | [diff] [blame] | 231 | return nla_nest_end(skb, opts); |
| 232 | |
| 233 | nla_put_failure: |
| 234 | nla_nest_cancel(skb, opts); |
| 235 | return -1; |
| 236 | } |
| 237 | |
| 238 | static int codel_dump_stats(struct Qdisc *sch, struct gnet_dump *d) |
| 239 | { |
| 240 | const struct codel_sched_data *q = qdisc_priv(sch); |
| 241 | struct tc_codel_xstats st = { |
| 242 | .maxpacket = q->stats.maxpacket, |
| 243 | .count = q->vars.count, |
| 244 | .lastcount = q->vars.lastcount, |
| 245 | .drop_overlimit = q->drop_overlimit, |
| 246 | .ldelay = codel_time_to_us(q->vars.ldelay), |
| 247 | .dropping = q->vars.dropping, |
| 248 | .ecn_mark = q->stats.ecn_mark, |
Eric Dumazet | 80ba92f | 2015-05-08 15:05:12 -0700 | [diff] [blame] | 249 | .ce_mark = q->stats.ce_mark, |
Eric Dumazet | 76e3cc1 | 2012-05-10 07:51:25 +0000 | [diff] [blame] | 250 | }; |
| 251 | |
| 252 | if (q->vars.dropping) { |
| 253 | codel_tdiff_t delta = q->vars.drop_next - codel_get_time(); |
| 254 | |
| 255 | if (delta >= 0) |
| 256 | st.drop_next = codel_time_to_us(delta); |
| 257 | else |
| 258 | st.drop_next = -codel_time_to_us(-delta); |
| 259 | } |
| 260 | |
| 261 | return gnet_stats_copy_app(d, &st, sizeof(st)); |
| 262 | } |
| 263 | |
| 264 | static void codel_reset(struct Qdisc *sch) |
| 265 | { |
| 266 | struct codel_sched_data *q = qdisc_priv(sch); |
| 267 | |
| 268 | qdisc_reset_queue(sch); |
| 269 | codel_vars_init(&q->vars); |
| 270 | } |
| 271 | |
| 272 | static struct Qdisc_ops codel_qdisc_ops __read_mostly = { |
| 273 | .id = "codel", |
| 274 | .priv_size = sizeof(struct codel_sched_data), |
| 275 | |
| 276 | .enqueue = codel_qdisc_enqueue, |
| 277 | .dequeue = codel_qdisc_dequeue, |
| 278 | .peek = qdisc_peek_dequeued, |
| 279 | .init = codel_init, |
| 280 | .reset = codel_reset, |
| 281 | .change = codel_change, |
| 282 | .dump = codel_dump, |
| 283 | .dump_stats = codel_dump_stats, |
| 284 | .owner = THIS_MODULE, |
| 285 | }; |
| 286 | |
| 287 | static int __init codel_module_init(void) |
| 288 | { |
| 289 | return register_qdisc(&codel_qdisc_ops); |
| 290 | } |
| 291 | |
| 292 | static void __exit codel_module_exit(void) |
| 293 | { |
| 294 | unregister_qdisc(&codel_qdisc_ops); |
| 295 | } |
| 296 | |
| 297 | module_init(codel_module_init) |
| 298 | module_exit(codel_module_exit) |
| 299 | |
| 300 | MODULE_DESCRIPTION("Controlled Delay queue discipline"); |
| 301 | MODULE_AUTHOR("Dave Taht"); |
| 302 | MODULE_AUTHOR("Eric Dumazet"); |
| 303 | MODULE_LICENSE("Dual BSD/GPL"); |