Re: [PATCH net-next v3 09/15] quic: add congestion control

[Paolo Abeni <pabeni@redhat.com>]

On 9/19/25 12:34 AM, Xin Long wrote:
> This patch introduces 'quic_cong' for RTT measurement and congestion
> control. The 'quic_cong_ops' is added to define the congestion
> control algorithm.
> 
> It implements a congestion control state machine with slow start,
> congestion avoidance, and recovery phases, and introduces the New
> Reno and CUBIC algorithms.

To moderate the initial submission size, you could initially introduce
just one of the above.

> The implementation updates RTT estimates when packets are acknowledged,
> reacts to loss and ECN signals, and adjusts the congestion window
> accordingly during packet transmission and acknowledgment processing.
> 
> - quic_cong_rtt_update(): Performs RTT measurement, invoked when a
>   packet is acknowledged by the largest number in the ACK frame.
> 
> - quic_cong_on_packet_acked(): Invoked when a packet is acknowledged.
> 
> - quic_cong_on_packet_lost(): Invoked when a packet is marked as lost.
> 
> - quic_cong_on_process_ecn(): Invoked when an ACK_ECN frame is received.
> 
> - quic_cong_on_packet_sent(): Invoked when a packet is transmitted.
> 
> - quic_cong_on_ack_recv(): Invoked when an ACK frame is received.
> 
> Signed-off-by: Xin Long <lucien.xin@gmail.com>
> ---
>  net/quic/Makefile |   3 +-
>  net/quic/cong.c   | 700 ++++++++++++++++++++++++++++++++++++++++++++++
>  net/quic/cong.h   | 120 ++++++++
>  net/quic/socket.c |   1 +
>  net/quic/socket.h |   7 +
>  5 files changed, 830 insertions(+), 1 deletion(-)
>  create mode 100644 net/quic/cong.c
>  create mode 100644 net/quic/cong.h
> 
> diff --git a/net/quic/Makefile b/net/quic/Makefile
> index 1565fb5cef9d..4d4a42c6d565 100644
> --- a/net/quic/Makefile
> +++ b/net/quic/Makefile
> @@ -5,4 +5,5 @@
>  
>  obj-$(CONFIG_IP_QUIC) += quic.o
>  
> -quic-y := common.o family.o protocol.o socket.o stream.o connid.o path.o
> +quic-y := common.o family.o protocol.o socket.o stream.o connid.o path.o \
> +	  cong.o
> diff --git a/net/quic/cong.c b/net/quic/cong.c
> new file mode 100644
> index 000000000000..d598cc14b15e
> --- /dev/null
> +++ b/net/quic/cong.c
> @@ -0,0 +1,700 @@
> +// SPDX-License-Identifier: GPL-2.0-or-later
> +/* QUIC kernel implementation
> + * (C) Copyright Red Hat Corp. 2023
> + *
> + * This file is part of the QUIC kernel implementation
> + *
> + * Initialization/cleanup for QUIC protocol support.
> + *
> + * Written or modified by:
> + *    Xin Long <lucien.xin@gmail.com>
> + */
> +
> +#include <linux/jiffies.h>
> +#include <linux/quic.h>
> +#include <net/sock.h>
> +
> +#include "common.h"
> +#include "cong.h"
> +
> +/* CUBIC APIs */
> +struct quic_cubic {
> +	/* Variables of Interest in rfc9438#section-4.1.2 */
> +	u32 pending_w_add;		/* Accumulate fractional increments to W_est */
> +	u32 origin_point;		/* W_max */
> +	u32 epoch_start;		/* t_epoch */
> +	u32 pending_add;		/* Accumulates fractional additions to W_cubic */
> +	u32 w_last_max;			/* last W_max */
> +	u32 w_tcp;			/* W_est */
> +	u64 k;				/* K */
> +
> +	/* HyStart++ variables in rfc9406#section-4.2 */
> +	u32 current_round_min_rtt;	/* currentRoundMinRTT */
> +	u32 css_baseline_min_rtt;	/* cssBaselineMinRtt */
> +	u32 last_round_min_rtt;		/* lastRoundMinRTT */
> +	u16 rtt_sample_count;		/* rttSampleCount */
> +	u16 css_rounds;			/* Counter for consecutive rounds showing RTT increase */
> +	s64 window_end;			/* End of current CSS round (packet number) */
> +};
> +
> +/* HyStart++ constants in rfc9406#section-4.3 */
> +#define QUIC_HS_MIN_SSTHRESH		16
> +#define QUIC_HS_N_RTT_SAMPLE		8
> +#define QUIC_HS_MIN_ETA			4000
> +#define QUIC_HS_MAX_ETA			16000
> +#define QUIC_HS_MIN_RTT_DIVISOR		8
> +#define QUIC_HS_CSS_GROWTH_DIVISOR	4
> +#define QUIC_HS_CSS_ROUNDS		5
> +
> +static u64 cubic_root(u64 n)
> +{
> +	u64 a, d;
> +
> +	if (!n)
> +		return 0;
> +
> +	d = (64 - __builtin_clzll(n)) / 3;
> +	a = BIT_ULL(d + 1);
> +
> +	for (; a * a * a > n;) {
> +		d = div64_ul(n, a * a);
> +		a = div64_ul(2 * a + d, 3);
> +	}
> +	return a;
> +}

tcp_cubic() has already an helper to compute the square root. You could
re-use that one.

> +
> +/* rfc9406#section-4: HyStart++ Algorithm */
> +static void cubic_slow_start(struct quic_cong *cong, u32 bytes, s64 number)
> +{
> +	struct quic_cubic *cubic = quic_cong_priv(cong);
> +	u32 eta;
> +
> +	if (cubic->window_end <= number)
> +		cubic->window_end = -1;
> +
> +	/* cwnd = cwnd + (min(N, L * SMSS) / CSS_GROWTH_DIVISOR) */
> +	if (cubic->css_baseline_min_rtt != U32_MAX)
> +		bytes = bytes / QUIC_HS_CSS_GROWTH_DIVISOR;
> +	cong->window = min_t(u32, cong->window + bytes, cong->max_window);
> +
> +	if (cubic->css_baseline_min_rtt != U32_MAX) {
> +		/* If CSS_ROUNDS rounds are complete, enter congestion avoidance. */
> +		if (++cubic->css_rounds > QUIC_HS_CSS_ROUNDS) {
> +			cubic->css_baseline_min_rtt = U32_MAX;
> +			cubic->w_last_max = cong->window;
> +			cong->ssthresh = cong->window;
> +			cubic->css_rounds = 0;
> +		}
> +		return;
> +	}
> +
> +	/* if ((rttSampleCount >= N_RTT_SAMPLE) AND
> +	 *     (currentRoundMinRTT != infinity) AND
> +	 *     (lastRoundMinRTT != infinity))
> +	 *   RttThresh = max(MIN_RTT_THRESH,
> +	 *     min(lastRoundMinRTT / MIN_RTT_DIVISOR, MAX_RTT_THRESH))
> +	 *   if (currentRoundMinRTT >= (lastRoundMinRTT + RttThresh))
> +	 *     cssBaselineMinRtt = currentRoundMinRTT
> +	 *     exit slow start and enter CSS
> +	 */
> +	if (cubic->last_round_min_rtt != U32_MAX &&
> +	    cubic->current_round_min_rtt != U32_MAX &&
> +	    cong->window >= QUIC_HS_MIN_SSTHRESH * cong->mss &&
> +	    cubic->rtt_sample_count >= QUIC_HS_N_RTT_SAMPLE) {
> +		eta = cubic->last_round_min_rtt / QUIC_HS_MIN_RTT_DIVISOR;
> +		if (eta < QUIC_HS_MIN_ETA)
> +			eta = QUIC_HS_MIN_ETA;
> +		else if (eta > QUIC_HS_MAX_ETA)
> +			eta = QUIC_HS_MAX_ETA;
> +
> +		pr_debug("%s: current_round_min_rtt: %u, last_round_min_rtt: %u, eta: %u\n",
> +			 __func__, cubic->current_round_min_rtt, cubic->last_round_min_rtt, eta);
> +
> +		/* Delay increase triggers slow start exit and enter CSS. */
> +		if (cubic->current_round_min_rtt >= cubic->last_round_min_rtt + eta)
> +			cubic->css_baseline_min_rtt = cubic->current_round_min_rtt;
> +	}
> +}
> +
> +/* rfc9438#section-4: CUBIC Congestion Control */
> +static void cubic_cong_avoid(struct quic_cong *cong, u32 bytes)
> +{
> +	struct quic_cubic *cubic = quic_cong_priv(cong);
> +	u64 tx, kx, time_delta, delta, t;
> +	u64 target_add, tcp_add = 0;
> +	u64 target, cwnd_thres, m;
> +
> +	if (cubic->epoch_start == U32_MAX) {
> +		cubic->epoch_start = cong->time;
> +		if (cong->window < cubic->w_last_max) {
> +			/*
> +			 *        ┌────────────────┐
> +			 *     3  │W    - cwnd
> +			 *     ╲  │ max       epoch
> +			 * K =  ╲ │────────────────
> +			 *       ╲│       C
> +			 */
> +			cubic->k = cubic->w_last_max - cong->window;
> +			cubic->k = cubic_root(div64_ul(cubic->k * 10, (u64)cong->mss * 4));

Can `mss` be 0 at this point? Why?

> +			cubic->origin_point = cubic->w_last_max;
> +		} else {
> +			cubic->k = 0;
> +			cubic->origin_point = cong->window;
> +		}
> +		cubic->w_tcp = cong->window;
> +		cubic->pending_add = 0;
> +		cubic->pending_w_add = 0;
> +	}
> +
> +	/*
> +	 * t = t        - t
> +	 *      current    epoch
> +	 */
> +	t = cong->time - cubic->epoch_start;
> +	tx = div64_ul(t << 10, USEC_PER_SEC);
> +	kx = (cubic->k << 10);
> +	if (tx > kx)
> +		time_delta = tx - kx;
> +	else
> +		time_delta = kx - tx;
> +	/*
> +	 *                        3
> +	 * W     (t) = C * (t - K)  + W
> +	 *  cubic                      max
> +	 */
> +	delta = cong->mss * ((((time_delta * time_delta) >> 10) * time_delta) >> 10);
> +	delta = div64_ul(delta * 4, 10) >> 10;
> +	if (tx > kx)
> +		target = cubic->origin_point + delta;
> +	else
> +		target = cubic->origin_point - delta;
> +
> +	/*
> +	 * W     (t + RTT)
> +	 *  cubic
> +	 */
> +	cwnd_thres = (div64_ul((t + cong->smoothed_rtt) << 10, USEC_PER_SEC) * target) >> 10;
> +	pr_debug("%s: tgt: %llu, thres: %llu, delta: %llu, t: %llu, srtt: %u, tx: %llu, kx: %llu\n",
> +		 __func__, target, cwnd_thres, delta, t, cong->smoothed_rtt, tx, kx);
> +	/*
> +	 *          ⎧
> +	 *          ⎪cwnd            if  W     (t + RTT) < cwnd
> +	 *          ⎪                     cubic
> +	 *          ⎨1.5 * cwnd      if  W     (t + RTT) > 1.5 * cwnd
> +	 * target = ⎪                     cubic
> +	 *          ⎪W     (t + RTT) otherwise
> +	 *          ⎩ cubic
> +	 */
> +	if (cwnd_thres < cong->window)
> +		target = cong->window;
> +	else if (cwnd_thres * 2 > (u64)cong->window * 3)
> +		target = cong->window * 3 / 2;
> +	else
> +		target = cwnd_thres;
> +
> +	/*
> +	 * target - cwnd
> +	 * ─────────────
> +	 *      cwnd
> +	 */
> +	if (target > cong->window) {
> +		target_add = cubic->pending_add + cong->mss * (target - cong->window);
> +		cubic->pending_add = do_div(target_add, cong->window);
> +	} else {
> +		target_add = cubic->pending_add + cong->mss;
> +		cubic->pending_add = do_div(target_add, 100 * cong->window);
> +	}

Can `window` be 0 here? why?

> +
> +	pr_debug("%s: target: %llu, window: %u, target_add: %llu\n",
> +		 __func__, target, cong->window, target_add);
> +
> +	/*
> +	 *                        segments_acked
> +	 * W    = W    + α      * ──────────────
> +	 *  est    est    cubic        cwnd
> +	 */
> +	m = cubic->pending_w_add + cong->mss * bytes;
> +	cubic->pending_w_add = do_div(m, cong->window);
> +	cubic->w_tcp += m;
> +
> +	if (cubic->w_tcp > cong->window)
> +		tcp_add = div64_ul((u64)cong->mss * (cubic->w_tcp - cong->window), cong->window);
> +
> +	pr_debug("%s: w_tcp: %u, window: %u, tcp_add: %llu\n",
> +		 __func__, cubic->w_tcp, cong->window, tcp_add);
> +
> +	/* W_cubic(_t_) or _W_est_, whichever is bigger. */
> +	cong->window += max(tcp_add, target_add);
> +}
> +
> +static void cubic_recovery(struct quic_cong *cong)
> +{
> +	struct quic_cubic *cubic = quic_cong_priv(cong);
> +
> +	cong->recovery_time = cong->time;
> +	cubic->epoch_start = U32_MAX;
> +
> +	/* rfc9438#section-3.4:
> +	 *   CUBIC sets the multiplicative window decrease factor (β__cubic_) to 0.7,
> +	 *   whereas Reno uses 0.5.
> +	 *
> +	 * rfc9438#section-4.6:
> +	 *   ssthresh =  flight_size * β      new  ssthresh
> +	 *
> +	 *   Some implementations of CUBIC currently use _cwnd_ instead of _flight_size_ when
> +	 *   calculating a new _ssthresh_.
> +	 *
> +	 * rfc9438#section-4.7:
> +	 *
> +	 *          ⎧       1 + β
> +	 *          ⎪            cubic
> +	 *          ⎪cwnd * ────────── if  cwnd < W_max and fast convergence
> +	 *   W    = ⎨           2
> +	 *    max   ⎪                  enabled, further reduce  W_max
> +	 *          ⎪
> +	 *          ⎩cwnd             otherwise, remember cwnd before reduction
> +	 */
> +	if (cong->window < cubic->w_last_max)
> +		cubic->w_last_max = cong->window * 17 / 10 / 2;
> +	else
> +		cubic->w_last_max = cong->window;
> +
> +	cong->ssthresh = cong->window * 7 / 10;

There are quite a bit of magic numbers that should be replaced by macros
and/or associated with explainatory comments.

> +
> +/* rfc9002#section-5: Estimating the Round-Trip Time */
> +void quic_cong_rtt_update(struct quic_cong *cong, u32 time, u32 ack_delay)
> +{
> +	u32 adjusted_rtt, rttvar_sample;
> +
> +	/* Ignore RTT sample if ACK delay is suspiciously large. */
> +	if (ack_delay > cong->max_ack_delay * 2)
> +		return;
> +
> +	/* rfc9002#section-5.1: latest_rtt = ack_time - send_time_of_largest_acked */
> +	cong->latest_rtt = cong->time - time;
> +
> +	/* rfc9002#section-5.2: Estimating min_rtt */
> +	if (!cong->min_rtt_valid) {
> +		cong->min_rtt = cong->latest_rtt;
> +		cong->min_rtt_valid = 1;
> +	}
> +	if (cong->min_rtt > cong->latest_rtt)
> +		cong->min_rtt = cong->latest_rtt;
> +
> +	if (!cong->is_rtt_set) {
> +		/* rfc9002#section-5.3:
> +		 *   smoothed_rtt = latest_rtt
> +		 *   rttvar = latest_rtt / 2
> +		 */
> +		cong->smoothed_rtt = cong->latest_rtt;
> +		cong->rttvar = cong->smoothed_rtt / 2;
> +		quic_cong_pto_update(cong);
> +		cong->is_rtt_set = 1;
> +		return;
> +	}
> +
> +	/* rfc9002#section-5.3:
> +	 *   adjusted_rtt = latest_rtt
> +	 *   if (latest_rtt >= min_rtt + ack_delay):
> +	 *     adjusted_rtt = latest_rtt - ack_delay
> +	 *   smoothed_rtt = 7/8 * smoothed_rtt + 1/8 * adjusted_rtt
> +	 *   rttvar_sample = abs(smoothed_rtt - adjusted_rtt)
> +	 *   rttvar = 3/4 * rttvar + 1/4 * rttvar_sample
> +	 */
> +	adjusted_rtt = cong->latest_rtt;
> +	if (cong->latest_rtt >= cong->min_rtt + ack_delay)
> +		adjusted_rtt = cong->latest_rtt - ack_delay;
> +
> +	cong->smoothed_rtt = (cong->smoothed_rtt * 7 + adjusted_rtt) / 8;
> +	if (cong->smoothed_rtt >= adjusted_rtt)
> +		rttvar_sample = cong->smoothed_rtt - adjusted_rtt;
> +	else
> +		rttvar_sample = adjusted_rtt - cong->smoothed_rtt;

Here in a few other place before you could use abs_diff()

/P