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_perturb(skb, fq->perturbation);
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);
311 fq->perturbation = prandom_u32();
314 fq->memory_limit = 16 << 20; /* 16 MBytes */
316 fq->flows = kcalloc(fq->flows_cnt, sizeof(fq->flows[0]), GFP_KERNEL);
320 for (i = 0; i < fq->flows_cnt; i++)
321 fq_flow_init(&fq->flows[i]);
326 static void fq_reset(struct fq *fq,
327 fq_skb_free_t free_func)
331 for (i = 0; i < fq->flows_cnt; i++)
332 fq_flow_reset(fq, &fq->flows[i], free_func);