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