198b83d42ba8159044420896b7ee4e89fe7d48c6
[linux-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 <linux/jhash.h>
23 #include <net/ip.h>
24 #include <net/netlink.h>
25 #include <net/pkt_sched.h>
26
27
28 /*      Stochastic Fairness Queuing algorithm.
29         =======================================
30
31         Source:
32         Paul E. McKenney "Stochastic Fairness Queuing",
33         IEEE INFOCOMM'90 Proceedings, San Francisco, 1990.
34
35         Paul E. McKenney "Stochastic Fairness Queuing",
36         "Interworking: Research and Experience", v.2, 1991, p.113-131.
37
38
39         See also:
40         M. Shreedhar and George Varghese "Efficient Fair
41         Queuing using Deficit Round Robin", Proc. SIGCOMM 95.
42
43
44         This is not the thing that is usually called (W)FQ nowadays.
45         It does not use any timestamp mechanism, but instead
46         processes queues in round-robin order.
47
48         ADVANTAGE:
49
50         - It is very cheap. Both CPU and memory requirements are minimal.
51
52         DRAWBACKS:
53
54         - "Stochastic" -> It is not 100% fair.
55         When hash collisions occur, several flows are considered as one.
56
57         - "Round-robin" -> It introduces larger delays than virtual clock
58         based schemes, and should not be used for isolating interactive
59         traffic from non-interactive. It means, that this scheduler
60         should be used as leaf of CBQ or P3, which put interactive traffic
61         to higher priority band.
62
63         We still need true WFQ for top level CSZ, but using WFQ
64         for the best effort traffic is absolutely pointless:
65         SFQ is superior for this purpose.
66
67         IMPLEMENTATION:
68         This implementation limits maximal queue length to 128;
69         maximal mtu to 2^15-1; number of hash buckets to 1024.
70         The only goal of this restrictions was that all data
71         fit into one 4K page :-). Struct sfq_sched_data is
72         organized in anti-cache manner: all the data for a bucket
73         are scattered over different locations. This is not good,
74         but it allowed me to put it into 4K.
75
76         It is easy to increase these values, but not in flight.  */
77
78 #define SFQ_DEPTH               128
79 #define SFQ_HASH_DIVISOR        1024
80
81 /* This type should contain at least SFQ_DEPTH*2 values */
82 typedef unsigned char sfq_index;
83
84 struct sfq_head
85 {
86         sfq_index       next;
87         sfq_index       prev;
88 };
89
90 struct sfq_sched_data
91 {
92 /* Parameters */
93         int             perturb_period;
94         unsigned        quantum;        /* Allotment per round: MUST BE >= MTU */
95         int             limit;
96
97 /* Variables */
98         struct tcf_proto *filter_list;
99         struct timer_list perturb_timer;
100         u32             perturbation;
101         sfq_index       tail;           /* Index of current slot in round */
102         sfq_index       max_depth;      /* Maximal depth */
103
104         sfq_index       ht[SFQ_HASH_DIVISOR];   /* Hash table */
105         sfq_index       next[SFQ_DEPTH];        /* Active slots link */
106         short           allot[SFQ_DEPTH];       /* Current allotment per slot */
107         unsigned short  hash[SFQ_DEPTH];        /* Hash value indexed by slots */
108         struct sk_buff_head     qs[SFQ_DEPTH];          /* Slot queue */
109         struct sfq_head dep[SFQ_DEPTH*2];       /* Linked list of slots, indexed by depth */
110 };
111
112 static __inline__ unsigned sfq_fold_hash(struct sfq_sched_data *q, u32 h, u32 h1)
113 {
114         return jhash_2words(h, h1, q->perturbation) & (SFQ_HASH_DIVISOR - 1);
115 }
116
117 static unsigned sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb)
118 {
119         u32 h, h2;
120
121         switch (skb->protocol) {
122         case htons(ETH_P_IP):
123         {
124                 const struct iphdr *iph = ip_hdr(skb);
125                 h = iph->daddr;
126                 h2 = iph->saddr ^ iph->protocol;
127                 if (!(iph->frag_off&htons(IP_MF|IP_OFFSET)) &&
128                     (iph->protocol == IPPROTO_TCP ||
129                      iph->protocol == IPPROTO_UDP ||
130                      iph->protocol == IPPROTO_UDPLITE ||
131                      iph->protocol == IPPROTO_SCTP ||
132                      iph->protocol == IPPROTO_DCCP ||
133                      iph->protocol == IPPROTO_ESP))
134                         h2 ^= *(((u32*)iph) + iph->ihl);
135                 break;
136         }
137         case htons(ETH_P_IPV6):
138         {
139                 struct ipv6hdr *iph = ipv6_hdr(skb);
140                 h = iph->daddr.s6_addr32[3];
141                 h2 = iph->saddr.s6_addr32[3] ^ iph->nexthdr;
142                 if (iph->nexthdr == IPPROTO_TCP ||
143                     iph->nexthdr == IPPROTO_UDP ||
144                     iph->nexthdr == IPPROTO_UDPLITE ||
145                     iph->nexthdr == IPPROTO_SCTP ||
146                     iph->nexthdr == IPPROTO_DCCP ||
147                     iph->nexthdr == IPPROTO_ESP)
148                         h2 ^= *(u32*)&iph[1];
149                 break;
150         }
151         default:
152                 h = (unsigned long)skb->dst ^ skb->protocol;
153                 h2 = (unsigned long)skb->sk;
154         }
155
156         return sfq_fold_hash(q, h, h2);
157 }
158
159 static unsigned int sfq_classify(struct sk_buff *skb, struct Qdisc *sch,
160                                  int *qerr)
161 {
162         struct sfq_sched_data *q = qdisc_priv(sch);
163         struct tcf_result res;
164         int result;
165
166         if (TC_H_MAJ(skb->priority) == sch->handle &&
167             TC_H_MIN(skb->priority) > 0 &&
168             TC_H_MIN(skb->priority) <= SFQ_HASH_DIVISOR)
169                 return TC_H_MIN(skb->priority);
170
171         if (!q->filter_list)
172                 return sfq_hash(q, skb) + 1;
173
174         *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
175         result = tc_classify(skb, q->filter_list, &res);
176         if (result >= 0) {
177 #ifdef CONFIG_NET_CLS_ACT
178                 switch (result) {
179                 case TC_ACT_STOLEN:
180                 case TC_ACT_QUEUED:
181                         *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
182                 case TC_ACT_SHOT:
183                         return 0;
184                 }
185 #endif
186                 if (TC_H_MIN(res.classid) <= SFQ_HASH_DIVISOR)
187                         return TC_H_MIN(res.classid);
188         }
189         return 0;
190 }
191
192 static inline void sfq_link(struct sfq_sched_data *q, sfq_index x)
193 {
194         sfq_index p, n;
195         int d = q->qs[x].qlen + SFQ_DEPTH;
196
197         p = d;
198         n = q->dep[d].next;
199         q->dep[x].next = n;
200         q->dep[x].prev = p;
201         q->dep[p].next = q->dep[n].prev = x;
202 }
203
204 static inline void sfq_dec(struct sfq_sched_data *q, sfq_index x)
205 {
206         sfq_index p, n;
207
208         n = q->dep[x].next;
209         p = q->dep[x].prev;
210         q->dep[p].next = n;
211         q->dep[n].prev = p;
212
213         if (n == p && q->max_depth == q->qs[x].qlen + 1)
214                 q->max_depth--;
215
216         sfq_link(q, x);
217 }
218
219 static inline void sfq_inc(struct sfq_sched_data *q, sfq_index x)
220 {
221         sfq_index p, n;
222         int d;
223
224         n = q->dep[x].next;
225         p = q->dep[x].prev;
226         q->dep[p].next = n;
227         q->dep[n].prev = p;
228         d = q->qs[x].qlen;
229         if (q->max_depth < d)
230                 q->max_depth = d;
231
232         sfq_link(q, x);
233 }
234
235 static unsigned int sfq_drop(struct Qdisc *sch)
236 {
237         struct sfq_sched_data *q = qdisc_priv(sch);
238         sfq_index d = q->max_depth;
239         struct sk_buff *skb;
240         unsigned int len;
241
242         /* Queue is full! Find the longest slot and
243            drop a packet from it */
244
245         if (d > 1) {
246                 sfq_index x = q->dep[d + SFQ_DEPTH].next;
247                 skb = q->qs[x].prev;
248                 len = qdisc_pkt_len(skb);
249                 __skb_unlink(skb, &q->qs[x]);
250                 kfree_skb(skb);
251                 sfq_dec(q, x);
252                 sch->q.qlen--;
253                 sch->qstats.drops++;
254                 sch->qstats.backlog -= len;
255                 return len;
256         }
257
258         if (d == 1) {
259                 /* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
260                 d = q->next[q->tail];
261                 q->next[q->tail] = q->next[d];
262                 q->allot[q->next[d]] += q->quantum;
263                 skb = q->qs[d].prev;
264                 len = qdisc_pkt_len(skb);
265                 __skb_unlink(skb, &q->qs[d]);
266                 kfree_skb(skb);
267                 sfq_dec(q, d);
268                 sch->q.qlen--;
269                 q->ht[q->hash[d]] = SFQ_DEPTH;
270                 sch->qstats.drops++;
271                 sch->qstats.backlog -= len;
272                 return len;
273         }
274
275         return 0;
276 }
277
278 static int
279 sfq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
280 {
281         struct sfq_sched_data *q = qdisc_priv(sch);
282         unsigned int hash;
283         sfq_index x;
284         int ret;
285
286         hash = sfq_classify(skb, sch, &ret);
287         if (hash == 0) {
288                 if (ret & __NET_XMIT_BYPASS)
289                         sch->qstats.drops++;
290                 kfree_skb(skb);
291                 return ret;
292         }
293         hash--;
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
301         /* If selected queue has length q->limit, this means that
302          * all another queues are empty and that we do simple tail drop,
303          * i.e. drop _this_ packet.
304          */
305         if (q->qs[x].qlen >= q->limit)
306                 return qdisc_drop(skb, sch);
307
308         sch->qstats.backlog += qdisc_pkt_len(skb);
309         __skb_queue_tail(&q->qs[x], skb);
310         sfq_inc(q, x);
311         if (q->qs[x].qlen == 1) {               /* The flow is new */
312                 if (q->tail == SFQ_DEPTH) {     /* It is the first flow */
313                         q->tail = x;
314                         q->next[x] = x;
315                         q->allot[x] = q->quantum;
316                 } else {
317                         q->next[x] = q->next[q->tail];
318                         q->next[q->tail] = x;
319                         q->tail = x;
320                 }
321         }
322         if (++sch->q.qlen <= q->limit) {
323                 sch->bstats.bytes += qdisc_pkt_len(skb);
324                 sch->bstats.packets++;
325                 return 0;
326         }
327
328         sfq_drop(sch);
329         return NET_XMIT_CN;
330 }
331
332 static int
333 sfq_requeue(struct sk_buff *skb, struct Qdisc *sch)
334 {
335         struct sfq_sched_data *q = qdisc_priv(sch);
336         unsigned int hash;
337         sfq_index x;
338         int ret;
339
340         hash = sfq_classify(skb, sch, &ret);
341         if (hash == 0) {
342                 if (ret & __NET_XMIT_BYPASS)
343                         sch->qstats.drops++;
344                 kfree_skb(skb);
345                 return ret;
346         }
347         hash--;
348
349         x = q->ht[hash];
350         if (x == SFQ_DEPTH) {
351                 q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
352                 q->hash[x] = hash;
353         }
354
355         sch->qstats.backlog += qdisc_pkt_len(skb);
356         __skb_queue_head(&q->qs[x], skb);
357         /* If selected queue has length q->limit+1, this means that
358          * all another queues are empty and we do simple tail drop.
359          * This packet is still requeued at head of queue, tail packet
360          * is dropped.
361          */
362         if (q->qs[x].qlen > q->limit) {
363                 skb = q->qs[x].prev;
364                 __skb_unlink(skb, &q->qs[x]);
365                 sch->qstats.drops++;
366                 sch->qstats.backlog -= qdisc_pkt_len(skb);
367                 kfree_skb(skb);
368                 return NET_XMIT_CN;
369         }
370
371         sfq_inc(q, x);
372         if (q->qs[x].qlen == 1) {               /* The flow is new */
373                 if (q->tail == SFQ_DEPTH) {     /* It is the first flow */
374                         q->tail = x;
375                         q->next[x] = x;
376                         q->allot[x] = q->quantum;
377                 } else {
378                         q->next[x] = q->next[q->tail];
379                         q->next[q->tail] = x;
380                         q->tail = x;
381                 }
382         }
383
384         if (++sch->q.qlen <= q->limit) {
385                 sch->qstats.requeues++;
386                 return 0;
387         }
388
389         sch->qstats.drops++;
390         sfq_drop(sch);
391         return NET_XMIT_CN;
392 }
393
394 static struct sk_buff *
395 sfq_peek(struct Qdisc *sch)
396 {
397         struct sfq_sched_data *q = qdisc_priv(sch);
398         sfq_index a;
399
400         /* No active slots */
401         if (q->tail == SFQ_DEPTH)
402                 return NULL;
403
404         a = q->next[q->tail];
405         return skb_peek(&q->qs[a]);
406 }
407
408 static struct sk_buff *
409 sfq_dequeue(struct Qdisc *sch)
410 {
411         struct sfq_sched_data *q = qdisc_priv(sch);
412         struct sk_buff *skb;
413         sfq_index a, old_a;
414
415         /* No active slots */
416         if (q->tail == SFQ_DEPTH)
417                 return NULL;
418
419         a = old_a = q->next[q->tail];
420
421         /* Grab packet */
422         skb = __skb_dequeue(&q->qs[a]);
423         sfq_dec(q, a);
424         sch->q.qlen--;
425         sch->qstats.backlog -= qdisc_pkt_len(skb);
426
427         /* Is the slot empty? */
428         if (q->qs[a].qlen == 0) {
429                 q->ht[q->hash[a]] = SFQ_DEPTH;
430                 a = q->next[a];
431                 if (a == old_a) {
432                         q->tail = SFQ_DEPTH;
433                         return skb;
434                 }
435                 q->next[q->tail] = a;
436                 q->allot[a] += q->quantum;
437         } else if ((q->allot[a] -= qdisc_pkt_len(skb)) <= 0) {
438                 q->tail = a;
439                 a = q->next[a];
440                 q->allot[a] += q->quantum;
441         }
442         return skb;
443 }
444
445 static void
446 sfq_reset(struct Qdisc *sch)
447 {
448         struct sk_buff *skb;
449
450         while ((skb = sfq_dequeue(sch)) != NULL)
451                 kfree_skb(skb);
452 }
453
454 static void sfq_perturbation(unsigned long arg)
455 {
456         struct Qdisc *sch = (struct Qdisc *)arg;
457         struct sfq_sched_data *q = qdisc_priv(sch);
458
459         q->perturbation = net_random();
460
461         if (q->perturb_period)
462                 mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
463 }
464
465 static int sfq_change(struct Qdisc *sch, struct nlattr *opt)
466 {
467         struct sfq_sched_data *q = qdisc_priv(sch);
468         struct tc_sfq_qopt *ctl = nla_data(opt);
469         unsigned int qlen;
470
471         if (opt->nla_len < nla_attr_size(sizeof(*ctl)))
472                 return -EINVAL;
473
474         sch_tree_lock(sch);
475         q->quantum = ctl->quantum ? : psched_mtu(qdisc_dev(sch));
476         q->perturb_period = ctl->perturb_period * HZ;
477         if (ctl->limit)
478                 q->limit = min_t(u32, ctl->limit, SFQ_DEPTH - 1);
479
480         qlen = sch->q.qlen;
481         while (sch->q.qlen > q->limit)
482                 sfq_drop(sch);
483         qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen);
484
485         del_timer(&q->perturb_timer);
486         if (q->perturb_period) {
487                 mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
488                 q->perturbation = net_random();
489         }
490         sch_tree_unlock(sch);
491         return 0;
492 }
493
494 static int sfq_init(struct Qdisc *sch, struct nlattr *opt)
495 {
496         struct sfq_sched_data *q = qdisc_priv(sch);
497         int i;
498
499         q->perturb_timer.function = sfq_perturbation;
500         q->perturb_timer.data = (unsigned long)sch;;
501         init_timer_deferrable(&q->perturb_timer);
502
503         for (i = 0; i < SFQ_HASH_DIVISOR; i++)
504                 q->ht[i] = SFQ_DEPTH;
505
506         for (i = 0; i < SFQ_DEPTH; i++) {
507                 skb_queue_head_init(&q->qs[i]);
508                 q->dep[i + SFQ_DEPTH].next = i + SFQ_DEPTH;
509                 q->dep[i + SFQ_DEPTH].prev = i + SFQ_DEPTH;
510         }
511
512         q->limit = SFQ_DEPTH - 1;
513         q->max_depth = 0;
514         q->tail = SFQ_DEPTH;
515         if (opt == NULL) {
516                 q->quantum = psched_mtu(qdisc_dev(sch));
517                 q->perturb_period = 0;
518                 q->perturbation = net_random();
519         } else {
520                 int err = sfq_change(sch, opt);
521                 if (err)
522                         return err;
523         }
524
525         for (i = 0; i < SFQ_DEPTH; i++)
526                 sfq_link(q, i);
527         return 0;
528 }
529
530 static void sfq_destroy(struct Qdisc *sch)
531 {
532         struct sfq_sched_data *q = qdisc_priv(sch);
533
534         tcf_destroy_chain(&q->filter_list);
535         q->perturb_period = 0;
536         del_timer_sync(&q->perturb_timer);
537 }
538
539 static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
540 {
541         struct sfq_sched_data *q = qdisc_priv(sch);
542         unsigned char *b = skb_tail_pointer(skb);
543         struct tc_sfq_qopt opt;
544
545         opt.quantum = q->quantum;
546         opt.perturb_period = q->perturb_period / HZ;
547
548         opt.limit = q->limit;
549         opt.divisor = SFQ_HASH_DIVISOR;
550         opt.flows = q->limit;
551
552         NLA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
553
554         return skb->len;
555
556 nla_put_failure:
557         nlmsg_trim(skb, b);
558         return -1;
559 }
560
561 static int sfq_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
562                             struct nlattr **tca, unsigned long *arg)
563 {
564         return -EOPNOTSUPP;
565 }
566
567 static unsigned long sfq_get(struct Qdisc *sch, u32 classid)
568 {
569         return 0;
570 }
571
572 static struct tcf_proto **sfq_find_tcf(struct Qdisc *sch, unsigned long cl)
573 {
574         struct sfq_sched_data *q = qdisc_priv(sch);
575
576         if (cl)
577                 return NULL;
578         return &q->filter_list;
579 }
580
581 static int sfq_dump_class(struct Qdisc *sch, unsigned long cl,
582                           struct sk_buff *skb, struct tcmsg *tcm)
583 {
584         tcm->tcm_handle |= TC_H_MIN(cl);
585         return 0;
586 }
587
588 static int sfq_dump_class_stats(struct Qdisc *sch, unsigned long cl,
589                                 struct gnet_dump *d)
590 {
591         struct sfq_sched_data *q = qdisc_priv(sch);
592         sfq_index idx = q->ht[cl-1];
593         struct gnet_stats_queue qs = { .qlen = q->qs[idx].qlen };
594         struct tc_sfq_xstats xstats = { .allot = q->allot[idx] };
595
596         if (gnet_stats_copy_queue(d, &qs) < 0)
597                 return -1;
598         return gnet_stats_copy_app(d, &xstats, sizeof(xstats));
599 }
600
601 static void sfq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
602 {
603         struct sfq_sched_data *q = qdisc_priv(sch);
604         unsigned int i;
605
606         if (arg->stop)
607                 return;
608
609         for (i = 0; i < SFQ_HASH_DIVISOR; i++) {
610                 if (q->ht[i] == SFQ_DEPTH ||
611                     arg->count < arg->skip) {
612                         arg->count++;
613                         continue;
614                 }
615                 if (arg->fn(sch, i + 1, arg) < 0) {
616                         arg->stop = 1;
617                         break;
618                 }
619                 arg->count++;
620         }
621 }
622
623 static const struct Qdisc_class_ops sfq_class_ops = {
624         .get            =       sfq_get,
625         .change         =       sfq_change_class,
626         .tcf_chain      =       sfq_find_tcf,
627         .dump           =       sfq_dump_class,
628         .dump_stats     =       sfq_dump_class_stats,
629         .walk           =       sfq_walk,
630 };
631
632 static struct Qdisc_ops sfq_qdisc_ops __read_mostly = {
633         .cl_ops         =       &sfq_class_ops,
634         .id             =       "sfq",
635         .priv_size      =       sizeof(struct sfq_sched_data),
636         .enqueue        =       sfq_enqueue,
637         .dequeue        =       sfq_dequeue,
638         .peek           =       sfq_peek,
639         .requeue        =       sfq_requeue,
640         .drop           =       sfq_drop,
641         .init           =       sfq_init,
642         .reset          =       sfq_reset,
643         .destroy        =       sfq_destroy,
644         .change         =       NULL,
645         .dump           =       sfq_dump,
646         .owner          =       THIS_MODULE,
647 };
648
649 static int __init sfq_module_init(void)
650 {
651         return register_qdisc(&sfq_qdisc_ops);
652 }
653 static void __exit sfq_module_exit(void)
654 {
655         unregister_qdisc(&sfq_qdisc_ops);
656 }
657 module_init(sfq_module_init)
658 module_exit(sfq_module_exit)
659 MODULE_LICENSE("GPL");