blob: 6649463da1b68e6e59e6709c7e1d0b527a60ab63 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * net/sched/sch_red.c Random Early Detection queue.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version
7 * 2 of the License, or (at your option) any later version.
8 *
9 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
10 *
11 * Changes:
Thomas Grafdba051f2005-11-05 21:14:08 +010012 * J Hadi Salim 980914: computation fixes
Linus Torvalds1da177e2005-04-16 15:20:36 -070013 * Alexey Makarenko <makar@phoenix.kharkov.ua> 990814: qave on idle link was calculated incorrectly.
Thomas Grafdba051f2005-11-05 21:14:08 +010014 * J Hadi Salim 980816: ECN support
Linus Torvalds1da177e2005-04-16 15:20:36 -070015 */
16
Linus Torvalds1da177e2005-04-16 15:20:36 -070017#include <linux/module.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070018#include <linux/types.h>
19#include <linux/kernel.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070020#include <linux/skbuff.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070021#include <net/pkt_sched.h>
22#include <net/inet_ecn.h>
Thomas Graf6b31b282005-11-05 21:14:05 +010023#include <net/red.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070024
25
Thomas Graf6b31b282005-11-05 21:14:05 +010026/* Parameters, settable by user:
Linus Torvalds1da177e2005-04-16 15:20:36 -070027 -----------------------------
28
29 limit - bytes (must be > qth_max + burst)
30
31 Hard limit on queue length, should be chosen >qth_max
32 to allow packet bursts. This parameter does not
33 affect the algorithms behaviour and can be chosen
34 arbitrarily high (well, less than ram size)
35 Really, this limit will never be reached
36 if RED works correctly.
Linus Torvalds1da177e2005-04-16 15:20:36 -070037 */
38
Eric Dumazetcc7ec452011-01-19 19:26:56 +000039struct red_sched_data {
Thomas Graf6b31b282005-11-05 21:14:05 +010040 u32 limit; /* HARD maximal queue length */
41 unsigned char flags;
42 struct red_parms parms;
43 struct red_stats stats;
Patrick McHardyf38c39d2006-03-20 19:20:44 -080044 struct Qdisc *qdisc;
Linus Torvalds1da177e2005-04-16 15:20:36 -070045};
46
Thomas Graf6b31b282005-11-05 21:14:05 +010047static inline int red_use_ecn(struct red_sched_data *q)
Linus Torvalds1da177e2005-04-16 15:20:36 -070048{
Thomas Graf6b31b282005-11-05 21:14:05 +010049 return q->flags & TC_RED_ECN;
Linus Torvalds1da177e2005-04-16 15:20:36 -070050}
51
Thomas Grafbdc450a2005-11-05 21:14:28 +010052static inline int red_use_harddrop(struct red_sched_data *q)
53{
54 return q->flags & TC_RED_HARDDROP;
55}
56
Eric Dumazetcc7ec452011-01-19 19:26:56 +000057static int red_enqueue(struct sk_buff *skb, struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -070058{
59 struct red_sched_data *q = qdisc_priv(sch);
Patrick McHardyf38c39d2006-03-20 19:20:44 -080060 struct Qdisc *child = q->qdisc;
61 int ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -070062
Patrick McHardyf38c39d2006-03-20 19:20:44 -080063 q->parms.qavg = red_calc_qavg(&q->parms, child->qstats.backlog);
Linus Torvalds1da177e2005-04-16 15:20:36 -070064
Thomas Graf6b31b282005-11-05 21:14:05 +010065 if (red_is_idling(&q->parms))
66 red_end_of_idle_period(&q->parms);
Linus Torvalds1da177e2005-04-16 15:20:36 -070067
Thomas Graf6b31b282005-11-05 21:14:05 +010068 switch (red_action(&q->parms, q->parms.qavg)) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +000069 case RED_DONT_MARK:
70 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -070071
Eric Dumazetcc7ec452011-01-19 19:26:56 +000072 case RED_PROB_MARK:
73 sch->qstats.overlimits++;
74 if (!red_use_ecn(q) || !INET_ECN_set_ce(skb)) {
75 q->stats.prob_drop++;
76 goto congestion_drop;
77 }
Linus Torvalds1da177e2005-04-16 15:20:36 -070078
Eric Dumazetcc7ec452011-01-19 19:26:56 +000079 q->stats.prob_mark++;
80 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -070081
Eric Dumazetcc7ec452011-01-19 19:26:56 +000082 case RED_HARD_MARK:
83 sch->qstats.overlimits++;
84 if (red_use_harddrop(q) || !red_use_ecn(q) ||
85 !INET_ECN_set_ce(skb)) {
86 q->stats.forced_drop++;
87 goto congestion_drop;
88 }
Linus Torvalds1da177e2005-04-16 15:20:36 -070089
Eric Dumazetcc7ec452011-01-19 19:26:56 +000090 q->stats.forced_mark++;
91 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -070092 }
93
Jussi Kivilinna5f861732008-07-20 00:08:04 -070094 ret = qdisc_enqueue(skb, child);
Patrick McHardyf38c39d2006-03-20 19:20:44 -080095 if (likely(ret == NET_XMIT_SUCCESS)) {
Patrick McHardyf38c39d2006-03-20 19:20:44 -080096 sch->q.qlen++;
Jarek Poplawski378a2f02008-08-04 22:31:03 -070097 } else if (net_xmit_drop_count(ret)) {
Patrick McHardyf38c39d2006-03-20 19:20:44 -080098 q->stats.pdrop++;
99 sch->qstats.drops++;
100 }
101 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700102
Thomas Graf6b31b282005-11-05 21:14:05 +0100103congestion_drop:
Thomas Graf9e178ff2005-11-05 21:14:06 +0100104 qdisc_drop(skb, sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700105 return NET_XMIT_CN;
106}
107
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000108static struct sk_buff *red_dequeue(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700109{
110 struct sk_buff *skb;
111 struct red_sched_data *q = qdisc_priv(sch);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800112 struct Qdisc *child = q->qdisc;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700113
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800114 skb = child->dequeue(child);
Eric Dumazet9190b3b2011-01-20 23:31:33 -0800115 if (skb) {
116 qdisc_bstats_update(sch, skb);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800117 sch->q.qlen--;
Eric Dumazet9190b3b2011-01-20 23:31:33 -0800118 } else {
119 if (!red_is_idling(&q->parms))
120 red_start_of_idle_period(&q->parms);
121 }
Thomas Graf9e178ff2005-11-05 21:14:06 +0100122 return skb;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700123}
124
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000125static struct sk_buff *red_peek(struct Qdisc *sch)
Jarek Poplawski8e3af972008-10-31 00:45:55 -0700126{
127 struct red_sched_data *q = qdisc_priv(sch);
128 struct Qdisc *child = q->qdisc;
129
130 return child->ops->peek(child);
131}
132
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000133static unsigned int red_drop(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700134{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700135 struct red_sched_data *q = qdisc_priv(sch);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800136 struct Qdisc *child = q->qdisc;
137 unsigned int len;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700138
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800139 if (child->ops->drop && (len = child->ops->drop(child)) > 0) {
Thomas Graf6b31b282005-11-05 21:14:05 +0100140 q->stats.other++;
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800141 sch->qstats.drops++;
142 sch->q.qlen--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700143 return len;
144 }
Thomas Graf6b31b282005-11-05 21:14:05 +0100145
Thomas Graf6a1b63d2005-11-05 21:14:07 +0100146 if (!red_is_idling(&q->parms))
147 red_start_of_idle_period(&q->parms);
148
Linus Torvalds1da177e2005-04-16 15:20:36 -0700149 return 0;
150}
151
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000152static void red_reset(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700153{
154 struct red_sched_data *q = qdisc_priv(sch);
155
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800156 qdisc_reset(q->qdisc);
157 sch->q.qlen = 0;
Thomas Graf6b31b282005-11-05 21:14:05 +0100158 red_restart(&q->parms);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700159}
160
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800161static void red_destroy(struct Qdisc *sch)
162{
163 struct red_sched_data *q = qdisc_priv(sch);
164 qdisc_destroy(q->qdisc);
165}
166
Patrick McHardy27a34212008-01-23 20:35:39 -0800167static const struct nla_policy red_policy[TCA_RED_MAX + 1] = {
168 [TCA_RED_PARMS] = { .len = sizeof(struct tc_red_qopt) },
169 [TCA_RED_STAB] = { .len = RED_STAB_SIZE },
170};
171
Patrick McHardy1e904742008-01-22 22:11:17 -0800172static int red_change(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700173{
174 struct red_sched_data *q = qdisc_priv(sch);
Patrick McHardy1e904742008-01-22 22:11:17 -0800175 struct nlattr *tb[TCA_RED_MAX + 1];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700176 struct tc_red_qopt *ctl;
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800177 struct Qdisc *child = NULL;
Patrick McHardycee63722008-01-23 20:33:32 -0800178 int err;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700179
Patrick McHardycee63722008-01-23 20:33:32 -0800180 if (opt == NULL)
Thomas Grafdba051f2005-11-05 21:14:08 +0100181 return -EINVAL;
182
Patrick McHardy27a34212008-01-23 20:35:39 -0800183 err = nla_parse_nested(tb, TCA_RED_MAX, opt, red_policy);
Patrick McHardycee63722008-01-23 20:33:32 -0800184 if (err < 0)
185 return err;
186
Patrick McHardy1e904742008-01-22 22:11:17 -0800187 if (tb[TCA_RED_PARMS] == NULL ||
Patrick McHardy27a34212008-01-23 20:35:39 -0800188 tb[TCA_RED_STAB] == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700189 return -EINVAL;
190
Patrick McHardy1e904742008-01-22 22:11:17 -0800191 ctl = nla_data(tb[TCA_RED_PARMS]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700192
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800193 if (ctl->limit > 0) {
Patrick McHardyfb0305c2008-07-05 23:40:21 -0700194 child = fifo_create_dflt(sch, &bfifo_qdisc_ops, ctl->limit);
195 if (IS_ERR(child))
196 return PTR_ERR(child);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800197 }
198
Linus Torvalds1da177e2005-04-16 15:20:36 -0700199 sch_tree_lock(sch);
200 q->flags = ctl->flags;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700201 q->limit = ctl->limit;
Patrick McHardy5e50da02006-11-29 17:36:20 -0800202 if (child) {
203 qdisc_tree_decrease_qlen(q->qdisc, q->qdisc->q.qlen);
Patrick McHardyb94c8af2008-11-20 04:11:36 -0800204 qdisc_destroy(q->qdisc);
205 q->qdisc = child;
Patrick McHardy5e50da02006-11-29 17:36:20 -0800206 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700207
Thomas Graf6b31b282005-11-05 21:14:05 +0100208 red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog,
209 ctl->Plog, ctl->Scell_log,
Patrick McHardy1e904742008-01-22 22:11:17 -0800210 nla_data(tb[TCA_RED_STAB]));
Thomas Graf6b31b282005-11-05 21:14:05 +0100211
David S. Millerb03efcf2005-07-08 14:57:23 -0700212 if (skb_queue_empty(&sch->q))
Thomas Graf6b31b282005-11-05 21:14:05 +0100213 red_end_of_idle_period(&q->parms);
Thomas Grafdba051f2005-11-05 21:14:08 +0100214
Linus Torvalds1da177e2005-04-16 15:20:36 -0700215 sch_tree_unlock(sch);
216 return 0;
217}
218
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000219static int red_init(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700220{
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800221 struct red_sched_data *q = qdisc_priv(sch);
222
223 q->qdisc = &noop_qdisc;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700224 return red_change(sch, opt);
225}
226
227static int red_dump(struct Qdisc *sch, struct sk_buff *skb)
228{
229 struct red_sched_data *q = qdisc_priv(sch);
Patrick McHardy1e904742008-01-22 22:11:17 -0800230 struct nlattr *opts = NULL;
Thomas Graf6b31b282005-11-05 21:14:05 +0100231 struct tc_red_qopt opt = {
232 .limit = q->limit,
233 .flags = q->flags,
234 .qth_min = q->parms.qth_min >> q->parms.Wlog,
235 .qth_max = q->parms.qth_max >> q->parms.Wlog,
236 .Wlog = q->parms.Wlog,
237 .Plog = q->parms.Plog,
238 .Scell_log = q->parms.Scell_log,
239 };
Linus Torvalds1da177e2005-04-16 15:20:36 -0700240
Eric Dumazet0dfb33a2011-01-03 08:11:38 +0000241 sch->qstats.backlog = q->qdisc->qstats.backlog;
Patrick McHardy1e904742008-01-22 22:11:17 -0800242 opts = nla_nest_start(skb, TCA_OPTIONS);
243 if (opts == NULL)
244 goto nla_put_failure;
245 NLA_PUT(skb, TCA_RED_PARMS, sizeof(opt), &opt);
246 return nla_nest_end(skb, opts);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700247
Patrick McHardy1e904742008-01-22 22:11:17 -0800248nla_put_failure:
Thomas Grafbc3ed282008-06-03 16:36:54 -0700249 nla_nest_cancel(skb, opts);
250 return -EMSGSIZE;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700251}
252
253static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
254{
255 struct red_sched_data *q = qdisc_priv(sch);
Thomas Graf6b31b282005-11-05 21:14:05 +0100256 struct tc_red_xstats st = {
257 .early = q->stats.prob_drop + q->stats.forced_drop,
258 .pdrop = q->stats.pdrop,
259 .other = q->stats.other,
260 .marked = q->stats.prob_mark + q->stats.forced_mark,
261 };
Linus Torvalds1da177e2005-04-16 15:20:36 -0700262
Thomas Graf6b31b282005-11-05 21:14:05 +0100263 return gnet_stats_copy_app(d, &st, sizeof(st));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700264}
265
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800266static int red_dump_class(struct Qdisc *sch, unsigned long cl,
267 struct sk_buff *skb, struct tcmsg *tcm)
268{
269 struct red_sched_data *q = qdisc_priv(sch);
270
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800271 tcm->tcm_handle |= TC_H_MIN(1);
272 tcm->tcm_info = q->qdisc->handle;
273 return 0;
274}
275
276static int red_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
277 struct Qdisc **old)
278{
279 struct red_sched_data *q = qdisc_priv(sch);
280
281 if (new == NULL)
282 new = &noop_qdisc;
283
284 sch_tree_lock(sch);
Patrick McHardyb94c8af2008-11-20 04:11:36 -0800285 *old = q->qdisc;
286 q->qdisc = new;
Patrick McHardy5e50da02006-11-29 17:36:20 -0800287 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800288 qdisc_reset(*old);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800289 sch_tree_unlock(sch);
290 return 0;
291}
292
293static struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg)
294{
295 struct red_sched_data *q = qdisc_priv(sch);
296 return q->qdisc;
297}
298
299static unsigned long red_get(struct Qdisc *sch, u32 classid)
300{
301 return 1;
302}
303
304static void red_put(struct Qdisc *sch, unsigned long arg)
305{
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800306}
307
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800308static void red_walk(struct Qdisc *sch, struct qdisc_walker *walker)
309{
310 if (!walker->stop) {
311 if (walker->count >= walker->skip)
312 if (walker->fn(sch, 1, walker) < 0) {
313 walker->stop = 1;
314 return;
315 }
316 walker->count++;
317 }
318}
319
Eric Dumazet20fea082007-11-14 01:44:41 -0800320static const struct Qdisc_class_ops red_class_ops = {
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800321 .graft = red_graft,
322 .leaf = red_leaf,
323 .get = red_get,
324 .put = red_put,
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800325 .walk = red_walk,
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800326 .dump = red_dump_class,
327};
328
Eric Dumazet20fea082007-11-14 01:44:41 -0800329static struct Qdisc_ops red_qdisc_ops __read_mostly = {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700330 .id = "red",
331 .priv_size = sizeof(struct red_sched_data),
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800332 .cl_ops = &red_class_ops,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700333 .enqueue = red_enqueue,
334 .dequeue = red_dequeue,
Jarek Poplawski8e3af972008-10-31 00:45:55 -0700335 .peek = red_peek,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700336 .drop = red_drop,
337 .init = red_init,
338 .reset = red_reset,
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800339 .destroy = red_destroy,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700340 .change = red_change,
341 .dump = red_dump,
342 .dump_stats = red_dump_stats,
343 .owner = THIS_MODULE,
344};
345
346static int __init red_module_init(void)
347{
348 return register_qdisc(&red_qdisc_ops);
349}
Thomas Grafdba051f2005-11-05 21:14:08 +0100350
351static void __exit red_module_exit(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700352{
353 unregister_qdisc(&red_qdisc_ops);
354}
Thomas Grafdba051f2005-11-05 21:14:08 +0100355
Linus Torvalds1da177e2005-04-16 15:20:36 -0700356module_init(red_module_init)
357module_exit(red_module_exit)
Thomas Grafdba051f2005-11-05 21:14:08 +0100358
Linus Torvalds1da177e2005-04-16 15:20:36 -0700359MODULE_LICENSE("GPL");