package/kernel/mac80211/patches/subsys/312-net-fq_impl-do-not-maintain-a-backlog-sorted-list-of.patch

   1 From: Felix Fietkau <nbd@nbd.name>
   2 Date: Wed, 25 Nov 2020 18:10:34 +0100
   3 Subject: [PATCH] net/fq_impl: do not maintain a backlog-sorted list of
   4  flows
   5
   6 A sorted flow list is only needed to drop packets in the biggest flow when
   7 hitting the overmemory condition.
   8 By scanning flows only when needed, we can avoid paying the cost of
   9 maintaining the list under normal conditions
  10 In order to avoid scanning lots of empty flows and touching too many cold
  11 cache lines, a bitmap of flows with backlog is maintained
  12
  13 Signed-off-by: Felix Fietkau <nbd@nbd.name>
  14 ---
  15
  16 --- a/include/net/fq.h
  17 +++ b/include/net/fq.h
  18 @@ -19,8 +19,6 @@ struct fq_tin;
  19   * @flowchain: can be linked to fq_tin's new_flows or old_flows. Used for DRR++
  20   *     (deficit round robin) based round robin queuing similar to the one
  21   *     found in net/sched/sch_fq_codel.c
  22 - * @backlogchain: can be linked to other fq_flow and fq. Used to keep track of
  23 - *     fat flows and efficient head-dropping if packet limit is reached
  24   * @queue: sk_buff queue to hold packets
  25   * @backlog: number of bytes pending in the queue. The number of packets can be
  26   *     found in @queue.qlen
  27 @@ -29,7 +27,6 @@ struct fq_tin;
  28  struct fq_flow {
  29         struct fq_tin *tin;
  30         struct list_head flowchain;
  31 -       struct list_head backlogchain;
  32         struct sk_buff_head queue;
  33         u32 backlog;
  34         int deficit;
  35 @@ -47,6 +44,7 @@ struct fq_flow {
  36  struct fq_tin {
  37         struct list_head new_flows;
  38         struct list_head old_flows;
  39 +       struct list_head tin_list;
  40         struct fq_flow default_flow;
  41         u32 backlog_bytes;
  42         u32 backlog_packets;
  43 @@ -60,14 +58,14 @@ struct fq_tin {
  44  /**
  45   * struct fq - main container for fair queuing purposes
  46   *
  47 - * @backlogs: linked to fq_flows. Used to maintain fat flows for efficient
  48 - *     head-dropping when @backlog reaches @limit
  49   * @limit: max number of packets that can be queued across all flows
  50   * @backlog: number of packets queued across all flows
  51   */
  52  struct fq {
  53         struct fq_flow *flows;
  54 -       struct list_head backlogs;
  55 +       unsigned long *flows_bitmap;
  56 +
  57 +       struct list_head tin_backlog;
  58         spinlock_t lock;
  59         u32 flows_cnt;
  60         u32 limit;
  61 --- a/include/net/fq_impl.h
  62 +++ b/include/net/fq_impl.h
  63 @@ -17,12 +17,24 @@ __fq_adjust_removal(struct fq *fq, struc
  64                     unsigned int bytes, unsigned int truesize)
  65  {
  66         struct fq_tin *tin = flow->tin;
  67 +       int idx;
  68
  69         tin->backlog_bytes -= bytes;
  70         tin->backlog_packets -= packets;
  71         flow->backlog -= bytes;
  72         fq->backlog -= packets;
  73         fq->memory_usage -= truesize;
  74 +
  75 +       if (flow->backlog)
  76 +               return;
  77 +
  78 +       if (flow == &tin->default_flow) {
  79 +               list_del_init(&tin->tin_list);
  80 +               return;
  81 +       }
  82 +
  83 +       idx = flow - fq->flows;
  84 +       __clear_bit(idx, fq->flows_bitmap);
  85  }
  86
  87  static void fq_adjust_removal(struct fq *fq,
  88 @@ -32,24 +44,6 @@ static void fq_adjust_removal(struct fq
  89         __fq_adjust_removal(fq, flow, 1, skb->len, skb->truesize);
  90  }
  91
  92 -static void fq_rejigger_backlog(struct fq *fq, struct fq_flow *flow)
  93 -{
  94 -       struct fq_flow *i;
  95 -
  96 -       if (flow->backlog == 0) {
  97 -               list_del_init(&flow->backlogchain);
  98 -       } else {
  99 -               i = flow;
 100 -
 101 -               list_for_each_entry_continue(i, &fq->backlogs, backlogchain)
 102 -                       if (i->backlog < flow->backlog)
 103 -                               break;
 104 -
 105 -               list_move_tail(&flow->backlogchain,
 106 -                              &i->backlogchain);
 107 -       }
 108 -}
 109 -
 110  static struct sk_buff *fq_flow_dequeue(struct fq *fq,
 111                                        struct fq_flow *flow)
 112  {
 113 @@ -62,7 +56,6 @@ static struct sk_buff *fq_flow_dequeue(s
 114                 return NULL;
 115
 116         fq_adjust_removal(fq, flow, skb);
 117 -       fq_rejigger_backlog(fq, flow);
 118
 119         return skb;
 120  }
 121 @@ -90,7 +83,6 @@ static int fq_flow_drop(struct fq *fq, s
 122         } while (packets < pending);
 123
 124         __fq_adjust_removal(fq, flow, packets, bytes, truesize);
 125 -       fq_rejigger_backlog(fq, flow);
 126
 127         return packets;
 128  }
 129 @@ -170,22 +162,36 @@ static struct fq_flow *fq_flow_classify(
 130         return flow;
 131  }
 132
 133 -static void fq_recalc_backlog(struct fq *fq,
 134 -                             struct fq_tin *tin,
 135 -                             struct fq_flow *flow)
 136 +static struct fq_flow *fq_find_fattest_flow(struct fq *fq)
 137  {
 138 -       struct fq_flow *i;
 139 +       struct fq_tin *tin;
 140 +       struct fq_flow *flow = NULL;
 141 +       u32 len = 0;
 142 +       int i;
 143
 144 -       if (list_empty(&flow->backlogchain))
 145 -               list_add_tail(&flow->backlogchain, &fq->backlogs);
 146 +       for_each_set_bit(i, fq->flows_bitmap, fq->flows_cnt) {
 147 +               struct fq_flow *cur = &fq->flows[i];
 148 +               unsigned int cur_len;
 149
 150 -       i = flow;
 151 -       list_for_each_entry_continue_reverse(i, &fq->backlogs,
 152 -                                            backlogchain)
 153 -               if (i->backlog > flow->backlog)
 154 -                       break;
 155 +               cur_len = cur->backlog;
 156 +               if (cur_len <= len)
 157 +                       continue;
 158
 159 -       list_move(&flow->backlogchain, &i->backlogchain);
 160 +               flow = cur;
 161 +               len = cur_len;
 162 +       }
 163 +
 164 +       list_for_each_entry(tin, &fq->tin_backlog, tin_list) {
 165 +               unsigned int cur_len = tin->default_flow.backlog;
 166 +
 167 +               if (cur_len <= len)
 168 +                       continue;
 169 +
 170 +               flow = &tin->default_flow;
 171 +               len = cur_len;
 172 +       }
 173 +
 174 +       return flow;
 175  }
 176
 177  static void fq_tin_enqueue(struct fq *fq,
 178 @@ -200,6 +206,13 @@ static void fq_tin_enqueue(struct fq *fq
 179
 180         flow = fq_flow_classify(fq, tin, idx, skb);
 181
 182 +       if (!flow->backlog) {
 183 +               if (flow != &tin->default_flow)
 184 +                       __set_bit(idx, fq->flows_bitmap);
 185 +               else if (list_empty(&tin->tin_list))
 186 +                       list_add(&tin->tin_list, &fq->tin_backlog);
 187 +       }
 188 +
 189         flow->tin = tin;
 190         flow->backlog += skb->len;
 191         tin->backlog_bytes += skb->len;
 192 @@ -207,8 +220,6 @@ static void fq_tin_enqueue(struct fq *fq
 193         fq->memory_usage += skb->truesize;
 194         fq->backlog++;
 195
 196 -       fq_recalc_backlog(fq, tin, flow);
 197 -
 198         if (list_empty(&flow->flowchain)) {
 199                 flow->deficit = fq->quantum;
 200                 list_add_tail(&flow->flowchain,
 201 @@ -218,9 +229,7 @@ static void fq_tin_enqueue(struct fq *fq
 202         __skb_queue_tail(&flow->queue, skb);
 203         oom = (fq->memory_usage > fq->memory_limit);
 204         while (fq->backlog > fq->limit || oom) {
 205 -               flow = list_first_entry_or_null(&fq->backlogs,
 206 -                                               struct fq_flow,
 207 -                                               backlogchain);
 208 +               flow = fq_find_fattest_flow(fq);
 209                 if (!flow)
 210                         return;
 211
 212 @@ -255,8 +264,6 @@ static void fq_flow_filter(struct fq *fq
 213                 fq_adjust_removal(fq, flow, skb);
 214                 free_func(fq, tin, flow, skb);
 215         }
 216 -
 217 -       fq_rejigger_backlog(fq, flow);
 218  }
 219
 220  static void fq_tin_filter(struct fq *fq,
 221 @@ -279,16 +286,18 @@ static void fq_flow_reset(struct fq *fq,
 222                           struct fq_flow *flow,
 223                           fq_skb_free_t free_func)
 224  {
 225 +       struct fq_tin *tin = flow->tin;
 226         struct sk_buff *skb;
 227
 228         while ((skb = fq_flow_dequeue(fq, flow)))
 229 -               free_func(fq, flow->tin, flow, skb);
 230 +               free_func(fq, tin, flow, skb);
 231
 232 -       if (!list_empty(&flow->flowchain))
 233 +       if (!list_empty(&flow->flowchain)) {
 234                 list_del_init(&flow->flowchain);
 235 -
 236 -       if (!list_empty(&flow->backlogchain))
 237 -               list_del_init(&flow->backlogchain);
 238 +               if (list_empty(&tin->new_flows) &&
 239 +                   list_empty(&tin->old_flows))
 240 +                       list_del_init(&tin->tin_list);
 241 +       }
 242
 243         flow->tin = NULL;
 244
 245 @@ -314,6 +323,7 @@ static void fq_tin_reset(struct fq *fq,
 246                 fq_flow_reset(fq, flow, free_func);
 247         }
 248
 249 +       WARN_ON_ONCE(!list_empty(&tin->tin_list));
 250         WARN_ON_ONCE(tin->backlog_bytes);
 251         WARN_ON_ONCE(tin->backlog_packets);
 252  }
 253 @@ -321,7 +331,6 @@ static void fq_tin_reset(struct fq *fq,
 254  static void fq_flow_init(struct fq_flow *flow)
 255  {
 256         INIT_LIST_HEAD(&flow->flowchain);
 257 -       INIT_LIST_HEAD(&flow->backlogchain);
 258         __skb_queue_head_init(&flow->queue);
 259  }
 260
 261 @@ -329,6 +338,7 @@ static void fq_tin_init(struct fq_tin *t
 262  {
 263         INIT_LIST_HEAD(&tin->new_flows);
 264         INIT_LIST_HEAD(&tin->old_flows);
 265 +       INIT_LIST_HEAD(&tin->tin_list);
 266         fq_flow_init(&tin->default_flow);
 267  }
 268
 269 @@ -337,8 +347,8 @@ static int fq_init(struct fq *fq, int fl
 270         int i;
 271
 272         memset(fq, 0, sizeof(fq[0]));
 273 -       INIT_LIST_HEAD(&fq->backlogs);
 274         spin_lock_init(&fq->lock);
 275 +       INIT_LIST_HEAD(&fq->tin_backlog);
 276         fq->flows_cnt = max_t(u32, flows_cnt, 1);
 277         fq->quantum = 300;
 278         fq->limit = 8192;
 279 @@ -348,6 +358,14 @@ static int fq_init(struct fq *fq, int fl
 280         if (!fq->flows)
 281                 return -ENOMEM;
 282
 283 +       fq->flows_bitmap = kcalloc(BITS_TO_LONGS(fq->flows_cnt), sizeof(long),
 284 +                                  GFP_KERNEL);
 285 +       if (!fq->flows_bitmap) {
 286 +               kvfree(fq->flows);
 287 +               fq->flows = NULL;
 288 +               return -ENOMEM;
 289 +       }
 290 +
 291         for (i = 0; i < fq->flows_cnt; i++)
 292                 fq_flow_init(&fq->flows[i]);
 293
 294 @@ -364,6 +382,9 @@ static void fq_reset(struct fq *fq,
 295
 296         kvfree(fq->flows);
 297         fq->flows = NULL;
 298 +
 299 +       kfree(fq->flows_bitmap);
 300 +       fq->flows_bitmap = NULL;
 301  }
 302
 303  #endif
 304 --- a/net/mac80211/tx.c
 305 +++ b/net/mac80211/tx.c
 306 @@ -3364,8 +3364,6 @@ out_recalc:
 307         if (head->len != orig_len) {
 308                 flow->backlog += head->len - orig_len;
 309                 tin->backlog_bytes += head->len - orig_len;
 310 -
 311 -               fq_recalc_backlog(fq, tin, flow);
 312         }
 313  out:
 314         spin_unlock_bh(&fq->lock);