blob: 3f2d1d7f3bbd2dae4fd43d9d86241797d3087f09 [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
39struct red_sched_data
40{
Thomas Graf6b31b282005-11-05 21:14:05 +010041 u32 limit; /* HARD maximal queue length */
42 unsigned char flags;
43 struct red_parms parms;
44 struct red_stats stats;
Patrick McHardyf38c39d2006-03-20 19:20:44 -080045 struct Qdisc *qdisc;
Linus Torvalds1da177e2005-04-16 15:20:36 -070046};
47
Thomas Graf6b31b282005-11-05 21:14:05 +010048static inline int red_use_ecn(struct red_sched_data *q)
Linus Torvalds1da177e2005-04-16 15:20:36 -070049{
Thomas Graf6b31b282005-11-05 21:14:05 +010050 return q->flags & TC_RED_ECN;
Linus Torvalds1da177e2005-04-16 15:20:36 -070051}
52
Thomas Grafbdc450a2005-11-05 21:14:28 +010053static inline int red_use_harddrop(struct red_sched_data *q)
54{
55 return q->flags & TC_RED_HARDDROP;
56}
57
Thomas Grafdba051f2005-11-05 21:14:08 +010058static int red_enqueue(struct sk_buff *skb, struct Qdisc* sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -070059{
60 struct red_sched_data *q = qdisc_priv(sch);
Patrick McHardyf38c39d2006-03-20 19:20:44 -080061 struct Qdisc *child = q->qdisc;
62 int ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -070063
Patrick McHardyf38c39d2006-03-20 19:20:44 -080064 q->parms.qavg = red_calc_qavg(&q->parms, child->qstats.backlog);
Linus Torvalds1da177e2005-04-16 15:20:36 -070065
Thomas Graf6b31b282005-11-05 21:14:05 +010066 if (red_is_idling(&q->parms))
67 red_end_of_idle_period(&q->parms);
Linus Torvalds1da177e2005-04-16 15:20:36 -070068
Thomas Graf6b31b282005-11-05 21:14:05 +010069 switch (red_action(&q->parms, q->parms.qavg)) {
70 case RED_DONT_MARK:
71 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -070072
Thomas Graf6b31b282005-11-05 21:14:05 +010073 case RED_PROB_MARK:
74 sch->qstats.overlimits++;
75 if (!red_use_ecn(q) || !INET_ECN_set_ce(skb)) {
76 q->stats.prob_drop++;
77 goto congestion_drop;
78 }
Linus Torvalds1da177e2005-04-16 15:20:36 -070079
Thomas Graf6b31b282005-11-05 21:14:05 +010080 q->stats.prob_mark++;
81 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -070082
Thomas Graf6b31b282005-11-05 21:14:05 +010083 case RED_HARD_MARK:
84 sch->qstats.overlimits++;
Thomas Grafbdc450a2005-11-05 21:14:28 +010085 if (red_use_harddrop(q) || !red_use_ecn(q) ||
86 !INET_ECN_set_ce(skb)) {
Thomas Graf6b31b282005-11-05 21:14:05 +010087 q->stats.forced_drop++;
88 goto congestion_drop;
89 }
Linus Torvalds1da177e2005-04-16 15:20:36 -070090
Thomas Graf6b31b282005-11-05 21:14:05 +010091 q->stats.forced_mark++;
92 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -070093 }
94
Jussi Kivilinna5f861732008-07-20 00:08:04 -070095 ret = qdisc_enqueue(skb, child);
Patrick McHardyf38c39d2006-03-20 19:20:44 -080096 if (likely(ret == NET_XMIT_SUCCESS)) {
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -070097 sch->bstats.bytes += qdisc_pkt_len(skb);
Patrick McHardyf38c39d2006-03-20 19:20:44 -080098 sch->bstats.packets++;
99 sch->q.qlen++;
100 } else {
101 q->stats.pdrop++;
102 sch->qstats.drops++;
103 }
104 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700105
Thomas Graf6b31b282005-11-05 21:14:05 +0100106congestion_drop:
Thomas Graf9e178ff2005-11-05 21:14:06 +0100107 qdisc_drop(skb, sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700108 return NET_XMIT_CN;
109}
110
Thomas Grafdba051f2005-11-05 21:14:08 +0100111static int red_requeue(struct sk_buff *skb, struct Qdisc* sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700112{
113 struct red_sched_data *q = qdisc_priv(sch);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800114 struct Qdisc *child = q->qdisc;
115 int ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700116
Thomas Graf6b31b282005-11-05 21:14:05 +0100117 if (red_is_idling(&q->parms))
118 red_end_of_idle_period(&q->parms);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700119
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800120 ret = child->ops->requeue(skb, child);
121 if (likely(ret == NET_XMIT_SUCCESS)) {
122 sch->qstats.requeues++;
123 sch->q.qlen++;
124 }
125 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700126}
127
Thomas Grafdba051f2005-11-05 21:14:08 +0100128static struct sk_buff * red_dequeue(struct Qdisc* sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700129{
130 struct sk_buff *skb;
131 struct red_sched_data *q = qdisc_priv(sch);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800132 struct Qdisc *child = q->qdisc;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700133
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800134 skb = child->dequeue(child);
135 if (skb)
136 sch->q.qlen--;
137 else if (!red_is_idling(&q->parms))
Thomas Graf9e178ff2005-11-05 21:14:06 +0100138 red_start_of_idle_period(&q->parms);
139
140 return skb;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700141}
142
143static unsigned int red_drop(struct Qdisc* sch)
144{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700145 struct red_sched_data *q = qdisc_priv(sch);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800146 struct Qdisc *child = q->qdisc;
147 unsigned int len;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700148
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800149 if (child->ops->drop && (len = child->ops->drop(child)) > 0) {
Thomas Graf6b31b282005-11-05 21:14:05 +0100150 q->stats.other++;
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800151 sch->qstats.drops++;
152 sch->q.qlen--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700153 return len;
154 }
Thomas Graf6b31b282005-11-05 21:14:05 +0100155
Thomas Graf6a1b63d2005-11-05 21:14:07 +0100156 if (!red_is_idling(&q->parms))
157 red_start_of_idle_period(&q->parms);
158
Linus Torvalds1da177e2005-04-16 15:20:36 -0700159 return 0;
160}
161
162static void red_reset(struct Qdisc* sch)
163{
164 struct red_sched_data *q = qdisc_priv(sch);
165
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800166 qdisc_reset(q->qdisc);
167 sch->q.qlen = 0;
Thomas Graf6b31b282005-11-05 21:14:05 +0100168 red_restart(&q->parms);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700169}
170
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800171static void red_destroy(struct Qdisc *sch)
172{
173 struct red_sched_data *q = qdisc_priv(sch);
174 qdisc_destroy(q->qdisc);
175}
176
Patrick McHardy27a34212008-01-23 20:35:39 -0800177static const struct nla_policy red_policy[TCA_RED_MAX + 1] = {
178 [TCA_RED_PARMS] = { .len = sizeof(struct tc_red_qopt) },
179 [TCA_RED_STAB] = { .len = RED_STAB_SIZE },
180};
181
Patrick McHardy1e904742008-01-22 22:11:17 -0800182static int red_change(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700183{
184 struct red_sched_data *q = qdisc_priv(sch);
Patrick McHardy1e904742008-01-22 22:11:17 -0800185 struct nlattr *tb[TCA_RED_MAX + 1];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700186 struct tc_red_qopt *ctl;
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800187 struct Qdisc *child = NULL;
Patrick McHardycee63722008-01-23 20:33:32 -0800188 int err;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700189
Patrick McHardycee63722008-01-23 20:33:32 -0800190 if (opt == NULL)
Thomas Grafdba051f2005-11-05 21:14:08 +0100191 return -EINVAL;
192
Patrick McHardy27a34212008-01-23 20:35:39 -0800193 err = nla_parse_nested(tb, TCA_RED_MAX, opt, red_policy);
Patrick McHardycee63722008-01-23 20:33:32 -0800194 if (err < 0)
195 return err;
196
Patrick McHardy1e904742008-01-22 22:11:17 -0800197 if (tb[TCA_RED_PARMS] == NULL ||
Patrick McHardy27a34212008-01-23 20:35:39 -0800198 tb[TCA_RED_STAB] == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700199 return -EINVAL;
200
Patrick McHardy1e904742008-01-22 22:11:17 -0800201 ctl = nla_data(tb[TCA_RED_PARMS]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700202
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800203 if (ctl->limit > 0) {
Patrick McHardyfb0305c2008-07-05 23:40:21 -0700204 child = fifo_create_dflt(sch, &bfifo_qdisc_ops, ctl->limit);
205 if (IS_ERR(child))
206 return PTR_ERR(child);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800207 }
208
Linus Torvalds1da177e2005-04-16 15:20:36 -0700209 sch_tree_lock(sch);
210 q->flags = ctl->flags;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700211 q->limit = ctl->limit;
Patrick McHardy5e50da02006-11-29 17:36:20 -0800212 if (child) {
213 qdisc_tree_decrease_qlen(q->qdisc, q->qdisc->q.qlen);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800214 qdisc_destroy(xchg(&q->qdisc, child));
Patrick McHardy5e50da02006-11-29 17:36:20 -0800215 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700216
Thomas Graf6b31b282005-11-05 21:14:05 +0100217 red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog,
218 ctl->Plog, ctl->Scell_log,
Patrick McHardy1e904742008-01-22 22:11:17 -0800219 nla_data(tb[TCA_RED_STAB]));
Thomas Graf6b31b282005-11-05 21:14:05 +0100220
David S. Millerb03efcf2005-07-08 14:57:23 -0700221 if (skb_queue_empty(&sch->q))
Thomas Graf6b31b282005-11-05 21:14:05 +0100222 red_end_of_idle_period(&q->parms);
Thomas Grafdba051f2005-11-05 21:14:08 +0100223
Linus Torvalds1da177e2005-04-16 15:20:36 -0700224 sch_tree_unlock(sch);
225 return 0;
226}
227
Patrick McHardy1e904742008-01-22 22:11:17 -0800228static int red_init(struct Qdisc* sch, struct nlattr *opt)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700229{
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800230 struct red_sched_data *q = qdisc_priv(sch);
231
232 q->qdisc = &noop_qdisc;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700233 return red_change(sch, opt);
234}
235
236static int red_dump(struct Qdisc *sch, struct sk_buff *skb)
237{
238 struct red_sched_data *q = qdisc_priv(sch);
Patrick McHardy1e904742008-01-22 22:11:17 -0800239 struct nlattr *opts = NULL;
Thomas Graf6b31b282005-11-05 21:14:05 +0100240 struct tc_red_qopt opt = {
241 .limit = q->limit,
242 .flags = q->flags,
243 .qth_min = q->parms.qth_min >> q->parms.Wlog,
244 .qth_max = q->parms.qth_max >> q->parms.Wlog,
245 .Wlog = q->parms.Wlog,
246 .Plog = q->parms.Plog,
247 .Scell_log = q->parms.Scell_log,
248 };
Linus Torvalds1da177e2005-04-16 15:20:36 -0700249
Patrick McHardy1e904742008-01-22 22:11:17 -0800250 opts = nla_nest_start(skb, TCA_OPTIONS);
251 if (opts == NULL)
252 goto nla_put_failure;
253 NLA_PUT(skb, TCA_RED_PARMS, sizeof(opt), &opt);
254 return nla_nest_end(skb, opts);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700255
Patrick McHardy1e904742008-01-22 22:11:17 -0800256nla_put_failure:
Thomas Grafbc3ed282008-06-03 16:36:54 -0700257 nla_nest_cancel(skb, opts);
258 return -EMSGSIZE;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700259}
260
261static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
262{
263 struct red_sched_data *q = qdisc_priv(sch);
Thomas Graf6b31b282005-11-05 21:14:05 +0100264 struct tc_red_xstats st = {
265 .early = q->stats.prob_drop + q->stats.forced_drop,
266 .pdrop = q->stats.pdrop,
267 .other = q->stats.other,
268 .marked = q->stats.prob_mark + q->stats.forced_mark,
269 };
Linus Torvalds1da177e2005-04-16 15:20:36 -0700270
Thomas Graf6b31b282005-11-05 21:14:05 +0100271 return gnet_stats_copy_app(d, &st, sizeof(st));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700272}
273
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800274static int red_dump_class(struct Qdisc *sch, unsigned long cl,
275 struct sk_buff *skb, struct tcmsg *tcm)
276{
277 struct red_sched_data *q = qdisc_priv(sch);
278
279 if (cl != 1)
280 return -ENOENT;
281 tcm->tcm_handle |= TC_H_MIN(1);
282 tcm->tcm_info = q->qdisc->handle;
283 return 0;
284}
285
286static int red_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
287 struct Qdisc **old)
288{
289 struct red_sched_data *q = qdisc_priv(sch);
290
291 if (new == NULL)
292 new = &noop_qdisc;
293
294 sch_tree_lock(sch);
295 *old = xchg(&q->qdisc, new);
Patrick McHardy5e50da02006-11-29 17:36:20 -0800296 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800297 qdisc_reset(*old);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800298 sch_tree_unlock(sch);
299 return 0;
300}
301
302static struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg)
303{
304 struct red_sched_data *q = qdisc_priv(sch);
305 return q->qdisc;
306}
307
308static unsigned long red_get(struct Qdisc *sch, u32 classid)
309{
310 return 1;
311}
312
313static void red_put(struct Qdisc *sch, unsigned long arg)
314{
315 return;
316}
317
318static int red_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
Patrick McHardy1e904742008-01-22 22:11:17 -0800319 struct nlattr **tca, unsigned long *arg)
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800320{
321 return -ENOSYS;
322}
323
324static int red_delete(struct Qdisc *sch, unsigned long cl)
325{
326 return -ENOSYS;
327}
328
329static void red_walk(struct Qdisc *sch, struct qdisc_walker *walker)
330{
331 if (!walker->stop) {
332 if (walker->count >= walker->skip)
333 if (walker->fn(sch, 1, walker) < 0) {
334 walker->stop = 1;
335 return;
336 }
337 walker->count++;
338 }
339}
340
341static struct tcf_proto **red_find_tcf(struct Qdisc *sch, unsigned long cl)
342{
343 return NULL;
344}
345
Eric Dumazet20fea082007-11-14 01:44:41 -0800346static const struct Qdisc_class_ops red_class_ops = {
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800347 .graft = red_graft,
348 .leaf = red_leaf,
349 .get = red_get,
350 .put = red_put,
351 .change = red_change_class,
352 .delete = red_delete,
353 .walk = red_walk,
354 .tcf_chain = red_find_tcf,
355 .dump = red_dump_class,
356};
357
Eric Dumazet20fea082007-11-14 01:44:41 -0800358static struct Qdisc_ops red_qdisc_ops __read_mostly = {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700359 .id = "red",
360 .priv_size = sizeof(struct red_sched_data),
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800361 .cl_ops = &red_class_ops,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700362 .enqueue = red_enqueue,
363 .dequeue = red_dequeue,
364 .requeue = red_requeue,
365 .drop = red_drop,
366 .init = red_init,
367 .reset = red_reset,
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800368 .destroy = red_destroy,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700369 .change = red_change,
370 .dump = red_dump,
371 .dump_stats = red_dump_stats,
372 .owner = THIS_MODULE,
373};
374
375static int __init red_module_init(void)
376{
377 return register_qdisc(&red_qdisc_ops);
378}
Thomas Grafdba051f2005-11-05 21:14:08 +0100379
380static void __exit red_module_exit(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700381{
382 unregister_qdisc(&red_qdisc_ops);
383}
Thomas Grafdba051f2005-11-05 21:14:08 +0100384
Linus Torvalds1da177e2005-04-16 15:20:36 -0700385module_init(red_module_init)
386module_exit(red_module_exit)
Thomas Grafdba051f2005-11-05 21:14:08 +0100387
Linus Torvalds1da177e2005-04-16 15:20:36 -0700388MODULE_LICENSE("GPL");