include/net/fq_impl.h

   1 /* SPDX-License-Identifier: GPL-2.0-only */
   2 /*
   3  * Copyright (c) 2016 Qualcomm Atheros, Inc
   4  *
   5  * Based on net/sched/sch_fq_codel.c
   6  */
   7 #ifndef __NET_SCHED_FQ_IMPL_H
   8 #define __NET_SCHED_FQ_IMPL_H
   9
  10 #include <net/fq.h>
  11
  12 /* functions that are embedded into includer */
  13
  14 static void fq_adjust_removal(struct fq *fq,
  15                               struct fq_flow *flow,
  16                               struct sk_buff *skb)
  17 {
  18         struct fq_tin *tin = flow->tin;
  19
  20         tin->backlog_bytes -= skb->len;
  21         tin->backlog_packets--;
  22         flow->backlog -= skb->len;
  23         fq->backlog--;
  24         fq->memory_usage -= skb->truesize;
  25 }
  26
  27 static void fq_rejigger_backlog(struct fq *fq, struct fq_flow *flow)
  28 {
  29         struct fq_flow *i;
  30
  31         if (flow->backlog == 0) {
  32                 list_del_init(&flow->backlogchain);
  33         } else {
  34                 i = flow;
  35
  36                 list_for_each_entry_continue(i, &fq->backlogs, backlogchain)
  37                         if (i->backlog < flow->backlog)
  38                                 break;
  39
  40                 list_move_tail(&flow->backlogchain,
  41                                &i->backlogchain);
  42         }
  43 }
  44
  45 static struct sk_buff *fq_flow_dequeue(struct fq *fq,
  46                                        struct fq_flow *flow)
  47 {
  48         struct sk_buff *skb;
  49
  50         lockdep_assert_held(&fq->lock);
  51
  52         skb = __skb_dequeue(&flow->queue);
  53         if (!skb)
  54                 return NULL;
  55
  56         fq_adjust_removal(fq, flow, skb);
  57         fq_rejigger_backlog(fq, flow);
  58
  59         return skb;
  60 }
  61
  62 static struct sk_buff *fq_tin_dequeue(struct fq *fq,
  63                                       struct fq_tin *tin,
  64                                       fq_tin_dequeue_t dequeue_func)
  65 {
  66         struct fq_flow *flow;
  67         struct list_head *head;
  68         struct sk_buff *skb;
  69
  70         lockdep_assert_held(&fq->lock);
  71
  72 begin:
  73         head = &tin->new_flows;
  74         if (list_empty(head)) {
  75                 head = &tin->old_flows;
  76                 if (list_empty(head))
  77                         return NULL;
  78         }
  79
  80         flow = list_first_entry(head, struct fq_flow, flowchain);
  81
  82         if (flow->deficit <= 0) {
  83                 flow->deficit += fq->quantum;
  84                 list_move_tail(&flow->flowchain,
  85                                &tin->old_flows);
  86                 goto begin;
  87         }
  88
  89         skb = dequeue_func(fq, tin, flow);
  90         if (!skb) {
  91                 /* force a pass through old_flows to prevent starvation */
  92                 if ((head == &tin->new_flows) &&
  93                     !list_empty(&tin->old_flows)) {
  94                         list_move_tail(&flow->flowchain, &tin->old_flows);
  95                 } else {
  96                         list_del_init(&flow->flowchain);
  97                         flow->tin = NULL;
  98                 }
  99                 goto begin;
 100         }
 101
 102         flow->deficit -= skb->len;
 103         tin->tx_bytes += skb->len;
 104         tin->tx_packets++;
 105
 106         return skb;
 107 }
 108
 109 static u32 fq_flow_idx(struct fq *fq, struct sk_buff *skb)
 110 {
 111         u32 hash = skb_get_hash_perturb(skb, &fq->perturbation);
 112
 113         return reciprocal_scale(hash, fq->flows_cnt);
 114 }
 115
 116 static struct fq_flow *fq_flow_classify(struct fq *fq,
 117                                         struct fq_tin *tin, u32 idx,
 118                                         struct sk_buff *skb,
 119                                         fq_flow_get_default_t get_default_func)
 120 {
 121         struct fq_flow *flow;
 122
 123         lockdep_assert_held(&fq->lock);
 124
 125         flow = &fq->flows[idx];
 126         if (flow->tin && flow->tin != tin) {
 127                 flow = get_default_func(fq, tin, idx, skb);
 128                 tin->collisions++;
 129                 fq->collisions++;
 130         }
 131
 132         if (!flow->tin)
 133                 tin->flows++;
 134
 135         return flow;
 136 }
 137
 138 static void fq_recalc_backlog(struct fq *fq,
 139                               struct fq_tin *tin,
 140                               struct fq_flow *flow)
 141 {
 142         struct fq_flow *i;
 143
 144         if (list_empty(&flow->backlogchain))
 145                 list_add_tail(&flow->backlogchain, &fq->backlogs);
 146
 147         i = flow;
 148         list_for_each_entry_continue_reverse(i, &fq->backlogs,
 149                                              backlogchain)
 150                 if (i->backlog > flow->backlog)
 151                         break;
 152
 153         list_move(&flow->backlogchain, &i->backlogchain);
 154 }
 155
 156 static void fq_tin_enqueue(struct fq *fq,
 157                            struct fq_tin *tin, u32 idx,
 158                            struct sk_buff *skb,
 159                            fq_skb_free_t free_func,
 160                            fq_flow_get_default_t get_default_func)
 161 {
 162         struct fq_flow *flow;
 163         bool oom;
 164
 165         lockdep_assert_held(&fq->lock);
 166
 167         flow = fq_flow_classify(fq, tin, idx, skb, get_default_func);
 168
 169         flow->tin = tin;
 170         flow->backlog += skb->len;
 171         tin->backlog_bytes += skb->len;
 172         tin->backlog_packets++;
 173         fq->memory_usage += skb->truesize;
 174         fq->backlog++;
 175
 176         fq_recalc_backlog(fq, tin, flow);
 177
 178         if (list_empty(&flow->flowchain)) {
 179                 flow->deficit = fq->quantum;
 180                 list_add_tail(&flow->flowchain,
 181                               &tin->new_flows);
 182         }
 183
 184         __skb_queue_tail(&flow->queue, skb);
 185         oom = (fq->memory_usage > fq->memory_limit);
 186         while (fq->backlog > fq->limit || oom) {
 187                 flow = list_first_entry_or_null(&fq->backlogs,
 188                                                 struct fq_flow,
 189                                                 backlogchain);
 190                 if (!flow)
 191                         return;
 192
 193                 skb = fq_flow_dequeue(fq, flow);
 194                 if (!skb)
 195                         return;
 196
 197                 free_func(fq, flow->tin, flow, skb);
 198
 199                 flow->tin->overlimit++;
 200                 fq->overlimit++;
 201                 if (oom) {
 202                         fq->overmemory++;
 203                         oom = (fq->memory_usage > fq->memory_limit);
 204                 }
 205         }
 206 }
 207
 208 static void fq_flow_filter(struct fq *fq,
 209                            struct fq_flow *flow,
 210                            fq_skb_filter_t filter_func,
 211                            void *filter_data,
 212                            fq_skb_free_t free_func)
 213 {
 214         struct fq_tin *tin = flow->tin;
 215         struct sk_buff *skb, *tmp;
 216
 217         lockdep_assert_held(&fq->lock);
 218
 219         skb_queue_walk_safe(&flow->queue, skb, tmp) {
 220                 if (!filter_func(fq, tin, flow, skb, filter_data))
 221                         continue;
 222
 223                 __skb_unlink(skb, &flow->queue);
 224                 fq_adjust_removal(fq, flow, skb);
 225                 free_func(fq, tin, flow, skb);
 226         }
 227
 228         fq_rejigger_backlog(fq, flow);
 229 }
 230
 231 static void fq_tin_filter(struct fq *fq,
 232                           struct fq_tin *tin,
 233                           fq_skb_filter_t filter_func,
 234                           void *filter_data,
 235                           fq_skb_free_t free_func)
 236 {
 237         struct fq_flow *flow;
 238
 239         lockdep_assert_held(&fq->lock);
 240
 241         list_for_each_entry(flow, &tin->new_flows, flowchain)
 242                 fq_flow_filter(fq, flow, filter_func, filter_data, free_func);
 243         list_for_each_entry(flow, &tin->old_flows, flowchain)
 244                 fq_flow_filter(fq, flow, filter_func, filter_data, free_func);
 245 }
 246
 247 static void fq_flow_reset(struct fq *fq,
 248                           struct fq_flow *flow,
 249                           fq_skb_free_t free_func)
 250 {
 251         struct sk_buff *skb;
 252
 253         while ((skb = fq_flow_dequeue(fq, flow)))
 254                 free_func(fq, flow->tin, flow, skb);
 255
 256         if (!list_empty(&flow->flowchain))
 257                 list_del_init(&flow->flowchain);
 258
 259         if (!list_empty(&flow->backlogchain))
 260                 list_del_init(&flow->backlogchain);
 261
 262         flow->tin = NULL;
 263
 264         WARN_ON_ONCE(flow->backlog);
 265 }
 266
 267 static void fq_tin_reset(struct fq *fq,
 268                          struct fq_tin *tin,
 269                          fq_skb_free_t free_func)
 270 {
 271         struct list_head *head;
 272         struct fq_flow *flow;
 273
 274         for (;;) {
 275                 head = &tin->new_flows;
 276                 if (list_empty(head)) {
 277                         head = &tin->old_flows;
 278                         if (list_empty(head))
 279                                 break;
 280                 }
 281
 282                 flow = list_first_entry(head, struct fq_flow, flowchain);
 283                 fq_flow_reset(fq, flow, free_func);
 284         }
 285
 286         WARN_ON_ONCE(tin->backlog_bytes);
 287         WARN_ON_ONCE(tin->backlog_packets);
 288 }
 289
 290 static void fq_flow_init(struct fq_flow *flow)
 291 {
 292         INIT_LIST_HEAD(&flow->flowchain);
 293         INIT_LIST_HEAD(&flow->backlogchain);
 294         __skb_queue_head_init(&flow->queue);
 295 }
 296
 297 static void fq_tin_init(struct fq_tin *tin)
 298 {
 299         INIT_LIST_HEAD(&tin->new_flows);
 300         INIT_LIST_HEAD(&tin->old_flows);
 301 }
 302
 303 static int fq_init(struct fq *fq, int flows_cnt)
 304 {
 305         int i;
 306
 307         memset(fq, 0, sizeof(fq[0]));
 308         INIT_LIST_HEAD(&fq->backlogs);
 309         spin_lock_init(&fq->lock);
 310         fq->flows_cnt = max_t(u32, flows_cnt, 1);
 311         get_random_bytes(&fq->perturbation, sizeof(fq->perturbation));
 312         fq->quantum = 300;
 313         fq->limit = 8192;
 314         fq->memory_limit = 16 << 20; /* 16 MBytes */
 315
 316         fq->flows = kvcalloc(fq->flows_cnt, sizeof(fq->flows[0]), GFP_KERNEL);
 317         if (!fq->flows)
 318                 return -ENOMEM;
 319
 320         for (i = 0; i < fq->flows_cnt; i++)
 321                 fq_flow_init(&fq->flows[i]);
 322
 323         return 0;
 324 }
 325
 326 static void fq_reset(struct fq *fq,
 327                      fq_skb_free_t free_func)
 328 {
 329         int i;
 330
 331         for (i = 0; i < fq->flows_cnt; i++)
 332                 fq_flow_reset(fq, &fq->flows[i], free_func);
 333
 334         kvfree(fq->flows);
 335         fq->flows = NULL;
 336 }
 337
 338 #endif