aboutsummaryrefslogtreecommitdiffstats
path: root/net/sched/sch_sfq.c
diff options
context:
space:
mode:
Diffstat (limited to 'net/sched/sch_sfq.c')
-rw-r--r--net/sched/sch_sfq.c497
1 files changed, 497 insertions, 0 deletions
diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
new file mode 100644
index 000000000000..8734bb7280e3
--- /dev/null
+++ b/net/sched/sch_sfq.c
@@ -0,0 +1,497 @@
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/config.h>
13#include <linux/module.h>
14#include <asm/uaccess.h>
15#include <asm/system.h>
16#include <linux/bitops.h>
17#include <linux/types.h>
18#include <linux/kernel.h>
19#include <linux/jiffies.h>
20#include <linux/string.h>
21#include <linux/mm.h>
22#include <linux/socket.h>
23#include <linux/sockios.h>
24#include <linux/in.h>
25#include <linux/errno.h>
26#include <linux/interrupt.h>
27#include <linux/if_ether.h>
28#include <linux/inet.h>
29#include <linux/netdevice.h>
30#include <linux/etherdevice.h>
31#include <linux/notifier.h>
32#include <linux/init.h>
33#include <net/ip.h>
34#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
57 This is not the thing that is usually called (W)FQ nowadays.
58 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
67 - "Stochastic" -> It is not 100% fair.
68 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 {
141 struct iphdr *iph = skb->nh.iph;
142 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 ||
147 iph->protocol == IPPROTO_ESP))
148 h2 ^= *(((u32*)iph) + iph->ihl);
149 break;
150 }
151 case __constant_htons(ETH_P_IPV6):
152 {
153 struct ipv6hdr *iph = skb->nh.ipv6h;
154 h = iph->daddr.s6_addr32[3];
155 h2 = iph->saddr.s6_addr32[3]^iph->nexthdr;
156 if (iph->nexthdr == IPPROTO_TCP ||
157 iph->nexthdr == IPPROTO_UDP ||
158 iph->nexthdr == IPPROTO_ESP)
159 h2 ^= *(u32*)&iph[1];
160 break;
161 }
162 default:
163 h = (u32)(unsigned long)skb->dst^skb->protocol;
164 h2 = (u32)(unsigned long)skb->sk;
165 }
166 return sfq_fold_hash(q, h, h2);
167}
168
169static inline void sfq_link(struct sfq_sched_data *q, sfq_index x)
170{
171 sfq_index p, n;
172 int d = q->qs[x].qlen + SFQ_DEPTH;
173
174 p = d;
175 n = q->dep[d].next;
176 q->dep[x].next = n;
177 q->dep[x].prev = p;
178 q->dep[p].next = q->dep[n].prev = x;
179}
180
181static inline void sfq_dec(struct sfq_sched_data *q, sfq_index x)
182{
183 sfq_index p, n;
184
185 n = q->dep[x].next;
186 p = q->dep[x].prev;
187 q->dep[p].next = n;
188 q->dep[n].prev = p;
189
190 if (n == p && q->max_depth == q->qs[x].qlen + 1)
191 q->max_depth--;
192
193 sfq_link(q, x);
194}
195
196static inline void sfq_inc(struct sfq_sched_data *q, sfq_index x)
197{
198 sfq_index p, n;
199 int d;
200
201 n = q->dep[x].next;
202 p = q->dep[x].prev;
203 q->dep[p].next = n;
204 q->dep[n].prev = p;
205 d = q->qs[x].qlen;
206 if (q->max_depth < d)
207 q->max_depth = d;
208
209 sfq_link(q, x);
210}
211
212static unsigned int sfq_drop(struct Qdisc *sch)
213{
214 struct sfq_sched_data *q = qdisc_priv(sch);
215 sfq_index d = q->max_depth;
216 struct sk_buff *skb;
217 unsigned int len;
218
219 /* Queue is full! Find the longest slot and
220 drop a packet from it */
221
222 if (d > 1) {
223 sfq_index x = q->dep[d+SFQ_DEPTH].next;
224 skb = q->qs[x].prev;
225 len = skb->len;
226 __skb_unlink(skb, &q->qs[x]);
227 kfree_skb(skb);
228 sfq_dec(q, x);
229 sch->q.qlen--;
230 sch->qstats.drops++;
231 return len;
232 }
233
234 if (d == 1) {
235 /* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
236 d = q->next[q->tail];
237 q->next[q->tail] = q->next[d];
238 q->allot[q->next[d]] += q->quantum;
239 skb = q->qs[d].prev;
240 len = skb->len;
241 __skb_unlink(skb, &q->qs[d]);
242 kfree_skb(skb);
243 sfq_dec(q, d);
244 sch->q.qlen--;
245 q->ht[q->hash[d]] = SFQ_DEPTH;
246 sch->qstats.drops++;
247 return len;
248 }
249
250 return 0;
251}
252
253static int
254sfq_enqueue(struct sk_buff *skb, struct Qdisc* sch)
255{
256 struct sfq_sched_data *q = qdisc_priv(sch);
257 unsigned hash = sfq_hash(q, skb);
258 sfq_index x;
259
260 x = q->ht[hash];
261 if (x == SFQ_DEPTH) {
262 q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
263 q->hash[x] = hash;
264 }
265 __skb_queue_tail(&q->qs[x], skb);
266 sfq_inc(q, x);
267 if (q->qs[x].qlen == 1) { /* The flow is new */
268 if (q->tail == SFQ_DEPTH) { /* It is the first flow */
269 q->tail = x;
270 q->next[x] = x;
271 q->allot[x] = q->quantum;
272 } else {
273 q->next[x] = q->next[q->tail];
274 q->next[q->tail] = x;
275 q->tail = x;
276 }
277 }
278 if (++sch->q.qlen < q->limit-1) {
279 sch->bstats.bytes += skb->len;
280 sch->bstats.packets++;
281 return 0;
282 }
283
284 sfq_drop(sch);
285 return NET_XMIT_CN;
286}
287
288static int
289sfq_requeue(struct sk_buff *skb, struct Qdisc* sch)
290{
291 struct sfq_sched_data *q = qdisc_priv(sch);
292 unsigned hash = sfq_hash(q, skb);
293 sfq_index x;
294
295 x = q->ht[hash];
296 if (x == SFQ_DEPTH) {
297 q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
298 q->hash[x] = hash;
299 }
300 __skb_queue_head(&q->qs[x], skb);
301 sfq_inc(q, x);
302 if (q->qs[x].qlen == 1) { /* The flow is new */
303 if (q->tail == SFQ_DEPTH) { /* It is the first flow */
304 q->tail = x;
305 q->next[x] = x;
306 q->allot[x] = q->quantum;
307 } else {
308 q->next[x] = q->next[q->tail];
309 q->next[q->tail] = x;
310 q->tail = x;
311 }
312 }
313 if (++sch->q.qlen < q->limit - 1) {
314 sch->qstats.requeues++;
315 return 0;
316 }
317
318 sch->qstats.drops++;
319 sfq_drop(sch);
320 return NET_XMIT_CN;
321}
322
323
324
325
326static struct sk_buff *
327sfq_dequeue(struct Qdisc* sch)
328{
329 struct sfq_sched_data *q = qdisc_priv(sch);
330 struct sk_buff *skb;
331 sfq_index a, old_a;
332
333 /* No active slots */
334 if (q->tail == SFQ_DEPTH)
335 return NULL;
336
337 a = old_a = q->next[q->tail];
338
339 /* Grab packet */
340 skb = __skb_dequeue(&q->qs[a]);
341 sfq_dec(q, a);
342 sch->q.qlen--;
343
344 /* Is the slot empty? */
345 if (q->qs[a].qlen == 0) {
346 q->ht[q->hash[a]] = SFQ_DEPTH;
347 a = q->next[a];
348 if (a == old_a) {
349 q->tail = SFQ_DEPTH;
350 return skb;
351 }
352 q->next[q->tail] = a;
353 q->allot[a] += q->quantum;
354 } else if ((q->allot[a] -= skb->len) <= 0) {
355 q->tail = a;
356 a = q->next[a];
357 q->allot[a] += q->quantum;
358 }
359 return skb;
360}
361
362static void
363sfq_reset(struct Qdisc* sch)
364{
365 struct sk_buff *skb;
366
367 while ((skb = sfq_dequeue(sch)) != NULL)
368 kfree_skb(skb);
369}
370
371static void sfq_perturbation(unsigned long arg)
372{
373 struct Qdisc *sch = (struct Qdisc*)arg;
374 struct sfq_sched_data *q = qdisc_priv(sch);
375
376 q->perturbation = net_random()&0x1F;
377
378 if (q->perturb_period) {
379 q->perturb_timer.expires = jiffies + q->perturb_period;
380 add_timer(&q->perturb_timer);
381 }
382}
383
384static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
385{
386 struct sfq_sched_data *q = qdisc_priv(sch);
387 struct tc_sfq_qopt *ctl = RTA_DATA(opt);
388
389 if (opt->rta_len < RTA_LENGTH(sizeof(*ctl)))
390 return -EINVAL;
391
392 sch_tree_lock(sch);
393 q->quantum = ctl->quantum ? : psched_mtu(sch->dev);
394 q->perturb_period = ctl->perturb_period*HZ;
395 if (ctl->limit)
396 q->limit = min_t(u32, ctl->limit, SFQ_DEPTH);
397
398 while (sch->q.qlen >= q->limit-1)
399 sfq_drop(sch);
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
410static 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
442static void sfq_destroy(struct Qdisc *sch)
443{
444 struct sfq_sched_data *q = qdisc_priv(sch);
445 del_timer(&q->perturb_timer);
446}
447
448static 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;
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
465rtattr_failure:
466 skb_trim(skb, b - skb->data);
467 return -1;
468}
469
470static 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
487static int __init sfq_module_init(void)
488{
489 return register_qdisc(&sfq_qdisc_ops);
490}
491static void __exit sfq_module_exit(void)
492{
493 unregister_qdisc(&sfq_qdisc_ops);
494}
495module_init(sfq_module_init)
496module_exit(sfq_module_exit)
497MODULE_LICENSE("GPL");