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