1 /*-
2 * Copyright (c) 2007-2008
3 * Swinburne University of Technology, Melbourne, Australia
4 * Copyright (c) 2009-2010 Lawrence Stewart <lstewart@freebsd.org>
5 * Copyright (c) 2014 Midori Kato <katoon@sfc.wide.ad.jp>
6 * Copyright (c) 2014 The FreeBSD Foundation
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 * SUCH DAMAGE.
29 */
30
31 /*
32 * An implementation of the DCTCP algorithm for FreeBSD, based on
33 * "Data Center TCP (DCTCP)" by M. Alizadeh, A. Greenberg, D. A. Maltz,
34 * J. Padhye, P. Patel, B. Prabhakar, S. Sengupta, and M. Sridharan.,
35 * in ACM Conference on SIGCOMM 2010, New York, USA,
36 * Originally released as the contribution of Microsoft Research project.
37 */
38
39 #include <sys/cdefs.h>
40 __FBSDID("$FreeBSD$");
41
42 #include <sys/param.h>
43 #include <sys/kernel.h>
44 #include <sys/malloc.h>
45 #include <sys/module.h>
46 #include <sys/socket.h>
47 #include <sys/socketvar.h>
48 #include <sys/sysctl.h>
49 #include <sys/systm.h>
50
51 #include <net/vnet.h>
52
53 #include <netinet/in.h>
54 #include <netinet/ip.h>
55 #include <netinet/cc.h>
56 #include <netinet/tcp_seq.h>
57 #include <netinet/tcp_var.h>
58
59 #include <netinet/cc/cc_module.h>
60
61 #define CAST_PTR_INT(X) (*((int*)(X)))
62
63 #define MAX_ALPHA_VALUE 1024
64 static VNET_DEFINE(uint32_t, dctcp_alpha) = 0;
65 #define V_dctcp_alpha VNET(dctcp_alpha)
66 static VNET_DEFINE(uint32_t, dctcp_shift_g) = 4;
67 #define V_dctcp_shift_g VNET(dctcp_shift_g)
68 static VNET_DEFINE(uint32_t, dctcp_slowstart) = 0;
69 #define V_dctcp_slowstart VNET(dctcp_slowstart)
70
71 struct dctcp {
72 int bytes_ecn; /* # of marked bytes during a RTT */
73 int bytes_total; /* # of acked bytes during a RTT */
74 int alpha; /* the fraction of marked bytes */
75 int ce_prev; /* CE state of the last segment */
76 int save_sndnxt; /* end sequence number of the current window */
77 int ece_curr; /* ECE flag in this segment */
78 int ece_prev; /* ECE flag in the last segment */
79 uint32_t num_cong_events; /* # of congestion events */
80 };
81
82 static MALLOC_DEFINE(M_dctcp, "dctcp data",
83 "Per connection data required for the dctcp algorithm");
84
85 static void dctcp_ack_received(struct cc_var *ccv, uint16_t type);
86 static void dctcp_after_idle(struct cc_var *ccv);
87 static void dctcp_cb_destroy(struct cc_var *ccv);
88 static int dctcp_cb_init(struct cc_var *ccv);
89 static void dctcp_cong_signal(struct cc_var *ccv, uint32_t type);
90 static void dctcp_conn_init(struct cc_var *ccv);
91 static void dctcp_post_recovery(struct cc_var *ccv);
92 static void dctcp_ecnpkt_handler(struct cc_var *ccv);
93 static void dctcp_update_alpha(struct cc_var *ccv);
94
95 struct cc_algo dctcp_cc_algo = {
96 .name = "dctcp",
97 .ack_received = dctcp_ack_received,
98 .cb_destroy = dctcp_cb_destroy,
99 .cb_init = dctcp_cb_init,
100 .cong_signal = dctcp_cong_signal,
101 .conn_init = dctcp_conn_init,
102 .post_recovery = dctcp_post_recovery,
103 .ecnpkt_handler = dctcp_ecnpkt_handler,
104 .after_idle = dctcp_after_idle,
105 };
106
107 static void
dctcp_ack_received(struct cc_var * ccv,uint16_t type)108 dctcp_ack_received(struct cc_var *ccv, uint16_t type)
109 {
110 struct dctcp *dctcp_data;
111 int bytes_acked = 0;
112
113 dctcp_data = ccv->cc_data;
114
115 if (CCV(ccv, t_flags) & TF_ECN_PERMIT) {
116 /*
117 * DCTCP doesn't treat receipt of ECN marked packet as a
118 * congestion event. Thus, DCTCP always executes the ACK
119 * processing out of congestion recovery.
120 */
121 if (IN_CONGRECOVERY(CCV(ccv, t_flags))) {
122 EXIT_CONGRECOVERY(CCV(ccv, t_flags));
123 newreno_cc_algo.ack_received(ccv, type);
124 ENTER_CONGRECOVERY(CCV(ccv, t_flags));
125 } else
126 newreno_cc_algo.ack_received(ccv, type);
127
128 if (type == CC_DUPACK)
129 bytes_acked = CCV(ccv, t_maxseg);
130
131 if (type == CC_ACK)
132 bytes_acked = ccv->bytes_this_ack;
133
134 /* Update total bytes. */
135 dctcp_data->bytes_total += bytes_acked;
136
137 /* Update total marked bytes. */
138 if (dctcp_data->ece_curr) {
139 if (!dctcp_data->ece_prev
140 && bytes_acked > CCV(ccv, t_maxseg)) {
141 dctcp_data->bytes_ecn +=
142 (bytes_acked - CCV(ccv, t_maxseg));
143 } else
144 dctcp_data->bytes_ecn += bytes_acked;
145 dctcp_data->ece_prev = 1;
146 } else {
147 if (dctcp_data->ece_prev
148 && bytes_acked > CCV(ccv, t_maxseg))
149 dctcp_data->bytes_ecn += CCV(ccv, t_maxseg);
150 dctcp_data->ece_prev = 0;
151 }
152 dctcp_data->ece_curr = 0;
153
154 /*
155 * Update the fraction of marked bytes at the end of
156 * current window size.
157 */
158 if ((IN_FASTRECOVERY(CCV(ccv, t_flags)) &&
159 SEQ_GEQ(ccv->curack, CCV(ccv, snd_recover))) ||
160 (!IN_FASTRECOVERY(CCV(ccv, t_flags)) &&
161 SEQ_GT(ccv->curack, dctcp_data->save_sndnxt)))
162 dctcp_update_alpha(ccv);
163 } else
164 newreno_cc_algo.ack_received(ccv, type);
165 }
166
167 static void
dctcp_after_idle(struct cc_var * ccv)168 dctcp_after_idle(struct cc_var *ccv)
169 {
170 struct dctcp *dctcp_data;
171
172 dctcp_data = ccv->cc_data;
173
174 /* Initialize internal parameters after idle time */
175 dctcp_data->bytes_ecn = 0;
176 dctcp_data->bytes_total = 0;
177 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt);
178 dctcp_data->alpha = V_dctcp_alpha;
179 dctcp_data->ece_curr = 0;
180 dctcp_data->ece_prev = 0;
181 dctcp_data->num_cong_events = 0;
182
183 dctcp_cc_algo.after_idle = newreno_cc_algo.after_idle;
184 }
185
186 static void
dctcp_cb_destroy(struct cc_var * ccv)187 dctcp_cb_destroy(struct cc_var *ccv)
188 {
189 if (ccv->cc_data != NULL)
190 free(ccv->cc_data, M_dctcp);
191 }
192
193 static int
dctcp_cb_init(struct cc_var * ccv)194 dctcp_cb_init(struct cc_var *ccv)
195 {
196 struct dctcp *dctcp_data;
197
198 dctcp_data = malloc(sizeof(struct dctcp), M_dctcp, M_NOWAIT|M_ZERO);
199
200 if (dctcp_data == NULL)
201 return (ENOMEM);
202
203 /* Initialize some key variables with sensible defaults. */
204 dctcp_data->bytes_ecn = 0;
205 dctcp_data->bytes_total = 0;
206 /*
207 * When alpha is set to 0 in the beggining, DCTCP sender transfers as
208 * much data as possible until the value converges which may expand the
209 * queueing delay at the switch. When alpha is set to 1, queueing delay
210 * is kept small.
211 * Throughput-sensitive applications should have alpha = 0
212 * Latency-sensitive applications should have alpha = 1
213 *
214 * Note: DCTCP draft suggests initial alpha to be 1 but we've decided to
215 * keep it 0 as default.
216 */
217 dctcp_data->alpha = V_dctcp_alpha;
218 dctcp_data->save_sndnxt = 0;
219 dctcp_data->ce_prev = 0;
220 dctcp_data->ece_curr = 0;
221 dctcp_data->ece_prev = 0;
222 dctcp_data->num_cong_events = 0;
223
224 ccv->cc_data = dctcp_data;
225 return (0);
226 }
227
228 /*
229 * Perform any necessary tasks before we enter congestion recovery.
230 */
231 static void
dctcp_cong_signal(struct cc_var * ccv,uint32_t type)232 dctcp_cong_signal(struct cc_var *ccv, uint32_t type)
233 {
234 struct dctcp *dctcp_data;
235 u_int win, mss;
236
237 dctcp_data = ccv->cc_data;
238 win = CCV(ccv, snd_cwnd);
239 mss = CCV(ccv, t_maxseg);
240
241 switch (type) {
242 case CC_NDUPACK:
243 if (!IN_FASTRECOVERY(CCV(ccv, t_flags))) {
244 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) {
245 CCV(ccv, snd_ssthresh) = mss *
246 max(win / 2 / mss, 2);
247 dctcp_data->num_cong_events++;
248 } else {
249 /* cwnd has already updated as congestion
250 * recovery. Reverse cwnd value using
251 * snd_cwnd_prev and recalculate snd_ssthresh
252 */
253 win = CCV(ccv, snd_cwnd_prev);
254 CCV(ccv, snd_ssthresh) =
255 max(win / 2 / mss, 2) * mss;
256 }
257 ENTER_RECOVERY(CCV(ccv, t_flags));
258 }
259 break;
260 case CC_ECN:
261 /*
262 * Save current snd_cwnd when the host encounters both
263 * congestion recovery and fast recovery.
264 */
265 CCV(ccv, snd_cwnd_prev) = win;
266 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) {
267 if (V_dctcp_slowstart &&
268 dctcp_data->num_cong_events++ == 0) {
269 CCV(ccv, snd_ssthresh) =
270 mss * max(win / 2 / mss, 2);
271 dctcp_data->alpha = MAX_ALPHA_VALUE;
272 dctcp_data->bytes_ecn = 0;
273 dctcp_data->bytes_total = 0;
274 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt);
275 } else
276 CCV(ccv, snd_ssthresh) = max((win - ((win *
277 dctcp_data->alpha) >> 11)) / mss, 2) * mss;
278 CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh);
279 ENTER_CONGRECOVERY(CCV(ccv, t_flags));
280 }
281 dctcp_data->ece_curr = 1;
282 break;
283 case CC_RTO:
284 if (CCV(ccv, t_flags) & TF_ECN_PERMIT) {
285 CCV(ccv, t_flags) |= TF_ECN_SND_CWR;
286 dctcp_update_alpha(ccv);
287 dctcp_data->save_sndnxt += CCV(ccv, t_maxseg);
288 dctcp_data->num_cong_events++;
289 }
290 break;
291 }
292 }
293
294 static void
dctcp_conn_init(struct cc_var * ccv)295 dctcp_conn_init(struct cc_var *ccv)
296 {
297 struct dctcp *dctcp_data;
298
299 dctcp_data = ccv->cc_data;
300
301 if (CCV(ccv, t_flags) & TF_ECN_PERMIT)
302 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt);
303 }
304
305 /*
306 * Perform any necessary tasks before we exit congestion recovery.
307 */
308 static void
dctcp_post_recovery(struct cc_var * ccv)309 dctcp_post_recovery(struct cc_var *ccv)
310 {
311 dctcp_cc_algo.post_recovery = newreno_cc_algo.post_recovery;
312
313 if (CCV(ccv, t_flags) & TF_ECN_PERMIT)
314 dctcp_update_alpha(ccv);
315 }
316
317 /*
318 * Execute an additional ECN processing using ECN field in IP header and the CWR
319 * bit in TCP header.
320 *
321 * delay_ack == 0 - Delayed ACK disabled
322 * delay_ack == 1 - Delayed ACK enabled
323 */
324
325 static void
dctcp_ecnpkt_handler(struct cc_var * ccv)326 dctcp_ecnpkt_handler(struct cc_var *ccv)
327 {
328 struct dctcp *dctcp_data;
329 uint32_t ccflag;
330 int delay_ack;
331
332 dctcp_data = ccv->cc_data;
333 ccflag = ccv->flags;
334 delay_ack = 1;
335
336 /*
337 * DCTCP responses an ACK immediately when the CE state
338 * in between this segment and the last segment is not same.
339 */
340 if (ccflag & CCF_IPHDR_CE) {
341 if (!dctcp_data->ce_prev && (ccflag & CCF_DELACK))
342 delay_ack = 0;
343 dctcp_data->ce_prev = 1;
344 CCV(ccv, t_flags) |= TF_ECN_SND_ECE;
345 } else {
346 if (dctcp_data->ce_prev && (ccflag & CCF_DELACK))
347 delay_ack = 0;
348 dctcp_data->ce_prev = 0;
349 CCV(ccv, t_flags) &= ~TF_ECN_SND_ECE;
350 }
351
352 /* DCTCP sets delayed ack when this segment sets the CWR flag. */
353 if ((ccflag & CCF_DELACK) && (ccflag & CCF_TCPHDR_CWR))
354 delay_ack = 1;
355
356 if (delay_ack == 0)
357 ccv->flags |= CCF_ACKNOW;
358 else
359 ccv->flags &= ~CCF_ACKNOW;
360 }
361
362 /*
363 * Update the fraction of marked bytes represented as 'alpha'.
364 * Also initialize several internal parameters at the end of this function.
365 */
366 static void
dctcp_update_alpha(struct cc_var * ccv)367 dctcp_update_alpha(struct cc_var *ccv)
368 {
369 struct dctcp *dctcp_data;
370 int alpha_prev;
371
372 dctcp_data = ccv->cc_data;
373 alpha_prev = dctcp_data->alpha;
374 dctcp_data->bytes_total = max(dctcp_data->bytes_total, 1);
375
376 /*
377 * Update alpha: alpha = (1 - g) * alpha + g * F.
378 * Here:
379 * g is weight factor
380 * recommaded to be set to 1/16
381 * small g = slow convergence between competitive DCTCP flows
382 * large g = impacts low utilization of bandwidth at switches
383 * F is fraction of marked segments in last RTT
384 * updated every RTT
385 * Alpha must be round to 0 - MAX_ALPHA_VALUE.
386 */
387 dctcp_data->alpha = min(alpha_prev - (alpha_prev >> V_dctcp_shift_g) +
388 (dctcp_data->bytes_ecn << (10 - V_dctcp_shift_g)) /
389 dctcp_data->bytes_total, MAX_ALPHA_VALUE);
390
391 /* Initialize internal parameters for next alpha calculation */
392 dctcp_data->bytes_ecn = 0;
393 dctcp_data->bytes_total = 0;
394 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt);
395 }
396
397 static int
dctcp_alpha_handler(SYSCTL_HANDLER_ARGS)398 dctcp_alpha_handler(SYSCTL_HANDLER_ARGS)
399 {
400 uint32_t new;
401 int error;
402
403 new = V_dctcp_alpha;
404 error = sysctl_handle_int(oidp, &new, 0, req);
405 if (error == 0 && req->newptr != NULL) {
406 if (CAST_PTR_INT(req->newptr) > 1)
407 error = EINVAL;
408 else {
409 if (new > MAX_ALPHA_VALUE)
410 V_dctcp_alpha = MAX_ALPHA_VALUE;
411 else
412 V_dctcp_alpha = new;
413 }
414 }
415
416 return (error);
417 }
418
419 static int
dctcp_shift_g_handler(SYSCTL_HANDLER_ARGS)420 dctcp_shift_g_handler(SYSCTL_HANDLER_ARGS)
421 {
422 uint32_t new;
423 int error;
424
425 new = V_dctcp_shift_g;
426 error = sysctl_handle_int(oidp, &new, 0, req);
427 if (error == 0 && req->newptr != NULL) {
428 if (CAST_PTR_INT(req->newptr) > 1)
429 error = EINVAL;
430 else
431 V_dctcp_shift_g = new;
432 }
433
434 return (error);
435 }
436
437 static int
dctcp_slowstart_handler(SYSCTL_HANDLER_ARGS)438 dctcp_slowstart_handler(SYSCTL_HANDLER_ARGS)
439 {
440 uint32_t new;
441 int error;
442
443 new = V_dctcp_slowstart;
444 error = sysctl_handle_int(oidp, &new, 0, req);
445 if (error == 0 && req->newptr != NULL) {
446 if (CAST_PTR_INT(req->newptr) > 1)
447 error = EINVAL;
448 else
449 V_dctcp_slowstart = new;
450 }
451
452 return (error);
453 }
454
455 SYSCTL_DECL(_net_inet_tcp_cc_dctcp);
456 SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, dctcp, CTLFLAG_RW, NULL,
457 "dctcp congestion control related settings");
458
459 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, alpha,
460 CTLFLAG_VNET|CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(dctcp_alpha), 0,
461 &dctcp_alpha_handler,
462 "IU", "dctcp alpha parameter");
463
464 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, shift_g,
465 CTLFLAG_VNET|CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(dctcp_shift_g), 4,
466 &dctcp_shift_g_handler,
467 "IU", "dctcp shift parameter");
468
469 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, slowstart,
470 CTLFLAG_VNET|CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(dctcp_slowstart), 0,
471 &dctcp_slowstart_handler,
472 "IU", "half CWND reduction after the first slow start");
473
474 DECLARE_CC_MODULE(dctcp, &dctcp_cc_algo);
475