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/tcp.h> 54 #include <netinet/tcp_seq.h> 55 #include <netinet/tcp_var.h> 56 #include <netinet/cc/cc.h> 57 #include <netinet/cc/cc_module.h> 58 59 #define CAST_PTR_INT(X) (*((int*)(X))) 60 61 #define MAX_ALPHA_VALUE 1024 62 static VNET_DEFINE(uint32_t, dctcp_alpha) = 0; 63 #define V_dctcp_alpha VNET(dctcp_alpha) 64 static VNET_DEFINE(uint32_t, dctcp_shift_g) = 4; 65 #define V_dctcp_shift_g VNET(dctcp_shift_g) 66 static VNET_DEFINE(uint32_t, dctcp_slowstart) = 0; 67 #define V_dctcp_slowstart VNET(dctcp_slowstart) 68 69 struct dctcp { 70 int bytes_ecn; /* # of marked bytes during a RTT */ 71 int bytes_total; /* # of acked bytes during a RTT */ 72 int alpha; /* the fraction of marked bytes */ 73 int ce_prev; /* CE state of the last segment */ 74 int save_sndnxt; /* end sequence number of the current window */ 75 int ece_curr; /* ECE flag in this segment */ 76 int ece_prev; /* ECE flag in the last segment */ 77 uint32_t num_cong_events; /* # of congestion events */ 78 }; 79 80 static MALLOC_DEFINE(M_dctcp, "dctcp data", 81 "Per connection data required for the dctcp algorithm"); 82 83 static void dctcp_ack_received(struct cc_var *ccv, uint16_t type); 84 static void dctcp_after_idle(struct cc_var *ccv); 85 static void dctcp_cb_destroy(struct cc_var *ccv); 86 static int dctcp_cb_init(struct cc_var *ccv); 87 static void dctcp_cong_signal(struct cc_var *ccv, uint32_t type); 88 static void dctcp_conn_init(struct cc_var *ccv); 89 static void dctcp_post_recovery(struct cc_var *ccv); 90 static void dctcp_ecnpkt_handler(struct cc_var *ccv); 91 static void dctcp_update_alpha(struct cc_var *ccv); 92 93 struct cc_algo dctcp_cc_algo = { 94 .name = "dctcp", 95 .ack_received = dctcp_ack_received, 96 .cb_destroy = dctcp_cb_destroy, 97 .cb_init = dctcp_cb_init, 98 .cong_signal = dctcp_cong_signal, 99 .conn_init = dctcp_conn_init, 100 .post_recovery = dctcp_post_recovery, 101 .ecnpkt_handler = dctcp_ecnpkt_handler, 102 .after_idle = dctcp_after_idle, 103 }; 104 105 static void 106 dctcp_ack_received(struct cc_var *ccv, uint16_t type) 107 { 108 struct dctcp *dctcp_data; 109 int bytes_acked = 0; 110 111 dctcp_data = ccv->cc_data; 112 113 if (CCV(ccv, t_flags) & TF_ECN_PERMIT) { 114 /* 115 * DCTCP doesn't treat receipt of ECN marked packet as a 116 * congestion event. Thus, DCTCP always executes the ACK 117 * processing out of congestion recovery. 118 */ 119 if (IN_CONGRECOVERY(CCV(ccv, t_flags))) { 120 EXIT_CONGRECOVERY(CCV(ccv, t_flags)); 121 newreno_cc_algo.ack_received(ccv, type); 122 ENTER_CONGRECOVERY(CCV(ccv, t_flags)); 123 } else 124 newreno_cc_algo.ack_received(ccv, type); 125 126 if (type == CC_DUPACK) 127 bytes_acked = CCV(ccv, t_maxseg); 128 129 if (type == CC_ACK) 130 bytes_acked = ccv->bytes_this_ack; 131 132 /* Update total bytes. */ 133 dctcp_data->bytes_total += bytes_acked; 134 135 /* Update total marked bytes. */ 136 if (dctcp_data->ece_curr) { 137 if (!dctcp_data->ece_prev 138 && bytes_acked > CCV(ccv, t_maxseg)) { 139 dctcp_data->bytes_ecn += 140 (bytes_acked - CCV(ccv, t_maxseg)); 141 } else 142 dctcp_data->bytes_ecn += bytes_acked; 143 dctcp_data->ece_prev = 1; 144 } else { 145 if (dctcp_data->ece_prev 146 && bytes_acked > CCV(ccv, t_maxseg)) 147 dctcp_data->bytes_ecn += CCV(ccv, t_maxseg); 148 dctcp_data->ece_prev = 0; 149 } 150 dctcp_data->ece_curr = 0; 151 152 /* 153 * Update the fraction of marked bytes at the end of 154 * current window size. 155 */ 156 if ((IN_FASTRECOVERY(CCV(ccv, t_flags)) && 157 SEQ_GEQ(ccv->curack, CCV(ccv, snd_recover))) || 158 (!IN_FASTRECOVERY(CCV(ccv, t_flags)) && 159 SEQ_GT(ccv->curack, dctcp_data->save_sndnxt))) 160 dctcp_update_alpha(ccv); 161 } else 162 newreno_cc_algo.ack_received(ccv, type); 163 } 164 165 static void 166 dctcp_after_idle(struct cc_var *ccv) 167 { 168 struct dctcp *dctcp_data; 169 170 dctcp_data = ccv->cc_data; 171 172 /* Initialize internal parameters after idle time */ 173 dctcp_data->bytes_ecn = 0; 174 dctcp_data->bytes_total = 0; 175 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt); 176 dctcp_data->alpha = V_dctcp_alpha; 177 dctcp_data->ece_curr = 0; 178 dctcp_data->ece_prev = 0; 179 dctcp_data->num_cong_events = 0; 180 181 dctcp_cc_algo.after_idle = newreno_cc_algo.after_idle; 182 } 183 184 static void 185 dctcp_cb_destroy(struct cc_var *ccv) 186 { 187 if (ccv->cc_data != NULL) 188 free(ccv->cc_data, M_dctcp); 189 } 190 191 static int 192 dctcp_cb_init(struct cc_var *ccv) 193 { 194 struct dctcp *dctcp_data; 195 196 dctcp_data = malloc(sizeof(struct dctcp), M_dctcp, M_NOWAIT|M_ZERO); 197 198 if (dctcp_data == NULL) 199 return (ENOMEM); 200 201 /* Initialize some key variables with sensible defaults. */ 202 dctcp_data->bytes_ecn = 0; 203 dctcp_data->bytes_total = 0; 204 /* 205 * When alpha is set to 0 in the beginning, DCTCP sender transfers as 206 * much data as possible until the value converges which may expand the 207 * queueing delay at the switch. When alpha is set to 1, queueing delay 208 * is kept small. 209 * Throughput-sensitive applications should have alpha = 0 210 * Latency-sensitive applications should have alpha = 1 211 * 212 * Note: DCTCP draft suggests initial alpha to be 1 but we've decided to 213 * keep it 0 as default. 214 */ 215 dctcp_data->alpha = V_dctcp_alpha; 216 dctcp_data->save_sndnxt = 0; 217 dctcp_data->ce_prev = 0; 218 dctcp_data->ece_curr = 0; 219 dctcp_data->ece_prev = 0; 220 dctcp_data->num_cong_events = 0; 221 222 ccv->cc_data = dctcp_data; 223 return (0); 224 } 225 226 /* 227 * Perform any necessary tasks before we enter congestion recovery. 228 */ 229 static void 230 dctcp_cong_signal(struct cc_var *ccv, uint32_t type) 231 { 232 struct dctcp *dctcp_data; 233 u_int win, mss; 234 235 dctcp_data = ccv->cc_data; 236 win = CCV(ccv, snd_cwnd); 237 mss = CCV(ccv, t_maxseg); 238 239 switch (type) { 240 case CC_NDUPACK: 241 if (!IN_FASTRECOVERY(CCV(ccv, t_flags))) { 242 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) { 243 CCV(ccv, snd_ssthresh) = mss * 244 max(win / 2 / mss, 2); 245 dctcp_data->num_cong_events++; 246 } else { 247 /* cwnd has already updated as congestion 248 * recovery. Reverse cwnd value using 249 * snd_cwnd_prev and recalculate snd_ssthresh 250 */ 251 win = CCV(ccv, snd_cwnd_prev); 252 CCV(ccv, snd_ssthresh) = 253 max(win / 2 / mss, 2) * mss; 254 } 255 ENTER_RECOVERY(CCV(ccv, t_flags)); 256 } 257 break; 258 case CC_ECN: 259 /* 260 * Save current snd_cwnd when the host encounters both 261 * congestion recovery and fast recovery. 262 */ 263 CCV(ccv, snd_cwnd_prev) = win; 264 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) { 265 if (V_dctcp_slowstart && 266 dctcp_data->num_cong_events++ == 0) { 267 CCV(ccv, snd_ssthresh) = 268 mss * max(win / 2 / mss, 2); 269 dctcp_data->alpha = MAX_ALPHA_VALUE; 270 dctcp_data->bytes_ecn = 0; 271 dctcp_data->bytes_total = 0; 272 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt); 273 } else 274 CCV(ccv, snd_ssthresh) = max((win - ((win * 275 dctcp_data->alpha) >> 11)) / mss, 2) * mss; 276 CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh); 277 ENTER_CONGRECOVERY(CCV(ccv, t_flags)); 278 } 279 dctcp_data->ece_curr = 1; 280 break; 281 case CC_RTO: 282 if (CCV(ccv, t_flags) & TF_ECN_PERMIT) { 283 CCV(ccv, t_flags) |= TF_ECN_SND_CWR; 284 dctcp_update_alpha(ccv); 285 dctcp_data->save_sndnxt += CCV(ccv, t_maxseg); 286 dctcp_data->num_cong_events++; 287 } 288 break; 289 } 290 } 291 292 static void 293 dctcp_conn_init(struct cc_var *ccv) 294 { 295 struct dctcp *dctcp_data; 296 297 dctcp_data = ccv->cc_data; 298 299 if (CCV(ccv, t_flags) & TF_ECN_PERMIT) 300 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt); 301 } 302 303 /* 304 * Perform any necessary tasks before we exit congestion recovery. 305 */ 306 static void 307 dctcp_post_recovery(struct cc_var *ccv) 308 { 309 dctcp_cc_algo.post_recovery = newreno_cc_algo.post_recovery; 310 311 if (CCV(ccv, t_flags) & TF_ECN_PERMIT) 312 dctcp_update_alpha(ccv); 313 } 314 315 /* 316 * Execute an additional ECN processing using ECN field in IP header and the CWR 317 * bit in TCP header. 318 * 319 * delay_ack == 0 - Delayed ACK disabled 320 * delay_ack == 1 - Delayed ACK enabled 321 */ 322 323 static void 324 dctcp_ecnpkt_handler(struct cc_var *ccv) 325 { 326 struct dctcp *dctcp_data; 327 uint32_t ccflag; 328 int delay_ack; 329 330 dctcp_data = ccv->cc_data; 331 ccflag = ccv->flags; 332 delay_ack = 1; 333 334 /* 335 * DCTCP responses an ACK immediately when the CE state 336 * in between this segment and the last segment is not same. 337 */ 338 if (ccflag & CCF_IPHDR_CE) { 339 if (!dctcp_data->ce_prev && (ccflag & CCF_DELACK)) 340 delay_ack = 0; 341 dctcp_data->ce_prev = 1; 342 CCV(ccv, t_flags) |= TF_ECN_SND_ECE; 343 } else { 344 if (dctcp_data->ce_prev && (ccflag & CCF_DELACK)) 345 delay_ack = 0; 346 dctcp_data->ce_prev = 0; 347 CCV(ccv, t_flags) &= ~TF_ECN_SND_ECE; 348 } 349 350 /* DCTCP sets delayed ack when this segment sets the CWR flag. */ 351 if ((ccflag & CCF_DELACK) && (ccflag & CCF_TCPHDR_CWR)) 352 delay_ack = 1; 353 354 if (delay_ack == 0) 355 ccv->flags |= CCF_ACKNOW; 356 else 357 ccv->flags &= ~CCF_ACKNOW; 358 } 359 360 /* 361 * Update the fraction of marked bytes represented as 'alpha'. 362 * Also initialize several internal parameters at the end of this function. 363 */ 364 static void 365 dctcp_update_alpha(struct cc_var *ccv) 366 { 367 struct dctcp *dctcp_data; 368 int alpha_prev; 369 370 dctcp_data = ccv->cc_data; 371 alpha_prev = dctcp_data->alpha; 372 dctcp_data->bytes_total = max(dctcp_data->bytes_total, 1); 373 374 /* 375 * Update alpha: alpha = (1 - g) * alpha + g * F. 376 * Here: 377 * g is weight factor 378 * recommaded to be set to 1/16 379 * small g = slow convergence between competitive DCTCP flows 380 * large g = impacts low utilization of bandwidth at switches 381 * F is fraction of marked segments in last RTT 382 * updated every RTT 383 * Alpha must be round to 0 - MAX_ALPHA_VALUE. 384 */ 385 dctcp_data->alpha = min(alpha_prev - (alpha_prev >> V_dctcp_shift_g) + 386 (dctcp_data->bytes_ecn << (10 - V_dctcp_shift_g)) / 387 dctcp_data->bytes_total, MAX_ALPHA_VALUE); 388 389 /* Initialize internal parameters for next alpha calculation */ 390 dctcp_data->bytes_ecn = 0; 391 dctcp_data->bytes_total = 0; 392 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt); 393 } 394 395 static int 396 dctcp_alpha_handler(SYSCTL_HANDLER_ARGS) 397 { 398 uint32_t new; 399 int error; 400 401 new = V_dctcp_alpha; 402 error = sysctl_handle_int(oidp, &new, 0, req); 403 if (error == 0 && req->newptr != NULL) { 404 if (CAST_PTR_INT(req->newptr) > 1) 405 error = EINVAL; 406 else { 407 if (new > MAX_ALPHA_VALUE) 408 V_dctcp_alpha = MAX_ALPHA_VALUE; 409 else 410 V_dctcp_alpha = new; 411 } 412 } 413 414 return (error); 415 } 416 417 static int 418 dctcp_shift_g_handler(SYSCTL_HANDLER_ARGS) 419 { 420 uint32_t new; 421 int error; 422 423 new = V_dctcp_shift_g; 424 error = sysctl_handle_int(oidp, &new, 0, req); 425 if (error == 0 && req->newptr != NULL) { 426 if (CAST_PTR_INT(req->newptr) > 1) 427 error = EINVAL; 428 else 429 V_dctcp_shift_g = new; 430 } 431 432 return (error); 433 } 434 435 static int 436 dctcp_slowstart_handler(SYSCTL_HANDLER_ARGS) 437 { 438 uint32_t new; 439 int error; 440 441 new = V_dctcp_slowstart; 442 error = sysctl_handle_int(oidp, &new, 0, req); 443 if (error == 0 && req->newptr != NULL) { 444 if (CAST_PTR_INT(req->newptr) > 1) 445 error = EINVAL; 446 else 447 V_dctcp_slowstart = new; 448 } 449 450 return (error); 451 } 452 453 SYSCTL_DECL(_net_inet_tcp_cc_dctcp); 454 SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, dctcp, CTLFLAG_RW, NULL, 455 "dctcp congestion control related settings"); 456 457 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, alpha, 458 CTLFLAG_VNET|CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(dctcp_alpha), 0, 459 &dctcp_alpha_handler, 460 "IU", "dctcp alpha parameter"); 461 462 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, shift_g, 463 CTLFLAG_VNET|CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(dctcp_shift_g), 4, 464 &dctcp_shift_g_handler, 465 "IU", "dctcp shift parameter"); 466 467 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, slowstart, 468 CTLFLAG_VNET|CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(dctcp_slowstart), 0, 469 &dctcp_slowstart_handler, 470 "IU", "half CWND reduction after the first slow start"); 471 472 DECLARE_CC_MODULE(dctcp, &dctcp_cc_algo); 473