16 __fq_adjust_removal(struct fq *fq, struct fq_flow *flow, unsigned int packets,  in __fq_adjust_removal()  argument
25 	fq->backlog -= packets;  in __fq_adjust_removal()
26 	fq->memory_usage -= truesize;  in __fq_adjust_removal()
36 	idx = flow - fq->flows;  in __fq_adjust_removal()
37 	__clear_bit(idx, fq->flows_bitmap);  in __fq_adjust_removal()
40 static void fq_adjust_removal(struct fq *fq,  in fq_adjust_removal()  argument
44 	__fq_adjust_removal(fq, flow, 1, skb->len, skb->truesize);  in fq_adjust_removal()
47 static struct sk_buff *fq_flow_dequeue(struct fq *fq,  in fq_flow_dequeue()  argument
52 	lockdep_assert_held(&fq->lock);  in fq_flow_dequeue()
58 	fq_adjust_removal(fq, flow, skb);  in fq_flow_dequeue()
63 static int fq_flow_drop(struct fq *fq, struct fq_flow *flow,  in fq_flow_drop()  argument
71 	lockdep_assert_held(&fq->lock);  in fq_flow_drop()
82 		free_func(fq, tin, flow, skb);  in fq_flow_drop()
85 	__fq_adjust_removal(fq, flow, packets, bytes, truesize);  in fq_flow_drop()
90 static struct sk_buff *fq_tin_dequeue(struct fq *fq,  in fq_tin_dequeue()  argument
98 	lockdep_assert_held(&fq->lock);  in fq_tin_dequeue()
111 		flow->deficit += fq->quantum;  in fq_tin_dequeue()
117 	skb = dequeue_func(fq, tin, flow);  in fq_tin_dequeue()
137 static u32 fq_flow_idx(struct fq *fq, struct sk_buff *skb)  in fq_flow_idx()  argument
141 	return reciprocal_scale(hash, fq->flows_cnt);  in fq_flow_idx()
144 static struct fq_flow *fq_flow_classify(struct fq *fq,  in fq_flow_classify()  argument
150 	lockdep_assert_held(&fq->lock);  in fq_flow_classify()
152 	flow = &fq->flows[idx];  in fq_flow_classify()
156 		fq->collisions++;  in fq_flow_classify()
165 static struct fq_flow *fq_find_fattest_flow(struct fq *fq)  in fq_find_fattest_flow()  argument
172 	for_each_set_bit(i, fq->flows_bitmap, fq->flows_cnt) {  in fq_find_fattest_flow()
173 		struct fq_flow *cur = &fq->flows[i];  in fq_find_fattest_flow()
184 	list_for_each_entry(tin, &fq->tin_backlog, tin_list) {  in fq_find_fattest_flow()
197 static void fq_tin_enqueue(struct fq *fq,  in fq_tin_enqueue()  argument
206 	lockdep_assert_held(&fq->lock);  in fq_tin_enqueue()
208 	flow = fq_flow_classify(fq, tin, idx, skb);  in fq_tin_enqueue()
212 			__set_bit(idx, fq->flows_bitmap);  in fq_tin_enqueue()
214 			list_add(&tin->tin_list, &fq->tin_backlog);  in fq_tin_enqueue()
223 		fq->memory_usage += skb->truesize;  in fq_tin_enqueue()
224 		fq->backlog++;  in fq_tin_enqueue()
229 		flow->deficit = fq->quantum;  in fq_tin_enqueue()
234 	oom = (fq->memory_usage > fq->memory_limit);  in fq_tin_enqueue()
235 	while (fq->backlog > fq->limit || oom) {  in fq_tin_enqueue()
236 		flow = fq_find_fattest_flow(fq);  in fq_tin_enqueue()
240 		if (!fq_flow_drop(fq, flow, free_func))  in fq_tin_enqueue()
244 		fq->overlimit++;  in fq_tin_enqueue()
246 			fq->overmemory++;  in fq_tin_enqueue()
247 			oom = (fq->memory_usage > fq->memory_limit);  in fq_tin_enqueue()
252 static void fq_flow_filter(struct fq *fq,  in fq_flow_filter()  argument
261 	lockdep_assert_held(&fq->lock);  in fq_flow_filter()
264 		if (!filter_func(fq, tin, flow, skb, filter_data))  in fq_flow_filter()
268 		fq_adjust_removal(fq, flow, skb);  in fq_flow_filter()
269 		free_func(fq, tin, flow, skb);  in fq_flow_filter()
273 static void fq_tin_filter(struct fq *fq,  in fq_tin_filter()  argument
281 	lockdep_assert_held(&fq->lock);  in fq_tin_filter()
284 		fq_flow_filter(fq, flow, filter_func, filter_data, free_func);  in fq_tin_filter()
286 		fq_flow_filter(fq, flow, filter_func, filter_data, free_func);  in fq_tin_filter()
289 static void fq_flow_reset(struct fq *fq,  in fq_flow_reset()  argument
296 	while ((skb = fq_flow_dequeue(fq, flow)))  in fq_flow_reset()
297 		free_func(fq, tin, flow, skb);  in fq_flow_reset()
311 static void fq_tin_reset(struct fq *fq,  in fq_tin_reset()  argument
327 		fq_flow_reset(fq, flow, free_func);  in fq_tin_reset()
349 static int fq_init(struct fq *fq, int flows_cnt)  in fq_init()  argument
353 	memset(fq, 0, sizeof(fq[0]));  in fq_init()
354 	spin_lock_init(&fq->lock);  in fq_init()
355 	INIT_LIST_HEAD(&fq->tin_backlog);  in fq_init()
356 	fq->flows_cnt = max_t(u32, flows_cnt, 1);  in fq_init()
357 	fq->quantum = 300;  in fq_init()
358 	fq->limit = 8192;  in fq_init()
359 	fq->memory_limit = 16 << 20; /* 16 MBytes */  in fq_init()
361 	fq->flows = kvcalloc(fq->flows_cnt, sizeof(fq->flows[0]), GFP_KERNEL);  in fq_init()
362 	if (!fq->flows)  in fq_init()
365 	fq->flows_bitmap = bitmap_zalloc(fq->flows_cnt, GFP_KERNEL);  in fq_init()
366 	if (!fq->flows_bitmap) {  in fq_init()
367 		kvfree(fq->flows);  in fq_init()
368 		fq->flows = NULL;  in fq_init()
372 	for (i = 0; i < fq->flows_cnt; i++)  in fq_init()
373 		fq_flow_init(&fq->flows[i]);  in fq_init()
378 static void fq_reset(struct fq *fq,  in fq_reset()  argument
383 	for (i = 0; i < fq->flows_cnt; i++)  in fq_reset()
384 		fq_flow_reset(fq, &fq->flows[i], free_func);  in fq_reset()
386 	kvfree(fq->flows);  in fq_reset()
387 	fq->flows = NULL;  in fq_reset()
389 	bitmap_free(fq->flows_bitmap);  in fq_reset()
390 	fq->flows_bitmap = NULL;  in fq_reset()