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