109c434b8SThomas Gleixner // SPDX-License-Identifier: GPL-2.0-only
2a628d29bSJohn Heffner /*
3a628d29bSJohn Heffner * Sally Floyd's High Speed TCP (RFC 3649) congestion control
4a628d29bSJohn Heffner *
57a6498ebSAlexander A. Klimov * See https://www.icir.org/floyd/hstcp.html
6a628d29bSJohn Heffner *
7a628d29bSJohn Heffner * John Heffner <jheffner@psc.edu>
8a628d29bSJohn Heffner */
9a628d29bSJohn Heffner
10a628d29bSJohn Heffner #include <linux/module.h>
11a628d29bSJohn Heffner #include <net/tcp.h>
12a628d29bSJohn Heffner
13a628d29bSJohn Heffner /* From AIMD tables from RFC 3649 appendix B,
14a628d29bSJohn Heffner * with fixed-point MD scaled <<8.
15a628d29bSJohn Heffner */
16a628d29bSJohn Heffner static const struct hstcp_aimd_val {
17a628d29bSJohn Heffner unsigned int cwnd;
18a628d29bSJohn Heffner unsigned int md;
19a628d29bSJohn Heffner } hstcp_aimd_vals[] = {
20a628d29bSJohn Heffner { 38, 128, /* 0.50 */ },
21a628d29bSJohn Heffner { 118, 112, /* 0.44 */ },
22a628d29bSJohn Heffner { 221, 104, /* 0.41 */ },
23a628d29bSJohn Heffner { 347, 98, /* 0.38 */ },
24a628d29bSJohn Heffner { 495, 93, /* 0.37 */ },
25a628d29bSJohn Heffner { 663, 89, /* 0.35 */ },
26a628d29bSJohn Heffner { 851, 86, /* 0.34 */ },
27a628d29bSJohn Heffner { 1058, 83, /* 0.33 */ },
28a628d29bSJohn Heffner { 1284, 81, /* 0.32 */ },
29a628d29bSJohn Heffner { 1529, 78, /* 0.31 */ },
30a628d29bSJohn Heffner { 1793, 76, /* 0.30 */ },
31a628d29bSJohn Heffner { 2076, 74, /* 0.29 */ },
32a628d29bSJohn Heffner { 2378, 72, /* 0.28 */ },
33a628d29bSJohn Heffner { 2699, 71, /* 0.28 */ },
34a628d29bSJohn Heffner { 3039, 69, /* 0.27 */ },
35a628d29bSJohn Heffner { 3399, 68, /* 0.27 */ },
36a628d29bSJohn Heffner { 3778, 66, /* 0.26 */ },
37a628d29bSJohn Heffner { 4177, 65, /* 0.26 */ },
38a628d29bSJohn Heffner { 4596, 64, /* 0.25 */ },
39a628d29bSJohn Heffner { 5036, 62, /* 0.25 */ },
40a628d29bSJohn Heffner { 5497, 61, /* 0.24 */ },
41a628d29bSJohn Heffner { 5979, 60, /* 0.24 */ },
42a628d29bSJohn Heffner { 6483, 59, /* 0.23 */ },
43a628d29bSJohn Heffner { 7009, 58, /* 0.23 */ },
44a628d29bSJohn Heffner { 7558, 57, /* 0.22 */ },
45a628d29bSJohn Heffner { 8130, 56, /* 0.22 */ },
46a628d29bSJohn Heffner { 8726, 55, /* 0.22 */ },
47a628d29bSJohn Heffner { 9346, 54, /* 0.21 */ },
48a628d29bSJohn Heffner { 9991, 53, /* 0.21 */ },
49a628d29bSJohn Heffner { 10661, 52, /* 0.21 */ },
50a628d29bSJohn Heffner { 11358, 52, /* 0.20 */ },
51a628d29bSJohn Heffner { 12082, 51, /* 0.20 */ },
52a628d29bSJohn Heffner { 12834, 50, /* 0.20 */ },
53a628d29bSJohn Heffner { 13614, 49, /* 0.19 */ },
54a628d29bSJohn Heffner { 14424, 48, /* 0.19 */ },
55a628d29bSJohn Heffner { 15265, 48, /* 0.19 */ },
56a628d29bSJohn Heffner { 16137, 47, /* 0.19 */ },
57a628d29bSJohn Heffner { 17042, 46, /* 0.18 */ },
58a628d29bSJohn Heffner { 17981, 45, /* 0.18 */ },
59a628d29bSJohn Heffner { 18955, 45, /* 0.18 */ },
60a628d29bSJohn Heffner { 19965, 44, /* 0.17 */ },
61a628d29bSJohn Heffner { 21013, 43, /* 0.17 */ },
62a628d29bSJohn Heffner { 22101, 43, /* 0.17 */ },
63a628d29bSJohn Heffner { 23230, 42, /* 0.17 */ },
64a628d29bSJohn Heffner { 24402, 41, /* 0.16 */ },
65a628d29bSJohn Heffner { 25618, 41, /* 0.16 */ },
66a628d29bSJohn Heffner { 26881, 40, /* 0.16 */ },
67a628d29bSJohn Heffner { 28193, 39, /* 0.16 */ },
68a628d29bSJohn Heffner { 29557, 39, /* 0.15 */ },
69a628d29bSJohn Heffner { 30975, 38, /* 0.15 */ },
70a628d29bSJohn Heffner { 32450, 38, /* 0.15 */ },
71a628d29bSJohn Heffner { 33986, 37, /* 0.15 */ },
72a628d29bSJohn Heffner { 35586, 36, /* 0.14 */ },
73a628d29bSJohn Heffner { 37253, 36, /* 0.14 */ },
74a628d29bSJohn Heffner { 38992, 35, /* 0.14 */ },
75a628d29bSJohn Heffner { 40808, 35, /* 0.14 */ },
76a628d29bSJohn Heffner { 42707, 34, /* 0.13 */ },
77a628d29bSJohn Heffner { 44694, 33, /* 0.13 */ },
78a628d29bSJohn Heffner { 46776, 33, /* 0.13 */ },
79a628d29bSJohn Heffner { 48961, 32, /* 0.13 */ },
80a628d29bSJohn Heffner { 51258, 32, /* 0.13 */ },
81a628d29bSJohn Heffner { 53677, 31, /* 0.12 */ },
82a628d29bSJohn Heffner { 56230, 30, /* 0.12 */ },
83a628d29bSJohn Heffner { 58932, 30, /* 0.12 */ },
84a628d29bSJohn Heffner { 61799, 29, /* 0.12 */ },
85a628d29bSJohn Heffner { 64851, 28, /* 0.11 */ },
86a628d29bSJohn Heffner { 68113, 28, /* 0.11 */ },
87a628d29bSJohn Heffner { 71617, 27, /* 0.11 */ },
88a628d29bSJohn Heffner { 75401, 26, /* 0.10 */ },
89a628d29bSJohn Heffner { 79517, 26, /* 0.10 */ },
90a628d29bSJohn Heffner { 84035, 25, /* 0.10 */ },
91a628d29bSJohn Heffner { 89053, 24, /* 0.10 */ },
92a628d29bSJohn Heffner };
93a628d29bSJohn Heffner
94a628d29bSJohn Heffner #define HSTCP_AIMD_MAX ARRAY_SIZE(hstcp_aimd_vals)
95a628d29bSJohn Heffner
96a628d29bSJohn Heffner struct hstcp {
97a628d29bSJohn Heffner u32 ai;
98a628d29bSJohn Heffner };
99a628d29bSJohn Heffner
hstcp_init(struct sock * sk)1006687e988SArnaldo Carvalho de Melo static void hstcp_init(struct sock *sk)
101a628d29bSJohn Heffner {
1026687e988SArnaldo Carvalho de Melo struct tcp_sock *tp = tcp_sk(sk);
1036687e988SArnaldo Carvalho de Melo struct hstcp *ca = inet_csk_ca(sk);
104a628d29bSJohn Heffner
105a628d29bSJohn Heffner ca->ai = 0;
106a628d29bSJohn Heffner
107a628d29bSJohn Heffner /* Ensure the MD arithmetic works. This is somewhat pedantic,
108a628d29bSJohn Heffner * since I don't think we will see a cwnd this large. :) */
109a628d29bSJohn Heffner tp->snd_cwnd_clamp = min_t(u32, tp->snd_cwnd_clamp, 0xffffffff/128);
110a628d29bSJohn Heffner }
111a628d29bSJohn Heffner
hstcp_cong_avoid(struct sock * sk,u32 ack,u32 acked)11224901551SEric Dumazet static void hstcp_cong_avoid(struct sock *sk, u32 ack, u32 acked)
113a628d29bSJohn Heffner {
1146687e988SArnaldo Carvalho de Melo struct tcp_sock *tp = tcp_sk(sk);
1156687e988SArnaldo Carvalho de Melo struct hstcp *ca = inet_csk_ca(sk);
116a628d29bSJohn Heffner
11724901551SEric Dumazet if (!tcp_is_cwnd_limited(sk))
118a628d29bSJohn Heffner return;
119a628d29bSJohn Heffner
120071d5080SYuchung Cheng if (tcp_in_slow_start(tp))
1219f9843a7SYuchung Cheng tcp_slow_start(tp, acked);
12203fba047SIlpo Järvinen else {
1236150c22eSXiaoliang (David) Wei /* Update AIMD parameters.
1246150c22eSXiaoliang (David) Wei *
1256150c22eSXiaoliang (David) Wei * We want to guarantee that:
1266150c22eSXiaoliang (David) Wei * hstcp_aimd_vals[ca->ai-1].cwnd <
1276150c22eSXiaoliang (David) Wei * snd_cwnd <=
1286150c22eSXiaoliang (David) Wei * hstcp_aimd_vals[ca->ai].cwnd
1296150c22eSXiaoliang (David) Wei */
130*40570375SEric Dumazet if (tcp_snd_cwnd(tp) > hstcp_aimd_vals[ca->ai].cwnd) {
131*40570375SEric Dumazet while (tcp_snd_cwnd(tp) > hstcp_aimd_vals[ca->ai].cwnd &&
1324a1ff6e2SPatrick McHardy ca->ai < HSTCP_AIMD_MAX - 1)
133a628d29bSJohn Heffner ca->ai++;
134*40570375SEric Dumazet } else if (ca->ai && tcp_snd_cwnd(tp) <= hstcp_aimd_vals[ca->ai-1].cwnd) {
135*40570375SEric Dumazet while (ca->ai && tcp_snd_cwnd(tp) <= hstcp_aimd_vals[ca->ai-1].cwnd)
136a628d29bSJohn Heffner ca->ai--;
137a628d29bSJohn Heffner }
138a628d29bSJohn Heffner
139a628d29bSJohn Heffner /* Do additive increase */
140*40570375SEric Dumazet if (tcp_snd_cwnd(tp) < tp->snd_cwnd_clamp) {
141fb80a6e1SStephen Hemminger /* cwnd = cwnd + a(w) / cwnd */
142fb80a6e1SStephen Hemminger tp->snd_cwnd_cnt += ca->ai + 1;
143*40570375SEric Dumazet if (tp->snd_cwnd_cnt >= tcp_snd_cwnd(tp)) {
144*40570375SEric Dumazet tp->snd_cwnd_cnt -= tcp_snd_cwnd(tp);
145*40570375SEric Dumazet tcp_snd_cwnd_set(tp, tcp_snd_cwnd(tp) + 1);
146a628d29bSJohn Heffner }
147a628d29bSJohn Heffner }
148a628d29bSJohn Heffner }
149a628d29bSJohn Heffner }
150a628d29bSJohn Heffner
hstcp_ssthresh(struct sock * sk)1516687e988SArnaldo Carvalho de Melo static u32 hstcp_ssthresh(struct sock *sk)
152a628d29bSJohn Heffner {
1536687e988SArnaldo Carvalho de Melo const struct tcp_sock *tp = tcp_sk(sk);
15485f7e750SFlorian Westphal struct hstcp *ca = inet_csk_ca(sk);
155a628d29bSJohn Heffner
156a628d29bSJohn Heffner /* Do multiplicative decrease */
157*40570375SEric Dumazet return max(tcp_snd_cwnd(tp) - ((tcp_snd_cwnd(tp) * hstcp_aimd_vals[ca->ai].md) >> 8), 2U);
158a628d29bSJohn Heffner }
159a628d29bSJohn Heffner
160a252bebeSStephen Hemminger static struct tcp_congestion_ops tcp_highspeed __read_mostly = {
161a628d29bSJohn Heffner .init = hstcp_init,
162a628d29bSJohn Heffner .ssthresh = hstcp_ssthresh,
163f1722a1bSYuchung Cheng .undo_cwnd = tcp_reno_undo_cwnd,
164a628d29bSJohn Heffner .cong_avoid = hstcp_cong_avoid,
165a628d29bSJohn Heffner
166a628d29bSJohn Heffner .owner = THIS_MODULE,
167a628d29bSJohn Heffner .name = "highspeed"
168a628d29bSJohn Heffner };
169a628d29bSJohn Heffner
hstcp_register(void)170a628d29bSJohn Heffner static int __init hstcp_register(void)
171a628d29bSJohn Heffner {
17274975d40SAlexey Dobriyan BUILD_BUG_ON(sizeof(struct hstcp) > ICSK_CA_PRIV_SIZE);
173a628d29bSJohn Heffner return tcp_register_congestion_control(&tcp_highspeed);
174a628d29bSJohn Heffner }
175a628d29bSJohn Heffner
hstcp_unregister(void)176a628d29bSJohn Heffner static void __exit hstcp_unregister(void)
177a628d29bSJohn Heffner {
178a628d29bSJohn Heffner tcp_unregister_congestion_control(&tcp_highspeed);
179a628d29bSJohn Heffner }
180a628d29bSJohn Heffner
181a628d29bSJohn Heffner module_init(hstcp_register);
182a628d29bSJohn Heffner module_exit(hstcp_unregister);
183a628d29bSJohn Heffner
184a628d29bSJohn Heffner MODULE_AUTHOR("John Heffner");
185a628d29bSJohn Heffner MODULE_LICENSE("GPL");
186a628d29bSJohn Heffner MODULE_DESCRIPTION("High Speed TCP");
187