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 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 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) 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 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 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 1726de4a9c4SMartin KaFai Lau /* "struct_ops/" prefix is not a requirement 1736de4a9c4SMartin KaFai Lau * It will be recognized as BPF_PROG_TYPE_STRUCT_OPS 1746de4a9c4SMartin KaFai Lau * as long as it is used in one of the func ptr 1756de4a9c4SMartin KaFai Lau * under SEC(".struct_ops"). 1766de4a9c4SMartin KaFai Lau */ 17739cd9e0fSMartin KaFai Lau SEC("struct_ops/bpf_cubic_init") 17839cd9e0fSMartin KaFai Lau void BPF_PROG(bpf_cubic_init, struct sock *sk) 1796de4a9c4SMartin KaFai Lau { 1806de4a9c4SMartin KaFai Lau struct bictcp *ca = inet_csk_ca(sk); 1816de4a9c4SMartin KaFai Lau 1826de4a9c4SMartin KaFai Lau bictcp_reset(ca); 1836de4a9c4SMartin KaFai Lau 1846de4a9c4SMartin KaFai Lau if (hystart) 1856de4a9c4SMartin KaFai Lau bictcp_hystart_reset(sk); 1866de4a9c4SMartin KaFai Lau 1876de4a9c4SMartin KaFai Lau if (!hystart && initial_ssthresh) 1886de4a9c4SMartin KaFai Lau tcp_sk(sk)->snd_ssthresh = initial_ssthresh; 1896de4a9c4SMartin KaFai Lau } 1906de4a9c4SMartin KaFai Lau 1916de4a9c4SMartin KaFai Lau /* No prefix in SEC will also work. 1926de4a9c4SMartin KaFai Lau * The remaining tcp-cubic functions have an easier way. 1936de4a9c4SMartin KaFai Lau */ 1946de4a9c4SMartin KaFai Lau SEC("no-sec-prefix-bictcp_cwnd_event") 19539cd9e0fSMartin KaFai Lau void BPF_PROG(bpf_cubic_cwnd_event, struct sock *sk, enum tcp_ca_event event) 1966de4a9c4SMartin KaFai Lau { 1976de4a9c4SMartin KaFai Lau if (event == CA_EVENT_TX_START) { 1986de4a9c4SMartin KaFai Lau struct bictcp *ca = inet_csk_ca(sk); 1996de4a9c4SMartin KaFai Lau __u32 now = tcp_jiffies32; 2006de4a9c4SMartin KaFai Lau __s32 delta; 2016de4a9c4SMartin KaFai Lau 2026de4a9c4SMartin KaFai Lau delta = now - tcp_sk(sk)->lsndtime; 2036de4a9c4SMartin KaFai Lau 2046de4a9c4SMartin KaFai Lau /* We were application limited (idle) for a while. 2056de4a9c4SMartin KaFai Lau * Shift epoch_start to keep cwnd growth to cubic curve. 2066de4a9c4SMartin KaFai Lau */ 2076de4a9c4SMartin KaFai Lau if (ca->epoch_start && delta > 0) { 2086de4a9c4SMartin KaFai Lau ca->epoch_start += delta; 2096de4a9c4SMartin KaFai Lau if (after(ca->epoch_start, now)) 2106de4a9c4SMartin KaFai Lau ca->epoch_start = now; 2116de4a9c4SMartin KaFai Lau } 2126de4a9c4SMartin KaFai Lau return; 2136de4a9c4SMartin KaFai Lau } 2146de4a9c4SMartin KaFai Lau } 2156de4a9c4SMartin KaFai Lau 2166de4a9c4SMartin KaFai Lau /* 2176de4a9c4SMartin KaFai Lau * cbrt(x) MSB values for x MSB values in [0..63]. 2186de4a9c4SMartin KaFai Lau * Precomputed then refined by hand - Willy Tarreau 2196de4a9c4SMartin KaFai Lau * 2206de4a9c4SMartin KaFai Lau * For x in [0..63], 2216de4a9c4SMartin KaFai Lau * v = cbrt(x << 18) - 1 2226de4a9c4SMartin KaFai Lau * cbrt(x) = (v[x] + 10) >> 6 2236de4a9c4SMartin KaFai Lau */ 2246de4a9c4SMartin KaFai Lau static const __u8 v[] = { 2256de4a9c4SMartin KaFai Lau /* 0x00 */ 0, 54, 54, 54, 118, 118, 118, 118, 2266de4a9c4SMartin KaFai Lau /* 0x08 */ 123, 129, 134, 138, 143, 147, 151, 156, 2276de4a9c4SMartin KaFai Lau /* 0x10 */ 157, 161, 164, 168, 170, 173, 176, 179, 2286de4a9c4SMartin KaFai Lau /* 0x18 */ 181, 185, 187, 190, 192, 194, 197, 199, 2296de4a9c4SMartin KaFai Lau /* 0x20 */ 200, 202, 204, 206, 209, 211, 213, 215, 2306de4a9c4SMartin KaFai Lau /* 0x28 */ 217, 219, 221, 222, 224, 225, 227, 229, 2316de4a9c4SMartin KaFai Lau /* 0x30 */ 231, 232, 234, 236, 237, 239, 240, 242, 2326de4a9c4SMartin KaFai Lau /* 0x38 */ 244, 245, 246, 248, 250, 251, 252, 254, 2336de4a9c4SMartin KaFai Lau }; 2346de4a9c4SMartin KaFai Lau 2356de4a9c4SMartin KaFai Lau /* calculate the cubic root of x using a table lookup followed by one 2366de4a9c4SMartin KaFai Lau * Newton-Raphson iteration. 2376de4a9c4SMartin KaFai Lau * Avg err ~= 0.195% 2386de4a9c4SMartin KaFai Lau */ 2396de4a9c4SMartin KaFai Lau static __always_inline __u32 cubic_root(__u64 a) 2406de4a9c4SMartin KaFai Lau { 2416de4a9c4SMartin KaFai Lau __u32 x, b, shift; 2426de4a9c4SMartin KaFai Lau 2436de4a9c4SMartin KaFai Lau if (a < 64) { 2446de4a9c4SMartin KaFai Lau /* a in [0..63] */ 2456de4a9c4SMartin KaFai Lau return ((__u32)v[(__u32)a] + 35) >> 6; 2466de4a9c4SMartin KaFai Lau } 2476de4a9c4SMartin KaFai Lau 2486de4a9c4SMartin KaFai Lau b = fls64(a); 2496de4a9c4SMartin KaFai Lau b = ((b * 84) >> 8) - 1; 2506de4a9c4SMartin KaFai Lau shift = (a >> (b * 3)); 2516de4a9c4SMartin KaFai Lau 2526de4a9c4SMartin KaFai Lau /* it is needed for verifier's bound check on v */ 2536de4a9c4SMartin KaFai Lau if (shift >= 64) 2546de4a9c4SMartin KaFai Lau return 0; 2556de4a9c4SMartin KaFai Lau 2566de4a9c4SMartin KaFai Lau x = ((__u32)(((__u32)v[shift] + 10) << b)) >> 6; 2576de4a9c4SMartin KaFai Lau 2586de4a9c4SMartin KaFai Lau /* 2596de4a9c4SMartin KaFai Lau * Newton-Raphson iteration 2606de4a9c4SMartin KaFai Lau * 2 2616de4a9c4SMartin KaFai Lau * x = ( 2 * x + a / x ) / 3 2626de4a9c4SMartin KaFai Lau * k+1 k k 2636de4a9c4SMartin KaFai Lau */ 2646de4a9c4SMartin KaFai Lau x = (2 * x + (__u32)div64_u64(a, (__u64)x * (__u64)(x - 1))); 2656de4a9c4SMartin KaFai Lau x = ((x * 341) >> 10); 2666de4a9c4SMartin KaFai Lau return x; 2676de4a9c4SMartin KaFai Lau } 2686de4a9c4SMartin KaFai Lau 2696de4a9c4SMartin KaFai Lau /* 2706de4a9c4SMartin KaFai Lau * Compute congestion window to use. 2716de4a9c4SMartin KaFai Lau */ 2726de4a9c4SMartin KaFai Lau static __always_inline void bictcp_update(struct bictcp *ca, __u32 cwnd, 2736de4a9c4SMartin KaFai Lau __u32 acked) 2746de4a9c4SMartin KaFai Lau { 2756de4a9c4SMartin KaFai Lau __u32 delta, bic_target, max_cnt; 2766de4a9c4SMartin KaFai Lau __u64 offs, t; 2776de4a9c4SMartin KaFai Lau 2786de4a9c4SMartin KaFai Lau ca->ack_cnt += acked; /* count the number of ACKed packets */ 2796de4a9c4SMartin KaFai Lau 2806de4a9c4SMartin KaFai Lau if (ca->last_cwnd == cwnd && 2816de4a9c4SMartin KaFai Lau (__s32)(tcp_jiffies32 - ca->last_time) <= HZ / 32) 2826de4a9c4SMartin KaFai Lau return; 2836de4a9c4SMartin KaFai Lau 2846de4a9c4SMartin KaFai Lau /* The CUBIC function can update ca->cnt at most once per jiffy. 2856de4a9c4SMartin KaFai Lau * On all cwnd reduction events, ca->epoch_start is set to 0, 2866de4a9c4SMartin KaFai Lau * which will force a recalculation of ca->cnt. 2876de4a9c4SMartin KaFai Lau */ 2886de4a9c4SMartin KaFai Lau if (ca->epoch_start && tcp_jiffies32 == ca->last_time) 2896de4a9c4SMartin KaFai Lau goto tcp_friendliness; 2906de4a9c4SMartin KaFai Lau 2916de4a9c4SMartin KaFai Lau ca->last_cwnd = cwnd; 2926de4a9c4SMartin KaFai Lau ca->last_time = tcp_jiffies32; 2936de4a9c4SMartin KaFai Lau 2946de4a9c4SMartin KaFai Lau if (ca->epoch_start == 0) { 2956de4a9c4SMartin KaFai Lau ca->epoch_start = tcp_jiffies32; /* record beginning */ 2966de4a9c4SMartin KaFai Lau ca->ack_cnt = acked; /* start counting */ 2976de4a9c4SMartin KaFai Lau ca->tcp_cwnd = cwnd; /* syn with cubic */ 2986de4a9c4SMartin KaFai Lau 2996de4a9c4SMartin KaFai Lau if (ca->last_max_cwnd <= cwnd) { 3006de4a9c4SMartin KaFai Lau ca->bic_K = 0; 3016de4a9c4SMartin KaFai Lau ca->bic_origin_point = cwnd; 3026de4a9c4SMartin KaFai Lau } else { 3036de4a9c4SMartin KaFai Lau /* Compute new K based on 3046de4a9c4SMartin KaFai Lau * (wmax-cwnd) * (srtt>>3 / HZ) / c * 2^(3*bictcp_HZ) 3056de4a9c4SMartin KaFai Lau */ 3066de4a9c4SMartin KaFai Lau ca->bic_K = cubic_root(cube_factor 3076de4a9c4SMartin KaFai Lau * (ca->last_max_cwnd - cwnd)); 3086de4a9c4SMartin KaFai Lau ca->bic_origin_point = ca->last_max_cwnd; 3096de4a9c4SMartin KaFai Lau } 3106de4a9c4SMartin KaFai Lau } 3116de4a9c4SMartin KaFai Lau 3126de4a9c4SMartin KaFai Lau /* cubic function - calc*/ 3136de4a9c4SMartin KaFai Lau /* calculate c * time^3 / rtt, 3146de4a9c4SMartin KaFai Lau * while considering overflow in calculation of time^3 3156de4a9c4SMartin KaFai Lau * (so time^3 is done by using 64 bit) 3166de4a9c4SMartin KaFai Lau * and without the support of division of 64bit numbers 3176de4a9c4SMartin KaFai Lau * (so all divisions are done by using 32 bit) 3186de4a9c4SMartin KaFai Lau * also NOTE the unit of those veriables 3196de4a9c4SMartin KaFai Lau * time = (t - K) / 2^bictcp_HZ 3206de4a9c4SMartin KaFai Lau * c = bic_scale >> 10 3216de4a9c4SMartin KaFai Lau * rtt = (srtt >> 3) / HZ 3226de4a9c4SMartin KaFai Lau * !!! The following code does not have overflow problems, 3236de4a9c4SMartin KaFai Lau * if the cwnd < 1 million packets !!! 3246de4a9c4SMartin KaFai Lau */ 3256de4a9c4SMartin KaFai Lau 3266de4a9c4SMartin KaFai Lau t = (__s32)(tcp_jiffies32 - ca->epoch_start) * USEC_PER_JIFFY; 3276de4a9c4SMartin KaFai Lau t += ca->delay_min; 3286de4a9c4SMartin KaFai Lau /* change the unit from usec to bictcp_HZ */ 3296de4a9c4SMartin KaFai Lau t <<= BICTCP_HZ; 3306de4a9c4SMartin KaFai Lau t /= USEC_PER_SEC; 3316de4a9c4SMartin KaFai Lau 3326de4a9c4SMartin KaFai Lau if (t < ca->bic_K) /* t - K */ 3336de4a9c4SMartin KaFai Lau offs = ca->bic_K - t; 3346de4a9c4SMartin KaFai Lau else 3356de4a9c4SMartin KaFai Lau offs = t - ca->bic_K; 3366de4a9c4SMartin KaFai Lau 3376de4a9c4SMartin KaFai Lau /* c/rtt * (t-K)^3 */ 3386de4a9c4SMartin KaFai Lau delta = (cube_rtt_scale * offs * offs * offs) >> (10+3*BICTCP_HZ); 3396de4a9c4SMartin KaFai Lau if (t < ca->bic_K) /* below origin*/ 3406de4a9c4SMartin KaFai Lau bic_target = ca->bic_origin_point - delta; 3416de4a9c4SMartin KaFai Lau else /* above origin*/ 3426de4a9c4SMartin KaFai Lau bic_target = ca->bic_origin_point + delta; 3436de4a9c4SMartin KaFai Lau 3446de4a9c4SMartin KaFai Lau /* cubic function - calc bictcp_cnt*/ 3456de4a9c4SMartin KaFai Lau if (bic_target > cwnd) { 3466de4a9c4SMartin KaFai Lau ca->cnt = cwnd / (bic_target - cwnd); 3476de4a9c4SMartin KaFai Lau } else { 3486de4a9c4SMartin KaFai Lau ca->cnt = 100 * cwnd; /* very small increment*/ 3496de4a9c4SMartin KaFai Lau } 3506de4a9c4SMartin KaFai Lau 3516de4a9c4SMartin KaFai Lau /* 3526de4a9c4SMartin KaFai Lau * The initial growth of cubic function may be too conservative 3536de4a9c4SMartin KaFai Lau * when the available bandwidth is still unknown. 3546de4a9c4SMartin KaFai Lau */ 3556de4a9c4SMartin KaFai Lau if (ca->last_max_cwnd == 0 && ca->cnt > 20) 3566de4a9c4SMartin KaFai Lau ca->cnt = 20; /* increase cwnd 5% per RTT */ 3576de4a9c4SMartin KaFai Lau 3586de4a9c4SMartin KaFai Lau tcp_friendliness: 3596de4a9c4SMartin KaFai Lau /* TCP Friendly */ 3606de4a9c4SMartin KaFai Lau if (tcp_friendliness) { 3616de4a9c4SMartin KaFai Lau __u32 scale = beta_scale; 3626de4a9c4SMartin KaFai Lau __u32 n; 3636de4a9c4SMartin KaFai Lau 3646de4a9c4SMartin KaFai Lau /* update tcp cwnd */ 3656de4a9c4SMartin KaFai Lau delta = (cwnd * scale) >> 3; 3666de4a9c4SMartin KaFai Lau if (ca->ack_cnt > delta && delta) { 3676de4a9c4SMartin KaFai Lau n = ca->ack_cnt / delta; 3686de4a9c4SMartin KaFai Lau ca->ack_cnt -= n * delta; 3696de4a9c4SMartin KaFai Lau ca->tcp_cwnd += n; 3706de4a9c4SMartin KaFai Lau } 3716de4a9c4SMartin KaFai Lau 3726de4a9c4SMartin KaFai Lau if (ca->tcp_cwnd > cwnd) { /* if bic is slower than tcp */ 3736de4a9c4SMartin KaFai Lau delta = ca->tcp_cwnd - cwnd; 3746de4a9c4SMartin KaFai Lau max_cnt = cwnd / delta; 3756de4a9c4SMartin KaFai Lau if (ca->cnt > max_cnt) 3766de4a9c4SMartin KaFai Lau ca->cnt = max_cnt; 3776de4a9c4SMartin KaFai Lau } 3786de4a9c4SMartin KaFai Lau } 3796de4a9c4SMartin KaFai Lau 3806de4a9c4SMartin KaFai Lau /* The maximum rate of cwnd increase CUBIC allows is 1 packet per 3816de4a9c4SMartin KaFai Lau * 2 packets ACKed, meaning cwnd grows at 1.5x per RTT. 3826de4a9c4SMartin KaFai Lau */ 3836de4a9c4SMartin KaFai Lau ca->cnt = max(ca->cnt, 2U); 3846de4a9c4SMartin KaFai Lau } 3856de4a9c4SMartin KaFai Lau 3866de4a9c4SMartin KaFai Lau /* Or simply use the BPF_STRUCT_OPS to avoid the SEC boiler plate. */ 38739cd9e0fSMartin KaFai Lau void BPF_STRUCT_OPS(bpf_cubic_cong_avoid, struct sock *sk, __u32 ack, __u32 acked) 3886de4a9c4SMartin KaFai Lau { 3896de4a9c4SMartin KaFai Lau struct tcp_sock *tp = tcp_sk(sk); 3906de4a9c4SMartin KaFai Lau struct bictcp *ca = inet_csk_ca(sk); 3916de4a9c4SMartin KaFai Lau 3926de4a9c4SMartin KaFai Lau if (!tcp_is_cwnd_limited(sk)) 3936de4a9c4SMartin KaFai Lau return; 3946de4a9c4SMartin KaFai Lau 3956de4a9c4SMartin KaFai Lau if (tcp_in_slow_start(tp)) { 3966de4a9c4SMartin KaFai Lau if (hystart && after(ack, ca->end_seq)) 3976de4a9c4SMartin KaFai Lau bictcp_hystart_reset(sk); 3986de4a9c4SMartin KaFai Lau acked = tcp_slow_start(tp, acked); 3996de4a9c4SMartin KaFai Lau if (!acked) 4006de4a9c4SMartin KaFai Lau return; 4016de4a9c4SMartin KaFai Lau } 4026de4a9c4SMartin KaFai Lau bictcp_update(ca, tp->snd_cwnd, acked); 4036de4a9c4SMartin KaFai Lau tcp_cong_avoid_ai(tp, ca->cnt, acked); 4046de4a9c4SMartin KaFai Lau } 4056de4a9c4SMartin KaFai Lau 40639cd9e0fSMartin KaFai Lau __u32 BPF_STRUCT_OPS(bpf_cubic_recalc_ssthresh, struct sock *sk) 4076de4a9c4SMartin KaFai Lau { 4086de4a9c4SMartin KaFai Lau const struct tcp_sock *tp = tcp_sk(sk); 4096de4a9c4SMartin KaFai Lau struct bictcp *ca = inet_csk_ca(sk); 4106de4a9c4SMartin KaFai Lau 4116de4a9c4SMartin KaFai Lau ca->epoch_start = 0; /* end of epoch */ 4126de4a9c4SMartin KaFai Lau 4136de4a9c4SMartin KaFai Lau /* Wmax and fast convergence */ 4146de4a9c4SMartin KaFai Lau if (tp->snd_cwnd < ca->last_max_cwnd && fast_convergence) 4156de4a9c4SMartin KaFai Lau ca->last_max_cwnd = (tp->snd_cwnd * (BICTCP_BETA_SCALE + beta)) 4166de4a9c4SMartin KaFai Lau / (2 * BICTCP_BETA_SCALE); 4176de4a9c4SMartin KaFai Lau else 4186de4a9c4SMartin KaFai Lau ca->last_max_cwnd = tp->snd_cwnd; 4196de4a9c4SMartin KaFai Lau 4206de4a9c4SMartin KaFai Lau return max((tp->snd_cwnd * beta) / BICTCP_BETA_SCALE, 2U); 4216de4a9c4SMartin KaFai Lau } 4226de4a9c4SMartin KaFai Lau 42339cd9e0fSMartin KaFai Lau void BPF_STRUCT_OPS(bpf_cubic_state, struct sock *sk, __u8 new_state) 4246de4a9c4SMartin KaFai Lau { 4256de4a9c4SMartin KaFai Lau if (new_state == TCP_CA_Loss) { 4266de4a9c4SMartin KaFai Lau bictcp_reset(inet_csk_ca(sk)); 4276de4a9c4SMartin KaFai Lau bictcp_hystart_reset(sk); 4286de4a9c4SMartin KaFai Lau } 4296de4a9c4SMartin KaFai Lau } 4306de4a9c4SMartin KaFai Lau 4316de4a9c4SMartin KaFai Lau #define GSO_MAX_SIZE 65536 4326de4a9c4SMartin KaFai Lau 4336de4a9c4SMartin KaFai Lau /* Account for TSO/GRO delays. 4346de4a9c4SMartin KaFai Lau * Otherwise short RTT flows could get too small ssthresh, since during 4356de4a9c4SMartin KaFai Lau * slow start we begin with small TSO packets and ca->delay_min would 4366de4a9c4SMartin KaFai Lau * not account for long aggregation delay when TSO packets get bigger. 4376de4a9c4SMartin KaFai Lau * Ideally even with a very small RTT we would like to have at least one 4386de4a9c4SMartin KaFai Lau * TSO packet being sent and received by GRO, and another one in qdisc layer. 4396de4a9c4SMartin KaFai Lau * We apply another 100% factor because @rate is doubled at this point. 4406de4a9c4SMartin KaFai Lau * We cap the cushion to 1ms. 4416de4a9c4SMartin KaFai Lau */ 4426de4a9c4SMartin KaFai Lau static __always_inline __u32 hystart_ack_delay(struct sock *sk) 4436de4a9c4SMartin KaFai Lau { 4446de4a9c4SMartin KaFai Lau unsigned long rate; 4456de4a9c4SMartin KaFai Lau 4466de4a9c4SMartin KaFai Lau rate = sk->sk_pacing_rate; 4476de4a9c4SMartin KaFai Lau if (!rate) 4486de4a9c4SMartin KaFai Lau return 0; 4496de4a9c4SMartin KaFai Lau return min((__u64)USEC_PER_MSEC, 4506de4a9c4SMartin KaFai Lau div64_ul((__u64)GSO_MAX_SIZE * 4 * USEC_PER_SEC, rate)); 4516de4a9c4SMartin KaFai Lau } 4526de4a9c4SMartin KaFai Lau 4536de4a9c4SMartin KaFai Lau static __always_inline void hystart_update(struct sock *sk, __u32 delay) 4546de4a9c4SMartin KaFai Lau { 4556de4a9c4SMartin KaFai Lau struct tcp_sock *tp = tcp_sk(sk); 4566de4a9c4SMartin KaFai Lau struct bictcp *ca = inet_csk_ca(sk); 4576de4a9c4SMartin KaFai Lau __u32 threshold; 4586de4a9c4SMartin KaFai Lau 4596de4a9c4SMartin KaFai Lau if (hystart_detect & HYSTART_ACK_TRAIN) { 4606de4a9c4SMartin KaFai Lau __u32 now = bictcp_clock_us(sk); 4616de4a9c4SMartin KaFai Lau 4626de4a9c4SMartin KaFai Lau /* first detection parameter - ack-train detection */ 4636de4a9c4SMartin KaFai Lau if ((__s32)(now - ca->last_ack) <= hystart_ack_delta_us) { 4646de4a9c4SMartin KaFai Lau ca->last_ack = now; 4656de4a9c4SMartin KaFai Lau 4666de4a9c4SMartin KaFai Lau threshold = ca->delay_min + hystart_ack_delay(sk); 4676de4a9c4SMartin KaFai Lau 4686de4a9c4SMartin KaFai Lau /* Hystart ack train triggers if we get ack past 4696de4a9c4SMartin KaFai Lau * ca->delay_min/2. 4706de4a9c4SMartin KaFai Lau * Pacing might have delayed packets up to RTT/2 4716de4a9c4SMartin KaFai Lau * during slow start. 4726de4a9c4SMartin KaFai Lau */ 4736de4a9c4SMartin KaFai Lau if (sk->sk_pacing_status == SK_PACING_NONE) 4746de4a9c4SMartin KaFai Lau threshold >>= 1; 4756de4a9c4SMartin KaFai Lau 4766de4a9c4SMartin KaFai Lau if ((__s32)(now - ca->round_start) > threshold) { 4776de4a9c4SMartin KaFai Lau ca->found = 1; 4786de4a9c4SMartin KaFai Lau tp->snd_ssthresh = tp->snd_cwnd; 4796de4a9c4SMartin KaFai Lau } 4806de4a9c4SMartin KaFai Lau } 4816de4a9c4SMartin KaFai Lau } 4826de4a9c4SMartin KaFai Lau 4836de4a9c4SMartin KaFai Lau if (hystart_detect & HYSTART_DELAY) { 4846de4a9c4SMartin KaFai Lau /* obtain the minimum delay of more than sampling packets */ 4856de4a9c4SMartin KaFai Lau if (ca->curr_rtt > delay) 4866de4a9c4SMartin KaFai Lau ca->curr_rtt = delay; 4877d21d54dSNeal Cardwell if (ca->sample_cnt < HYSTART_MIN_SAMPLES) { 4886de4a9c4SMartin KaFai Lau ca->sample_cnt++; 4896de4a9c4SMartin KaFai Lau } else { 4906de4a9c4SMartin KaFai Lau if (ca->curr_rtt > ca->delay_min + 4916de4a9c4SMartin KaFai Lau HYSTART_DELAY_THRESH(ca->delay_min >> 3)) { 4926de4a9c4SMartin KaFai Lau ca->found = 1; 4936de4a9c4SMartin KaFai Lau tp->snd_ssthresh = tp->snd_cwnd; 4946de4a9c4SMartin KaFai Lau } 4956de4a9c4SMartin KaFai Lau } 4966de4a9c4SMartin KaFai Lau } 4976de4a9c4SMartin KaFai Lau } 4986de4a9c4SMartin KaFai Lau 49939cd9e0fSMartin KaFai Lau void BPF_STRUCT_OPS(bpf_cubic_acked, struct sock *sk, 5006de4a9c4SMartin KaFai Lau const struct ack_sample *sample) 5016de4a9c4SMartin KaFai Lau { 5026de4a9c4SMartin KaFai Lau const struct tcp_sock *tp = tcp_sk(sk); 5036de4a9c4SMartin KaFai Lau struct bictcp *ca = inet_csk_ca(sk); 5046de4a9c4SMartin KaFai Lau __u32 delay; 5056de4a9c4SMartin KaFai Lau 5066de4a9c4SMartin KaFai Lau /* Some calls are for duplicates without timetamps */ 5076de4a9c4SMartin KaFai Lau if (sample->rtt_us < 0) 5086de4a9c4SMartin KaFai Lau return; 5096de4a9c4SMartin KaFai Lau 5106de4a9c4SMartin KaFai Lau /* Discard delay samples right after fast recovery */ 5116de4a9c4SMartin KaFai Lau if (ca->epoch_start && (__s32)(tcp_jiffies32 - ca->epoch_start) < HZ) 5126de4a9c4SMartin KaFai Lau return; 5136de4a9c4SMartin KaFai Lau 5146de4a9c4SMartin KaFai Lau delay = sample->rtt_us; 5156de4a9c4SMartin KaFai Lau if (delay == 0) 5166de4a9c4SMartin KaFai Lau delay = 1; 5176de4a9c4SMartin KaFai Lau 5186de4a9c4SMartin KaFai Lau /* first time call or link delay decreases */ 5196de4a9c4SMartin KaFai Lau if (ca->delay_min == 0 || ca->delay_min > delay) 5206de4a9c4SMartin KaFai Lau ca->delay_min = delay; 5216de4a9c4SMartin KaFai Lau 5226de4a9c4SMartin KaFai Lau /* hystart triggers when cwnd is larger than some threshold */ 5236de4a9c4SMartin KaFai Lau if (!ca->found && tcp_in_slow_start(tp) && hystart && 5246de4a9c4SMartin KaFai Lau tp->snd_cwnd >= hystart_low_window) 5256de4a9c4SMartin KaFai Lau hystart_update(sk, delay); 5266de4a9c4SMartin KaFai Lau } 5276de4a9c4SMartin KaFai Lau 528*78e60bbbSMartin KaFai Lau extern __u32 tcp_reno_undo_cwnd(struct sock *sk) __ksym; 529*78e60bbbSMartin KaFai Lau 53039cd9e0fSMartin KaFai Lau __u32 BPF_STRUCT_OPS(bpf_cubic_undo_cwnd, struct sock *sk) 5316de4a9c4SMartin KaFai Lau { 532*78e60bbbSMartin KaFai Lau return tcp_reno_undo_cwnd(sk); 5336de4a9c4SMartin KaFai Lau } 5346de4a9c4SMartin KaFai Lau 5356de4a9c4SMartin KaFai Lau SEC(".struct_ops") 5366de4a9c4SMartin KaFai Lau struct tcp_congestion_ops cubic = { 53739cd9e0fSMartin KaFai Lau .init = (void *)bpf_cubic_init, 53839cd9e0fSMartin KaFai Lau .ssthresh = (void *)bpf_cubic_recalc_ssthresh, 53939cd9e0fSMartin KaFai Lau .cong_avoid = (void *)bpf_cubic_cong_avoid, 54039cd9e0fSMartin KaFai Lau .set_state = (void *)bpf_cubic_state, 54139cd9e0fSMartin KaFai Lau .undo_cwnd = (void *)bpf_cubic_undo_cwnd, 54239cd9e0fSMartin KaFai Lau .cwnd_event = (void *)bpf_cubic_cwnd_event, 54339cd9e0fSMartin KaFai Lau .pkts_acked = (void *)bpf_cubic_acked, 5446de4a9c4SMartin KaFai Lau .name = "bpf_cubic", 5456de4a9c4SMartin KaFai Lau }; 546