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