2 * Copyright (c) 2016 Qualcomm Atheros, Inc
6 * Based on net/sched/sch_fq_codel.c
8 #ifndef __NET_SCHED_FQ_IMPL_H
9 #define __NET_SCHED_FQ_IMPL_H
13 /* functions that are embedded into includer */
15 static struct sk_buff *fq_flow_dequeue(struct fq *fq,
18 struct fq_tin *tin = flow->tin;
22 lockdep_assert_held(&fq->lock);
24 skb = __skb_dequeue(&flow->queue);
28 tin->backlog_bytes -= skb->len;
29 tin->backlog_packets--;
30 flow->backlog -= skb->len;
33 if (flow->backlog == 0) {
34 list_del_init(&flow->backlogchain);
38 list_for_each_entry_continue(i, &fq->backlogs, backlogchain)
39 if (i->backlog < flow->backlog)
42 list_move_tail(&flow->backlogchain,
49 static struct sk_buff *fq_tin_dequeue(struct fq *fq,
51 fq_tin_dequeue_t dequeue_func)
54 struct list_head *head;
57 lockdep_assert_held(&fq->lock);
60 head = &tin->new_flows;
61 if (list_empty(head)) {
62 head = &tin->old_flows;
67 flow = list_first_entry(head, struct fq_flow, flowchain);
69 if (flow->deficit <= 0) {
70 flow->deficit += fq->quantum;
71 list_move_tail(&flow->flowchain,
76 skb = dequeue_func(fq, tin, flow);
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);
83 list_del_init(&flow->flowchain);
89 flow->deficit -= skb->len;
90 tin->tx_bytes += skb->len;
96 static struct fq_flow *fq_flow_classify(struct fq *fq,
99 fq_flow_get_default_t get_default_func)
101 struct fq_flow *flow;
105 lockdep_assert_held(&fq->lock);
107 hash = skb_get_hash_perturb(skb, fq->perturbation);
108 idx = reciprocal_scale(hash, fq->flows_cnt);
109 flow = &fq->flows[idx];
111 if (flow->tin && flow->tin != tin) {
112 flow = get_default_func(fq, tin, idx, skb);
123 static void fq_recalc_backlog(struct fq *fq,
125 struct fq_flow *flow)
129 if (list_empty(&flow->backlogchain))
130 list_add_tail(&flow->backlogchain, &fq->backlogs);
133 list_for_each_entry_continue_reverse(i, &fq->backlogs,
135 if (i->backlog > flow->backlog)
138 list_move(&flow->backlogchain, &i->backlogchain);
141 static void fq_tin_enqueue(struct fq *fq,
144 fq_skb_free_t free_func,
145 fq_flow_get_default_t get_default_func)
147 struct fq_flow *flow;
149 lockdep_assert_held(&fq->lock);
151 flow = fq_flow_classify(fq, tin, skb, get_default_func);
154 flow->backlog += skb->len;
155 tin->backlog_bytes += skb->len;
156 tin->backlog_packets++;
159 fq_recalc_backlog(fq, tin, flow);
161 if (list_empty(&flow->flowchain)) {
162 flow->deficit = fq->quantum;
163 list_add_tail(&flow->flowchain,
167 __skb_queue_tail(&flow->queue, skb);
169 if (fq->backlog > fq->limit) {
170 flow = list_first_entry_or_null(&fq->backlogs,
176 skb = fq_flow_dequeue(fq, flow);
180 free_func(fq, flow->tin, flow, skb);
182 flow->tin->overlimit++;
187 static void fq_flow_reset(struct fq *fq,
188 struct fq_flow *flow,
189 fq_skb_free_t free_func)
193 while ((skb = fq_flow_dequeue(fq, flow)))
194 free_func(fq, flow->tin, flow, skb);
196 if (!list_empty(&flow->flowchain))
197 list_del_init(&flow->flowchain);
199 if (!list_empty(&flow->backlogchain))
200 list_del_init(&flow->backlogchain);
204 WARN_ON_ONCE(flow->backlog);
207 static void fq_tin_reset(struct fq *fq,
209 fq_skb_free_t free_func)
211 struct list_head *head;
212 struct fq_flow *flow;
215 head = &tin->new_flows;
216 if (list_empty(head)) {
217 head = &tin->old_flows;
218 if (list_empty(head))
222 flow = list_first_entry(head, struct fq_flow, flowchain);
223 fq_flow_reset(fq, flow, free_func);
226 WARN_ON_ONCE(tin->backlog_bytes);
227 WARN_ON_ONCE(tin->backlog_packets);
230 static void fq_flow_init(struct fq_flow *flow)
232 INIT_LIST_HEAD(&flow->flowchain);
233 INIT_LIST_HEAD(&flow->backlogchain);
234 __skb_queue_head_init(&flow->queue);
237 static void fq_tin_init(struct fq_tin *tin)
239 INIT_LIST_HEAD(&tin->new_flows);
240 INIT_LIST_HEAD(&tin->old_flows);
243 static int fq_init(struct fq *fq, int flows_cnt)
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();
255 fq->flows = kcalloc(fq->flows_cnt, sizeof(fq->flows[0]), GFP_KERNEL);
259 for (i = 0; i < fq->flows_cnt; i++)
260 fq_flow_init(&fq->flows[i]);
265 static void fq_reset(struct fq *fq,
266 fq_skb_free_t free_func)
270 for (i = 0; i < fq->flows_cnt; i++)
271 fq_flow_reset(fq, &fq->flows[i], free_func);