blob: 00db53eb8159ecadc156fe1eab669cf179d4008d [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/netdevice.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070021#include <linux/skbuff.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070022#include <net/pkt_sched.h>
23#include <net/inet_ecn.h>
Thomas Graf6b31b282005-11-05 21:14:05 +010024#include <net/red.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070025
26
Thomas Graf6b31b282005-11-05 21:14:05 +010027/* Parameters, settable by user:
Linus Torvalds1da177e2005-04-16 15:20:36 -070028 -----------------------------
29
30 limit - bytes (must be > qth_max + burst)
31
32 Hard limit on queue length, should be chosen >qth_max
33 to allow packet bursts. This parameter does not
34 affect the algorithms behaviour and can be chosen
35 arbitrarily high (well, less than ram size)
36 Really, this limit will never be reached
37 if RED works correctly.
Linus Torvalds1da177e2005-04-16 15:20:36 -070038 */
39
40struct red_sched_data
41{
Thomas Graf6b31b282005-11-05 21:14:05 +010042 u32 limit; /* HARD maximal queue length */
43 unsigned char flags;
44 struct red_parms parms;
45 struct red_stats stats;
Patrick McHardyf38c39d2006-03-20 19:20:44 -080046 struct Qdisc *qdisc;
Linus Torvalds1da177e2005-04-16 15:20:36 -070047};
48
Thomas Graf6b31b282005-11-05 21:14:05 +010049static inline int red_use_ecn(struct red_sched_data *q)
Linus Torvalds1da177e2005-04-16 15:20:36 -070050{
Thomas Graf6b31b282005-11-05 21:14:05 +010051 return q->flags & TC_RED_ECN;
Linus Torvalds1da177e2005-04-16 15:20:36 -070052}
53
Thomas Grafbdc450a2005-11-05 21:14:28 +010054static inline int red_use_harddrop(struct red_sched_data *q)
55{
56 return q->flags & TC_RED_HARDDROP;
57}
58
Thomas Grafdba051f2005-11-05 21:14:08 +010059static int red_enqueue(struct sk_buff *skb, struct Qdisc* sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -070060{
61 struct red_sched_data *q = qdisc_priv(sch);
Patrick McHardyf38c39d2006-03-20 19:20:44 -080062 struct Qdisc *child = q->qdisc;
63 int ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -070064
Patrick McHardyf38c39d2006-03-20 19:20:44 -080065 q->parms.qavg = red_calc_qavg(&q->parms, child->qstats.backlog);
Linus Torvalds1da177e2005-04-16 15:20:36 -070066
Thomas Graf6b31b282005-11-05 21:14:05 +010067 if (red_is_idling(&q->parms))
68 red_end_of_idle_period(&q->parms);
Linus Torvalds1da177e2005-04-16 15:20:36 -070069
Thomas Graf6b31b282005-11-05 21:14:05 +010070 switch (red_action(&q->parms, q->parms.qavg)) {
71 case RED_DONT_MARK:
72 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -070073
Thomas Graf6b31b282005-11-05 21:14:05 +010074 case RED_PROB_MARK:
75 sch->qstats.overlimits++;
76 if (!red_use_ecn(q) || !INET_ECN_set_ce(skb)) {
77 q->stats.prob_drop++;
78 goto congestion_drop;
79 }
Linus Torvalds1da177e2005-04-16 15:20:36 -070080
Thomas Graf6b31b282005-11-05 21:14:05 +010081 q->stats.prob_mark++;
82 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -070083
Thomas Graf6b31b282005-11-05 21:14:05 +010084 case RED_HARD_MARK:
85 sch->qstats.overlimits++;
Thomas Grafbdc450a2005-11-05 21:14:28 +010086 if (red_use_harddrop(q) || !red_use_ecn(q) ||
87 !INET_ECN_set_ce(skb)) {
Thomas Graf6b31b282005-11-05 21:14:05 +010088 q->stats.forced_drop++;
89 goto congestion_drop;
90 }
Linus Torvalds1da177e2005-04-16 15:20:36 -070091
Thomas Graf6b31b282005-11-05 21:14:05 +010092 q->stats.forced_mark++;
93 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -070094 }
95
Patrick McHardyf38c39d2006-03-20 19:20:44 -080096 ret = child->enqueue(skb, child);
97 if (likely(ret == NET_XMIT_SUCCESS)) {
98 sch->bstats.bytes += skb->len;
99 sch->bstats.packets++;
100 sch->q.qlen++;
101 } else {
102 q->stats.pdrop++;
103 sch->qstats.drops++;
104 }
105 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700106
Thomas Graf6b31b282005-11-05 21:14:05 +0100107congestion_drop:
Thomas Graf9e178ff2005-11-05 21:14:06 +0100108 qdisc_drop(skb, sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700109 return NET_XMIT_CN;
110}
111
Thomas Grafdba051f2005-11-05 21:14:08 +0100112static int red_requeue(struct sk_buff *skb, struct Qdisc* sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700113{
114 struct red_sched_data *q = qdisc_priv(sch);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800115 struct Qdisc *child = q->qdisc;
116 int ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700117
Thomas Graf6b31b282005-11-05 21:14:05 +0100118 if (red_is_idling(&q->parms))
119 red_end_of_idle_period(&q->parms);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700120
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800121 ret = child->ops->requeue(skb, child);
122 if (likely(ret == NET_XMIT_SUCCESS)) {
123 sch->qstats.requeues++;
124 sch->q.qlen++;
125 }
126 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700127}
128
Thomas Grafdba051f2005-11-05 21:14:08 +0100129static struct sk_buff * red_dequeue(struct Qdisc* sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700130{
131 struct sk_buff *skb;
132 struct red_sched_data *q = qdisc_priv(sch);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800133 struct Qdisc *child = q->qdisc;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700134
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800135 skb = child->dequeue(child);
136 if (skb)
137 sch->q.qlen--;
138 else if (!red_is_idling(&q->parms))
Thomas Graf9e178ff2005-11-05 21:14:06 +0100139 red_start_of_idle_period(&q->parms);
140
141 return skb;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700142}
143
144static unsigned int red_drop(struct Qdisc* sch)
145{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700146 struct red_sched_data *q = qdisc_priv(sch);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800147 struct Qdisc *child = q->qdisc;
148 unsigned int len;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700149
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800150 if (child->ops->drop && (len = child->ops->drop(child)) > 0) {
Thomas Graf6b31b282005-11-05 21:14:05 +0100151 q->stats.other++;
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800152 sch->qstats.drops++;
153 sch->q.qlen--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700154 return len;
155 }
Thomas Graf6b31b282005-11-05 21:14:05 +0100156
Thomas Graf6a1b63d2005-11-05 21:14:07 +0100157 if (!red_is_idling(&q->parms))
158 red_start_of_idle_period(&q->parms);
159
Linus Torvalds1da177e2005-04-16 15:20:36 -0700160 return 0;
161}
162
163static void red_reset(struct Qdisc* sch)
164{
165 struct red_sched_data *q = qdisc_priv(sch);
166
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800167 qdisc_reset(q->qdisc);
168 sch->q.qlen = 0;
Thomas Graf6b31b282005-11-05 21:14:05 +0100169 red_restart(&q->parms);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700170}
171
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800172static void red_destroy(struct Qdisc *sch)
173{
174 struct red_sched_data *q = qdisc_priv(sch);
175 qdisc_destroy(q->qdisc);
176}
177
Patrick McHardy9f9afec2006-11-29 17:35:18 -0800178static struct Qdisc *red_create_dflt(struct Qdisc *sch, u32 limit)
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800179{
Patrick McHardy9f9afec2006-11-29 17:35:18 -0800180 struct Qdisc *q;
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800181 struct rtattr *rta;
182 int ret;
183
Patrick McHardy9f9afec2006-11-29 17:35:18 -0800184 q = qdisc_create_dflt(sch->dev, &bfifo_qdisc_ops,
185 TC_H_MAKE(sch->handle, 1));
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800186 if (q) {
187 rta = kmalloc(RTA_LENGTH(sizeof(struct tc_fifo_qopt)),
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900188 GFP_KERNEL);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800189 if (rta) {
190 rta->rta_type = RTM_NEWQDISC;
191 rta->rta_len = RTA_LENGTH(sizeof(struct tc_fifo_qopt));
192 ((struct tc_fifo_qopt *)RTA_DATA(rta))->limit = limit;
193
194 ret = q->ops->change(q, rta);
195 kfree(rta);
196
197 if (ret == 0)
198 return q;
199 }
200 qdisc_destroy(q);
201 }
202 return NULL;
203}
204
Linus Torvalds1da177e2005-04-16 15:20:36 -0700205static int red_change(struct Qdisc *sch, struct rtattr *opt)
206{
207 struct red_sched_data *q = qdisc_priv(sch);
Thomas Grafdba051f2005-11-05 21:14:08 +0100208 struct rtattr *tb[TCA_RED_MAX];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700209 struct tc_red_qopt *ctl;
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800210 struct Qdisc *child = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700211
Thomas Grafdba051f2005-11-05 21:14:08 +0100212 if (opt == NULL || rtattr_parse_nested(tb, TCA_RED_MAX, opt))
213 return -EINVAL;
214
215 if (tb[TCA_RED_PARMS-1] == NULL ||
Linus Torvalds1da177e2005-04-16 15:20:36 -0700216 RTA_PAYLOAD(tb[TCA_RED_PARMS-1]) < sizeof(*ctl) ||
Thomas Grafdba051f2005-11-05 21:14:08 +0100217 tb[TCA_RED_STAB-1] == NULL ||
218 RTA_PAYLOAD(tb[TCA_RED_STAB-1]) < RED_STAB_SIZE)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700219 return -EINVAL;
220
221 ctl = RTA_DATA(tb[TCA_RED_PARMS-1]);
222
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800223 if (ctl->limit > 0) {
Patrick McHardy9f9afec2006-11-29 17:35:18 -0800224 child = red_create_dflt(sch, ctl->limit);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800225 if (child == NULL)
226 return -ENOMEM;
227 }
228
Linus Torvalds1da177e2005-04-16 15:20:36 -0700229 sch_tree_lock(sch);
230 q->flags = ctl->flags;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700231 q->limit = ctl->limit;
Patrick McHardy5e50da02006-11-29 17:36:20 -0800232 if (child) {
233 qdisc_tree_decrease_qlen(q->qdisc, q->qdisc->q.qlen);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800234 qdisc_destroy(xchg(&q->qdisc, child));
Patrick McHardy5e50da02006-11-29 17:36:20 -0800235 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700236
Thomas Graf6b31b282005-11-05 21:14:05 +0100237 red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog,
238 ctl->Plog, ctl->Scell_log,
239 RTA_DATA(tb[TCA_RED_STAB-1]));
240
David S. Millerb03efcf2005-07-08 14:57:23 -0700241 if (skb_queue_empty(&sch->q))
Thomas Graf6b31b282005-11-05 21:14:05 +0100242 red_end_of_idle_period(&q->parms);
Thomas Grafdba051f2005-11-05 21:14:08 +0100243
Linus Torvalds1da177e2005-04-16 15:20:36 -0700244 sch_tree_unlock(sch);
245 return 0;
246}
247
248static int red_init(struct Qdisc* sch, struct rtattr *opt)
249{
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800250 struct red_sched_data *q = qdisc_priv(sch);
251
252 q->qdisc = &noop_qdisc;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700253 return red_change(sch, opt);
254}
255
256static int red_dump(struct Qdisc *sch, struct sk_buff *skb)
257{
258 struct red_sched_data *q = qdisc_priv(sch);
Thomas Grafdba051f2005-11-05 21:14:08 +0100259 struct rtattr *opts = NULL;
Thomas Graf6b31b282005-11-05 21:14:05 +0100260 struct tc_red_qopt opt = {
261 .limit = q->limit,
262 .flags = q->flags,
263 .qth_min = q->parms.qth_min >> q->parms.Wlog,
264 .qth_max = q->parms.qth_max >> q->parms.Wlog,
265 .Wlog = q->parms.Wlog,
266 .Plog = q->parms.Plog,
267 .Scell_log = q->parms.Scell_log,
268 };
Linus Torvalds1da177e2005-04-16 15:20:36 -0700269
Thomas Grafdba051f2005-11-05 21:14:08 +0100270 opts = RTA_NEST(skb, TCA_OPTIONS);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700271 RTA_PUT(skb, TCA_RED_PARMS, sizeof(opt), &opt);
Thomas Grafdba051f2005-11-05 21:14:08 +0100272 return RTA_NEST_END(skb, opts);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700273
274rtattr_failure:
Thomas Grafdba051f2005-11-05 21:14:08 +0100275 return RTA_NEST_CANCEL(skb, opts);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700276}
277
278static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
279{
280 struct red_sched_data *q = qdisc_priv(sch);
Thomas Graf6b31b282005-11-05 21:14:05 +0100281 struct tc_red_xstats st = {
282 .early = q->stats.prob_drop + q->stats.forced_drop,
283 .pdrop = q->stats.pdrop,
284 .other = q->stats.other,
285 .marked = q->stats.prob_mark + q->stats.forced_mark,
286 };
Linus Torvalds1da177e2005-04-16 15:20:36 -0700287
Thomas Graf6b31b282005-11-05 21:14:05 +0100288 return gnet_stats_copy_app(d, &st, sizeof(st));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700289}
290
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800291static int red_dump_class(struct Qdisc *sch, unsigned long cl,
292 struct sk_buff *skb, struct tcmsg *tcm)
293{
294 struct red_sched_data *q = qdisc_priv(sch);
295
296 if (cl != 1)
297 return -ENOENT;
298 tcm->tcm_handle |= TC_H_MIN(1);
299 tcm->tcm_info = q->qdisc->handle;
300 return 0;
301}
302
303static int red_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
304 struct Qdisc **old)
305{
306 struct red_sched_data *q = qdisc_priv(sch);
307
308 if (new == NULL)
309 new = &noop_qdisc;
310
311 sch_tree_lock(sch);
312 *old = xchg(&q->qdisc, new);
Patrick McHardy5e50da02006-11-29 17:36:20 -0800313 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800314 qdisc_reset(*old);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800315 sch_tree_unlock(sch);
316 return 0;
317}
318
319static struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg)
320{
321 struct red_sched_data *q = qdisc_priv(sch);
322 return q->qdisc;
323}
324
325static unsigned long red_get(struct Qdisc *sch, u32 classid)
326{
327 return 1;
328}
329
330static void red_put(struct Qdisc *sch, unsigned long arg)
331{
332 return;
333}
334
335static int red_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
336 struct rtattr **tca, unsigned long *arg)
337{
338 return -ENOSYS;
339}
340
341static int red_delete(struct Qdisc *sch, unsigned long cl)
342{
343 return -ENOSYS;
344}
345
346static void red_walk(struct Qdisc *sch, struct qdisc_walker *walker)
347{
348 if (!walker->stop) {
349 if (walker->count >= walker->skip)
350 if (walker->fn(sch, 1, walker) < 0) {
351 walker->stop = 1;
352 return;
353 }
354 walker->count++;
355 }
356}
357
358static struct tcf_proto **red_find_tcf(struct Qdisc *sch, unsigned long cl)
359{
360 return NULL;
361}
362
363static struct Qdisc_class_ops red_class_ops = {
364 .graft = red_graft,
365 .leaf = red_leaf,
366 .get = red_get,
367 .put = red_put,
368 .change = red_change_class,
369 .delete = red_delete,
370 .walk = red_walk,
371 .tcf_chain = red_find_tcf,
372 .dump = red_dump_class,
373};
374
Linus Torvalds1da177e2005-04-16 15:20:36 -0700375static struct Qdisc_ops red_qdisc_ops = {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700376 .id = "red",
377 .priv_size = sizeof(struct red_sched_data),
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800378 .cl_ops = &red_class_ops,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700379 .enqueue = red_enqueue,
380 .dequeue = red_dequeue,
381 .requeue = red_requeue,
382 .drop = red_drop,
383 .init = red_init,
384 .reset = red_reset,
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800385 .destroy = red_destroy,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700386 .change = red_change,
387 .dump = red_dump,
388 .dump_stats = red_dump_stats,
389 .owner = THIS_MODULE,
390};
391
392static int __init red_module_init(void)
393{
394 return register_qdisc(&red_qdisc_ops);
395}
Thomas Grafdba051f2005-11-05 21:14:08 +0100396
397static void __exit red_module_exit(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700398{
399 unregister_qdisc(&red_qdisc_ops);
400}
Thomas Grafdba051f2005-11-05 21:14:08 +0100401
Linus Torvalds1da177e2005-04-16 15:20:36 -0700402module_init(red_module_init)
403module_exit(red_module_exit)
Thomas Grafdba051f2005-11-05 21:14:08 +0100404
Linus Torvalds1da177e2005-04-16 15:20:36 -0700405MODULE_LICENSE("GPL");