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 <asm/bitops.h>
  17 #include <linux/types.h>
  18 #include <linux/kernel.h>
  19 #include <linux/sched.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
 109 /* Variables */
 110         struct timer_list perturb_timer;
 111         int             perturbation;
 112         sfq_index       tail;           /* Index of current slot in round */
 113         sfq_index       max_depth;      /* Maximal depth */
 114
 115         sfq_index       ht[SFQ_HASH_DIVISOR];   /* Hash table */
 116         sfq_index       next[SFQ_DEPTH];        /* Active slots link */
 117         short           allot[SFQ_DEPTH];       /* Current allotment per slot */
 118         unsigned short  hash[SFQ_DEPTH];        /* Hash value indexed by slots */
 119         struct sk_buff_head     qs[SFQ_DEPTH];          /* Slot queue */
 120         struct sfq_head dep[SFQ_DEPTH*2];       /* Linked list of slots, indexed by depth */
 121 };
 122
 123 static __inline__ unsigned sfq_fold_hash(struct sfq_sched_data *q, u32 h, u32 h1)
 124 {
 125         int pert = q->perturbation;
 126
 127         /* Have we any rotation primitives? If not, WHY? */
 128         h ^= (h1<<pert) ^ (h1>>(0x1F - pert));
 129         h ^= h>>10;
 130         return h & 0x3FF;
 131 }
 132
 133 #ifndef IPPROTO_ESP
 134 #define IPPROTO_ESP 50
 135 #endif
 136
 137 static unsigned sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb)
 138 {
 139         u32 h, h2;
 140
 141         switch (skb->protocol) {
 142         case __constant_htons(ETH_P_IP):
 143         {
 144                 struct iphdr *iph = skb->nh.iph;
 145                 h = iph->daddr;
 146                 h2 = iph->saddr^iph->protocol;
 147                 if (!(iph->frag_off&htons(IP_MF|IP_OFFSET)) &&
 148                     (iph->protocol == IPPROTO_TCP ||
 149                      iph->protocol == IPPROTO_UDP ||
 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 = skb->nh.ipv6h;
 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_ESP)
 162                         h2 ^= *(u32*)&iph[1];
 163                 break;
 164         }
 165         default:
 166                 h = (u32)(unsigned long)skb->dst^skb->protocol;
 167                 h2 = (u32)(unsigned long)skb->sk;
 168         }
 169         return sfq_fold_hash(q, h, h2);
 170 }
 171
 172 extern __inline__ void sfq_link(struct sfq_sched_data *q, sfq_index x)
 173 {
 174         sfq_index p, n;
 175         int d = q->qs[x].qlen + SFQ_DEPTH;
 176
 177         p = d;
 178         n = q->dep[d].next;
 179         q->dep[x].next = n;
 180         q->dep[x].prev = p;
 181         q->dep[p].next = q->dep[n].prev = x;
 182 }
 183
 184 extern __inline__ void sfq_dec(struct sfq_sched_data *q, sfq_index x)
 185 {
 186         sfq_index p, n;
 187
 188         n = q->dep[x].next;
 189         p = q->dep[x].prev;
 190         q->dep[p].next = n;
 191         q->dep[n].prev = p;
 192
 193         if (n == p && q->max_depth == q->qs[x].qlen + 1)
 194                 q->max_depth--;
 195
 196         sfq_link(q, x);
 197 }
 198
 199 extern __inline__ void sfq_inc(struct sfq_sched_data *q, sfq_index x)
 200 {
 201         sfq_index p, n;
 202         int d;
 203
 204         n = q->dep[x].next;
 205         p = q->dep[x].prev;
 206         q->dep[p].next = n;
 207         q->dep[n].prev = p;
 208         d = q->qs[x].qlen;
 209         if (q->max_depth < d)
 210                 q->max_depth = d;
 211
 212         sfq_link(q, x);
 213 }
 214
 215 static int sfq_drop(struct Qdisc *sch)
 216 {
 217         struct sfq_sched_data *q = (struct sfq_sched_data *)sch->data;
 218         sfq_index d = q->max_depth;
 219         struct sk_buff *skb;
 220
 221         /* Queue is full! Find the longest slot and
 222            drop a packet from it */
 223
 224         if (d > 1) {
 225                 sfq_index x = q->dep[d+SFQ_DEPTH].next;
 226                 skb = q->qs[x].prev;
 227                 __skb_unlink(skb, &q->qs[x]);
 228                 kfree_skb(skb);
 229                 sfq_dec(q, x);
 230                 sch->q.qlen--;
 231                 sch->stats.drops++;
 232                 return 1;
 233         }
 234
 235         if (d == 1) {
 236                 /* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
 237                 d = q->next[q->tail];
 238                 q->next[q->tail] = q->next[d];
 239                 q->allot[q->next[d]] += q->quantum;
 240                 skb = q->qs[d].prev;
 241                 __skb_unlink(skb, &q->qs[d]);
 242                 kfree_skb(skb);
 243                 sfq_dec(q, d);
 244                 sch->q.qlen--;
 245                 q->ht[q->hash[d]] = SFQ_DEPTH;
 246                 sch->stats.drops++;
 247                 return 1;
 248         }
 249
 250         return 0;
 251 }
 252
 253 static int
 254 sfq_enqueue(struct sk_buff *skb, struct Qdisc* sch)
 255 {
 256         struct sfq_sched_data *q = (struct sfq_sched_data *)sch->data;
 257         unsigned hash = sfq_hash(q, skb);
 258         sfq_index x;
 259
 260         x = q->ht[hash];
 261         if (x == SFQ_DEPTH) {
 262                 q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
 263                 q->hash[x] = hash;
 264         }
 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 < SFQ_DEPTH-1) {
 279                 sch->stats.bytes += skb->len;
 280                 sch->stats.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 = (struct sfq_sched_data *)sch->data;
 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         __skb_queue_head(&q->qs[x], skb);
 301         sfq_inc(q, x);
 302         if (q->qs[x].qlen == 1) {               /* The flow is new */
 303                 if (q->tail == SFQ_DEPTH) {     /* It is the first flow */
 304                         q->tail = x;
 305                         q->next[x] = x;
 306                         q->allot[x] = q->quantum;
 307                 } else {
 308                         q->next[x] = q->next[q->tail];
 309                         q->next[q->tail] = x;
 310                         q->tail = x;
 311                 }
 312         }
 313         if (++sch->q.qlen < SFQ_DEPTH-1)
 314                 return 0;
 315
 316         sch->stats.drops++;
 317         sfq_drop(sch);
 318         return NET_XMIT_CN;
 319 }
 320
 321
 322
 323
 324 static struct sk_buff *
 325 sfq_dequeue(struct Qdisc* sch)
 326 {
 327         struct sfq_sched_data *q = (struct sfq_sched_data *)sch->data;
 328         struct sk_buff *skb;
 329         sfq_index a, old_a;
 330
 331         /* No active slots */
 332         if (q->tail == SFQ_DEPTH)
 333                 return NULL;
 334
 335         a = old_a = q->next[q->tail];
 336
 337         /* Grab packet */
 338         skb = __skb_dequeue(&q->qs[a]);
 339         sfq_dec(q, a);
 340         sch->q.qlen--;
 341
 342         /* Is the slot empty? */
 343         if (q->qs[a].qlen == 0) {
 344                 a = q->next[a];
 345                 if (a == old_a) {
 346                         q->tail = SFQ_DEPTH;
 347                         return skb;
 348                 }
 349                 q->next[q->tail] = a;
 350                 q->allot[a] += q->quantum;
 351         } else if ((q->allot[a] -= skb->len) <= 0) {
 352                 q->tail = a;
 353                 a = q->next[a];
 354                 q->allot[a] += q->quantum;
 355         }
 356         return skb;
 357 }
 358
 359 static void
 360 sfq_reset(struct Qdisc* sch)
 361 {
 362         struct sk_buff *skb;
 363
 364         while ((skb = sfq_dequeue(sch)) != NULL)
 365                 kfree_skb(skb);
 366 }
 367
 368 static void sfq_perturbation(unsigned long arg)
 369 {
 370         struct Qdisc *sch = (struct Qdisc*)arg;
 371         struct sfq_sched_data *q = (struct sfq_sched_data *)sch->data;
 372
 373         q->perturbation = net_random()&0x1F;
 374         q->perturb_timer.expires = jiffies + q->perturb_period;
 375
 376         if (q->perturb_period) {
 377                 q->perturb_timer.expires = jiffies + q->perturb_period;
 378                 add_timer(&q->perturb_timer);
 379         }
 380 }
 381
 382 static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
 383 {
 384         struct sfq_sched_data *q = (struct sfq_sched_data *)sch->data;
 385         struct tc_sfq_qopt *ctl = RTA_DATA(opt);
 386
 387         if (opt->rta_len < RTA_LENGTH(sizeof(*ctl)))
 388                 return -EINVAL;
 389
 390         sch_tree_lock(sch);
 391         q->quantum = ctl->quantum ? : psched_mtu(sch->dev);
 392         q->perturb_period = ctl->perturb_period*HZ;
 393
 394         del_timer(&q->perturb_timer);
 395         if (q->perturb_period) {
 396                 q->perturb_timer.expires = jiffies + q->perturb_period;
 397                 add_timer(&q->perturb_timer);
 398         }
 399         sch_tree_unlock(sch);
 400         return 0;
 401 }
 402
 403 static int sfq_init(struct Qdisc *sch, struct rtattr *opt)
 404 {
 405         struct sfq_sched_data *q = (struct sfq_sched_data *)sch->data;
 406         int i;
 407
 408         q->perturb_timer.data = (unsigned long)sch;
 409         q->perturb_timer.function = sfq_perturbation;
 410         init_timer(&q->perturb_timer);
 411
 412         for (i=0; i<SFQ_HASH_DIVISOR; i++)
 413                 q->ht[i] = SFQ_DEPTH;
 414         for (i=0; i<SFQ_DEPTH; i++) {
 415                 skb_queue_head_init(&q->qs[i]);
 416                 q->dep[i+SFQ_DEPTH].next = i+SFQ_DEPTH;
 417                 q->dep[i+SFQ_DEPTH].prev = i+SFQ_DEPTH;
 418         }
 419         q->max_depth = 0;
 420         q->tail = SFQ_DEPTH;
 421         if (opt == NULL) {
 422                 q->quantum = psched_mtu(sch->dev);
 423                 q->perturb_period = 0;
 424         } else {
 425                 int err = sfq_change(sch, opt);
 426                 if (err)
 427                         return err;
 428         }
 429         for (i=0; i<SFQ_DEPTH; i++)
 430                 sfq_link(q, i);
 431         MOD_INC_USE_COUNT;
 432         return 0;
 433 }
 434
 435 static void sfq_destroy(struct Qdisc *sch)
 436 {
 437         struct sfq_sched_data *q = (struct sfq_sched_data *)sch->data;
 438         del_timer(&q->perturb_timer);
 439         MOD_DEC_USE_COUNT;
 440 }
 441
 442 #ifdef CONFIG_RTNETLINK
 443 static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
 444 {
 445         struct sfq_sched_data *q = (struct sfq_sched_data *)sch->data;
 446         unsigned char    *b = skb->tail;
 447         struct tc_sfq_qopt opt;
 448
 449         opt.quantum = q->quantum;
 450         opt.perturb_period = q->perturb_period/HZ;
 451
 452         opt.limit = SFQ_DEPTH;
 453         opt.divisor = SFQ_HASH_DIVISOR;
 454         opt.flows = SFQ_DEPTH;
 455
 456         RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
 457
 458         return skb->len;
 459
 460 rtattr_failure:
 461         skb_trim(skb, b - skb->data);
 462         return -1;
 463 }
 464 #endif
 465
 466 struct Qdisc_ops sfq_qdisc_ops =
 467 {
 468         NULL,
 469         NULL,
 470         "sfq",
 471         sizeof(struct sfq_sched_data),
 472
 473         sfq_enqueue,
 474         sfq_dequeue,
 475         sfq_requeue,
 476         sfq_drop,
 477
 478         sfq_init,
 479         sfq_reset,
 480         sfq_destroy,
 481         NULL, /* sfq_change */
 482
 483 #ifdef CONFIG_RTNETLINK
 484         sfq_dump,
 485 #endif
 486 };
 487
 488 #ifdef MODULE
 489 int init_module(void)
 490 {
 491         return register_qdisc(&sfq_qdisc_ops);
 492 }
 493
 494 void cleanup_module(void)
 495 {
 496         unregister_qdisc(&sfq_qdisc_ops);
 497 }
 498 #endif