xref: /linux/net/sched/sch_red.c (revision 14b42963f64b98ab61fa9723c03d71aa5ef4f862) 
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");
402