14  * - Supports ECN L4S-identifier (IP.ECN==0b*1)
41 /* 32b enable to support flows with windows up to ~8.6 * 1e9 packets
52  * netlink-provided values can use at most 31b, i.e. be at most (2^23)-1
53  * (~4MHz) as those are given in 1/256th. This enable to tune alpha/beta to
56 #define ALPHA_BETA_MAX ((1U << 31) - 1)
61  * scale_alpha_beta(1) will not round down to 0.
88 	bool	step_in_packets; /* Step thresh in packets (1) or time (0) */
101 	bool	drop_early;	/* Drop at enqueue (1) instead of dequeue  (0) */
102 	bool	drop_overload;	/* Drop (1) on overload, or overflow (0) */
103 	bool	split_gso;	/* Split aggregated skb (1) or leave as is (0) */
108 	u64	last_qdelay;	/* Q delay val at the last probability update */
124 	u8 apply_step:1,	/* Can we apply the step threshold */
131 	DUALPI2_C_L4S		= 1,	/* L-queue (scale mark/classic drop) */
147 static u64 head_enqueue_time(struct Qdisc *q)  in head_enqueue_time()  argument
149 	struct sk_buff *skb = qdisc_peek_head(q);  in head_enqueue_time()
170 static ktime_t next_pi2_timeout(struct dualpi2_sched_data *q)  in next_pi2_timeout()  argument
172 	return ktime_add_ns(ktime_get_ns(), q->pi2_tupdate);  in next_pi2_timeout()
185 static bool skb_apply_step(struct sk_buff *skb, struct dualpi2_sched_data *q)  in skb_apply_step()  argument
187 	return skb_is_l4s(skb) && qdisc_qlen(q->l_queue) >= q->min_qlen_step;  in skb_apply_step()
190 static bool dualpi2_mark(struct dualpi2_sched_data *q, struct sk_buff *skb)  in dualpi2_mark()  argument
193 		q->ecn_mark++;  in dualpi2_mark()
199 static void dualpi2_reset_c_protection(struct dualpi2_sched_data *q)  in dualpi2_reset_c_protection()  argument
201 	q->c_protection_credit = q->c_protection_init;  in dualpi2_reset_c_protection()
209 					   struct dualpi2_sched_data *q, u32 wc)  in dualpi2_calculate_c_protection()  argument
211 	q->c_protection_wc = wc;  in dualpi2_calculate_c_protection()
212 	q->c_protection_wl = MAX_WC - wc;  in dualpi2_calculate_c_protection()
213 	q->c_protection_init = (s32)psched_mtu(qdisc_dev(sch)) *  in dualpi2_calculate_c_protection()
214 		((int)q->c_protection_wc - (int)q->c_protection_wl);  in dualpi2_calculate_c_protection()
215 	dualpi2_reset_c_protection(q);  in dualpi2_calculate_c_protection()
230 static bool dualpi2_classic_marking(struct dualpi2_sched_data *q,  in dualpi2_classic_marking()  argument
237 		dualpi2_mark(q, skb);  in dualpi2_classic_marking()
247  *   @q->drop_overload), apply classic drops first before marking.
253 static bool dualpi2_scalable_marking(struct dualpi2_sched_data *q,  in dualpi2_scalable_marking()  argument
260 		if (!q->drop_overload ||  in dualpi2_scalable_marking()
272 		dualpi2_mark(q, skb);  in dualpi2_scalable_marking()
282 static bool must_drop(struct Qdisc *sch, struct dualpi2_sched_data *q,  in must_drop()  argument
292 	prob = READ_ONCE(q->pi2_prob);  in must_drop()
293 	local_l_prob = (u64)prob * q->coupling_factor;  in must_drop()
298 		return dualpi2_classic_marking(q, skb, prob, overload);  in must_drop()
300 		return dualpi2_scalable_marking(q, skb, local_l_prob, prob,  in must_drop()
341 static int dualpi2_skb_classify(struct dualpi2_sched_data *q,  in dualpi2_skb_classify()  argument
350 	if (cb->ect & q->ecn_mask) {  in dualpi2_skb_classify()
355 	if (TC_H_MAJ(skb->priority) == q->sch->handle &&  in dualpi2_skb_classify()
361 	fl = rcu_dereference_bh(q->tcf_filters);  in dualpi2_skb_classify()
388 	struct dualpi2_sched_data *q = qdisc_priv(sch);  in dualpi2_enqueue_skb()  local
392 	    unlikely((u64)q->memory_used + skb->truesize > q->memory_limit)) {  in dualpi2_enqueue_skb()
395 			qdisc_qstats_overlimit(q->l_queue);  in dualpi2_enqueue_skb()
400 	if (q->drop_early && must_drop(sch, q, skb)) {  in dualpi2_enqueue_skb()
408 	q->memory_used += skb->truesize;  in dualpi2_enqueue_skb()
409 	if (q->memory_used > q->max_memory_used)  in dualpi2_enqueue_skb()
410 		q->max_memory_used = q->memory_used;  in dualpi2_enqueue_skb()
412 	if (qdisc_qlen(sch) > q->maxq)  in dualpi2_enqueue_skb()
413 		q->maxq = qdisc_qlen(sch);  in dualpi2_enqueue_skb()
417 		dualpi2_skb_cb(skb)->apply_step = skb_apply_step(skb, q);  in dualpi2_enqueue_skb()
420 		++sch->q.qlen;  in dualpi2_enqueue_skb()
422 		++q->packets_in_l;  in dualpi2_enqueue_skb()
423 		if (!q->l_head_ts)  in dualpi2_enqueue_skb()
424 			q->l_head_ts = cb->ts;  in dualpi2_enqueue_skb()
425 		return qdisc_enqueue_tail(skb, q->l_queue);  in dualpi2_enqueue_skb()
427 	++q->packets_in_c;  in dualpi2_enqueue_skb()
428 	if (!q->c_head_ts)  in dualpi2_enqueue_skb()
429 		q->c_head_ts = cb->ts;  in dualpi2_enqueue_skb()
444 	struct dualpi2_sched_data *q = qdisc_priv(sch);  in dualpi2_qdisc_enqueue()  local
447 	err = dualpi2_skb_classify(q, skb);  in dualpi2_qdisc_enqueue()
455 	if (q->split_gso && skb_is_gso(skb)) {  in dualpi2_qdisc_enqueue()
466 		cnt = 1;  in dualpi2_qdisc_enqueue()
473 			 * (1) Set pkt_len from the single GSO fragments  in dualpi2_qdisc_enqueue()
492 		if (cnt > 1) {  in dualpi2_qdisc_enqueue()
517 				      struct dualpi2_sched_data *q,  in dequeue_packet()  argument
525 	c_len = qdisc_qlen(sch) - qdisc_qlen(q->l_queue);  in dequeue_packet()
526 	if (qdisc_qlen(q->l_queue) && (!c_len || q->c_protection_credit <= 0)) {  in dequeue_packet()
527 		skb = __qdisc_dequeue_head(&q->l_queue->q);  in dequeue_packet()
528 		WRITE_ONCE(q->l_head_ts, head_enqueue_time(q->l_queue));  in dequeue_packet()
530 			*credit_change = q->c_protection_wc;  in dequeue_packet()
531 		qdisc_qstats_backlog_dec(q->l_queue, skb);  in dequeue_packet()
534 		--sch->q.qlen;  in dequeue_packet()
535 		q->memory_used -= skb->truesize;  in dequeue_packet()
537 		skb = __qdisc_dequeue_head(&sch->q);  in dequeue_packet()
538 		WRITE_ONCE(q->c_head_ts, head_enqueue_time(sch));  in dequeue_packet()
539 		if (qdisc_qlen(q->l_queue))  in dequeue_packet()
540 			*credit_change = ~((s32)q->c_protection_wl) + 1;  in dequeue_packet()
541 		q->memory_used -= skb->truesize;  in dequeue_packet()
543 		dualpi2_reset_c_protection(q);  in dequeue_packet()
551 static int do_step_aqm(struct dualpi2_sched_data *q, struct sk_buff *skb,  in do_step_aqm()  argument
556 	if (q->step_in_packets)  in do_step_aqm()
557 		qdelay = qdisc_qlen(q->l_queue);  in do_step_aqm()
561 	if (dualpi2_skb_cb(skb)->apply_step && qdelay > q->step_thresh) {  in do_step_aqm()
564 			return 1;  in do_step_aqm()
567 		if (dualpi2_mark(q, skb))  in do_step_aqm()
568 			++q->step_marks;  in do_step_aqm()
570 	qdisc_bstats_update(q->l_queue, skb);  in do_step_aqm()
574 static void drop_and_retry(struct dualpi2_sched_data *q, struct sk_buff *skb,  in drop_and_retry()  argument
577 	++q->deferred_drops_cnt;  in drop_and_retry()
578 	q->deferred_drops_len += qdisc_pkt_len(skb);  in drop_and_retry()
585 	struct dualpi2_sched_data *q = qdisc_priv(sch);  in dualpi2_qdisc_dequeue()  local
592 	while ((skb = dequeue_packet(sch, q, &credit_change, now))) {  in dualpi2_qdisc_dequeue()
593 		if (!q->drop_early && must_drop(sch, q, skb)) {  in dualpi2_qdisc_dequeue()
594 			drop_and_retry(q, skb, sch,  in dualpi2_qdisc_dequeue()
599 		if (skb_in_l_queue(skb) && do_step_aqm(q, skb, now)) {  in dualpi2_qdisc_dequeue()
600 			qdisc_qstats_drop(q->l_queue);  in dualpi2_qdisc_dequeue()
601 			drop_and_retry(q, skb, sch,  in dualpi2_qdisc_dequeue()
606 		q->c_protection_credit += credit_change;  in dualpi2_qdisc_dequeue()
611 	if (q->deferred_drops_cnt) {  in dualpi2_qdisc_dequeue()
612 		qdisc_tree_reduce_backlog(sch, q->deferred_drops_cnt,  in dualpi2_qdisc_dequeue()
613 					  q->deferred_drops_len);  in dualpi2_qdisc_dequeue()
614 		q->deferred_drops_cnt = 0;  in dualpi2_qdisc_dequeue()
615 		q->deferred_drops_len = 0;  in dualpi2_qdisc_dequeue()
622 	do_div(diff, 1 << ALPHA_BETA_GRANULARITY);  in __scale_delta()
626 static void get_queue_delays(struct dualpi2_sched_data *q, u64 *qdelay_c,  in get_queue_delays()  argument
632 	qc = READ_ONCE(q->c_head_ts);  in get_queue_delays()
633 	ql = READ_ONCE(q->l_head_ts);  in get_queue_delays()
641 	struct dualpi2_sched_data *q = qdisc_priv(sch);  in calculate_probability()  local
648 	get_queue_delays(q, &qdelay_c, &qdelay_l);  in calculate_probability()
654 	delta = ((s64)qdelay - (s64)q->pi2_target) * q->pi2_alpha;  in calculate_probability()
655 	delta += ((s64)qdelay - (s64)q->last_qdelay) * q->pi2_beta;  in calculate_probability()
656 	q->last_qdelay = qdelay;  in calculate_probability()
660 		new_prob = __scale_delta(delta) + q->pi2_prob;  in calculate_probability()
661 		if (new_prob < q->pi2_prob)  in calculate_probability()
664 		new_prob = q->pi2_prob - __scale_delta(~delta + 1);  in calculate_probability()
665 		if (new_prob > q->pi2_prob)  in calculate_probability()
672 	if (!q->drop_overload)  in calculate_probability()
673 		return min_t(u32, new_prob, MAX_PROB / q->coupling_factor);  in calculate_probability()
711 	struct dualpi2_sched_data *q = timer_container_of(q, timer, pi2_timer);  in dualpi2_timer()  local
712 	struct Qdisc *sch = q->sch;  in dualpi2_timer()
719 	WRITE_ONCE(q->pi2_prob, calculate_probability(sch));  in dualpi2_timer()
720 	hrtimer_set_expires(&q->pi2_timer, next_pi2_timeout(q));  in dualpi2_timer()
728 	.min = 1,
732 static const struct nla_policy dualpi2_policy[TCA_DUALPI2_MAX + 1] = {
733 	[TCA_DUALPI2_LIMIT]		= NLA_POLICY_MIN(NLA_U32, 1),
734 	[TCA_DUALPI2_MEMORY_LIMIT]	= NLA_POLICY_MIN(NLA_U32, 1),
736 	[TCA_DUALPI2_TUPDATE]		= NLA_POLICY_MIN(NLA_U32, 1),
744 	[TCA_DUALPI2_COUPLING]		= NLA_POLICY_MIN(NLA_U8, 1),
761 	struct nlattr *tb[TCA_DUALPI2_MAX + 1];  in dualpi2_change()
762 	struct dualpi2_sched_data *q;  in dualpi2_change()  local
780 	q = qdisc_priv(sch);  in dualpi2_change()
787 		WRITE_ONCE(q->memory_limit, get_memory_limit(sch, limit));  in dualpi2_change()
791 		WRITE_ONCE(q->memory_limit,  in dualpi2_change()
797 		WRITE_ONCE(q->pi2_target, target * NSEC_PER_USEC);  in dualpi2_change()
803 		WRITE_ONCE(q->pi2_tupdate, convert_us_to_nsec(tupdate));  in dualpi2_change()
809 		WRITE_ONCE(q->pi2_alpha, dualpi2_scale_alpha_beta(alpha));  in dualpi2_change()
815 		WRITE_ONCE(q->pi2_beta, dualpi2_scale_alpha_beta(beta));  in dualpi2_change()
821 		WRITE_ONCE(q->step_in_packets, true);  in dualpi2_change()
822 		WRITE_ONCE(q->step_thresh, step_th);  in dualpi2_change()
826 		WRITE_ONCE(q->step_in_packets, false);  in dualpi2_change()
827 		WRITE_ONCE(q->step_thresh, convert_us_to_nsec(step_th));  in dualpi2_change()
831 		WRITE_ONCE(q->min_qlen_step,  in dualpi2_change()
837 		WRITE_ONCE(q->coupling_factor, coupling);  in dualpi2_change()
843 		WRITE_ONCE(q->drop_overload, (bool)drop_overload);  in dualpi2_change()
849 		WRITE_ONCE(q->drop_early, (bool)drop_early);  in dualpi2_change()
855 		dualpi2_calculate_c_protection(sch, q, wc);  in dualpi2_change()
861 		WRITE_ONCE(q->ecn_mask, ecn_mask);  in dualpi2_change()
867 		WRITE_ONCE(q->split_gso, (bool)split_gso);  in dualpi2_change()
873 	       q->memory_used > q->memory_limit) {  in dualpi2_change()
876 		q->memory_used -= skb->truesize;  in dualpi2_change()
890 	struct dualpi2_sched_data *q = qdisc_priv(sch);  in dualpi2_reset_default()  local
892 	q->sch->limit = 10000;				/* Max 125ms at 1Gbps */  in dualpi2_reset_default()
893 	q->memory_limit = get_memory_limit(sch, q->sch->limit);  in dualpi2_reset_default()
895 	q->pi2_target = 15 * NSEC_PER_MSEC;  in dualpi2_reset_default()
896 	q->pi2_tupdate = 16 * NSEC_PER_MSEC;  in dualpi2_reset_default()
897 	q->pi2_alpha = dualpi2_scale_alpha_beta(41);	/* ~0.16 Hz * 256 */  in dualpi2_reset_default()
898 	q->pi2_beta = dualpi2_scale_alpha_beta(819);	/* ~3.20 Hz * 256 */  in dualpi2_reset_default()
900 	q->step_thresh = 1 * NSEC_PER_MSEC;  in dualpi2_reset_default()
901 	q->step_in_packets = false;  in dualpi2_reset_default()
903 	dualpi2_calculate_c_protection(q->sch, q, 10);	/* wc=10%, wl=90% */  in dualpi2_reset_default()
905 	q->ecn_mask = TC_DUALPI2_ECN_MASK_L4S_ECT;	/* INET_ECN_ECT_1 */  in dualpi2_reset_default()
906 	q->min_qlen_step = 0;		/* Always apply step mark in L-queue */  in dualpi2_reset_default()
907 	q->coupling_factor = 2;		/* window fairness for equal RTTs */  in dualpi2_reset_default()
908 	q->drop_overload = TC_DUALPI2_DROP_OVERLOAD_DROP; /* Drop overload */  in dualpi2_reset_default()
909 	q->drop_early = TC_DUALPI2_DROP_EARLY_DROP_DEQUEUE; /* Drop dequeue */  in dualpi2_reset_default()
910 	q->split_gso = TC_DUALPI2_SPLIT_GSO_SPLIT_GSO;	/* Split GSO */  in dualpi2_reset_default()
916 	struct dualpi2_sched_data *q = qdisc_priv(sch);  in dualpi2_init()  local
919 	q->l_queue = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,  in dualpi2_init()
920 				       TC_H_MAKE(sch->handle, 1), extack);  in dualpi2_init()
921 	if (!q->l_queue)  in dualpi2_init()
924 	err = tcf_block_get(&q->tcf_block, &q->tcf_filters, sch, extack);  in dualpi2_init()
928 	q->sch = sch;  in dualpi2_init()
930 	hrtimer_setup(&q->pi2_timer, dualpi2_timer, CLOCK_MONOTONIC,  in dualpi2_init()
940 	hrtimer_start(&q->pi2_timer, next_pi2_timeout(q),  in dualpi2_init()
947 	struct dualpi2_sched_data *q = qdisc_priv(sch);  in dualpi2_dump()  local
952 	step_in_pkts = READ_ONCE(q->step_in_packets);  in dualpi2_dump()
953 	step_th = READ_ONCE(q->step_thresh);  in dualpi2_dump()
962 			READ_ONCE(q->memory_limit)) ||  in dualpi2_dump()
964 			convert_ns_to_usec(READ_ONCE(q->pi2_target))) ||  in dualpi2_dump()
966 			convert_ns_to_usec(READ_ONCE(q->pi2_tupdate))) ||  in dualpi2_dump()
968 			dualpi2_unscale_alpha_beta(READ_ONCE(q->pi2_alpha))) ||  in dualpi2_dump()
970 			dualpi2_unscale_alpha_beta(READ_ONCE(q->pi2_beta))) ||  in dualpi2_dump()
973 			READ_ONCE(q->min_qlen_step)) ||  in dualpi2_dump()
975 		       READ_ONCE(q->coupling_factor)) ||  in dualpi2_dump()
977 		       READ_ONCE(q->drop_overload)) ||  in dualpi2_dump()
979 		       READ_ONCE(q->drop_early)) ||  in dualpi2_dump()
981 		       READ_ONCE(q->c_protection_wc)) ||  in dualpi2_dump()
982 	    nla_put_u8(skb, TCA_DUALPI2_ECN_MASK, READ_ONCE(q->ecn_mask)) ||  in dualpi2_dump()
983 	    nla_put_u8(skb, TCA_DUALPI2_SPLIT_GSO, READ_ONCE(q->split_gso))))  in dualpi2_dump()
989 			READ_ONCE(q->memory_limit)) ||  in dualpi2_dump()
991 			convert_ns_to_usec(READ_ONCE(q->pi2_target))) ||  in dualpi2_dump()
993 			convert_ns_to_usec(READ_ONCE(q->pi2_tupdate))) ||  in dualpi2_dump()
995 			dualpi2_unscale_alpha_beta(READ_ONCE(q->pi2_alpha))) ||  in dualpi2_dump()
997 			dualpi2_unscale_alpha_beta(READ_ONCE(q->pi2_beta))) ||  in dualpi2_dump()
1001 			READ_ONCE(q->min_qlen_step)) ||  in dualpi2_dump()
1003 		       READ_ONCE(q->coupling_factor)) ||  in dualpi2_dump()
1005 		       READ_ONCE(q->drop_overload)) ||  in dualpi2_dump()
1007 		       READ_ONCE(q->drop_early)) ||  in dualpi2_dump()
1009 		       READ_ONCE(q->c_protection_wc)) ||  in dualpi2_dump()
1010 	    nla_put_u8(skb, TCA_DUALPI2_ECN_MASK, READ_ONCE(q->ecn_mask)) ||  in dualpi2_dump()
1011 	    nla_put_u8(skb, TCA_DUALPI2_SPLIT_GSO, READ_ONCE(q->split_gso))))  in dualpi2_dump()
1018 	return -1;  in dualpi2_dump()
1023 	struct dualpi2_sched_data *q = qdisc_priv(sch);  in dualpi2_dump_stats()  local
1025 		.prob			= READ_ONCE(q->pi2_prob),  in dualpi2_dump_stats()
1026 		.packets_in_c		= q->packets_in_c,  in dualpi2_dump_stats()
1027 		.packets_in_l		= q->packets_in_l,  in dualpi2_dump_stats()
1028 		.maxq			= q->maxq,  in dualpi2_dump_stats()
1029 		.ecn_mark		= q->ecn_mark,  in dualpi2_dump_stats()
1030 		.credit			= q->c_protection_credit,  in dualpi2_dump_stats()
1031 		.step_marks		= q->step_marks,  in dualpi2_dump_stats()
1032 		.memory_used		= q->memory_used,  in dualpi2_dump_stats()
1033 		.max_memory_used	= q->max_memory_used,  in dualpi2_dump_stats()
1034 		.memory_limit		= q->memory_limit,  in dualpi2_dump_stats()
1038 	get_queue_delays(q, &qc, &ql);  in dualpi2_dump_stats()
1050 	struct dualpi2_sched_data *q = qdisc_priv(sch);  in dualpi2_reset()  local
1053 	qdisc_reset_queue(q->l_queue);  in dualpi2_reset()
1054 	q->c_head_ts = 0;  in dualpi2_reset()
1055 	q->l_head_ts = 0;  in dualpi2_reset()
1056 	q->pi2_prob = 0;  in dualpi2_reset()
1057 	q->packets_in_c = 0;  in dualpi2_reset()
1058 	q->packets_in_l = 0;  in dualpi2_reset()
1059 	q->maxq = 0;  in dualpi2_reset()
1060 	q->ecn_mark = 0;  in dualpi2_reset()
1061 	q->step_marks = 0;  in dualpi2_reset()
1062 	q->memory_used = 0;  in dualpi2_reset()
1063 	q->max_memory_used = 0;  in dualpi2_reset()
1064 	dualpi2_reset_c_protection(q);  in dualpi2_reset()
1069 	struct dualpi2_sched_data *q = qdisc_priv(sch);  in dualpi2_destroy()  local
1071 	q->pi2_tupdate = 0;  in dualpi2_destroy()
1072 	hrtimer_cancel(&q->pi2_timer);  in dualpi2_destroy()
1073 	if (q->l_queue)  in dualpi2_destroy()
1074 		qdisc_put(q->l_queue);  in dualpi2_destroy()
1075 	tcf_block_put(q->tcf_block);  in dualpi2_destroy()
1094 static void dualpi2_unbind(struct Qdisc *q, unsigned long cl)  in dualpi2_unbind()  argument
1101 	struct dualpi2_sched_data *q = qdisc_priv(sch);  in dualpi2_tcf_block()  local
1105 	return q->tcf_block;  in dualpi2_tcf_block()
1121 		if (arg->fn(sch, i + 1, arg) < 0) {  in dualpi2_walk()
1122 			arg->stop = 1;  in dualpi2_walk()