blob: 9f98dbd32d4c8176d6c940dd098f71fa0c00cb4d [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)) {
Patrick McHardyf38c39d2006-03-20 19:20:44 -080097 sch->q.qlen++;
Jarek Poplawski378a2f02008-08-04 22:31:03 -070098 } else if (net_xmit_drop_count(ret)) {
Patrick McHardyf38c39d2006-03-20 19:20:44 -080099 q->stats.pdrop++;
100 sch->qstats.drops++;
101 }
102 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700103
Thomas Graf6b31b282005-11-05 21:14:05 +0100104congestion_drop:
Thomas Graf9e178ff2005-11-05 21:14:06 +0100105 qdisc_drop(skb, sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700106 return NET_XMIT_CN;
107}
108
Thomas Grafdba051f2005-11-05 21:14:08 +0100109static struct sk_buff * red_dequeue(struct Qdisc* sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700110{
111 struct sk_buff *skb;
112 struct red_sched_data *q = qdisc_priv(sch);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800113 struct Qdisc *child = q->qdisc;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700114
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800115 skb = child->dequeue(child);
Eric Dumazet9190b3b2011-01-20 23:31:33 -0800116 if (skb) {
117 qdisc_bstats_update(sch, skb);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800118 sch->q.qlen--;
Eric Dumazet9190b3b2011-01-20 23:31:33 -0800119 } else {
120 if (!red_is_idling(&q->parms))
121 red_start_of_idle_period(&q->parms);
122 }
Thomas Graf9e178ff2005-11-05 21:14:06 +0100123 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
Eric Dumazet0dfb33a2011-01-03 08:11:38 +0000242 sch->qstats.backlog = q->qdisc->qstats.backlog;
Patrick McHardy1e904742008-01-22 22:11:17 -0800243 opts = nla_nest_start(skb, TCA_OPTIONS);
244 if (opts == NULL)
245 goto nla_put_failure;
246 NLA_PUT(skb, TCA_RED_PARMS, sizeof(opt), &opt);
247 return nla_nest_end(skb, opts);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700248
Patrick McHardy1e904742008-01-22 22:11:17 -0800249nla_put_failure:
Thomas Grafbc3ed282008-06-03 16:36:54 -0700250 nla_nest_cancel(skb, opts);
251 return -EMSGSIZE;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700252}
253
254static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
255{
256 struct red_sched_data *q = qdisc_priv(sch);
Thomas Graf6b31b282005-11-05 21:14:05 +0100257 struct tc_red_xstats st = {
258 .early = q->stats.prob_drop + q->stats.forced_drop,
259 .pdrop = q->stats.pdrop,
260 .other = q->stats.other,
261 .marked = q->stats.prob_mark + q->stats.forced_mark,
262 };
Linus Torvalds1da177e2005-04-16 15:20:36 -0700263
Thomas Graf6b31b282005-11-05 21:14:05 +0100264 return gnet_stats_copy_app(d, &st, sizeof(st));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700265}
266
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800267static int red_dump_class(struct Qdisc *sch, unsigned long cl,
268 struct sk_buff *skb, struct tcmsg *tcm)
269{
270 struct red_sched_data *q = qdisc_priv(sch);
271
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800272 tcm->tcm_handle |= TC_H_MIN(1);
273 tcm->tcm_info = q->qdisc->handle;
274 return 0;
275}
276
277static int red_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
278 struct Qdisc **old)
279{
280 struct red_sched_data *q = qdisc_priv(sch);
281
282 if (new == NULL)
283 new = &noop_qdisc;
284
285 sch_tree_lock(sch);
Patrick McHardyb94c8af2008-11-20 04:11:36 -0800286 *old = q->qdisc;
287 q->qdisc = new;
Patrick McHardy5e50da02006-11-29 17:36:20 -0800288 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800289 qdisc_reset(*old);
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800290 sch_tree_unlock(sch);
291 return 0;
292}
293
294static struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg)
295{
296 struct red_sched_data *q = qdisc_priv(sch);
297 return q->qdisc;
298}
299
300static unsigned long red_get(struct Qdisc *sch, u32 classid)
301{
302 return 1;
303}
304
305static void red_put(struct Qdisc *sch, unsigned long arg)
306{
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800307}
308
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800309static void red_walk(struct Qdisc *sch, struct qdisc_walker *walker)
310{
311 if (!walker->stop) {
312 if (walker->count >= walker->skip)
313 if (walker->fn(sch, 1, walker) < 0) {
314 walker->stop = 1;
315 return;
316 }
317 walker->count++;
318 }
319}
320
Eric Dumazet20fea082007-11-14 01:44:41 -0800321static const struct Qdisc_class_ops red_class_ops = {
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800322 .graft = red_graft,
323 .leaf = red_leaf,
324 .get = red_get,
325 .put = red_put,
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800326 .walk = red_walk,
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800327 .dump = red_dump_class,
328};
329
Eric Dumazet20fea082007-11-14 01:44:41 -0800330static struct Qdisc_ops red_qdisc_ops __read_mostly = {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700331 .id = "red",
332 .priv_size = sizeof(struct red_sched_data),
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800333 .cl_ops = &red_class_ops,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700334 .enqueue = red_enqueue,
335 .dequeue = red_dequeue,
Jarek Poplawski8e3af972008-10-31 00:45:55 -0700336 .peek = red_peek,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700337 .drop = red_drop,
338 .init = red_init,
339 .reset = red_reset,
Patrick McHardyf38c39d2006-03-20 19:20:44 -0800340 .destroy = red_destroy,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700341 .change = red_change,
342 .dump = red_dump,
343 .dump_stats = red_dump_stats,
344 .owner = THIS_MODULE,
345};
346
347static int __init red_module_init(void)
348{
349 return register_qdisc(&red_qdisc_ops);
350}
Thomas Grafdba051f2005-11-05 21:14:08 +0100351
352static void __exit red_module_exit(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700353{
354 unregister_qdisc(&red_qdisc_ops);
355}
Thomas Grafdba051f2005-11-05 21:14:08 +0100356
Linus Torvalds1da177e2005-04-16 15:20:36 -0700357module_init(red_module_init)
358module_exit(red_module_exit)
Thomas Grafdba051f2005-11-05 21:14:08 +0100359
Linus Torvalds1da177e2005-04-16 15:20:36 -0700360MODULE_LICENSE("GPL");