xref: /linux/include/net/fq_impl.h (revision 7ae9fb1b7ecbb5d85d07857943f677fd1a559b18)
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 
15 static void
__fq_adjust_removal(struct fq * fq,struct fq_flow * flow,unsigned int packets,unsigned int bytes,unsigned int truesize)16 __fq_adjust_removal(struct fq *fq, struct fq_flow *flow, unsigned int packets,
17 		    unsigned int bytes, unsigned int truesize)
18 {
19 	struct fq_tin *tin = flow->tin;
20 	int idx;
21 
22 	tin->backlog_bytes -= bytes;
23 	tin->backlog_packets -= packets;
24 	flow->backlog -= bytes;
25 	fq->backlog -= packets;
26 	fq->memory_usage -= truesize;
27 
28 	if (flow->backlog)
29 		return;
30 
31 	if (flow == &tin->default_flow) {
32 		list_del_init(&tin->tin_list);
33 		return;
34 	}
35 
36 	idx = flow - fq->flows;
37 	__clear_bit(idx, fq->flows_bitmap);
38 }
39 
fq_adjust_removal(struct fq * fq,struct fq_flow * flow,struct sk_buff * skb)40 static void fq_adjust_removal(struct fq *fq,
41 			      struct fq_flow *flow,
42 			      struct sk_buff *skb)
43 {
44 	__fq_adjust_removal(fq, flow, 1, skb->len, skb->truesize);
45 }
46 
fq_flow_dequeue(struct fq * fq,struct fq_flow * flow)47 static struct sk_buff *fq_flow_dequeue(struct fq *fq,
48 				       struct fq_flow *flow)
49 {
50 	struct sk_buff *skb;
51 
52 	lockdep_assert_held(&fq->lock);
53 
54 	skb = __skb_dequeue(&flow->queue);
55 	if (!skb)
56 		return NULL;
57 
58 	fq_adjust_removal(fq, flow, skb);
59 
60 	return skb;
61 }
62 
fq_flow_drop(struct fq * fq,struct fq_flow * flow,fq_skb_free_t free_func)63 static int fq_flow_drop(struct fq *fq, struct fq_flow *flow,
64 			fq_skb_free_t free_func)
65 {
66 	unsigned int packets = 0, bytes = 0, truesize = 0;
67 	struct fq_tin *tin = flow->tin;
68 	struct sk_buff *skb;
69 	int pending;
70 
71 	lockdep_assert_held(&fq->lock);
72 
73 	pending = min_t(int, 32, skb_queue_len(&flow->queue) / 2);
74 	do {
75 		skb = __skb_dequeue(&flow->queue);
76 		if (!skb)
77 			break;
78 
79 		packets++;
80 		bytes += skb->len;
81 		truesize += skb->truesize;
82 		free_func(fq, tin, flow, skb);
83 	} while (packets < pending);
84 
85 	__fq_adjust_removal(fq, flow, packets, bytes, truesize);
86 
87 	return packets;
88 }
89 
fq_tin_dequeue(struct fq * fq,struct fq_tin * tin,fq_tin_dequeue_t dequeue_func)90 static struct sk_buff *fq_tin_dequeue(struct fq *fq,
91 				      struct fq_tin *tin,
92 				      fq_tin_dequeue_t dequeue_func)
93 {
94 	struct fq_flow *flow;
95 	struct list_head *head;
96 	struct sk_buff *skb;
97 
98 	lockdep_assert_held(&fq->lock);
99 
100 begin:
101 	head = &tin->new_flows;
102 	if (list_empty(head)) {
103 		head = &tin->old_flows;
104 		if (list_empty(head))
105 			return NULL;
106 	}
107 
108 	flow = list_first_entry(head, struct fq_flow, flowchain);
109 
110 	if (flow->deficit <= 0) {
111 		flow->deficit += fq->quantum;
112 		list_move_tail(&flow->flowchain,
113 			       &tin->old_flows);
114 		goto begin;
115 	}
116 
117 	skb = dequeue_func(fq, tin, flow);
118 	if (!skb) {
119 		/* force a pass through old_flows to prevent starvation */
120 		if ((head == &tin->new_flows) &&
121 		    !list_empty(&tin->old_flows)) {
122 			list_move_tail(&flow->flowchain, &tin->old_flows);
123 		} else {
124 			list_del_init(&flow->flowchain);
125 			flow->tin = NULL;
126 		}
127 		goto begin;
128 	}
129 
130 	flow->deficit -= skb->len;
131 	tin->tx_bytes += skb->len;
132 	tin->tx_packets++;
133 
134 	return skb;
135 }
136 
fq_flow_idx(struct fq * fq,struct sk_buff * skb)137 static u32 fq_flow_idx(struct fq *fq, struct sk_buff *skb)
138 {
139 	u32 hash = skb_get_hash(skb);
140 
141 	return reciprocal_scale(hash, fq->flows_cnt);
142 }
143 
fq_flow_classify(struct fq * fq,struct fq_tin * tin,u32 idx,struct sk_buff * skb)144 static struct fq_flow *fq_flow_classify(struct fq *fq,
145 					struct fq_tin *tin, u32 idx,
146 					struct sk_buff *skb)
147 {
148 	struct fq_flow *flow;
149 
150 	lockdep_assert_held(&fq->lock);
151 
152 	flow = &fq->flows[idx];
153 	if (flow->tin && flow->tin != tin) {
154 		flow = &tin->default_flow;
155 		tin->collisions++;
156 		fq->collisions++;
157 	}
158 
159 	if (!flow->tin)
160 		tin->flows++;
161 
162 	return flow;
163 }
164 
fq_find_fattest_flow(struct fq * fq)165 static struct fq_flow *fq_find_fattest_flow(struct fq *fq)
166 {
167 	struct fq_tin *tin;
168 	struct fq_flow *flow = NULL;
169 	u32 len = 0;
170 	int i;
171 
172 	for_each_set_bit(i, fq->flows_bitmap, fq->flows_cnt) {
173 		struct fq_flow *cur = &fq->flows[i];
174 		unsigned int cur_len;
175 
176 		cur_len = cur->backlog;
177 		if (cur_len <= len)
178 			continue;
179 
180 		flow = cur;
181 		len = cur_len;
182 	}
183 
184 	list_for_each_entry(tin, &fq->tin_backlog, tin_list) {
185 		unsigned int cur_len = tin->default_flow.backlog;
186 
187 		if (cur_len <= len)
188 			continue;
189 
190 		flow = &tin->default_flow;
191 		len = cur_len;
192 	}
193 
194 	return flow;
195 }
196 
fq_tin_enqueue(struct fq * fq,struct fq_tin * tin,u32 idx,struct sk_buff * skb,fq_skb_free_t free_func)197 static void fq_tin_enqueue(struct fq *fq,
198 			   struct fq_tin *tin, u32 idx,
199 			   struct sk_buff *skb,
200 			   fq_skb_free_t free_func)
201 {
202 	struct fq_flow *flow;
203 	struct sk_buff *next;
204 	bool oom;
205 
206 	lockdep_assert_held(&fq->lock);
207 
208 	flow = fq_flow_classify(fq, tin, idx, skb);
209 
210 	if (!flow->backlog) {
211 		if (flow != &tin->default_flow)
212 			__set_bit(idx, fq->flows_bitmap);
213 		else if (list_empty(&tin->tin_list))
214 			list_add(&tin->tin_list, &fq->tin_backlog);
215 	}
216 
217 	flow->tin = tin;
218 	skb_list_walk_safe(skb, skb, next) {
219 		skb_mark_not_on_list(skb);
220 		flow->backlog += skb->len;
221 		tin->backlog_bytes += skb->len;
222 		tin->backlog_packets++;
223 		fq->memory_usage += skb->truesize;
224 		fq->backlog++;
225 		__skb_queue_tail(&flow->queue, skb);
226 	}
227 
228 	if (list_empty(&flow->flowchain)) {
229 		flow->deficit = fq->quantum;
230 		list_add_tail(&flow->flowchain,
231 			      &tin->new_flows);
232 	}
233 
234 	oom = (fq->memory_usage > fq->memory_limit);
235 	while (fq->backlog > fq->limit || oom) {
236 		flow = fq_find_fattest_flow(fq);
237 		if (!flow)
238 			return;
239 
240 		if (!fq_flow_drop(fq, flow, free_func))
241 			return;
242 
243 		flow->tin->overlimit++;
244 		fq->overlimit++;
245 		if (oom) {
246 			fq->overmemory++;
247 			oom = (fq->memory_usage > fq->memory_limit);
248 		}
249 	}
250 }
251 
fq_flow_filter(struct fq * fq,struct fq_flow * flow,fq_skb_filter_t filter_func,void * filter_data,fq_skb_free_t free_func)252 static void fq_flow_filter(struct fq *fq,
253 			   struct fq_flow *flow,
254 			   fq_skb_filter_t filter_func,
255 			   void *filter_data,
256 			   fq_skb_free_t free_func)
257 {
258 	struct fq_tin *tin = flow->tin;
259 	struct sk_buff *skb, *tmp;
260 
261 	lockdep_assert_held(&fq->lock);
262 
263 	skb_queue_walk_safe(&flow->queue, skb, tmp) {
264 		if (!filter_func(fq, tin, flow, skb, filter_data))
265 			continue;
266 
267 		__skb_unlink(skb, &flow->queue);
268 		fq_adjust_removal(fq, flow, skb);
269 		free_func(fq, tin, flow, skb);
270 	}
271 }
272 
fq_tin_filter(struct fq * fq,struct fq_tin * tin,fq_skb_filter_t filter_func,void * filter_data,fq_skb_free_t free_func)273 static void fq_tin_filter(struct fq *fq,
274 			  struct fq_tin *tin,
275 			  fq_skb_filter_t filter_func,
276 			  void *filter_data,
277 			  fq_skb_free_t free_func)
278 {
279 	struct fq_flow *flow;
280 
281 	lockdep_assert_held(&fq->lock);
282 
283 	list_for_each_entry(flow, &tin->new_flows, flowchain)
284 		fq_flow_filter(fq, flow, filter_func, filter_data, free_func);
285 	list_for_each_entry(flow, &tin->old_flows, flowchain)
286 		fq_flow_filter(fq, flow, filter_func, filter_data, free_func);
287 }
288 
fq_flow_reset(struct fq * fq,struct fq_flow * flow,fq_skb_free_t free_func)289 static void fq_flow_reset(struct fq *fq,
290 			  struct fq_flow *flow,
291 			  fq_skb_free_t free_func)
292 {
293 	struct fq_tin *tin = flow->tin;
294 	struct sk_buff *skb;
295 
296 	while ((skb = fq_flow_dequeue(fq, flow)))
297 		free_func(fq, tin, flow, skb);
298 
299 	if (!list_empty(&flow->flowchain)) {
300 		list_del_init(&flow->flowchain);
301 		if (list_empty(&tin->new_flows) &&
302 		    list_empty(&tin->old_flows))
303 			list_del_init(&tin->tin_list);
304 	}
305 
306 	flow->tin = NULL;
307 
308 	WARN_ON_ONCE(flow->backlog);
309 }
310 
fq_tin_reset(struct fq * fq,struct fq_tin * tin,fq_skb_free_t free_func)311 static void fq_tin_reset(struct fq *fq,
312 			 struct fq_tin *tin,
313 			 fq_skb_free_t free_func)
314 {
315 	struct list_head *head;
316 	struct fq_flow *flow;
317 
318 	for (;;) {
319 		head = &tin->new_flows;
320 		if (list_empty(head)) {
321 			head = &tin->old_flows;
322 			if (list_empty(head))
323 				break;
324 		}
325 
326 		flow = list_first_entry(head, struct fq_flow, flowchain);
327 		fq_flow_reset(fq, flow, free_func);
328 	}
329 
330 	WARN_ON_ONCE(!list_empty(&tin->tin_list));
331 	WARN_ON_ONCE(tin->backlog_bytes);
332 	WARN_ON_ONCE(tin->backlog_packets);
333 }
334 
fq_flow_init(struct fq_flow * flow)335 static void fq_flow_init(struct fq_flow *flow)
336 {
337 	INIT_LIST_HEAD(&flow->flowchain);
338 	__skb_queue_head_init(&flow->queue);
339 }
340 
fq_tin_init(struct fq_tin * tin)341 static void fq_tin_init(struct fq_tin *tin)
342 {
343 	INIT_LIST_HEAD(&tin->new_flows);
344 	INIT_LIST_HEAD(&tin->old_flows);
345 	INIT_LIST_HEAD(&tin->tin_list);
346 	fq_flow_init(&tin->default_flow);
347 }
348 
fq_init(struct fq * fq,int flows_cnt)349 static int fq_init(struct fq *fq, int flows_cnt)
350 {
351 	int i;
352 
353 	memset(fq, 0, sizeof(fq[0]));
354 	spin_lock_init(&fq->lock);
355 	INIT_LIST_HEAD(&fq->tin_backlog);
356 	fq->flows_cnt = max_t(u32, flows_cnt, 1);
357 	fq->quantum = 300;
358 	fq->limit = 8192;
359 	fq->memory_limit = 16 << 20; /* 16 MBytes */
360 
361 	fq->flows = kvcalloc(fq->flows_cnt, sizeof(fq->flows[0]), GFP_KERNEL);
362 	if (!fq->flows)
363 		return -ENOMEM;
364 
365 	fq->flows_bitmap = bitmap_zalloc(fq->flows_cnt, GFP_KERNEL);
366 	if (!fq->flows_bitmap) {
367 		kvfree(fq->flows);
368 		fq->flows = NULL;
369 		return -ENOMEM;
370 	}
371 
372 	for (i = 0; i < fq->flows_cnt; i++)
373 		fq_flow_init(&fq->flows[i]);
374 
375 	return 0;
376 }
377 
fq_reset(struct fq * fq,fq_skb_free_t free_func)378 static void fq_reset(struct fq *fq,
379 		     fq_skb_free_t free_func)
380 {
381 	int i;
382 
383 	for (i = 0; i < fq->flows_cnt; i++)
384 		fq_flow_reset(fq, &fq->flows[i], free_func);
385 
386 	kvfree(fq->flows);
387 	fq->flows = NULL;
388 
389 	bitmap_free(fq->flows_bitmap);
390 	fq->flows_bitmap = NULL;
391 }
392 
393 #endif
394