Training courses

Kernel and Embedded Linux

Bootlin training courses

Embedded Linux, kernel,
Yocto Project, Buildroot, real-time,
graphics, boot time, debugging...

Bootlin logo

Elixir Cross Referencer

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
/*
 * CAIA Delay-Gradient (CDG) congestion control
 *
 * This implementation is based on the paper:
 *   D.A. Hayes and G. Armitage. "Revisiting TCP congestion control using
 *   delay gradients." In IFIP Networking, pages 328-341. Springer, 2011.
 *
 * Scavenger traffic (Less-than-Best-Effort) should disable coexistence
 * heuristics using parameters use_shadow=0 and use_ineff=0.
 *
 * Parameters window, backoff_beta, and backoff_factor are crucial for
 * throughput and delay. Future work is needed to determine better defaults,
 * and to provide guidelines for use in different environments/contexts.
 *
 * Except for window, knobs are configured via /sys/module/tcp_cdg/parameters/.
 * Parameter window is only configurable when loading tcp_cdg as a module.
 *
 * Notable differences from paper/FreeBSD:
 *   o Using Hybrid Slow start and Proportional Rate Reduction.
 *   o Add toggle for shadow window mechanism. Suggested by David Hayes.
 *   o Add toggle for non-congestion loss tolerance.
 *   o Scaling parameter G is changed to a backoff factor;
 *     conversion is given by: backoff_factor = 1000/(G * window).
 *   o Limit shadow window to 2 * cwnd, or to cwnd when application limited.
 *   o More accurate e^-x.
 */
#include <linux/kernel.h>
#include <linux/random.h>
#include <linux/module.h>
#include <net/tcp.h>

#define HYSTART_ACK_TRAIN	1
#define HYSTART_DELAY		2

static int window __read_mostly = 8;
static unsigned int backoff_beta __read_mostly = 0.7071 * 1024; /* sqrt 0.5 */
static unsigned int backoff_factor __read_mostly = 42;
static unsigned int hystart_detect __read_mostly = 3;
static unsigned int use_ineff __read_mostly = 5;
static bool use_shadow __read_mostly = true;
static bool use_tolerance __read_mostly;

module_param(window, int, 0444);
MODULE_PARM_DESC(window, "gradient window size (power of two <= 256)");
module_param(backoff_beta, uint, 0644);
MODULE_PARM_DESC(backoff_beta, "backoff beta (0-1024)");
module_param(backoff_factor, uint, 0644);
MODULE_PARM_DESC(backoff_factor, "backoff probability scale factor");
module_param(hystart_detect, uint, 0644);
MODULE_PARM_DESC(hystart_detect, "use Hybrid Slow start "
		 "(0: disabled, 1: ACK train, 2: delay threshold, 3: both)");
module_param(use_ineff, uint, 0644);
MODULE_PARM_DESC(use_ineff, "use ineffectual backoff detection (threshold)");
module_param(use_shadow, bool, 0644);
MODULE_PARM_DESC(use_shadow, "use shadow window heuristic");
module_param(use_tolerance, bool, 0644);
MODULE_PARM_DESC(use_tolerance, "use loss tolerance heuristic");

struct cdg_minmax {
	union {
		struct {
			s32 min;
			s32 max;
		};
		u64 v64;
	};
};

enum cdg_state {
	CDG_UNKNOWN = 0,
	CDG_NONFULL = 1,
	CDG_FULL    = 2,
	CDG_BACKOFF = 3,
};

struct cdg {
	struct cdg_minmax rtt;
	struct cdg_minmax rtt_prev;
	struct cdg_minmax *gradients;
	struct cdg_minmax gsum;
	bool gfilled;
	u8  tail;
	u8  state;
	u8  delack;
	u32 rtt_seq;
	u32 undo_cwnd;
	u32 shadow_wnd;
	u16 backoff_cnt;
	u16 sample_cnt;
	s32 delay_min;
	u32 last_ack;
	u32 round_start;
};

/**
 * nexp_u32 - negative base-e exponential
 * @ux: x in units of micro
 *
 * Returns exp(ux * -1e-6) * U32_MAX.
 */
static u32 __pure nexp_u32(u32 ux)
{
	static const u16 v[] = {
		/* exp(-x)*65536-1 for x = 0, 0.000256, 0.000512, ... */
		65535,
		65518, 65501, 65468, 65401, 65267, 65001, 64470, 63422,
		61378, 57484, 50423, 38795, 22965, 8047,  987,   14,
	};
	u32 msb = ux >> 8;
	u32 res;
	int i;

	/* Cut off when ux >= 2^24 (actual result is <= 222/U32_MAX). */
	if (msb > U16_MAX)
		return 0;

	/* Scale first eight bits linearly: */
	res = U32_MAX - (ux & 0xff) * (U32_MAX / 1000000);

	/* Obtain e^(x + y + ...) by computing e^x * e^y * ...: */
	for (i = 1; msb; i++, msb >>= 1) {
		u32 y = v[i & -(msb & 1)] + U32_C(1);

		res = ((u64)res * y) >> 16;
	}

	return res;
}

/* Based on the HyStart algorithm (by Ha et al.) that is implemented in
 * tcp_cubic. Differences/experimental changes:
 *   o Using Hayes' delayed ACK filter.
 *   o Using a usec clock for the ACK train.
 *   o Reset ACK train when application limited.
 *   o Invoked at any cwnd (i.e. also when cwnd < 16).
 *   o Invoked only when cwnd < ssthresh (i.e. not when cwnd == ssthresh).
 */
static void tcp_cdg_hystart_update(struct sock *sk)
{
	struct cdg *ca = inet_csk_ca(sk);
	struct tcp_sock *tp = tcp_sk(sk);

	ca->delay_min = min_not_zero(ca->delay_min, ca->rtt.min);
	if (ca->delay_min == 0)
		return;

	if (hystart_detect & HYSTART_ACK_TRAIN) {
		u32 now_us = div_u64(local_clock(), NSEC_PER_USEC);

		if (ca->last_ack == 0 || !tcp_is_cwnd_limited(sk)) {
			ca->last_ack = now_us;
			ca->round_start = now_us;
		} else if (before(now_us, ca->last_ack + 3000)) {
			u32 base_owd = max(ca->delay_min / 2U, 125U);

			ca->last_ack = now_us;
			if (after(now_us, ca->round_start + base_owd)) {
				NET_INC_STATS(sock_net(sk),
					      LINUX_MIB_TCPHYSTARTTRAINDETECT);
				NET_ADD_STATS(sock_net(sk),
					      LINUX_MIB_TCPHYSTARTTRAINCWND,
					      tp->snd_cwnd);
				tp->snd_ssthresh = tp->snd_cwnd;
				return;
			}
		}
	}

	if (hystart_detect & HYSTART_DELAY) {
		if (ca->sample_cnt < 8) {
			ca->sample_cnt++;
		} else {
			s32 thresh = max(ca->delay_min + ca->delay_min / 8U,
					 125U);

			if (ca->rtt.min > thresh) {
				NET_INC_STATS(sock_net(sk),
					      LINUX_MIB_TCPHYSTARTDELAYDETECT);
				NET_ADD_STATS(sock_net(sk),
					      LINUX_MIB_TCPHYSTARTDELAYCWND,
					      tp->snd_cwnd);
				tp->snd_ssthresh = tp->snd_cwnd;
			}
		}
	}
}

static s32 tcp_cdg_grad(struct cdg *ca)
{
	s32 gmin = ca->rtt.min - ca->rtt_prev.min;
	s32 gmax = ca->rtt.max - ca->rtt_prev.max;
	s32 grad;

	if (ca->gradients) {
		ca->gsum.min += gmin - ca->gradients[ca->tail].min;
		ca->gsum.max += gmax - ca->gradients[ca->tail].max;
		ca->gradients[ca->tail].min = gmin;
		ca->gradients[ca->tail].max = gmax;
		ca->tail = (ca->tail + 1) & (window - 1);
		gmin = ca->gsum.min;
		gmax = ca->gsum.max;
	}

	/* We keep sums to ignore gradients during cwnd reductions;
	 * the paper's smoothed gradients otherwise simplify to:
	 * (rtt_latest - rtt_oldest) / window.
	 *
	 * We also drop division by window here.
	 */
	grad = gmin > 0 ? gmin : gmax;

	/* Extrapolate missing values in gradient window: */
	if (!ca->gfilled) {
		if (!ca->gradients && window > 1)
			grad *= window; /* Memory allocation failed. */
		else if (ca->tail == 0)
			ca->gfilled = true;
		else
			grad = (grad * window) / (int)ca->tail;
	}

	/* Backoff was effectual: */
	if (gmin <= -32 || gmax <= -32)
		ca->backoff_cnt = 0;

	if (use_tolerance) {
		/* Reduce small variations to zero: */
		gmin = DIV_ROUND_CLOSEST(gmin, 64);
		gmax = DIV_ROUND_CLOSEST(gmax, 64);

		if (gmin > 0 && gmax <= 0)
			ca->state = CDG_FULL;
		else if ((gmin > 0 && gmax > 0) || gmax < 0)
			ca->state = CDG_NONFULL;
	}
	return grad;
}

static bool tcp_cdg_backoff(struct sock *sk, u32 grad)
{
	struct cdg *ca = inet_csk_ca(sk);
	struct tcp_sock *tp = tcp_sk(sk);

	if (prandom_u32() <= nexp_u32(grad * backoff_factor))
		return false;

	if (use_ineff) {
		ca->backoff_cnt++;
		if (ca->backoff_cnt > use_ineff)
			return false;
	}

	ca->shadow_wnd = max(ca->shadow_wnd, tp->snd_cwnd);
	ca->state = CDG_BACKOFF;
	tcp_enter_cwr(sk);
	return true;
}

/* Not called in CWR or Recovery state. */
static void tcp_cdg_cong_avoid(struct sock *sk, u32 ack, u32 acked)
{
	struct cdg *ca = inet_csk_ca(sk);
	struct tcp_sock *tp = tcp_sk(sk);
	u32 prior_snd_cwnd;
	u32 incr;

	if (tcp_in_slow_start(tp) && hystart_detect)
		tcp_cdg_hystart_update(sk);

	if (after(ack, ca->rtt_seq) && ca->rtt.v64) {
		s32 grad = 0;

		if (ca->rtt_prev.v64)
			grad = tcp_cdg_grad(ca);
		ca->rtt_seq = tp->snd_nxt;
		ca->rtt_prev = ca->rtt;
		ca->rtt.v64 = 0;
		ca->last_ack = 0;
		ca->sample_cnt = 0;

		if (grad > 0 && tcp_cdg_backoff(sk, grad))
			return;
	}

	if (!tcp_is_cwnd_limited(sk)) {
		ca->shadow_wnd = min(ca->shadow_wnd, tp->snd_cwnd);
		return;
	}

	prior_snd_cwnd = tp->snd_cwnd;
	tcp_reno_cong_avoid(sk, ack, acked);

	incr = tp->snd_cwnd - prior_snd_cwnd;
	ca->shadow_wnd = max(ca->shadow_wnd, ca->shadow_wnd + incr);
}

static void tcp_cdg_acked(struct sock *sk, const struct ack_sample *sample)
{
	struct cdg *ca = inet_csk_ca(sk);
	struct tcp_sock *tp = tcp_sk(sk);

	if (sample->rtt_us <= 0)
		return;

	/* A heuristic for filtering delayed ACKs, adapted from:
	 * D.A. Hayes. "Timing enhancements to the FreeBSD kernel to support
	 * delay and rate based TCP mechanisms." TR 100219A. CAIA, 2010.
	 */
	if (tp->sacked_out == 0) {
		if (sample->pkts_acked == 1 && ca->delack) {
			/* A delayed ACK is only used for the minimum if it is
			 * provenly lower than an existing non-zero minimum.
			 */
			ca->rtt.min = min(ca->rtt.min, sample->rtt_us);
			ca->delack--;
			return;
		} else if (sample->pkts_acked > 1 && ca->delack < 5) {
			ca->delack++;
		}
	}

	ca->rtt.min = min_not_zero(ca->rtt.min, sample->rtt_us);
	ca->rtt.max = max(ca->rtt.max, sample->rtt_us);
}

static u32 tcp_cdg_ssthresh(struct sock *sk)
{
	struct cdg *ca = inet_csk_ca(sk);
	struct tcp_sock *tp = tcp_sk(sk);

	ca->undo_cwnd = tp->snd_cwnd;

	if (ca->state == CDG_BACKOFF)
		return max(2U, (tp->snd_cwnd * min(1024U, backoff_beta)) >> 10);

	if (ca->state == CDG_NONFULL && use_tolerance)
		return tp->snd_cwnd;

	ca->shadow_wnd = min(ca->shadow_wnd >> 1, tp->snd_cwnd);
	if (use_shadow)
		return max3(2U, ca->shadow_wnd, tp->snd_cwnd >> 1);
	return max(2U, tp->snd_cwnd >> 1);
}

static u32 tcp_cdg_undo_cwnd(struct sock *sk)
{
	struct cdg *ca = inet_csk_ca(sk);

	return max(tcp_sk(sk)->snd_cwnd, ca->undo_cwnd);
}

static void tcp_cdg_cwnd_event(struct sock *sk, const enum tcp_ca_event ev)
{
	struct cdg *ca = inet_csk_ca(sk);
	struct tcp_sock *tp = tcp_sk(sk);
	struct cdg_minmax *gradients;

	switch (ev) {
	case CA_EVENT_CWND_RESTART:
		gradients = ca->gradients;
		if (gradients)
			memset(gradients, 0, window * sizeof(gradients[0]));
		memset(ca, 0, sizeof(*ca));

		ca->gradients = gradients;
		ca->rtt_seq = tp->snd_nxt;
		ca->shadow_wnd = tp->snd_cwnd;
		break;
	case CA_EVENT_COMPLETE_CWR:
		ca->state = CDG_UNKNOWN;
		ca->rtt_seq = tp->snd_nxt;
		ca->rtt_prev = ca->rtt;
		ca->rtt.v64 = 0;
		break;
	default:
		break;
	}
}

static void tcp_cdg_init(struct sock *sk)
{
	struct cdg *ca = inet_csk_ca(sk);
	struct tcp_sock *tp = tcp_sk(sk);

	/* We silently fall back to window = 1 if allocation fails. */
	if (window > 1)
		ca->gradients = kcalloc(window, sizeof(ca->gradients[0]),
					GFP_NOWAIT | __GFP_NOWARN);
	ca->rtt_seq = tp->snd_nxt;
	ca->shadow_wnd = tp->snd_cwnd;
}

static void tcp_cdg_release(struct sock *sk)
{
	struct cdg *ca = inet_csk_ca(sk);

	kfree(ca->gradients);
}

struct tcp_congestion_ops tcp_cdg __read_mostly = {
	.cong_avoid = tcp_cdg_cong_avoid,
	.cwnd_event = tcp_cdg_cwnd_event,
	.pkts_acked = tcp_cdg_acked,
	.undo_cwnd = tcp_cdg_undo_cwnd,
	.ssthresh = tcp_cdg_ssthresh,
	.release = tcp_cdg_release,
	.init = tcp_cdg_init,
	.owner = THIS_MODULE,
	.name = "cdg",
};

static int __init tcp_cdg_register(void)
{
	if (backoff_beta > 1024 || window < 1 || window > 256)
		return -ERANGE;
	if (!is_power_of_2(window))
		return -EINVAL;

	BUILD_BUG_ON(sizeof(struct cdg) > ICSK_CA_PRIV_SIZE);
	tcp_register_congestion_control(&tcp_cdg);
	return 0;
}

static void __exit tcp_cdg_unregister(void)
{
	tcp_unregister_congestion_control(&tcp_cdg);
}

module_init(tcp_cdg_register);
module_exit(tcp_cdg_unregister);
MODULE_AUTHOR("Kenneth Klette Jonassen");
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("TCP CDG");