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()
92 	if (unlikely(qdisc_qlen(sch) >= sch->limit)) {  in pie_qdisc_enqueue()
93 		q->stats.overlimit++;  in pie_qdisc_enqueue()
99 	if (!pie_drop_early(sch, &q->params, &q->vars, sch->qstats.backlog,  in pie_qdisc_enqueue()
100 			    skb->len)) {  in pie_qdisc_enqueue()
102 	} else if (q->params.ecn && (q->vars.prob <= MAX_PROB / 10) &&  in pie_qdisc_enqueue()
107 		q->stats.ecn_mark++;  in pie_qdisc_enqueue()
114 		if (!q->params.dq_rate_estimator)  in pie_qdisc_enqueue()
117 		q->stats.packets_in++;  in pie_qdisc_enqueue()
118 		if (qdisc_qlen(sch) > q->stats.maxq)  in pie_qdisc_enqueue()
119 			q->stats.maxq = qdisc_qlen(sch);  in pie_qdisc_enqueue()
125 	q->stats.dropped++;  in pie_qdisc_enqueue()
126 	q->vars.accu_prob = 0;  in pie_qdisc_enqueue()
156 	/* convert from microseconds to pschedtime */  in pie_change()
161 		/* convert to pschedtime */  in pie_change()
162 		WRITE_ONCE(q->params.target,  in pie_change()
168 		WRITE_ONCE(q->params.tupdate,  in pie_change()
174 		WRITE_ONCE(q->params.limit, limit);  in pie_change()
175 		WRITE_ONCE(sch->limit, limit);  in pie_change()
179 		WRITE_ONCE(q->params.alpha, nla_get_u32(tb[TCA_PIE_ALPHA]));  in pie_change()
182 		WRITE_ONCE(q->params.beta, nla_get_u32(tb[TCA_PIE_BETA]));  in pie_change()
185 		WRITE_ONCE(q->params.ecn, nla_get_u32(tb[TCA_PIE_ECN]));  in pie_change()
188 		WRITE_ONCE(q->params.bytemode,  in pie_change()
192 		WRITE_ONCE(q->params.dq_rate_estimator,  in pie_change()
196 	qlen = sch->q.qlen;  in pie_change()
197 	while (sch->q.qlen > sch->limit) {  in pie_change()
198 		struct sk_buff *skb = __qdisc_dequeue_head(&sch->q);  in pie_change()
204 	qdisc_tree_reduce_backlog(sch, qlen - sch->q.qlen, dropped);  in pie_change()
219 	if (!params->dq_rate_estimator) {  in pie_process_dequeue()
220 		vars->qdelay = now - pie_get_enqueue_time(skb);  in pie_process_dequeue()
222 		if (vars->dq_tstamp != DTIME_INVALID)  in pie_process_dequeue()
223 			dtime = now - vars->dq_tstamp;  in pie_process_dequeue()
225 		vars->dq_tstamp = now;  in pie_process_dequeue()
228 			vars->qdelay = 0;  in pie_process_dequeue()
237 	 * we have enough packets to calculate the drain rate. Save  in pie_process_dequeue()
240 	if (backlog >= QUEUE_THRESHOLD && vars->dq_count == DQCOUNT_INVALID) {  in pie_process_dequeue()
241 		vars->dq_tstamp = psched_get_time();  in pie_process_dequeue()
242 		vars->dq_count = 0;  in pie_process_dequeue()
245 	/* Calculate the average drain rate from this value. If queue length  in pie_process_dequeue()
247 	 * the dq_count to -1 as we don't have enough packets to calculate the  in pie_process_dequeue()
248 	 * drain rate anymore. The following if block is entered only when we  in pie_process_dequeue()
250 	 * and we calculate the drain rate for the threshold here.  dq_count is  in pie_process_dequeue()
251 	 * in bytes, time difference in psched_time, hence rate is in  in pie_process_dequeue()
254 	if (vars->dq_count != DQCOUNT_INVALID) {  in pie_process_dequeue()
255 		vars->dq_count += skb->len;  in pie_process_dequeue()
257 		if (vars->dq_count >= QUEUE_THRESHOLD) {  in pie_process_dequeue()
258 			u32 count = vars->dq_count << PIE_SCALE;  in pie_process_dequeue()
260 			dtime = now - vars->dq_tstamp;  in pie_process_dequeue()
267 			if (vars->avg_dq_rate == 0)  in pie_process_dequeue()
268 				vars->avg_dq_rate = count;  in pie_process_dequeue()
270 				vars->avg_dq_rate =  in pie_process_dequeue()
271 				    (vars->avg_dq_rate -  in pie_process_dequeue()
272 				     (vars->avg_dq_rate >> 3)) + (count >> 3);  in pie_process_dequeue()
275 			 * on to the last drain rate calculated, else we reset  in pie_process_dequeue()
276 			 * dq_count to 0 to re-enter the if block when the next  in pie_process_dequeue()
280 				vars->dq_count = DQCOUNT_INVALID;  in pie_process_dequeue()
282 				vars->dq_count = 0;  in pie_process_dequeue()
283 				vars->dq_tstamp = psched_get_time();  in pie_process_dequeue()
293 	if (vars->burst_time > 0) {  in pie_process_dequeue()
294 		if (vars->burst_time > dtime)  in pie_process_dequeue()
295 			vars->burst_time -= dtime;  in pie_process_dequeue()
297 			vars->burst_time = 0;  in pie_process_dequeue()
313 	if (params->dq_rate_estimator) {  in pie_calculate_probability()
314 		qdelay_old = vars->qdelay;  in pie_calculate_probability()
315 		vars->qdelay_old = vars->qdelay;  in pie_calculate_probability()
317 		if (vars->avg_dq_rate > 0)  in pie_calculate_probability()
318 			qdelay = (backlog << PIE_SCALE) / vars->avg_dq_rate;  in pie_calculate_probability()
322 		qdelay = vars->qdelay;  in pie_calculate_probability()
323 		qdelay_old = vars->qdelay_old;  in pie_calculate_probability()
333 	 * value for alpha as 0.125. In this implementation, we use values 0-32  in pie_calculate_probability()
337 	 * by 16 to come to 0-2 range.  in pie_calculate_probability()
339 	alpha = ((u64)params->alpha * (MAX_PROB / PSCHED_TICKS_PER_SEC)) >> 4;  in pie_calculate_probability()
340 	beta = ((u64)params->beta * (MAX_PROB / PSCHED_TICKS_PER_SEC)) >> 4;  in pie_calculate_probability()
345 	if (vars->prob < MAX_PROB / 10) {  in pie_calculate_probability()
350 		while (vars->prob < div_u64(MAX_PROB, power) &&  in pie_calculate_probability()
359 	delta += alpha * (qdelay - params->target);  in pie_calculate_probability()
360 	delta += beta * (qdelay - qdelay_old);  in pie_calculate_probability()
362 	oldprob = vars->prob;  in pie_calculate_probability()
366 	    vars->prob >= MAX_PROB / 10)  in pie_calculate_probability()
369 	/* Non-linear drop:  in pie_calculate_probability()
377 	vars->prob += delta;  in pie_calculate_probability()
381 		if (vars->prob < oldprob) {  in pie_calculate_probability()
382 			vars->prob = MAX_PROB;  in pie_calculate_probability()
385 			 * skip the check to do a non-linear drop in the next  in pie_calculate_probability()
392 		if (vars->prob > oldprob)  in pie_calculate_probability()
393 			vars->prob = 0;  in pie_calculate_probability()
396 	/* Non-linear drop in probability: Reduce drop probability quickly if  in pie_calculate_probability()
402 		vars->prob -= vars->prob / 64;  in pie_calculate_probability()
404 	vars->qdelay = qdelay;  in pie_calculate_probability()
405 	vars->backlog_old = backlog;  in pie_calculate_probability()
411 	 *    estimate for the avg_dq_rate ie., is a non-zero value  in pie_calculate_probability()
413 	if ((vars->qdelay < params->target / 2) &&  in pie_calculate_probability()
414 	    (vars->qdelay_old < params->target / 2) &&  in pie_calculate_probability()
415 	    vars->prob == 0 &&  in pie_calculate_probability()
416 	    (!params->dq_rate_estimator || vars->avg_dq_rate > 0)) {  in pie_calculate_probability()
420 	if (!params->dq_rate_estimator)  in pie_calculate_probability()
421 		vars->qdelay_old = qdelay;  in pie_calculate_probability()
428 	struct Qdisc *sch = q->sch;  in pie_timer()
434 	pie_calculate_probability(&q->params, &q->vars, sch->qstats.backlog);  in pie_timer()
437 	if (q->params.tupdate)  in pie_timer()
438 		mod_timer(&q->adapt_timer, jiffies + q->params.tupdate);  in pie_timer()
448 	pie_params_init(&q->params);  in pie_init()
449 	pie_vars_init(&q->vars);  in pie_init()
450 	sch->limit = q->params.limit;  in pie_init()
452 	q->sch = sch;  in pie_init()
453 	timer_setup(&q->adapt_timer, pie_timer, 0);  in pie_init()
462 	mod_timer(&q->adapt_timer, jiffies + HZ / 2);  in pie_init()
475 	/* convert target from pschedtime to us */  in pie_dump()
477 			((u32)PSCHED_TICKS2NS(READ_ONCE(q->params.target))) /  in pie_dump()
479 	    nla_put_u32(skb, TCA_PIE_LIMIT, READ_ONCE(sch->limit)) ||  in pie_dump()
481 			jiffies_to_usecs(READ_ONCE(q->params.tupdate))) ||  in pie_dump()
482 	    nla_put_u32(skb, TCA_PIE_ALPHA, READ_ONCE(q->params.alpha)) ||  in pie_dump()
483 	    nla_put_u32(skb, TCA_PIE_BETA, READ_ONCE(q->params.beta)) ||  in pie_dump()
484 	    nla_put_u32(skb, TCA_PIE_ECN, q->params.ecn) ||  in pie_dump()
486 			READ_ONCE(q->params.bytemode)) ||  in pie_dump()
488 			READ_ONCE(q->params.dq_rate_estimator)))  in pie_dump()
495 	return -1;  in pie_dump()
502 		.prob		= q->vars.prob << BITS_PER_BYTE,  in pie_dump_stats()
503 		.delay		= ((u32)PSCHED_TICKS2NS(q->vars.qdelay)) /  in pie_dump_stats()
505 		.packets_in	= q->stats.packets_in,  in pie_dump_stats()
506 		.overlimit	= q->stats.overlimit,  in pie_dump_stats()
507 		.maxq		= q->stats.maxq,  in pie_dump_stats()
508 		.dropped	= q->stats.dropped,  in pie_dump_stats()
509 		.ecn_mark	= q->stats.ecn_mark,  in pie_dump_stats()
513 	st.dq_rate_estimating = q->params.dq_rate_estimator;  in pie_dump_stats()
516 	if (q->params.dq_rate_estimator)  in pie_dump_stats()
517 		st.avg_dq_rate = q->vars.avg_dq_rate *  in pie_dump_stats()
531 	pie_process_dequeue(skb, &q->params, &q->vars, sch->qstats.backlog);  in pie_qdisc_dequeue()
540 	pie_vars_init(&q->vars);  in pie_reset()
547 	q->params.tupdate = 0;  in pie_destroy()
548 	del_timer_sync(&q->adapt_timer);  in pie_destroy()