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