git.oblomov.eu Git - linux-2.6/blob - 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                 return len;
 236         }
 237
 238         if (d == 1) {
 239                 /* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
 240                 d = q->next[q->tail];
 241                 q->next[q->tail] = q->next[d];
 242                 q->allot[q->next[d]] += q->quantum;
 243                 skb = q->qs[d].prev;
 244                 len = skb->len;
 245                 __skb_unlink(skb, &q->qs[d]);
 246                 kfree_skb(skb);
 247                 sfq_dec(q, d);
 248                 sch->q.qlen--;
 249                 q->ht[q->hash[d]] = SFQ_DEPTH;
 250                 sch->qstats.drops++;
 251                 return len;
 252         }
 253
 254         return 0;
 255 }
 256
 257 static int
 258 sfq_enqueue(struct sk_buff *skb, struct Qdisc* sch)
 259 {
 260         struct sfq_sched_data *q = qdisc_priv(sch);
 261         unsigned hash = sfq_hash(q, skb);
 262         sfq_index x;
 263
 264         x = q->ht[hash];
 265         if (x == SFQ_DEPTH) {
 266                 q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
 267                 q->hash[x] = hash;
 268         }
 269         __skb_queue_tail(&q->qs[x], skb);
 270         sfq_inc(q, x);
 271         if (q->qs[x].qlen == 1) {               /* The flow is new */
 272                 if (q->tail == SFQ_DEPTH) {     /* It is the first flow */
 273                         q->tail = x;
 274                         q->next[x] = x;
 275                         q->allot[x] = q->quantum;
 276                 } else {
 277                         q->next[x] = q->next[q->tail];
 278                         q->next[q->tail] = x;
 279                         q->tail = x;
 280                 }
 281         }
 282         if (++sch->q.qlen < q->limit-1) {
 283                 sch->bstats.bytes += skb->len;
 284                 sch->bstats.packets++;
 285                 return 0;
 286         }
 287
 288         sfq_drop(sch);
 289         return NET_XMIT_CN;
 290 }
 291
 292 static int
 293 sfq_requeue(struct sk_buff *skb, struct Qdisc* sch)
 294 {
 295         struct sfq_sched_data *q = qdisc_priv(sch);
 296         unsigned hash = sfq_hash(q, skb);
 297         sfq_index x;
 298
 299         x = q->ht[hash];
 300         if (x == SFQ_DEPTH) {
 301                 q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
 302                 q->hash[x] = hash;
 303         }
 304         __skb_queue_head(&q->qs[x], skb);
 305         sfq_inc(q, x);
 306         if (q->qs[x].qlen == 1) {               /* The flow is new */
 307                 if (q->tail == SFQ_DEPTH) {     /* It is the first flow */
 308                         q->tail = x;
 309                         q->next[x] = x;
 310                         q->allot[x] = q->quantum;
 311                 } else {
 312                         q->next[x] = q->next[q->tail];
 313                         q->next[q->tail] = x;
 314                         q->tail = x;
 315                 }
 316         }
 317         if (++sch->q.qlen < q->limit - 1) {
 318                 sch->qstats.requeues++;
 319                 return 0;
 320         }
 321
 322         sch->qstats.drops++;
 323         sfq_drop(sch);
 324         return NET_XMIT_CN;
 325 }
 326
 327
 328
 329
 330 static struct sk_buff *
 331 sfq_dequeue(struct Qdisc* sch)
 332 {
 333         struct sfq_sched_data *q = qdisc_priv(sch);
 334         struct sk_buff *skb;
 335         sfq_index a, old_a;
 336
 337         /* No active slots */
 338         if (q->tail == SFQ_DEPTH)
 339                 return NULL;
 340
 341         a = old_a = q->next[q->tail];
 342
 343         /* Grab packet */
 344         skb = __skb_dequeue(&q->qs[a]);
 345         sfq_dec(q, a);
 346         sch->q.qlen--;
 347
 348         /* Is the slot empty? */
 349         if (q->qs[a].qlen == 0) {
 350                 q->ht[q->hash[a]] = SFQ_DEPTH;
 351                 a = q->next[a];
 352                 if (a == old_a) {
 353                         q->tail = SFQ_DEPTH;
 354                         return skb;
 355                 }
 356                 q->next[q->tail] = a;
 357                 q->allot[a] += q->quantum;
 358         } else if ((q->allot[a] -= skb->len) <= 0) {
 359                 q->tail = a;
 360                 a = q->next[a];
 361                 q->allot[a] += q->quantum;
 362         }
 363         return skb;
 364 }
 365
 366 static void
 367 sfq_reset(struct Qdisc* sch)
 368 {
 369         struct sk_buff *skb;
 370
 371         while ((skb = sfq_dequeue(sch)) != NULL)
 372                 kfree_skb(skb);
 373 }
 374
 375 static void sfq_perturbation(unsigned long arg)
 376 {
 377         struct Qdisc *sch = (struct Qdisc*)arg;
 378         struct sfq_sched_data *q = qdisc_priv(sch);
 379
 380         q->perturbation = net_random()&0x1F;
 381
 382         if (q->perturb_period) {
 383                 q->perturb_timer.expires = jiffies + q->perturb_period;
 384                 add_timer(&q->perturb_timer);
 385         }
 386 }
 387
 388 static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
 389 {
 390         struct sfq_sched_data *q = qdisc_priv(sch);
 391         struct tc_sfq_qopt *ctl = RTA_DATA(opt);
 392
 393         if (opt->rta_len < RTA_LENGTH(sizeof(*ctl)))
 394                 return -EINVAL;
 395
 396         sch_tree_lock(sch);
 397         q->quantum = ctl->quantum ? : psched_mtu(sch->dev);
 398         q->perturb_period = ctl->perturb_period*HZ;
 399         if (ctl->limit)
 400                 q->limit = min_t(u32, ctl->limit, SFQ_DEPTH);
 401
 402         while (sch->q.qlen >= q->limit-1)
 403                 sfq_drop(sch);
 404
 405         del_timer(&q->perturb_timer);
 406         if (q->perturb_period) {
 407                 q->perturb_timer.expires = jiffies + q->perturb_period;
 408                 add_timer(&q->perturb_timer);
 409         }
 410         sch_tree_unlock(sch);
 411         return 0;
 412 }
 413
 414 static int sfq_init(struct Qdisc *sch, struct rtattr *opt)
 415 {
 416         struct sfq_sched_data *q = qdisc_priv(sch);
 417         int i;
 418
 419         init_timer(&q->perturb_timer);
 420         q->perturb_timer.data = (unsigned long)sch;
 421         q->perturb_timer.function = sfq_perturbation;
 422
 423         for (i=0; i<SFQ_HASH_DIVISOR; i++)
 424                 q->ht[i] = SFQ_DEPTH;
 425         for (i=0; i<SFQ_DEPTH; i++) {
 426                 skb_queue_head_init(&q->qs[i]);
 427                 q->dep[i+SFQ_DEPTH].next = i+SFQ_DEPTH;
 428                 q->dep[i+SFQ_DEPTH].prev = i+SFQ_DEPTH;
 429         }
 430         q->limit = SFQ_DEPTH;
 431         q->max_depth = 0;
 432         q->tail = SFQ_DEPTH;
 433         if (opt == NULL) {
 434                 q->quantum = psched_mtu(sch->dev);
 435                 q->perturb_period = 0;
 436         } else {
 437                 int err = sfq_change(sch, opt);
 438                 if (err)
 439                         return err;
 440         }
 441         for (i=0; i<SFQ_DEPTH; i++)
 442                 sfq_link(q, i);
 443         return 0;
 444 }
 445
 446 static void sfq_destroy(struct Qdisc *sch)
 447 {
 448         struct sfq_sched_data *q = qdisc_priv(sch);
 449         del_timer(&q->perturb_timer);
 450 }
 451
 452 static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
 453 {
 454         struct sfq_sched_data *q = qdisc_priv(sch);
 455         unsigned char    *b = skb->tail;
 456         struct tc_sfq_qopt opt;
 457
 458         opt.quantum = q->quantum;
 459         opt.perturb_period = q->perturb_period/HZ;
 460
 461         opt.limit = q->limit;
 462         opt.divisor = SFQ_HASH_DIVISOR;
 463         opt.flows = q->limit;
 464
 465         RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
 466
 467         return skb->len;
 468
 469 rtattr_failure:
 470         skb_trim(skb, b - skb->data);
 471         return -1;
 472 }
 473
 474 static struct Qdisc_ops sfq_qdisc_ops = {
 475         .next           =       NULL,
 476         .cl_ops         =       NULL,
 477         .id             =       "sfq",
 478         .priv_size      =       sizeof(struct sfq_sched_data),
 479         .enqueue        =       sfq_enqueue,
 480         .dequeue        =       sfq_dequeue,
 481         .requeue        =       sfq_requeue,
 482         .drop           =       sfq_drop,
 483         .init           =       sfq_init,
 484         .reset          =       sfq_reset,
 485         .destroy        =       sfq_destroy,
 486         .change         =       NULL,
 487         .dump           =       sfq_dump,
 488         .owner          =       THIS_MODULE,
 489 };
 490
 491 static int __init sfq_module_init(void)
 492 {
 493         return register_qdisc(&sfq_qdisc_ops);
 494 }
 495 static void __exit sfq_module_exit(void)
 496 {
 497         unregister_qdisc(&sfq_qdisc_ops);
 498 }
 499 module_init(sfq_module_init)
 500 module_exit(sfq_module_exit)
 501 MODULE_LICENSE("GPL");