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/sched.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));
135 #define IPPROTO_ESP 50
138 static unsigned sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb)
142 switch (skb->protocol) {
143 case __constant_htons(ETH_P_IP):
145 struct iphdr *iph = skb->nh.iph;
147 h2 = iph->saddr^iph->protocol;
148 if (!(iph->frag_off&htons(IP_MF|IP_OFFSET)) &&
149 (iph->protocol == IPPROTO_TCP ||
150 iph->protocol == IPPROTO_UDP ||
151 iph->protocol == IPPROTO_ESP))
152 h2 ^= *(((u32*)iph) + iph->ihl);
155 case __constant_htons(ETH_P_IPV6):
157 struct ipv6hdr *iph = skb->nh.ipv6h;
158 h = iph->daddr.s6_addr32[3];
159 h2 = iph->saddr.s6_addr32[3]^iph->nexthdr;
160 if (iph->nexthdr == IPPROTO_TCP ||
161 iph->nexthdr == IPPROTO_UDP ||
162 iph->nexthdr == IPPROTO_ESP)
163 h2 ^= *(u32*)&iph[1];
167 h = (u32)(unsigned long)skb->dst^skb->protocol;
168 h2 = (u32)(unsigned long)skb->sk;
170 return sfq_fold_hash(q, h, h2);
173 extern __inline__ void sfq_link(struct sfq_sched_data *q, sfq_index x)
176 int d = q->qs[x].qlen + SFQ_DEPTH;
182 q->dep[p].next = q->dep[n].prev = x;
185 extern __inline__ void sfq_dec(struct sfq_sched_data *q, sfq_index x)
194 if (n == p && q->max_depth == q->qs[x].qlen + 1)
200 extern __inline__ void sfq_inc(struct sfq_sched_data *q, sfq_index x)
210 if (q->max_depth < d)
216 static int sfq_drop(struct Qdisc *sch)
218 struct sfq_sched_data *q = (struct sfq_sched_data *)sch->data;
219 sfq_index d = q->max_depth;
222 /* Queue is full! Find the longest slot and
223 drop a packet from it */
226 sfq_index x = q->dep[d+SFQ_DEPTH].next;
228 __skb_unlink(skb, &q->qs[x]);
237 /* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
238 d = q->next[q->tail];
239 q->next[q->tail] = q->next[d];
240 q->allot[q->next[d]] += q->quantum;
242 __skb_unlink(skb, &q->qs[d]);
246 q->ht[q->hash[d]] = SFQ_DEPTH;
255 sfq_enqueue(struct sk_buff *skb, struct Qdisc* sch)
257 struct sfq_sched_data *q = (struct sfq_sched_data *)sch->data;
258 unsigned hash = sfq_hash(q, skb);
262 if (x == SFQ_DEPTH) {
263 q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
266 __skb_queue_tail(&q->qs[x], skb);
268 if (q->qs[x].qlen == 1) { /* The flow is new */
269 if (q->tail == SFQ_DEPTH) { /* It is the first flow */
272 q->allot[x] = q->quantum;
274 q->next[x] = q->next[q->tail];
275 q->next[q->tail] = x;
279 if (++sch->q.qlen < q->limit-1) {
280 sch->stats.bytes += skb->len;
281 sch->stats.packets++;
290 sfq_requeue(struct sk_buff *skb, struct Qdisc* sch)
292 struct sfq_sched_data *q = (struct sfq_sched_data *)sch->data;
293 unsigned hash = sfq_hash(q, skb);
297 if (x == SFQ_DEPTH) {
298 q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
301 __skb_queue_head(&q->qs[x], skb);
303 if (q->qs[x].qlen == 1) { /* The flow is new */
304 if (q->tail == SFQ_DEPTH) { /* It is the first flow */
307 q->allot[x] = q->quantum;
309 q->next[x] = q->next[q->tail];
310 q->next[q->tail] = x;
314 if (++sch->q.qlen < q->limit - 1)
325 static struct sk_buff *
326 sfq_dequeue(struct Qdisc* sch)
328 struct sfq_sched_data *q = (struct sfq_sched_data *)sch->data;
332 /* No active slots */
333 if (q->tail == SFQ_DEPTH)
336 a = old_a = q->next[q->tail];
339 skb = __skb_dequeue(&q->qs[a]);
343 /* Is the slot empty? */
344 if (q->qs[a].qlen == 0) {
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 = (struct sfq_sched_data *)sch->data;
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 = (struct sfq_sched_data *)sch->data;
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 = (struct sfq_sched_data *)sch->data;
414 q->perturb_timer.data = (unsigned long)sch;
415 q->perturb_timer.function = sfq_perturbation;
416 init_timer(&q->perturb_timer);
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++)
442 static void sfq_destroy(struct Qdisc *sch)
444 struct sfq_sched_data *q = (struct sfq_sched_data *)sch->data;
445 del_timer(&q->perturb_timer);
449 static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
451 struct sfq_sched_data *q = (struct sfq_sched_data *)sch->data;
452 unsigned char *b = skb->tail;
453 struct tc_sfq_qopt opt;
455 opt.quantum = q->quantum;
456 opt.perturb_period = q->perturb_period/HZ;
458 opt.limit = q->limit;
459 opt.divisor = SFQ_HASH_DIVISOR;
460 opt.flows = q->limit;
462 RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
467 skb_trim(skb, b - skb->data);
471 struct Qdisc_ops sfq_qdisc_ops =
476 sizeof(struct sfq_sched_data),
486 NULL, /* sfq_change */
492 int init_module(void)
494 return register_qdisc(&sfq_qdisc_ops);
497 void cleanup_module(void)
499 unregister_qdisc(&sfq_qdisc_ops);
502 MODULE_LICENSE("GPL");