blob: 163f3ed0f05a741ed0f18933895f48a7c91bf754 [file] [log] [blame]
Michal Kazior557fc4a2016-04-22 14:20:13 +02001/*
2 * Copyright (c) 2016 Qualcomm Atheros, Inc
3 *
4 * GPL v2
5 *
6 * Based on net/sched/sch_fq_codel.c
7 */
8#ifndef __NET_SCHED_FQ_IMPL_H
9#define __NET_SCHED_FQ_IMPL_H
10
11#include <net/fq.h>
12
13/* functions that are embedded into includer */
14
15static struct sk_buff *fq_flow_dequeue(struct fq *fq,
16 struct fq_flow *flow)
17{
18 struct fq_tin *tin = flow->tin;
19 struct fq_flow *i;
20 struct sk_buff *skb;
21
22 lockdep_assert_held(&fq->lock);
23
24 skb = __skb_dequeue(&flow->queue);
25 if (!skb)
26 return NULL;
27
28 tin->backlog_bytes -= skb->len;
29 tin->backlog_packets--;
30 flow->backlog -= skb->len;
31 fq->backlog--;
32
33 if (flow->backlog == 0) {
34 list_del_init(&flow->backlogchain);
35 } else {
36 i = flow;
37
38 list_for_each_entry_continue(i, &fq->backlogs, backlogchain)
39 if (i->backlog < flow->backlog)
40 break;
41
42 list_move_tail(&flow->backlogchain,
43 &i->backlogchain);
44 }
45
46 return skb;
47}
48
49static struct sk_buff *fq_tin_dequeue(struct fq *fq,
50 struct fq_tin *tin,
51 fq_tin_dequeue_t dequeue_func)
52{
53 struct fq_flow *flow;
54 struct list_head *head;
55 struct sk_buff *skb;
56
57 lockdep_assert_held(&fq->lock);
58
59begin:
60 head = &tin->new_flows;
61 if (list_empty(head)) {
62 head = &tin->old_flows;
63 if (list_empty(head))
64 return NULL;
65 }
66
67 flow = list_first_entry(head, struct fq_flow, flowchain);
68
69 if (flow->deficit <= 0) {
70 flow->deficit += fq->quantum;
71 list_move_tail(&flow->flowchain,
72 &tin->old_flows);
73 goto begin;
74 }
75
76 skb = dequeue_func(fq, tin, flow);
77 if (!skb) {
78 /* force a pass through old_flows to prevent starvation */
79 if ((head == &tin->new_flows) &&
80 !list_empty(&tin->old_flows)) {
81 list_move_tail(&flow->flowchain, &tin->old_flows);
82 } else {
83 list_del_init(&flow->flowchain);
84 flow->tin = NULL;
85 }
86 goto begin;
87 }
88
89 flow->deficit -= skb->len;
90 tin->tx_bytes += skb->len;
91 tin->tx_packets++;
92
93 return skb;
94}
95
96static struct fq_flow *fq_flow_classify(struct fq *fq,
97 struct fq_tin *tin,
98 struct sk_buff *skb,
99 fq_flow_get_default_t get_default_func)
100{
101 struct fq_flow *flow;
102 u32 hash;
103 u32 idx;
104
105 lockdep_assert_held(&fq->lock);
106
107 hash = skb_get_hash_perturb(skb, fq->perturbation);
108 idx = reciprocal_scale(hash, fq->flows_cnt);
109 flow = &fq->flows[idx];
110
111 if (flow->tin && flow->tin != tin) {
112 flow = get_default_func(fq, tin, idx, skb);
113 tin->collisions++;
114 fq->collisions++;
115 }
116
117 if (!flow->tin)
118 tin->flows++;
119
120 return flow;
121}
122
Michal Kaziorb43e7192016-04-27 12:59:13 +0200123static void fq_recalc_backlog(struct fq *fq,
124 struct fq_tin *tin,
125 struct fq_flow *flow)
Michal Kazior557fc4a2016-04-22 14:20:13 +0200126{
Michal Kazior557fc4a2016-04-22 14:20:13 +0200127 struct fq_flow *i;
128
Michal Kazior557fc4a2016-04-22 14:20:13 +0200129 if (list_empty(&flow->backlogchain))
130 list_add_tail(&flow->backlogchain, &fq->backlogs);
131
132 i = flow;
133 list_for_each_entry_continue_reverse(i, &fq->backlogs,
134 backlogchain)
135 if (i->backlog > flow->backlog)
136 break;
137
138 list_move(&flow->backlogchain, &i->backlogchain);
Michal Kaziorb43e7192016-04-27 12:59:13 +0200139}
140
141static void fq_tin_enqueue(struct fq *fq,
142 struct fq_tin *tin,
143 struct sk_buff *skb,
144 fq_skb_free_t free_func,
145 fq_flow_get_default_t get_default_func)
146{
147 struct fq_flow *flow;
148
149 lockdep_assert_held(&fq->lock);
150
151 flow = fq_flow_classify(fq, tin, skb, get_default_func);
152
153 flow->tin = tin;
154 flow->backlog += skb->len;
155 tin->backlog_bytes += skb->len;
156 tin->backlog_packets++;
157 fq->backlog++;
158
159 fq_recalc_backlog(fq, tin, flow);
Michal Kazior557fc4a2016-04-22 14:20:13 +0200160
161 if (list_empty(&flow->flowchain)) {
162 flow->deficit = fq->quantum;
163 list_add_tail(&flow->flowchain,
164 &tin->new_flows);
165 }
166
167 __skb_queue_tail(&flow->queue, skb);
168
169 if (fq->backlog > fq->limit) {
170 flow = list_first_entry_or_null(&fq->backlogs,
171 struct fq_flow,
172 backlogchain);
173 if (!flow)
174 return;
175
176 skb = fq_flow_dequeue(fq, flow);
177 if (!skb)
178 return;
179
180 free_func(fq, flow->tin, flow, skb);
181
182 flow->tin->overlimit++;
183 fq->overlimit++;
184 }
185}
186
187static void fq_flow_reset(struct fq *fq,
188 struct fq_flow *flow,
189 fq_skb_free_t free_func)
190{
191 struct sk_buff *skb;
192
193 while ((skb = fq_flow_dequeue(fq, flow)))
194 free_func(fq, flow->tin, flow, skb);
195
196 if (!list_empty(&flow->flowchain))
197 list_del_init(&flow->flowchain);
198
199 if (!list_empty(&flow->backlogchain))
200 list_del_init(&flow->backlogchain);
201
202 flow->tin = NULL;
203
204 WARN_ON_ONCE(flow->backlog);
205}
206
207static void fq_tin_reset(struct fq *fq,
208 struct fq_tin *tin,
209 fq_skb_free_t free_func)
210{
211 struct list_head *head;
212 struct fq_flow *flow;
213
214 for (;;) {
215 head = &tin->new_flows;
216 if (list_empty(head)) {
217 head = &tin->old_flows;
218 if (list_empty(head))
219 break;
220 }
221
222 flow = list_first_entry(head, struct fq_flow, flowchain);
223 fq_flow_reset(fq, flow, free_func);
224 }
225
226 WARN_ON_ONCE(tin->backlog_bytes);
227 WARN_ON_ONCE(tin->backlog_packets);
228}
229
230static void fq_flow_init(struct fq_flow *flow)
231{
232 INIT_LIST_HEAD(&flow->flowchain);
233 INIT_LIST_HEAD(&flow->backlogchain);
234 __skb_queue_head_init(&flow->queue);
235}
236
237static void fq_tin_init(struct fq_tin *tin)
238{
239 INIT_LIST_HEAD(&tin->new_flows);
240 INIT_LIST_HEAD(&tin->old_flows);
241}
242
243static int fq_init(struct fq *fq, int flows_cnt)
244{
245 int i;
246
247 memset(fq, 0, sizeof(fq[0]));
248 INIT_LIST_HEAD(&fq->backlogs);
249 spin_lock_init(&fq->lock);
250 fq->flows_cnt = max_t(u32, flows_cnt, 1);
251 fq->perturbation = prandom_u32();
252 fq->quantum = 300;
253 fq->limit = 8192;
254
255 fq->flows = kcalloc(fq->flows_cnt, sizeof(fq->flows[0]), GFP_KERNEL);
256 if (!fq->flows)
257 return -ENOMEM;
258
259 for (i = 0; i < fq->flows_cnt; i++)
260 fq_flow_init(&fq->flows[i]);
261
262 return 0;
263}
264
265static void fq_reset(struct fq *fq,
266 fq_skb_free_t free_func)
267{
268 int i;
269
270 for (i = 0; i < fq->flows_cnt; i++)
271 fq_flow_reset(fq, &fq->flows[i], free_func);
272
273 kfree(fq->flows);
274 fq->flows = NULL;
275}
276
277#endif