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) ^ 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 uninitialized_var(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 struct sk_buff *
 333 sfq_peek(struct Qdisc *sch)
 334 {
 335         struct sfq_sched_data *q = qdisc_priv(sch);
 336         sfq_index a;
 337
 338         /* No active slots */
 339         if (q->tail == SFQ_DEPTH)
 340                 return NULL;
 341
 342         a = q->next[q->tail];
 343         return skb_peek(&q->qs[a]);
 344 }
 345
 346 static struct sk_buff *
 347 sfq_dequeue(struct Qdisc *sch)
 348 {
 349         struct sfq_sched_data *q = qdisc_priv(sch);
 350         struct sk_buff *skb;
 351         sfq_index a, old_a;
 352
 353         /* No active slots */
 354         if (q->tail == SFQ_DEPTH)
 355                 return NULL;
 356
 357         a = old_a = q->next[q->tail];
 358
 359         /* Grab packet */
 360         skb = __skb_dequeue(&q->qs[a]);
 361         sfq_dec(q, a);
 362         sch->q.qlen--;
 363         sch->qstats.backlog -= qdisc_pkt_len(skb);
 364
 365         /* Is the slot empty? */
 366         if (q->qs[a].qlen == 0) {
 367                 q->ht[q->hash[a]] = SFQ_DEPTH;
 368                 a = q->next[a];
 369                 if (a == old_a) {
 370                         q->tail = SFQ_DEPTH;
 371                         return skb;
 372                 }
 373                 q->next[q->tail] = a;
 374                 q->allot[a] += q->quantum;
 375         } else if ((q->allot[a] -= qdisc_pkt_len(skb)) <= 0) {
 376                 q->tail = a;
 377                 a = q->next[a];
 378                 q->allot[a] += q->quantum;
 379         }
 380         return skb;
 381 }
 382
 383 static void
 384 sfq_reset(struct Qdisc *sch)
 385 {
 386         struct sk_buff *skb;
 387
 388         while ((skb = sfq_dequeue(sch)) != NULL)
 389                 kfree_skb(skb);
 390 }
 391
 392 static void sfq_perturbation(unsigned long arg)
 393 {
 394         struct Qdisc *sch = (struct Qdisc *)arg;
 395         struct sfq_sched_data *q = qdisc_priv(sch);
 396
 397         q->perturbation = net_random();
 398
 399         if (q->perturb_period)
 400                 mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
 401 }
 402
 403 static int sfq_change(struct Qdisc *sch, struct nlattr *opt)
 404 {
 405         struct sfq_sched_data *q = qdisc_priv(sch);
 406         struct tc_sfq_qopt *ctl = nla_data(opt);
 407         unsigned int qlen;
 408
 409         if (opt->nla_len < nla_attr_size(sizeof(*ctl)))
 410                 return -EINVAL;
 411
 412         sch_tree_lock(sch);
 413         q->quantum = ctl->quantum ? : psched_mtu(qdisc_dev(sch));
 414         q->perturb_period = ctl->perturb_period * HZ;
 415         if (ctl->limit)
 416                 q->limit = min_t(u32, ctl->limit, SFQ_DEPTH - 1);
 417
 418         qlen = sch->q.qlen;
 419         while (sch->q.qlen > q->limit)
 420                 sfq_drop(sch);
 421         qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen);
 422
 423         del_timer(&q->perturb_timer);
 424         if (q->perturb_period) {
 425                 mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
 426                 q->perturbation = net_random();
 427         }
 428         sch_tree_unlock(sch);
 429         return 0;
 430 }
 431
 432 static int sfq_init(struct Qdisc *sch, struct nlattr *opt)
 433 {
 434         struct sfq_sched_data *q = qdisc_priv(sch);
 435         int i;
 436
 437         q->perturb_timer.function = sfq_perturbation;
 438         q->perturb_timer.data = (unsigned long)sch;
 439         init_timer_deferrable(&q->perturb_timer);
 440
 441         for (i = 0; i < SFQ_HASH_DIVISOR; i++)
 442                 q->ht[i] = SFQ_DEPTH;
 443
 444         for (i = 0; i < SFQ_DEPTH; i++) {
 445                 skb_queue_head_init(&q->qs[i]);
 446                 q->dep[i + SFQ_DEPTH].next = i + SFQ_DEPTH;
 447                 q->dep[i + SFQ_DEPTH].prev = i + SFQ_DEPTH;
 448         }
 449
 450         q->limit = SFQ_DEPTH - 1;
 451         q->max_depth = 0;
 452         q->tail = SFQ_DEPTH;
 453         if (opt == NULL) {
 454                 q->quantum = psched_mtu(qdisc_dev(sch));
 455                 q->perturb_period = 0;
 456                 q->perturbation = net_random();
 457         } else {
 458                 int err = sfq_change(sch, opt);
 459                 if (err)
 460                         return err;
 461         }
 462
 463         for (i = 0; i < SFQ_DEPTH; i++)
 464                 sfq_link(q, i);
 465         return 0;
 466 }
 467
 468 static void sfq_destroy(struct Qdisc *sch)
 469 {
 470         struct sfq_sched_data *q = qdisc_priv(sch);
 471
 472         tcf_destroy_chain(&q->filter_list);
 473         q->perturb_period = 0;
 474         del_timer_sync(&q->perturb_timer);
 475 }
 476
 477 static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
 478 {
 479         struct sfq_sched_data *q = qdisc_priv(sch);
 480         unsigned char *b = skb_tail_pointer(skb);
 481         struct tc_sfq_qopt opt;
 482
 483         opt.quantum = q->quantum;
 484         opt.perturb_period = q->perturb_period / HZ;
 485
 486         opt.limit = q->limit;
 487         opt.divisor = SFQ_HASH_DIVISOR;
 488         opt.flows = q->limit;
 489
 490         NLA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
 491
 492         return skb->len;
 493
 494 nla_put_failure:
 495         nlmsg_trim(skb, b);
 496         return -1;
 497 }
 498
 499 static int sfq_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
 500                             struct nlattr **tca, unsigned long *arg)
 501 {
 502         return -EOPNOTSUPP;
 503 }
 504
 505 static unsigned long sfq_get(struct Qdisc *sch, u32 classid)
 506 {
 507         return 0;
 508 }
 509
 510 static struct tcf_proto **sfq_find_tcf(struct Qdisc *sch, unsigned long cl)
 511 {
 512         struct sfq_sched_data *q = qdisc_priv(sch);
 513
 514         if (cl)
 515                 return NULL;
 516         return &q->filter_list;
 517 }
 518
 519 static int sfq_dump_class(struct Qdisc *sch, unsigned long cl,
 520                           struct sk_buff *skb, struct tcmsg *tcm)
 521 {
 522         tcm->tcm_handle |= TC_H_MIN(cl);
 523         return 0;
 524 }
 525
 526 static int sfq_dump_class_stats(struct Qdisc *sch, unsigned long cl,
 527                                 struct gnet_dump *d)
 528 {
 529         struct sfq_sched_data *q = qdisc_priv(sch);
 530         sfq_index idx = q->ht[cl-1];
 531         struct gnet_stats_queue qs = { .qlen = q->qs[idx].qlen };
 532         struct tc_sfq_xstats xstats = { .allot = q->allot[idx] };
 533
 534         if (gnet_stats_copy_queue(d, &qs) < 0)
 535                 return -1;
 536         return gnet_stats_copy_app(d, &xstats, sizeof(xstats));
 537 }
 538
 539 static void sfq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
 540 {
 541         struct sfq_sched_data *q = qdisc_priv(sch);
 542         unsigned int i;
 543
 544         if (arg->stop)
 545                 return;
 546
 547         for (i = 0; i < SFQ_HASH_DIVISOR; i++) {
 548                 if (q->ht[i] == SFQ_DEPTH ||
 549                     arg->count < arg->skip) {
 550                         arg->count++;
 551                         continue;
 552                 }
 553                 if (arg->fn(sch, i + 1, arg) < 0) {
 554                         arg->stop = 1;
 555                         break;
 556                 }
 557                 arg->count++;
 558         }
 559 }
 560
 561 static const struct Qdisc_class_ops sfq_class_ops = {
 562         .get            =       sfq_get,
 563         .change         =       sfq_change_class,
 564         .tcf_chain      =       sfq_find_tcf,
 565         .dump           =       sfq_dump_class,
 566         .dump_stats     =       sfq_dump_class_stats,
 567         .walk           =       sfq_walk,
 568 };
 569
 570 static struct Qdisc_ops sfq_qdisc_ops __read_mostly = {
 571         .cl_ops         =       &sfq_class_ops,
 572         .id             =       "sfq",
 573         .priv_size      =       sizeof(struct sfq_sched_data),
 574         .enqueue        =       sfq_enqueue,
 575         .dequeue        =       sfq_dequeue,
 576         .peek           =       sfq_peek,
 577         .drop           =       sfq_drop,
 578         .init           =       sfq_init,
 579         .reset          =       sfq_reset,
 580         .destroy        =       sfq_destroy,
 581         .change         =       NULL,
 582         .dump           =       sfq_dump,
 583         .owner          =       THIS_MODULE,
 584 };
 585
 586 static int __init sfq_module_init(void)
 587 {
 588         return register_qdisc(&sfq_qdisc_ops);
 589 }
 590 static void __exit sfq_module_exit(void)
 591 {
 592         unregister_qdisc(&sfq_qdisc_ops);
 593 }
 594 module_init(sfq_module_init)
 595 module_exit(sfq_module_exit)
 596 MODULE_LICENSE("GPL");