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 <asm/uaccess.h>
  14 #include <asm/system.h>
  15 #include <linux/bitops.h>
  16 #include <linux/types.h>
  17 #include <linux/kernel.h>
  18 #include <linux/jiffies.h>
  19 #include <linux/string.h>
  20 #include <linux/mm.h>
  21 #include <linux/socket.h>
  22 #include <linux/sockios.h>
  23 #include <linux/in.h>
  24 #include <linux/errno.h>
  25 #include <linux/interrupt.h>
  26 #include <linux/if_ether.h>
  27 #include <linux/inet.h>
  28 #include <linux/netdevice.h>
  29 #include <linux/etherdevice.h>
  30 #include <linux/notifier.h>
  31 #include <linux/init.h>
  32 #include <net/ip.h>
  33 #include <net/netlink.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                 const struct iphdr *iph = ip_hdr(skb);
 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_UDPLITE ||
 148                      iph->protocol == IPPROTO_SCTP ||
 149                      iph->protocol == IPPROTO_DCCP ||
 150                      iph->protocol == IPPROTO_ESP))
 151                         h2 ^= *(((u32*)iph) + iph->ihl);
 152                 break;
 153         }
 154         case __constant_htons(ETH_P_IPV6):
 155         {
 156                 struct ipv6hdr *iph = ipv6_hdr(skb);
 157                 h = iph->daddr.s6_addr32[3];
 158                 h2 = iph->saddr.s6_addr32[3]^iph->nexthdr;
 159                 if (iph->nexthdr == IPPROTO_TCP ||
 160                     iph->nexthdr == IPPROTO_UDP ||
 161                     iph->nexthdr == IPPROTO_UDPLITE ||
 162                     iph->nexthdr == IPPROTO_SCTP ||
 163                     iph->nexthdr == IPPROTO_DCCP ||
 164                     iph->nexthdr == IPPROTO_ESP)
 165                         h2 ^= *(u32*)&iph[1];
 166                 break;
 167         }
 168         default:
 169                 h = (u32)(unsigned long)skb->dst^skb->protocol;
 170                 h2 = (u32)(unsigned long)skb->sk;
 171         }
 172         return sfq_fold_hash(q, h, h2);
 173 }
 174
 175 static inline void sfq_link(struct sfq_sched_data *q, sfq_index x)
 176 {
 177         sfq_index p, n;
 178         int d = q->qs[x].qlen + SFQ_DEPTH;
 179
 180         p = d;
 181         n = q->dep[d].next;
 182         q->dep[x].next = n;
 183         q->dep[x].prev = p;
 184         q->dep[p].next = q->dep[n].prev = x;
 185 }
 186
 187 static inline void sfq_dec(struct sfq_sched_data *q, sfq_index x)
 188 {
 189         sfq_index p, n;
 190
 191         n = q->dep[x].next;
 192         p = q->dep[x].prev;
 193         q->dep[p].next = n;
 194         q->dep[n].prev = p;
 195
 196         if (n == p && q->max_depth == q->qs[x].qlen + 1)
 197                 q->max_depth--;
 198
 199         sfq_link(q, x);
 200 }
 201
 202 static inline void sfq_inc(struct sfq_sched_data *q, sfq_index x)
 203 {
 204         sfq_index p, n;
 205         int d;
 206
 207         n = q->dep[x].next;
 208         p = q->dep[x].prev;
 209         q->dep[p].next = n;
 210         q->dep[n].prev = p;
 211         d = q->qs[x].qlen;
 212         if (q->max_depth < d)
 213                 q->max_depth = d;
 214
 215         sfq_link(q, x);
 216 }
 217
 218 static unsigned int sfq_drop(struct Qdisc *sch)
 219 {
 220         struct sfq_sched_data *q = qdisc_priv(sch);
 221         sfq_index d = q->max_depth;
 222         struct sk_buff *skb;
 223         unsigned int len;
 224
 225         /* Queue is full! Find the longest slot and
 226            drop a packet from it */
 227
 228         if (d > 1) {
 229                 sfq_index x = q->dep[d+SFQ_DEPTH].next;
 230                 skb = q->qs[x].prev;
 231                 len = skb->len;
 232                 __skb_unlink(skb, &q->qs[x]);
 233                 kfree_skb(skb);
 234                 sfq_dec(q, x);
 235                 sch->q.qlen--;
 236                 sch->qstats.drops++;
 237                 sch->qstats.backlog -= len;
 238                 return len;
 239         }
 240
 241         if (d == 1) {
 242                 /* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
 243                 d = q->next[q->tail];
 244                 q->next[q->tail] = q->next[d];
 245                 q->allot[q->next[d]] += q->quantum;
 246                 skb = q->qs[d].prev;
 247                 len = skb->len;
 248                 __skb_unlink(skb, &q->qs[d]);
 249                 kfree_skb(skb);
 250                 sfq_dec(q, d);
 251                 sch->q.qlen--;
 252                 q->ht[q->hash[d]] = SFQ_DEPTH;
 253                 sch->qstats.drops++;
 254                 sch->qstats.backlog -= len;
 255                 return len;
 256         }
 257
 258         return 0;
 259 }
 260
 261 static int
 262 sfq_enqueue(struct sk_buff *skb, struct Qdisc* sch)
 263 {
 264         struct sfq_sched_data *q = qdisc_priv(sch);
 265         unsigned hash = sfq_hash(q, skb);
 266         sfq_index x;
 267
 268         x = q->ht[hash];
 269         if (x == SFQ_DEPTH) {
 270                 q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
 271                 q->hash[x] = hash;
 272         }
 273         sch->qstats.backlog += skb->len;
 274         __skb_queue_tail(&q->qs[x], skb);
 275         sfq_inc(q, x);
 276         if (q->qs[x].qlen == 1) {               /* The flow is new */
 277                 if (q->tail == SFQ_DEPTH) {     /* It is the first flow */
 278                         q->tail = x;
 279                         q->next[x] = x;
 280                         q->allot[x] = q->quantum;
 281                 } else {
 282                         q->next[x] = q->next[q->tail];
 283                         q->next[q->tail] = x;
 284                         q->tail = x;
 285                 }
 286         }
 287         if (++sch->q.qlen < q->limit-1) {
 288                 sch->bstats.bytes += skb->len;
 289                 sch->bstats.packets++;
 290                 return 0;
 291         }
 292
 293         sfq_drop(sch);
 294         return NET_XMIT_CN;
 295 }
 296
 297 static int
 298 sfq_requeue(struct sk_buff *skb, struct Qdisc* sch)
 299 {
 300         struct sfq_sched_data *q = qdisc_priv(sch);
 301         unsigned hash = sfq_hash(q, skb);
 302         sfq_index x;
 303
 304         x = q->ht[hash];
 305         if (x == SFQ_DEPTH) {
 306                 q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
 307                 q->hash[x] = hash;
 308         }
 309         sch->qstats.backlog += skb->len;
 310         __skb_queue_head(&q->qs[x], skb);
 311         sfq_inc(q, x);
 312         if (q->qs[x].qlen == 1) {               /* The flow is new */
 313                 if (q->tail == SFQ_DEPTH) {     /* It is the first flow */
 314                         q->tail = x;
 315                         q->next[x] = x;
 316                         q->allot[x] = q->quantum;
 317                 } else {
 318                         q->next[x] = q->next[q->tail];
 319                         q->next[q->tail] = x;
 320                         q->tail = x;
 321                 }
 322         }
 323         if (++sch->q.qlen < q->limit - 1) {
 324                 sch->qstats.requeues++;
 325                 return 0;
 326         }
 327
 328         sch->qstats.drops++;
 329         sfq_drop(sch);
 330         return NET_XMIT_CN;
 331 }
 332
 333
 334
 335
 336 static struct sk_buff *
 337 sfq_dequeue(struct Qdisc* sch)
 338 {
 339         struct sfq_sched_data *q = qdisc_priv(sch);
 340         struct sk_buff *skb;
 341         sfq_index a, old_a;
 342
 343         /* No active slots */
 344         if (q->tail == SFQ_DEPTH)
 345                 return NULL;
 346
 347         a = old_a = q->next[q->tail];
 348
 349         /* Grab packet */
 350         skb = __skb_dequeue(&q->qs[a]);
 351         sfq_dec(q, a);
 352         sch->q.qlen--;
 353         sch->qstats.backlog -= skb->len;
 354
 355         /* Is the slot empty? */
 356         if (q->qs[a].qlen == 0) {
 357                 q->ht[q->hash[a]] = SFQ_DEPTH;
 358                 a = q->next[a];
 359                 if (a == old_a) {
 360                         q->tail = SFQ_DEPTH;
 361                         return skb;
 362                 }
 363                 q->next[q->tail] = a;
 364                 q->allot[a] += q->quantum;
 365         } else if ((q->allot[a] -= skb->len) <= 0) {
 366                 q->tail = a;
 367                 a = q->next[a];
 368                 q->allot[a] += q->quantum;
 369         }
 370         return skb;
 371 }
 372
 373 static void
 374 sfq_reset(struct Qdisc* sch)
 375 {
 376         struct sk_buff *skb;
 377
 378         while ((skb = sfq_dequeue(sch)) != NULL)
 379                 kfree_skb(skb);
 380 }
 381
 382 static void sfq_perturbation(unsigned long arg)
 383 {
 384         struct Qdisc *sch = (struct Qdisc*)arg;
 385         struct sfq_sched_data *q = qdisc_priv(sch);
 386
 387         q->perturbation = net_random()&0x1F;
 388
 389         if (q->perturb_period) {
 390                 q->perturb_timer.expires = jiffies + q->perturb_period;
 391                 add_timer(&q->perturb_timer);
 392         }
 393 }
 394
 395 static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
 396 {
 397         struct sfq_sched_data *q = qdisc_priv(sch);
 398         struct tc_sfq_qopt *ctl = RTA_DATA(opt);
 399         unsigned int qlen;
 400
 401         if (opt->rta_len < RTA_LENGTH(sizeof(*ctl)))
 402                 return -EINVAL;
 403
 404         sch_tree_lock(sch);
 405         q->quantum = ctl->quantum ? : psched_mtu(sch->dev);
 406         q->perturb_period = ctl->perturb_period*HZ;
 407         if (ctl->limit)
 408                 q->limit = min_t(u32, ctl->limit, SFQ_DEPTH);
 409
 410         qlen = sch->q.qlen;
 411         while (sch->q.qlen >= q->limit-1)
 412                 sfq_drop(sch);
 413         qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen);
 414
 415         del_timer(&q->perturb_timer);
 416         if (q->perturb_period) {
 417                 q->perturb_timer.expires = jiffies + q->perturb_period;
 418                 add_timer(&q->perturb_timer);
 419         }
 420         sch_tree_unlock(sch);
 421         return 0;
 422 }
 423
 424 static int sfq_init(struct Qdisc *sch, struct rtattr *opt)
 425 {
 426         struct sfq_sched_data *q = qdisc_priv(sch);
 427         int i;
 428
 429         init_timer(&q->perturb_timer);
 430         q->perturb_timer.data = (unsigned long)sch;
 431         q->perturb_timer.function = sfq_perturbation;
 432
 433         for (i=0; i<SFQ_HASH_DIVISOR; i++)
 434                 q->ht[i] = SFQ_DEPTH;
 435         for (i=0; i<SFQ_DEPTH; i++) {
 436                 skb_queue_head_init(&q->qs[i]);
 437                 q->dep[i+SFQ_DEPTH].next = i+SFQ_DEPTH;
 438                 q->dep[i+SFQ_DEPTH].prev = i+SFQ_DEPTH;
 439         }
 440         q->limit = SFQ_DEPTH;
 441         q->max_depth = 0;
 442         q->tail = SFQ_DEPTH;
 443         if (opt == NULL) {
 444                 q->quantum = psched_mtu(sch->dev);
 445                 q->perturb_period = 0;
 446         } else {
 447                 int err = sfq_change(sch, opt);
 448                 if (err)
 449                         return err;
 450         }
 451         for (i=0; i<SFQ_DEPTH; i++)
 452                 sfq_link(q, i);
 453         return 0;
 454 }
 455
 456 static void sfq_destroy(struct Qdisc *sch)
 457 {
 458         struct sfq_sched_data *q = qdisc_priv(sch);
 459         del_timer(&q->perturb_timer);
 460 }
 461
 462 static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
 463 {
 464         struct sfq_sched_data *q = qdisc_priv(sch);
 465         unsigned char *b = skb_tail_pointer(skb);
 466         struct tc_sfq_qopt opt;
 467
 468         opt.quantum = q->quantum;
 469         opt.perturb_period = q->perturb_period/HZ;
 470
 471         opt.limit = q->limit;
 472         opt.divisor = SFQ_HASH_DIVISOR;
 473         opt.flows = q->limit;
 474
 475         RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
 476
 477         return skb->len;
 478
 479 rtattr_failure:
 480         nlmsg_trim(skb, b);
 481         return -1;
 482 }
 483
 484 static struct Qdisc_ops sfq_qdisc_ops = {
 485         .next           =       NULL,
 486         .cl_ops         =       NULL,
 487         .id             =       "sfq",
 488         .priv_size      =       sizeof(struct sfq_sched_data),
 489         .enqueue        =       sfq_enqueue,
 490         .dequeue        =       sfq_dequeue,
 491         .requeue        =       sfq_requeue,
 492         .drop           =       sfq_drop,
 493         .init           =       sfq_init,
 494         .reset          =       sfq_reset,
 495         .destroy        =       sfq_destroy,
 496         .change         =       NULL,
 497         .dump           =       sfq_dump,
 498         .owner          =       THIS_MODULE,
 499 };
 500
 501 static int __init sfq_module_init(void)
 502 {
 503         return register_qdisc(&sfq_qdisc_ops);
 504 }
 505 static void __exit sfq_module_exit(void)
 506 {
 507         unregister_qdisc(&sfq_qdisc_ops);
 508 }
 509 module_init(sfq_module_init)
 510 module_exit(sfq_module_exit)
 511 MODULE_LICENSE("GPL");