Merge branch 'upstream-linus' of master.kernel.org:/pub/scm/linux/kernel/git/jgarzik...
[sfrench/cifs-2.6.git] / 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/module.h>
13 #include <linux/types.h>
14 #include <linux/kernel.h>
15 #include <linux/jiffies.h>
16 #include <linux/string.h>
17 #include <linux/in.h>
18 #include <linux/errno.h>
19 #include <linux/init.h>
20 #include <linux/ipv6.h>
21 #include <linux/skbuff.h>
22 #include <net/ip.h>
23 #include <net/netlink.h>
24 #include <net/pkt_sched.h>
25
26
27 /*      Stochastic Fairness Queuing algorithm.
28         =======================================
29
30         Source:
31         Paul E. McKenney "Stochastic Fairness Queuing",
32         IEEE INFOCOMM'90 Proceedings, San Francisco, 1990.
33
34         Paul E. McKenney "Stochastic Fairness Queuing",
35         "Interworking: Research and Experience", v.2, 1991, p.113-131.
36
37
38         See also:
39         M. Shreedhar and George Varghese "Efficient Fair
40         Queuing using Deficit Round Robin", Proc. SIGCOMM 95.
41
42
43         This is not the thing that is usually called (W)FQ nowadays.
44         It does not use any timestamp mechanism, but instead
45         processes queues in round-robin order.
46
47         ADVANTAGE:
48
49         - It is very cheap. Both CPU and memory requirements are minimal.
50
51         DRAWBACKS:
52
53         - "Stochastic" -> It is not 100% fair.
54         When hash collisions occur, several flows are considered as one.
55
56         - "Round-robin" -> It introduces larger delays than virtual clock
57         based schemes, and should not be used for isolating interactive
58         traffic from non-interactive. It means, that this scheduler
59         should be used as leaf of CBQ or P3, which put interactive traffic
60         to higher priority band.
61
62         We still need true WFQ for top level CSZ, but using WFQ
63         for the best effort traffic is absolutely pointless:
64         SFQ is superior for this purpose.
65
66         IMPLEMENTATION:
67         This implementation limits maximal queue length to 128;
68         maximal mtu to 2^15-1; number of hash buckets to 1024.
69         The only goal of this restrictions was that all data
70         fit into one 4K page :-). Struct sfq_sched_data is
71         organized in anti-cache manner: all the data for a bucket
72         are scattered over different locations. This is not good,
73         but it allowed me to put it into 4K.
74
75         It is easy to increase these values, but not in flight.  */
76
77 #define SFQ_DEPTH               128
78 #define SFQ_HASH_DIVISOR        1024
79
80 /* This type should contain at least SFQ_DEPTH*2 values */
81 typedef unsigned char sfq_index;
82
83 struct sfq_head
84 {
85         sfq_index       next;
86         sfq_index       prev;
87 };
88
89 struct sfq_sched_data
90 {
91 /* Parameters */
92         int             perturb_period;
93         unsigned        quantum;        /* Allotment per round: MUST BE >= MTU */
94         int             limit;
95
96 /* Variables */
97         struct timer_list perturb_timer;
98         int             perturbation;
99         sfq_index       tail;           /* Index of current slot in round */
100         sfq_index       max_depth;      /* Maximal depth */
101
102         sfq_index       ht[SFQ_HASH_DIVISOR];   /* Hash table */
103         sfq_index       next[SFQ_DEPTH];        /* Active slots link */
104         short           allot[SFQ_DEPTH];       /* Current allotment per slot */
105         unsigned short  hash[SFQ_DEPTH];        /* Hash value indexed by slots */
106         struct sk_buff_head     qs[SFQ_DEPTH];          /* Slot queue */
107         struct sfq_head dep[SFQ_DEPTH*2];       /* Linked list of slots, indexed by depth */
108 };
109
110 static __inline__ unsigned sfq_fold_hash(struct sfq_sched_data *q, u32 h, u32 h1)
111 {
112         int pert = q->perturbation;
113
114         /* Have we any rotation primitives? If not, WHY? */
115         h ^= (h1<<pert) ^ (h1>>(0x1F - pert));
116         h ^= h>>10;
117         return h & 0x3FF;
118 }
119
120 static unsigned sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb)
121 {
122         u32 h, h2;
123
124         switch (skb->protocol) {
125         case __constant_htons(ETH_P_IP):
126         {
127                 const struct iphdr *iph = ip_hdr(skb);
128                 h = iph->daddr;
129                 h2 = iph->saddr^iph->protocol;
130                 if (!(iph->frag_off&htons(IP_MF|IP_OFFSET)) &&
131                     (iph->protocol == IPPROTO_TCP ||
132                      iph->protocol == IPPROTO_UDP ||
133                      iph->protocol == IPPROTO_UDPLITE ||
134                      iph->protocol == IPPROTO_SCTP ||
135                      iph->protocol == IPPROTO_DCCP ||
136                      iph->protocol == IPPROTO_ESP))
137                         h2 ^= *(((u32*)iph) + iph->ihl);
138                 break;
139         }
140         case __constant_htons(ETH_P_IPV6):
141         {
142                 struct ipv6hdr *iph = ipv6_hdr(skb);
143                 h = iph->daddr.s6_addr32[3];
144                 h2 = iph->saddr.s6_addr32[3]^iph->nexthdr;
145                 if (iph->nexthdr == IPPROTO_TCP ||
146                     iph->nexthdr == IPPROTO_UDP ||
147                     iph->nexthdr == IPPROTO_UDPLITE ||
148                     iph->nexthdr == IPPROTO_SCTP ||
149                     iph->nexthdr == IPPROTO_DCCP ||
150                     iph->nexthdr == IPPROTO_ESP)
151                         h2 ^= *(u32*)&iph[1];
152                 break;
153         }
154         default:
155                 h = (u32)(unsigned long)skb->dst^skb->protocol;
156                 h2 = (u32)(unsigned long)skb->sk;
157         }
158         return sfq_fold_hash(q, h, h2);
159 }
160
161 static inline void sfq_link(struct sfq_sched_data *q, sfq_index x)
162 {
163         sfq_index p, n;
164         int d = q->qs[x].qlen + SFQ_DEPTH;
165
166         p = d;
167         n = q->dep[d].next;
168         q->dep[x].next = n;
169         q->dep[x].prev = p;
170         q->dep[p].next = q->dep[n].prev = x;
171 }
172
173 static inline void sfq_dec(struct sfq_sched_data *q, sfq_index x)
174 {
175         sfq_index p, n;
176
177         n = q->dep[x].next;
178         p = q->dep[x].prev;
179         q->dep[p].next = n;
180         q->dep[n].prev = p;
181
182         if (n == p && q->max_depth == q->qs[x].qlen + 1)
183                 q->max_depth--;
184
185         sfq_link(q, x);
186 }
187
188 static inline void sfq_inc(struct sfq_sched_data *q, sfq_index x)
189 {
190         sfq_index p, n;
191         int d;
192
193         n = q->dep[x].next;
194         p = q->dep[x].prev;
195         q->dep[p].next = n;
196         q->dep[n].prev = p;
197         d = q->qs[x].qlen;
198         if (q->max_depth < d)
199                 q->max_depth = d;
200
201         sfq_link(q, x);
202 }
203
204 static unsigned int sfq_drop(struct Qdisc *sch)
205 {
206         struct sfq_sched_data *q = qdisc_priv(sch);
207         sfq_index d = q->max_depth;
208         struct sk_buff *skb;
209         unsigned int len;
210
211         /* Queue is full! Find the longest slot and
212            drop a packet from it */
213
214         if (d > 1) {
215                 sfq_index x = q->dep[d+SFQ_DEPTH].next;
216                 skb = q->qs[x].prev;
217                 len = skb->len;
218                 __skb_unlink(skb, &q->qs[x]);
219                 kfree_skb(skb);
220                 sfq_dec(q, x);
221                 sch->q.qlen--;
222                 sch->qstats.drops++;
223                 sch->qstats.backlog -= len;
224                 return len;
225         }
226
227         if (d == 1) {
228                 /* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
229                 d = q->next[q->tail];
230                 q->next[q->tail] = q->next[d];
231                 q->allot[q->next[d]] += q->quantum;
232                 skb = q->qs[d].prev;
233                 len = skb->len;
234                 __skb_unlink(skb, &q->qs[d]);
235                 kfree_skb(skb);
236                 sfq_dec(q, d);
237                 sch->q.qlen--;
238                 q->ht[q->hash[d]] = SFQ_DEPTH;
239                 sch->qstats.drops++;
240                 sch->qstats.backlog -= len;
241                 return len;
242         }
243
244         return 0;
245 }
246
247 static int
248 sfq_enqueue(struct sk_buff *skb, struct Qdisc* sch)
249 {
250         struct sfq_sched_data *q = qdisc_priv(sch);
251         unsigned hash = sfq_hash(q, skb);
252         sfq_index x;
253
254         x = q->ht[hash];
255         if (x == SFQ_DEPTH) {
256                 q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
257                 q->hash[x] = hash;
258         }
259         sch->qstats.backlog += skb->len;
260         __skb_queue_tail(&q->qs[x], skb);
261         sfq_inc(q, x);
262         if (q->qs[x].qlen == 1) {               /* The flow is new */
263                 if (q->tail == SFQ_DEPTH) {     /* It is the first flow */
264                         q->tail = x;
265                         q->next[x] = x;
266                         q->allot[x] = q->quantum;
267                 } else {
268                         q->next[x] = q->next[q->tail];
269                         q->next[q->tail] = x;
270                         q->tail = x;
271                 }
272         }
273         if (++sch->q.qlen < q->limit-1) {
274                 sch->bstats.bytes += skb->len;
275                 sch->bstats.packets++;
276                 return 0;
277         }
278
279         sfq_drop(sch);
280         return NET_XMIT_CN;
281 }
282
283 static int
284 sfq_requeue(struct sk_buff *skb, struct Qdisc* sch)
285 {
286         struct sfq_sched_data *q = qdisc_priv(sch);
287         unsigned hash = sfq_hash(q, skb);
288         sfq_index x;
289
290         x = q->ht[hash];
291         if (x == SFQ_DEPTH) {
292                 q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
293                 q->hash[x] = hash;
294         }
295         sch->qstats.backlog += skb->len;
296         __skb_queue_head(&q->qs[x], skb);
297         sfq_inc(q, x);
298         if (q->qs[x].qlen == 1) {               /* The flow is new */
299                 if (q->tail == SFQ_DEPTH) {     /* It is the first flow */
300                         q->tail = x;
301                         q->next[x] = x;
302                         q->allot[x] = q->quantum;
303                 } else {
304                         q->next[x] = q->next[q->tail];
305                         q->next[q->tail] = x;
306                         q->tail = x;
307                 }
308         }
309         if (++sch->q.qlen < q->limit - 1) {
310                 sch->qstats.requeues++;
311                 return 0;
312         }
313
314         sch->qstats.drops++;
315         sfq_drop(sch);
316         return NET_XMIT_CN;
317 }
318
319
320
321
322 static struct sk_buff *
323 sfq_dequeue(struct Qdisc* sch)
324 {
325         struct sfq_sched_data *q = qdisc_priv(sch);
326         struct sk_buff *skb;
327         sfq_index a, old_a;
328
329         /* No active slots */
330         if (q->tail == SFQ_DEPTH)
331                 return NULL;
332
333         a = old_a = q->next[q->tail];
334
335         /* Grab packet */
336         skb = __skb_dequeue(&q->qs[a]);
337         sfq_dec(q, a);
338         sch->q.qlen--;
339         sch->qstats.backlog -= skb->len;
340
341         /* Is the slot empty? */
342         if (q->qs[a].qlen == 0) {
343                 q->ht[q->hash[a]] = SFQ_DEPTH;
344                 a = q->next[a];
345                 if (a == old_a) {
346                         q->tail = SFQ_DEPTH;
347                         return skb;
348                 }
349                 q->next[q->tail] = a;
350                 q->allot[a] += q->quantum;
351         } else if ((q->allot[a] -= skb->len) <= 0) {
352                 q->tail = a;
353                 a = q->next[a];
354                 q->allot[a] += q->quantum;
355         }
356         return skb;
357 }
358
359 static void
360 sfq_reset(struct Qdisc* sch)
361 {
362         struct sk_buff *skb;
363
364         while ((skb = sfq_dequeue(sch)) != NULL)
365                 kfree_skb(skb);
366 }
367
368 static void sfq_perturbation(unsigned long arg)
369 {
370         struct Qdisc *sch = (struct Qdisc*)arg;
371         struct sfq_sched_data *q = qdisc_priv(sch);
372
373         q->perturbation = net_random()&0x1F;
374
375         if (q->perturb_period) {
376                 q->perturb_timer.expires = jiffies + q->perturb_period;
377                 add_timer(&q->perturb_timer);
378         }
379 }
380
381 static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
382 {
383         struct sfq_sched_data *q = qdisc_priv(sch);
384         struct tc_sfq_qopt *ctl = RTA_DATA(opt);
385         unsigned int qlen;
386
387         if (opt->rta_len < RTA_LENGTH(sizeof(*ctl)))
388                 return -EINVAL;
389
390         sch_tree_lock(sch);
391         q->quantum = ctl->quantum ? : psched_mtu(sch->dev);
392         q->perturb_period = ctl->perturb_period*HZ;
393         if (ctl->limit)
394                 q->limit = min_t(u32, ctl->limit, SFQ_DEPTH);
395
396         qlen = sch->q.qlen;
397         while (sch->q.qlen >= q->limit-1)
398                 sfq_drop(sch);
399         qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen);
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
410 static 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
442 static void sfq_destroy(struct Qdisc *sch)
443 {
444         struct sfq_sched_data *q = qdisc_priv(sch);
445         del_timer(&q->perturb_timer);
446 }
447
448 static 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_pointer(skb);
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
465 rtattr_failure:
466         nlmsg_trim(skb, b);
467         return -1;
468 }
469
470 static 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
487 static int __init sfq_module_init(void)
488 {
489         return register_qdisc(&sfq_qdisc_ops);
490 }
491 static void __exit sfq_module_exit(void)
492 {
493         unregister_qdisc(&sfq_qdisc_ops);
494 }
495 module_init(sfq_module_init)
496 module_exit(sfq_module_exit)
497 MODULE_LICENSE("GPL");