Pileus Git - ~andy/linux/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 <linux/jhash.h>
  23 #include <linux/slab.h>
  24 #include <linux/vmalloc.h>
  25 #include <net/ip.h>
  26 #include <net/netlink.h>
  27 #include <net/pkt_sched.h>
  28
  29
  30 /*      Stochastic Fairness Queuing algorithm.
  31         =======================================
  32
  33         Source:
  34         Paul E. McKenney "Stochastic Fairness Queuing",
  35         IEEE INFOCOMM'90 Proceedings, San Francisco, 1990.
  36
  37         Paul E. McKenney "Stochastic Fairness Queuing",
  38         "Interworking: Research and Experience", v.2, 1991, p.113-131.
  39
  40
  41         See also:
  42         M. Shreedhar and George Varghese "Efficient Fair
  43         Queuing using Deficit Round Robin", Proc. SIGCOMM 95.
  44
  45
  46         This is not the thing that is usually called (W)FQ nowadays.
  47         It does not use any timestamp mechanism, but instead
  48         processes queues in round-robin order.
  49
  50         ADVANTAGE:
  51
  52         - It is very cheap. Both CPU and memory requirements are minimal.
  53
  54         DRAWBACKS:
  55
  56         - "Stochastic" -> It is not 100% fair.
  57         When hash collisions occur, several flows are considered as one.
  58
  59         - "Round-robin" -> It introduces larger delays than virtual clock
  60         based schemes, and should not be used for isolating interactive
  61         traffic from non-interactive. It means, that this scheduler
  62         should be used as leaf of CBQ or P3, which put interactive traffic
  63         to higher priority band.
  64
  65         We still need true WFQ for top level CSZ, but using WFQ
  66         for the best effort traffic is absolutely pointless:
  67         SFQ is superior for this purpose.
  68
  69         IMPLEMENTATION:
  70         This implementation limits maximal queue length to 128;
  71         max mtu to 2^18-1; max 128 flows, number of hash buckets to 1024.
  72         The only goal of this restrictions was that all data
  73         fit into one 4K page on 32bit arches.
  74
  75         It is easy to increase these values, but not in flight.  */
  76
  77 #define SFQ_DEPTH               128 /* max number of packets per flow */
  78 #define SFQ_SLOTS               128 /* max number of flows */
  79 #define SFQ_EMPTY_SLOT          255
  80 #define SFQ_DEFAULT_HASH_DIVISOR 1024
  81
  82 /* We use 16 bits to store allot, and want to handle packets up to 64K
  83  * Scale allot by 8 (1<<3) so that no overflow occurs.
  84  */
  85 #define SFQ_ALLOT_SHIFT         3
  86 #define SFQ_ALLOT_SIZE(X)       DIV_ROUND_UP(X, 1 << SFQ_ALLOT_SHIFT)
  87
  88 /* This type should contain at least SFQ_DEPTH + SFQ_SLOTS values */
  89 typedef unsigned char sfq_index;
  90
  91 /*
  92  * We dont use pointers to save space.
  93  * Small indexes [0 ... SFQ_SLOTS - 1] are 'pointers' to slots[] array
  94  * while following values [SFQ_SLOTS ... SFQ_SLOTS + SFQ_DEPTH - 1]
  95  * are 'pointers' to dep[] array
  96  */
  97 struct sfq_head {
  98         sfq_index       next;
  99         sfq_index       prev;
 100 };
 101
 102 struct sfq_slot {
 103         struct sk_buff  *skblist_next;
 104         struct sk_buff  *skblist_prev;
 105         sfq_index       qlen; /* number of skbs in skblist */
 106         sfq_index       next; /* next slot in sfq chain */
 107         struct sfq_head dep; /* anchor in dep[] chains */
 108         unsigned short  hash; /* hash value (index in ht[]) */
 109         short           allot; /* credit for this slot */
 110 };
 111
 112 struct sfq_sched_data {
 113 /* Parameters */
 114         int             perturb_period;
 115         unsigned int    quantum;        /* Allotment per round: MUST BE >= MTU */
 116         int             limit;
 117         unsigned int    divisor;        /* number of slots in hash table */
 118 /* Variables */
 119         struct tcf_proto *filter_list;
 120         struct timer_list perturb_timer;
 121         u32             perturbation;
 122         sfq_index       cur_depth;      /* depth of longest slot */
 123         unsigned short  scaled_quantum; /* SFQ_ALLOT_SIZE(quantum) */
 124         struct sfq_slot *tail;          /* current slot in round */
 125         sfq_index       *ht;            /* Hash table (divisor slots) */
 126         struct sfq_slot slots[SFQ_SLOTS];
 127         struct sfq_head dep[SFQ_DEPTH]; /* Linked list of slots, indexed by depth */
 128 };
 129
 130 /*
 131  * sfq_head are either in a sfq_slot or in dep[] array
 132  */
 133 static inline struct sfq_head *sfq_dep_head(struct sfq_sched_data *q, sfq_index val)
 134 {
 135         if (val < SFQ_SLOTS)
 136                 return &q->slots[val].dep;
 137         return &q->dep[val - SFQ_SLOTS];
 138 }
 139
 140 static unsigned int sfq_fold_hash(struct sfq_sched_data *q, u32 h, u32 h1)
 141 {
 142         return jhash_2words(h, h1, q->perturbation) & (q->divisor - 1);
 143 }
 144
 145 static unsigned int sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb)
 146 {
 147         u32 h, h2;
 148
 149         switch (skb->protocol) {
 150         case htons(ETH_P_IP):
 151         {
 152                 const struct iphdr *iph;
 153                 int poff;
 154
 155                 if (!pskb_network_may_pull(skb, sizeof(*iph)))
 156                         goto err;
 157                 iph = ip_hdr(skb);
 158                 h = (__force u32)iph->daddr;
 159                 h2 = (__force u32)iph->saddr ^ iph->protocol;
 160                 if (iph->frag_off & htons(IP_MF | IP_OFFSET))
 161                         break;
 162                 poff = proto_ports_offset(iph->protocol);
 163                 if (poff >= 0 &&
 164                     pskb_network_may_pull(skb, iph->ihl * 4 + 4 + poff)) {
 165                         iph = ip_hdr(skb);
 166                         h2 ^= *(u32 *)((void *)iph + iph->ihl * 4 + poff);
 167                 }
 168                 break;
 169         }
 170         case htons(ETH_P_IPV6):
 171         {
 172                 const struct ipv6hdr *iph;
 173                 int poff;
 174
 175                 if (!pskb_network_may_pull(skb, sizeof(*iph)))
 176                         goto err;
 177                 iph = ipv6_hdr(skb);
 178                 h = (__force u32)iph->daddr.s6_addr32[3];
 179                 h2 = (__force u32)iph->saddr.s6_addr32[3] ^ iph->nexthdr;
 180                 poff = proto_ports_offset(iph->nexthdr);
 181                 if (poff >= 0 &&
 182                     pskb_network_may_pull(skb, sizeof(*iph) + 4 + poff)) {
 183                         iph = ipv6_hdr(skb);
 184                         h2 ^= *(u32 *)((void *)iph + sizeof(*iph) + poff);
 185                 }
 186                 break;
 187         }
 188         default:
 189 err:
 190                 h = (unsigned long)skb_dst(skb) ^ (__force u32)skb->protocol;
 191                 h2 = (unsigned long)skb->sk;
 192         }
 193
 194         return sfq_fold_hash(q, h, h2);
 195 }
 196
 197 static unsigned int sfq_classify(struct sk_buff *skb, struct Qdisc *sch,
 198                                  int *qerr)
 199 {
 200         struct sfq_sched_data *q = qdisc_priv(sch);
 201         struct tcf_result res;
 202         int result;
 203
 204         if (TC_H_MAJ(skb->priority) == sch->handle &&
 205             TC_H_MIN(skb->priority) > 0 &&
 206             TC_H_MIN(skb->priority) <= q->divisor)
 207                 return TC_H_MIN(skb->priority);
 208
 209         if (!q->filter_list)
 210                 return sfq_hash(q, skb) + 1;
 211
 212         *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
 213         result = tc_classify(skb, q->filter_list, &res);
 214         if (result >= 0) {
 215 #ifdef CONFIG_NET_CLS_ACT
 216                 switch (result) {
 217                 case TC_ACT_STOLEN:
 218                 case TC_ACT_QUEUED:
 219                         *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
 220                 case TC_ACT_SHOT:
 221                         return 0;
 222                 }
 223 #endif
 224                 if (TC_H_MIN(res.classid) <= q->divisor)
 225                         return TC_H_MIN(res.classid);
 226         }
 227         return 0;
 228 }
 229
 230 /*
 231  * x : slot number [0 .. SFQ_SLOTS - 1]
 232  */
 233 static inline void sfq_link(struct sfq_sched_data *q, sfq_index x)
 234 {
 235         sfq_index p, n;
 236         int qlen = q->slots[x].qlen;
 237
 238         p = qlen + SFQ_SLOTS;
 239         n = q->dep[qlen].next;
 240
 241         q->slots[x].dep.next = n;
 242         q->slots[x].dep.prev = p;
 243
 244         q->dep[qlen].next = x;          /* sfq_dep_head(q, p)->next = x */
 245         sfq_dep_head(q, n)->prev = x;
 246 }
 247
 248 #define sfq_unlink(q, x, n, p)                  \
 249         n = q->slots[x].dep.next;               \
 250         p = q->slots[x].dep.prev;               \
 251         sfq_dep_head(q, p)->next = n;           \
 252         sfq_dep_head(q, n)->prev = p
 253
 254
 255 static inline void sfq_dec(struct sfq_sched_data *q, sfq_index x)
 256 {
 257         sfq_index p, n;
 258         int d;
 259
 260         sfq_unlink(q, x, n, p);
 261
 262         d = q->slots[x].qlen--;
 263         if (n == p && q->cur_depth == d)
 264                 q->cur_depth--;
 265         sfq_link(q, x);
 266 }
 267
 268 static inline void sfq_inc(struct sfq_sched_data *q, sfq_index x)
 269 {
 270         sfq_index p, n;
 271         int d;
 272
 273         sfq_unlink(q, x, n, p);
 274
 275         d = ++q->slots[x].qlen;
 276         if (q->cur_depth < d)
 277                 q->cur_depth = d;
 278         sfq_link(q, x);
 279 }
 280
 281 /* helper functions : might be changed when/if skb use a standard list_head */
 282
 283 /* remove one skb from tail of slot queue */
 284 static inline struct sk_buff *slot_dequeue_tail(struct sfq_slot *slot)
 285 {
 286         struct sk_buff *skb = slot->skblist_prev;
 287
 288         slot->skblist_prev = skb->prev;
 289         skb->prev->next = (struct sk_buff *)slot;
 290         skb->next = skb->prev = NULL;
 291         return skb;
 292 }
 293
 294 /* remove one skb from head of slot queue */
 295 static inline struct sk_buff *slot_dequeue_head(struct sfq_slot *slot)
 296 {
 297         struct sk_buff *skb = slot->skblist_next;
 298
 299         slot->skblist_next = skb->next;
 300         skb->next->prev = (struct sk_buff *)slot;
 301         skb->next = skb->prev = NULL;
 302         return skb;
 303 }
 304
 305 static inline void slot_queue_init(struct sfq_slot *slot)
 306 {
 307         slot->skblist_prev = slot->skblist_next = (struct sk_buff *)slot;
 308 }
 309
 310 /* add skb to slot queue (tail add) */
 311 static inline void slot_queue_add(struct sfq_slot *slot, struct sk_buff *skb)
 312 {
 313         skb->prev = slot->skblist_prev;
 314         skb->next = (struct sk_buff *)slot;
 315         slot->skblist_prev->next = skb;
 316         slot->skblist_prev = skb;
 317 }
 318
 319 #define slot_queue_walk(slot, skb)              \
 320         for (skb = slot->skblist_next;          \
 321              skb != (struct sk_buff *)slot;     \
 322              skb = skb->next)
 323
 324 static unsigned int sfq_drop(struct Qdisc *sch)
 325 {
 326         struct sfq_sched_data *q = qdisc_priv(sch);
 327         sfq_index x, d = q->cur_depth;
 328         struct sk_buff *skb;
 329         unsigned int len;
 330         struct sfq_slot *slot;
 331
 332         /* Queue is full! Find the longest slot and drop tail packet from it */
 333         if (d > 1) {
 334                 x = q->dep[d].next;
 335                 slot = &q->slots[x];
 336 drop:
 337                 skb = slot_dequeue_tail(slot);
 338                 len = qdisc_pkt_len(skb);
 339                 sfq_dec(q, x);
 340                 kfree_skb(skb);
 341                 sch->q.qlen--;
 342                 sch->qstats.drops++;
 343                 sch->qstats.backlog -= len;
 344                 return len;
 345         }
 346
 347         if (d == 1) {
 348                 /* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
 349                 x = q->tail->next;
 350                 slot = &q->slots[x];
 351                 q->tail->next = slot->next;
 352                 q->ht[slot->hash] = SFQ_EMPTY_SLOT;
 353                 goto drop;
 354         }
 355
 356         return 0;
 357 }
 358
 359 static int
 360 sfq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 361 {
 362         struct sfq_sched_data *q = qdisc_priv(sch);
 363         unsigned int hash;
 364         sfq_index x, qlen;
 365         struct sfq_slot *slot;
 366         int uninitialized_var(ret);
 367
 368         hash = sfq_classify(skb, sch, &ret);
 369         if (hash == 0) {
 370                 if (ret & __NET_XMIT_BYPASS)
 371                         sch->qstats.drops++;
 372                 kfree_skb(skb);
 373                 return ret;
 374         }
 375         hash--;
 376
 377         x = q->ht[hash];
 378         slot = &q->slots[x];
 379         if (x == SFQ_EMPTY_SLOT) {
 380                 x = q->dep[0].next; /* get a free slot */
 381                 q->ht[hash] = x;
 382                 slot = &q->slots[x];
 383                 slot->hash = hash;
 384         }
 385
 386         /* If selected queue has length q->limit, do simple tail drop,
 387          * i.e. drop _this_ packet.
 388          */
 389         if (slot->qlen >= q->limit)
 390                 return qdisc_drop(skb, sch);
 391
 392         sch->qstats.backlog += qdisc_pkt_len(skb);
 393         slot_queue_add(slot, skb);
 394         sfq_inc(q, x);
 395         if (slot->qlen == 1) {          /* The flow is new */
 396                 if (q->tail == NULL) {  /* It is the first flow */
 397                         slot->next = x;
 398                 } else {
 399                         slot->next = q->tail->next;
 400                         q->tail->next = x;
 401                 }
 402                 q->tail = slot;
 403                 slot->allot = q->scaled_quantum;
 404         }
 405         if (++sch->q.qlen <= q->limit)
 406                 return NET_XMIT_SUCCESS;
 407
 408         qlen = slot->qlen;
 409         sfq_drop(sch);
 410         /* Return Congestion Notification only if we dropped a packet
 411          * from this flow.
 412          */
 413         return (qlen != slot->qlen) ? NET_XMIT_CN : NET_XMIT_SUCCESS;
 414 }
 415
 416 static struct sk_buff *
 417 sfq_peek(struct Qdisc *sch)
 418 {
 419         struct sfq_sched_data *q = qdisc_priv(sch);
 420
 421         /* No active slots */
 422         if (q->tail == NULL)
 423                 return NULL;
 424
 425         return q->slots[q->tail->next].skblist_next;
 426 }
 427
 428 static struct sk_buff *
 429 sfq_dequeue(struct Qdisc *sch)
 430 {
 431         struct sfq_sched_data *q = qdisc_priv(sch);
 432         struct sk_buff *skb;
 433         sfq_index a, next_a;
 434         struct sfq_slot *slot;
 435
 436         /* No active slots */
 437         if (q->tail == NULL)
 438                 return NULL;
 439
 440 next_slot:
 441         a = q->tail->next;
 442         slot = &q->slots[a];
 443         if (slot->allot <= 0) {
 444                 q->tail = slot;
 445                 slot->allot += q->scaled_quantum;
 446                 goto next_slot;
 447         }
 448         skb = slot_dequeue_head(slot);
 449         sfq_dec(q, a);
 450         qdisc_bstats_update(sch, skb);
 451         sch->q.qlen--;
 452         sch->qstats.backlog -= qdisc_pkt_len(skb);
 453
 454         /* Is the slot empty? */
 455         if (slot->qlen == 0) {
 456                 q->ht[slot->hash] = SFQ_EMPTY_SLOT;
 457                 next_a = slot->next;
 458                 if (a == next_a) {
 459                         q->tail = NULL; /* no more active slots */
 460                         return skb;
 461                 }
 462                 q->tail->next = next_a;
 463         } else {
 464                 slot->allot -= SFQ_ALLOT_SIZE(qdisc_pkt_len(skb));
 465         }
 466         return skb;
 467 }
 468
 469 static void
 470 sfq_reset(struct Qdisc *sch)
 471 {
 472         struct sk_buff *skb;
 473
 474         while ((skb = sfq_dequeue(sch)) != NULL)
 475                 kfree_skb(skb);
 476 }
 477
 478 static void sfq_perturbation(unsigned long arg)
 479 {
 480         struct Qdisc *sch = (struct Qdisc *)arg;
 481         struct sfq_sched_data *q = qdisc_priv(sch);
 482
 483         q->perturbation = net_random();
 484
 485         if (q->perturb_period)
 486                 mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
 487 }
 488
 489 static int sfq_change(struct Qdisc *sch, struct nlattr *opt)
 490 {
 491         struct sfq_sched_data *q = qdisc_priv(sch);
 492         struct tc_sfq_qopt *ctl = nla_data(opt);
 493         unsigned int qlen;
 494
 495         if (opt->nla_len < nla_attr_size(sizeof(*ctl)))
 496                 return -EINVAL;
 497
 498         if (ctl->divisor &&
 499             (!is_power_of_2(ctl->divisor) || ctl->divisor > 65536))
 500                 return -EINVAL;
 501
 502         sch_tree_lock(sch);
 503         q->quantum = ctl->quantum ? : psched_mtu(qdisc_dev(sch));
 504         q->scaled_quantum = SFQ_ALLOT_SIZE(q->quantum);
 505         q->perturb_period = ctl->perturb_period * HZ;
 506         if (ctl->limit)
 507                 q->limit = min_t(u32, ctl->limit, SFQ_DEPTH - 1);
 508         if (ctl->divisor)
 509                 q->divisor = ctl->divisor;
 510         qlen = sch->q.qlen;
 511         while (sch->q.qlen > q->limit)
 512                 sfq_drop(sch);
 513         qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen);
 514
 515         del_timer(&q->perturb_timer);
 516         if (q->perturb_period) {
 517                 mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
 518                 q->perturbation = net_random();
 519         }
 520         sch_tree_unlock(sch);
 521         return 0;
 522 }
 523
 524 static int sfq_init(struct Qdisc *sch, struct nlattr *opt)
 525 {
 526         struct sfq_sched_data *q = qdisc_priv(sch);
 527         size_t sz;
 528         int i;
 529
 530         q->perturb_timer.function = sfq_perturbation;
 531         q->perturb_timer.data = (unsigned long)sch;
 532         init_timer_deferrable(&q->perturb_timer);
 533
 534         for (i = 0; i < SFQ_DEPTH; i++) {
 535                 q->dep[i].next = i + SFQ_SLOTS;
 536                 q->dep[i].prev = i + SFQ_SLOTS;
 537         }
 538
 539         q->limit = SFQ_DEPTH - 1;
 540         q->cur_depth = 0;
 541         q->tail = NULL;
 542         q->divisor = SFQ_DEFAULT_HASH_DIVISOR;
 543         if (opt == NULL) {
 544                 q->quantum = psched_mtu(qdisc_dev(sch));
 545                 q->scaled_quantum = SFQ_ALLOT_SIZE(q->quantum);
 546                 q->perturb_period = 0;
 547                 q->perturbation = net_random();
 548         } else {
 549                 int err = sfq_change(sch, opt);
 550                 if (err)
 551                         return err;
 552         }
 553
 554         sz = sizeof(q->ht[0]) * q->divisor;
 555         q->ht = kmalloc(sz, GFP_KERNEL);
 556         if (!q->ht && sz > PAGE_SIZE)
 557                 q->ht = vmalloc(sz);
 558         if (!q->ht)
 559                 return -ENOMEM;
 560         for (i = 0; i < q->divisor; i++)
 561                 q->ht[i] = SFQ_EMPTY_SLOT;
 562
 563         for (i = 0; i < SFQ_SLOTS; i++) {
 564                 slot_queue_init(&q->slots[i]);
 565                 sfq_link(q, i);
 566         }
 567         if (q->limit >= 1)
 568                 sch->flags |= TCQ_F_CAN_BYPASS;
 569         else
 570                 sch->flags &= ~TCQ_F_CAN_BYPASS;
 571         return 0;
 572 }
 573
 574 static void sfq_destroy(struct Qdisc *sch)
 575 {
 576         struct sfq_sched_data *q = qdisc_priv(sch);
 577
 578         tcf_destroy_chain(&q->filter_list);
 579         q->perturb_period = 0;
 580         del_timer_sync(&q->perturb_timer);
 581         if (is_vmalloc_addr(q->ht))
 582                 vfree(q->ht);
 583         else
 584                 kfree(q->ht);
 585 }
 586
 587 static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
 588 {
 589         struct sfq_sched_data *q = qdisc_priv(sch);
 590         unsigned char *b = skb_tail_pointer(skb);
 591         struct tc_sfq_qopt opt;
 592
 593         opt.quantum = q->quantum;
 594         opt.perturb_period = q->perturb_period / HZ;
 595
 596         opt.limit = q->limit;
 597         opt.divisor = q->divisor;
 598         opt.flows = q->limit;
 599
 600         NLA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
 601
 602         return skb->len;
 603
 604 nla_put_failure:
 605         nlmsg_trim(skb, b);
 606         return -1;
 607 }
 608
 609 static struct Qdisc *sfq_leaf(struct Qdisc *sch, unsigned long arg)
 610 {
 611         return NULL;
 612 }
 613
 614 static unsigned long sfq_get(struct Qdisc *sch, u32 classid)
 615 {
 616         return 0;
 617 }
 618
 619 static unsigned long sfq_bind(struct Qdisc *sch, unsigned long parent,
 620                               u32 classid)
 621 {
 622         /* we cannot bypass queue discipline anymore */
 623         sch->flags &= ~TCQ_F_CAN_BYPASS;
 624         return 0;
 625 }
 626
 627 static void sfq_put(struct Qdisc *q, unsigned long cl)
 628 {
 629 }
 630
 631 static struct tcf_proto **sfq_find_tcf(struct Qdisc *sch, unsigned long cl)
 632 {
 633         struct sfq_sched_data *q = qdisc_priv(sch);
 634
 635         if (cl)
 636                 return NULL;
 637         return &q->filter_list;
 638 }
 639
 640 static int sfq_dump_class(struct Qdisc *sch, unsigned long cl,
 641                           struct sk_buff *skb, struct tcmsg *tcm)
 642 {
 643         tcm->tcm_handle |= TC_H_MIN(cl);
 644         return 0;
 645 }
 646
 647 static int sfq_dump_class_stats(struct Qdisc *sch, unsigned long cl,
 648                                 struct gnet_dump *d)
 649 {
 650         struct sfq_sched_data *q = qdisc_priv(sch);
 651         sfq_index idx = q->ht[cl - 1];
 652         struct gnet_stats_queue qs = { 0 };
 653         struct tc_sfq_xstats xstats = { 0 };
 654         struct sk_buff *skb;
 655
 656         if (idx != SFQ_EMPTY_SLOT) {
 657                 const struct sfq_slot *slot = &q->slots[idx];
 658
 659                 xstats.allot = slot->allot << SFQ_ALLOT_SHIFT;
 660                 qs.qlen = slot->qlen;
 661                 slot_queue_walk(slot, skb)
 662                         qs.backlog += qdisc_pkt_len(skb);
 663         }
 664         if (gnet_stats_copy_queue(d, &qs) < 0)
 665                 return -1;
 666         return gnet_stats_copy_app(d, &xstats, sizeof(xstats));
 667 }
 668
 669 static void sfq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
 670 {
 671         struct sfq_sched_data *q = qdisc_priv(sch);
 672         unsigned int i;
 673
 674         if (arg->stop)
 675                 return;
 676
 677         for (i = 0; i < q->divisor; i++) {
 678                 if (q->ht[i] == SFQ_EMPTY_SLOT ||
 679                     arg->count < arg->skip) {
 680                         arg->count++;
 681                         continue;
 682                 }
 683                 if (arg->fn(sch, i + 1, arg) < 0) {
 684                         arg->stop = 1;
 685                         break;
 686                 }
 687                 arg->count++;
 688         }
 689 }
 690
 691 static const struct Qdisc_class_ops sfq_class_ops = {
 692         .leaf           =       sfq_leaf,
 693         .get            =       sfq_get,
 694         .put            =       sfq_put,
 695         .tcf_chain      =       sfq_find_tcf,
 696         .bind_tcf       =       sfq_bind,
 697         .unbind_tcf     =       sfq_put,
 698         .dump           =       sfq_dump_class,
 699         .dump_stats     =       sfq_dump_class_stats,
 700         .walk           =       sfq_walk,
 701 };
 702
 703 static struct Qdisc_ops sfq_qdisc_ops __read_mostly = {
 704         .cl_ops         =       &sfq_class_ops,
 705         .id             =       "sfq",
 706         .priv_size      =       sizeof(struct sfq_sched_data),
 707         .enqueue        =       sfq_enqueue,
 708         .dequeue        =       sfq_dequeue,
 709         .peek           =       sfq_peek,
 710         .drop           =       sfq_drop,
 711         .init           =       sfq_init,
 712         .reset          =       sfq_reset,
 713         .destroy        =       sfq_destroy,
 714         .change         =       NULL,
 715         .dump           =       sfq_dump,
 716         .owner          =       THIS_MODULE,
 717 };
 718
 719 static int __init sfq_module_init(void)
 720 {
 721         return register_qdisc(&sfq_qdisc_ops);
 722 }
 723 static void __exit sfq_module_exit(void)
 724 {
 725         unregister_qdisc(&sfq_qdisc_ops);
 726 }
 727 module_init(sfq_module_init)
 728 module_exit(sfq_module_exit)
 729 MODULE_LICENSE("GPL");