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 timer_list perturb_timer;
  99         u32             perturbation;
 100         sfq_index       tail;           /* Index of current slot in round */
 101         sfq_index       max_depth;      /* Maximal depth */
 102
 103         sfq_index       ht[SFQ_HASH_DIVISOR];   /* Hash table */
 104         sfq_index       next[SFQ_DEPTH];        /* Active slots link */
 105         short           allot[SFQ_DEPTH];       /* Current allotment per slot */
 106         unsigned short  hash[SFQ_DEPTH];        /* Hash value indexed by slots */
 107         struct sk_buff_head     qs[SFQ_DEPTH];          /* Slot queue */
 108         struct sfq_head dep[SFQ_DEPTH*2];       /* Linked list of slots, indexed by depth */
 109 };
 110
 111 static __inline__ unsigned sfq_fold_hash(struct sfq_sched_data *q, u32 h, u32 h1)
 112 {
 113         return jhash_2words(h, h1, q->perturbation) & (SFQ_HASH_DIVISOR - 1);
 114 }
 115
 116 static unsigned sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb)
 117 {
 118         u32 h, h2;
 119
 120         switch (skb->protocol) {
 121         case __constant_htons(ETH_P_IP):
 122         {
 123                 const struct iphdr *iph = ip_hdr(skb);
 124                 h = iph->daddr;
 125                 h2 = iph->saddr ^ iph->protocol;
 126                 if (!(iph->frag_off&htons(IP_MF|IP_OFFSET)) &&
 127                     (iph->protocol == IPPROTO_TCP ||
 128                      iph->protocol == IPPROTO_UDP ||
 129                      iph->protocol == IPPROTO_UDPLITE ||
 130                      iph->protocol == IPPROTO_SCTP ||
 131                      iph->protocol == IPPROTO_DCCP ||
 132                      iph->protocol == IPPROTO_ESP))
 133                         h2 ^= *(((u32*)iph) + iph->ihl);
 134                 break;
 135         }
 136         case __constant_htons(ETH_P_IPV6):
 137         {
 138                 struct ipv6hdr *iph = ipv6_hdr(skb);
 139                 h = iph->daddr.s6_addr32[3];
 140                 h2 = iph->saddr.s6_addr32[3] ^ iph->nexthdr;
 141                 if (iph->nexthdr == IPPROTO_TCP ||
 142                     iph->nexthdr == IPPROTO_UDP ||
 143                     iph->nexthdr == IPPROTO_UDPLITE ||
 144                     iph->nexthdr == IPPROTO_SCTP ||
 145                     iph->nexthdr == IPPROTO_DCCP ||
 146                     iph->nexthdr == IPPROTO_ESP)
 147                         h2 ^= *(u32*)&iph[1];
 148                 break;
 149         }
 150         default:
 151                 h = (unsigned long)skb->dst ^ skb->protocol;
 152                 h2 = (unsigned long)skb->sk;
 153         }
 154
 155         return sfq_fold_hash(q, h, h2);
 156 }
 157
 158 static inline void sfq_link(struct sfq_sched_data *q, sfq_index x)
 159 {
 160         sfq_index p, n;
 161         int d = q->qs[x].qlen + SFQ_DEPTH;
 162
 163         p = d;
 164         n = q->dep[d].next;
 165         q->dep[x].next = n;
 166         q->dep[x].prev = p;
 167         q->dep[p].next = q->dep[n].prev = x;
 168 }
 169
 170 static inline void sfq_dec(struct sfq_sched_data *q, sfq_index x)
 171 {
 172         sfq_index p, n;
 173
 174         n = q->dep[x].next;
 175         p = q->dep[x].prev;
 176         q->dep[p].next = n;
 177         q->dep[n].prev = p;
 178
 179         if (n == p && q->max_depth == q->qs[x].qlen + 1)
 180                 q->max_depth--;
 181
 182         sfq_link(q, x);
 183 }
 184
 185 static inline void sfq_inc(struct sfq_sched_data *q, sfq_index x)
 186 {
 187         sfq_index p, n;
 188         int d;
 189
 190         n = q->dep[x].next;
 191         p = q->dep[x].prev;
 192         q->dep[p].next = n;
 193         q->dep[n].prev = p;
 194         d = q->qs[x].qlen;
 195         if (q->max_depth < d)
 196                 q->max_depth = d;
 197
 198         sfq_link(q, x);
 199 }
 200
 201 static unsigned int sfq_drop(struct Qdisc *sch)
 202 {
 203         struct sfq_sched_data *q = qdisc_priv(sch);
 204         sfq_index d = q->max_depth;
 205         struct sk_buff *skb;
 206         unsigned int len;
 207
 208         /* Queue is full! Find the longest slot and
 209            drop a packet from it */
 210
 211         if (d > 1) {
 212                 sfq_index x = q->dep[d + SFQ_DEPTH].next;
 213                 skb = q->qs[x].prev;
 214                 len = skb->len;
 215                 __skb_unlink(skb, &q->qs[x]);
 216                 kfree_skb(skb);
 217                 sfq_dec(q, x);
 218                 sch->q.qlen--;
 219                 sch->qstats.drops++;
 220                 sch->qstats.backlog -= len;
 221                 return len;
 222         }
 223
 224         if (d == 1) {
 225                 /* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
 226                 d = q->next[q->tail];
 227                 q->next[q->tail] = q->next[d];
 228                 q->allot[q->next[d]] += q->quantum;
 229                 skb = q->qs[d].prev;
 230                 len = skb->len;
 231                 __skb_unlink(skb, &q->qs[d]);
 232                 kfree_skb(skb);
 233                 sfq_dec(q, d);
 234                 sch->q.qlen--;
 235                 q->ht[q->hash[d]] = SFQ_DEPTH;
 236                 sch->qstats.drops++;
 237                 sch->qstats.backlog -= len;
 238                 return len;
 239         }
 240
 241         return 0;
 242 }
 243
 244 static int
 245 sfq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 246 {
 247         struct sfq_sched_data *q = qdisc_priv(sch);
 248         unsigned hash = sfq_hash(q, skb);
 249         sfq_index x;
 250
 251         x = q->ht[hash];
 252         if (x == SFQ_DEPTH) {
 253                 q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
 254                 q->hash[x] = hash;
 255         }
 256
 257         /* If selected queue has length q->limit, this means that
 258          * all another queues are empty and that we do simple tail drop,
 259          * i.e. drop _this_ packet.
 260          */
 261         if (q->qs[x].qlen >= q->limit)
 262                 return qdisc_drop(skb, sch);
 263
 264         sch->qstats.backlog += skb->len;
 265         __skb_queue_tail(&q->qs[x], skb);
 266         sfq_inc(q, x);
 267         if (q->qs[x].qlen == 1) {               /* The flow is new */
 268                 if (q->tail == SFQ_DEPTH) {     /* It is the first flow */
 269                         q->tail = x;
 270                         q->next[x] = x;
 271                         q->allot[x] = q->quantum;
 272                 } else {
 273                         q->next[x] = q->next[q->tail];
 274                         q->next[q->tail] = x;
 275                         q->tail = x;
 276                 }
 277         }
 278         if (++sch->q.qlen <= q->limit) {
 279                 sch->bstats.bytes += skb->len;
 280                 sch->bstats.packets++;
 281                 return 0;
 282         }
 283
 284         sfq_drop(sch);
 285         return NET_XMIT_CN;
 286 }
 287
 288 static int
 289 sfq_requeue(struct sk_buff *skb, struct Qdisc *sch)
 290 {
 291         struct sfq_sched_data *q = qdisc_priv(sch);
 292         unsigned hash = sfq_hash(q, skb);
 293         sfq_index x;
 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         sch->qstats.backlog += skb->len;
 302         __skb_queue_head(&q->qs[x], skb);
 303         /* If selected queue has length q->limit+1, this means that
 304          * all another queues are empty and we do simple tail drop.
 305          * This packet is still requeued at head of queue, tail packet
 306          * is dropped.
 307          */
 308         if (q->qs[x].qlen > q->limit) {
 309                 skb = q->qs[x].prev;
 310                 __skb_unlink(skb, &q->qs[x]);
 311                 sch->qstats.drops++;
 312                 sch->qstats.backlog -= skb->len;
 313                 kfree_skb(skb);
 314                 return NET_XMIT_CN;
 315         }
 316
 317         sfq_inc(q, x);
 318         if (q->qs[x].qlen == 1) {               /* The flow is new */
 319                 if (q->tail == SFQ_DEPTH) {     /* It is the first flow */
 320                         q->tail = x;
 321                         q->next[x] = x;
 322                         q->allot[x] = q->quantum;
 323                 } else {
 324                         q->next[x] = q->next[q->tail];
 325                         q->next[q->tail] = x;
 326                         q->tail = x;
 327                 }
 328         }
 329
 330         if (++sch->q.qlen <= q->limit) {
 331                 sch->qstats.requeues++;
 332                 return 0;
 333         }
 334
 335         sch->qstats.drops++;
 336         sfq_drop(sch);
 337         return NET_XMIT_CN;
 338 }
 339
 340
 341
 342
 343 static struct sk_buff *
 344 sfq_dequeue(struct Qdisc *sch)
 345 {
 346         struct sfq_sched_data *q = qdisc_priv(sch);
 347         struct sk_buff *skb;
 348         sfq_index a, old_a;
 349
 350         /* No active slots */
 351         if (q->tail == SFQ_DEPTH)
 352                 return NULL;
 353
 354         a = old_a = q->next[q->tail];
 355
 356         /* Grab packet */
 357         skb = __skb_dequeue(&q->qs[a]);
 358         sfq_dec(q, a);
 359         sch->q.qlen--;
 360         sch->qstats.backlog -= skb->len;
 361
 362         /* Is the slot empty? */
 363         if (q->qs[a].qlen == 0) {
 364                 q->ht[q->hash[a]] = SFQ_DEPTH;
 365                 a = q->next[a];
 366                 if (a == old_a) {
 367                         q->tail = SFQ_DEPTH;
 368                         return skb;
 369                 }
 370                 q->next[q->tail] = a;
 371                 q->allot[a] += q->quantum;
 372         } else if ((q->allot[a] -= skb->len) <= 0) {
 373                 q->tail = a;
 374                 a = q->next[a];
 375                 q->allot[a] += q->quantum;
 376         }
 377         return skb;
 378 }
 379
 380 static void
 381 sfq_reset(struct Qdisc *sch)
 382 {
 383         struct sk_buff *skb;
 384
 385         while ((skb = sfq_dequeue(sch)) != NULL)
 386                 kfree_skb(skb);
 387 }
 388
 389 static void sfq_perturbation(unsigned long arg)
 390 {
 391         struct Qdisc *sch = (struct Qdisc *)arg;
 392         struct sfq_sched_data *q = qdisc_priv(sch);
 393
 394         q->perturbation = net_random();
 395
 396         if (q->perturb_period)
 397                 mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
 398 }
 399
 400 static int sfq_change(struct Qdisc *sch, struct nlattr *opt)
 401 {
 402         struct sfq_sched_data *q = qdisc_priv(sch);
 403         struct tc_sfq_qopt *ctl = nla_data(opt);
 404         unsigned int qlen;
 405
 406         if (opt->nla_len < nla_attr_size(sizeof(*ctl)))
 407                 return -EINVAL;
 408
 409         sch_tree_lock(sch);
 410         q->quantum = ctl->quantum ? : psched_mtu(sch->dev);
 411         q->perturb_period = ctl->perturb_period * HZ;
 412         if (ctl->limit)
 413                 q->limit = min_t(u32, ctl->limit, SFQ_DEPTH - 1);
 414
 415         qlen = sch->q.qlen;
 416         while (sch->q.qlen > q->limit)
 417                 sfq_drop(sch);
 418         qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen);
 419
 420         del_timer(&q->perturb_timer);
 421         if (q->perturb_period) {
 422                 mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
 423                 q->perturbation = net_random();
 424         }
 425         sch_tree_unlock(sch);
 426         return 0;
 427 }
 428
 429 static int sfq_init(struct Qdisc *sch, struct nlattr *opt)
 430 {
 431         struct sfq_sched_data *q = qdisc_priv(sch);
 432         int i;
 433
 434         q->perturb_timer.function = sfq_perturbation;
 435         q->perturb_timer.data = (unsigned long)sch;;
 436         init_timer_deferrable(&q->perturb_timer);
 437
 438         for (i = 0; i < SFQ_HASH_DIVISOR; i++)
 439                 q->ht[i] = SFQ_DEPTH;
 440
 441         for (i = 0; i < SFQ_DEPTH; i++) {
 442                 skb_queue_head_init(&q->qs[i]);
 443                 q->dep[i + SFQ_DEPTH].next = i + SFQ_DEPTH;
 444                 q->dep[i + SFQ_DEPTH].prev = i + SFQ_DEPTH;
 445         }
 446
 447         q->limit = SFQ_DEPTH - 1;
 448         q->max_depth = 0;
 449         q->tail = SFQ_DEPTH;
 450         if (opt == NULL) {
 451                 q->quantum = psched_mtu(sch->dev);
 452                 q->perturb_period = 0;
 453                 q->perturbation = net_random();
 454         } else {
 455                 int err = sfq_change(sch, opt);
 456                 if (err)
 457                         return err;
 458         }
 459
 460         for (i = 0; i < SFQ_DEPTH; i++)
 461                 sfq_link(q, i);
 462         return 0;
 463 }
 464
 465 static void sfq_destroy(struct Qdisc *sch)
 466 {
 467         struct sfq_sched_data *q = qdisc_priv(sch);
 468         del_timer(&q->perturb_timer);
 469 }
 470
 471 static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
 472 {
 473         struct sfq_sched_data *q = qdisc_priv(sch);
 474         unsigned char *b = skb_tail_pointer(skb);
 475         struct tc_sfq_qopt opt;
 476
 477         opt.quantum = q->quantum;
 478         opt.perturb_period = q->perturb_period / HZ;
 479
 480         opt.limit = q->limit;
 481         opt.divisor = SFQ_HASH_DIVISOR;
 482         opt.flows = q->limit;
 483
 484         NLA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
 485
 486         return skb->len;
 487
 488 nla_put_failure:
 489         nlmsg_trim(skb, b);
 490         return -1;
 491 }
 492
 493 static struct Qdisc_ops sfq_qdisc_ops __read_mostly = {
 494         .next           =       NULL,
 495         .cl_ops         =       NULL,
 496         .id             =       "sfq",
 497         .priv_size      =       sizeof(struct sfq_sched_data),
 498         .enqueue        =       sfq_enqueue,
 499         .dequeue        =       sfq_dequeue,
 500         .requeue        =       sfq_requeue,
 501         .drop           =       sfq_drop,
 502         .init           =       sfq_init,
 503         .reset          =       sfq_reset,
 504         .destroy        =       sfq_destroy,
 505         .change         =       NULL,
 506         .dump           =       sfq_dump,
 507         .owner          =       THIS_MODULE,
 508 };
 509
 510 static int __init sfq_module_init(void)
 511 {
 512         return register_qdisc(&sfq_qdisc_ops);
 513 }
 514 static void __exit sfq_module_exit(void)
 515 {
 516         unregister_qdisc(&sfq_qdisc_ops);
 517 }
 518 module_init(sfq_module_init)
 519 module_exit(sfq_module_exit)
 520 MODULE_LICENSE("GPL");