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)
62VNET_DEFINE_STATIC(uint32_t, dctcp_alpha) = MAX_ALPHA_VALUE;
63#define V_dctcp_alpha	    VNET(dctcp_alpha)
64VNET_DEFINE_STATIC(uint32_t, dctcp_shift_g) = 4;
65#define	V_dctcp_shift_g	    VNET(dctcp_shift_g)
66VNET_DEFINE_STATIC(uint32_t, dctcp_slowstart) = 0;
67#define	V_dctcp_slowstart   VNET(dctcp_slowstart)
68VNET_DEFINE_STATIC(uint32_t, dctcp_ect1) = 0;
69#define	V_dctcp_ect1	    VNET(dctcp_ect1)
70
71struct 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
82static void	dctcp_ack_received(struct cc_var *ccv, ccsignal_t type);
83static void	dctcp_after_idle(struct cc_var *ccv);
84static void	dctcp_cb_destroy(struct cc_var *ccv);
85static int	dctcp_cb_init(struct cc_var *ccv, void *ptr);
86static void	dctcp_cong_signal(struct cc_var *ccv, ccsignal_t type);
87static void	dctcp_conn_init(struct cc_var *ccv);
88static void	dctcp_post_recovery(struct cc_var *ccv);
89static void	dctcp_ecnpkt_handler(struct cc_var *ccv);
90static void	dctcp_update_alpha(struct cc_var *ccv);
91static size_t	dctcp_data_sz(void);
92
93struct 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
106static void
107dctcp_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
166static size_t
167dctcp_data_sz(void)
168{
169	return (sizeof(struct dctcp));
170}
171
172static void
173dctcp_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
193static void
194dctcp_cb_destroy(struct cc_var *ccv)
195{
196	free(ccv->cc_data, M_CC_MEM);
197}
198
199static int
200dctcp_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 */
239static void
240dctcp_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
318static void
319dctcp_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 */
335static void
336dctcp_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 */
348static void
349dctcp_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 */
388static void
389dctcp_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
419static int
420dctcp_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
437static int
438dctcp_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
455static int
456dctcp_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
473SYSCTL_DECL(_net_inet_tcp_cc_dctcp);
474SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, dctcp,
475    CTLFLAG_RW | CTLFLAG_MPSAFE, NULL,
476    "dctcp congestion control related settings");
477
478SYSCTL_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
483SYSCTL_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
488SYSCTL_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
493SYSCTL_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
498DECLARE_CC_MODULE(dctcp, &dctcp_cc_algo);
499MODULE_VERSION(dctcp, 2);
500