target/linux/generic/patches-3.3/042-fq_codel-Fair-Queue-Codel-AQM.patch

   1 From 4b549a2ef4bef9965d97cbd992ba67930cd3e0fe Mon Sep 17 00:00:00 2001
   2 From: Eric Dumazet <edumazet@google.com>
   3 Date: Fri, 11 May 2012 09:30:50 +0000
   4 Subject: [PATCH 38/41] fq_codel: Fair Queue Codel AQM
   5
   6 Fair Queue Codel packet scheduler
   7
   8 Principles :
   9
  10 - Packets are classified (internal classifier or external) on flows.
  11 - This is a Stochastic model (as we use a hash, several flows might
  12                               be hashed on same slot)
  13 - Each flow has a CoDel managed queue.
  14 - Flows are linked onto two (Round Robin) lists,
  15   so that new flows have priority on old ones.
  16
  17 - For a given flow, packets are not reordered (CoDel uses a FIFO)
  18 - head drops only.
  19 - ECN capability is on by default.
  20 - Very low memory footprint (64 bytes per flow)
  21
  22 tc qdisc ... fq_codel [ limit PACKETS ] [ flows number ]
  23                       [ target TIME ] [ interval TIME ] [ noecn ]
  24                       [ quantum BYTES ]
  25
  26 defaults : 1024 flows, 10240 packets limit, quantum : device MTU
  27            target : 5ms (CoDel default)
  28            interval : 100ms (CoDel default)
  29
  30 Impressive results on load :
  31
  32 class htb 1:1 root leaf 10: prio 0 quantum 1514 rate 200000Kbit ceil 200000Kbit burst 1475b/8 mpu 0b overhead 0b cburst 1475b/8 mpu 0b overhead 0b level 0
  33  Sent 43304920109 bytes 33063109 pkt (dropped 0, overlimits 0 requeues 0)
  34  rate 201691Kbit 28595pps backlog 0b 312p requeues 0
  35  lended: 33063109 borrowed: 0 giants: 0
  36  tokens: -912 ctokens: -912
  37
  38 class fq_codel 10:1735 parent 10:
  39  (dropped 1292, overlimits 0 requeues 0)
  40  backlog 15140b 10p requeues 0
  41   deficit 1514 count 1 lastcount 1 ldelay 7.1ms
  42 class fq_codel 10:4524 parent 10:
  43  (dropped 1291, overlimits 0 requeues 0)
  44  backlog 16654b 11p requeues 0
  45   deficit 1514 count 1 lastcount 1 ldelay 7.1ms
  46 class fq_codel 10:4e74 parent 10:
  47  (dropped 1290, overlimits 0 requeues 0)
  48  backlog 6056b 4p requeues 0
  49   deficit 1514 count 1 lastcount 1 ldelay 6.4ms dropping drop_next 92.0ms
  50 class fq_codel 10:628a parent 10:
  51  (dropped 1289, overlimits 0 requeues 0)
  52  backlog 7570b 5p requeues 0
  53   deficit 1514 count 1 lastcount 1 ldelay 5.4ms dropping drop_next 90.9ms
  54 class fq_codel 10:a4b3 parent 10:
  55  (dropped 302, overlimits 0 requeues 0)
  56  backlog 16654b 11p requeues 0
  57   deficit 1514 count 1 lastcount 1 ldelay 7.1ms
  58 class fq_codel 10:c3c2 parent 10:
  59  (dropped 1284, overlimits 0 requeues 0)
  60  backlog 13626b 9p requeues 0
  61   deficit 1514 count 1 lastcount 1 ldelay 5.9ms
  62 class fq_codel 10:d331 parent 10:
  63  (dropped 299, overlimits 0 requeues 0)
  64  backlog 15140b 10p requeues 0
  65   deficit 1514 count 1 lastcount 1 ldelay 7.0ms
  66 class fq_codel 10:d526 parent 10:
  67  (dropped 12160, overlimits 0 requeues 0)
  68  backlog 35870b 211p requeues 0
  69   deficit 1508 count 12160 lastcount 1 ldelay 15.3ms dropping drop_next 247us
  70 class fq_codel 10:e2c6 parent 10:
  71  (dropped 1288, overlimits 0 requeues 0)
  72  backlog 15140b 10p requeues 0
  73   deficit 1514 count 1 lastcount 1 ldelay 7.1ms
  74 class fq_codel 10:eab5 parent 10:
  75  (dropped 1285, overlimits 0 requeues 0)
  76  backlog 16654b 11p requeues 0
  77   deficit 1514 count 1 lastcount 1 ldelay 5.9ms
  78 class fq_codel 10:f220 parent 10:
  79  (dropped 1289, overlimits 0 requeues 0)
  80  backlog 15140b 10p requeues 0
  81   deficit 1514 count 1 lastcount 1 ldelay 7.1ms
  82
  83 qdisc htb 1: root refcnt 6 r2q 10 default 1 direct_packets_stat 0 ver 3.17
  84  Sent 43331086547 bytes 33092812 pkt (dropped 0, overlimits 66063544 requeues 71)
  85  rate 201697Kbit 28602pps backlog 0b 260p requeues 71
  86 qdisc fq_codel 10: parent 1:1 limit 10240p flows 65536 target 5.0ms interval 100.0ms ecn
  87  Sent 43331086547 bytes 33092812 pkt (dropped 949359, overlimits 0 requeues 0)
  88  rate 201697Kbit 28602pps backlog 189352b 260p requeues 0
  89   maxpacket 1514 drop_overlimit 0 new_flow_count 5582 ecn_mark 125593
  90   new_flows_len 0 old_flows_len 11
  91
  92 PING 172.30.42.18 (172.30.42.18) 56(84) bytes of data.
  93 64 bytes from 172.30.42.18: icmp_req=1 ttl=64 time=0.227 ms
  94 64 bytes from 172.30.42.18: icmp_req=2 ttl=64 time=0.165 ms
  95 64 bytes from 172.30.42.18: icmp_req=3 ttl=64 time=0.166 ms
  96 64 bytes from 172.30.42.18: icmp_req=4 ttl=64 time=0.151 ms
  97 64 bytes from 172.30.42.18: icmp_req=5 ttl=64 time=0.164 ms
  98 64 bytes from 172.30.42.18: icmp_req=6 ttl=64 time=0.172 ms
  99 64 bytes from 172.30.42.18: icmp_req=7 ttl=64 time=0.175 ms
 100 64 bytes from 172.30.42.18: icmp_req=8 ttl=64 time=0.183 ms
 101 64 bytes from 172.30.42.18: icmp_req=9 ttl=64 time=0.158 ms
 102 64 bytes from 172.30.42.18: icmp_req=10 ttl=64 time=0.200 ms
 103
 104 10 packets transmitted, 10 received, 0% packet loss, time 8999ms
 105 rtt min/avg/max/mdev = 0.151/0.176/0.227/0.022 ms
 106
 107 Much better than SFQ because of priority given to new flows, and fast
 108 path dirtying less cache lines.
 109
 110 Signed-off-by: Eric Dumazet <edumazet@google.com>
 111 Signed-off-by: David S. Miller <davem@davemloft.net>
 112 ---
 113  include/linux/pkt_sched.h |   54 ++++
 114  net/sched/Kconfig         |   11 +
 115  net/sched/Makefile        |    1 +
 116  net/sched/sch_fq_codel.c  |  624 +++++++++++++++++++++++++++++++++++++++++++++
 117  4 files changed, 690 insertions(+)
 118  create mode 100644 net/sched/sch_fq_codel.c
 119
 120 --- a/include/linux/pkt_sched.h
 121 +++ b/include/linux/pkt_sched.h
 122 @@ -659,4 +659,58 @@ struct tc_codel_xstats {
 123         __u32   dropping;  /* are we in dropping state ? */
 124  };
 125
 126 +/* FQ_CODEL */
 127 +
 128 +enum {
 129 +       TCA_FQ_CODEL_UNSPEC,
 130 +       TCA_FQ_CODEL_TARGET,
 131 +       TCA_FQ_CODEL_LIMIT,
 132 +       TCA_FQ_CODEL_INTERVAL,
 133 +       TCA_FQ_CODEL_ECN,
 134 +       TCA_FQ_CODEL_FLOWS,
 135 +       TCA_FQ_CODEL_QUANTUM,
 136 +       __TCA_FQ_CODEL_MAX
 137 +};
 138 +
 139 +#define TCA_FQ_CODEL_MAX       (__TCA_FQ_CODEL_MAX - 1)
 140 +
 141 +enum {
 142 +       TCA_FQ_CODEL_XSTATS_QDISC,
 143 +       TCA_FQ_CODEL_XSTATS_CLASS,
 144 +};
 145 +
 146 +struct tc_fq_codel_qd_stats {
 147 +       __u32   maxpacket;      /* largest packet we've seen so far */
 148 +       __u32   drop_overlimit; /* number of time max qdisc
 149 +                                * packet limit was hit
 150 +                                */
 151 +       __u32   ecn_mark;       /* number of packets we ECN marked
 152 +                                * instead of being dropped
 153 +                                */
 154 +       __u32   new_flow_count; /* number of time packets
 155 +                                * created a 'new flow'
 156 +                                */
 157 +       __u32   new_flows_len;  /* count of flows in new list */
 158 +       __u32   old_flows_len;  /* count of flows in old list */
 159 +};
 160 +
 161 +struct tc_fq_codel_cl_stats {
 162 +       __s32   deficit;
 163 +       __u32   ldelay;         /* in-queue delay seen by most recently
 164 +                                * dequeued packet
 165 +                                */
 166 +       __u32   count;
 167 +       __u32   lastcount;
 168 +       __u32   dropping;
 169 +       __s32   drop_next;
 170 +};
 171 +
 172 +struct tc_fq_codel_xstats {
 173 +       __u32   type;
 174 +       union {
 175 +               struct tc_fq_codel_qd_stats qdisc_stats;
 176 +               struct tc_fq_codel_cl_stats class_stats;
 177 +       };
 178 +};
 179 +
 180  #endif
 181 --- a/net/sched/Kconfig
 182 +++ b/net/sched/Kconfig
 183 @@ -261,6 +261,17 @@ config NET_SCH_CODEL
 184
 185           If unsure, say N.
 186
 187 +config NET_SCH_FQ_CODEL
 188 +       tristate "Fair Queue Controlled Delay AQM (FQ_CODEL)"
 189 +       help
 190 +         Say Y here if you want to use the FQ Controlled Delay (FQ_CODEL)
 191 +         packet scheduling algorithm.
 192 +
 193 +         To compile this driver as a module, choose M here: the module
 194 +         will be called sch_fq_codel.
 195 +
 196 +         If unsure, say N.
 197 +
 198  config NET_SCH_INGRESS
 199         tristate "Ingress Qdisc"
 200         depends on NET_CLS_ACT
 201 --- a/net/sched/Makefile
 202 +++ b/net/sched/Makefile
 203 @@ -37,6 +37,7 @@ obj-$(CONFIG_NET_SCH_MQPRIO)  += sch_mqpr
 204  obj-$(CONFIG_NET_SCH_CHOKE)    += sch_choke.o
 205  obj-$(CONFIG_NET_SCH_QFQ)      += sch_qfq.o
 206  obj-$(CONFIG_NET_SCH_CODEL)    += sch_codel.o
 207 +obj-$(CONFIG_NET_SCH_FQ_CODEL) += sch_fq_codel.o
 208
 209  obj-$(CONFIG_NET_CLS_U32)      += cls_u32.o
 210  obj-$(CONFIG_NET_CLS_ROUTE4)   += cls_route.o
 211 --- /dev/null
 212 +++ b/net/sched/sch_fq_codel.c
 213 @@ -0,0 +1,624 @@
 214 +/*
 215 + * Fair Queue CoDel discipline
 216 + *
 217 + *     This program is free software; you can redistribute it and/or
 218 + *     modify it under the terms of the GNU General Public License
 219 + *     as published by the Free Software Foundation; either version
 220 + *     2 of the License, or (at your option) any later version.
 221 + *
 222 + *  Copyright (C) 2012 Eric Dumazet <edumazet@google.com>
 223 + */
 224 +
 225 +#include <linux/module.h>
 226 +#include <linux/types.h>
 227 +#include <linux/kernel.h>
 228 +#include <linux/jiffies.h>
 229 +#include <linux/string.h>
 230 +#include <linux/in.h>
 231 +#include <linux/errno.h>
 232 +#include <linux/init.h>
 233 +#include <linux/skbuff.h>
 234 +#include <linux/jhash.h>
 235 +#include <linux/slab.h>
 236 +#include <linux/vmalloc.h>
 237 +#include <net/netlink.h>
 238 +#include <net/pkt_sched.h>
 239 +#include <net/flow_keys.h>
 240 +#include <net/codel.h>
 241 +
 242 +/*     Fair Queue CoDel.
 243 + *
 244 + * Principles :
 245 + * Packets are classified (internal classifier or external) on flows.
 246 + * This is a Stochastic model (as we use a hash, several flows
 247 + *                            might be hashed on same slot)
 248 + * Each flow has a CoDel managed queue.
 249 + * Flows are linked onto two (Round Robin) lists,
 250 + * so that new flows have priority on old ones.
 251 + *
 252 + * For a given flow, packets are not reordered (CoDel uses a FIFO)
 253 + * head drops only.
 254 + * ECN capability is on by default.
 255 + * Low memory footprint (64 bytes per flow)
 256 + */
 257 +
 258 +struct fq_codel_flow {
 259 +       struct sk_buff    *head;
 260 +       struct sk_buff    *tail;
 261 +       struct list_head  flowchain;
 262 +       int               deficit;
 263 +       u32               dropped; /* number of drops (or ECN marks) on this flow */
 264 +       struct codel_vars cvars;
 265 +}; /* please try to keep this structure <= 64 bytes */
 266 +
 267 +struct fq_codel_sched_data {
 268 +       struct tcf_proto *filter_list;  /* optional external classifier */
 269 +       struct fq_codel_flow *flows;    /* Flows table [flows_cnt] */
 270 +       u32             *backlogs;      /* backlog table [flows_cnt] */
 271 +       u32             flows_cnt;      /* number of flows */
 272 +       u32             perturbation;   /* hash perturbation */
 273 +       u32             quantum;        /* psched_mtu(qdisc_dev(sch)); */
 274 +       struct codel_params cparams;
 275 +       struct codel_stats cstats;
 276 +       u32             drop_overlimit;
 277 +       u32             new_flow_count;
 278 +
 279 +       struct list_head new_flows;     /* list of new flows */
 280 +       struct list_head old_flows;     /* list of old flows */
 281 +};
 282 +
 283 +static unsigned int fq_codel_hash(const struct fq_codel_sched_data *q,
 284 +                                 const struct sk_buff *skb)
 285 +{
 286 +       struct flow_keys keys;
 287 +       unsigned int hash;
 288 +
 289 +       skb_flow_dissect(skb, &keys);
 290 +       hash = jhash_3words((__force u32)keys.dst,
 291 +                           (__force u32)keys.src ^ keys.ip_proto,
 292 +                           (__force u32)keys.ports, q->perturbation);
 293 +       return ((u64)hash * q->flows_cnt) >> 32;
 294 +}
 295 +
 296 +static unsigned int fq_codel_classify(struct sk_buff *skb, struct Qdisc *sch,
 297 +                                     int *qerr)
 298 +{
 299 +       struct fq_codel_sched_data *q = qdisc_priv(sch);
 300 +       struct tcf_result res;
 301 +       int result;
 302 +
 303 +       if (TC_H_MAJ(skb->priority) == sch->handle &&
 304 +           TC_H_MIN(skb->priority) > 0 &&
 305 +           TC_H_MIN(skb->priority) <= q->flows_cnt)
 306 +               return TC_H_MIN(skb->priority);
 307 +
 308 +       if (!q->filter_list)
 309 +               return fq_codel_hash(q, skb) + 1;
 310 +
 311 +       *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
 312 +       result = tc_classify(skb, q->filter_list, &res);
 313 +       if (result >= 0) {
 314 +#ifdef CONFIG_NET_CLS_ACT
 315 +               switch (result) {
 316 +               case TC_ACT_STOLEN:
 317 +               case TC_ACT_QUEUED:
 318 +                       *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
 319 +               case TC_ACT_SHOT:
 320 +                       return 0;
 321 +               }
 322 +#endif
 323 +               if (TC_H_MIN(res.classid) <= q->flows_cnt)
 324 +                       return TC_H_MIN(res.classid);
 325 +       }
 326 +       return 0;
 327 +}
 328 +
 329 +/* helper functions : might be changed when/if skb use a standard list_head */
 330 +
 331 +/* remove one skb from head of slot queue */
 332 +static inline struct sk_buff *dequeue_head(struct fq_codel_flow *flow)
 333 +{
 334 +       struct sk_buff *skb = flow->head;
 335 +
 336 +       flow->head = skb->next;
 337 +       skb->next = NULL;
 338 +       return skb;
 339 +}
 340 +
 341 +/* add skb to flow queue (tail add) */
 342 +static inline void flow_queue_add(struct fq_codel_flow *flow,
 343 +                                 struct sk_buff *skb)
 344 +{
 345 +       if (flow->head == NULL)
 346 +               flow->head = skb;
 347 +       else
 348 +               flow->tail->next = skb;
 349 +       flow->tail = skb;
 350 +       skb->next = NULL;
 351 +}
 352 +
 353 +static unsigned int fq_codel_drop(struct Qdisc *sch)
 354 +{
 355 +       struct fq_codel_sched_data *q = qdisc_priv(sch);
 356 +       struct sk_buff *skb;
 357 +       unsigned int maxbacklog = 0, idx = 0, i, len;
 358 +       struct fq_codel_flow *flow;
 359 +
 360 +       /* Queue is full! Find the fat flow and drop packet from it.
 361 +        * This might sound expensive, but with 1024 flows, we scan
 362 +        * 4KB of memory, and we dont need to handle a complex tree
 363 +        * in fast path (packet queue/enqueue) with many cache misses.
 364 +        */
 365 +       for (i = 0; i < q->flows_cnt; i++) {
 366 +               if (q->backlogs[i] > maxbacklog) {
 367 +                       maxbacklog = q->backlogs[i];
 368 +                       idx = i;
 369 +               }
 370 +       }
 371 +       flow = &q->flows[idx];
 372 +       skb = dequeue_head(flow);
 373 +       len = qdisc_pkt_len(skb);
 374 +       q->backlogs[idx] -= len;
 375 +       kfree_skb(skb);
 376 +       sch->q.qlen--;
 377 +       sch->qstats.drops++;
 378 +       sch->qstats.backlog -= len;
 379 +       flow->dropped++;
 380 +       return idx;
 381 +}
 382 +
 383 +static int fq_codel_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 384 +{
 385 +       struct fq_codel_sched_data *q = qdisc_priv(sch);
 386 +       unsigned int idx;
 387 +       struct fq_codel_flow *flow;
 388 +       int uninitialized_var(ret);
 389 +
 390 +       idx = fq_codel_classify(skb, sch, &ret);
 391 +       if (idx == 0) {
 392 +               if (ret & __NET_XMIT_BYPASS)
 393 +                       sch->qstats.drops++;
 394 +               kfree_skb(skb);
 395 +               return ret;
 396 +       }
 397 +       idx--;
 398 +
 399 +       codel_set_enqueue_time(skb);
 400 +       flow = &q->flows[idx];
 401 +       flow_queue_add(flow, skb);
 402 +       q->backlogs[idx] += qdisc_pkt_len(skb);
 403 +       sch->qstats.backlog += qdisc_pkt_len(skb);
 404 +
 405 +       if (list_empty(&flow->flowchain)) {
 406 +               list_add_tail(&flow->flowchain, &q->new_flows);
 407 +               codel_vars_init(&flow->cvars);
 408 +               q->new_flow_count++;
 409 +               flow->deficit = q->quantum;
 410 +               flow->dropped = 0;
 411 +       }
 412 +       if (++sch->q.qlen < sch->limit)
 413 +               return NET_XMIT_SUCCESS;
 414 +
 415 +       q->drop_overlimit++;
 416 +       /* Return Congestion Notification only if we dropped a packet
 417 +        * from this flow.
 418 +        */
 419 +       if (fq_codel_drop(sch) == idx)
 420 +               return NET_XMIT_CN;
 421 +
 422 +       /* As we dropped a packet, better let upper stack know this */
 423 +       qdisc_tree_decrease_qlen(sch, 1);
 424 +       return NET_XMIT_SUCCESS;
 425 +}
 426 +
 427 +/* This is the specific function called from codel_dequeue()
 428 + * to dequeue a packet from queue. Note: backlog is handled in
 429 + * codel, we dont need to reduce it here.
 430 + */
 431 +static struct sk_buff *dequeue(struct codel_vars *vars, struct Qdisc *sch)
 432 +{
 433 +       struct fq_codel_flow *flow;
 434 +       struct sk_buff *skb = NULL;
 435 +
 436 +       flow = container_of(vars, struct fq_codel_flow, cvars);
 437 +       if (flow->head) {
 438 +               skb = dequeue_head(flow);
 439 +               sch->qstats.backlog -= qdisc_pkt_len(skb);
 440 +               sch->q.qlen--;
 441 +       }
 442 +       return skb;
 443 +}
 444 +
 445 +static struct sk_buff *fq_codel_dequeue(struct Qdisc *sch)
 446 +{
 447 +       struct fq_codel_sched_data *q = qdisc_priv(sch);
 448 +       struct sk_buff *skb;
 449 +       struct fq_codel_flow *flow;
 450 +       struct list_head *head;
 451 +       u32 prev_drop_count, prev_ecn_mark;
 452 +
 453 +begin:
 454 +       head = &q->new_flows;
 455 +       if (list_empty(head)) {
 456 +               head = &q->old_flows;
 457 +               if (list_empty(head))
 458 +                       return NULL;
 459 +       }
 460 +       flow = list_first_entry(head, struct fq_codel_flow, flowchain);
 461 +
 462 +       if (flow->deficit <= 0) {
 463 +               flow->deficit += q->quantum;
 464 +               list_move_tail(&flow->flowchain, &q->old_flows);
 465 +               goto begin;
 466 +       }
 467 +
 468 +       prev_drop_count = q->cstats.drop_count;
 469 +       prev_ecn_mark = q->cstats.ecn_mark;
 470 +
 471 +       skb = codel_dequeue(sch, &q->cparams, &flow->cvars, &q->cstats,
 472 +                           dequeue, &q->backlogs[flow - q->flows]);
 473 +
 474 +       flow->dropped += q->cstats.drop_count - prev_drop_count;
 475 +       flow->dropped += q->cstats.ecn_mark - prev_ecn_mark;
 476 +
 477 +       if (!skb) {
 478 +               /* force a pass through old_flows to prevent starvation */
 479 +               if ((head == &q->new_flows) && !list_empty(&q->old_flows))
 480 +                       list_move_tail(&flow->flowchain, &q->old_flows);
 481 +               else
 482 +                       list_del_init(&flow->flowchain);
 483 +               goto begin;
 484 +       }
 485 +       qdisc_bstats_update(sch, skb);
 486 +       flow->deficit -= qdisc_pkt_len(skb);
 487 +       /* We cant call qdisc_tree_decrease_qlen() if our qlen is 0,
 488 +        * or HTB crashes. Defer it for next round.
 489 +        */
 490 +       if (q->cstats.drop_count && sch->q.qlen) {
 491 +               qdisc_tree_decrease_qlen(sch, q->cstats.drop_count);
 492 +               q->cstats.drop_count = 0;
 493 +       }
 494 +       return skb;
 495 +}
 496 +
 497 +static void fq_codel_reset(struct Qdisc *sch)
 498 +{
 499 +       struct sk_buff *skb;
 500 +
 501 +       while ((skb = fq_codel_dequeue(sch)) != NULL)
 502 +               kfree_skb(skb);
 503 +}
 504 +
 505 +static const struct nla_policy fq_codel_policy[TCA_FQ_CODEL_MAX + 1] = {
 506 +       [TCA_FQ_CODEL_TARGET]   = { .type = NLA_U32 },
 507 +       [TCA_FQ_CODEL_LIMIT]    = { .type = NLA_U32 },
 508 +       [TCA_FQ_CODEL_INTERVAL] = { .type = NLA_U32 },
 509 +       [TCA_FQ_CODEL_ECN]      = { .type = NLA_U32 },
 510 +       [TCA_FQ_CODEL_FLOWS]    = { .type = NLA_U32 },
 511 +       [TCA_FQ_CODEL_QUANTUM]  = { .type = NLA_U32 },
 512 +};
 513 +
 514 +static int fq_codel_change(struct Qdisc *sch, struct nlattr *opt)
 515 +{
 516 +       struct fq_codel_sched_data *q = qdisc_priv(sch);
 517 +       struct nlattr *tb[TCA_FQ_CODEL_MAX + 1];
 518 +       int err;
 519 +
 520 +       if (!opt)
 521 +               return -EINVAL;
 522 +
 523 +       err = nla_parse_nested(tb, TCA_FQ_CODEL_MAX, opt, fq_codel_policy);
 524 +       if (err < 0)
 525 +               return err;
 526 +       if (tb[TCA_FQ_CODEL_FLOWS]) {
 527 +               if (q->flows)
 528 +                       return -EINVAL;
 529 +               q->flows_cnt = nla_get_u32(tb[TCA_FQ_CODEL_FLOWS]);
 530 +               if (!q->flows_cnt ||
 531 +                   q->flows_cnt > 65536)
 532 +                       return -EINVAL;
 533 +       }
 534 +       sch_tree_lock(sch);
 535 +
 536 +       if (tb[TCA_FQ_CODEL_TARGET]) {
 537 +               u64 target = nla_get_u32(tb[TCA_FQ_CODEL_TARGET]);
 538 +
 539 +               q->cparams.target = (target * NSEC_PER_USEC) >> CODEL_SHIFT;
 540 +       }
 541 +
 542 +       if (tb[TCA_FQ_CODEL_INTERVAL]) {
 543 +               u64 interval = nla_get_u32(tb[TCA_FQ_CODEL_INTERVAL]);
 544 +
 545 +               q->cparams.interval = (interval * NSEC_PER_USEC) >> CODEL_SHIFT;
 546 +       }
 547 +
 548 +       if (tb[TCA_FQ_CODEL_LIMIT])
 549 +               sch->limit = nla_get_u32(tb[TCA_FQ_CODEL_LIMIT]);
 550 +
 551 +       if (tb[TCA_FQ_CODEL_ECN])
 552 +               q->cparams.ecn = !!nla_get_u32(tb[TCA_FQ_CODEL_ECN]);
 553 +
 554 +       if (tb[TCA_FQ_CODEL_QUANTUM])
 555 +               q->quantum = max(256U, nla_get_u32(tb[TCA_FQ_CODEL_QUANTUM]));
 556 +
 557 +       while (sch->q.qlen > sch->limit) {
 558 +               struct sk_buff *skb = fq_codel_dequeue(sch);
 559 +
 560 +               kfree_skb(skb);
 561 +               q->cstats.drop_count++;
 562 +       }
 563 +       qdisc_tree_decrease_qlen(sch, q->cstats.drop_count);
 564 +       q->cstats.drop_count = 0;
 565 +
 566 +       sch_tree_unlock(sch);
 567 +       return 0;
 568 +}
 569 +
 570 +static void *fq_codel_zalloc(size_t sz)
 571 +{
 572 +       void *ptr = kzalloc(sz, GFP_KERNEL | __GFP_NOWARN);
 573 +
 574 +       if (!ptr)
 575 +               ptr = vzalloc(sz);
 576 +       return ptr;
 577 +}
 578 +
 579 +static void fq_codel_free(void *addr)
 580 +{
 581 +       if (addr) {
 582 +               if (is_vmalloc_addr(addr))
 583 +                       vfree(addr);
 584 +               else
 585 +                       kfree(addr);
 586 +       }
 587 +}
 588 +
 589 +static void fq_codel_destroy(struct Qdisc *sch)
 590 +{
 591 +       struct fq_codel_sched_data *q = qdisc_priv(sch);
 592 +
 593 +       tcf_destroy_chain(&q->filter_list);
 594 +       fq_codel_free(q->backlogs);
 595 +       fq_codel_free(q->flows);
 596 +}
 597 +
 598 +static int fq_codel_init(struct Qdisc *sch, struct nlattr *opt)
 599 +{
 600 +       struct fq_codel_sched_data *q = qdisc_priv(sch);
 601 +       int i;
 602 +
 603 +       sch->limit = 10*1024;
 604 +       q->flows_cnt = 1024;
 605 +       q->quantum = psched_mtu(qdisc_dev(sch));
 606 +       q->perturbation = net_random();
 607 +       INIT_LIST_HEAD(&q->new_flows);
 608 +       INIT_LIST_HEAD(&q->old_flows);
 609 +       codel_params_init(&q->cparams);
 610 +       codel_stats_init(&q->cstats);
 611 +       q->cparams.ecn = true;
 612 +
 613 +       if (opt) {
 614 +               int err = fq_codel_change(sch, opt);
 615 +               if (err)
 616 +                       return err;
 617 +       }
 618 +
 619 +       if (!q->flows) {
 620 +               q->flows = fq_codel_zalloc(q->flows_cnt *
 621 +                                          sizeof(struct fq_codel_flow));
 622 +               if (!q->flows)
 623 +                       return -ENOMEM;
 624 +               q->backlogs = fq_codel_zalloc(q->flows_cnt * sizeof(u32));
 625 +               if (!q->backlogs) {
 626 +                       fq_codel_free(q->flows);
 627 +                       return -ENOMEM;
 628 +               }
 629 +               for (i = 0; i < q->flows_cnt; i++) {
 630 +                       struct fq_codel_flow *flow = q->flows + i;
 631 +
 632 +                       INIT_LIST_HEAD(&flow->flowchain);
 633 +               }
 634 +       }
 635 +       if (sch->limit >= 1)
 636 +               sch->flags |= TCQ_F_CAN_BYPASS;
 637 +       else
 638 +               sch->flags &= ~TCQ_F_CAN_BYPASS;
 639 +       return 0;
 640 +}
 641 +
 642 +static int fq_codel_dump(struct Qdisc *sch, struct sk_buff *skb)
 643 +{
 644 +       struct fq_codel_sched_data *q = qdisc_priv(sch);
 645 +       struct nlattr *opts;
 646 +
 647 +       opts = nla_nest_start(skb, TCA_OPTIONS);
 648 +       if (opts == NULL)
 649 +               goto nla_put_failure;
 650 +
 651 +       if (nla_put_u32(skb, TCA_FQ_CODEL_TARGET,
 652 +                       codel_time_to_us(q->cparams.target)) ||
 653 +           nla_put_u32(skb, TCA_FQ_CODEL_LIMIT,
 654 +                       sch->limit) ||
 655 +           nla_put_u32(skb, TCA_FQ_CODEL_INTERVAL,
 656 +                       codel_time_to_us(q->cparams.interval)) ||
 657 +           nla_put_u32(skb, TCA_FQ_CODEL_ECN,
 658 +                       q->cparams.ecn) ||
 659 +           nla_put_u32(skb, TCA_FQ_CODEL_QUANTUM,
 660 +                       q->quantum) ||
 661 +           nla_put_u32(skb, TCA_FQ_CODEL_FLOWS,
 662 +                       q->flows_cnt))
 663 +               goto nla_put_failure;
 664 +
 665 +       nla_nest_end(skb, opts);
 666 +       return skb->len;
 667 +
 668 +nla_put_failure:
 669 +       return -1;
 670 +}
 671 +
 672 +static int fq_codel_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
 673 +{
 674 +       struct fq_codel_sched_data *q = qdisc_priv(sch);
 675 +       struct tc_fq_codel_xstats st = {
 676 +               .type                           = TCA_FQ_CODEL_XSTATS_QDISC,
 677 +               .qdisc_stats.maxpacket          = q->cstats.maxpacket,
 678 +               .qdisc_stats.drop_overlimit     = q->drop_overlimit,
 679 +               .qdisc_stats.ecn_mark           = q->cstats.ecn_mark,
 680 +               .qdisc_stats.new_flow_count     = q->new_flow_count,
 681 +       };
 682 +       struct list_head *pos;
 683 +
 684 +       list_for_each(pos, &q->new_flows)
 685 +               st.qdisc_stats.new_flows_len++;
 686 +
 687 +       list_for_each(pos, &q->old_flows)
 688 +               st.qdisc_stats.old_flows_len++;
 689 +
 690 +       return gnet_stats_copy_app(d, &st, sizeof(st));
 691 +}
 692 +
 693 +static struct Qdisc *fq_codel_leaf(struct Qdisc *sch, unsigned long arg)
 694 +{
 695 +       return NULL;
 696 +}
 697 +
 698 +static unsigned long fq_codel_get(struct Qdisc *sch, u32 classid)
 699 +{
 700 +       return 0;
 701 +}
 702 +
 703 +static unsigned long fq_codel_bind(struct Qdisc *sch, unsigned long parent,
 704 +                             u32 classid)
 705 +{
 706 +       /* we cannot bypass queue discipline anymore */
 707 +       sch->flags &= ~TCQ_F_CAN_BYPASS;
 708 +       return 0;
 709 +}
 710 +
 711 +static void fq_codel_put(struct Qdisc *q, unsigned long cl)
 712 +{
 713 +}
 714 +
 715 +static struct tcf_proto **fq_codel_find_tcf(struct Qdisc *sch, unsigned long cl)
 716 +{
 717 +       struct fq_codel_sched_data *q = qdisc_priv(sch);
 718 +
 719 +       if (cl)
 720 +               return NULL;
 721 +       return &q->filter_list;
 722 +}
 723 +
 724 +static int fq_codel_dump_class(struct Qdisc *sch, unsigned long cl,
 725 +                         struct sk_buff *skb, struct tcmsg *tcm)
 726 +{
 727 +       tcm->tcm_handle |= TC_H_MIN(cl);
 728 +       return 0;
 729 +}
 730 +
 731 +static int fq_codel_dump_class_stats(struct Qdisc *sch, unsigned long cl,
 732 +                                    struct gnet_dump *d)
 733 +{
 734 +       struct fq_codel_sched_data *q = qdisc_priv(sch);
 735 +       u32 idx = cl - 1;
 736 +       struct gnet_stats_queue qs = { 0 };
 737 +       struct tc_fq_codel_xstats xstats;
 738 +
 739 +       if (idx < q->flows_cnt) {
 740 +               const struct fq_codel_flow *flow = &q->flows[idx];
 741 +               const struct sk_buff *skb = flow->head;
 742 +
 743 +               memset(&xstats, 0, sizeof(xstats));
 744 +               xstats.type = TCA_FQ_CODEL_XSTATS_CLASS;
 745 +               xstats.class_stats.deficit = flow->deficit;
 746 +               xstats.class_stats.ldelay =
 747 +                       codel_time_to_us(flow->cvars.ldelay);
 748 +               xstats.class_stats.count = flow->cvars.count;
 749 +               xstats.class_stats.lastcount = flow->cvars.lastcount;
 750 +               xstats.class_stats.dropping = flow->cvars.dropping;
 751 +               if (flow->cvars.dropping) {
 752 +                       codel_tdiff_t delta = flow->cvars.drop_next -
 753 +                                             codel_get_time();
 754 +
 755 +                       xstats.class_stats.drop_next = (delta >= 0) ?
 756 +                               codel_time_to_us(delta) :
 757 +                               -codel_time_to_us(-delta);
 758 +               }
 759 +               while (skb) {
 760 +                       qs.qlen++;
 761 +                       skb = skb->next;
 762 +               }
 763 +               qs.backlog = q->backlogs[idx];
 764 +               qs.drops = flow->dropped;
 765 +       }
 766 +       if (gnet_stats_copy_queue(d, &qs) < 0)
 767 +               return -1;
 768 +       if (idx < q->flows_cnt)
 769 +               return gnet_stats_copy_app(d, &xstats, sizeof(xstats));
 770 +       return 0;
 771 +}
 772 +
 773 +static void fq_codel_walk(struct Qdisc *sch, struct qdisc_walker *arg)
 774 +{
 775 +       struct fq_codel_sched_data *q = qdisc_priv(sch);
 776 +       unsigned int i;
 777 +
 778 +       if (arg->stop)
 779 +               return;
 780 +
 781 +       for (i = 0; i < q->flows_cnt; i++) {
 782 +               if (list_empty(&q->flows[i].flowchain) ||
 783 +                   arg->count < arg->skip) {
 784 +                       arg->count++;
 785 +                       continue;
 786 +               }
 787 +               if (arg->fn(sch, i + 1, arg) < 0) {
 788 +                       arg->stop = 1;
 789 +                       break;
 790 +               }
 791 +               arg->count++;
 792 +       }
 793 +}
 794 +
 795 +static const struct Qdisc_class_ops fq_codel_class_ops = {
 796 +       .leaf           =       fq_codel_leaf,
 797 +       .get            =       fq_codel_get,
 798 +       .put            =       fq_codel_put,
 799 +       .tcf_chain      =       fq_codel_find_tcf,
 800 +       .bind_tcf       =       fq_codel_bind,
 801 +       .unbind_tcf     =       fq_codel_put,
 802 +       .dump           =       fq_codel_dump_class,
 803 +       .dump_stats     =       fq_codel_dump_class_stats,
 804 +       .walk           =       fq_codel_walk,
 805 +};
 806 +
 807 +static struct Qdisc_ops fq_codel_qdisc_ops __read_mostly = {
 808 +       .cl_ops         =       &fq_codel_class_ops,
 809 +       .id             =       "fq_codel",
 810 +       .priv_size      =       sizeof(struct fq_codel_sched_data),
 811 +       .enqueue        =       fq_codel_enqueue,
 812 +       .dequeue        =       fq_codel_dequeue,
 813 +       .peek           =       qdisc_peek_dequeued,
 814 +       .drop           =       fq_codel_drop,
 815 +       .init           =       fq_codel_init,
 816 +       .reset          =       fq_codel_reset,
 817 +       .destroy        =       fq_codel_destroy,
 818 +       .change         =       fq_codel_change,
 819 +       .dump           =       fq_codel_dump,
 820 +       .dump_stats =   fq_codel_dump_stats,
 821 +       .owner          =       THIS_MODULE,
 822 +};
 823 +
 824 +static int __init fq_codel_module_init(void)
 825 +{
 826 +       return register_qdisc(&fq_codel_qdisc_ops);
 827 +}
 828 +
 829 +static void __exit fq_codel_module_exit(void)
 830 +{
 831 +       unregister_qdisc(&fq_codel_qdisc_ops);
 832 +}
 833 +
 834 +module_init(fq_codel_module_init)
 835 +module_exit(fq_codel_module_exit)
 836 +MODULE_AUTHOR("Eric Dumazet");
 837 +MODULE_LICENSE("GPL");