sch_red: Adaptative RED AQM
[linux-2.6.git] / net / sched / sch_red.c
1 /*
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:
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
15  */
16
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>
23 #include <net/red.h>
24
25
26 /*      Parameters, settable by user:
27         -----------------------------
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.
37  */
38
39 struct red_sched_data {
40         u32                     limit;          /* HARD maximal queue length */
41         unsigned char           flags;
42         struct timer_list       adapt_timer;
43         struct red_parms        parms;
44         struct red_stats        stats;
45         struct Qdisc            *qdisc;
46 };
47
48 static inline int red_use_ecn(struct red_sched_data *q)
49 {
50         return q->flags & TC_RED_ECN;
51 }
52
53 static inline int red_use_harddrop(struct red_sched_data *q)
54 {
55         return q->flags & TC_RED_HARDDROP;
56 }
57
58 static int red_enqueue(struct sk_buff *skb, struct Qdisc *sch)
59 {
60         struct red_sched_data *q = qdisc_priv(sch);
61         struct Qdisc *child = q->qdisc;
62         int ret;
63
64         q->parms.qavg = red_calc_qavg(&q->parms, child->qstats.backlog);
65
66         if (red_is_idling(&q->parms))
67                 red_end_of_idle_period(&q->parms);
68
69         switch (red_action(&q->parms, q->parms.qavg)) {
70         case RED_DONT_MARK:
71                 break;
72
73         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                 }
79
80                 q->stats.prob_mark++;
81                 break;
82
83         case RED_HARD_MARK:
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++;
88                         goto congestion_drop;
89                 }
90
91                 q->stats.forced_mark++;
92                 break;
93         }
94
95         ret = qdisc_enqueue(skb, child);
96         if (likely(ret == NET_XMIT_SUCCESS)) {
97                 sch->q.qlen++;
98         } else if (net_xmit_drop_count(ret)) {
99                 q->stats.pdrop++;
100                 sch->qstats.drops++;
101         }
102         return ret;
103
104 congestion_drop:
105         qdisc_drop(skb, sch);
106         return NET_XMIT_CN;
107 }
108
109 static struct sk_buff *red_dequeue(struct Qdisc *sch)
110 {
111         struct sk_buff *skb;
112         struct red_sched_data *q = qdisc_priv(sch);
113         struct Qdisc *child = q->qdisc;
114
115         skb = child->dequeue(child);
116         if (skb) {
117                 qdisc_bstats_update(sch, skb);
118                 sch->q.qlen--;
119         } else {
120                 if (!red_is_idling(&q->parms))
121                         red_start_of_idle_period(&q->parms);
122         }
123         return skb;
124 }
125
126 static 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
134 static unsigned int red_drop(struct Qdisc *sch)
135 {
136         struct red_sched_data *q = qdisc_priv(sch);
137         struct Qdisc *child = q->qdisc;
138         unsigned int len;
139
140         if (child->ops->drop && (len = child->ops->drop(child)) > 0) {
141                 q->stats.other++;
142                 sch->qstats.drops++;
143                 sch->q.qlen--;
144                 return len;
145         }
146
147         if (!red_is_idling(&q->parms))
148                 red_start_of_idle_period(&q->parms);
149
150         return 0;
151 }
152
153 static void red_reset(struct Qdisc *sch)
154 {
155         struct red_sched_data *q = qdisc_priv(sch);
156
157         qdisc_reset(q->qdisc);
158         sch->q.qlen = 0;
159         red_restart(&q->parms);
160 }
161
162 static void red_destroy(struct Qdisc *sch)
163 {
164         struct red_sched_data *q = qdisc_priv(sch);
165
166         del_timer_sync(&q->adapt_timer);
167         qdisc_destroy(q->qdisc);
168 }
169
170 static const struct nla_policy red_policy[TCA_RED_MAX + 1] = {
171         [TCA_RED_PARMS] = { .len = sizeof(struct tc_red_qopt) },
172         [TCA_RED_STAB]  = { .len = RED_STAB_SIZE },
173 };
174
175 static int red_change(struct Qdisc *sch, struct nlattr *opt)
176 {
177         struct red_sched_data *q = qdisc_priv(sch);
178         struct nlattr *tb[TCA_RED_MAX + 1];
179         struct tc_red_qopt *ctl;
180         struct Qdisc *child = NULL;
181         int err;
182
183         if (opt == NULL)
184                 return -EINVAL;
185
186         err = nla_parse_nested(tb, TCA_RED_MAX, opt, red_policy);
187         if (err < 0)
188                 return err;
189
190         if (tb[TCA_RED_PARMS] == NULL ||
191             tb[TCA_RED_STAB] == NULL)
192                 return -EINVAL;
193
194         ctl = nla_data(tb[TCA_RED_PARMS]);
195
196         if (ctl->limit > 0) {
197                 child = fifo_create_dflt(sch, &bfifo_qdisc_ops, ctl->limit);
198                 if (IS_ERR(child))
199                         return PTR_ERR(child);
200         }
201
202         sch_tree_lock(sch);
203         q->flags = ctl->flags;
204         q->limit = ctl->limit;
205         if (child) {
206                 qdisc_tree_decrease_qlen(q->qdisc, q->qdisc->q.qlen);
207                 qdisc_destroy(q->qdisc);
208                 q->qdisc = child;
209         }
210
211         red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog,
212                                  ctl->Plog, ctl->Scell_log,
213                                  nla_data(tb[TCA_RED_STAB]));
214
215         del_timer(&q->adapt_timer);
216         if (ctl->flags & TC_RED_ADAPTATIVE)
217                 mod_timer(&q->adapt_timer, jiffies + HZ/2);
218
219         if (!q->qdisc->q.qlen)
220                 red_start_of_idle_period(&q->parms);
221
222         sch_tree_unlock(sch);
223         return 0;
224 }
225
226 static inline void red_adaptative_timer(unsigned long arg)
227 {
228         struct Qdisc *sch = (struct Qdisc *)arg;
229         struct red_sched_data *q = qdisc_priv(sch);
230         spinlock_t *root_lock = qdisc_lock(qdisc_root_sleeping(sch));
231
232         spin_lock(root_lock);
233         red_adaptative_algo(&q->parms);
234         mod_timer(&q->adapt_timer, jiffies + HZ/2);
235         spin_unlock(root_lock);
236 }
237
238 static int red_init(struct Qdisc *sch, struct nlattr *opt)
239 {
240         struct red_sched_data *q = qdisc_priv(sch);
241
242         q->qdisc = &noop_qdisc;
243         setup_timer(&q->adapt_timer, red_adaptative_timer, (unsigned long)sch);
244         return red_change(sch, opt);
245 }
246
247 static int red_dump(struct Qdisc *sch, struct sk_buff *skb)
248 {
249         struct red_sched_data *q = qdisc_priv(sch);
250         struct nlattr *opts = NULL;
251         struct tc_red_qopt opt = {
252                 .limit          = q->limit,
253                 .flags          = q->flags,
254                 .qth_min        = q->parms.qth_min >> q->parms.Wlog,
255                 .qth_max        = q->parms.qth_max >> q->parms.Wlog,
256                 .Wlog           = q->parms.Wlog,
257                 .Plog           = q->parms.Plog,
258                 .Scell_log      = q->parms.Scell_log,
259         };
260
261         sch->qstats.backlog = q->qdisc->qstats.backlog;
262         opts = nla_nest_start(skb, TCA_OPTIONS);
263         if (opts == NULL)
264                 goto nla_put_failure;
265         NLA_PUT(skb, TCA_RED_PARMS, sizeof(opt), &opt);
266         NLA_PUT_U32(skb, TCA_RED_MAX_P, q->parms.max_P);
267         return nla_nest_end(skb, opts);
268
269 nla_put_failure:
270         nla_nest_cancel(skb, opts);
271         return -EMSGSIZE;
272 }
273
274 static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
275 {
276         struct red_sched_data *q = qdisc_priv(sch);
277         struct tc_red_xstats st = {
278                 .early  = q->stats.prob_drop + q->stats.forced_drop,
279                 .pdrop  = q->stats.pdrop,
280                 .other  = q->stats.other,
281                 .marked = q->stats.prob_mark + q->stats.forced_mark,
282         };
283
284         return gnet_stats_copy_app(d, &st, sizeof(st));
285 }
286
287 static int red_dump_class(struct Qdisc *sch, unsigned long cl,
288                           struct sk_buff *skb, struct tcmsg *tcm)
289 {
290         struct red_sched_data *q = qdisc_priv(sch);
291
292         tcm->tcm_handle |= TC_H_MIN(1);
293         tcm->tcm_info = q->qdisc->handle;
294         return 0;
295 }
296
297 static int red_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
298                      struct Qdisc **old)
299 {
300         struct red_sched_data *q = qdisc_priv(sch);
301
302         if (new == NULL)
303                 new = &noop_qdisc;
304
305         sch_tree_lock(sch);
306         *old = q->qdisc;
307         q->qdisc = new;
308         qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
309         qdisc_reset(*old);
310         sch_tree_unlock(sch);
311         return 0;
312 }
313
314 static struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg)
315 {
316         struct red_sched_data *q = qdisc_priv(sch);
317         return q->qdisc;
318 }
319
320 static unsigned long red_get(struct Qdisc *sch, u32 classid)
321 {
322         return 1;
323 }
324
325 static void red_put(struct Qdisc *sch, unsigned long arg)
326 {
327 }
328
329 static void red_walk(struct Qdisc *sch, struct qdisc_walker *walker)
330 {
331         if (!walker->stop) {
332                 if (walker->count >= walker->skip)
333                         if (walker->fn(sch, 1, walker) < 0) {
334                                 walker->stop = 1;
335                                 return;
336                         }
337                 walker->count++;
338         }
339 }
340
341 static const struct Qdisc_class_ops red_class_ops = {
342         .graft          =       red_graft,
343         .leaf           =       red_leaf,
344         .get            =       red_get,
345         .put            =       red_put,
346         .walk           =       red_walk,
347         .dump           =       red_dump_class,
348 };
349
350 static struct Qdisc_ops red_qdisc_ops __read_mostly = {
351         .id             =       "red",
352         .priv_size      =       sizeof(struct red_sched_data),
353         .cl_ops         =       &red_class_ops,
354         .enqueue        =       red_enqueue,
355         .dequeue        =       red_dequeue,
356         .peek           =       red_peek,
357         .drop           =       red_drop,
358         .init           =       red_init,
359         .reset          =       red_reset,
360         .destroy        =       red_destroy,
361         .change         =       red_change,
362         .dump           =       red_dump,
363         .dump_stats     =       red_dump_stats,
364         .owner          =       THIS_MODULE,
365 };
366
367 static int __init red_module_init(void)
368 {
369         return register_qdisc(&red_qdisc_ops);
370 }
371
372 static void __exit red_module_exit(void)
373 {
374         unregister_qdisc(&red_qdisc_ops);
375 }
376
377 module_init(red_module_init)
378 module_exit(red_module_exit)
379
380 MODULE_LICENSE("GPL");