blob: 072cdf442f8eeb8ecad1a7b146c93653b25f6964 [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
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{
306 return;
307}
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");