?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Merge master.kernel.org:/pub/scm/linux/kernel/git/davem/sparc-2.6
[linux/fpc-iii.git] / net / sched / sch_red.c
blobd65cadddea691020c0ce71e1ae08bf7af8975c78
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/netdevice.h>
21 #include <linux/skbuff.h>
22 #include <net/pkt_sched.h>
23 #include <net/inet_ecn.h>
24 #include <net/red.h>
25
26
27 /* Parameters, settable by user:
28 -----------------------------
29
30 limit - bytes (must be > qth_max + burst)
31
32 Hard limit on queue length, should be chosen >qth_max
33 to allow packet bursts. This parameter does not
34 affect the algorithms behaviour and can be chosen
35 arbitrarily high (well, less than ram size)
36 Really, this limit will never be reached
37 if RED works correctly.
38 */
39
40 struct red_sched_data
41 {
42 u32 limit; /* HARD maximal queue length */
43 unsigned char flags;
44 struct red_parms parms;
45 struct red_stats stats;
46 struct Qdisc *qdisc;
47 };
48
49 static inline int red_use_ecn(struct red_sched_data *q)
50 {
51 return q->flags & TC_RED_ECN;
52 }
53
54 static inline int red_use_harddrop(struct red_sched_data *q)
55 {
56 return q->flags & TC_RED_HARDDROP;
57 }
58
59 static int red_enqueue(struct sk_buff *skb, struct Qdisc* sch)
60 {
61 struct red_sched_data *q = qdisc_priv(sch);
62 struct Qdisc *child = q->qdisc;
63 int ret;
64
65 q->parms.qavg = red_calc_qavg(&q->parms, child->qstats.backlog);
66
67 if (red_is_idling(&q->parms))
68 red_end_of_idle_period(&q->parms);
69
70 switch (red_action(&q->parms, q->parms.qavg)) {
71 case RED_DONT_MARK:
72 break;
73
74 case RED_PROB_MARK:
75 sch->qstats.overlimits++;
76 if (!red_use_ecn(q) || !INET_ECN_set_ce(skb)) {
77 q->stats.prob_drop++;
78 goto congestion_drop;
79 }
80
81 q->stats.prob_mark++;
82 break;
83
84 case RED_HARD_MARK:
85 sch->qstats.overlimits++;
86 if (red_use_harddrop(q) || !red_use_ecn(q) ||
87 !INET_ECN_set_ce(skb)) {
88 q->stats.forced_drop++;
89 goto congestion_drop;
90 }
91
92 q->stats.forced_mark++;
93 break;
94 }
95
96 ret = child->enqueue(skb, child);
97 if (likely(ret == NET_XMIT_SUCCESS)) {
98 sch->bstats.bytes += skb->len;
99 sch->bstats.packets++;
100 sch->q.qlen++;
101 } else {
102 q->stats.pdrop++;
103 sch->qstats.drops++;
104 }
105 return ret;
106
107 congestion_drop:
108 qdisc_drop(skb, sch);
109 return NET_XMIT_CN;
110 }
111
112 static int red_requeue(struct sk_buff *skb, struct Qdisc* sch)
113 {
114 struct red_sched_data *q = qdisc_priv(sch);
115 struct Qdisc *child = q->qdisc;
116 int ret;
117
118 if (red_is_idling(&q->parms))
119 red_end_of_idle_period(&q->parms);
120
121 ret = child->ops->requeue(skb, child);
122 if (likely(ret == NET_XMIT_SUCCESS)) {
123 sch->qstats.requeues++;
124 sch->q.qlen++;
125 }
126 return ret;
127 }
128
129 static struct sk_buff * red_dequeue(struct Qdisc* sch)
130 {
131 struct sk_buff *skb;
132 struct red_sched_data *q = qdisc_priv(sch);
133 struct Qdisc *child = q->qdisc;
134
135 skb = child->dequeue(child);
136 if (skb)
137 sch->q.qlen--;
138 else if (!red_is_idling(&q->parms))
139 red_start_of_idle_period(&q->parms);
140
141 return skb;
142 }
143
144 static unsigned int red_drop(struct Qdisc* sch)
145 {
146 struct red_sched_data *q = qdisc_priv(sch);
147 struct Qdisc *child = q->qdisc;
148 unsigned int len;
149
150 if (child->ops->drop && (len = child->ops->drop(child)) > 0) {
151 q->stats.other++;
152 sch->qstats.drops++;
153 sch->q.qlen--;
154 return len;
155 }
156
157 if (!red_is_idling(&q->parms))
158 red_start_of_idle_period(&q->parms);
159
160 return 0;
161 }
162
163 static void red_reset(struct Qdisc* sch)
164 {
165 struct red_sched_data *q = qdisc_priv(sch);
166
167 qdisc_reset(q->qdisc);
168 sch->q.qlen = 0;
169 red_restart(&q->parms);
170 }
171
172 static void red_destroy(struct Qdisc *sch)
173 {
174 struct red_sched_data *q = qdisc_priv(sch);
175 qdisc_destroy(q->qdisc);
176 }
177
178 static struct Qdisc *red_create_dflt(struct net_device *dev, u32 limit)
179 {
180 struct Qdisc *q = qdisc_create_dflt(dev, &bfifo_qdisc_ops);
181 struct rtattr *rta;
182 int ret;
183
184 if (q) {
185 rta = kmalloc(RTA_LENGTH(sizeof(struct tc_fifo_qopt)),
186 GFP_KERNEL);
187 if (rta) {
188 rta->rta_type = RTM_NEWQDISC;
189 rta->rta_len = RTA_LENGTH(sizeof(struct tc_fifo_qopt));
190 ((struct tc_fifo_qopt *)RTA_DATA(rta))->limit = limit;
191
192 ret = q->ops->change(q, rta);
193 kfree(rta);
194
195 if (ret == 0)
196 return q;
197 }
198 qdisc_destroy(q);
199 }
200 return NULL;
201 }
202
203 static int red_change(struct Qdisc *sch, struct rtattr *opt)
204 {
205 struct red_sched_data *q = qdisc_priv(sch);
206 struct rtattr *tb[TCA_RED_MAX];
207 struct tc_red_qopt *ctl;
208 struct Qdisc *child = NULL;
209
210 if (opt == NULL || rtattr_parse_nested(tb, TCA_RED_MAX, opt))
211 return -EINVAL;
212
213 if (tb[TCA_RED_PARMS-1] == NULL ||
214 RTA_PAYLOAD(tb[TCA_RED_PARMS-1]) < sizeof(*ctl) ||
215 tb[TCA_RED_STAB-1] == NULL ||
216 RTA_PAYLOAD(tb[TCA_RED_STAB-1]) < RED_STAB_SIZE)
217 return -EINVAL;
218
219 ctl = RTA_DATA(tb[TCA_RED_PARMS-1]);
220
221 if (ctl->limit > 0) {
222 child = red_create_dflt(sch->dev, ctl->limit);
223 if (child == NULL)
224 return -ENOMEM;
225 }
226
227 sch_tree_lock(sch);
228 q->flags = ctl->flags;
229 q->limit = ctl->limit;
230 if (child)
231 qdisc_destroy(xchg(&q->qdisc, child));
232
233 red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog,
234 ctl->Plog, ctl->Scell_log,
235 RTA_DATA(tb[TCA_RED_STAB-1]));
236
237 if (skb_queue_empty(&sch->q))
238 red_end_of_idle_period(&q->parms);
239
240 sch_tree_unlock(sch);
241 return 0;
242 }
243
244 static int red_init(struct Qdisc* sch, struct rtattr *opt)
245 {
246 struct red_sched_data *q = qdisc_priv(sch);
247
248 q->qdisc = &noop_qdisc;
249 return red_change(sch, opt);
250 }
251
252 static int red_dump(struct Qdisc *sch, struct sk_buff *skb)
253 {
254 struct red_sched_data *q = qdisc_priv(sch);
255 struct rtattr *opts = NULL;
256 struct tc_red_qopt opt = {
257 .limit = q->limit,
258 .flags = q->flags,
259 .qth_min = q->parms.qth_min >> q->parms.Wlog,
260 .qth_max = q->parms.qth_max >> q->parms.Wlog,
261 .Wlog = q->parms.Wlog,
262 .Plog = q->parms.Plog,
263 .Scell_log = q->parms.Scell_log,
264 };
265
266 opts = RTA_NEST(skb, TCA_OPTIONS);
267 RTA_PUT(skb, TCA_RED_PARMS, sizeof(opt), &opt);
268 return RTA_NEST_END(skb, opts);
269
270 rtattr_failure:
271 return RTA_NEST_CANCEL(skb, opts);
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 if (cl != 1)
293 return -ENOENT;
294 tcm->tcm_handle |= TC_H_MIN(1);
295 tcm->tcm_info = q->qdisc->handle;
296 return 0;
297 }
298
299 static int red_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
300 struct Qdisc **old)
301 {
302 struct red_sched_data *q = qdisc_priv(sch);
303
304 if (new == NULL)
305 new = &noop_qdisc;
306
307 sch_tree_lock(sch);
308 *old = xchg(&q->qdisc, new);
309 qdisc_reset(*old);
310 sch->q.qlen = 0;
311 sch_tree_unlock(sch);
312 return 0;
313 }
314
315 static struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg)
316 {
317 struct red_sched_data *q = qdisc_priv(sch);
318 return q->qdisc;
319 }
320
321 static unsigned long red_get(struct Qdisc *sch, u32 classid)
322 {
323 return 1;
324 }
325
326 static void red_put(struct Qdisc *sch, unsigned long arg)
327 {
328 return;
329 }
330
331 static int red_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
332 struct rtattr **tca, unsigned long *arg)
333 {
334 return -ENOSYS;
335 }
336
337 static int red_delete(struct Qdisc *sch, unsigned long cl)
338 {
339 return -ENOSYS;
340 }
341
342 static void red_walk(struct Qdisc *sch, struct qdisc_walker *walker)
343 {
344 if (!walker->stop) {
345 if (walker->count >= walker->skip)
346 if (walker->fn(sch, 1, walker) < 0) {
347 walker->stop = 1;
348 return;
349 }
350 walker->count++;
351 }
352 }
353
354 static struct tcf_proto **red_find_tcf(struct Qdisc *sch, unsigned long cl)
355 {
356 return NULL;
357 }
358
359 static struct Qdisc_class_ops red_class_ops = {
360 .graft = red_graft,
361 .leaf = red_leaf,
362 .get = red_get,
363 .put = red_put,
364 .change = red_change_class,
365 .delete = red_delete,
366 .walk = red_walk,
367 .tcf_chain = red_find_tcf,
368 .dump = red_dump_class,
369 };
370
371 static struct Qdisc_ops red_qdisc_ops = {
372 .id = "red",
373 .priv_size = sizeof(struct red_sched_data),
374 .cl_ops = &red_class_ops,
375 .enqueue = red_enqueue,
376 .dequeue = red_dequeue,
377 .requeue = red_requeue,
378 .drop = red_drop,
379 .init = red_init,
380 .reset = red_reset,
381 .destroy = red_destroy,
382 .change = red_change,
383 .dump = red_dump,
384 .dump_stats = red_dump_stats,
385 .owner = THIS_MODULE,
386 };
387
388 static int __init red_module_init(void)
389 {
390 return register_qdisc(&red_qdisc_ops);
391 }
392
393 static void __exit red_module_exit(void)
394 {
395 unregister_qdisc(&red_qdisc_ops);
396 }
397
398 module_init(red_module_init)
399 module_exit(red_module_exit)
400
401 MODULE_LICENSE("GPL");
Linux with added FPC-III support