Lines Matching +full:static +full:- +full:beta
1 // SPDX-License-Identifier: GPL-2.0-only
13 * "while (ca->ack_cnt > delta)" loop is changed to the equivalent
14 * "ca->ack_cnt / delta" operation.
25 static bool before(__u32 seq1, __u32 seq2) in before()
27 return (__s32)(seq1-seq2) < 0; in before()
34 #define BICTCP_BETA_SCALE 1024 /* Scale factor beta calculation
35 * max_cwnd = snd_cwnd * beta
49 static int fast_convergence = 1;
50 static const int beta = 717; /* = 717/1024 (BICTCP_BETA_SCALE) */ variable
51 static int initial_ssthresh;
52 static const int bic_scale = 41;
53 static int tcp_friendliness = 1;
55 static int hystart = 1;
56 static int hystart_detect = HYSTART_ACK_TRAIN | HYSTART_DELAY;
57 static int hystart_low_window = 16;
58 static int hystart_ack_delta_us = 2000;
60 static const __u32 cube_rtt_scale = (bic_scale * 10); /* 1024*c/rtt */
61 static const __u32 beta_scale = 8*(BICTCP_BETA_SCALE+beta) / 3
62 / (BICTCP_BETA_SCALE - beta);
63 /* calculate the "K" for (wmax-cwnd) = c/rtt * K^3
64 * so K = cubic_root( (wmax-cwnd)*rtt/c )
73 * HZ < 1,000,00 (corresponding to 10 nano-second)
77 static const __u64 cube_factor = (__u64)(1ull << (10+3*BICTCP_HZ))
102 static void bictcp_reset(struct bpf_bictcp *ca) in bictcp_reset()
104 ca->cnt = 0; in bictcp_reset()
105 ca->last_max_cwnd = 0; in bictcp_reset()
106 ca->last_cwnd = 0; in bictcp_reset()
107 ca->last_time = 0; in bictcp_reset()
108 ca->bic_origin_point = 0; in bictcp_reset()
109 ca->bic_K = 0; in bictcp_reset()
110 ca->delay_min = 0; in bictcp_reset()
111 ca->epoch_start = 0; in bictcp_reset()
112 ca->ack_cnt = 0; in bictcp_reset()
113 ca->tcp_cwnd = 0; in bictcp_reset()
114 ca->found = 0; in bictcp_reset()
123 static __u64 div64_u64(__u64 dividend, __u64 divisor) in div64_u64()
131 static int fls64(__u64 x) in fls64()
133 int num = BITS_PER_U64 - 1; in fls64()
138 if (!(x & (~0ull << (BITS_PER_U64-32)))) { in fls64()
139 num -= 32; in fls64()
142 if (!(x & (~0ull << (BITS_PER_U64-16)))) { in fls64()
143 num -= 16; in fls64()
146 if (!(x & (~0ull << (BITS_PER_U64-8)))) { in fls64()
147 num -= 8; in fls64()
150 if (!(x & (~0ull << (BITS_PER_U64-4)))) { in fls64()
151 num -= 4; in fls64()
154 if (!(x & (~0ull << (BITS_PER_U64-2)))) { in fls64()
155 num -= 2; in fls64()
158 if (!(x & (~0ull << (BITS_PER_U64-1)))) in fls64()
159 num -= 1; in fls64()
164 static __u32 bictcp_clock_us(const struct sock *sk) in bictcp_clock_us()
166 return tcp_sk(sk)->tcp_mstamp; in bictcp_clock_us()
169 static void bictcp_hystart_reset(struct sock *sk) in bictcp_hystart_reset()
174 ca->round_start = ca->last_ack = bictcp_clock_us(sk); in bictcp_hystart_reset()
175 ca->end_seq = tp->snd_nxt; in bictcp_hystart_reset()
176 ca->curr_rtt = ~0U; in bictcp_hystart_reset()
177 ca->sample_cnt = 0; in bictcp_hystart_reset()
191 tcp_sk(sk)->snd_ssthresh = initial_ssthresh; in BPF_PROG()
202 delta = now - tcp_sk(sk)->lsndtime; in BPF_PROG()
207 if (ca->epoch_start && delta > 0) { in BPF_PROG()
208 ca->epoch_start += delta; in BPF_PROG()
209 if (after(ca->epoch_start, now)) in BPF_PROG()
210 ca->epoch_start = now; in BPF_PROG()
218 * Precomputed then refined by hand - Willy Tarreau
221 * v = cbrt(x << 18) - 1
224 static const __u8 v[] = {
236 * Newton-Raphson iteration.
239 static __u32 cubic_root(__u64 a) in cubic_root()
249 b = ((b * 84) >> 8) - 1; in cubic_root()
259 * Newton-Raphson iteration in cubic_root()
264 x = (2 * x + (__u32)div64_u64(a, (__u64)x * (__u64)(x - 1))); in cubic_root()
272 static void bictcp_update(struct bpf_bictcp *ca, __u32 cwnd, __u32 acked) in bictcp_update()
277 ca->ack_cnt += acked; /* count the number of ACKed packets */ in bictcp_update()
279 if (ca->last_cwnd == cwnd && in bictcp_update()
280 (__s32)(tcp_jiffies32 - ca->last_time) <= HZ / 32) in bictcp_update()
283 /* The CUBIC function can update ca->cnt at most once per jiffy. in bictcp_update()
284 * On all cwnd reduction events, ca->epoch_start is set to 0, in bictcp_update()
285 * which will force a recalculation of ca->cnt. in bictcp_update()
287 if (ca->epoch_start && tcp_jiffies32 == ca->last_time) in bictcp_update()
290 ca->last_cwnd = cwnd; in bictcp_update()
291 ca->last_time = tcp_jiffies32; in bictcp_update()
293 if (ca->epoch_start == 0) { in bictcp_update()
294 ca->epoch_start = tcp_jiffies32; /* record beginning */ in bictcp_update()
295 ca->ack_cnt = acked; /* start counting */ in bictcp_update()
296 ca->tcp_cwnd = cwnd; /* syn with cubic */ in bictcp_update()
298 if (ca->last_max_cwnd <= cwnd) { in bictcp_update()
299 ca->bic_K = 0; in bictcp_update()
300 ca->bic_origin_point = cwnd; in bictcp_update()
303 * (wmax-cwnd) * (srtt>>3 / HZ) / c * 2^(3*bictcp_HZ) in bictcp_update()
305 ca->bic_K = cubic_root(cube_factor in bictcp_update()
306 * (ca->last_max_cwnd - cwnd)); in bictcp_update()
307 ca->bic_origin_point = ca->last_max_cwnd; in bictcp_update()
311 /* cubic function - calc*/ in bictcp_update()
318 * time = (t - K) / 2^bictcp_HZ in bictcp_update()
325 t = (__s32)(tcp_jiffies32 - ca->epoch_start) * USEC_PER_JIFFY; in bictcp_update()
326 t += ca->delay_min; in bictcp_update()
331 if (t < ca->bic_K) /* t - K */ in bictcp_update()
332 offs = ca->bic_K - t; in bictcp_update()
334 offs = t - ca->bic_K; in bictcp_update()
336 /* c/rtt * (t-K)^3 */ in bictcp_update()
338 if (t < ca->bic_K) /* below origin*/ in bictcp_update()
339 bic_target = ca->bic_origin_point - delta; in bictcp_update()
341 bic_target = ca->bic_origin_point + delta; in bictcp_update()
343 /* cubic function - calc bictcp_cnt*/ in bictcp_update()
345 ca->cnt = cwnd / (bic_target - cwnd); in bictcp_update()
347 ca->cnt = 100 * cwnd; /* very small increment*/ in bictcp_update()
354 if (ca->last_max_cwnd == 0 && ca->cnt > 20) in bictcp_update()
355 ca->cnt = 20; /* increase cwnd 5% per RTT */ in bictcp_update()
365 if (ca->ack_cnt > delta && delta) { in bictcp_update()
366 n = ca->ack_cnt / delta; in bictcp_update()
367 ca->ack_cnt -= n * delta; in bictcp_update()
368 ca->tcp_cwnd += n; in bictcp_update()
371 if (ca->tcp_cwnd > cwnd) { /* if bic is slower than tcp */ in bictcp_update()
372 delta = ca->tcp_cwnd - cwnd; in bictcp_update()
374 if (ca->cnt > max_cnt) in bictcp_update()
375 ca->cnt = max_cnt; in bictcp_update()
382 ca->cnt = max(ca->cnt, 2U); in bictcp_update()
395 if (hystart && after(ack, ca->end_seq)) in BPF_PROG()
401 bictcp_update(ca, tp->snd_cwnd, acked); in BPF_PROG()
402 tcp_cong_avoid_ai(tp, ca->cnt, acked); in BPF_PROG()
411 ca->epoch_start = 0; /* end of epoch */ in BPF_PROG()
414 if (tp->snd_cwnd < ca->last_max_cwnd && fast_convergence) in BPF_PROG()
415 ca->last_max_cwnd = (tp->snd_cwnd * (BICTCP_BETA_SCALE + beta)) in BPF_PROG()
418 ca->last_max_cwnd = tp->snd_cwnd; in BPF_PROG()
420 return max((tp->snd_cwnd * beta) / BICTCP_BETA_SCALE, 2U); in BPF_PROG()
436 * slow start we begin with small TSO packets and ca->delay_min would
443 static __u32 hystart_ack_delay(struct sock *sk) in hystart_ack_delay()
447 rate = sk->sk_pacing_rate; in hystart_ack_delay()
454 static void hystart_update(struct sock *sk, __u32 delay) in hystart_update()
463 /* first detection parameter - ack-train detection */ in hystart_update()
464 if ((__s32)(now - ca->last_ack) <= hystart_ack_delta_us) { in hystart_update()
465 ca->last_ack = now; in hystart_update()
467 threshold = ca->delay_min + hystart_ack_delay(sk); in hystart_update()
470 * ca->delay_min/2. in hystart_update()
474 if (sk->sk_pacing_status == SK_PACING_NONE) in hystart_update()
477 if ((__s32)(now - ca->round_start) > threshold) { in hystart_update()
478 ca->found = 1; in hystart_update()
479 tp->snd_ssthresh = tp->snd_cwnd; in hystart_update()
486 if (ca->curr_rtt > delay) in hystart_update()
487 ca->curr_rtt = delay; in hystart_update()
488 if (ca->sample_cnt < HYSTART_MIN_SAMPLES) { in hystart_update()
489 ca->sample_cnt++; in hystart_update()
491 if (ca->curr_rtt > ca->delay_min + in hystart_update()
492 HYSTART_DELAY_THRESH(ca->delay_min >> 3)) { in hystart_update()
493 ca->found = 1; in hystart_update()
494 tp->snd_ssthresh = tp->snd_cwnd; in hystart_update()
511 if (sample->rtt_us < 0) in BPF_PROG()
515 if (ca->epoch_start && (__s32)(tcp_jiffies32 - ca->epoch_start) < HZ) in BPF_PROG()
518 delay = sample->rtt_us; in BPF_PROG()
523 if (ca->delay_min == 0 || ca->delay_min > delay) in BPF_PROG()
524 ca->delay_min = delay; in BPF_PROG()
527 if (!ca->found && tcp_in_slow_start(tp) && hystart && in BPF_PROG()
528 tp->snd_cwnd >= hystart_low_window) in BPF_PROG()