target/linux/generic/pending-4.4/032-fq_codel-add-batch-ability-to-fq_codel_drop.patch

   1 From: Eric Dumazet <edumazet@google.com>
   2 Date: Sun, 1 May 2016 16:47:26 -0700
   3 Subject: [PATCH] fq_codel: add batch ability to fq_codel_drop()
   4
   5 In presence of inelastic flows and stress, we can call
   6 fq_codel_drop() for every packet entering fq_codel qdisc.
   7
   8 fq_codel_drop() is quite expensive, as it does a linear scan
   9 of 4 KB of memory to find a fat flow.
  10 Once found, it drops the oldest packet of this flow.
  11
  12 Instead of dropping a single packet, try to drop 50% of the backlog
  13 of this fat flow, with a configurable limit of 64 packets per round.
  14
  15 TCA_FQ_CODEL_DROP_BATCH_SIZE is the new attribute to make this
  16 limit configurable.
  17
  18 With this strategy the 4 KB search is amortized to a single cache line
  19 per drop [1], so fq_codel_drop() no longer appears at the top of kernel
  20 profile in presence of few inelastic flows.
  21
  22 [1] Assuming a 64byte cache line, and 1024 buckets
  23
  24 Signed-off-by: Eric Dumazet <edumazet@google.com>
  25 Reported-by: Dave Taht <dave.taht@gmail.com>
  26 Cc: Jonathan Morton <chromatix99@gmail.com>
  27 Acked-by: Jesper Dangaard Brouer <brouer@redhat.com>
  28 Acked-by: Dave Taht
  29 Signed-off-by: David S. Miller <davem@davemloft.net>
  30 ---
  31
  32 --- a/include/uapi/linux/pkt_sched.h
  33 +++ b/include/uapi/linux/pkt_sched.h
  34 @@ -711,6 +711,7 @@ enum {
  35         TCA_FQ_CODEL_FLOWS,
  36         TCA_FQ_CODEL_QUANTUM,
  37         TCA_FQ_CODEL_CE_THRESHOLD,
  38 +       TCA_FQ_CODEL_DROP_BATCH_SIZE,
  39         __TCA_FQ_CODEL_MAX
  40  };
  41
  42 --- a/net/sched/sch_fq_codel.c
  43 +++ b/net/sched/sch_fq_codel.c
  44 @@ -57,6 +57,7 @@ struct fq_codel_sched_data {
  45         u32             flows_cnt;      /* number of flows */
  46         u32             perturbation;   /* hash perturbation */
  47         u32             quantum;        /* psched_mtu(qdisc_dev(sch)); */
  48 +       u32             drop_batch_size;
  49         struct codel_params cparams;
  50         struct codel_stats cstats;
  51         u32             drop_overlimit;
  52 @@ -133,17 +134,20 @@ static inline void flow_queue_add(struct
  53         skb->next = NULL;
  54  }
  55
  56 -static unsigned int fq_codel_drop(struct Qdisc *sch)
  57 +static unsigned int fq_codel_drop(struct Qdisc *sch, unsigned int max_packets)
  58  {
  59         struct fq_codel_sched_data *q = qdisc_priv(sch);
  60         struct sk_buff *skb;
  61         unsigned int maxbacklog = 0, idx = 0, i, len;
  62         struct fq_codel_flow *flow;
  63 +       unsigned int threshold;
  64
  65 -       /* Queue is full! Find the fat flow and drop packet from it.
  66 +       /* Queue is full! Find the fat flow and drop packet(s) from it.
  67          * This might sound expensive, but with 1024 flows, we scan
  68          * 4KB of memory, and we dont need to handle a complex tree
  69          * in fast path (packet queue/enqueue) with many cache misses.
  70 +        * In stress mode, we'll try to drop 64 packets from the flow,
  71 +        * amortizing this linear lookup to one cache line per drop.
  72          */
  73         for (i = 0; i < q->flows_cnt; i++) {
  74                 if (q->backlogs[i] > maxbacklog) {
  75 @@ -151,15 +155,24 @@ static unsigned int fq_codel_drop(struct
  76                         idx = i;
  77                 }
  78         }
  79 +
  80 +       /* Our goal is to drop half of this fat flow backlog */
  81 +       threshold = maxbacklog >> 1;
  82 +
  83         flow = &q->flows[idx];
  84 -       skb = dequeue_head(flow);
  85 -       len = qdisc_pkt_len(skb);
  86 +       len = 0;
  87 +       i = 0;
  88 +       do {
  89 +               skb = dequeue_head(flow);
  90 +               len += qdisc_pkt_len(skb);
  91 +               kfree_skb(skb);
  92 +       } while (++i < max_packets && len < threshold);
  93 +
  94 +       flow->dropped += i;
  95         q->backlogs[idx] -= len;
  96 -       sch->q.qlen--;
  97 -       qdisc_qstats_drop(sch);
  98 -       qdisc_qstats_backlog_dec(sch, skb);
  99 -       kfree_skb(skb);
 100 -       flow->dropped++;
 101 +       sch->qstats.drops += i;
 102 +       sch->qstats.backlog -= len;
 103 +       sch->q.qlen -= i;
 104         return idx;
 105  }
 106
 107 @@ -168,14 +181,14 @@ static unsigned int fq_codel_qdisc_drop(
 108         unsigned int prev_backlog;
 109
 110         prev_backlog = sch->qstats.backlog;
 111 -       fq_codel_drop(sch);
 112 +       fq_codel_drop(sch, 1U);
 113         return prev_backlog - sch->qstats.backlog;
 114  }
 115
 116  static int fq_codel_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 117  {
 118         struct fq_codel_sched_data *q = qdisc_priv(sch);
 119 -       unsigned int idx, prev_backlog;
 120 +       unsigned int idx, prev_backlog, prev_qlen;
 121         struct fq_codel_flow *flow;
 122         int uninitialized_var(ret);
 123
 124 @@ -204,16 +217,22 @@ static int fq_codel_enqueue(struct sk_bu
 125                 return NET_XMIT_SUCCESS;
 126
 127         prev_backlog = sch->qstats.backlog;
 128 -       q->drop_overlimit++;
 129 -       /* Return Congestion Notification only if we dropped a packet
 130 -        * from this flow.
 131 +       prev_qlen = sch->q.qlen;
 132 +
 133 +       /* fq_codel_drop() is quite expensive, as it performs a linear search
 134 +        * in q->backlogs[] to find a fat flow.
 135 +        * So instead of dropping a single packet, drop half of its backlog
 136 +        * with a 64 packets limit to not add a too big cpu spike here.
 137          */
 138 -       if (fq_codel_drop(sch) == idx)
 139 -               return NET_XMIT_CN;
 140 +       ret = fq_codel_drop(sch, q->drop_batch_size);
 141 +
 142 +       q->drop_overlimit += prev_qlen - sch->q.qlen;
 143
 144 -       /* As we dropped a packet, better let upper stack know this */
 145 -       qdisc_tree_reduce_backlog(sch, 1, prev_backlog - sch->qstats.backlog);
 146 -       return NET_XMIT_SUCCESS;
 147 +       /* As we dropped packet(s), better let upper stack know this */
 148 +       qdisc_tree_reduce_backlog(sch, prev_qlen - sch->q.qlen,
 149 +                                 prev_backlog - sch->qstats.backlog);
 150 +
 151 +       return ret == idx ? NET_XMIT_CN : NET_XMIT_SUCCESS;
 152  }
 153
 154  /* This is the specific function called from codel_dequeue()
 155 @@ -323,6 +342,7 @@ static const struct nla_policy fq_codel_
 156         [TCA_FQ_CODEL_FLOWS]    = { .type = NLA_U32 },
 157         [TCA_FQ_CODEL_QUANTUM]  = { .type = NLA_U32 },
 158         [TCA_FQ_CODEL_CE_THRESHOLD] = { .type = NLA_U32 },
 159 +       [TCA_FQ_CODEL_DROP_BATCH_SIZE] = { .type = NLA_U32 },
 160  };
 161
 162  static int fq_codel_change(struct Qdisc *sch, struct nlattr *opt)
 163 @@ -374,6 +394,9 @@ static int fq_codel_change(struct Qdisc
 164         if (tb[TCA_FQ_CODEL_QUANTUM])
 165                 q->quantum = max(256U, nla_get_u32(tb[TCA_FQ_CODEL_QUANTUM]));
 166
 167 +       if (tb[TCA_FQ_CODEL_DROP_BATCH_SIZE])
 168 +               q->drop_batch_size = min(1U, nla_get_u32(tb[TCA_FQ_CODEL_DROP_BATCH_SIZE]));
 169 +
 170         while (sch->q.qlen > sch->limit) {
 171                 struct sk_buff *skb = fq_codel_dequeue(sch);
 172
 173 @@ -419,6 +442,7 @@ static int fq_codel_init(struct Qdisc *s
 174
 175         sch->limit = 10*1024;
 176         q->flows_cnt = 1024;
 177 +       q->drop_batch_size = 64;
 178         q->quantum = psched_mtu(qdisc_dev(sch));
 179         q->perturbation = prandom_u32();
 180         INIT_LIST_HEAD(&q->new_flows);
 181 @@ -476,6 +500,8 @@ static int fq_codel_dump(struct Qdisc *s
 182                         q->cparams.ecn) ||
 183             nla_put_u32(skb, TCA_FQ_CODEL_QUANTUM,
 184                         q->quantum) ||
 185 +           nla_put_u32(skb, TCA_FQ_CODEL_DROP_BATCH_SIZE,
 186 +                       q->drop_batch_size) ||
 187             nla_put_u32(skb, TCA_FQ_CODEL_FLOWS,
 188                         q->flows_cnt))
 189                 goto nla_put_failure;