blob: 2bdf241f63154df3996bf0c5ec3460cf1fae25c7 [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++;
Jarek Poplawski378a2f02008-08-04 22:31:03 -0700100 } else if (net_xmit_drop_count(ret)) {
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800101 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 struct sk_buff * red_dequeue(struct Qdisc* sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700112{
113 struct sk_buff *skb;
114 struct red_sched_data *q = qdisc_priv(sch);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800115 struct Qdisc *child = q->qdisc;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700116
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800117 skb = child->dequeue(child);
118 if (skb)
119 sch->q.qlen--;
120 else if (!red_is_idling(&q->parms))
Thomas Graf9e178ff2005-11-05 21:14:06 +0100121 red_start_of_idle_period(&q->parms);
122
123 return skb;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700124}
125
Jarek Poplawski8e3af972008-10-31 00:45:55 -0700126static struct sk_buff * red_peek(struct Qdisc* sch)
127{
128 struct red_sched_data *q = qdisc_priv(sch);
129 struct Qdisc *child = q->qdisc;
130
131 return child->ops->peek(child);
132}
133
Linus Torvalds1da177e2005-04-16 15:20:36 -0700134static unsigned int red_drop(struct Qdisc* sch)
135{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700136 struct red_sched_data *q = qdisc_priv(sch);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800137 struct Qdisc *child = q->qdisc;
138 unsigned int len;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700139
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800140 if (child->ops->drop && (len = child->ops->drop(child)) > 0) {
Thomas Graf6b31b282005-11-05 21:14:05 +0100141 q->stats.other++;
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800142 sch->qstats.drops++;
143 sch->q.qlen--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700144 return len;
145 }
Thomas Graf6b31b282005-11-05 21:14:05 +0100146
Thomas Graf6a1b63d2005-11-05 21:14:07 +0100147 if (!red_is_idling(&q->parms))
148 red_start_of_idle_period(&q->parms);
149
Linus Torvalds1da177e2005-04-16 15:20:36 -0700150 return 0;
151}
152
153static void red_reset(struct Qdisc* sch)
154{
155 struct red_sched_data *q = qdisc_priv(sch);
156
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800157 qdisc_reset(q->qdisc);
158 sch->q.qlen = 0;
Thomas Graf6b31b282005-11-05 21:14:05 +0100159 red_restart(&q->parms);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700160}
161
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800162static void red_destroy(struct Qdisc *sch)
163{
164 struct red_sched_data *q = qdisc_priv(sch);
165 qdisc_destroy(q->qdisc);
166}
167
Patrick McHardy27a34212008-01-23 20:35:39 -0800168static const struct nla_policy red_policy[TCA_RED_MAX + 1] = {
169 [TCA_RED_PARMS] = { .len = sizeof(struct tc_red_qopt) },
170 [TCA_RED_STAB] = { .len = RED_STAB_SIZE },
171};
172
Patrick McHardy1e904742008-01-22 22:11:17 -0800173static int red_change(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700174{
175 struct red_sched_data *q = qdisc_priv(sch);
Patrick McHardy1e904742008-01-22 22:11:17 -0800176 struct nlattr *tb[TCA_RED_MAX + 1];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700177 struct tc_red_qopt *ctl;
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800178 struct Qdisc *child = NULL;
Patrick McHardycee63722008-01-23 20:33:32 -0800179 int err;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700180
Patrick McHardycee63722008-01-23 20:33:32 -0800181 if (opt == NULL)
Thomas Grafdba051f2005-11-05 21:14:08 +0100182 return -EINVAL;
183
Patrick McHardy27a34212008-01-23 20:35:39 -0800184 err = nla_parse_nested(tb, TCA_RED_MAX, opt, red_policy);
Patrick McHardycee63722008-01-23 20:33:32 -0800185 if (err < 0)
186 return err;
187
Patrick McHardy1e904742008-01-22 22:11:17 -0800188 if (tb[TCA_RED_PARMS] == NULL ||
Patrick McHardy27a34212008-01-23 20:35:39 -0800189 tb[TCA_RED_STAB] == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700190 return -EINVAL;
191
Patrick McHardy1e904742008-01-22 22:11:17 -0800192 ctl = nla_data(tb[TCA_RED_PARMS]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700193
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800194 if (ctl->limit > 0) {
Patrick McHardyfb0305c2008-07-05 23:40:21 -0700195 child = fifo_create_dflt(sch, &bfifo_qdisc_ops, ctl->limit);
196 if (IS_ERR(child))
197 return PTR_ERR(child);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800198 }
199
Linus Torvalds1da177e2005-04-16 15:20:36 -0700200 sch_tree_lock(sch);
201 q->flags = ctl->flags;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700202 q->limit = ctl->limit;
Patrick McHardy5e50da02006-11-29 17:36:20 -0800203 if (child) {
204 qdisc_tree_decrease_qlen(q->qdisc, q->qdisc->q.qlen);
Patrick McHardyb94c8af2008-11-20 04:11:36 -0800205 qdisc_destroy(q->qdisc);
206 q->qdisc = child;
Patrick McHardy5e50da02006-11-29 17:36:20 -0800207 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700208
Thomas Graf6b31b282005-11-05 21:14:05 +0100209 red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog,
210 ctl->Plog, ctl->Scell_log,
Patrick McHardy1e904742008-01-22 22:11:17 -0800211 nla_data(tb[TCA_RED_STAB]));
Thomas Graf6b31b282005-11-05 21:14:05 +0100212
David S. Millerb03efcf2005-07-08 14:57:23 -0700213 if (skb_queue_empty(&sch->q))
Thomas Graf6b31b282005-11-05 21:14:05 +0100214 red_end_of_idle_period(&q->parms);
Thomas Grafdba051f2005-11-05 21:14:08 +0100215
Linus Torvalds1da177e2005-04-16 15:20:36 -0700216 sch_tree_unlock(sch);
217 return 0;
218}
219
Patrick McHardy1e904742008-01-22 22:11:17 -0800220static int red_init(struct Qdisc* sch, struct nlattr *opt)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700221{
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800222 struct red_sched_data *q = qdisc_priv(sch);
223
224 q->qdisc = &noop_qdisc;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700225 return red_change(sch, opt);
226}
227
228static int red_dump(struct Qdisc *sch, struct sk_buff *skb)
229{
230 struct red_sched_data *q = qdisc_priv(sch);
Patrick McHardy1e904742008-01-22 22:11:17 -0800231 struct nlattr *opts = NULL;
Thomas Graf6b31b282005-11-05 21:14:05 +0100232 struct tc_red_qopt opt = {
233 .limit = q->limit,
234 .flags = q->flags,
235 .qth_min = q->parms.qth_min >> q->parms.Wlog,
236 .qth_max = q->parms.qth_max >> q->parms.Wlog,
237 .Wlog = q->parms.Wlog,
238 .Plog = q->parms.Plog,
239 .Scell_log = q->parms.Scell_log,
240 };
Linus Torvalds1da177e2005-04-16 15:20:36 -0700241
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
271 if (cl != 1)
272 return -ENOENT;
273 tcm->tcm_handle |= TC_H_MIN(1);
274 tcm->tcm_info = q->qdisc->handle;
275 return 0;
276}
277
278static int red_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
279 struct Qdisc **old)
280{
281 struct red_sched_data *q = qdisc_priv(sch);
282
283 if (new == NULL)
284 new = &noop_qdisc;
285
286 sch_tree_lock(sch);
Patrick McHardyb94c8af2008-11-20 04:11:36 -0800287 *old = q->qdisc;
288 q->qdisc = new;
Patrick McHardy5e50da02006-11-29 17:36:20 -0800289 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800290 qdisc_reset(*old);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800291 sch_tree_unlock(sch);
292 return 0;
293}
294
295static struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg)
296{
297 struct red_sched_data *q = qdisc_priv(sch);
298 return q->qdisc;
299}
300
301static unsigned long red_get(struct Qdisc *sch, u32 classid)
302{
303 return 1;
304}
305
306static void red_put(struct Qdisc *sch, unsigned long arg)
307{
308 return;
309}
310
311static int red_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
Patrick McHardy1e904742008-01-22 22:11:17 -0800312 struct nlattr **tca, unsigned long *arg)
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800313{
314 return -ENOSYS;
315}
316
317static int red_delete(struct Qdisc *sch, unsigned long cl)
318{
319 return -ENOSYS;
320}
321
322static void red_walk(struct Qdisc *sch, struct qdisc_walker *walker)
323{
324 if (!walker->stop) {
325 if (walker->count >= walker->skip)
326 if (walker->fn(sch, 1, walker) < 0) {
327 walker->stop = 1;
328 return;
329 }
330 walker->count++;
331 }
332}
333
334static struct tcf_proto **red_find_tcf(struct Qdisc *sch, unsigned long cl)
335{
336 return NULL;
337}
338
Eric Dumazet20fea082007-11-14 01:44:41 -0800339static const struct Qdisc_class_ops red_class_ops = {
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800340 .graft = red_graft,
341 .leaf = red_leaf,
342 .get = red_get,
343 .put = red_put,
344 .change = red_change_class,
345 .delete = red_delete,
346 .walk = red_walk,
347 .tcf_chain = red_find_tcf,
348 .dump = red_dump_class,
349};
350
Eric Dumazet20fea082007-11-14 01:44:41 -0800351static struct Qdisc_ops red_qdisc_ops __read_mostly = {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700352 .id = "red",
353 .priv_size = sizeof(struct red_sched_data),
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800354 .cl_ops = &red_class_ops,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700355 .enqueue = red_enqueue,
356 .dequeue = red_dequeue,
Jarek Poplawski8e3af972008-10-31 00:45:55 -0700357 .peek = red_peek,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700358 .drop = red_drop,
359 .init = red_init,
360 .reset = red_reset,
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800361 .destroy = red_destroy,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700362 .change = red_change,
363 .dump = red_dump,
364 .dump_stats = red_dump_stats,
365 .owner = THIS_MODULE,
366};
367
368static int __init red_module_init(void)
369{
370 return register_qdisc(&red_qdisc_ops);
371}
Thomas Grafdba051f2005-11-05 21:14:08 +0100372
373static void __exit red_module_exit(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700374{
375 unregister_qdisc(&red_qdisc_ops);
376}
Thomas Grafdba051f2005-11-05 21:14:08 +0100377
Linus Torvalds1da177e2005-04-16 15:20:36 -0700378module_init(red_module_init)
379module_exit(red_module_exit)
Thomas Grafdba051f2005-11-05 21:14:08 +0100380
Linus Torvalds1da177e2005-04-16 15:20:36 -0700381MODULE_LICENSE("GPL");