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
dctcp_reset(const struct tcp_sock * tp,struct dctcp * ca)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
dctcp_init(struct sock * sk)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
dctcp_ssthresh(struct sock * sk)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
dctcp_ce_state_0_to_1(struct sock * sk)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 tcp_enter_quickack_mode(sk, 1);
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
dctcp_ce_state_1_to_0(struct sock * sk)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 tcp_enter_quickack_mode(sk, 1);
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
dctcp_update_alpha(struct sock * sk,u32 flags)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
dctcp_react_to_loss(struct sock * sk)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
dctcp_state(struct sock * sk,u8 new_state)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
dctcp_cwnd_event(struct sock * sk,enum tcp_ca_event ev)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
dctcp_get_info(struct sock * sk,u32 ext,int * attr,union tcp_cc_info * info)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
dctcp_cwnd_undo(struct sock * sk)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
dctcp_register(void)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
dctcp_unregister(void)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)");
321