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/skbuff.h>
  21 #include <linux/siphash.h>
  22 #include <linux/slab.h>
  23 #include <linux/vmalloc.h>
  24 #include <net/netlink.h>
  25 #include <net/pkt_sched.h>
  26 #include <net/red.h>
  27
  28
  29 /*      Stochastic Fairness Queuing algorithm.
  30         =======================================
  31
  32         Source:
  33         Paul E. McKenney "Stochastic Fairness Queuing",
  34         IEEE INFOCOMM'90 Proceedings, San Francisco, 1990.
  35
  36         Paul E. McKenney "Stochastic Fairness Queuing",
  37         "Interworking: Research and Experience", v.2, 1991, p.113-131.
  38
  39
  40         See also:
  41         M. Shreedhar and George Varghese "Efficient Fair
  42         Queuing using Deficit Round Robin", Proc. SIGCOMM 95.
  43
  44
  45         This is not the thing that is usually called (W)FQ nowadays.
  46         It does not use any timestamp mechanism, but instead
  47         processes queues in round-robin order.
  48
  49         ADVANTAGE:
  50
  51         - It is very cheap. Both CPU and memory requirements are minimal.
  52
  53         DRAWBACKS:
  54
  55         - "Stochastic" -> It is not 100% fair.
  56         When hash collisions occur, several flows are considered as one.
  57
  58         - "Round-robin" -> It introduces larger delays than virtual clock
  59         based schemes, and should not be used for isolating interactive
  60         traffic from non-interactive. It means, that this scheduler
  61         should be used as leaf of CBQ or P3, which put interactive traffic
  62         to higher priority band.
  63
  64         We still need true WFQ for top level CSZ, but using WFQ
  65         for the best effort traffic is absolutely pointless:
  66         SFQ is superior for this purpose.
  67
  68         IMPLEMENTATION:
  69         This implementation limits :
  70         - maximal queue length per flow to 127 packets.
  71         - max mtu to 2^18-1;
  72         - max 65408 flows,
  73         - number of hash buckets to 65536.
  74
  75         It is easy to increase these values, but not in flight.  */
  76
  77 #define SFQ_MAX_DEPTH           127 /* max number of packets per flow */
  78 #define SFQ_DEFAULT_FLOWS       128
  79 #define SFQ_MAX_FLOWS           (0x10000 - SFQ_MAX_DEPTH - 1) /* max number of flows */
  80 #define SFQ_EMPTY_SLOT          0xffff
  81 #define SFQ_DEFAULT_HASH_DIVISOR 1024
  82
  83 /* We use 16 bits to store allot, and want to handle packets up to 64K
  84  * Scale allot by 8 (1<<3) so that no overflow occurs.
  85  */
  86 #define SFQ_ALLOT_SHIFT         3
  87 #define SFQ_ALLOT_SIZE(X)       DIV_ROUND_UP(X, 1 << SFQ_ALLOT_SHIFT)
  88
  89 /* This type should contain at least SFQ_MAX_DEPTH + 1 + SFQ_MAX_FLOWS values */
  90 typedef u16 sfq_index;
  91
  92 /*
  93  * We dont use pointers to save space.
  94  * Small indexes [0 ... SFQ_MAX_FLOWS - 1] are 'pointers' to slots[] array
  95  * while following values [SFQ_MAX_FLOWS ... SFQ_MAX_FLOWS + SFQ_MAX_DEPTH]
  96  * are 'pointers' to dep[] array
  97  */
  98 struct sfq_head {
  99         sfq_index       next;
 100         sfq_index       prev;
 101 };
 102
 103 struct sfq_slot {
 104         struct sk_buff  *skblist_next;
 105         struct sk_buff  *skblist_prev;
 106         sfq_index       qlen; /* number of skbs in skblist */
 107         sfq_index       next; /* next slot in sfq RR chain */
 108         struct sfq_head dep; /* anchor in dep[] chains */
 109         unsigned short  hash; /* hash value (index in ht[]) */
 110         short           allot; /* credit for this slot */
 111
 112         unsigned int    backlog;
 113         struct red_vars vars;
 114 };
 115
 116 struct sfq_sched_data {
 117 /* frequently used fields */
 118         int             limit;          /* limit of total number of packets in this qdisc */
 119         unsigned int    divisor;        /* number of slots in hash table */
 120         u8              headdrop;
 121         u8              maxdepth;       /* limit of packets per flow */
 122
 123         siphash_key_t   perturbation;
 124         u8              cur_depth;      /* depth of longest slot */
 125         u8              flags;
 126         unsigned short  scaled_quantum; /* SFQ_ALLOT_SIZE(quantum) */
 127         struct tcf_proto __rcu *filter_list;
 128         sfq_index       *ht;            /* Hash table ('divisor' slots) */
 129         struct sfq_slot *slots;         /* Flows table ('maxflows' entries) */
 130
 131         struct red_parms *red_parms;
 132         struct tc_sfqred_stats stats;
 133         struct sfq_slot *tail;          /* current slot in round */
 134
 135         struct sfq_head dep[SFQ_MAX_DEPTH + 1];
 136                                         /* Linked lists of slots, indexed by depth
 137                                          * dep[0] : list of unused flows
 138                                          * dep[1] : list of flows with 1 packet
 139                                          * dep[X] : list of flows with X packets
 140                                          */
 141
 142         unsigned int    maxflows;       /* number of flows in flows array */
 143         int             perturb_period;
 144         unsigned int    quantum;        /* Allotment per round: MUST BE >= MTU */
 145         struct timer_list perturb_timer;
 146 };
 147
 148 /*
 149  * sfq_head are either in a sfq_slot or in dep[] array
 150  */
 151 static inline struct sfq_head *sfq_dep_head(struct sfq_sched_data *q, sfq_index val)
 152 {
 153         if (val < SFQ_MAX_FLOWS)
 154                 return &q->slots[val].dep;
 155         return &q->dep[val - SFQ_MAX_FLOWS];
 156 }
 157
 158 static unsigned int sfq_hash(const struct sfq_sched_data *q,
 159                              const struct sk_buff *skb)
 160 {
 161         return skb_get_hash_perturb(skb, &q->perturbation) & (q->divisor - 1);
 162 }
 163
 164 static unsigned int sfq_classify(struct sk_buff *skb, struct Qdisc *sch,
 165                                  int *qerr)
 166 {
 167         struct sfq_sched_data *q = qdisc_priv(sch);
 168         struct tcf_result res;
 169         struct tcf_proto *fl;
 170         int result;
 171
 172         if (TC_H_MAJ(skb->priority) == sch->handle &&
 173             TC_H_MIN(skb->priority) > 0 &&
 174             TC_H_MIN(skb->priority) <= q->divisor)
 175                 return TC_H_MIN(skb->priority);
 176
 177         fl = rcu_dereference_bh(q->filter_list);
 178         if (!fl)
 179                 return sfq_hash(q, skb) + 1;
 180
 181         *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
 182         result = tc_classify(skb, fl, &res, false);
 183         if (result >= 0) {
 184 #ifdef CONFIG_NET_CLS_ACT
 185                 switch (result) {
 186                 case TC_ACT_STOLEN:
 187                 case TC_ACT_QUEUED:
 188                         *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
 189                 case TC_ACT_SHOT:
 190                         return 0;
 191                 }
 192 #endif
 193                 if (TC_H_MIN(res.classid) <= q->divisor)
 194                         return TC_H_MIN(res.classid);
 195         }
 196         return 0;
 197 }
 198
 199 /*
 200  * x : slot number [0 .. SFQ_MAX_FLOWS - 1]
 201  */
 202 static inline void sfq_link(struct sfq_sched_data *q, sfq_index x)
 203 {
 204         sfq_index p, n;
 205         struct sfq_slot *slot = &q->slots[x];
 206         int qlen = slot->qlen;
 207
 208         p = qlen + SFQ_MAX_FLOWS;
 209         n = q->dep[qlen].next;
 210
 211         slot->dep.next = n;
 212         slot->dep.prev = p;
 213
 214         q->dep[qlen].next = x;          /* sfq_dep_head(q, p)->next = x */
 215         sfq_dep_head(q, n)->prev = x;
 216 }
 217
 218 #define sfq_unlink(q, x, n, p)                  \
 219         do {                                    \
 220                 n = q->slots[x].dep.next;       \
 221                 p = q->slots[x].dep.prev;       \
 222                 sfq_dep_head(q, p)->next = n;   \
 223                 sfq_dep_head(q, n)->prev = p;   \
 224         } while (0)
 225
 226
 227 static inline void sfq_dec(struct sfq_sched_data *q, sfq_index x)
 228 {
 229         sfq_index p, n;
 230         int d;
 231
 232         sfq_unlink(q, x, n, p);
 233
 234         d = q->slots[x].qlen--;
 235         if (n == p && q->cur_depth == d)
 236                 q->cur_depth--;
 237         sfq_link(q, x);
 238 }
 239
 240 static inline void sfq_inc(struct sfq_sched_data *q, sfq_index x)
 241 {
 242         sfq_index p, n;
 243         int d;
 244
 245         sfq_unlink(q, x, n, p);
 246
 247         d = ++q->slots[x].qlen;
 248         if (q->cur_depth < d)
 249                 q->cur_depth = d;
 250         sfq_link(q, x);
 251 }
 252
 253 /* helper functions : might be changed when/if skb use a standard list_head */
 254
 255 /* remove one skb from tail of slot queue */
 256 static inline struct sk_buff *slot_dequeue_tail(struct sfq_slot *slot)
 257 {
 258         struct sk_buff *skb = slot->skblist_prev;
 259
 260         slot->skblist_prev = skb->prev;
 261         skb->prev->next = (struct sk_buff *)slot;
 262         skb->next = skb->prev = NULL;
 263         return skb;
 264 }
 265
 266 /* remove one skb from head of slot queue */
 267 static inline struct sk_buff *slot_dequeue_head(struct sfq_slot *slot)
 268 {
 269         struct sk_buff *skb = slot->skblist_next;
 270
 271         slot->skblist_next = skb->next;
 272         skb->next->prev = (struct sk_buff *)slot;
 273         skb->next = skb->prev = NULL;
 274         return skb;
 275 }
 276
 277 static inline void slot_queue_init(struct sfq_slot *slot)
 278 {
 279         memset(slot, 0, sizeof(*slot));
 280         slot->skblist_prev = slot->skblist_next = (struct sk_buff *)slot;
 281 }
 282
 283 /* add skb to slot queue (tail add) */
 284 static inline void slot_queue_add(struct sfq_slot *slot, struct sk_buff *skb)
 285 {
 286         skb->prev = slot->skblist_prev;
 287         skb->next = (struct sk_buff *)slot;
 288         slot->skblist_prev->next = skb;
 289         slot->skblist_prev = skb;
 290 }
 291
 292 static unsigned int sfq_drop(struct Qdisc *sch)
 293 {
 294         struct sfq_sched_data *q = qdisc_priv(sch);
 295         sfq_index x, d = q->cur_depth;
 296         struct sk_buff *skb;
 297         unsigned int len;
 298         struct sfq_slot *slot;
 299
 300         /* Queue is full! Find the longest slot and drop tail packet from it */
 301         if (d > 1) {
 302                 x = q->dep[d].next;
 303                 slot = &q->slots[x];
 304 drop:
 305                 skb = q->headdrop ? slot_dequeue_head(slot) : slot_dequeue_tail(slot);
 306                 len = qdisc_pkt_len(skb);
 307                 slot->backlog -= len;
 308                 sfq_dec(q, x);
 309                 sch->q.qlen--;
 310                 qdisc_qstats_drop(sch);
 311                 qdisc_qstats_backlog_dec(sch, skb);
 312                 kfree_skb(skb);
 313                 return len;
 314         }
 315
 316         if (d == 1) {
 317                 /* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
 318                 x = q->tail->next;
 319                 slot = &q->slots[x];
 320                 q->tail->next = slot->next;
 321                 q->ht[slot->hash] = SFQ_EMPTY_SLOT;
 322                 goto drop;
 323         }
 324
 325         return 0;
 326 }
 327
 328 /* Is ECN parameter configured */
 329 static int sfq_prob_mark(const struct sfq_sched_data *q)
 330 {
 331         return q->flags & TC_RED_ECN;
 332 }
 333
 334 /* Should packets over max threshold just be marked */
 335 static int sfq_hard_mark(const struct sfq_sched_data *q)
 336 {
 337         return (q->flags & (TC_RED_ECN | TC_RED_HARDDROP)) == TC_RED_ECN;
 338 }
 339
 340 static int sfq_headdrop(const struct sfq_sched_data *q)
 341 {
 342         return q->headdrop;
 343 }
 344
 345 static int
 346 sfq_enqueue(struct sk_buff *skb, struct Qdisc *sch, struct sk_buff **to_free)
 347 {
 348         struct sfq_sched_data *q = qdisc_priv(sch);
 349         unsigned int hash, dropped;
 350         sfq_index x, qlen;
 351         struct sfq_slot *slot;
 352         int uninitialized_var(ret);
 353         struct sk_buff *head;
 354         int delta;
 355
 356         hash = sfq_classify(skb, sch, &ret);
 357         if (hash == 0) {
 358                 if (ret & __NET_XMIT_BYPASS)
 359                         qdisc_qstats_drop(sch);
 360                 kfree_skb(skb);
 361                 return ret;
 362         }
 363         hash--;
 364
 365         x = q->ht[hash];
 366         slot = &q->slots[x];
 367         if (x == SFQ_EMPTY_SLOT) {
 368                 x = q->dep[0].next; /* get a free slot */
 369                 if (x >= SFQ_MAX_FLOWS)
 370                         return qdisc_drop(skb, sch, to_free);
 371                 q->ht[hash] = x;
 372                 slot = &q->slots[x];
 373                 slot->hash = hash;
 374                 slot->backlog = 0; /* should already be 0 anyway... */
 375                 red_set_vars(&slot->vars);
 376                 goto enqueue;
 377         }
 378         if (q->red_parms) {
 379                 slot->vars.qavg = red_calc_qavg_no_idle_time(q->red_parms,
 380                                                         &slot->vars,
 381                                                         slot->backlog);
 382                 switch (red_action(q->red_parms,
 383                                    &slot->vars,
 384                                    slot->vars.qavg)) {
 385                 case RED_DONT_MARK:
 386                         break;
 387
 388                 case RED_PROB_MARK:
 389                         qdisc_qstats_overlimit(sch);
 390                         if (sfq_prob_mark(q)) {
 391                                 /* We know we have at least one packet in queue */
 392                                 if (sfq_headdrop(q) &&
 393                                     INET_ECN_set_ce(slot->skblist_next)) {
 394                                         q->stats.prob_mark_head++;
 395                                         break;
 396                                 }
 397                                 if (INET_ECN_set_ce(skb)) {
 398                                         q->stats.prob_mark++;
 399                                         break;
 400                                 }
 401                         }
 402                         q->stats.prob_drop++;
 403                         goto congestion_drop;
 404
 405                 case RED_HARD_MARK:
 406                         qdisc_qstats_overlimit(sch);
 407                         if (sfq_hard_mark(q)) {
 408                                 /* We know we have at least one packet in queue */
 409                                 if (sfq_headdrop(q) &&
 410                                     INET_ECN_set_ce(slot->skblist_next)) {
 411                                         q->stats.forced_mark_head++;
 412                                         break;
 413                                 }
 414                                 if (INET_ECN_set_ce(skb)) {
 415                                         q->stats.forced_mark++;
 416                                         break;
 417                                 }
 418                         }
 419                         q->stats.forced_drop++;
 420                         goto congestion_drop;
 421                 }
 422         }
 423
 424         if (slot->qlen >= q->maxdepth) {
 425 congestion_drop:
 426                 if (!sfq_headdrop(q))
 427                         return qdisc_drop(skb, sch, to_free);
 428
 429                 /* We know we have at least one packet in queue */
 430                 head = slot_dequeue_head(slot);
 431                 delta = qdisc_pkt_len(head) - qdisc_pkt_len(skb);
 432                 sch->qstats.backlog -= delta;
 433                 slot->backlog -= delta;
 434                 qdisc_drop(head, sch, to_free);
 435
 436                 slot_queue_add(slot, skb);
 437                 qdisc_tree_reduce_backlog(sch, 0, delta);
 438                 return NET_XMIT_CN;
 439         }
 440
 441 enqueue:
 442         qdisc_qstats_backlog_inc(sch, skb);
 443         slot->backlog += qdisc_pkt_len(skb);
 444         slot_queue_add(slot, skb);
 445         sfq_inc(q, x);
 446         if (slot->qlen == 1) {          /* The flow is new */
 447                 if (q->tail == NULL) {  /* It is the first flow */
 448                         slot->next = x;
 449                 } else {
 450                         slot->next = q->tail->next;
 451                         q->tail->next = x;
 452                 }
 453                 /* We put this flow at the end of our flow list.
 454                  * This might sound unfair for a new flow to wait after old ones,
 455                  * but we could endup servicing new flows only, and freeze old ones.
 456                  */
 457                 q->tail = slot;
 458                 /* We could use a bigger initial quantum for new flows */
 459                 slot->allot = q->scaled_quantum;
 460         }
 461         if (++sch->q.qlen <= q->limit)
 462                 return NET_XMIT_SUCCESS;
 463
 464         qlen = slot->qlen;
 465         dropped = sfq_drop(sch);
 466         /* Return Congestion Notification only if we dropped a packet
 467          * from this flow.
 468          */
 469         if (qlen != slot->qlen) {
 470                 qdisc_tree_reduce_backlog(sch, 0, dropped - qdisc_pkt_len(skb));
 471                 return NET_XMIT_CN;
 472         }
 473
 474         /* As we dropped a packet, better let upper stack know this */
 475         qdisc_tree_reduce_backlog(sch, 1, dropped);
 476         return NET_XMIT_SUCCESS;
 477 }
 478
 479 static struct sk_buff *
 480 sfq_dequeue(struct Qdisc *sch)
 481 {
 482         struct sfq_sched_data *q = qdisc_priv(sch);
 483         struct sk_buff *skb;
 484         sfq_index a, next_a;
 485         struct sfq_slot *slot;
 486
 487         /* No active slots */
 488         if (q->tail == NULL)
 489                 return NULL;
 490
 491 next_slot:
 492         a = q->tail->next;
 493         slot = &q->slots[a];
 494         if (slot->allot <= 0) {
 495                 q->tail = slot;
 496                 slot->allot += q->scaled_quantum;
 497                 goto next_slot;
 498         }
 499         skb = slot_dequeue_head(slot);
 500         sfq_dec(q, a);
 501         qdisc_bstats_update(sch, skb);
 502         sch->q.qlen--;
 503         qdisc_qstats_backlog_dec(sch, skb);
 504         slot->backlog -= qdisc_pkt_len(skb);
 505         /* Is the slot empty? */
 506         if (slot->qlen == 0) {
 507                 q->ht[slot->hash] = SFQ_EMPTY_SLOT;
 508                 next_a = slot->next;
 509                 if (a == next_a) {
 510                         q->tail = NULL; /* no more active slots */
 511                         return skb;
 512                 }
 513                 q->tail->next = next_a;
 514         } else {
 515                 slot->allot -= SFQ_ALLOT_SIZE(qdisc_pkt_len(skb));
 516         }
 517         return skb;
 518 }
 519
 520 static void
 521 sfq_reset(struct Qdisc *sch)
 522 {
 523         struct sk_buff *skb;
 524
 525         while ((skb = sfq_dequeue(sch)) != NULL)
 526                 rtnl_kfree_skbs(skb, skb);
 527 }
 528
 529 /*
 530  * When q->perturbation is changed, we rehash all queued skbs
 531  * to avoid OOO (Out Of Order) effects.
 532  * We dont use sfq_dequeue()/sfq_enqueue() because we dont want to change
 533  * counters.
 534  */
 535 static void sfq_rehash(struct Qdisc *sch)
 536 {
 537         struct sfq_sched_data *q = qdisc_priv(sch);
 538         struct sk_buff *skb;
 539         int i;
 540         struct sfq_slot *slot;
 541         struct sk_buff_head list;
 542         int dropped = 0;
 543         unsigned int drop_len = 0;
 544
 545         __skb_queue_head_init(&list);
 546
 547         for (i = 0; i < q->maxflows; i++) {
 548                 slot = &q->slots[i];
 549                 if (!slot->qlen)
 550                         continue;
 551                 while (slot->qlen) {
 552                         skb = slot_dequeue_head(slot);
 553                         sfq_dec(q, i);
 554                         __skb_queue_tail(&list, skb);
 555                 }
 556                 slot->backlog = 0;
 557                 red_set_vars(&slot->vars);
 558                 q->ht[slot->hash] = SFQ_EMPTY_SLOT;
 559         }
 560         q->tail = NULL;
 561
 562         while ((skb = __skb_dequeue(&list)) != NULL) {
 563                 unsigned int hash = sfq_hash(q, skb);
 564                 sfq_index x = q->ht[hash];
 565
 566                 slot = &q->slots[x];
 567                 if (x == SFQ_EMPTY_SLOT) {
 568                         x = q->dep[0].next; /* get a free slot */
 569                         if (x >= SFQ_MAX_FLOWS) {
 570 drop:
 571                                 qdisc_qstats_backlog_dec(sch, skb);
 572                                 drop_len += qdisc_pkt_len(skb);
 573                                 kfree_skb(skb);
 574                                 dropped++;
 575                                 continue;
 576                         }
 577                         q->ht[hash] = x;
 578                         slot = &q->slots[x];
 579                         slot->hash = hash;
 580                 }
 581                 if (slot->qlen >= q->maxdepth)
 582                         goto drop;
 583                 slot_queue_add(slot, skb);
 584                 if (q->red_parms)
 585                         slot->vars.qavg = red_calc_qavg(q->red_parms,
 586                                                         &slot->vars,
 587                                                         slot->backlog);
 588                 slot->backlog += qdisc_pkt_len(skb);
 589                 sfq_inc(q, x);
 590                 if (slot->qlen == 1) {          /* The flow is new */
 591                         if (q->tail == NULL) {  /* It is the first flow */
 592                                 slot->next = x;
 593                         } else {
 594                                 slot->next = q->tail->next;
 595                                 q->tail->next = x;
 596                         }
 597                         q->tail = slot;
 598                         slot->allot = q->scaled_quantum;
 599                 }
 600         }
 601         sch->q.qlen -= dropped;
 602         qdisc_tree_reduce_backlog(sch, dropped, drop_len);
 603 }
 604
 605 static void sfq_perturbation(unsigned long arg)
 606 {
 607         struct Qdisc *sch = (struct Qdisc *)arg;
 608         struct sfq_sched_data *q = qdisc_priv(sch);
 609         spinlock_t *root_lock = qdisc_lock(qdisc_root_sleeping(sch));
 610         siphash_key_t nkey;
 611
 612         get_random_bytes(&nkey, sizeof(nkey));
 613         spin_lock(root_lock);
 614         q->perturbation = nkey;
 615         if (!q->filter_list && q->tail)
 616                 sfq_rehash(sch);
 617         spin_unlock(root_lock);
 618
 619         if (q->perturb_period)
 620                 mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
 621 }
 622
 623 static int sfq_change(struct Qdisc *sch, struct nlattr *opt)
 624 {
 625         struct sfq_sched_data *q = qdisc_priv(sch);
 626         struct tc_sfq_qopt *ctl = nla_data(opt);
 627         struct tc_sfq_qopt_v1 *ctl_v1 = NULL;
 628         unsigned int qlen, dropped = 0;
 629         struct red_parms *p = NULL;
 630
 631         if (opt->nla_len < nla_attr_size(sizeof(*ctl)))
 632                 return -EINVAL;
 633         if (opt->nla_len >= nla_attr_size(sizeof(*ctl_v1)))
 634                 ctl_v1 = nla_data(opt);
 635         if (ctl->divisor &&
 636             (!is_power_of_2(ctl->divisor) || ctl->divisor > 65536))
 637                 return -EINVAL;
 638
 639         /* slot->allot is a short, make sure quantum is not too big. */
 640         if (ctl->quantum) {
 641                 unsigned int scaled = SFQ_ALLOT_SIZE(ctl->quantum);
 642
 643                 if (scaled <= 0 || scaled > SHRT_MAX)
 644                         return -EINVAL;
 645         }
 646
 647         if (ctl_v1 && !red_check_params(ctl_v1->qth_min, ctl_v1->qth_max,
 648                                         ctl_v1->Wlog, ctl_v1->Scell_log, NULL))
 649                 return -EINVAL;
 650         if (ctl_v1 && ctl_v1->qth_min) {
 651                 p = kmalloc(sizeof(*p), GFP_KERNEL);
 652                 if (!p)
 653                         return -ENOMEM;
 654         }
 655         sch_tree_lock(sch);
 656         if (ctl->quantum) {
 657                 q->quantum = ctl->quantum;
 658                 q->scaled_quantum = SFQ_ALLOT_SIZE(q->quantum);
 659         }
 660         q->perturb_period = ctl->perturb_period * HZ;
 661         if (ctl->flows)
 662                 q->maxflows = min_t(u32, ctl->flows, SFQ_MAX_FLOWS);
 663         if (ctl->divisor) {
 664                 q->divisor = ctl->divisor;
 665                 q->maxflows = min_t(u32, q->maxflows, q->divisor);
 666         }
 667         if (ctl_v1) {
 668                 if (ctl_v1->depth)
 669                         q->maxdepth = min_t(u32, ctl_v1->depth, SFQ_MAX_DEPTH);
 670                 if (p) {
 671                         swap(q->red_parms, p);
 672                         red_set_parms(q->red_parms,
 673                                       ctl_v1->qth_min, ctl_v1->qth_max,
 674                                       ctl_v1->Wlog,
 675                                       ctl_v1->Plog, ctl_v1->Scell_log,
 676                                       NULL,
 677                                       ctl_v1->max_P);
 678                 }
 679                 q->flags = ctl_v1->flags;
 680                 q->headdrop = ctl_v1->headdrop;
 681         }
 682         if (ctl->limit) {
 683                 q->limit = min_t(u32, ctl->limit, q->maxdepth * q->maxflows);
 684                 q->maxflows = min_t(u32, q->maxflows, q->limit);
 685         }
 686
 687         qlen = sch->q.qlen;
 688         while (sch->q.qlen > q->limit)
 689                 dropped += sfq_drop(sch);
 690         qdisc_tree_reduce_backlog(sch, qlen - sch->q.qlen, dropped);
 691
 692         del_timer(&q->perturb_timer);
 693         if (q->perturb_period) {
 694                 mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
 695                 get_random_bytes(&q->perturbation, sizeof(q->perturbation));
 696         }
 697         sch_tree_unlock(sch);
 698         kfree(p);
 699         return 0;
 700 }
 701
 702 static void *sfq_alloc(size_t sz)
 703 {
 704         void *ptr = kmalloc(sz, GFP_KERNEL | __GFP_NOWARN);
 705
 706         if (!ptr)
 707                 ptr = vmalloc(sz);
 708         return ptr;
 709 }
 710
 711 static void sfq_free(void *addr)
 712 {
 713         kvfree(addr);
 714 }
 715
 716 static void sfq_destroy(struct Qdisc *sch)
 717 {
 718         struct sfq_sched_data *q = qdisc_priv(sch);
 719
 720         tcf_destroy_chain(&q->filter_list);
 721         q->perturb_period = 0;
 722         del_timer_sync(&q->perturb_timer);
 723         sfq_free(q->ht);
 724         sfq_free(q->slots);
 725         kfree(q->red_parms);
 726 }
 727
 728 static int sfq_init(struct Qdisc *sch, struct nlattr *opt)
 729 {
 730         struct sfq_sched_data *q = qdisc_priv(sch);
 731         int i;
 732
 733         q->perturb_timer.function = sfq_perturbation;
 734         q->perturb_timer.data = (unsigned long)sch;
 735         init_timer_deferrable(&q->perturb_timer);
 736
 737         for (i = 0; i < SFQ_MAX_DEPTH + 1; i++) {
 738                 q->dep[i].next = i + SFQ_MAX_FLOWS;
 739                 q->dep[i].prev = i + SFQ_MAX_FLOWS;
 740         }
 741
 742         q->limit = SFQ_MAX_DEPTH;
 743         q->maxdepth = SFQ_MAX_DEPTH;
 744         q->cur_depth = 0;
 745         q->tail = NULL;
 746         q->divisor = SFQ_DEFAULT_HASH_DIVISOR;
 747         q->maxflows = SFQ_DEFAULT_FLOWS;
 748         q->quantum = psched_mtu(qdisc_dev(sch));
 749         q->scaled_quantum = SFQ_ALLOT_SIZE(q->quantum);
 750         q->perturb_period = 0;
 751         get_random_bytes(&q->perturbation, sizeof(q->perturbation));
 752
 753         if (opt) {
 754                 int err = sfq_change(sch, opt);
 755                 if (err)
 756                         return err;
 757         }
 758
 759         q->ht = sfq_alloc(sizeof(q->ht[0]) * q->divisor);
 760         q->slots = sfq_alloc(sizeof(q->slots[0]) * q->maxflows);
 761         if (!q->ht || !q->slots) {
 762                 /* Note: sfq_destroy() will be called by our caller */
 763                 return -ENOMEM;
 764         }
 765
 766         for (i = 0; i < q->divisor; i++)
 767                 q->ht[i] = SFQ_EMPTY_SLOT;
 768
 769         for (i = 0; i < q->maxflows; i++) {
 770                 slot_queue_init(&q->slots[i]);
 771                 sfq_link(q, i);
 772         }
 773         if (q->limit >= 1)
 774                 sch->flags |= TCQ_F_CAN_BYPASS;
 775         else
 776                 sch->flags &= ~TCQ_F_CAN_BYPASS;
 777         return 0;
 778 }
 779
 780 static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
 781 {
 782         struct sfq_sched_data *q = qdisc_priv(sch);
 783         unsigned char *b = skb_tail_pointer(skb);
 784         struct tc_sfq_qopt_v1 opt;
 785         struct red_parms *p = q->red_parms;
 786
 787         memset(&opt, 0, sizeof(opt));
 788         opt.v0.quantum  = q->quantum;
 789         opt.v0.perturb_period = q->perturb_period / HZ;
 790         opt.v0.limit    = q->limit;
 791         opt.v0.divisor  = q->divisor;
 792         opt.v0.flows    = q->maxflows;
 793         opt.depth       = q->maxdepth;
 794         opt.headdrop    = q->headdrop;
 795
 796         if (p) {
 797                 opt.qth_min     = p->qth_min >> p->Wlog;
 798                 opt.qth_max     = p->qth_max >> p->Wlog;
 799                 opt.Wlog        = p->Wlog;
 800                 opt.Plog        = p->Plog;
 801                 opt.Scell_log   = p->Scell_log;
 802                 opt.max_P       = p->max_P;
 803         }
 804         memcpy(&opt.stats, &q->stats, sizeof(opt.stats));
 805         opt.flags       = q->flags;
 806
 807         if (nla_put(skb, TCA_OPTIONS, sizeof(opt), &opt))
 808                 goto nla_put_failure;
 809
 810         return skb->len;
 811
 812 nla_put_failure:
 813         nlmsg_trim(skb, b);
 814         return -1;
 815 }
 816
 817 static struct Qdisc *sfq_leaf(struct Qdisc *sch, unsigned long arg)
 818 {
 819         return NULL;
 820 }
 821
 822 static unsigned long sfq_get(struct Qdisc *sch, u32 classid)
 823 {
 824         return 0;
 825 }
 826
 827 static unsigned long sfq_bind(struct Qdisc *sch, unsigned long parent,
 828                               u32 classid)
 829 {
 830         /* we cannot bypass queue discipline anymore */
 831         sch->flags &= ~TCQ_F_CAN_BYPASS;
 832         return 0;
 833 }
 834
 835 static void sfq_put(struct Qdisc *q, unsigned long cl)
 836 {
 837 }
 838
 839 static struct tcf_proto __rcu **sfq_find_tcf(struct Qdisc *sch,
 840                                              unsigned long cl)
 841 {
 842         struct sfq_sched_data *q = qdisc_priv(sch);
 843
 844         if (cl)
 845                 return NULL;
 846         return &q->filter_list;
 847 }
 848
 849 static int sfq_dump_class(struct Qdisc *sch, unsigned long cl,
 850                           struct sk_buff *skb, struct tcmsg *tcm)
 851 {
 852         tcm->tcm_handle |= TC_H_MIN(cl);
 853         return 0;
 854 }
 855
 856 static int sfq_dump_class_stats(struct Qdisc *sch, unsigned long cl,
 857                                 struct gnet_dump *d)
 858 {
 859         struct sfq_sched_data *q = qdisc_priv(sch);
 860         sfq_index idx = q->ht[cl - 1];
 861         struct gnet_stats_queue qs = { 0 };
 862         struct tc_sfq_xstats xstats = { 0 };
 863
 864         if (idx != SFQ_EMPTY_SLOT) {
 865                 const struct sfq_slot *slot = &q->slots[idx];
 866
 867                 xstats.allot = slot->allot << SFQ_ALLOT_SHIFT;
 868                 qs.qlen = slot->qlen;
 869                 qs.backlog = slot->backlog;
 870         }
 871         if (gnet_stats_copy_queue(d, NULL, &qs, qs.qlen) < 0)
 872                 return -1;
 873         return gnet_stats_copy_app(d, &xstats, sizeof(xstats));
 874 }
 875
 876 static void sfq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
 877 {
 878         struct sfq_sched_data *q = qdisc_priv(sch);
 879         unsigned int i;
 880
 881         if (arg->stop)
 882                 return;
 883
 884         for (i = 0; i < q->divisor; i++) {
 885                 if (q->ht[i] == SFQ_EMPTY_SLOT ||
 886                     arg->count < arg->skip) {
 887                         arg->count++;
 888                         continue;
 889                 }
 890                 if (arg->fn(sch, i + 1, arg) < 0) {
 891                         arg->stop = 1;
 892                         break;
 893                 }
 894                 arg->count++;
 895         }
 896 }
 897
 898 static const struct Qdisc_class_ops sfq_class_ops = {
 899         .leaf           =       sfq_leaf,
 900         .get            =       sfq_get,
 901         .put            =       sfq_put,
 902         .tcf_chain      =       sfq_find_tcf,
 903         .bind_tcf       =       sfq_bind,
 904         .unbind_tcf     =       sfq_put,
 905         .dump           =       sfq_dump_class,
 906         .dump_stats     =       sfq_dump_class_stats,
 907         .walk           =       sfq_walk,
 908 };
 909
 910 static struct Qdisc_ops sfq_qdisc_ops __read_mostly = {
 911         .cl_ops         =       &sfq_class_ops,
 912         .id             =       "sfq",
 913         .priv_size      =       sizeof(struct sfq_sched_data),
 914         .enqueue        =       sfq_enqueue,
 915         .dequeue        =       sfq_dequeue,
 916         .peek           =       qdisc_peek_dequeued,
 917         .init           =       sfq_init,
 918         .reset          =       sfq_reset,
 919         .destroy        =       sfq_destroy,
 920         .change         =       NULL,
 921         .dump           =       sfq_dump,
 922         .owner          =       THIS_MODULE,
 923 };
 924
 925 static int __init sfq_module_init(void)
 926 {
 927         return register_qdisc(&sfq_qdisc_ops);
 928 }
 929 static void __exit sfq_module_exit(void)
 930 {
 931         unregister_qdisc(&sfq_qdisc_ops);
 932 }
 933 module_init(sfq_module_init)
 934 module_exit(sfq_module_exit)
 935 MODULE_LICENSE("GPL");