2 * net/sched/sch_red.c Random Early Detection queue.
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.
9 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
12 * J Hadi Salim 980914: computation fixes
13 * Alexey Makarenko <makar@phoenix.kharkov.ua> 990814: qave on idle link was calculated incorrectly.
14 * J Hadi Salim 980816: ECN support
17 #include <linux/module.h>
18 #include <linux/types.h>
19 #include <linux/kernel.h>
20 #include <linux/skbuff.h>
21 #include <net/pkt_sched.h>
22 #include <net/inet_ecn.h>
26 /* Parameters, settable by user:
27 -----------------------------
29 limit - bytes (must be > qth_max + burst)
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.
41 u32 limit; /* HARD maximal queue length */
43 struct red_parms parms;
44 struct red_stats stats;
48 static inline int red_use_ecn(struct red_sched_data *q)
50 return q->flags & TC_RED_ECN;
53 static inline int red_use_harddrop(struct red_sched_data *q)
55 return q->flags & TC_RED_HARDDROP;
58 static int red_enqueue(struct sk_buff *skb, struct Qdisc* sch)
60 struct red_sched_data *q = qdisc_priv(sch);
61 struct Qdisc *child = q->qdisc;
64 q->parms.qavg = red_calc_qavg(&q->parms, child->qstats.backlog);
66 if (red_is_idling(&q->parms))
67 red_end_of_idle_period(&q->parms);
69 switch (red_action(&q->parms, q->parms.qavg)) {
74 sch->qstats.overlimits++;
75 if (!red_use_ecn(q) || !INET_ECN_set_ce(skb)) {
84 sch->qstats.overlimits++;
85 if (red_use_harddrop(q) || !red_use_ecn(q) ||
86 !INET_ECN_set_ce(skb)) {
87 q->stats.forced_drop++;
91 q->stats.forced_mark++;
95 ret = qdisc_enqueue(skb, child);
96 if (likely(ret == NET_XMIT_SUCCESS)) {
97 sch->bstats.bytes += qdisc_pkt_len(skb);
98 sch->bstats.packets++;
100 } else if (net_xmit_drop_count(ret)) {
107 qdisc_drop(skb, sch);
111 static struct sk_buff * red_dequeue(struct Qdisc* sch)
114 struct red_sched_data *q = qdisc_priv(sch);
115 struct Qdisc *child = q->qdisc;
117 skb = child->dequeue(child);
120 else if (!red_is_idling(&q->parms))
121 red_start_of_idle_period(&q->parms);
126 static struct sk_buff * red_peek(struct Qdisc* sch)
128 struct red_sched_data *q = qdisc_priv(sch);
129 struct Qdisc *child = q->qdisc;
131 return child->ops->peek(child);
134 static unsigned int red_drop(struct Qdisc* sch)
136 struct red_sched_data *q = qdisc_priv(sch);
137 struct Qdisc *child = q->qdisc;
140 if (child->ops->drop && (len = child->ops->drop(child)) > 0) {
147 if (!red_is_idling(&q->parms))
148 red_start_of_idle_period(&q->parms);
153 static void red_reset(struct Qdisc* sch)
155 struct red_sched_data *q = qdisc_priv(sch);
157 qdisc_reset(q->qdisc);
159 red_restart(&q->parms);
162 static void red_destroy(struct Qdisc *sch)
164 struct red_sched_data *q = qdisc_priv(sch);
165 qdisc_destroy(q->qdisc);
168 static 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 },
173 static int red_change(struct Qdisc *sch, struct nlattr *opt)
175 struct red_sched_data *q = qdisc_priv(sch);
176 struct nlattr *tb[TCA_RED_MAX + 1];
177 struct tc_red_qopt *ctl;
178 struct Qdisc *child = NULL;
184 err = nla_parse_nested(tb, TCA_RED_MAX, opt, red_policy);
188 if (tb[TCA_RED_PARMS] == NULL ||
189 tb[TCA_RED_STAB] == NULL)
192 ctl = nla_data(tb[TCA_RED_PARMS]);
194 if (ctl->limit > 0) {
195 child = fifo_create_dflt(sch, &bfifo_qdisc_ops, ctl->limit);
197 return PTR_ERR(child);
201 q->flags = ctl->flags;
202 q->limit = ctl->limit;
204 qdisc_tree_decrease_qlen(q->qdisc, q->qdisc->q.qlen);
205 qdisc_destroy(xchg(&q->qdisc, child));
208 red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog,
209 ctl->Plog, ctl->Scell_log,
210 nla_data(tb[TCA_RED_STAB]));
212 if (skb_queue_empty(&sch->q))
213 red_end_of_idle_period(&q->parms);
215 sch_tree_unlock(sch);
219 static int red_init(struct Qdisc* sch, struct nlattr *opt)
221 struct red_sched_data *q = qdisc_priv(sch);
223 q->qdisc = &noop_qdisc;
224 return red_change(sch, opt);
227 static int red_dump(struct Qdisc *sch, struct sk_buff *skb)
229 struct red_sched_data *q = qdisc_priv(sch);
230 struct nlattr *opts = NULL;
231 struct tc_red_qopt opt = {
234 .qth_min = q->parms.qth_min >> q->parms.Wlog,
235 .qth_max = q->parms.qth_max >> q->parms.Wlog,
236 .Wlog = q->parms.Wlog,
237 .Plog = q->parms.Plog,
238 .Scell_log = q->parms.Scell_log,
241 opts = nla_nest_start(skb, TCA_OPTIONS);
243 goto nla_put_failure;
244 NLA_PUT(skb, TCA_RED_PARMS, sizeof(opt), &opt);
245 return nla_nest_end(skb, opts);
248 nla_nest_cancel(skb, opts);
252 static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
254 struct red_sched_data *q = qdisc_priv(sch);
255 struct tc_red_xstats st = {
256 .early = q->stats.prob_drop + q->stats.forced_drop,
257 .pdrop = q->stats.pdrop,
258 .other = q->stats.other,
259 .marked = q->stats.prob_mark + q->stats.forced_mark,
262 return gnet_stats_copy_app(d, &st, sizeof(st));
265 static int red_dump_class(struct Qdisc *sch, unsigned long cl,
266 struct sk_buff *skb, struct tcmsg *tcm)
268 struct red_sched_data *q = qdisc_priv(sch);
272 tcm->tcm_handle |= TC_H_MIN(1);
273 tcm->tcm_info = q->qdisc->handle;
277 static int red_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
280 struct red_sched_data *q = qdisc_priv(sch);
286 *old = xchg(&q->qdisc, new);
287 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
289 sch_tree_unlock(sch);
293 static struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg)
295 struct red_sched_data *q = qdisc_priv(sch);
299 static unsigned long red_get(struct Qdisc *sch, u32 classid)
304 static void red_put(struct Qdisc *sch, unsigned long arg)
309 static int red_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
310 struct nlattr **tca, unsigned long *arg)
315 static int red_delete(struct Qdisc *sch, unsigned long cl)
320 static void red_walk(struct Qdisc *sch, struct qdisc_walker *walker)
323 if (walker->count >= walker->skip)
324 if (walker->fn(sch, 1, walker) < 0) {
332 static struct tcf_proto **red_find_tcf(struct Qdisc *sch, unsigned long cl)
337 static const struct Qdisc_class_ops red_class_ops = {
342 .change = red_change_class,
343 .delete = red_delete,
345 .tcf_chain = red_find_tcf,
346 .dump = red_dump_class,
349 static struct Qdisc_ops red_qdisc_ops __read_mostly = {
351 .priv_size = sizeof(struct red_sched_data),
352 .cl_ops = &red_class_ops,
353 .enqueue = red_enqueue,
354 .dequeue = red_dequeue,
359 .destroy = red_destroy,
360 .change = red_change,
362 .dump_stats = red_dump_stats,
363 .owner = THIS_MODULE,
366 static int __init red_module_init(void)
368 return register_qdisc(&red_qdisc_ops);
371 static void __exit red_module_exit(void)
373 unregister_qdisc(&red_qdisc_ops);
376 module_init(red_module_init)
377 module_exit(red_module_exit)
379 MODULE_LICENSE("GPL");