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