Merge branch 'mv-merge'
[linux-2.6] / net / sched / sch_sfq.c
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 */
95 typedef unsigned char sfq_index;
96
97 struct sfq_head
98 {
99         sfq_index       next;
100         sfq_index       prev;
101 };
102
103 struct 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
124 static __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
134 static 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_SCTP ||
148                      iph->protocol == IPPROTO_DCCP ||
149                      iph->protocol == IPPROTO_ESP))
150                         h2 ^= *(((u32*)iph) + iph->ihl);
151                 break;
152         }
153         case __constant_htons(ETH_P_IPV6):
154         {
155                 struct ipv6hdr *iph = skb->nh.ipv6h;
156                 h = iph->daddr.s6_addr32[3];
157                 h2 = iph->saddr.s6_addr32[3]^iph->nexthdr;
158                 if (iph->nexthdr == IPPROTO_TCP ||
159                     iph->nexthdr == IPPROTO_UDP ||
160                     iph->nexthdr == IPPROTO_SCTP ||
161                     iph->nexthdr == IPPROTO_DCCP ||
162                     iph->nexthdr == IPPROTO_ESP)
163                         h2 ^= *(u32*)&iph[1];
164                 break;
165         }
166         default:
167                 h = (u32)(unsigned long)skb->dst^skb->protocol;
168                 h2 = (u32)(unsigned long)skb->sk;
169         }
170         return sfq_fold_hash(q, h, h2);
171 }
172
173 static inline void sfq_link(struct sfq_sched_data *q, sfq_index x)
174 {
175         sfq_index p, n;
176         int d = q->qs[x].qlen + SFQ_DEPTH;
177
178         p = d;
179         n = q->dep[d].next;
180         q->dep[x].next = n;
181         q->dep[x].prev = p;
182         q->dep[p].next = q->dep[n].prev = x;
183 }
184
185 static inline void sfq_dec(struct sfq_sched_data *q, sfq_index x)
186 {
187         sfq_index p, n;
188
189         n = q->dep[x].next;
190         p = q->dep[x].prev;
191         q->dep[p].next = n;
192         q->dep[n].prev = p;
193
194         if (n == p && q->max_depth == q->qs[x].qlen + 1)
195                 q->max_depth--;
196
197         sfq_link(q, x);
198 }
199
200 static inline void sfq_inc(struct sfq_sched_data *q, sfq_index x)
201 {
202         sfq_index p, n;
203         int d;
204
205         n = q->dep[x].next;
206         p = q->dep[x].prev;
207         q->dep[p].next = n;
208         q->dep[n].prev = p;
209         d = q->qs[x].qlen;
210         if (q->max_depth < d)
211                 q->max_depth = d;
212
213         sfq_link(q, x);
214 }
215
216 static unsigned int sfq_drop(struct Qdisc *sch)
217 {
218         struct sfq_sched_data *q = qdisc_priv(sch);
219         sfq_index d = q->max_depth;
220         struct sk_buff *skb;
221         unsigned int len;
222
223         /* Queue is full! Find the longest slot and
224            drop a packet from it */
225
226         if (d > 1) {
227                 sfq_index x = q->dep[d+SFQ_DEPTH].next;
228                 skb = q->qs[x].prev;
229                 len = skb->len;
230                 __skb_unlink(skb, &q->qs[x]);
231                 kfree_skb(skb);
232                 sfq_dec(q, x);
233                 sch->q.qlen--;
234                 sch->qstats.drops++;
235                 sch->qstats.backlog -= len;
236                 return len;
237         }
238
239         if (d == 1) {
240                 /* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
241                 d = q->next[q->tail];
242                 q->next[q->tail] = q->next[d];
243                 q->allot[q->next[d]] += q->quantum;
244                 skb = q->qs[d].prev;
245                 len = skb->len;
246                 __skb_unlink(skb, &q->qs[d]);
247                 kfree_skb(skb);
248                 sfq_dec(q, d);
249                 sch->q.qlen--;
250                 q->ht[q->hash[d]] = SFQ_DEPTH;
251                 sch->qstats.drops++;
252                 sch->qstats.backlog -= len;
253                 return len;
254         }
255
256         return 0;
257 }
258
259 static int
260 sfq_enqueue(struct sk_buff *skb, struct Qdisc* sch)
261 {
262         struct sfq_sched_data *q = qdisc_priv(sch);
263         unsigned hash = sfq_hash(q, skb);
264         sfq_index x;
265
266         x = q->ht[hash];
267         if (x == SFQ_DEPTH) {
268                 q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
269                 q->hash[x] = hash;
270         }
271         sch->qstats.backlog += skb->len;
272         __skb_queue_tail(&q->qs[x], skb);
273         sfq_inc(q, x);
274         if (q->qs[x].qlen == 1) {               /* The flow is new */
275                 if (q->tail == SFQ_DEPTH) {     /* It is the first flow */
276                         q->tail = x;
277                         q->next[x] = x;
278                         q->allot[x] = q->quantum;
279                 } else {
280                         q->next[x] = q->next[q->tail];
281                         q->next[q->tail] = x;
282                         q->tail = x;
283                 }
284         }
285         if (++sch->q.qlen < q->limit-1) {
286                 sch->bstats.bytes += skb->len;
287                 sch->bstats.packets++;
288                 return 0;
289         }
290
291         sfq_drop(sch);
292         return NET_XMIT_CN;
293 }
294
295 static int
296 sfq_requeue(struct sk_buff *skb, struct Qdisc* sch)
297 {
298         struct sfq_sched_data *q = qdisc_priv(sch);
299         unsigned hash = sfq_hash(q, skb);
300         sfq_index x;
301
302         x = q->ht[hash];
303         if (x == SFQ_DEPTH) {
304                 q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
305                 q->hash[x] = hash;
306         }
307         sch->qstats.backlog += skb->len;
308         __skb_queue_head(&q->qs[x], skb);
309         sfq_inc(q, x);
310         if (q->qs[x].qlen == 1) {               /* The flow is new */
311                 if (q->tail == SFQ_DEPTH) {     /* It is the first flow */
312                         q->tail = x;
313                         q->next[x] = x;
314                         q->allot[x] = q->quantum;
315                 } else {
316                         q->next[x] = q->next[q->tail];
317                         q->next[q->tail] = x;
318                         q->tail = x;
319                 }
320         }
321         if (++sch->q.qlen < q->limit - 1) {
322                 sch->qstats.requeues++;
323                 return 0;
324         }
325
326         sch->qstats.drops++;
327         sfq_drop(sch);
328         return NET_XMIT_CN;
329 }
330
331
332
333
334 static struct sk_buff *
335 sfq_dequeue(struct Qdisc* sch)
336 {
337         struct sfq_sched_data *q = qdisc_priv(sch);
338         struct sk_buff *skb;
339         sfq_index a, old_a;
340
341         /* No active slots */
342         if (q->tail == SFQ_DEPTH)
343                 return NULL;
344
345         a = old_a = q->next[q->tail];
346
347         /* Grab packet */
348         skb = __skb_dequeue(&q->qs[a]);
349         sfq_dec(q, a);
350         sch->q.qlen--;
351         sch->qstats.backlog -= skb->len;
352
353         /* Is the slot empty? */
354         if (q->qs[a].qlen == 0) {
355                 q->ht[q->hash[a]] = SFQ_DEPTH;
356                 a = q->next[a];
357                 if (a == old_a) {
358                         q->tail = SFQ_DEPTH;
359                         return skb;
360                 }
361                 q->next[q->tail] = a;
362                 q->allot[a] += q->quantum;
363         } else if ((q->allot[a] -= skb->len) <= 0) {
364                 q->tail = a;
365                 a = q->next[a];
366                 q->allot[a] += q->quantum;
367         }
368         return skb;
369 }
370
371 static void
372 sfq_reset(struct Qdisc* sch)
373 {
374         struct sk_buff *skb;
375
376         while ((skb = sfq_dequeue(sch)) != NULL)
377                 kfree_skb(skb);
378 }
379
380 static void sfq_perturbation(unsigned long arg)
381 {
382         struct Qdisc *sch = (struct Qdisc*)arg;
383         struct sfq_sched_data *q = qdisc_priv(sch);
384
385         q->perturbation = net_random()&0x1F;
386
387         if (q->perturb_period) {
388                 q->perturb_timer.expires = jiffies + q->perturb_period;
389                 add_timer(&q->perturb_timer);
390         }
391 }
392
393 static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
394 {
395         struct sfq_sched_data *q = qdisc_priv(sch);
396         struct tc_sfq_qopt *ctl = RTA_DATA(opt);
397
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
407         while (sch->q.qlen >= q->limit-1)
408                 sfq_drop(sch);
409
410         del_timer(&q->perturb_timer);
411         if (q->perturb_period) {
412                 q->perturb_timer.expires = jiffies + q->perturb_period;
413                 add_timer(&q->perturb_timer);
414         }
415         sch_tree_unlock(sch);
416         return 0;
417 }
418
419 static int sfq_init(struct Qdisc *sch, struct rtattr *opt)
420 {
421         struct sfq_sched_data *q = qdisc_priv(sch);
422         int i;
423
424         init_timer(&q->perturb_timer);
425         q->perturb_timer.data = (unsigned long)sch;
426         q->perturb_timer.function = sfq_perturbation;
427
428         for (i=0; i<SFQ_HASH_DIVISOR; i++)
429                 q->ht[i] = SFQ_DEPTH;
430         for (i=0; i<SFQ_DEPTH; i++) {
431                 skb_queue_head_init(&q->qs[i]);
432                 q->dep[i+SFQ_DEPTH].next = i+SFQ_DEPTH;
433                 q->dep[i+SFQ_DEPTH].prev = i+SFQ_DEPTH;
434         }
435         q->limit = SFQ_DEPTH;
436         q->max_depth = 0;
437         q->tail = SFQ_DEPTH;
438         if (opt == NULL) {
439                 q->quantum = psched_mtu(sch->dev);
440                 q->perturb_period = 0;
441         } else {
442                 int err = sfq_change(sch, opt);
443                 if (err)
444                         return err;
445         }
446         for (i=0; i<SFQ_DEPTH; i++)
447                 sfq_link(q, i);
448         return 0;
449 }
450
451 static void sfq_destroy(struct Qdisc *sch)
452 {
453         struct sfq_sched_data *q = qdisc_priv(sch);
454         del_timer(&q->perturb_timer);
455 }
456
457 static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
458 {
459         struct sfq_sched_data *q = qdisc_priv(sch);
460         unsigned char    *b = skb->tail;
461         struct tc_sfq_qopt opt;
462
463         opt.quantum = q->quantum;
464         opt.perturb_period = q->perturb_period/HZ;
465
466         opt.limit = q->limit;
467         opt.divisor = SFQ_HASH_DIVISOR;
468         opt.flows = q->limit;
469
470         RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
471
472         return skb->len;
473
474 rtattr_failure:
475         skb_trim(skb, b - skb->data);
476         return -1;
477 }
478
479 static struct Qdisc_ops sfq_qdisc_ops = {
480         .next           =       NULL,
481         .cl_ops         =       NULL,
482         .id             =       "sfq",
483         .priv_size      =       sizeof(struct sfq_sched_data),
484         .enqueue        =       sfq_enqueue,
485         .dequeue        =       sfq_dequeue,
486         .requeue        =       sfq_requeue,
487         .drop           =       sfq_drop,
488         .init           =       sfq_init,
489         .reset          =       sfq_reset,
490         .destroy        =       sfq_destroy,
491         .change         =       NULL,
492         .dump           =       sfq_dump,
493         .owner          =       THIS_MODULE,
494 };
495
496 static int __init sfq_module_init(void)
497 {
498         return register_qdisc(&sfq_qdisc_ops);
499 }
500 static void __exit sfq_module_exit(void) 
501 {
502         unregister_qdisc(&sfq_qdisc_ops);
503 }
504 module_init(sfq_module_init)
505 module_exit(sfq_module_exit)
506 MODULE_LICENSE("GPL");