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