Blame view
net/sched/sch_red.c
8.71 KB
1da177e4c Linux-2.6.12-rc2 |
1 2 3 4 5 6 7 8 9 10 11 |
/* * net/sched/sch_red.c Random Early Detection queue. * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License * as published by the Free Software Foundation; either version * 2 of the License, or (at your option) any later version. * * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru> * * Changes: |
dba051f36 [PKT_SCHED]: RED:... |
12 |
* J Hadi Salim 980914: computation fixes |
1da177e4c Linux-2.6.12-rc2 |
13 |
* Alexey Makarenko <makar@phoenix.kharkov.ua> 990814: qave on idle link was calculated incorrectly. |
dba051f36 [PKT_SCHED]: RED:... |
14 |
* J Hadi Salim 980816: ECN support |
1da177e4c Linux-2.6.12-rc2 |
15 |
*/ |
1da177e4c Linux-2.6.12-rc2 |
16 |
#include <linux/module.h> |
1da177e4c Linux-2.6.12-rc2 |
17 18 |
#include <linux/types.h> #include <linux/kernel.h> |
1da177e4c Linux-2.6.12-rc2 |
19 |
#include <linux/skbuff.h> |
1da177e4c Linux-2.6.12-rc2 |
20 21 |
#include <net/pkt_sched.h> #include <net/inet_ecn.h> |
6b31b28a4 [PKT_SCHED]: RED:... |
22 |
#include <net/red.h> |
1da177e4c Linux-2.6.12-rc2 |
23 |
|
6b31b28a4 [PKT_SCHED]: RED:... |
24 |
/* Parameters, settable by user: |
1da177e4c Linux-2.6.12-rc2 |
25 26 27 28 29 30 31 32 33 34 |
----------------------------- limit - bytes (must be > qth_max + burst) Hard limit on queue length, should be chosen >qth_max to allow packet bursts. This parameter does not affect the algorithms behaviour and can be chosen arbitrarily high (well, less than ram size) Really, this limit will never be reached if RED works correctly. |
1da177e4c Linux-2.6.12-rc2 |
35 |
*/ |
cc7ec456f net_sched: cleanups |
36 |
struct red_sched_data { |
6b31b28a4 [PKT_SCHED]: RED:... |
37 38 |
u32 limit; /* HARD maximal queue length */ unsigned char flags; |
8af2a218d sch_red: Adaptati... |
39 |
struct timer_list adapt_timer; |
6b31b28a4 [PKT_SCHED]: RED:... |
40 |
struct red_parms parms; |
eeca6688d net_sched: red: s... |
41 |
struct red_vars vars; |
6b31b28a4 [PKT_SCHED]: RED:... |
42 |
struct red_stats stats; |
f38c39d6c [PKT_SCHED]: Conv... |
43 |
struct Qdisc *qdisc; |
1da177e4c Linux-2.6.12-rc2 |
44 |
}; |
6b31b28a4 [PKT_SCHED]: RED:... |
45 |
static inline int red_use_ecn(struct red_sched_data *q) |
1da177e4c Linux-2.6.12-rc2 |
46 |
{ |
6b31b28a4 [PKT_SCHED]: RED:... |
47 |
return q->flags & TC_RED_ECN; |
1da177e4c Linux-2.6.12-rc2 |
48 |
} |
bdc450a0b [PKT_SCHED]: (G)R... |
49 50 51 52 |
static inline int red_use_harddrop(struct red_sched_data *q) { return q->flags & TC_RED_HARDDROP; } |
cc7ec456f net_sched: cleanups |
53 |
static int red_enqueue(struct sk_buff *skb, struct Qdisc *sch) |
1da177e4c Linux-2.6.12-rc2 |
54 55 |
{ struct red_sched_data *q = qdisc_priv(sch); |
f38c39d6c [PKT_SCHED]: Conv... |
56 57 |
struct Qdisc *child = q->qdisc; int ret; |
1da177e4c Linux-2.6.12-rc2 |
58 |
|
eeca6688d net_sched: red: s... |
59 60 61 |
q->vars.qavg = red_calc_qavg(&q->parms, &q->vars, child->qstats.backlog); |
1da177e4c Linux-2.6.12-rc2 |
62 |
|
eeca6688d net_sched: red: s... |
63 64 |
if (red_is_idling(&q->vars)) red_end_of_idle_period(&q->vars); |
1da177e4c Linux-2.6.12-rc2 |
65 |
|
eeca6688d net_sched: red: s... |
66 |
switch (red_action(&q->parms, &q->vars, q->vars.qavg)) { |
cc7ec456f net_sched: cleanups |
67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
case RED_DONT_MARK: break; case RED_PROB_MARK: sch->qstats.overlimits++; if (!red_use_ecn(q) || !INET_ECN_set_ce(skb)) { q->stats.prob_drop++; goto congestion_drop; } q->stats.prob_mark++; break; case RED_HARD_MARK: sch->qstats.overlimits++; if (red_use_harddrop(q) || !red_use_ecn(q) || !INET_ECN_set_ce(skb)) { q->stats.forced_drop++; goto congestion_drop; } q->stats.forced_mark++; break; |
1da177e4c Linux-2.6.12-rc2 |
90 |
} |
5f86173bd net_sched: Add qd... |
91 |
ret = qdisc_enqueue(skb, child); |
f38c39d6c [PKT_SCHED]: Conv... |
92 |
if (likely(ret == NET_XMIT_SUCCESS)) { |
f38c39d6c [PKT_SCHED]: Conv... |
93 |
sch->q.qlen++; |
378a2f090 net_sched: Add qd... |
94 |
} else if (net_xmit_drop_count(ret)) { |
f38c39d6c [PKT_SCHED]: Conv... |
95 96 97 98 |
q->stats.pdrop++; sch->qstats.drops++; } return ret; |
6b31b28a4 [PKT_SCHED]: RED:... |
99 100 |
congestion_drop: |
9e178ff27 [PKT_SCHED]: RED:... |
101 |
qdisc_drop(skb, sch); |
1da177e4c Linux-2.6.12-rc2 |
102 103 |
return NET_XMIT_CN; } |
cc7ec456f net_sched: cleanups |
104 |
static struct sk_buff *red_dequeue(struct Qdisc *sch) |
1da177e4c Linux-2.6.12-rc2 |
105 106 107 |
{ struct sk_buff *skb; struct red_sched_data *q = qdisc_priv(sch); |
f38c39d6c [PKT_SCHED]: Conv... |
108 |
struct Qdisc *child = q->qdisc; |
1da177e4c Linux-2.6.12-rc2 |
109 |
|
f38c39d6c [PKT_SCHED]: Conv... |
110 |
skb = child->dequeue(child); |
9190b3b32 net_sched: accura... |
111 112 |
if (skb) { qdisc_bstats_update(sch, skb); |
f38c39d6c [PKT_SCHED]: Conv... |
113 |
sch->q.qlen--; |
9190b3b32 net_sched: accura... |
114 |
} else { |
eeca6688d net_sched: red: s... |
115 116 |
if (!red_is_idling(&q->vars)) red_start_of_idle_period(&q->vars); |
9190b3b32 net_sched: accura... |
117 |
} |
9e178ff27 [PKT_SCHED]: RED:... |
118 |
return skb; |
1da177e4c Linux-2.6.12-rc2 |
119 |
} |
cc7ec456f net_sched: cleanups |
120 |
static struct sk_buff *red_peek(struct Qdisc *sch) |
8e3af9789 pkt_sched: Add qd... |
121 122 123 124 125 126 |
{ struct red_sched_data *q = qdisc_priv(sch); struct Qdisc *child = q->qdisc; return child->ops->peek(child); } |
cc7ec456f net_sched: cleanups |
127 |
static unsigned int red_drop(struct Qdisc *sch) |
1da177e4c Linux-2.6.12-rc2 |
128 |
{ |
1da177e4c Linux-2.6.12-rc2 |
129 |
struct red_sched_data *q = qdisc_priv(sch); |
f38c39d6c [PKT_SCHED]: Conv... |
130 131 |
struct Qdisc *child = q->qdisc; unsigned int len; |
1da177e4c Linux-2.6.12-rc2 |
132 |
|
f38c39d6c [PKT_SCHED]: Conv... |
133 |
if (child->ops->drop && (len = child->ops->drop(child)) > 0) { |
6b31b28a4 [PKT_SCHED]: RED:... |
134 |
q->stats.other++; |
f38c39d6c [PKT_SCHED]: Conv... |
135 136 |
sch->qstats.drops++; sch->q.qlen--; |
1da177e4c Linux-2.6.12-rc2 |
137 138 |
return len; } |
6b31b28a4 [PKT_SCHED]: RED:... |
139 |
|
eeca6688d net_sched: red: s... |
140 141 |
if (!red_is_idling(&q->vars)) red_start_of_idle_period(&q->vars); |
6a1b63d46 [PKT_SCHED]: RED:... |
142 |
|
1da177e4c Linux-2.6.12-rc2 |
143 144 |
return 0; } |
cc7ec456f net_sched: cleanups |
145 |
static void red_reset(struct Qdisc *sch) |
1da177e4c Linux-2.6.12-rc2 |
146 147 |
{ struct red_sched_data *q = qdisc_priv(sch); |
f38c39d6c [PKT_SCHED]: Conv... |
148 149 |
qdisc_reset(q->qdisc); sch->q.qlen = 0; |
eeca6688d net_sched: red: s... |
150 |
red_restart(&q->vars); |
1da177e4c Linux-2.6.12-rc2 |
151 |
} |
f38c39d6c [PKT_SCHED]: Conv... |
152 153 154 |
static void red_destroy(struct Qdisc *sch) { struct red_sched_data *q = qdisc_priv(sch); |
8af2a218d sch_red: Adaptati... |
155 156 |
del_timer_sync(&q->adapt_timer); |
f38c39d6c [PKT_SCHED]: Conv... |
157 158 |
qdisc_destroy(q->qdisc); } |
27a3421e4 [NET_SCHED]: Use ... |
159 160 161 |
static const struct nla_policy red_policy[TCA_RED_MAX + 1] = { [TCA_RED_PARMS] = { .len = sizeof(struct tc_red_qopt) }, [TCA_RED_STAB] = { .len = RED_STAB_SIZE }, |
a73ed26bb sch_red: generali... |
162 |
[TCA_RED_MAX_P] = { .type = NLA_U32 }, |
27a3421e4 [NET_SCHED]: Use ... |
163 |
}; |
1e90474c3 [NET_SCHED]: Conv... |
164 |
static int red_change(struct Qdisc *sch, struct nlattr *opt) |
1da177e4c Linux-2.6.12-rc2 |
165 166 |
{ struct red_sched_data *q = qdisc_priv(sch); |
1e90474c3 [NET_SCHED]: Conv... |
167 |
struct nlattr *tb[TCA_RED_MAX + 1]; |
1da177e4c Linux-2.6.12-rc2 |
168 |
struct tc_red_qopt *ctl; |
f38c39d6c [PKT_SCHED]: Conv... |
169 |
struct Qdisc *child = NULL; |
cee63723b [NET_SCHED]: Prop... |
170 |
int err; |
a73ed26bb sch_red: generali... |
171 |
u32 max_P; |
1da177e4c Linux-2.6.12-rc2 |
172 |
|
cee63723b [NET_SCHED]: Prop... |
173 |
if (opt == NULL) |
dba051f36 [PKT_SCHED]: RED:... |
174 |
return -EINVAL; |
27a3421e4 [NET_SCHED]: Use ... |
175 |
err = nla_parse_nested(tb, TCA_RED_MAX, opt, red_policy); |
cee63723b [NET_SCHED]: Prop... |
176 177 |
if (err < 0) return err; |
1e90474c3 [NET_SCHED]: Conv... |
178 |
if (tb[TCA_RED_PARMS] == NULL || |
27a3421e4 [NET_SCHED]: Use ... |
179 |
tb[TCA_RED_STAB] == NULL) |
1da177e4c Linux-2.6.12-rc2 |
180 |
return -EINVAL; |
a73ed26bb sch_red: generali... |
181 |
max_P = tb[TCA_RED_MAX_P] ? nla_get_u32(tb[TCA_RED_MAX_P]) : 0; |
1e90474c3 [NET_SCHED]: Conv... |
182 |
ctl = nla_data(tb[TCA_RED_PARMS]); |
1da177e4c Linux-2.6.12-rc2 |
183 |
|
f38c39d6c [PKT_SCHED]: Conv... |
184 |
if (ctl->limit > 0) { |
fb0305ce1 net-sched: consol... |
185 186 187 |
child = fifo_create_dflt(sch, &bfifo_qdisc_ops, ctl->limit); if (IS_ERR(child)) return PTR_ERR(child); |
f38c39d6c [PKT_SCHED]: Conv... |
188 |
} |
1da177e4c Linux-2.6.12-rc2 |
189 190 |
sch_tree_lock(sch); q->flags = ctl->flags; |
1da177e4c Linux-2.6.12-rc2 |
191 |
q->limit = ctl->limit; |
5e50da01d [NET_SCHED]: Fix ... |
192 193 |
if (child) { qdisc_tree_decrease_qlen(q->qdisc, q->qdisc->q.qlen); |
b94c8afcb pkt_sched: remove... |
194 195 |
qdisc_destroy(q->qdisc); q->qdisc = child; |
5e50da01d [NET_SCHED]: Fix ... |
196 |
} |
1da177e4c Linux-2.6.12-rc2 |
197 |
|
eeca6688d net_sched: red: s... |
198 199 |
red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog, |
a73ed26bb sch_red: generali... |
200 201 202 |
ctl->Plog, ctl->Scell_log, nla_data(tb[TCA_RED_STAB]), max_P); |
eeca6688d net_sched: red: s... |
203 |
red_set_vars(&q->vars); |
6b31b28a4 [PKT_SCHED]: RED:... |
204 |
|
8af2a218d sch_red: Adaptati... |
205 206 207 |
del_timer(&q->adapt_timer); if (ctl->flags & TC_RED_ADAPTATIVE) mod_timer(&q->adapt_timer, jiffies + HZ/2); |
1ee5fa1e9 sch_red: fix red_... |
208 |
if (!q->qdisc->q.qlen) |
eeca6688d net_sched: red: s... |
209 |
red_start_of_idle_period(&q->vars); |
dba051f36 [PKT_SCHED]: RED:... |
210 |
|
1da177e4c Linux-2.6.12-rc2 |
211 212 213 |
sch_tree_unlock(sch); return 0; } |
8af2a218d sch_red: Adaptati... |
214 215 216 217 218 219 220 |
static inline void red_adaptative_timer(unsigned long arg) { struct Qdisc *sch = (struct Qdisc *)arg; struct red_sched_data *q = qdisc_priv(sch); spinlock_t *root_lock = qdisc_lock(qdisc_root_sleeping(sch)); spin_lock(root_lock); |
eeca6688d net_sched: red: s... |
221 |
red_adaptative_algo(&q->parms, &q->vars); |
8af2a218d sch_red: Adaptati... |
222 223 224 |
mod_timer(&q->adapt_timer, jiffies + HZ/2); spin_unlock(root_lock); } |
cc7ec456f net_sched: cleanups |
225 |
static int red_init(struct Qdisc *sch, struct nlattr *opt) |
1da177e4c Linux-2.6.12-rc2 |
226 |
{ |
f38c39d6c [PKT_SCHED]: Conv... |
227 228 229 |
struct red_sched_data *q = qdisc_priv(sch); q->qdisc = &noop_qdisc; |
8af2a218d sch_red: Adaptati... |
230 |
setup_timer(&q->adapt_timer, red_adaptative_timer, (unsigned long)sch); |
1da177e4c Linux-2.6.12-rc2 |
231 232 233 234 235 236 |
return red_change(sch, opt); } static int red_dump(struct Qdisc *sch, struct sk_buff *skb) { struct red_sched_data *q = qdisc_priv(sch); |
1e90474c3 [NET_SCHED]: Conv... |
237 |
struct nlattr *opts = NULL; |
6b31b28a4 [PKT_SCHED]: RED:... |
238 239 240 241 242 243 244 245 246 |
struct tc_red_qopt opt = { .limit = q->limit, .flags = q->flags, .qth_min = q->parms.qth_min >> q->parms.Wlog, .qth_max = q->parms.qth_max >> q->parms.Wlog, .Wlog = q->parms.Wlog, .Plog = q->parms.Plog, .Scell_log = q->parms.Scell_log, }; |
1da177e4c Linux-2.6.12-rc2 |
247 |
|
0dfb33a0d sch_red: report b... |
248 |
sch->qstats.backlog = q->qdisc->qstats.backlog; |
1e90474c3 [NET_SCHED]: Conv... |
249 250 251 252 |
opts = nla_nest_start(skb, TCA_OPTIONS); if (opts == NULL) goto nla_put_failure; NLA_PUT(skb, TCA_RED_PARMS, sizeof(opt), &opt); |
8af2a218d sch_red: Adaptati... |
253 |
NLA_PUT_U32(skb, TCA_RED_MAX_P, q->parms.max_P); |
1e90474c3 [NET_SCHED]: Conv... |
254 |
return nla_nest_end(skb, opts); |
1da177e4c Linux-2.6.12-rc2 |
255 |
|
1e90474c3 [NET_SCHED]: Conv... |
256 |
nla_put_failure: |
bc3ed28ca netlink: Improve ... |
257 258 |
nla_nest_cancel(skb, opts); return -EMSGSIZE; |
1da177e4c Linux-2.6.12-rc2 |
259 260 261 262 263 |
} static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d) { struct red_sched_data *q = qdisc_priv(sch); |
6b31b28a4 [PKT_SCHED]: RED:... |
264 265 266 267 268 269 270 271 |
struct tc_red_xstats st = { .early = q->stats.prob_drop + q->stats.forced_drop, .pdrop = q->stats.pdrop, .other = q->stats.other, .marked = q->stats.prob_mark + q->stats.forced_mark, }; return gnet_stats_copy_app(d, &st, sizeof(st)); |
1da177e4c Linux-2.6.12-rc2 |
272 |
} |
f38c39d6c [PKT_SCHED]: Conv... |
273 274 275 276 |
static int red_dump_class(struct Qdisc *sch, unsigned long cl, struct sk_buff *skb, struct tcmsg *tcm) { struct red_sched_data *q = qdisc_priv(sch); |
f38c39d6c [PKT_SCHED]: Conv... |
277 278 279 280 281 282 283 284 285 286 287 288 289 290 |
tcm->tcm_handle |= TC_H_MIN(1); tcm->tcm_info = q->qdisc->handle; return 0; } static int red_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new, struct Qdisc **old) { struct red_sched_data *q = qdisc_priv(sch); if (new == NULL) new = &noop_qdisc; sch_tree_lock(sch); |
b94c8afcb pkt_sched: remove... |
291 292 |
*old = q->qdisc; q->qdisc = new; |
5e50da01d [NET_SCHED]: Fix ... |
293 |
qdisc_tree_decrease_qlen(*old, (*old)->q.qlen); |
f38c39d6c [PKT_SCHED]: Conv... |
294 |
qdisc_reset(*old); |
f38c39d6c [PKT_SCHED]: Conv... |
295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 |
sch_tree_unlock(sch); return 0; } static struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg) { struct red_sched_data *q = qdisc_priv(sch); return q->qdisc; } static unsigned long red_get(struct Qdisc *sch, u32 classid) { return 1; } static void red_put(struct Qdisc *sch, unsigned long arg) { |
f38c39d6c [PKT_SCHED]: Conv... |
312 |
} |
f38c39d6c [PKT_SCHED]: Conv... |
313 314 315 316 317 318 319 320 321 322 323 |
static void red_walk(struct Qdisc *sch, struct qdisc_walker *walker) { if (!walker->stop) { if (walker->count >= walker->skip) if (walker->fn(sch, 1, walker) < 0) { walker->stop = 1; return; } walker->count++; } } |
20fea08b5 [NET]: Move Qdisc... |
324 |
static const struct Qdisc_class_ops red_class_ops = { |
f38c39d6c [PKT_SCHED]: Conv... |
325 326 327 328 |
.graft = red_graft, .leaf = red_leaf, .get = red_get, .put = red_put, |
f38c39d6c [PKT_SCHED]: Conv... |
329 |
.walk = red_walk, |
f38c39d6c [PKT_SCHED]: Conv... |
330 331 |
.dump = red_dump_class, }; |
20fea08b5 [NET]: Move Qdisc... |
332 |
static struct Qdisc_ops red_qdisc_ops __read_mostly = { |
1da177e4c Linux-2.6.12-rc2 |
333 334 |
.id = "red", .priv_size = sizeof(struct red_sched_data), |
f38c39d6c [PKT_SCHED]: Conv... |
335 |
.cl_ops = &red_class_ops, |
1da177e4c Linux-2.6.12-rc2 |
336 337 |
.enqueue = red_enqueue, .dequeue = red_dequeue, |
8e3af9789 pkt_sched: Add qd... |
338 |
.peek = red_peek, |
1da177e4c Linux-2.6.12-rc2 |
339 340 341 |
.drop = red_drop, .init = red_init, .reset = red_reset, |
f38c39d6c [PKT_SCHED]: Conv... |
342 |
.destroy = red_destroy, |
1da177e4c Linux-2.6.12-rc2 |
343 344 345 346 347 348 349 350 351 352 |
.change = red_change, .dump = red_dump, .dump_stats = red_dump_stats, .owner = THIS_MODULE, }; static int __init red_module_init(void) { return register_qdisc(&red_qdisc_ops); } |
dba051f36 [PKT_SCHED]: RED:... |
353 354 |
static void __exit red_module_exit(void) |
1da177e4c Linux-2.6.12-rc2 |
355 356 357 |
{ unregister_qdisc(&red_qdisc_ops); } |
dba051f36 [PKT_SCHED]: RED:... |
358 |
|
1da177e4c Linux-2.6.12-rc2 |
359 360 |
module_init(red_module_init) module_exit(red_module_exit) |
dba051f36 [PKT_SCHED]: RED:... |
361 |
|
1da177e4c Linux-2.6.12-rc2 |
362 |
MODULE_LICENSE("GPL"); |