16de4a9c4SMartin KaFai Lau // SPDX-License-Identifier: GPL-2.0-only
26de4a9c4SMartin KaFai Lau
36de4a9c4SMartin KaFai Lau /* WARNING: This implemenation is not necessarily the same
46de4a9c4SMartin KaFai Lau * as the tcp_cubic.c. The purpose is mainly for testing
56de4a9c4SMartin KaFai Lau * the kernel BPF logic.
66de4a9c4SMartin KaFai Lau *
76de4a9c4SMartin KaFai Lau * Highlights:
86de4a9c4SMartin KaFai Lau * 1. CONFIG_HZ .kconfig map is used.
96de4a9c4SMartin KaFai Lau * 2. In bictcp_update(), calculation is changed to use usec
106de4a9c4SMartin KaFai Lau * resolution (i.e. USEC_PER_JIFFY) instead of using jiffies.
116de4a9c4SMartin KaFai Lau * Thus, usecs_to_jiffies() is not used in the bpf_cubic.c.
126de4a9c4SMartin KaFai Lau * 3. In bitctcp_update() [under tcp_friendliness], the original
136de4a9c4SMartin KaFai Lau * "while (ca->ack_cnt > delta)" loop is changed to the equivalent
146de4a9c4SMartin KaFai Lau * "ca->ack_cnt / delta" operation.
156de4a9c4SMartin KaFai Lau */
166de4a9c4SMartin KaFai Lau
176de4a9c4SMartin KaFai Lau #include <linux/bpf.h>
180c402c6cSMartin KaFai Lau #include <linux/stddef.h>
190c402c6cSMartin KaFai Lau #include <linux/tcp.h>
206de4a9c4SMartin KaFai Lau #include "bpf_tcp_helpers.h"
216de4a9c4SMartin KaFai Lau
226de4a9c4SMartin KaFai Lau char _license[] SEC("license") = "GPL";
236de4a9c4SMartin KaFai Lau
246de4a9c4SMartin KaFai Lau #define clamp(val, lo, hi) min((typeof(val))max(val, lo), hi)
256de4a9c4SMartin KaFai Lau
266de4a9c4SMartin KaFai Lau #define BICTCP_BETA_SCALE 1024 /* Scale factor beta calculation
276de4a9c4SMartin KaFai Lau * max_cwnd = snd_cwnd * beta
286de4a9c4SMartin KaFai Lau */
296de4a9c4SMartin KaFai Lau #define BICTCP_HZ 10 /* BIC HZ 2^10 = 1024 */
306de4a9c4SMartin KaFai Lau
316de4a9c4SMartin KaFai Lau /* Two methods of hybrid slow start */
326de4a9c4SMartin KaFai Lau #define HYSTART_ACK_TRAIN 0x1
336de4a9c4SMartin KaFai Lau #define HYSTART_DELAY 0x2
346de4a9c4SMartin KaFai Lau
356de4a9c4SMartin KaFai Lau /* Number of delay samples for detecting the increase of delay */
366de4a9c4SMartin KaFai Lau #define HYSTART_MIN_SAMPLES 8
376de4a9c4SMartin KaFai Lau #define HYSTART_DELAY_MIN (4000U) /* 4ms */
386de4a9c4SMartin KaFai Lau #define HYSTART_DELAY_MAX (16000U) /* 16 ms */
396de4a9c4SMartin KaFai Lau #define HYSTART_DELAY_THRESH(x) clamp(x, HYSTART_DELAY_MIN, HYSTART_DELAY_MAX)
406de4a9c4SMartin KaFai Lau
416de4a9c4SMartin KaFai Lau static int fast_convergence = 1;
426de4a9c4SMartin KaFai Lau static const int beta = 717; /* = 717/1024 (BICTCP_BETA_SCALE) */
436de4a9c4SMartin KaFai Lau static int initial_ssthresh;
446de4a9c4SMartin KaFai Lau static const int bic_scale = 41;
456de4a9c4SMartin KaFai Lau static int tcp_friendliness = 1;
466de4a9c4SMartin KaFai Lau
476de4a9c4SMartin KaFai Lau static int hystart = 1;
486de4a9c4SMartin KaFai Lau static int hystart_detect = HYSTART_ACK_TRAIN | HYSTART_DELAY;
496de4a9c4SMartin KaFai Lau static int hystart_low_window = 16;
506de4a9c4SMartin KaFai Lau static int hystart_ack_delta_us = 2000;
516de4a9c4SMartin KaFai Lau
526de4a9c4SMartin KaFai Lau static const __u32 cube_rtt_scale = (bic_scale * 10); /* 1024*c/rtt */
536de4a9c4SMartin KaFai Lau static const __u32 beta_scale = 8*(BICTCP_BETA_SCALE+beta) / 3
546de4a9c4SMartin KaFai Lau / (BICTCP_BETA_SCALE - beta);
556de4a9c4SMartin KaFai Lau /* calculate the "K" for (wmax-cwnd) = c/rtt * K^3
566de4a9c4SMartin KaFai Lau * so K = cubic_root( (wmax-cwnd)*rtt/c )
576de4a9c4SMartin KaFai Lau * the unit of K is bictcp_HZ=2^10, not HZ
586de4a9c4SMartin KaFai Lau *
596de4a9c4SMartin KaFai Lau * c = bic_scale >> 10
606de4a9c4SMartin KaFai Lau * rtt = 100ms
616de4a9c4SMartin KaFai Lau *
626de4a9c4SMartin KaFai Lau * the following code has been designed and tested for
636de4a9c4SMartin KaFai Lau * cwnd < 1 million packets
646de4a9c4SMartin KaFai Lau * RTT < 100 seconds
656de4a9c4SMartin KaFai Lau * HZ < 1,000,00 (corresponding to 10 nano-second)
666de4a9c4SMartin KaFai Lau */
676de4a9c4SMartin KaFai Lau
686de4a9c4SMartin KaFai Lau /* 1/c * 2^2*bictcp_HZ * srtt, 2^40 */
696de4a9c4SMartin KaFai Lau static const __u64 cube_factor = (__u64)(1ull << (10+3*BICTCP_HZ))
706de4a9c4SMartin KaFai Lau / (bic_scale * 10);
716de4a9c4SMartin KaFai Lau
726de4a9c4SMartin KaFai Lau /* BIC TCP Parameters */
736de4a9c4SMartin KaFai Lau struct bictcp {
746de4a9c4SMartin KaFai Lau __u32 cnt; /* increase cwnd by 1 after ACKs */
756de4a9c4SMartin KaFai Lau __u32 last_max_cwnd; /* last maximum snd_cwnd */
766de4a9c4SMartin KaFai Lau __u32 last_cwnd; /* the last snd_cwnd */
776de4a9c4SMartin KaFai Lau __u32 last_time; /* time when updated last_cwnd */
786de4a9c4SMartin KaFai Lau __u32 bic_origin_point;/* origin point of bic function */
796de4a9c4SMartin KaFai Lau __u32 bic_K; /* time to origin point
806de4a9c4SMartin KaFai Lau from the beginning of the current epoch */
816de4a9c4SMartin KaFai Lau __u32 delay_min; /* min delay (usec) */
826de4a9c4SMartin KaFai Lau __u32 epoch_start; /* beginning of an epoch */
836de4a9c4SMartin KaFai Lau __u32 ack_cnt; /* number of acks */
846de4a9c4SMartin KaFai Lau __u32 tcp_cwnd; /* estimated tcp cwnd */
856de4a9c4SMartin KaFai Lau __u16 unused;
866de4a9c4SMartin KaFai Lau __u8 sample_cnt; /* number of samples to decide curr_rtt */
876de4a9c4SMartin KaFai Lau __u8 found; /* the exit point is found? */
886de4a9c4SMartin KaFai Lau __u32 round_start; /* beginning of each round */
896de4a9c4SMartin KaFai Lau __u32 end_seq; /* end_seq of the round */
906de4a9c4SMartin KaFai Lau __u32 last_ack; /* last time when the ACK spacing is close */
916de4a9c4SMartin KaFai Lau __u32 curr_rtt; /* the minimum rtt of current round */
926de4a9c4SMartin KaFai Lau };
936de4a9c4SMartin KaFai Lau
bictcp_reset(struct bictcp * ca)946de4a9c4SMartin KaFai Lau static inline void bictcp_reset(struct bictcp *ca)
956de4a9c4SMartin KaFai Lau {
966de4a9c4SMartin KaFai Lau ca->cnt = 0;
976de4a9c4SMartin KaFai Lau ca->last_max_cwnd = 0;
986de4a9c4SMartin KaFai Lau ca->last_cwnd = 0;
996de4a9c4SMartin KaFai Lau ca->last_time = 0;
1006de4a9c4SMartin KaFai Lau ca->bic_origin_point = 0;
1016de4a9c4SMartin KaFai Lau ca->bic_K = 0;
1026de4a9c4SMartin KaFai Lau ca->delay_min = 0;
1036de4a9c4SMartin KaFai Lau ca->epoch_start = 0;
1046de4a9c4SMartin KaFai Lau ca->ack_cnt = 0;
1056de4a9c4SMartin KaFai Lau ca->tcp_cwnd = 0;
1066de4a9c4SMartin KaFai Lau ca->found = 0;
1076de4a9c4SMartin KaFai Lau }
1086de4a9c4SMartin KaFai Lau
1096de4a9c4SMartin KaFai Lau extern unsigned long CONFIG_HZ __kconfig;
1106de4a9c4SMartin KaFai Lau #define HZ CONFIG_HZ
1116de4a9c4SMartin KaFai Lau #define USEC_PER_MSEC 1000UL
1126de4a9c4SMartin KaFai Lau #define USEC_PER_SEC 1000000UL
1136de4a9c4SMartin KaFai Lau #define USEC_PER_JIFFY (USEC_PER_SEC / HZ)
1146de4a9c4SMartin KaFai Lau
div64_u64(__u64 dividend,__u64 divisor)1156de4a9c4SMartin KaFai Lau static __always_inline __u64 div64_u64(__u64 dividend, __u64 divisor)
1166de4a9c4SMartin KaFai Lau {
1176de4a9c4SMartin KaFai Lau return dividend / divisor;
1186de4a9c4SMartin KaFai Lau }
1196de4a9c4SMartin KaFai Lau
1206de4a9c4SMartin KaFai Lau #define div64_ul div64_u64
1216de4a9c4SMartin KaFai Lau
1226de4a9c4SMartin KaFai Lau #define BITS_PER_U64 (sizeof(__u64) * 8)
fls64(__u64 x)1236de4a9c4SMartin KaFai Lau static __always_inline int fls64(__u64 x)
1246de4a9c4SMartin KaFai Lau {
1256de4a9c4SMartin KaFai Lau int num = BITS_PER_U64 - 1;
1266de4a9c4SMartin KaFai Lau
1276de4a9c4SMartin KaFai Lau if (x == 0)
1286de4a9c4SMartin KaFai Lau return 0;
1296de4a9c4SMartin KaFai Lau
1306de4a9c4SMartin KaFai Lau if (!(x & (~0ull << (BITS_PER_U64-32)))) {
1316de4a9c4SMartin KaFai Lau num -= 32;
1326de4a9c4SMartin KaFai Lau x <<= 32;
1336de4a9c4SMartin KaFai Lau }
1346de4a9c4SMartin KaFai Lau if (!(x & (~0ull << (BITS_PER_U64-16)))) {
1356de4a9c4SMartin KaFai Lau num -= 16;
1366de4a9c4SMartin KaFai Lau x <<= 16;
1376de4a9c4SMartin KaFai Lau }
1386de4a9c4SMartin KaFai Lau if (!(x & (~0ull << (BITS_PER_U64-8)))) {
1396de4a9c4SMartin KaFai Lau num -= 8;
1406de4a9c4SMartin KaFai Lau x <<= 8;
1416de4a9c4SMartin KaFai Lau }
1426de4a9c4SMartin KaFai Lau if (!(x & (~0ull << (BITS_PER_U64-4)))) {
1436de4a9c4SMartin KaFai Lau num -= 4;
1446de4a9c4SMartin KaFai Lau x <<= 4;
1456de4a9c4SMartin KaFai Lau }
1466de4a9c4SMartin KaFai Lau if (!(x & (~0ull << (BITS_PER_U64-2)))) {
1476de4a9c4SMartin KaFai Lau num -= 2;
1486de4a9c4SMartin KaFai Lau x <<= 2;
1496de4a9c4SMartin KaFai Lau }
1506de4a9c4SMartin KaFai Lau if (!(x & (~0ull << (BITS_PER_U64-1))))
1516de4a9c4SMartin KaFai Lau num -= 1;
1526de4a9c4SMartin KaFai Lau
1536de4a9c4SMartin KaFai Lau return num + 1;
1546de4a9c4SMartin KaFai Lau }
1556de4a9c4SMartin KaFai Lau
bictcp_clock_us(const struct sock * sk)1566de4a9c4SMartin KaFai Lau static __always_inline __u32 bictcp_clock_us(const struct sock *sk)
1576de4a9c4SMartin KaFai Lau {
1586de4a9c4SMartin KaFai Lau return tcp_sk(sk)->tcp_mstamp;
1596de4a9c4SMartin KaFai Lau }
1606de4a9c4SMartin KaFai Lau
bictcp_hystart_reset(struct sock * sk)1616de4a9c4SMartin KaFai Lau static __always_inline void bictcp_hystart_reset(struct sock *sk)
1626de4a9c4SMartin KaFai Lau {
1636de4a9c4SMartin KaFai Lau struct tcp_sock *tp = tcp_sk(sk);
1646de4a9c4SMartin KaFai Lau struct bictcp *ca = inet_csk_ca(sk);
1656de4a9c4SMartin KaFai Lau
1666de4a9c4SMartin KaFai Lau ca->round_start = ca->last_ack = bictcp_clock_us(sk);
1676de4a9c4SMartin KaFai Lau ca->end_seq = tp->snd_nxt;
1686de4a9c4SMartin KaFai Lau ca->curr_rtt = ~0U;
1696de4a9c4SMartin KaFai Lau ca->sample_cnt = 0;
1706de4a9c4SMartin KaFai Lau }
1716de4a9c4SMartin KaFai Lau
17253df63ccSAndrii Nakryiko /* "struct_ops/" prefix is a requirement */
17339cd9e0fSMartin KaFai Lau SEC("struct_ops/bpf_cubic_init")
BPF_PROG(bpf_cubic_init,struct sock * sk)17439cd9e0fSMartin KaFai Lau void BPF_PROG(bpf_cubic_init, struct sock *sk)
1756de4a9c4SMartin KaFai Lau {
1766de4a9c4SMartin KaFai Lau struct bictcp *ca = inet_csk_ca(sk);
1776de4a9c4SMartin KaFai Lau
1786de4a9c4SMartin KaFai Lau bictcp_reset(ca);
1796de4a9c4SMartin KaFai Lau
1806de4a9c4SMartin KaFai Lau if (hystart)
1816de4a9c4SMartin KaFai Lau bictcp_hystart_reset(sk);
1826de4a9c4SMartin KaFai Lau
1836de4a9c4SMartin KaFai Lau if (!hystart && initial_ssthresh)
1846de4a9c4SMartin KaFai Lau tcp_sk(sk)->snd_ssthresh = initial_ssthresh;
1856de4a9c4SMartin KaFai Lau }
1866de4a9c4SMartin KaFai Lau
18753df63ccSAndrii Nakryiko /* "struct_ops" prefix is a requirement */
18853df63ccSAndrii Nakryiko SEC("struct_ops/bpf_cubic_cwnd_event")
BPF_PROG(bpf_cubic_cwnd_event,struct sock * sk,enum tcp_ca_event event)18939cd9e0fSMartin KaFai Lau void BPF_PROG(bpf_cubic_cwnd_event, struct sock *sk, enum tcp_ca_event event)
1906de4a9c4SMartin KaFai Lau {
1916de4a9c4SMartin KaFai Lau if (event == CA_EVENT_TX_START) {
1926de4a9c4SMartin KaFai Lau struct bictcp *ca = inet_csk_ca(sk);
1936de4a9c4SMartin KaFai Lau __u32 now = tcp_jiffies32;
1946de4a9c4SMartin KaFai Lau __s32 delta;
1956de4a9c4SMartin KaFai Lau
1966de4a9c4SMartin KaFai Lau delta = now - tcp_sk(sk)->lsndtime;
1976de4a9c4SMartin KaFai Lau
1986de4a9c4SMartin KaFai Lau /* We were application limited (idle) for a while.
1996de4a9c4SMartin KaFai Lau * Shift epoch_start to keep cwnd growth to cubic curve.
2006de4a9c4SMartin KaFai Lau */
2016de4a9c4SMartin KaFai Lau if (ca->epoch_start && delta > 0) {
2026de4a9c4SMartin KaFai Lau ca->epoch_start += delta;
2036de4a9c4SMartin KaFai Lau if (after(ca->epoch_start, now))
2046de4a9c4SMartin KaFai Lau ca->epoch_start = now;
2056de4a9c4SMartin KaFai Lau }
2066de4a9c4SMartin KaFai Lau return;
2076de4a9c4SMartin KaFai Lau }
2086de4a9c4SMartin KaFai Lau }
2096de4a9c4SMartin KaFai Lau
2106de4a9c4SMartin KaFai Lau /*
2116de4a9c4SMartin KaFai Lau * cbrt(x) MSB values for x MSB values in [0..63].
2126de4a9c4SMartin KaFai Lau * Precomputed then refined by hand - Willy Tarreau
2136de4a9c4SMartin KaFai Lau *
2146de4a9c4SMartin KaFai Lau * For x in [0..63],
2156de4a9c4SMartin KaFai Lau * v = cbrt(x << 18) - 1
2166de4a9c4SMartin KaFai Lau * cbrt(x) = (v[x] + 10) >> 6
2176de4a9c4SMartin KaFai Lau */
2186de4a9c4SMartin KaFai Lau static const __u8 v[] = {
2196de4a9c4SMartin KaFai Lau /* 0x00 */ 0, 54, 54, 54, 118, 118, 118, 118,
2206de4a9c4SMartin KaFai Lau /* 0x08 */ 123, 129, 134, 138, 143, 147, 151, 156,
2216de4a9c4SMartin KaFai Lau /* 0x10 */ 157, 161, 164, 168, 170, 173, 176, 179,
2226de4a9c4SMartin KaFai Lau /* 0x18 */ 181, 185, 187, 190, 192, 194, 197, 199,
2236de4a9c4SMartin KaFai Lau /* 0x20 */ 200, 202, 204, 206, 209, 211, 213, 215,
2246de4a9c4SMartin KaFai Lau /* 0x28 */ 217, 219, 221, 222, 224, 225, 227, 229,
2256de4a9c4SMartin KaFai Lau /* 0x30 */ 231, 232, 234, 236, 237, 239, 240, 242,
2266de4a9c4SMartin KaFai Lau /* 0x38 */ 244, 245, 246, 248, 250, 251, 252, 254,
2276de4a9c4SMartin KaFai Lau };
2286de4a9c4SMartin KaFai Lau
2296de4a9c4SMartin KaFai Lau /* calculate the cubic root of x using a table lookup followed by one
2306de4a9c4SMartin KaFai Lau * Newton-Raphson iteration.
2316de4a9c4SMartin KaFai Lau * Avg err ~= 0.195%
2326de4a9c4SMartin KaFai Lau */
cubic_root(__u64 a)2336de4a9c4SMartin KaFai Lau static __always_inline __u32 cubic_root(__u64 a)
2346de4a9c4SMartin KaFai Lau {
2356de4a9c4SMartin KaFai Lau __u32 x, b, shift;
2366de4a9c4SMartin KaFai Lau
2376de4a9c4SMartin KaFai Lau if (a < 64) {
2386de4a9c4SMartin KaFai Lau /* a in [0..63] */
2396de4a9c4SMartin KaFai Lau return ((__u32)v[(__u32)a] + 35) >> 6;
2406de4a9c4SMartin KaFai Lau }
2416de4a9c4SMartin KaFai Lau
2426de4a9c4SMartin KaFai Lau b = fls64(a);
2436de4a9c4SMartin KaFai Lau b = ((b * 84) >> 8) - 1;
2446de4a9c4SMartin KaFai Lau shift = (a >> (b * 3));
2456de4a9c4SMartin KaFai Lau
2466de4a9c4SMartin KaFai Lau /* it is needed for verifier's bound check on v */
2476de4a9c4SMartin KaFai Lau if (shift >= 64)
2486de4a9c4SMartin KaFai Lau return 0;
2496de4a9c4SMartin KaFai Lau
2506de4a9c4SMartin KaFai Lau x = ((__u32)(((__u32)v[shift] + 10) << b)) >> 6;
2516de4a9c4SMartin KaFai Lau
2526de4a9c4SMartin KaFai Lau /*
2536de4a9c4SMartin KaFai Lau * Newton-Raphson iteration
2546de4a9c4SMartin KaFai Lau * 2
2556de4a9c4SMartin KaFai Lau * x = ( 2 * x + a / x ) / 3
2566de4a9c4SMartin KaFai Lau * k+1 k k
2576de4a9c4SMartin KaFai Lau */
2586de4a9c4SMartin KaFai Lau x = (2 * x + (__u32)div64_u64(a, (__u64)x * (__u64)(x - 1)));
2596de4a9c4SMartin KaFai Lau x = ((x * 341) >> 10);
2606de4a9c4SMartin KaFai Lau return x;
2616de4a9c4SMartin KaFai Lau }
2626de4a9c4SMartin KaFai Lau
2636de4a9c4SMartin KaFai Lau /*
2646de4a9c4SMartin KaFai Lau * Compute congestion window to use.
2656de4a9c4SMartin KaFai Lau */
bictcp_update(struct bictcp * ca,__u32 cwnd,__u32 acked)2666de4a9c4SMartin KaFai Lau static __always_inline void bictcp_update(struct bictcp *ca, __u32 cwnd,
2676de4a9c4SMartin KaFai Lau __u32 acked)
2686de4a9c4SMartin KaFai Lau {
2696de4a9c4SMartin KaFai Lau __u32 delta, bic_target, max_cnt;
2706de4a9c4SMartin KaFai Lau __u64 offs, t;
2716de4a9c4SMartin KaFai Lau
2726de4a9c4SMartin KaFai Lau ca->ack_cnt += acked; /* count the number of ACKed packets */
2736de4a9c4SMartin KaFai Lau
2746de4a9c4SMartin KaFai Lau if (ca->last_cwnd == cwnd &&
2756de4a9c4SMartin KaFai Lau (__s32)(tcp_jiffies32 - ca->last_time) <= HZ / 32)
2766de4a9c4SMartin KaFai Lau return;
2776de4a9c4SMartin KaFai Lau
2786de4a9c4SMartin KaFai Lau /* The CUBIC function can update ca->cnt at most once per jiffy.
2796de4a9c4SMartin KaFai Lau * On all cwnd reduction events, ca->epoch_start is set to 0,
2806de4a9c4SMartin KaFai Lau * which will force a recalculation of ca->cnt.
2816de4a9c4SMartin KaFai Lau */
2826de4a9c4SMartin KaFai Lau if (ca->epoch_start && tcp_jiffies32 == ca->last_time)
2836de4a9c4SMartin KaFai Lau goto tcp_friendliness;
2846de4a9c4SMartin KaFai Lau
2856de4a9c4SMartin KaFai Lau ca->last_cwnd = cwnd;
2866de4a9c4SMartin KaFai Lau ca->last_time = tcp_jiffies32;
2876de4a9c4SMartin KaFai Lau
2886de4a9c4SMartin KaFai Lau if (ca->epoch_start == 0) {
2896de4a9c4SMartin KaFai Lau ca->epoch_start = tcp_jiffies32; /* record beginning */
2906de4a9c4SMartin KaFai Lau ca->ack_cnt = acked; /* start counting */
2916de4a9c4SMartin KaFai Lau ca->tcp_cwnd = cwnd; /* syn with cubic */
2926de4a9c4SMartin KaFai Lau
2936de4a9c4SMartin KaFai Lau if (ca->last_max_cwnd <= cwnd) {
2946de4a9c4SMartin KaFai Lau ca->bic_K = 0;
2956de4a9c4SMartin KaFai Lau ca->bic_origin_point = cwnd;
2966de4a9c4SMartin KaFai Lau } else {
2976de4a9c4SMartin KaFai Lau /* Compute new K based on
2986de4a9c4SMartin KaFai Lau * (wmax-cwnd) * (srtt>>3 / HZ) / c * 2^(3*bictcp_HZ)
2996de4a9c4SMartin KaFai Lau */
3006de4a9c4SMartin KaFai Lau ca->bic_K = cubic_root(cube_factor
3016de4a9c4SMartin KaFai Lau * (ca->last_max_cwnd - cwnd));
3026de4a9c4SMartin KaFai Lau ca->bic_origin_point = ca->last_max_cwnd;
3036de4a9c4SMartin KaFai Lau }
3046de4a9c4SMartin KaFai Lau }
3056de4a9c4SMartin KaFai Lau
3066de4a9c4SMartin KaFai Lau /* cubic function - calc*/
3076de4a9c4SMartin KaFai Lau /* calculate c * time^3 / rtt,
3086de4a9c4SMartin KaFai Lau * while considering overflow in calculation of time^3
3096de4a9c4SMartin KaFai Lau * (so time^3 is done by using 64 bit)
3106de4a9c4SMartin KaFai Lau * and without the support of division of 64bit numbers
3116de4a9c4SMartin KaFai Lau * (so all divisions are done by using 32 bit)
3126de4a9c4SMartin KaFai Lau * also NOTE the unit of those veriables
3136de4a9c4SMartin KaFai Lau * time = (t - K) / 2^bictcp_HZ
3146de4a9c4SMartin KaFai Lau * c = bic_scale >> 10
3156de4a9c4SMartin KaFai Lau * rtt = (srtt >> 3) / HZ
3166de4a9c4SMartin KaFai Lau * !!! The following code does not have overflow problems,
3176de4a9c4SMartin KaFai Lau * if the cwnd < 1 million packets !!!
3186de4a9c4SMartin KaFai Lau */
3196de4a9c4SMartin KaFai Lau
3206de4a9c4SMartin KaFai Lau t = (__s32)(tcp_jiffies32 - ca->epoch_start) * USEC_PER_JIFFY;
3216de4a9c4SMartin KaFai Lau t += ca->delay_min;
3226de4a9c4SMartin KaFai Lau /* change the unit from usec to bictcp_HZ */
3236de4a9c4SMartin KaFai Lau t <<= BICTCP_HZ;
3246de4a9c4SMartin KaFai Lau t /= USEC_PER_SEC;
3256de4a9c4SMartin KaFai Lau
3266de4a9c4SMartin KaFai Lau if (t < ca->bic_K) /* t - K */
3276de4a9c4SMartin KaFai Lau offs = ca->bic_K - t;
3286de4a9c4SMartin KaFai Lau else
3296de4a9c4SMartin KaFai Lau offs = t - ca->bic_K;
3306de4a9c4SMartin KaFai Lau
3316de4a9c4SMartin KaFai Lau /* c/rtt * (t-K)^3 */
3326de4a9c4SMartin KaFai Lau delta = (cube_rtt_scale * offs * offs * offs) >> (10+3*BICTCP_HZ);
3336de4a9c4SMartin KaFai Lau if (t < ca->bic_K) /* below origin*/
3346de4a9c4SMartin KaFai Lau bic_target = ca->bic_origin_point - delta;
3356de4a9c4SMartin KaFai Lau else /* above origin*/
3366de4a9c4SMartin KaFai Lau bic_target = ca->bic_origin_point + delta;
3376de4a9c4SMartin KaFai Lau
3386de4a9c4SMartin KaFai Lau /* cubic function - calc bictcp_cnt*/
3396de4a9c4SMartin KaFai Lau if (bic_target > cwnd) {
3406de4a9c4SMartin KaFai Lau ca->cnt = cwnd / (bic_target - cwnd);
3416de4a9c4SMartin KaFai Lau } else {
3426de4a9c4SMartin KaFai Lau ca->cnt = 100 * cwnd; /* very small increment*/
3436de4a9c4SMartin KaFai Lau }
3446de4a9c4SMartin KaFai Lau
3456de4a9c4SMartin KaFai Lau /*
3466de4a9c4SMartin KaFai Lau * The initial growth of cubic function may be too conservative
3476de4a9c4SMartin KaFai Lau * when the available bandwidth is still unknown.
3486de4a9c4SMartin KaFai Lau */
3496de4a9c4SMartin KaFai Lau if (ca->last_max_cwnd == 0 && ca->cnt > 20)
3506de4a9c4SMartin KaFai Lau ca->cnt = 20; /* increase cwnd 5% per RTT */
3516de4a9c4SMartin KaFai Lau
3526de4a9c4SMartin KaFai Lau tcp_friendliness:
3536de4a9c4SMartin KaFai Lau /* TCP Friendly */
3546de4a9c4SMartin KaFai Lau if (tcp_friendliness) {
3556de4a9c4SMartin KaFai Lau __u32 scale = beta_scale;
3566de4a9c4SMartin KaFai Lau __u32 n;
3576de4a9c4SMartin KaFai Lau
3586de4a9c4SMartin KaFai Lau /* update tcp cwnd */
3596de4a9c4SMartin KaFai Lau delta = (cwnd * scale) >> 3;
3606de4a9c4SMartin KaFai Lau if (ca->ack_cnt > delta && delta) {
3616de4a9c4SMartin KaFai Lau n = ca->ack_cnt / delta;
3626de4a9c4SMartin KaFai Lau ca->ack_cnt -= n * delta;
3636de4a9c4SMartin KaFai Lau ca->tcp_cwnd += n;
3646de4a9c4SMartin KaFai Lau }
3656de4a9c4SMartin KaFai Lau
3666de4a9c4SMartin KaFai Lau if (ca->tcp_cwnd > cwnd) { /* if bic is slower than tcp */
3676de4a9c4SMartin KaFai Lau delta = ca->tcp_cwnd - cwnd;
3686de4a9c4SMartin KaFai Lau max_cnt = cwnd / delta;
3696de4a9c4SMartin KaFai Lau if (ca->cnt > max_cnt)
3706de4a9c4SMartin KaFai Lau ca->cnt = max_cnt;
3716de4a9c4SMartin KaFai Lau }
3726de4a9c4SMartin KaFai Lau }
3736de4a9c4SMartin KaFai Lau
3746de4a9c4SMartin KaFai Lau /* The maximum rate of cwnd increase CUBIC allows is 1 packet per
3756de4a9c4SMartin KaFai Lau * 2 packets ACKed, meaning cwnd grows at 1.5x per RTT.
3766de4a9c4SMartin KaFai Lau */
3776de4a9c4SMartin KaFai Lau ca->cnt = max(ca->cnt, 2U);
3786de4a9c4SMartin KaFai Lau }
3796de4a9c4SMartin KaFai Lau
3806de4a9c4SMartin KaFai Lau /* Or simply use the BPF_STRUCT_OPS to avoid the SEC boiler plate. */
BPF_STRUCT_OPS(bpf_cubic_cong_avoid,struct sock * sk,__u32 ack,__u32 acked)38139cd9e0fSMartin KaFai Lau void BPF_STRUCT_OPS(bpf_cubic_cong_avoid, struct sock *sk, __u32 ack, __u32 acked)
3826de4a9c4SMartin KaFai Lau {
3836de4a9c4SMartin KaFai Lau struct tcp_sock *tp = tcp_sk(sk);
3846de4a9c4SMartin KaFai Lau struct bictcp *ca = inet_csk_ca(sk);
3856de4a9c4SMartin KaFai Lau
3866de4a9c4SMartin KaFai Lau if (!tcp_is_cwnd_limited(sk))
3876de4a9c4SMartin KaFai Lau return;
3886de4a9c4SMartin KaFai Lau
3896de4a9c4SMartin KaFai Lau if (tcp_in_slow_start(tp)) {
3906de4a9c4SMartin KaFai Lau if (hystart && after(ack, ca->end_seq))
3916de4a9c4SMartin KaFai Lau bictcp_hystart_reset(sk);
3926de4a9c4SMartin KaFai Lau acked = tcp_slow_start(tp, acked);
3936de4a9c4SMartin KaFai Lau if (!acked)
3946de4a9c4SMartin KaFai Lau return;
3956de4a9c4SMartin KaFai Lau }
3966de4a9c4SMartin KaFai Lau bictcp_update(ca, tp->snd_cwnd, acked);
3976de4a9c4SMartin KaFai Lau tcp_cong_avoid_ai(tp, ca->cnt, acked);
3986de4a9c4SMartin KaFai Lau }
3996de4a9c4SMartin KaFai Lau
BPF_STRUCT_OPS(bpf_cubic_recalc_ssthresh,struct sock * sk)40039cd9e0fSMartin KaFai Lau __u32 BPF_STRUCT_OPS(bpf_cubic_recalc_ssthresh, struct sock *sk)
4016de4a9c4SMartin KaFai Lau {
4026de4a9c4SMartin KaFai Lau const struct tcp_sock *tp = tcp_sk(sk);
4036de4a9c4SMartin KaFai Lau struct bictcp *ca = inet_csk_ca(sk);
4046de4a9c4SMartin KaFai Lau
4056de4a9c4SMartin KaFai Lau ca->epoch_start = 0; /* end of epoch */
4066de4a9c4SMartin KaFai Lau
4076de4a9c4SMartin KaFai Lau /* Wmax and fast convergence */
4086de4a9c4SMartin KaFai Lau if (tp->snd_cwnd < ca->last_max_cwnd && fast_convergence)
4096de4a9c4SMartin KaFai Lau ca->last_max_cwnd = (tp->snd_cwnd * (BICTCP_BETA_SCALE + beta))
4106de4a9c4SMartin KaFai Lau / (2 * BICTCP_BETA_SCALE);
4116de4a9c4SMartin KaFai Lau else
4126de4a9c4SMartin KaFai Lau ca->last_max_cwnd = tp->snd_cwnd;
4136de4a9c4SMartin KaFai Lau
4146de4a9c4SMartin KaFai Lau return max((tp->snd_cwnd * beta) / BICTCP_BETA_SCALE, 2U);
4156de4a9c4SMartin KaFai Lau }
4166de4a9c4SMartin KaFai Lau
BPF_STRUCT_OPS(bpf_cubic_state,struct sock * sk,__u8 new_state)41739cd9e0fSMartin KaFai Lau void BPF_STRUCT_OPS(bpf_cubic_state, struct sock *sk, __u8 new_state)
4186de4a9c4SMartin KaFai Lau {
4196de4a9c4SMartin KaFai Lau if (new_state == TCP_CA_Loss) {
4206de4a9c4SMartin KaFai Lau bictcp_reset(inet_csk_ca(sk));
4216de4a9c4SMartin KaFai Lau bictcp_hystart_reset(sk);
4226de4a9c4SMartin KaFai Lau }
4236de4a9c4SMartin KaFai Lau }
4246de4a9c4SMartin KaFai Lau
4256de4a9c4SMartin KaFai Lau #define GSO_MAX_SIZE 65536
4266de4a9c4SMartin KaFai Lau
4276de4a9c4SMartin KaFai Lau /* Account for TSO/GRO delays.
4286de4a9c4SMartin KaFai Lau * Otherwise short RTT flows could get too small ssthresh, since during
4296de4a9c4SMartin KaFai Lau * slow start we begin with small TSO packets and ca->delay_min would
4306de4a9c4SMartin KaFai Lau * not account for long aggregation delay when TSO packets get bigger.
4316de4a9c4SMartin KaFai Lau * Ideally even with a very small RTT we would like to have at least one
4326de4a9c4SMartin KaFai Lau * TSO packet being sent and received by GRO, and another one in qdisc layer.
4336de4a9c4SMartin KaFai Lau * We apply another 100% factor because @rate is doubled at this point.
4346de4a9c4SMartin KaFai Lau * We cap the cushion to 1ms.
4356de4a9c4SMartin KaFai Lau */
hystart_ack_delay(struct sock * sk)4366de4a9c4SMartin KaFai Lau static __always_inline __u32 hystart_ack_delay(struct sock *sk)
4376de4a9c4SMartin KaFai Lau {
4386de4a9c4SMartin KaFai Lau unsigned long rate;
4396de4a9c4SMartin KaFai Lau
4406de4a9c4SMartin KaFai Lau rate = sk->sk_pacing_rate;
4416de4a9c4SMartin KaFai Lau if (!rate)
4426de4a9c4SMartin KaFai Lau return 0;
4436de4a9c4SMartin KaFai Lau return min((__u64)USEC_PER_MSEC,
4446de4a9c4SMartin KaFai Lau div64_ul((__u64)GSO_MAX_SIZE * 4 * USEC_PER_SEC, rate));
4456de4a9c4SMartin KaFai Lau }
4466de4a9c4SMartin KaFai Lau
hystart_update(struct sock * sk,__u32 delay)4476de4a9c4SMartin KaFai Lau static __always_inline void hystart_update(struct sock *sk, __u32 delay)
4486de4a9c4SMartin KaFai Lau {
4496de4a9c4SMartin KaFai Lau struct tcp_sock *tp = tcp_sk(sk);
4506de4a9c4SMartin KaFai Lau struct bictcp *ca = inet_csk_ca(sk);
4516de4a9c4SMartin KaFai Lau __u32 threshold;
4526de4a9c4SMartin KaFai Lau
4536de4a9c4SMartin KaFai Lau if (hystart_detect & HYSTART_ACK_TRAIN) {
4546de4a9c4SMartin KaFai Lau __u32 now = bictcp_clock_us(sk);
4556de4a9c4SMartin KaFai Lau
4566de4a9c4SMartin KaFai Lau /* first detection parameter - ack-train detection */
4576de4a9c4SMartin KaFai Lau if ((__s32)(now - ca->last_ack) <= hystart_ack_delta_us) {
4586de4a9c4SMartin KaFai Lau ca->last_ack = now;
4596de4a9c4SMartin KaFai Lau
4606de4a9c4SMartin KaFai Lau threshold = ca->delay_min + hystart_ack_delay(sk);
4616de4a9c4SMartin KaFai Lau
4626de4a9c4SMartin KaFai Lau /* Hystart ack train triggers if we get ack past
4636de4a9c4SMartin KaFai Lau * ca->delay_min/2.
4646de4a9c4SMartin KaFai Lau * Pacing might have delayed packets up to RTT/2
4656de4a9c4SMartin KaFai Lau * during slow start.
4666de4a9c4SMartin KaFai Lau */
4676de4a9c4SMartin KaFai Lau if (sk->sk_pacing_status == SK_PACING_NONE)
4686de4a9c4SMartin KaFai Lau threshold >>= 1;
4696de4a9c4SMartin KaFai Lau
4706de4a9c4SMartin KaFai Lau if ((__s32)(now - ca->round_start) > threshold) {
4716de4a9c4SMartin KaFai Lau ca->found = 1;
4726de4a9c4SMartin KaFai Lau tp->snd_ssthresh = tp->snd_cwnd;
4736de4a9c4SMartin KaFai Lau }
4746de4a9c4SMartin KaFai Lau }
4756de4a9c4SMartin KaFai Lau }
4766de4a9c4SMartin KaFai Lau
4776de4a9c4SMartin KaFai Lau if (hystart_detect & HYSTART_DELAY) {
4786de4a9c4SMartin KaFai Lau /* obtain the minimum delay of more than sampling packets */
4796de4a9c4SMartin KaFai Lau if (ca->curr_rtt > delay)
4806de4a9c4SMartin KaFai Lau ca->curr_rtt = delay;
4817d21d54dSNeal Cardwell if (ca->sample_cnt < HYSTART_MIN_SAMPLES) {
4826de4a9c4SMartin KaFai Lau ca->sample_cnt++;
4836de4a9c4SMartin KaFai Lau } else {
4846de4a9c4SMartin KaFai Lau if (ca->curr_rtt > ca->delay_min +
4856de4a9c4SMartin KaFai Lau HYSTART_DELAY_THRESH(ca->delay_min >> 3)) {
4866de4a9c4SMartin KaFai Lau ca->found = 1;
4876de4a9c4SMartin KaFai Lau tp->snd_ssthresh = tp->snd_cwnd;
4886de4a9c4SMartin KaFai Lau }
4896de4a9c4SMartin KaFai Lau }
4906de4a9c4SMartin KaFai Lau }
4916de4a9c4SMartin KaFai Lau }
4926de4a9c4SMartin KaFai Lau
493*48f5e7d3SSong Liu int bpf_cubic_acked_called = 0;
494*48f5e7d3SSong Liu
BPF_STRUCT_OPS(bpf_cubic_acked,struct sock * sk,const struct ack_sample * sample)49539cd9e0fSMartin KaFai Lau void BPF_STRUCT_OPS(bpf_cubic_acked, struct sock *sk,
4966de4a9c4SMartin KaFai Lau const struct ack_sample *sample)
4976de4a9c4SMartin KaFai Lau {
4986de4a9c4SMartin KaFai Lau const struct tcp_sock *tp = tcp_sk(sk);
4996de4a9c4SMartin KaFai Lau struct bictcp *ca = inet_csk_ca(sk);
5006de4a9c4SMartin KaFai Lau __u32 delay;
5016de4a9c4SMartin KaFai Lau
502*48f5e7d3SSong Liu bpf_cubic_acked_called = 1;
5036de4a9c4SMartin KaFai Lau /* Some calls are for duplicates without timetamps */
5046de4a9c4SMartin KaFai Lau if (sample->rtt_us < 0)
5056de4a9c4SMartin KaFai Lau return;
5066de4a9c4SMartin KaFai Lau
5076de4a9c4SMartin KaFai Lau /* Discard delay samples right after fast recovery */
5086de4a9c4SMartin KaFai Lau if (ca->epoch_start && (__s32)(tcp_jiffies32 - ca->epoch_start) < HZ)
5096de4a9c4SMartin KaFai Lau return;
5106de4a9c4SMartin KaFai Lau
5116de4a9c4SMartin KaFai Lau delay = sample->rtt_us;
5126de4a9c4SMartin KaFai Lau if (delay == 0)
5136de4a9c4SMartin KaFai Lau delay = 1;
5146de4a9c4SMartin KaFai Lau
5156de4a9c4SMartin KaFai Lau /* first time call or link delay decreases */
5166de4a9c4SMartin KaFai Lau if (ca->delay_min == 0 || ca->delay_min > delay)
5176de4a9c4SMartin KaFai Lau ca->delay_min = delay;
5186de4a9c4SMartin KaFai Lau
5196de4a9c4SMartin KaFai Lau /* hystart triggers when cwnd is larger than some threshold */
5206de4a9c4SMartin KaFai Lau if (!ca->found && tcp_in_slow_start(tp) && hystart &&
5216de4a9c4SMartin KaFai Lau tp->snd_cwnd >= hystart_low_window)
5226de4a9c4SMartin KaFai Lau hystart_update(sk, delay);
5236de4a9c4SMartin KaFai Lau }
5246de4a9c4SMartin KaFai Lau
52578e60bbbSMartin KaFai Lau extern __u32 tcp_reno_undo_cwnd(struct sock *sk) __ksym;
52678e60bbbSMartin KaFai Lau
BPF_STRUCT_OPS(bpf_cubic_undo_cwnd,struct sock * sk)52739cd9e0fSMartin KaFai Lau __u32 BPF_STRUCT_OPS(bpf_cubic_undo_cwnd, struct sock *sk)
5286de4a9c4SMartin KaFai Lau {
52978e60bbbSMartin KaFai Lau return tcp_reno_undo_cwnd(sk);
5306de4a9c4SMartin KaFai Lau }
5316de4a9c4SMartin KaFai Lau
5326de4a9c4SMartin KaFai Lau SEC(".struct_ops")
5336de4a9c4SMartin KaFai Lau struct tcp_congestion_ops cubic = {
53439cd9e0fSMartin KaFai Lau .init = (void *)bpf_cubic_init,
53539cd9e0fSMartin KaFai Lau .ssthresh = (void *)bpf_cubic_recalc_ssthresh,
53639cd9e0fSMartin KaFai Lau .cong_avoid = (void *)bpf_cubic_cong_avoid,
53739cd9e0fSMartin KaFai Lau .set_state = (void *)bpf_cubic_state,
53839cd9e0fSMartin KaFai Lau .undo_cwnd = (void *)bpf_cubic_undo_cwnd,
53939cd9e0fSMartin KaFai Lau .cwnd_event = (void *)bpf_cubic_cwnd_event,
54039cd9e0fSMartin KaFai Lau .pkts_acked = (void *)bpf_cubic_acked,
5416de4a9c4SMartin KaFai Lau .name = "bpf_cubic",
5426de4a9c4SMartin KaFai Lau };
543