2 * net/sched/sch_sfq.c Stochastic Fairness Queueing discipline.
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.
9 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
12 #include <linux/config.h>
13 #include <linux/module.h>
14 #include <asm/uaccess.h>
15 #include <asm/system.h>
16 #include <asm/bitops.h>
17 #include <linux/types.h>
18 #include <linux/kernel.h>
19 #include <linux/jiffies.h>
20 #include <linux/string.h>
22 #include <linux/socket.h>
23 #include <linux/sockios.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>
34 #include <linux/ipv6.h>
35 #include <net/route.h>
36 #include <linux/skbuff.h>
38 #include <net/pkt_sched.h>
41 /* Stochastic Fairness Queuing algorithm.
42 =======================================
45 Paul E. McKenney "Stochastic Fairness Queuing",
46 IEEE INFOCOMM'90 Proceedings, San Francisco, 1990.
48 Paul E. McKenney "Stochastic Fairness Queuing",
49 "Interworking: Research and Experience", v.2, 1991, p.113-131.
53 M. Shreedhar and George Varghese "Efficient Fair
54 Queuing using Deficit Round Robin", Proc. SIGCOMM 95.
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.
63 - It is very cheap. Both CPU and memory requirements are minimal.
67 - "Stochastic" -> It is not 100% fair.
68 When hash collisions occur, several flows are considered as one.
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.
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.
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.
89 It is easy to increase these values, but not in flight. */
92 #define SFQ_HASH_DIVISOR 1024
94 /* This type should contain at least SFQ_DEPTH*2 values */
95 typedef unsigned char sfq_index;
103 struct sfq_sched_data
107 unsigned quantum; /* Allotment per round: MUST BE >= MTU */
111 struct timer_list perturb_timer;
113 sfq_index tail; /* Index of current slot in round */
114 sfq_index max_depth; /* Maximal depth */
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 */
124 static __inline__ unsigned sfq_fold_hash(struct sfq_sched_data *q, u32 h, u32 h1)
126 int pert = q->perturbation;
128 /* Have we any rotation primitives? If not, WHY? */
129 h ^= (h1<<pert) ^ (h1>>(0x1F - pert));
134 static unsigned sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb)
138 switch (skb->protocol) {
139 case __constant_htons(ETH_P_IP):
141 struct iphdr *iph = skb->nh.iph;
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);
151 case __constant_htons(ETH_P_IPV6):
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];
163 h = (u32)(unsigned long)skb->dst^skb->protocol;
164 h2 = (u32)(unsigned long)skb->sk;
166 return sfq_fold_hash(q, h, h2);
169 static inline void sfq_link(struct sfq_sched_data *q, sfq_index x)
172 int d = q->qs[x].qlen + SFQ_DEPTH;
178 q->dep[p].next = q->dep[n].prev = x;
181 static inline void sfq_dec(struct sfq_sched_data *q, sfq_index x)
190 if (n == p && q->max_depth == q->qs[x].qlen + 1)
196 static inline void sfq_inc(struct sfq_sched_data *q, sfq_index x)
206 if (q->max_depth < d)
212 static unsigned int sfq_drop(struct Qdisc *sch)
214 struct sfq_sched_data *q = qdisc_priv(sch);
215 sfq_index d = q->max_depth;
219 /* Queue is full! Find the longest slot and
220 drop a packet from it */
223 sfq_index x = q->dep[d+SFQ_DEPTH].next;
226 __skb_unlink(skb, &q->qs[x]);
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;
241 __skb_unlink(skb, &q->qs[d]);
245 q->ht[q->hash[d]] = SFQ_DEPTH;
254 sfq_enqueue(struct sk_buff *skb, struct Qdisc* sch)
256 struct sfq_sched_data *q = qdisc_priv(sch);
257 unsigned hash = sfq_hash(q, skb);
261 if (x == SFQ_DEPTH) {
262 q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
265 __skb_queue_tail(&q->qs[x], skb);
267 if (q->qs[x].qlen == 1) { /* The flow is new */
268 if (q->tail == SFQ_DEPTH) { /* It is the first flow */
271 q->allot[x] = q->quantum;
273 q->next[x] = q->next[q->tail];
274 q->next[q->tail] = x;
278 if (++sch->q.qlen < q->limit-1) {
279 sch->stats.bytes += skb->len;
280 sch->stats.packets++;
289 sfq_requeue(struct sk_buff *skb, struct Qdisc* sch)
291 struct sfq_sched_data *q = qdisc_priv(sch);
292 unsigned hash = sfq_hash(q, skb);
296 if (x == SFQ_DEPTH) {
297 q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
300 __skb_queue_head(&q->qs[x], skb);
302 if (q->qs[x].qlen == 1) { /* The flow is new */
303 if (q->tail == SFQ_DEPTH) { /* It is the first flow */
306 q->allot[x] = q->quantum;
308 q->next[x] = q->next[q->tail];
309 q->next[q->tail] = x;
313 if (++sch->q.qlen < q->limit - 1)
324 static struct sk_buff *
325 sfq_dequeue(struct Qdisc* sch)
327 struct sfq_sched_data *q = qdisc_priv(sch);
331 /* No active slots */
332 if (q->tail == SFQ_DEPTH)
335 a = old_a = q->next[q->tail];
338 skb = __skb_dequeue(&q->qs[a]);
342 /* Is the slot empty? */
343 if (q->qs[a].qlen == 0) {
344 q->ht[q->hash[a]] = SFQ_DEPTH;
350 q->next[q->tail] = a;
351 q->allot[a] += q->quantum;
352 } else if ((q->allot[a] -= skb->len) <= 0) {
355 q->allot[a] += q->quantum;
361 sfq_reset(struct Qdisc* sch)
365 while ((skb = sfq_dequeue(sch)) != NULL)
369 static void sfq_perturbation(unsigned long arg)
371 struct Qdisc *sch = (struct Qdisc*)arg;
372 struct sfq_sched_data *q = qdisc_priv(sch);
374 q->perturbation = net_random()&0x1F;
375 q->perturb_timer.expires = jiffies + q->perturb_period;
377 if (q->perturb_period) {
378 q->perturb_timer.expires = jiffies + q->perturb_period;
379 add_timer(&q->perturb_timer);
383 static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
385 struct sfq_sched_data *q = qdisc_priv(sch);
386 struct tc_sfq_qopt *ctl = RTA_DATA(opt);
388 if (opt->rta_len < RTA_LENGTH(sizeof(*ctl)))
392 q->quantum = ctl->quantum ? : psched_mtu(sch->dev);
393 q->perturb_period = ctl->perturb_period*HZ;
395 q->limit = min_t(u32, ctl->limit, SFQ_DEPTH);
397 while (sch->q.qlen >= q->limit-1)
400 del_timer(&q->perturb_timer);
401 if (q->perturb_period) {
402 q->perturb_timer.expires = jiffies + q->perturb_period;
403 add_timer(&q->perturb_timer);
405 sch_tree_unlock(sch);
409 static int sfq_init(struct Qdisc *sch, struct rtattr *opt)
411 struct sfq_sched_data *q = qdisc_priv(sch);
414 init_timer(&q->perturb_timer);
415 q->perturb_timer.data = (unsigned long)sch;
416 q->perturb_timer.function = sfq_perturbation;
418 for (i=0; i<SFQ_HASH_DIVISOR; i++)
419 q->ht[i] = SFQ_DEPTH;
420 for (i=0; i<SFQ_DEPTH; i++) {
421 skb_queue_head_init(&q->qs[i]);
422 q->dep[i+SFQ_DEPTH].next = i+SFQ_DEPTH;
423 q->dep[i+SFQ_DEPTH].prev = i+SFQ_DEPTH;
425 q->limit = SFQ_DEPTH;
429 q->quantum = psched_mtu(sch->dev);
430 q->perturb_period = 0;
432 int err = sfq_change(sch, opt);
436 for (i=0; i<SFQ_DEPTH; i++)
441 static void sfq_destroy(struct Qdisc *sch)
443 struct sfq_sched_data *q = qdisc_priv(sch);
444 del_timer(&q->perturb_timer);
447 static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
449 struct sfq_sched_data *q = qdisc_priv(sch);
450 unsigned char *b = skb->tail;
451 struct tc_sfq_qopt opt;
453 opt.quantum = q->quantum;
454 opt.perturb_period = q->perturb_period/HZ;
456 opt.limit = q->limit;
457 opt.divisor = SFQ_HASH_DIVISOR;
458 opt.flows = q->limit;
460 RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
465 skb_trim(skb, b - skb->data);
469 static struct Qdisc_ops sfq_qdisc_ops = {
473 .priv_size = sizeof(struct sfq_sched_data),
474 .enqueue = sfq_enqueue,
475 .dequeue = sfq_dequeue,
476 .requeue = sfq_requeue,
480 .destroy = sfq_destroy,
483 .owner = THIS_MODULE,
486 static int __init sfq_module_init(void)
488 return register_qdisc(&sfq_qdisc_ops);
490 static void __exit sfq_module_exit(void)
492 unregister_qdisc(&sfq_qdisc_ops);
494 module_init(sfq_module_init)
495 module_exit(sfq_module_exit)
496 MODULE_LICENSE("GPL");