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/param.h> 40 #include <sys/kernel.h> 41 #include <sys/malloc.h> 42 #include <sys/module.h> 43 #include <sys/socket.h> 44 #include <sys/socketvar.h> 45 #include <sys/sysctl.h> 46 #include <sys/systm.h> 47 48 #include <net/vnet.h> 49 50 #include <net/route.h> 51 #include <net/route/nhop.h> 52 53 #include <netinet/in_pcb.h> 54 #include <netinet/tcp.h> 55 #include <netinet/tcp_seq.h> 56 #include <netinet/tcp_var.h> 57 #include <netinet/cc/cc.h> 58 #include <netinet/cc/cc_module.h> 59 60 #define DCTCP_SHIFT 10 61 #define MAX_ALPHA_VALUE (1<<DCTCP_SHIFT) 62 VNET_DEFINE_STATIC(uint32_t, dctcp_alpha) = MAX_ALPHA_VALUE; 63 #define V_dctcp_alpha VNET(dctcp_alpha) 64 VNET_DEFINE_STATIC(uint32_t, dctcp_shift_g) = 4; 65 #define V_dctcp_shift_g VNET(dctcp_shift_g) 66 VNET_DEFINE_STATIC(uint32_t, dctcp_slowstart) = 0; 67 #define V_dctcp_slowstart VNET(dctcp_slowstart) 68 VNET_DEFINE_STATIC(uint32_t, dctcp_ect1) = 0; 69 #define V_dctcp_ect1 VNET(dctcp_ect1) 70 71 struct dctcp { 72 uint32_t bytes_ecn; /* # of marked bytes during a RTT */ 73 uint32_t 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 tcp_seq 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 void dctcp_ack_received(struct cc_var *ccv, ccsignal_t type); 83 static void dctcp_after_idle(struct cc_var *ccv); 84 static void dctcp_cb_destroy(struct cc_var *ccv); 85 static int dctcp_cb_init(struct cc_var *ccv, void *ptr); 86 static void dctcp_cong_signal(struct cc_var *ccv, ccsignal_t type); 87 static void dctcp_conn_init(struct cc_var *ccv); 88 static void dctcp_post_recovery(struct cc_var *ccv); 89 static void dctcp_ecnpkt_handler(struct cc_var *ccv); 90 static void dctcp_update_alpha(struct cc_var *ccv); 91 static size_t dctcp_data_sz(void); 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 .cc_data_sz = dctcp_data_sz, 104 }; 105 106 static void 107 dctcp_ack_received(struct cc_var *ccv, ccsignal_t type) 108 { 109 struct dctcp *dctcp_data; 110 int bytes_acked = 0; 111 112 dctcp_data = ccv->cc_data; 113 114 if (CCV(ccv, t_flags2) & TF2_ECN_PERMIT) { 115 /* 116 * DCTCP doesn't treat receipt of ECN marked packet as a 117 * congestion event. Thus, DCTCP always executes the ACK 118 * processing out of congestion recovery. 119 */ 120 if (IN_CONGRECOVERY(CCV(ccv, t_flags))) { 121 EXIT_CONGRECOVERY(CCV(ccv, t_flags)); 122 newreno_cc_ack_received(ccv, type); 123 ENTER_CONGRECOVERY(CCV(ccv, t_flags)); 124 } else 125 newreno_cc_ack_received(ccv, type); 126 127 if (type == CC_DUPACK) 128 bytes_acked = min(ccv->bytes_this_ack, CCV(ccv, t_maxseg)); 129 130 if (type == CC_ACK) 131 bytes_acked = ccv->bytes_this_ack; 132 133 /* Update total bytes. */ 134 dctcp_data->bytes_total += bytes_acked; 135 136 /* Update total marked bytes. */ 137 if (dctcp_data->ece_curr) { 138 //XXRMS: For fluid-model DCTCP, update 139 //cwnd here during for RTT fairness 140 if (!dctcp_data->ece_prev 141 && bytes_acked > CCV(ccv, t_maxseg)) { 142 dctcp_data->bytes_ecn += 143 (bytes_acked - CCV(ccv, t_maxseg)); 144 } else 145 dctcp_data->bytes_ecn += bytes_acked; 146 dctcp_data->ece_prev = 1; 147 } else { 148 if (dctcp_data->ece_prev 149 && bytes_acked > CCV(ccv, t_maxseg)) 150 dctcp_data->bytes_ecn += CCV(ccv, t_maxseg); 151 dctcp_data->ece_prev = 0; 152 } 153 dctcp_data->ece_curr = 0; 154 155 /* 156 * Update the fraction of marked bytes at the end of 157 * current window size. 158 */ 159 if (!IN_FASTRECOVERY(CCV(ccv, t_flags)) && 160 SEQ_GT(ccv->curack, dctcp_data->save_sndnxt)) 161 dctcp_update_alpha(ccv); 162 } else 163 newreno_cc_ack_received(ccv, type); 164 } 165 166 static size_t 167 dctcp_data_sz(void) 168 { 169 return (sizeof(struct dctcp)); 170 } 171 172 static void 173 dctcp_after_idle(struct cc_var *ccv) 174 { 175 struct dctcp *dctcp_data; 176 177 if (CCV(ccv, t_flags2) & TF2_ECN_PERMIT) { 178 dctcp_data = ccv->cc_data; 179 180 /* Initialize internal parameters after idle time */ 181 dctcp_data->bytes_ecn = 0; 182 dctcp_data->bytes_total = 0; 183 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt); 184 dctcp_data->alpha = V_dctcp_alpha; 185 dctcp_data->ece_curr = 0; 186 dctcp_data->ece_prev = 0; 187 dctcp_data->num_cong_events = 0; 188 } 189 190 newreno_cc_after_idle(ccv); 191 } 192 193 static void 194 dctcp_cb_destroy(struct cc_var *ccv) 195 { 196 free(ccv->cc_data, M_CC_MEM); 197 } 198 199 static int 200 dctcp_cb_init(struct cc_var *ccv, void *ptr) 201 { 202 struct dctcp *dctcp_data; 203 204 INP_WLOCK_ASSERT(tptoinpcb(ccv->ccvc.tcp)); 205 if (ptr == NULL) { 206 dctcp_data = malloc(sizeof(struct dctcp), M_CC_MEM, M_NOWAIT|M_ZERO); 207 if (dctcp_data == NULL) 208 return (ENOMEM); 209 } else 210 dctcp_data = ptr; 211 /* Initialize some key variables with sensible defaults. */ 212 dctcp_data->bytes_ecn = 0; 213 dctcp_data->bytes_total = 0; 214 /* 215 * When alpha is set to 0 in the beginning, DCTCP sender transfers as 216 * much data as possible until the value converges which may expand the 217 * queueing delay at the switch. When alpha is set to 1, queueing delay 218 * is kept small. 219 * Throughput-sensitive applications should have alpha = 0 220 * Latency-sensitive applications should have alpha = 1 221 * 222 * Note: DCTCP draft suggests initial alpha to be 1 but we've decided to 223 * keep it 0 as default. 224 */ 225 dctcp_data->alpha = V_dctcp_alpha; 226 dctcp_data->save_sndnxt = 0; 227 dctcp_data->ce_prev = 0; 228 dctcp_data->ece_curr = 0; 229 dctcp_data->ece_prev = 0; 230 dctcp_data->num_cong_events = 0; 231 232 ccv->cc_data = dctcp_data; 233 return (0); 234 } 235 236 /* 237 * Perform any necessary tasks before we enter congestion recovery. 238 */ 239 static void 240 dctcp_cong_signal(struct cc_var *ccv, ccsignal_t type) 241 { 242 struct dctcp *dctcp_data; 243 uint32_t cwin, mss, pipe; 244 245 if (CCV(ccv, t_flags2) & TF2_ECN_PERMIT) { 246 dctcp_data = ccv->cc_data; 247 cwin = CCV(ccv, snd_cwnd); 248 mss = tcp_fixed_maxseg(ccv->ccvc.tcp); 249 250 switch (type) { 251 case CC_NDUPACK: 252 if (!IN_FASTRECOVERY(CCV(ccv, t_flags))) { 253 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) { 254 CCV(ccv, snd_ssthresh) = 255 max(cwin / 2, 2 * mss); 256 dctcp_data->num_cong_events++; 257 } else { 258 /* cwnd has already updated as congestion 259 * recovery. Reverse cwnd value using 260 * snd_cwnd_prev and recalculate snd_ssthresh 261 */ 262 cwin = CCV(ccv, snd_cwnd_prev); 263 CCV(ccv, snd_ssthresh) = 264 max(cwin / 2, 2 * mss); 265 } 266 ENTER_RECOVERY(CCV(ccv, t_flags)); 267 } 268 break; 269 case CC_ECN: 270 /* 271 * Save current snd_cwnd when the host encounters both 272 * congestion recovery and fast recovery. 273 */ 274 CCV(ccv, snd_cwnd_prev) = cwin; 275 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) { 276 if (V_dctcp_slowstart && 277 dctcp_data->num_cong_events++ == 0) { 278 CCV(ccv, snd_ssthresh) = 279 max(cwin / 2, 2 * mss); 280 dctcp_data->alpha = MAX_ALPHA_VALUE; 281 dctcp_data->bytes_ecn = 0; 282 dctcp_data->bytes_total = 0; 283 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt); 284 } else 285 CCV(ccv, snd_ssthresh) = 286 max((cwin - (((uint64_t)cwin * 287 dctcp_data->alpha) >> (DCTCP_SHIFT+1))), 288 2 * mss); 289 CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh); 290 ENTER_CONGRECOVERY(CCV(ccv, t_flags)); 291 } 292 dctcp_data->ece_curr = 1; 293 break; 294 case CC_RTO: 295 if (CCV(ccv, t_rxtshift) == 1) { 296 if (V_tcp_do_newsack) { 297 pipe = tcp_compute_pipe(ccv->ccvc.tcp); 298 } else { 299 pipe = CCV(ccv, snd_max) - 300 CCV(ccv, snd_fack) + 301 CCV(ccv, sackhint.sack_bytes_rexmit); 302 } 303 CCV(ccv, snd_ssthresh) = max(2, 304 min(CCV(ccv, snd_wnd), pipe) / 2 / mss) * mss; 305 } 306 CCV(ccv, snd_cwnd) = mss; 307 dctcp_update_alpha(ccv); 308 dctcp_data->save_sndnxt += CCV(ccv, t_maxseg); 309 dctcp_data->num_cong_events++; 310 break; 311 default: 312 break; 313 } 314 } else 315 newreno_cc_cong_signal(ccv, type); 316 } 317 318 static void 319 dctcp_conn_init(struct cc_var *ccv) 320 { 321 struct dctcp *dctcp_data; 322 323 dctcp_data = ccv->cc_data; 324 325 if (CCV(ccv, t_flags2) & TF2_ECN_PERMIT) { 326 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt); 327 if (V_dctcp_ect1) 328 CCV(ccv, t_flags2) |= TF2_ECN_USE_ECT1; 329 } 330 } 331 332 /* 333 * Perform any necessary tasks before we exit congestion recovery. 334 */ 335 static void 336 dctcp_post_recovery(struct cc_var *ccv) 337 { 338 newreno_cc_post_recovery(ccv); 339 340 if (CCV(ccv, t_flags2) & TF2_ECN_PERMIT) 341 dctcp_update_alpha(ccv); 342 } 343 344 /* 345 * Execute an additional ECN processing using ECN field in IP header 346 * and the CWR bit in TCP header. 347 */ 348 static void 349 dctcp_ecnpkt_handler(struct cc_var *ccv) 350 { 351 struct dctcp *dctcp_data; 352 uint32_t ccflag; 353 int acknow; 354 355 dctcp_data = ccv->cc_data; 356 ccflag = ccv->flags; 357 acknow = 0; 358 359 /* 360 * DCTCP responds with an ACK immediately when the CE state 361 * in between this segment and the last segment has changed. 362 */ 363 if (ccflag & CCF_IPHDR_CE) { 364 if (!dctcp_data->ce_prev) { 365 acknow = 1; 366 dctcp_data->ce_prev = 1; 367 CCV(ccv, t_flags2) |= TF2_ECN_SND_ECE; 368 } 369 } else { 370 if (dctcp_data->ce_prev) { 371 acknow = 1; 372 dctcp_data->ce_prev = 0; 373 CCV(ccv, t_flags2) &= ~TF2_ECN_SND_ECE; 374 } 375 } 376 377 if ((acknow) || (ccflag & CCF_TCPHDR_CWR)) { 378 ccv->flags |= CCF_ACKNOW; 379 } else { 380 ccv->flags &= ~CCF_ACKNOW; 381 } 382 } 383 384 /* 385 * Update the fraction of marked bytes represented as 'alpha'. 386 * Also initialize several internal parameters at the end of this function. 387 */ 388 static void 389 dctcp_update_alpha(struct cc_var *ccv) 390 { 391 struct dctcp *dctcp_data; 392 int alpha_prev; 393 394 dctcp_data = ccv->cc_data; 395 alpha_prev = dctcp_data->alpha; 396 dctcp_data->bytes_total = max(dctcp_data->bytes_total, 1); 397 398 /* 399 * Update alpha: alpha = (1 - g) * alpha + g * M. 400 * Here: 401 * g is weight factor 402 * recommaded to be set to 1/16 403 * small g = slow convergence between competitive DCTCP flows 404 * large g = impacts low utilization of bandwidth at switches 405 * M is fraction of marked segments in last RTT 406 * updated every RTT 407 * Alpha must be round to 0 - MAX_ALPHA_VALUE. 408 */ 409 dctcp_data->alpha = ulmin(alpha_prev - (alpha_prev >> V_dctcp_shift_g) + 410 ((uint64_t)dctcp_data->bytes_ecn << (DCTCP_SHIFT - V_dctcp_shift_g)) / 411 dctcp_data->bytes_total, MAX_ALPHA_VALUE); 412 413 /* Initialize internal parameters for next alpha calculation */ 414 dctcp_data->bytes_ecn = 0; 415 dctcp_data->bytes_total = 0; 416 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt); 417 } 418 419 static int 420 dctcp_alpha_handler(SYSCTL_HANDLER_ARGS) 421 { 422 uint32_t new; 423 int error; 424 425 new = V_dctcp_alpha; 426 error = sysctl_handle_int(oidp, &new, 0, req); 427 if (error == 0 && req->newptr != NULL) { 428 if (new > MAX_ALPHA_VALUE) 429 error = EINVAL; 430 else 431 V_dctcp_alpha = new; 432 } 433 434 return (error); 435 } 436 437 static int 438 dctcp_shift_g_handler(SYSCTL_HANDLER_ARGS) 439 { 440 uint32_t new; 441 int error; 442 443 new = V_dctcp_shift_g; 444 error = sysctl_handle_int(oidp, &new, 0, req); 445 if (error == 0 && req->newptr != NULL) { 446 if (new > DCTCP_SHIFT) 447 error = EINVAL; 448 else 449 V_dctcp_shift_g = new; 450 } 451 452 return (error); 453 } 454 455 static int 456 dctcp_slowstart_handler(SYSCTL_HANDLER_ARGS) 457 { 458 uint32_t new; 459 int error; 460 461 new = V_dctcp_slowstart; 462 error = sysctl_handle_int(oidp, &new, 0, req); 463 if (error == 0 && req->newptr != NULL) { 464 if (new > 1) 465 error = EINVAL; 466 else 467 V_dctcp_slowstart = new; 468 } 469 470 return (error); 471 } 472 473 SYSCTL_DECL(_net_inet_tcp_cc_dctcp); 474 SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, dctcp, 475 CTLFLAG_RW | CTLFLAG_MPSAFE, NULL, 476 "dctcp congestion control related settings"); 477 478 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, alpha, 479 CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT, 480 &VNET_NAME(dctcp_alpha), 0, &dctcp_alpha_handler, "IU", 481 "dctcp alpha parameter at start of session"); 482 483 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, shift_g, 484 CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT, 485 &VNET_NAME(dctcp_shift_g), 4, &dctcp_shift_g_handler, "IU", 486 "dctcp shift parameter"); 487 488 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, slowstart, 489 CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT, 490 &VNET_NAME(dctcp_slowstart), 0, &dctcp_slowstart_handler, "IU", 491 "half CWND reduction after the first slow start"); 492 493 SYSCTL_UINT(_net_inet_tcp_cc_dctcp, OID_AUTO, ect1, 494 CTLFLAG_VNET | CTLFLAG_RW | CTLFLAG_NEEDGIANT, 495 &VNET_NAME(dctcp_ect1), 0, 496 "Send DCTCP segments with ÍP ECT(0) or ECT(1)"); 497 498 DECLARE_CC_MODULE(dctcp, &dctcp_cc_algo); 499 MODULE_VERSION(dctcp, 2); 500