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 DCTCP_SHIFT 10 60 #define MAX_ALPHA_VALUE (1<<DCTCP_SHIFT) 61 VNET_DEFINE_STATIC(uint32_t, dctcp_alpha) = MAX_ALPHA_VALUE; 62 #define V_dctcp_alpha VNET(dctcp_alpha) 63 VNET_DEFINE_STATIC(uint32_t, dctcp_shift_g) = 4; 64 #define V_dctcp_shift_g VNET(dctcp_shift_g) 65 VNET_DEFINE_STATIC(uint32_t, dctcp_slowstart) = 0; 66 #define V_dctcp_slowstart VNET(dctcp_slowstart) 67 68 struct dctcp { 69 uint32_t bytes_ecn; /* # of marked bytes during a RTT */ 70 uint32_t bytes_total; /* # of acked bytes during a RTT */ 71 int alpha; /* the fraction of marked bytes */ 72 int ce_prev; /* CE state of the last segment */ 73 tcp_seq save_sndnxt; /* end sequence number of the current window */ 74 int ece_curr; /* ECE flag in this segment */ 75 int ece_prev; /* ECE flag in the last segment */ 76 uint32_t num_cong_events; /* # of congestion events */ 77 }; 78 79 static MALLOC_DEFINE(M_dctcp, "dctcp data", 80 "Per connection data required for the dctcp algorithm"); 81 82 static void dctcp_ack_received(struct cc_var *ccv, uint16_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); 86 static void dctcp_cong_signal(struct cc_var *ccv, uint32_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 92 struct cc_algo dctcp_cc_algo = { 93 .name = "dctcp", 94 .ack_received = dctcp_ack_received, 95 .cb_destroy = dctcp_cb_destroy, 96 .cb_init = dctcp_cb_init, 97 .cong_signal = dctcp_cong_signal, 98 .conn_init = dctcp_conn_init, 99 .post_recovery = dctcp_post_recovery, 100 .ecnpkt_handler = dctcp_ecnpkt_handler, 101 .after_idle = dctcp_after_idle, 102 }; 103 104 static void 105 dctcp_ack_received(struct cc_var *ccv, uint16_t type) 106 { 107 struct dctcp *dctcp_data; 108 int bytes_acked = 0; 109 110 dctcp_data = ccv->cc_data; 111 112 if (CCV(ccv, t_flags2) & TF2_ECN_PERMIT) { 113 /* 114 * DCTCP doesn't treat receipt of ECN marked packet as a 115 * congestion event. Thus, DCTCP always executes the ACK 116 * processing out of congestion recovery. 117 */ 118 if (IN_CONGRECOVERY(CCV(ccv, t_flags))) { 119 EXIT_CONGRECOVERY(CCV(ccv, t_flags)); 120 newreno_cc_algo.ack_received(ccv, type); 121 ENTER_CONGRECOVERY(CCV(ccv, t_flags)); 122 } else 123 newreno_cc_algo.ack_received(ccv, type); 124 125 if (type == CC_DUPACK) 126 bytes_acked = min(ccv->bytes_this_ack, CCV(ccv, t_maxseg)); 127 128 if (type == CC_ACK) 129 bytes_acked = ccv->bytes_this_ack; 130 131 /* Update total bytes. */ 132 dctcp_data->bytes_total += bytes_acked; 133 134 /* Update total marked bytes. */ 135 if (dctcp_data->ece_curr) { 136 //XXRMS: For fluid-model DCTCP, update 137 //cwnd here during for RTT fairness 138 if (!dctcp_data->ece_prev 139 && bytes_acked > CCV(ccv, t_maxseg)) { 140 dctcp_data->bytes_ecn += 141 (bytes_acked - CCV(ccv, t_maxseg)); 142 } else 143 dctcp_data->bytes_ecn += bytes_acked; 144 dctcp_data->ece_prev = 1; 145 } else { 146 if (dctcp_data->ece_prev 147 && bytes_acked > CCV(ccv, t_maxseg)) 148 dctcp_data->bytes_ecn += CCV(ccv, t_maxseg); 149 dctcp_data->ece_prev = 0; 150 } 151 dctcp_data->ece_curr = 0; 152 153 /* 154 * Update the fraction of marked bytes at the end of 155 * current window size. 156 */ 157 if (!IN_FASTRECOVERY(CCV(ccv, t_flags)) && 158 SEQ_GT(ccv->curack, dctcp_data->save_sndnxt)) 159 dctcp_update_alpha(ccv); 160 } else 161 newreno_cc_algo.ack_received(ccv, type); 162 } 163 164 static void 165 dctcp_after_idle(struct cc_var *ccv) 166 { 167 struct dctcp *dctcp_data; 168 169 if (CCV(ccv, t_flags2) & TF2_ECN_PERMIT) { 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 182 newreno_cc_algo.after_idle(ccv); 183 } 184 185 static void 186 dctcp_cb_destroy(struct cc_var *ccv) 187 { 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 cwin, mss; 234 235 if (CCV(ccv, t_flags2) & TF2_ECN_PERMIT) { 236 dctcp_data = ccv->cc_data; 237 cwin = CCV(ccv, snd_cwnd); 238 mss = tcp_maxseg(ccv->ccvc.tcp); 239 240 switch (type) { 241 case CC_NDUPACK: 242 if (!IN_FASTRECOVERY(CCV(ccv, t_flags))) { 243 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) { 244 CCV(ccv, snd_ssthresh) = 245 max(cwin / 2, 2 * mss); 246 dctcp_data->num_cong_events++; 247 } else { 248 /* cwnd has already updated as congestion 249 * recovery. Reverse cwnd value using 250 * snd_cwnd_prev and recalculate snd_ssthresh 251 */ 252 cwin = CCV(ccv, snd_cwnd_prev); 253 CCV(ccv, snd_ssthresh) = 254 max(cwin / 2, 2 * mss); 255 } 256 ENTER_RECOVERY(CCV(ccv, t_flags)); 257 } 258 break; 259 case CC_ECN: 260 /* 261 * Save current snd_cwnd when the host encounters both 262 * congestion recovery and fast recovery. 263 */ 264 CCV(ccv, snd_cwnd_prev) = cwin; 265 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) { 266 if (V_dctcp_slowstart && 267 dctcp_data->num_cong_events++ == 0) { 268 CCV(ccv, snd_ssthresh) = 269 max(cwin / 2, 2 * mss); 270 dctcp_data->alpha = MAX_ALPHA_VALUE; 271 dctcp_data->bytes_ecn = 0; 272 dctcp_data->bytes_total = 0; 273 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt); 274 } else 275 CCV(ccv, snd_ssthresh) = 276 max((cwin - (((uint64_t)cwin * 277 dctcp_data->alpha) >> (DCTCP_SHIFT+1))), 278 2 * mss); 279 CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh); 280 ENTER_CONGRECOVERY(CCV(ccv, t_flags)); 281 } 282 dctcp_data->ece_curr = 1; 283 break; 284 case CC_RTO: 285 CCV(ccv, snd_ssthresh) = max(min(CCV(ccv, snd_wnd), 286 CCV(ccv, snd_cwnd)) / 2 / mss, 287 2) * mss; 288 CCV(ccv, snd_cwnd) = mss; 289 dctcp_update_alpha(ccv); 290 dctcp_data->save_sndnxt += CCV(ccv, t_maxseg); 291 dctcp_data->num_cong_events++; 292 break; 293 } 294 } else 295 newreno_cc_algo.cong_signal(ccv, type); 296 } 297 298 static void 299 dctcp_conn_init(struct cc_var *ccv) 300 { 301 struct dctcp *dctcp_data; 302 303 dctcp_data = ccv->cc_data; 304 305 if (CCV(ccv, t_flags2) & TF2_ECN_PERMIT) 306 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt); 307 } 308 309 /* 310 * Perform any necessary tasks before we exit congestion recovery. 311 */ 312 static void 313 dctcp_post_recovery(struct cc_var *ccv) 314 { 315 newreno_cc_algo.post_recovery(ccv); 316 317 if (CCV(ccv, t_flags2) & TF2_ECN_PERMIT) 318 dctcp_update_alpha(ccv); 319 } 320 321 /* 322 * Execute an additional ECN processing using ECN field in IP header 323 * and the CWR bit in TCP header. 324 */ 325 static void 326 dctcp_ecnpkt_handler(struct cc_var *ccv) 327 { 328 struct dctcp *dctcp_data; 329 uint32_t ccflag; 330 int acknow; 331 332 dctcp_data = ccv->cc_data; 333 ccflag = ccv->flags; 334 acknow = 0; 335 336 /* 337 * DCTCP responds with an ACK immediately when the CE state 338 * in between this segment and the last segment has changed. 339 */ 340 if (ccflag & CCF_IPHDR_CE) { 341 if (!dctcp_data->ce_prev) { 342 acknow = 1; 343 dctcp_data->ce_prev = 1; 344 CCV(ccv, t_flags2) |= TF2_ECN_SND_ECE; 345 } 346 } else { 347 if (dctcp_data->ce_prev) { 348 acknow = 1; 349 dctcp_data->ce_prev = 0; 350 CCV(ccv, t_flags2) &= ~TF2_ECN_SND_ECE; 351 } 352 } 353 354 if ((acknow) || (ccflag & CCF_TCPHDR_CWR)) { 355 ccv->flags |= CCF_ACKNOW; 356 } else { 357 ccv->flags &= ~CCF_ACKNOW; 358 } 359 } 360 361 /* 362 * Update the fraction of marked bytes represented as 'alpha'. 363 * Also initialize several internal parameters at the end of this function. 364 */ 365 static void 366 dctcp_update_alpha(struct cc_var *ccv) 367 { 368 struct dctcp *dctcp_data; 369 int alpha_prev; 370 371 dctcp_data = ccv->cc_data; 372 alpha_prev = dctcp_data->alpha; 373 dctcp_data->bytes_total = max(dctcp_data->bytes_total, 1); 374 375 /* 376 * Update alpha: alpha = (1 - g) * alpha + g * M. 377 * Here: 378 * g is weight factor 379 * recommaded to be set to 1/16 380 * small g = slow convergence between competitive DCTCP flows 381 * large g = impacts low utilization of bandwidth at switches 382 * M is fraction of marked segments in last RTT 383 * updated every RTT 384 * Alpha must be round to 0 - MAX_ALPHA_VALUE. 385 */ 386 dctcp_data->alpha = ulmin(alpha_prev - (alpha_prev >> V_dctcp_shift_g) + 387 ((uint64_t)dctcp_data->bytes_ecn << (DCTCP_SHIFT - V_dctcp_shift_g)) / 388 dctcp_data->bytes_total, MAX_ALPHA_VALUE); 389 390 /* Initialize internal parameters for next alpha calculation */ 391 dctcp_data->bytes_ecn = 0; 392 dctcp_data->bytes_total = 0; 393 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt); 394 } 395 396 static int 397 dctcp_alpha_handler(SYSCTL_HANDLER_ARGS) 398 { 399 uint32_t new; 400 int error; 401 402 new = V_dctcp_alpha; 403 error = sysctl_handle_int(oidp, &new, 0, req); 404 if (error == 0 && req->newptr != NULL) { 405 if (new > MAX_ALPHA_VALUE) 406 error = EINVAL; 407 else 408 V_dctcp_alpha = new; 409 } 410 411 return (error); 412 } 413 414 static int 415 dctcp_shift_g_handler(SYSCTL_HANDLER_ARGS) 416 { 417 uint32_t new; 418 int error; 419 420 new = V_dctcp_shift_g; 421 error = sysctl_handle_int(oidp, &new, 0, req); 422 if (error == 0 && req->newptr != NULL) { 423 if (new > DCTCP_SHIFT) 424 error = EINVAL; 425 else 426 V_dctcp_shift_g = new; 427 } 428 429 return (error); 430 } 431 432 static int 433 dctcp_slowstart_handler(SYSCTL_HANDLER_ARGS) 434 { 435 uint32_t new; 436 int error; 437 438 new = V_dctcp_slowstart; 439 error = sysctl_handle_int(oidp, &new, 0, req); 440 if (error == 0 && req->newptr != NULL) { 441 if (new > 1) 442 error = EINVAL; 443 else 444 V_dctcp_slowstart = new; 445 } 446 447 return (error); 448 } 449 450 SYSCTL_DECL(_net_inet_tcp_cc_dctcp); 451 SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, dctcp, 452 CTLFLAG_RW | CTLFLAG_MPSAFE, NULL, 453 "dctcp congestion control related settings"); 454 455 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, alpha, 456 CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT, 457 &VNET_NAME(dctcp_alpha), 0, &dctcp_alpha_handler, "IU", 458 "dctcp alpha parameter at start of session"); 459 460 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, shift_g, 461 CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT, 462 &VNET_NAME(dctcp_shift_g), 4, &dctcp_shift_g_handler, "IU", 463 "dctcp shift parameter"); 464 465 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, slowstart, 466 CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT, 467 &VNET_NAME(dctcp_slowstart), 0, &dctcp_slowstart_handler, "IU", 468 "half CWND reduction after the first slow start"); 469 470 DECLARE_CC_MODULE(dctcp, &dctcp_cc_algo); 471 MODULE_VERSION(dctcp, 1); 472