~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/include/net/fq_impl.h

Version: ~ [ linux-5.14-rc1 ] ~ [ linux-5.13.1 ] ~ [ linux-5.12.16 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.49 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.131 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.197 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.239 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.275 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.275 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.18.140 ] ~ [ linux-3.16.85 ] ~ [ linux-3.14.79 ] ~ [ linux-3.12.74 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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
339 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp