xref: /openbmc/linux/net/sched/sch_sfq.c (revision c21b37f6) 
1 /*
2  * net/sched/sch_sfq.c	Stochastic Fairness Queueing discipline.
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 
12 #include <linux/module.h>
13 #include <linux/types.h>
14 #include <linux/kernel.h>
15 #include <linux/jiffies.h>
16 #include <linux/string.h>
17 #include <linux/in.h>
18 #include <linux/errno.h>
19 #include <linux/init.h>
20 #include <linux/ipv6.h>
21 #include <linux/skbuff.h>
22 #include <net/ip.h>
23 #include <net/netlink.h>
24 #include <net/pkt_sched.h>
25 
26 
27 /*	Stochastic Fairness Queuing algorithm.
28 	=======================================
29 
30 	Source:
31 	Paul E. McKenney "Stochastic Fairness Queuing",
32 	IEEE INFOCOMM'90 Proceedings, San Francisco, 1990.
33 
34 	Paul E. McKenney "Stochastic Fairness Queuing",
35 	"Interworking: Research and Experience", v.2, 1991, p.113-131.
36 
37 
38 	See also:
39 	M. Shreedhar and George Varghese "Efficient Fair
40 	Queuing using Deficit Round Robin", Proc. SIGCOMM 95.
41 
42 
43 	This is not the thing that is usually called (W)FQ nowadays.
44 	It does not use any timestamp mechanism, but instead
45 	processes queues in round-robin order.
46 
47 	ADVANTAGE:
48 
49 	- It is very cheap. Both CPU and memory requirements are minimal.
50 
51 	DRAWBACKS:
52 
53 	- "Stochastic" -> It is not 100% fair.
54 	When hash collisions occur, several flows are considered as one.
55 
56 	- "Round-robin" -> It introduces larger delays than virtual clock
57 	based schemes, and should not be used for isolating interactive
58 	traffic	from non-interactive. It means, that this scheduler
59 	should be used as leaf of CBQ or P3, which put interactive traffic
60 	to higher priority band.
61 
62 	We still need true WFQ for top level CSZ, but using WFQ
63 	for the best effort traffic is absolutely pointless:
64 	SFQ is superior for this purpose.
65 
66 	IMPLEMENTATION:
67 	This implementation limits maximal queue length to 128;
68 	maximal mtu to 2^15-1; number of hash buckets to 1024.
69 	The only goal of this restrictions was that all data
70 	fit into one 4K page :-). Struct sfq_sched_data is
71 	organized in anti-cache manner: all the data for a bucket
72 	are scattered over different locations. This is not good,
73 	but it allowed me to put it into 4K.
74 
75 	It is easy to increase these values, but not in flight.  */
76 
77 #define SFQ_DEPTH		128
78 #define SFQ_HASH_DIVISOR	1024
79 
80 /* This type should contain at least SFQ_DEPTH*2 values */
81 typedef unsigned char sfq_index;
82 
83 struct sfq_head
84 {
85 	sfq_index	next;
86 	sfq_index	prev;
87 };
88 
89 struct sfq_sched_data
90 {
91 /* Parameters */
92 	int		perturb_period;
93 	unsigned	quantum;	/* Allotment per round: MUST BE >= MTU */
94 	int		limit;
95 
96 /* Variables */
97 	struct timer_list perturb_timer;
98 	int		perturbation;
99 	sfq_index	tail;		/* Index of current slot in round */
100 	sfq_index	max_depth;	/* Maximal depth */
101 
102 	sfq_index	ht[SFQ_HASH_DIVISOR];	/* Hash table */
103 	sfq_index	next[SFQ_DEPTH];	/* Active slots link */
104 	short		allot[SFQ_DEPTH];	/* Current allotment per slot */
105 	unsigned short	hash[SFQ_DEPTH];	/* Hash value indexed by slots */
106 	struct sk_buff_head	qs[SFQ_DEPTH];		/* Slot queue */
107 	struct sfq_head	dep[SFQ_DEPTH*2];	/* Linked list of slots, indexed by depth */
108 };
109 
110 static __inline__ unsigned sfq_fold_hash(struct sfq_sched_data *q, u32 h, u32 h1)
111 {
112 	int pert = q->perturbation;
113 
114 	/* Have we any rotation primitives? If not, WHY? */
115 	h ^= (h1<<pert) ^ (h1>>(0x1F - pert));
116 	h ^= h>>10;
117 	return h & 0x3FF;
118 }
119 
120 static unsigned sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb)
121 {
122 	u32 h, h2;
123 
124 	switch (skb->protocol) {
125 	case __constant_htons(ETH_P_IP):
126 	{
127 		const struct iphdr *iph = ip_hdr(skb);
128 		h = iph->daddr;
129 		h2 = iph->saddr^iph->protocol;
130 		if (!(iph->frag_off&htons(IP_MF|IP_OFFSET)) &&
131 		    (iph->protocol == IPPROTO_TCP ||
132 		     iph->protocol == IPPROTO_UDP ||
133 		     iph->protocol == IPPROTO_UDPLITE ||
134 		     iph->protocol == IPPROTO_SCTP ||
135 		     iph->protocol == IPPROTO_DCCP ||
136 		     iph->protocol == IPPROTO_ESP))
137 			h2 ^= *(((u32*)iph) + iph->ihl);
138 		break;
139 	}
140 	case __constant_htons(ETH_P_IPV6):
141 	{
142 		struct ipv6hdr *iph = ipv6_hdr(skb);
143 		h = iph->daddr.s6_addr32[3];
144 		h2 = iph->saddr.s6_addr32[3]^iph->nexthdr;
145 		if (iph->nexthdr == IPPROTO_TCP ||
146 		    iph->nexthdr == IPPROTO_UDP ||
147 		    iph->nexthdr == IPPROTO_UDPLITE ||
148 		    iph->nexthdr == IPPROTO_SCTP ||
149 		    iph->nexthdr == IPPROTO_DCCP ||
150 		    iph->nexthdr == IPPROTO_ESP)
151 			h2 ^= *(u32*)&iph[1];
152 		break;
153 	}
154 	default:
155 		h = (u32)(unsigned long)skb->dst^skb->protocol;
156 		h2 = (u32)(unsigned long)skb->sk;
157 	}
158 	return sfq_fold_hash(q, h, h2);
159 }
160 
161 static inline void sfq_link(struct sfq_sched_data *q, sfq_index x)
162 {
163 	sfq_index p, n;
164 	int d = q->qs[x].qlen + SFQ_DEPTH;
165 
166 	p = d;
167 	n = q->dep[d].next;
168 	q->dep[x].next = n;
169 	q->dep[x].prev = p;
170 	q->dep[p].next = q->dep[n].prev = x;
171 }
172 
173 static inline void sfq_dec(struct sfq_sched_data *q, sfq_index x)
174 {
175 	sfq_index p, n;
176 
177 	n = q->dep[x].next;
178 	p = q->dep[x].prev;
179 	q->dep[p].next = n;
180 	q->dep[n].prev = p;
181 
182 	if (n == p && q->max_depth == q->qs[x].qlen + 1)
183 		q->max_depth--;
184 
185 	sfq_link(q, x);
186 }
187 
188 static inline void sfq_inc(struct sfq_sched_data *q, sfq_index x)
189 {
190 	sfq_index p, n;
191 	int d;
192 
193 	n = q->dep[x].next;
194 	p = q->dep[x].prev;
195 	q->dep[p].next = n;
196 	q->dep[n].prev = p;
197 	d = q->qs[x].qlen;
198 	if (q->max_depth < d)
199 		q->max_depth = d;
200 
201 	sfq_link(q, x);
202 }
203 
204 static unsigned int sfq_drop(struct Qdisc *sch)
205 {
206 	struct sfq_sched_data *q = qdisc_priv(sch);
207 	sfq_index d = q->max_depth;
208 	struct sk_buff *skb;
209 	unsigned int len;
210 
211 	/* Queue is full! Find the longest slot and
212 	   drop a packet from it */
213 
214 	if (d > 1) {
215 		sfq_index x = q->dep[d+SFQ_DEPTH].next;
216 		skb = q->qs[x].prev;
217 		len = skb->len;
218 		__skb_unlink(skb, &q->qs[x]);
219 		kfree_skb(skb);
220 		sfq_dec(q, x);
221 		sch->q.qlen--;
222 		sch->qstats.drops++;
223 		sch->qstats.backlog -= len;
224 		return len;
225 	}
226 
227 	if (d == 1) {
228 		/* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
229 		d = q->next[q->tail];
230 		q->next[q->tail] = q->next[d];
231 		q->allot[q->next[d]] += q->quantum;
232 		skb = q->qs[d].prev;
233 		len = skb->len;
234 		__skb_unlink(skb, &q->qs[d]);
235 		kfree_skb(skb);
236 		sfq_dec(q, d);
237 		sch->q.qlen--;
238 		q->ht[q->hash[d]] = SFQ_DEPTH;
239 		sch->qstats.drops++;
240 		sch->qstats.backlog -= len;
241 		return len;
242 	}
243 
244 	return 0;
245 }
246 
247 static int
248 sfq_enqueue(struct sk_buff *skb, struct Qdisc* sch)
249 {
250 	struct sfq_sched_data *q = qdisc_priv(sch);
251 	unsigned hash = sfq_hash(q, skb);
252 	sfq_index x;
253 
254 	x = q->ht[hash];
255 	if (x == SFQ_DEPTH) {
256 		q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
257 		q->hash[x] = hash;
258 	}
259 	sch->qstats.backlog += skb->len;
260 	__skb_queue_tail(&q->qs[x], skb);
261 	sfq_inc(q, x);
262 	if (q->qs[x].qlen == 1) {		/* The flow is new */
263 		if (q->tail == SFQ_DEPTH) {	/* It is the first flow */
264 			q->tail = x;
265 			q->next[x] = x;
266 			q->allot[x] = q->quantum;
267 		} else {
268 			q->next[x] = q->next[q->tail];
269 			q->next[q->tail] = x;
270 			q->tail = x;
271 		}
272 	}
273 	if (++sch->q.qlen < q->limit-1) {
274 		sch->bstats.bytes += skb->len;
275 		sch->bstats.packets++;
276 		return 0;
277 	}
278 
279 	sfq_drop(sch);
280 	return NET_XMIT_CN;
281 }
282 
283 static int
284 sfq_requeue(struct sk_buff *skb, struct Qdisc* sch)
285 {
286 	struct sfq_sched_data *q = qdisc_priv(sch);
287 	unsigned hash = sfq_hash(q, skb);
288 	sfq_index x;
289 
290 	x = q->ht[hash];
291 	if (x == SFQ_DEPTH) {
292 		q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
293 		q->hash[x] = hash;
294 	}
295 	sch->qstats.backlog += skb->len;
296 	__skb_queue_head(&q->qs[x], skb);
297 	sfq_inc(q, x);
298 	if (q->qs[x].qlen == 1) {		/* The flow is new */
299 		if (q->tail == SFQ_DEPTH) {	/* It is the first flow */
300 			q->tail = x;
301 			q->next[x] = x;
302 			q->allot[x] = q->quantum;
303 		} else {
304 			q->next[x] = q->next[q->tail];
305 			q->next[q->tail] = x;
306 			q->tail = x;
307 		}
308 	}
309 	if (++sch->q.qlen < q->limit - 1) {
310 		sch->qstats.requeues++;
311 		return 0;
312 	}
313 
314 	sch->qstats.drops++;
315 	sfq_drop(sch);
316 	return NET_XMIT_CN;
317 }
318 
319 
320 
321 
322 static struct sk_buff *
323 sfq_dequeue(struct Qdisc* sch)
324 {
325 	struct sfq_sched_data *q = qdisc_priv(sch);
326 	struct sk_buff *skb;
327 	sfq_index a, old_a;
328 
329 	/* No active slots */
330 	if (q->tail == SFQ_DEPTH)
331 		return NULL;
332 
333 	a = old_a = q->next[q->tail];
334 
335 	/* Grab packet */
336 	skb = __skb_dequeue(&q->qs[a]);
337 	sfq_dec(q, a);
338 	sch->q.qlen--;
339 	sch->qstats.backlog -= skb->len;
340 
341 	/* Is the slot empty? */
342 	if (q->qs[a].qlen == 0) {
343 		q->ht[q->hash[a]] = SFQ_DEPTH;
344 		a = q->next[a];
345 		if (a == old_a) {
346 			q->tail = SFQ_DEPTH;
347 			return skb;
348 		}
349 		q->next[q->tail] = a;
350 		q->allot[a] += q->quantum;
351 	} else if ((q->allot[a] -= skb->len) <= 0) {
352 		q->tail = a;
353 		a = q->next[a];
354 		q->allot[a] += q->quantum;
355 	}
356 	return skb;
357 }
358 
359 static void
360 sfq_reset(struct Qdisc* sch)
361 {
362 	struct sk_buff *skb;
363 
364 	while ((skb = sfq_dequeue(sch)) != NULL)
365 		kfree_skb(skb);
366 }
367 
368 static void sfq_perturbation(unsigned long arg)
369 {
370 	struct Qdisc *sch = (struct Qdisc*)arg;
371 	struct sfq_sched_data *q = qdisc_priv(sch);
372 
373 	q->perturbation = net_random()&0x1F;
374 
375 	if (q->perturb_period) {
376 		q->perturb_timer.expires = jiffies + q->perturb_period;
377 		add_timer(&q->perturb_timer);
378 	}
379 }
380 
381 static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
382 {
383 	struct sfq_sched_data *q = qdisc_priv(sch);
384 	struct tc_sfq_qopt *ctl = RTA_DATA(opt);
385 	unsigned int qlen;
386 
387 	if (opt->rta_len < RTA_LENGTH(sizeof(*ctl)))
388 		return -EINVAL;
389 
390 	sch_tree_lock(sch);
391 	q->quantum = ctl->quantum ? : psched_mtu(sch->dev);
392 	q->perturb_period = ctl->perturb_period*HZ;
393 	if (ctl->limit)
394 		q->limit = min_t(u32, ctl->limit, SFQ_DEPTH);
395 
396 	qlen = sch->q.qlen;
397 	while (sch->q.qlen >= q->limit-1)
398 		sfq_drop(sch);
399 	qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen);
400 
401 	del_timer(&q->perturb_timer);
402 	if (q->perturb_period) {
403 		q->perturb_timer.expires = jiffies + q->perturb_period;
404 		add_timer(&q->perturb_timer);
405 	}
406 	sch_tree_unlock(sch);
407 	return 0;
408 }
409 
410 static int sfq_init(struct Qdisc *sch, struct rtattr *opt)
411 {
412 	struct sfq_sched_data *q = qdisc_priv(sch);
413 	int i;
414 
415 	init_timer(&q->perturb_timer);
416 	q->perturb_timer.data = (unsigned long)sch;
417 	q->perturb_timer.function = sfq_perturbation;
418 
419 	for (i=0; i<SFQ_HASH_DIVISOR; i++)
420 		q->ht[i] = SFQ_DEPTH;
421 	for (i=0; i<SFQ_DEPTH; i++) {
422 		skb_queue_head_init(&q->qs[i]);
423 		q->dep[i+SFQ_DEPTH].next = i+SFQ_DEPTH;
424 		q->dep[i+SFQ_DEPTH].prev = i+SFQ_DEPTH;
425 	}
426 	q->limit = SFQ_DEPTH;
427 	q->max_depth = 0;
428 	q->tail = SFQ_DEPTH;
429 	if (opt == NULL) {
430 		q->quantum = psched_mtu(sch->dev);
431 		q->perturb_period = 0;
432 	} else {
433 		int err = sfq_change(sch, opt);
434 		if (err)
435 			return err;
436 	}
437 	for (i=0; i<SFQ_DEPTH; i++)
438 		sfq_link(q, i);
439 	return 0;
440 }
441 
442 static void sfq_destroy(struct Qdisc *sch)
443 {
444 	struct sfq_sched_data *q = qdisc_priv(sch);
445 	del_timer(&q->perturb_timer);
446 }
447 
448 static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
449 {
450 	struct sfq_sched_data *q = qdisc_priv(sch);
451 	unsigned char *b = skb_tail_pointer(skb);
452 	struct tc_sfq_qopt opt;
453 
454 	opt.quantum = q->quantum;
455 	opt.perturb_period = q->perturb_period/HZ;
456 
457 	opt.limit = q->limit;
458 	opt.divisor = SFQ_HASH_DIVISOR;
459 	opt.flows = q->limit;
460 
461 	RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
462 
463 	return skb->len;
464 
465 rtattr_failure:
466 	nlmsg_trim(skb, b);
467 	return -1;
468 }
469 
470 static struct Qdisc_ops sfq_qdisc_ops = {
471 	.next		=	NULL,
472 	.cl_ops		=	NULL,
473 	.id		=	"sfq",
474 	.priv_size	=	sizeof(struct sfq_sched_data),
475 	.enqueue	=	sfq_enqueue,
476 	.dequeue	=	sfq_dequeue,
477 	.requeue	=	sfq_requeue,
478 	.drop		=	sfq_drop,
479 	.init		=	sfq_init,
480 	.reset		=	sfq_reset,
481 	.destroy	=	sfq_destroy,
482 	.change		=	NULL,
483 	.dump		=	sfq_dump,
484 	.owner		=	THIS_MODULE,
485 };
486 
487 static int __init sfq_module_init(void)
488 {
489 	return register_qdisc(&sfq_qdisc_ops);
490 }
491 static void __exit sfq_module_exit(void)
492 {
493 	unregister_qdisc(&sfq_qdisc_ops);
494 }
495 module_init(sfq_module_init)
496 module_exit(sfq_module_exit)
497 MODULE_LICENSE("GPL");
498