1 // SPDX-License-Identifier: GPL-2.0-only
37 	u64 local_prob = vars->prob;  in pie_drop_early()
41 	if (vars->burst_time > 0)  in pie_drop_early()
47 	if ((vars->qdelay < params->target / 2) &&  in pie_drop_early()
48 	    (vars->prob < MAX_PROB / 5))  in pie_drop_early()
51 	/* If we have fewer than 2 mtu-sized packets, disable pie_drop_early,  in pie_drop_early()
60 	if (params->bytemode && packet_size <= mtu)  in pie_drop_early()
63 		local_prob = vars->prob;  in pie_drop_early()
66 		vars->accu_prob = 0;  in pie_drop_early()
68 		vars->accu_prob += local_prob;  in pie_drop_early()
70 	if (vars->accu_prob < (MAX_PROB / 100) * 85)  in pie_drop_early()
72 	if (vars->accu_prob >= (MAX_PROB / 2) * 17)  in pie_drop_early()
77 		vars->accu_prob = 0;  in pie_drop_early()
85 static int pie_qdisc_enqueue(struct sk_buff *skb, struct Qdisc *sch,  in pie_qdisc_enqueue()
91 	if (unlikely(qdisc_qlen(sch) >= sch->limit)) {  in pie_qdisc_enqueue()
92 		q->stats.overlimit++;  in pie_qdisc_enqueue()
96 	if (!pie_drop_early(sch, &q->params, &q->vars, sch->qstats.backlog,  in pie_qdisc_enqueue()
97 			    skb->len)) {  in pie_qdisc_enqueue()
99 	} else if (q->params.ecn && (q->vars.prob <= MAX_PROB / 10) &&  in pie_qdisc_enqueue()
104 		q->stats.ecn_mark++;  in pie_qdisc_enqueue()
111 		if (!q->params.dq_rate_estimator)  in pie_qdisc_enqueue()
114 		q->stats.packets_in++;  in pie_qdisc_enqueue()
115 		if (qdisc_qlen(sch) > q->stats.maxq)  in pie_qdisc_enqueue()
116 			q->stats.maxq = qdisc_qlen(sch);  in pie_qdisc_enqueue()
122 	q->stats.dropped++;  in pie_qdisc_enqueue()
123 	q->vars.accu_prob = 0;  in pie_qdisc_enqueue()
127 static const struct nla_policy pie_policy[TCA_PIE_MAX + 1] = {
138 static int pie_change(struct Qdisc *sch, struct nlattr *opt,  in pie_change()
159 		q->params.target = PSCHED_NS2TICKS((u64)target * NSEC_PER_USEC);  in pie_change()
164 		q->params.tupdate =  in pie_change()
170 		q->params.limit = limit;  in pie_change()
171 		sch->limit = limit;  in pie_change()
175 		q->params.alpha = nla_get_u32(tb[TCA_PIE_ALPHA]);  in pie_change()
178 		q->params.beta = nla_get_u32(tb[TCA_PIE_BETA]);  in pie_change()
181 		q->params.ecn = nla_get_u32(tb[TCA_PIE_ECN]);  in pie_change()
184 		q->params.bytemode = nla_get_u32(tb[TCA_PIE_BYTEMODE]);  in pie_change()
187 		q->params.dq_rate_estimator =  in pie_change()
191 	qlen = sch->q.qlen;  in pie_change()
192 	while (sch->q.qlen > sch->limit) {  in pie_change()
193 		struct sk_buff *skb = __qdisc_dequeue_head(&sch->q);  in pie_change()
199 	qdisc_tree_reduce_backlog(sch, qlen - sch->q.qlen, dropped);  in pie_change()
214 	if (!params->dq_rate_estimator) {  in pie_process_dequeue()
215 		vars->qdelay = now - pie_get_enqueue_time(skb);  in pie_process_dequeue()
217 		if (vars->dq_tstamp != DTIME_INVALID)  in pie_process_dequeue()
218 			dtime = now - vars->dq_tstamp;  in pie_process_dequeue()
220 		vars->dq_tstamp = now;  in pie_process_dequeue()
223 			vars->qdelay = 0;  in pie_process_dequeue()
235 	if (backlog >= QUEUE_THRESHOLD && vars->dq_count == DQCOUNT_INVALID) {  in pie_process_dequeue()
236 		vars->dq_tstamp = psched_get_time();  in pie_process_dequeue()
237 		vars->dq_count = 0;  in pie_process_dequeue()
242 	 * the dq_count to -1 as we don't have enough packets to calculate the  in pie_process_dequeue()
249 	if (vars->dq_count != DQCOUNT_INVALID) {  in pie_process_dequeue()
250 		vars->dq_count += skb->len;  in pie_process_dequeue()
252 		if (vars->dq_count >= QUEUE_THRESHOLD) {  in pie_process_dequeue()
253 			u32 count = vars->dq_count << PIE_SCALE;  in pie_process_dequeue()
255 			dtime = now - vars->dq_tstamp;  in pie_process_dequeue()
262 			if (vars->avg_dq_rate == 0)  in pie_process_dequeue()
263 				vars->avg_dq_rate = count;  in pie_process_dequeue()
265 				vars->avg_dq_rate =  in pie_process_dequeue()
266 				    (vars->avg_dq_rate -  in pie_process_dequeue()
267 				     (vars->avg_dq_rate >> 3)) + (count >> 3);  in pie_process_dequeue()
271 			 * dq_count to 0 to re-enter the if block when the next  in pie_process_dequeue()
275 				vars->dq_count = DQCOUNT_INVALID;  in pie_process_dequeue()
277 				vars->dq_count = 0;  in pie_process_dequeue()
278 				vars->dq_tstamp = psched_get_time();  in pie_process_dequeue()
288 	if (vars->burst_time > 0) {  in pie_process_dequeue()
289 		if (vars->burst_time > dtime)  in pie_process_dequeue()
290 			vars->burst_time -= dtime;  in pie_process_dequeue()
292 			vars->burst_time = 0;  in pie_process_dequeue()
304 	u64 alpha, beta;  in pie_calculate_probability()  local
308 	if (params->dq_rate_estimator) {  in pie_calculate_probability()
309 		qdelay_old = vars->qdelay;  in pie_calculate_probability()
310 		vars->qdelay_old = vars->qdelay;  in pie_calculate_probability()
312 		if (vars->avg_dq_rate > 0)  in pie_calculate_probability()
313 			qdelay = (backlog << PIE_SCALE) / vars->avg_dq_rate;  in pie_calculate_probability()
317 		qdelay = vars->qdelay;  in pie_calculate_probability()
318 		qdelay_old = vars->qdelay_old;  in pie_calculate_probability()
327 	/* In the algorithm, alpha and beta are between 0 and 2 with typical  in pie_calculate_probability()
328 	 * value for alpha as 0.125. In this implementation, we use values 0-32  in pie_calculate_probability()
329 	 * passed from user space to represent this. Also, alpha and beta have  in pie_calculate_probability()
331 	 * probability. alpha/beta are updated locally below by scaling down  in pie_calculate_probability()
332 	 * by 16 to come to 0-2 range.  in pie_calculate_probability()
334 	alpha = ((u64)params->alpha * (MAX_PROB / PSCHED_TICKS_PER_SEC)) >> 4;  in pie_calculate_probability()
335 	beta = ((u64)params->beta * (MAX_PROB / PSCHED_TICKS_PER_SEC)) >> 4;  in pie_calculate_probability()
337 	/* We scale alpha and beta differently depending on how heavy the  in pie_calculate_probability()
340 	if (vars->prob < MAX_PROB / 10) {  in pie_calculate_probability()
342 		beta >>= 1;  in pie_calculate_probability()
345 		while (vars->prob < div_u64(MAX_PROB, power) &&  in pie_calculate_probability()
348 			beta >>= 2;  in pie_calculate_probability()
353 	/* alpha and beta should be between 0 and 32, in multiples of 1/16 */  in pie_calculate_probability()
354 	delta += alpha * (qdelay - params->target);  in pie_calculate_probability()
355 	delta += beta * (qdelay - qdelay_old);  in pie_calculate_probability()
357 	oldprob = vars->prob;  in pie_calculate_probability()
361 	    vars->prob >= MAX_PROB / 10)  in pie_calculate_probability()
364 	/* Non-linear drop:  in pie_calculate_probability()
372 	vars->prob += delta;  in pie_calculate_probability()
376 		if (vars->prob < oldprob) {  in pie_calculate_probability()
377 			vars->prob = MAX_PROB;  in pie_calculate_probability()
380 			 * skip the check to do a non-linear drop in the next  in pie_calculate_probability()
387 		if (vars->prob > oldprob)  in pie_calculate_probability()
388 			vars->prob = 0;  in pie_calculate_probability()
391 	/* Non-linear drop in probability: Reduce drop probability quickly if  in pie_calculate_probability()
397 		vars->prob -= vars->prob / 64;  in pie_calculate_probability()
399 	vars->qdelay = qdelay;  in pie_calculate_probability()
400 	vars->backlog_old = backlog;  in pie_calculate_probability()
406 	 *    estimate for the avg_dq_rate ie., is a non-zero value  in pie_calculate_probability()
408 	if ((vars->qdelay < params->target / 2) &&  in pie_calculate_probability()
409 	    (vars->qdelay_old < params->target / 2) &&  in pie_calculate_probability()
410 	    vars->prob == 0 &&  in pie_calculate_probability()
411 	    (!params->dq_rate_estimator || vars->avg_dq_rate > 0)) {  in pie_calculate_probability()
415 	if (!params->dq_rate_estimator)  in pie_calculate_probability()
416 		vars->qdelay_old = qdelay;  in pie_calculate_probability()
420 static void pie_timer(struct timer_list *t)  in pie_timer()
423 	struct Qdisc *sch = q->sch;  in pie_timer()
429 	pie_calculate_probability(&q->params, &q->vars, sch->qstats.backlog);  in pie_timer()
432 	if (q->params.tupdate)  in pie_timer()
433 		mod_timer(&q->adapt_timer, jiffies + q->params.tupdate);  in pie_timer()
438 static int pie_init(struct Qdisc *sch, struct nlattr *opt,  in pie_init()
443 	pie_params_init(&q->params);  in pie_init()
444 	pie_vars_init(&q->vars);  in pie_init()
445 	sch->limit = q->params.limit;  in pie_init()
447 	q->sch = sch;  in pie_init()
448 	timer_setup(&q->adapt_timer, pie_timer, 0);  in pie_init()
457 	mod_timer(&q->adapt_timer, jiffies + HZ / 2);  in pie_init()
461 static int pie_dump(struct Qdisc *sch, struct sk_buff *skb)  in pie_dump()
472 			((u32)PSCHED_TICKS2NS(q->params.target)) /  in pie_dump()
474 	    nla_put_u32(skb, TCA_PIE_LIMIT, sch->limit) ||  in pie_dump()
476 			jiffies_to_usecs(q->params.tupdate)) ||  in pie_dump()
477 	    nla_put_u32(skb, TCA_PIE_ALPHA, q->params.alpha) ||  in pie_dump()
478 	    nla_put_u32(skb, TCA_PIE_BETA, q->params.beta) ||  in pie_dump()
479 	    nla_put_u32(skb, TCA_PIE_ECN, q->params.ecn) ||  in pie_dump()
480 	    nla_put_u32(skb, TCA_PIE_BYTEMODE, q->params.bytemode) ||  in pie_dump()
482 			q->params.dq_rate_estimator))  in pie_dump()
489 	return -1;  in pie_dump()
492 static int pie_dump_stats(struct Qdisc *sch, struct gnet_dump *d)  in pie_dump_stats()
496 		.prob		= q->vars.prob << BITS_PER_BYTE,  in pie_dump_stats()
497 		.delay		= ((u32)PSCHED_TICKS2NS(q->vars.qdelay)) /  in pie_dump_stats()
499 		.packets_in	= q->stats.packets_in,  in pie_dump_stats()
500 		.overlimit	= q->stats.overlimit,  in pie_dump_stats()
501 		.maxq		= q->stats.maxq,  in pie_dump_stats()
502 		.dropped	= q->stats.dropped,  in pie_dump_stats()
503 		.ecn_mark	= q->stats.ecn_mark,  in pie_dump_stats()
507 	st.dq_rate_estimating = q->params.dq_rate_estimator;  in pie_dump_stats()
510 	if (q->params.dq_rate_estimator)  in pie_dump_stats()
511 		st.avg_dq_rate = q->vars.avg_dq_rate *  in pie_dump_stats()
517 static struct sk_buff *pie_qdisc_dequeue(struct Qdisc *sch)  in pie_qdisc_dequeue()
525 	pie_process_dequeue(skb, &q->params, &q->vars, sch->qstats.backlog);  in pie_qdisc_dequeue()
529 static void pie_reset(struct Qdisc *sch)  in pie_reset()
534 	pie_vars_init(&q->vars);  in pie_reset()
537 static void pie_destroy(struct Qdisc *sch)  in pie_destroy()
541 	q->params.tupdate = 0;  in pie_destroy()
542 	del_timer_sync(&q->adapt_timer);  in pie_destroy()
545 static struct Qdisc_ops pie_qdisc_ops __read_mostly = {
560 static int __init pie_module_init(void)  in pie_module_init()
565 static void __exit pie_module_exit(void)  in pie_module_exit()