GNU Linux-libre 4.19.211-gnu1
[releases.git] / net / ipv4 / tcp_dctcp.c
1 /* DataCenter TCP (DCTCP) congestion control.
2  *
3  * http://simula.stanford.edu/~alizade/Site/DCTCP.html
4  *
5  * This is an implementation of DCTCP over Reno, an enhancement to the
6  * TCP congestion control algorithm designed for data centers. DCTCP
7  * leverages Explicit Congestion Notification (ECN) in the network to
8  * provide multi-bit feedback to the end hosts. DCTCP's goal is to meet
9  * the following three data center transport requirements:
10  *
11  *  - High burst tolerance (incast due to partition/aggregate)
12  *  - Low latency (short flows, queries)
13  *  - High throughput (continuous data updates, large file transfers)
14  *    with commodity shallow buffered switches
15  *
16  * The algorithm is described in detail in the following two papers:
17  *
18  * 1) Mohammad Alizadeh, Albert Greenberg, David A. Maltz, Jitendra Padhye,
19  *    Parveen Patel, Balaji Prabhakar, Sudipta Sengupta, and Murari Sridharan:
20  *      "Data Center TCP (DCTCP)", Data Center Networks session
21  *      Proc. ACM SIGCOMM, New Delhi, 2010.
22  *   http://simula.stanford.edu/~alizade/Site/DCTCP_files/dctcp-final.pdf
23  *
24  * 2) Mohammad Alizadeh, Adel Javanmard, and Balaji Prabhakar:
25  *      "Analysis of DCTCP: Stability, Convergence, and Fairness"
26  *      Proc. ACM SIGMETRICS, San Jose, 2011.
27  *   http://simula.stanford.edu/~alizade/Site/DCTCP_files/dctcp_analysis-full.pdf
28  *
29  * Initial prototype from Abdul Kabbani, Masato Yasuda and Mohammad Alizadeh.
30  *
31  * Authors:
32  *
33  *      Daniel Borkmann <dborkman@redhat.com>
34  *      Florian Westphal <fw@strlen.de>
35  *      Glenn Judd <glenn.judd@morganstanley.com>
36  *
37  * This program is free software; you can redistribute it and/or modify
38  * it under the terms of the GNU General Public License as published by
39  * the Free Software Foundation; either version 2 of the License, or (at
40  * your option) any later version.
41  */
42
43 #include <linux/module.h>
44 #include <linux/mm.h>
45 #include <net/tcp.h>
46 #include <linux/inet_diag.h>
47
48 #define DCTCP_MAX_ALPHA 1024U
49
50 struct dctcp {
51         u32 acked_bytes_ecn;
52         u32 acked_bytes_total;
53         u32 prior_snd_una;
54         u32 prior_rcv_nxt;
55         u32 dctcp_alpha;
56         u32 next_seq;
57         u32 ce_state;
58         u32 loss_cwnd;
59 };
60
61 static unsigned int dctcp_shift_g __read_mostly = 4; /* g = 1/2^4 */
62 module_param(dctcp_shift_g, uint, 0644);
63 MODULE_PARM_DESC(dctcp_shift_g, "parameter g for updating dctcp_alpha");
64
65 static unsigned int dctcp_alpha_on_init __read_mostly = DCTCP_MAX_ALPHA;
66 module_param(dctcp_alpha_on_init, uint, 0644);
67 MODULE_PARM_DESC(dctcp_alpha_on_init, "parameter for initial alpha value");
68
69 static struct tcp_congestion_ops dctcp_reno;
70
71 static void dctcp_reset(const struct tcp_sock *tp, struct dctcp *ca)
72 {
73         ca->next_seq = tp->snd_nxt;
74
75         ca->acked_bytes_ecn = 0;
76         ca->acked_bytes_total = 0;
77 }
78
79 static void dctcp_init(struct sock *sk)
80 {
81         const struct tcp_sock *tp = tcp_sk(sk);
82
83         if ((tp->ecn_flags & TCP_ECN_OK) ||
84             (sk->sk_state == TCP_LISTEN ||
85              sk->sk_state == TCP_CLOSE)) {
86                 struct dctcp *ca = inet_csk_ca(sk);
87
88                 ca->prior_snd_una = tp->snd_una;
89                 ca->prior_rcv_nxt = tp->rcv_nxt;
90
91                 ca->dctcp_alpha = min(dctcp_alpha_on_init, DCTCP_MAX_ALPHA);
92
93                 ca->loss_cwnd = 0;
94                 ca->ce_state = 0;
95
96                 dctcp_reset(tp, ca);
97                 return;
98         }
99
100         /* No ECN support? Fall back to Reno. Also need to clear
101          * ECT from sk since it is set during 3WHS for DCTCP.
102          */
103         inet_csk(sk)->icsk_ca_ops = &dctcp_reno;
104         INET_ECN_dontxmit(sk);
105 }
106
107 static u32 dctcp_ssthresh(struct sock *sk)
108 {
109         struct dctcp *ca = inet_csk_ca(sk);
110         struct tcp_sock *tp = tcp_sk(sk);
111
112         ca->loss_cwnd = tp->snd_cwnd;
113         return max(tp->snd_cwnd - ((tp->snd_cwnd * ca->dctcp_alpha) >> 11U), 2U);
114 }
115
116 /* Minimal DCTP CE state machine:
117  *
118  * S:   0 <- last pkt was non-CE
119  *      1 <- last pkt was CE
120  */
121
122 static void dctcp_ce_state_0_to_1(struct sock *sk)
123 {
124         struct dctcp *ca = inet_csk_ca(sk);
125         struct tcp_sock *tp = tcp_sk(sk);
126
127         if (!ca->ce_state) {
128                 /* State has changed from CE=0 to CE=1, force an immediate
129                  * ACK to reflect the new CE state. If an ACK was delayed,
130                  * send that first to reflect the prior CE state.
131                  */
132                 if (inet_csk(sk)->icsk_ack.pending & ICSK_ACK_TIMER)
133                         __tcp_send_ack(sk, ca->prior_rcv_nxt);
134                 inet_csk(sk)->icsk_ack.pending |= ICSK_ACK_NOW;
135         }
136
137         ca->prior_rcv_nxt = tp->rcv_nxt;
138         ca->ce_state = 1;
139
140         tp->ecn_flags |= TCP_ECN_DEMAND_CWR;
141 }
142
143 static void dctcp_ce_state_1_to_0(struct sock *sk)
144 {
145         struct dctcp *ca = inet_csk_ca(sk);
146         struct tcp_sock *tp = tcp_sk(sk);
147
148         if (ca->ce_state) {
149                 /* State has changed from CE=1 to CE=0, force an immediate
150                  * ACK to reflect the new CE state. If an ACK was delayed,
151                  * send that first to reflect the prior CE state.
152                  */
153                 if (inet_csk(sk)->icsk_ack.pending & ICSK_ACK_TIMER)
154                         __tcp_send_ack(sk, ca->prior_rcv_nxt);
155                 inet_csk(sk)->icsk_ack.pending |= ICSK_ACK_NOW;
156         }
157
158         ca->prior_rcv_nxt = tp->rcv_nxt;
159         ca->ce_state = 0;
160
161         tp->ecn_flags &= ~TCP_ECN_DEMAND_CWR;
162 }
163
164 static void dctcp_update_alpha(struct sock *sk, u32 flags)
165 {
166         const struct tcp_sock *tp = tcp_sk(sk);
167         struct dctcp *ca = inet_csk_ca(sk);
168         u32 acked_bytes = tp->snd_una - ca->prior_snd_una;
169
170         /* If ack did not advance snd_una, count dupack as MSS size.
171          * If ack did update window, do not count it at all.
172          */
173         if (acked_bytes == 0 && !(flags & CA_ACK_WIN_UPDATE))
174                 acked_bytes = inet_csk(sk)->icsk_ack.rcv_mss;
175         if (acked_bytes) {
176                 ca->acked_bytes_total += acked_bytes;
177                 ca->prior_snd_una = tp->snd_una;
178
179                 if (flags & CA_ACK_ECE)
180                         ca->acked_bytes_ecn += acked_bytes;
181         }
182
183         /* Expired RTT */
184         if (!before(tp->snd_una, ca->next_seq)) {
185                 u64 bytes_ecn = ca->acked_bytes_ecn;
186                 u32 alpha = ca->dctcp_alpha;
187
188                 /* alpha = (1 - g) * alpha + g * F */
189
190                 alpha -= min_not_zero(alpha, alpha >> dctcp_shift_g);
191                 if (bytes_ecn) {
192                         /* If dctcp_shift_g == 1, a 32bit value would overflow
193                          * after 8 Mbytes.
194                          */
195                         bytes_ecn <<= (10 - dctcp_shift_g);
196                         do_div(bytes_ecn, max(1U, ca->acked_bytes_total));
197
198                         alpha = min(alpha + (u32)bytes_ecn, DCTCP_MAX_ALPHA);
199                 }
200                 /* dctcp_alpha can be read from dctcp_get_info() without
201                  * synchro, so we ask compiler to not use dctcp_alpha
202                  * as a temporary variable in prior operations.
203                  */
204                 WRITE_ONCE(ca->dctcp_alpha, alpha);
205                 dctcp_reset(tp, ca);
206         }
207 }
208
209 static void dctcp_react_to_loss(struct sock *sk)
210 {
211         struct dctcp *ca = inet_csk_ca(sk);
212         struct tcp_sock *tp = tcp_sk(sk);
213
214         ca->loss_cwnd = tp->snd_cwnd;
215         tp->snd_ssthresh = max(tp->snd_cwnd >> 1U, 2U);
216 }
217
218 static void dctcp_state(struct sock *sk, u8 new_state)
219 {
220         if (new_state == TCP_CA_Recovery &&
221             new_state != inet_csk(sk)->icsk_ca_state)
222                 dctcp_react_to_loss(sk);
223         /* We handle RTO in dctcp_cwnd_event to ensure that we perform only
224          * one loss-adjustment per RTT.
225          */
226 }
227
228 static void dctcp_cwnd_event(struct sock *sk, enum tcp_ca_event ev)
229 {
230         switch (ev) {
231         case CA_EVENT_ECN_IS_CE:
232                 dctcp_ce_state_0_to_1(sk);
233                 break;
234         case CA_EVENT_ECN_NO_CE:
235                 dctcp_ce_state_1_to_0(sk);
236                 break;
237         case CA_EVENT_LOSS:
238                 dctcp_react_to_loss(sk);
239                 break;
240         default:
241                 /* Don't care for the rest. */
242                 break;
243         }
244 }
245
246 static size_t dctcp_get_info(struct sock *sk, u32 ext, int *attr,
247                              union tcp_cc_info *info)
248 {
249         const struct dctcp *ca = inet_csk_ca(sk);
250
251         /* Fill it also in case of VEGASINFO due to req struct limits.
252          * We can still correctly retrieve it later.
253          */
254         if (ext & (1 << (INET_DIAG_DCTCPINFO - 1)) ||
255             ext & (1 << (INET_DIAG_VEGASINFO - 1))) {
256                 memset(&info->dctcp, 0, sizeof(info->dctcp));
257                 if (inet_csk(sk)->icsk_ca_ops != &dctcp_reno) {
258                         info->dctcp.dctcp_enabled = 1;
259                         info->dctcp.dctcp_ce_state = (u16) ca->ce_state;
260                         info->dctcp.dctcp_alpha = ca->dctcp_alpha;
261                         info->dctcp.dctcp_ab_ecn = ca->acked_bytes_ecn;
262                         info->dctcp.dctcp_ab_tot = ca->acked_bytes_total;
263                 }
264
265                 *attr = INET_DIAG_DCTCPINFO;
266                 return sizeof(info->dctcp);
267         }
268         return 0;
269 }
270
271 static u32 dctcp_cwnd_undo(struct sock *sk)
272 {
273         const struct dctcp *ca = inet_csk_ca(sk);
274
275         return max(tcp_sk(sk)->snd_cwnd, ca->loss_cwnd);
276 }
277
278 static struct tcp_congestion_ops dctcp __read_mostly = {
279         .init           = dctcp_init,
280         .in_ack_event   = dctcp_update_alpha,
281         .cwnd_event     = dctcp_cwnd_event,
282         .ssthresh       = dctcp_ssthresh,
283         .cong_avoid     = tcp_reno_cong_avoid,
284         .undo_cwnd      = dctcp_cwnd_undo,
285         .set_state      = dctcp_state,
286         .get_info       = dctcp_get_info,
287         .flags          = TCP_CONG_NEEDS_ECN,
288         .owner          = THIS_MODULE,
289         .name           = "dctcp",
290 };
291
292 static struct tcp_congestion_ops dctcp_reno __read_mostly = {
293         .ssthresh       = tcp_reno_ssthresh,
294         .cong_avoid     = tcp_reno_cong_avoid,
295         .undo_cwnd      = tcp_reno_undo_cwnd,
296         .get_info       = dctcp_get_info,
297         .owner          = THIS_MODULE,
298         .name           = "dctcp-reno",
299 };
300
301 static int __init dctcp_register(void)
302 {
303         BUILD_BUG_ON(sizeof(struct dctcp) > ICSK_CA_PRIV_SIZE);
304         return tcp_register_congestion_control(&dctcp);
305 }
306
307 static void __exit dctcp_unregister(void)
308 {
309         tcp_unregister_congestion_control(&dctcp);
310 }
311
312 module_init(dctcp_register);
313 module_exit(dctcp_unregister);
314
315 MODULE_AUTHOR("Daniel Borkmann <dborkman@redhat.com>");
316 MODULE_AUTHOR("Florian Westphal <fw@strlen.de>");
317 MODULE_AUTHOR("Glenn Judd <glenn.judd@morganstanley.com>");
318
319 MODULE_LICENSE("GPL v2");
320 MODULE_DESCRIPTION("DataCenter TCP (DCTCP)");