1 /* SPDX-License-Identifier: GPL-2.0-only */
3 * Copyright (c) 2016 Qualcomm Atheros, Inc
5 * Based on net/sched/sch_fq_codel.c
7 #ifndef __NET_SCHED_FQ_IMPL_H
8 #define __NET_SCHED_FQ_IMPL_H
12 /* functions that are embedded into includer */
14 static void fq_adjust_removal(struct fq
*fq
,
18 struct fq_tin
*tin
= flow
->tin
;
20 tin
->backlog_bytes
-= skb
->len
;
21 tin
->backlog_packets
--;
22 flow
->backlog
-= skb
->len
;
24 fq
->memory_usage
-= skb
->truesize
;
27 static void fq_rejigger_backlog(struct fq
*fq
, struct fq_flow
*flow
)
31 if (flow
->backlog
== 0) {
32 list_del_init(&flow
->backlogchain
);
36 list_for_each_entry_continue(i
, &fq
->backlogs
, backlogchain
)
37 if (i
->backlog
< flow
->backlog
)
40 list_move_tail(&flow
->backlogchain
,
45 static struct sk_buff
*fq_flow_dequeue(struct fq
*fq
,
50 lockdep_assert_held(&fq
->lock
);
52 skb
= __skb_dequeue(&flow
->queue
);
56 fq_adjust_removal(fq
, flow
, skb
);
57 fq_rejigger_backlog(fq
, flow
);
62 static struct sk_buff
*fq_tin_dequeue(struct fq
*fq
,
64 fq_tin_dequeue_t dequeue_func
)
67 struct list_head
*head
;
70 lockdep_assert_held(&fq
->lock
);
73 head
= &tin
->new_flows
;
74 if (list_empty(head
)) {
75 head
= &tin
->old_flows
;
80 flow
= list_first_entry(head
, struct fq_flow
, flowchain
);
82 if (flow
->deficit
<= 0) {
83 flow
->deficit
+= fq
->quantum
;
84 list_move_tail(&flow
->flowchain
,
89 skb
= dequeue_func(fq
, tin
, flow
);
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
);
96 list_del_init(&flow
->flowchain
);
102 flow
->deficit
-= skb
->len
;
103 tin
->tx_bytes
+= skb
->len
;
109 static u32
fq_flow_idx(struct fq
*fq
, struct sk_buff
*skb
)
111 u32 hash
= skb_get_hash(skb
);
113 return reciprocal_scale(hash
, fq
->flows_cnt
);
116 static struct fq_flow
*fq_flow_classify(struct fq
*fq
,
117 struct fq_tin
*tin
, u32 idx
,
119 fq_flow_get_default_t get_default_func
)
121 struct fq_flow
*flow
;
123 lockdep_assert_held(&fq
->lock
);
125 flow
= &fq
->flows
[idx
];
126 if (flow
->tin
&& flow
->tin
!= tin
) {
127 flow
= get_default_func(fq
, tin
, idx
, skb
);
138 static void fq_recalc_backlog(struct fq
*fq
,
140 struct fq_flow
*flow
)
144 if (list_empty(&flow
->backlogchain
))
145 list_add_tail(&flow
->backlogchain
, &fq
->backlogs
);
148 list_for_each_entry_continue_reverse(i
, &fq
->backlogs
,
150 if (i
->backlog
> flow
->backlog
)
153 list_move(&flow
->backlogchain
, &i
->backlogchain
);
156 static void fq_tin_enqueue(struct fq
*fq
,
157 struct fq_tin
*tin
, u32 idx
,
159 fq_skb_free_t free_func
,
160 fq_flow_get_default_t get_default_func
)
162 struct fq_flow
*flow
;
165 lockdep_assert_held(&fq
->lock
);
167 flow
= fq_flow_classify(fq
, tin
, idx
, skb
, get_default_func
);
170 flow
->backlog
+= skb
->len
;
171 tin
->backlog_bytes
+= skb
->len
;
172 tin
->backlog_packets
++;
173 fq
->memory_usage
+= skb
->truesize
;
176 fq_recalc_backlog(fq
, tin
, flow
);
178 if (list_empty(&flow
->flowchain
)) {
179 flow
->deficit
= fq
->quantum
;
180 list_add_tail(&flow
->flowchain
,
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
,
193 skb
= fq_flow_dequeue(fq
, flow
);
197 free_func(fq
, flow
->tin
, flow
, skb
);
199 flow
->tin
->overlimit
++;
203 oom
= (fq
->memory_usage
> fq
->memory_limit
);
208 static void fq_flow_filter(struct fq
*fq
,
209 struct fq_flow
*flow
,
210 fq_skb_filter_t filter_func
,
212 fq_skb_free_t free_func
)
214 struct fq_tin
*tin
= flow
->tin
;
215 struct sk_buff
*skb
, *tmp
;
217 lockdep_assert_held(&fq
->lock
);
219 skb_queue_walk_safe(&flow
->queue
, skb
, tmp
) {
220 if (!filter_func(fq
, tin
, flow
, skb
, filter_data
))
223 __skb_unlink(skb
, &flow
->queue
);
224 fq_adjust_removal(fq
, flow
, skb
);
225 free_func(fq
, tin
, flow
, skb
);
228 fq_rejigger_backlog(fq
, flow
);
231 static void fq_tin_filter(struct fq
*fq
,
233 fq_skb_filter_t filter_func
,
235 fq_skb_free_t free_func
)
237 struct fq_flow
*flow
;
239 lockdep_assert_held(&fq
->lock
);
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
);
247 static void fq_flow_reset(struct fq
*fq
,
248 struct fq_flow
*flow
,
249 fq_skb_free_t free_func
)
253 while ((skb
= fq_flow_dequeue(fq
, flow
)))
254 free_func(fq
, flow
->tin
, flow
, skb
);
256 if (!list_empty(&flow
->flowchain
))
257 list_del_init(&flow
->flowchain
);
259 if (!list_empty(&flow
->backlogchain
))
260 list_del_init(&flow
->backlogchain
);
264 WARN_ON_ONCE(flow
->backlog
);
267 static void fq_tin_reset(struct fq
*fq
,
269 fq_skb_free_t free_func
)
271 struct list_head
*head
;
272 struct fq_flow
*flow
;
275 head
= &tin
->new_flows
;
276 if (list_empty(head
)) {
277 head
= &tin
->old_flows
;
278 if (list_empty(head
))
282 flow
= list_first_entry(head
, struct fq_flow
, flowchain
);
283 fq_flow_reset(fq
, flow
, free_func
);
286 WARN_ON_ONCE(tin
->backlog_bytes
);
287 WARN_ON_ONCE(tin
->backlog_packets
);
290 static void fq_flow_init(struct fq_flow
*flow
)
292 INIT_LIST_HEAD(&flow
->flowchain
);
293 INIT_LIST_HEAD(&flow
->backlogchain
);
294 __skb_queue_head_init(&flow
->queue
);
297 static void fq_tin_init(struct fq_tin
*tin
)
299 INIT_LIST_HEAD(&tin
->new_flows
);
300 INIT_LIST_HEAD(&tin
->old_flows
);
303 static int fq_init(struct fq
*fq
, int flows_cnt
)
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);
313 fq
->memory_limit
= 16 << 20; /* 16 MBytes */
315 fq
->flows
= kvcalloc(fq
->flows_cnt
, sizeof(fq
->flows
[0]), GFP_KERNEL
);
319 for (i
= 0; i
< fq
->flows_cnt
; i
++)
320 fq_flow_init(&fq
->flows
[i
]);
325 static void fq_reset(struct fq
*fq
,
326 fq_skb_free_t free_func
)
330 for (i
= 0; i
< fq
->flows_cnt
; i
++)
331 fq_flow_reset(fq
, &fq
->flows
[i
], free_func
);