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)
61VNET_DEFINE_STATIC(uint32_t, dctcp_alpha) = MAX_ALPHA_VALUE;
62#define V_dctcp_alpha	    VNET(dctcp_alpha)
63VNET_DEFINE_STATIC(uint32_t, dctcp_shift_g) = 4;
64#define	V_dctcp_shift_g	    VNET(dctcp_shift_g)
65VNET_DEFINE_STATIC(uint32_t, dctcp_slowstart) = 0;
66#define	V_dctcp_slowstart   VNET(dctcp_slowstart)
67
68struct 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
79static MALLOC_DEFINE(M_dctcp, "dctcp data",
80    "Per connection data required for the dctcp algorithm");
81
82static void	dctcp_ack_received(struct cc_var *ccv, uint16_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);
86static void	dctcp_cong_signal(struct cc_var *ccv, uint32_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);
91
92struct 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
104static void
105dctcp_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_flags) & TF_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
164static void
165dctcp_after_idle(struct cc_var *ccv)
166{
167	struct dctcp *dctcp_data;
168
169	if (CCV(ccv, t_flags) & TF_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
185static void
186dctcp_cb_destroy(struct cc_var *ccv)
187{
188	free(ccv->cc_data, M_dctcp);
189}
190
191static int
192dctcp_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 */
229static void
230dctcp_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_flags) & TF_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
298static void
299dctcp_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_flags) & TF_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 */
312static void
313dctcp_post_recovery(struct cc_var *ccv)
314{
315	newreno_cc_algo.post_recovery(ccv);
316
317	if (CCV(ccv, t_flags) & TF_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 */
325static void
326dctcp_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) |= TF_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) &= ~TF_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 */
365static void
366dctcp_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
396static int
397dctcp_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
414static int
415dctcp_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
432static int
433dctcp_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
450SYSCTL_DECL(_net_inet_tcp_cc_dctcp);
451SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, dctcp, CTLFLAG_RW, NULL,
452    "dctcp congestion control related settings");
453
454SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, alpha,
455    CTLFLAG_VNET|CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(dctcp_alpha), 0,
456    &dctcp_alpha_handler,
457    "IU", "dctcp alpha parameter at start of session");
458
459SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, shift_g,
460    CTLFLAG_VNET|CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(dctcp_shift_g), 4,
461    &dctcp_shift_g_handler,
462    "IU", "dctcp shift parameter");
463
464SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, slowstart,
465    CTLFLAG_VNET|CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(dctcp_slowstart), 0,
466    &dctcp_slowstart_handler,
467    "IU", "half CWND reduction after the first slow start");
468
469DECLARE_CC_MODULE(dctcp, &dctcp_cc_algo);
470MODULE_VERSION(dctcp, 1);
471