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.
39 struct red_sched_data {
40 u32 limit; /* HARD maximal queue length */
42 struct timer_list adapt_timer;
43 struct red_parms parms;
45 struct red_stats stats;
49 static inline int red_use_ecn(struct red_sched_data *q)
51 return q->flags & TC_RED_ECN;
54 static inline int red_use_harddrop(struct red_sched_data *q)
56 return q->flags & TC_RED_HARDDROP;
59 static int red_enqueue(struct sk_buff *skb, struct Qdisc *sch)
61 struct red_sched_data *q = qdisc_priv(sch);
62 struct Qdisc *child = q->qdisc;
65 q->vars.qavg = red_calc_qavg(&q->parms,
67 child->qstats.backlog);
69 if (red_is_idling(&q->vars))
70 red_end_of_idle_period(&q->vars);
72 switch (red_action(&q->parms, &q->vars, q->vars.qavg)) {
77 qdisc_qstats_overlimit(sch);
78 if (!red_use_ecn(q) || !INET_ECN_set_ce(skb)) {
87 qdisc_qstats_overlimit(sch);
88 if (red_use_harddrop(q) || !red_use_ecn(q) ||
89 !INET_ECN_set_ce(skb)) {
90 q->stats.forced_drop++;
94 q->stats.forced_mark++;
98 ret = qdisc_enqueue(skb, child);
99 if (likely(ret == NET_XMIT_SUCCESS)) {
100 qdisc_qstats_backlog_inc(sch, skb);
102 } else if (net_xmit_drop_count(ret)) {
104 qdisc_qstats_drop(sch);
109 qdisc_drop(skb, sch);
113 static struct sk_buff *red_dequeue(struct Qdisc *sch)
116 struct red_sched_data *q = qdisc_priv(sch);
117 struct Qdisc *child = q->qdisc;
119 skb = child->dequeue(child);
121 qdisc_bstats_update(sch, skb);
122 qdisc_qstats_backlog_dec(sch, skb);
125 if (!red_is_idling(&q->vars))
126 red_start_of_idle_period(&q->vars);
131 static struct sk_buff *red_peek(struct Qdisc *sch)
133 struct red_sched_data *q = qdisc_priv(sch);
134 struct Qdisc *child = q->qdisc;
136 return child->ops->peek(child);
139 static unsigned int red_drop(struct Qdisc *sch)
141 struct red_sched_data *q = qdisc_priv(sch);
142 struct Qdisc *child = q->qdisc;
145 if (child->ops->drop && (len = child->ops->drop(child)) > 0) {
147 qdisc_qstats_drop(sch);
148 sch->qstats.backlog -= len;
153 if (!red_is_idling(&q->vars))
154 red_start_of_idle_period(&q->vars);
159 static void red_reset(struct Qdisc *sch)
161 struct red_sched_data *q = qdisc_priv(sch);
163 qdisc_reset(q->qdisc);
164 sch->qstats.backlog = 0;
166 red_restart(&q->vars);
169 static void red_destroy(struct Qdisc *sch)
171 struct red_sched_data *q = qdisc_priv(sch);
173 del_timer_sync(&q->adapt_timer);
174 qdisc_destroy(q->qdisc);
177 static const struct nla_policy red_policy[TCA_RED_MAX + 1] = {
178 [TCA_RED_PARMS] = { .len = sizeof(struct tc_red_qopt) },
179 [TCA_RED_STAB] = { .len = RED_STAB_SIZE },
180 [TCA_RED_MAX_P] = { .type = NLA_U32 },
183 static int red_change(struct Qdisc *sch, struct nlattr *opt)
185 struct red_sched_data *q = qdisc_priv(sch);
186 struct nlattr *tb[TCA_RED_MAX + 1];
187 struct tc_red_qopt *ctl;
188 struct Qdisc *child = NULL;
196 err = nla_parse_nested(tb, TCA_RED_MAX, opt, red_policy);
200 if (tb[TCA_RED_PARMS] == NULL ||
201 tb[TCA_RED_STAB] == NULL)
204 max_P = tb[TCA_RED_MAX_P] ? nla_get_u32(tb[TCA_RED_MAX_P]) : 0;
206 ctl = nla_data(tb[TCA_RED_PARMS]);
207 stab = nla_data(tb[TCA_RED_STAB]);
208 if (!red_check_params(ctl->qth_min, ctl->qth_max, ctl->Wlog,
209 ctl->Scell_log, stab))
212 if (ctl->limit > 0) {
213 child = fifo_create_dflt(sch, &bfifo_qdisc_ops, ctl->limit);
215 return PTR_ERR(child);
219 q->flags = ctl->flags;
220 q->limit = ctl->limit;
222 qdisc_tree_reduce_backlog(q->qdisc, q->qdisc->q.qlen,
223 q->qdisc->qstats.backlog);
224 qdisc_destroy(q->qdisc);
228 red_set_parms(&q->parms,
229 ctl->qth_min, ctl->qth_max, ctl->Wlog,
230 ctl->Plog, ctl->Scell_log,
233 red_set_vars(&q->vars);
235 del_timer(&q->adapt_timer);
236 if (ctl->flags & TC_RED_ADAPTATIVE)
237 mod_timer(&q->adapt_timer, jiffies + HZ/2);
239 if (!q->qdisc->q.qlen)
240 red_start_of_idle_period(&q->vars);
242 sch_tree_unlock(sch);
246 static inline void red_adaptative_timer(unsigned long arg)
248 struct Qdisc *sch = (struct Qdisc *)arg;
249 struct red_sched_data *q = qdisc_priv(sch);
250 spinlock_t *root_lock = qdisc_lock(qdisc_root_sleeping(sch));
252 spin_lock(root_lock);
253 red_adaptative_algo(&q->parms, &q->vars);
254 mod_timer(&q->adapt_timer, jiffies + HZ/2);
255 spin_unlock(root_lock);
258 static int red_init(struct Qdisc *sch, struct nlattr *opt)
260 struct red_sched_data *q = qdisc_priv(sch);
262 q->qdisc = &noop_qdisc;
263 setup_timer(&q->adapt_timer, red_adaptative_timer, (unsigned long)sch);
264 return red_change(sch, opt);
267 static int red_dump(struct Qdisc *sch, struct sk_buff *skb)
269 struct red_sched_data *q = qdisc_priv(sch);
270 struct nlattr *opts = NULL;
271 struct tc_red_qopt opt = {
274 .qth_min = q->parms.qth_min >> q->parms.Wlog,
275 .qth_max = q->parms.qth_max >> q->parms.Wlog,
276 .Wlog = q->parms.Wlog,
277 .Plog = q->parms.Plog,
278 .Scell_log = q->parms.Scell_log,
281 sch->qstats.backlog = q->qdisc->qstats.backlog;
282 opts = nla_nest_start(skb, TCA_OPTIONS);
284 goto nla_put_failure;
285 if (nla_put(skb, TCA_RED_PARMS, sizeof(opt), &opt) ||
286 nla_put_u32(skb, TCA_RED_MAX_P, q->parms.max_P))
287 goto nla_put_failure;
288 return nla_nest_end(skb, opts);
291 nla_nest_cancel(skb, opts);
295 static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
297 struct red_sched_data *q = qdisc_priv(sch);
298 struct tc_red_xstats st = {
299 .early = q->stats.prob_drop + q->stats.forced_drop,
300 .pdrop = q->stats.pdrop,
301 .other = q->stats.other,
302 .marked = q->stats.prob_mark + q->stats.forced_mark,
305 return gnet_stats_copy_app(d, &st, sizeof(st));
308 static int red_dump_class(struct Qdisc *sch, unsigned long cl,
309 struct sk_buff *skb, struct tcmsg *tcm)
311 struct red_sched_data *q = qdisc_priv(sch);
313 tcm->tcm_handle |= TC_H_MIN(1);
314 tcm->tcm_info = q->qdisc->handle;
318 static int red_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
321 struct red_sched_data *q = qdisc_priv(sch);
326 *old = qdisc_replace(sch, new, &q->qdisc);
330 static struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg)
332 struct red_sched_data *q = qdisc_priv(sch);
336 static unsigned long red_get(struct Qdisc *sch, u32 classid)
341 static void red_put(struct Qdisc *sch, unsigned long arg)
345 static void red_walk(struct Qdisc *sch, struct qdisc_walker *walker)
348 if (walker->count >= walker->skip)
349 if (walker->fn(sch, 1, walker) < 0) {
357 static const struct Qdisc_class_ops red_class_ops = {
363 .dump = red_dump_class,
366 static struct Qdisc_ops red_qdisc_ops __read_mostly = {
368 .priv_size = sizeof(struct red_sched_data),
369 .cl_ops = &red_class_ops,
370 .enqueue = red_enqueue,
371 .dequeue = red_dequeue,
376 .destroy = red_destroy,
377 .change = red_change,
379 .dump_stats = red_dump_stats,
380 .owner = THIS_MODULE,
383 static int __init red_module_init(void)
385 return register_qdisc(&red_qdisc_ops);
388 static void __exit red_module_exit(void)
390 unregister_qdisc(&red_qdisc_ops);
393 module_init(red_module_init)
394 module_exit(red_module_exit)
396 MODULE_LICENSE("GPL");