?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
[PATCH] Replace regular code with appropriate calls to container_of()
[linux-2.6/verdex.git] / net / sched / sch_red.c
blobacddad08850fa65d1082e2d5377b8fd9d3956b4b
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 Qdisc *sch, u32 limit)
179 {
180 struct Qdisc *q;
181 struct rtattr *rta;
182 int ret;
183
184 q = qdisc_create_dflt(sch->dev, &bfifo_qdisc_ops,
185 TC_H_MAKE(sch->handle, 1));
186 if (q) {
187 rta = kmalloc(RTA_LENGTH(sizeof(struct tc_fifo_qopt)),
188 GFP_KERNEL);
189 if (rta) {
190 rta->rta_type = RTM_NEWQDISC;
191 rta->rta_len = RTA_LENGTH(sizeof(struct tc_fifo_qopt));
192 ((struct tc_fifo_qopt *)RTA_DATA(rta))->limit = limit;
193
194 ret = q->ops->change(q, rta);
195 kfree(rta);
196
197 if (ret == 0)
198 return q;
199 }
200 qdisc_destroy(q);
201 }
202 return NULL;
203 }
204
205 static int red_change(struct Qdisc *sch, struct rtattr *opt)
206 {
207 struct red_sched_data *q = qdisc_priv(sch);
208 struct rtattr *tb[TCA_RED_MAX];
209 struct tc_red_qopt *ctl;
210 struct Qdisc *child = NULL;
211
212 if (opt == NULL || rtattr_parse_nested(tb, TCA_RED_MAX, opt))
213 return -EINVAL;
214
215 if (tb[TCA_RED_PARMS-1] == NULL ||
216 RTA_PAYLOAD(tb[TCA_RED_PARMS-1]) < sizeof(*ctl) ||
217 tb[TCA_RED_STAB-1] == NULL ||
218 RTA_PAYLOAD(tb[TCA_RED_STAB-1]) < RED_STAB_SIZE)
219 return -EINVAL;
220
221 ctl = RTA_DATA(tb[TCA_RED_PARMS-1]);
222
223 if (ctl->limit > 0) {
224 child = red_create_dflt(sch, ctl->limit);
225 if (child == NULL)
226 return -ENOMEM;
227 }
228
229 sch_tree_lock(sch);
230 q->flags = ctl->flags;
231 q->limit = ctl->limit;
232 if (child) {
233 qdisc_tree_decrease_qlen(q->qdisc, q->qdisc->q.qlen);
234 qdisc_destroy(xchg(&q->qdisc, child));
235 }
236
237 red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog,
238 ctl->Plog, ctl->Scell_log,
239 RTA_DATA(tb[TCA_RED_STAB-1]));
240
241 if (skb_queue_empty(&sch->q))
242 red_end_of_idle_period(&q->parms);
243
244 sch_tree_unlock(sch);
245 return 0;
246 }
247
248 static int red_init(struct Qdisc* sch, struct rtattr *opt)
249 {
250 struct red_sched_data *q = qdisc_priv(sch);
251
252 q->qdisc = &noop_qdisc;
253 return red_change(sch, opt);
254 }
255
256 static int red_dump(struct Qdisc *sch, struct sk_buff *skb)
257 {
258 struct red_sched_data *q = qdisc_priv(sch);
259 struct rtattr *opts = NULL;
260 struct tc_red_qopt opt = {
261 .limit = q->limit,
262 .flags = q->flags,
263 .qth_min = q->parms.qth_min >> q->parms.Wlog,
264 .qth_max = q->parms.qth_max >> q->parms.Wlog,
265 .Wlog = q->parms.Wlog,
266 .Plog = q->parms.Plog,
267 .Scell_log = q->parms.Scell_log,
268 };
269
270 opts = RTA_NEST(skb, TCA_OPTIONS);
271 RTA_PUT(skb, TCA_RED_PARMS, sizeof(opt), &opt);
272 return RTA_NEST_END(skb, opts);
273
274 rtattr_failure:
275 return RTA_NEST_CANCEL(skb, opts);
276 }
277
278 static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
279 {
280 struct red_sched_data *q = qdisc_priv(sch);
281 struct tc_red_xstats st = {
282 .early = q->stats.prob_drop + q->stats.forced_drop,
283 .pdrop = q->stats.pdrop,
284 .other = q->stats.other,
285 .marked = q->stats.prob_mark + q->stats.forced_mark,
286 };
287
288 return gnet_stats_copy_app(d, &st, sizeof(st));
289 }
290
291 static int red_dump_class(struct Qdisc *sch, unsigned long cl,
292 struct sk_buff *skb, struct tcmsg *tcm)
293 {
294 struct red_sched_data *q = qdisc_priv(sch);
295
296 if (cl != 1)
297 return -ENOENT;
298 tcm->tcm_handle |= TC_H_MIN(1);
299 tcm->tcm_info = q->qdisc->handle;
300 return 0;
301 }
302
303 static int red_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
304 struct Qdisc **old)
305 {
306 struct red_sched_data *q = qdisc_priv(sch);
307
308 if (new == NULL)
309 new = &noop_qdisc;
310
311 sch_tree_lock(sch);
312 *old = xchg(&q->qdisc, new);
313 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
314 qdisc_reset(*old);
315 sch_tree_unlock(sch);
316 return 0;
317 }
318
319 static struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg)
320 {
321 struct red_sched_data *q = qdisc_priv(sch);
322 return q->qdisc;
323 }
324
325 static unsigned long red_get(struct Qdisc *sch, u32 classid)
326 {
327 return 1;
328 }
329
330 static void red_put(struct Qdisc *sch, unsigned long arg)
331 {
332 return;
333 }
334
335 static int red_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
336 struct rtattr **tca, unsigned long *arg)
337 {
338 return -ENOSYS;
339 }
340
341 static int red_delete(struct Qdisc *sch, unsigned long cl)
342 {
343 return -ENOSYS;
344 }
345
346 static void red_walk(struct Qdisc *sch, struct qdisc_walker *walker)
347 {
348 if (!walker->stop) {
349 if (walker->count >= walker->skip)
350 if (walker->fn(sch, 1, walker) < 0) {
351 walker->stop = 1;
352 return;
353 }
354 walker->count++;
355 }
356 }
357
358 static struct tcf_proto **red_find_tcf(struct Qdisc *sch, unsigned long cl)
359 {
360 return NULL;
361 }
362
363 static struct Qdisc_class_ops red_class_ops = {
364 .graft = red_graft,
365 .leaf = red_leaf,
366 .get = red_get,
367 .put = red_put,
368 .change = red_change_class,
369 .delete = red_delete,
370 .walk = red_walk,
371 .tcf_chain = red_find_tcf,
372 .dump = red_dump_class,
373 };
374
375 static struct Qdisc_ops red_qdisc_ops = {
376 .id = "red",
377 .priv_size = sizeof(struct red_sched_data),
378 .cl_ops = &red_class_ops,
379 .enqueue = red_enqueue,
380 .dequeue = red_dequeue,
381 .requeue = red_requeue,
382 .drop = red_drop,
383 .init = red_init,
384 .reset = red_reset,
385 .destroy = red_destroy,
386 .change = red_change,
387 .dump = red_dump,
388 .dump_stats = red_dump_stats,
389 .owner = THIS_MODULE,
390 };
391
392 static int __init red_module_init(void)
393 {
394 return register_qdisc(&red_qdisc_ops);
395 }
396
397 static void __exit red_module_exit(void)
398 {
399 unregister_qdisc(&red_qdisc_ops);
400 }
401
402 module_init(red_module_init)
403 module_exit(red_module_exit)
404
405 MODULE_LICENSE("GPL");
Verdex Pro support