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