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