ccid2.c 19.3 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
/*
 *  Copyright (c) 2005, 2006 Andrea Bittau <a.bittau@cs.ucl.ac.uk>
 *
 *  Changes to meet Linux coding standards, and DCCP infrastructure fixes.
 *
 *  Copyright (c) 2006 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
24
 * This implementation should follow RFC 4341
25
 */
26
#include <linux/slab.h>
27
#include "../feat.h"
28 29 30
#include "ccid2.h"


31
#ifdef CONFIG_IP_DCCP_CCID2_DEBUG
32 33
static int ccid2_debug;
#define ccid2_pr_debug(format, a...)	DCCP_PR_DEBUG(ccid2_debug, format, ##a)
34
#else
35
#define ccid2_pr_debug(format, a...)
36 37
#endif

38
static int ccid2_hc_tx_alloc_seq(struct ccid2_hc_tx_sock *hc)
39 40 41 42 43
{
	struct ccid2_seq *seqp;
	int i;

	/* check if we have space to preserve the pointer to the buffer */
44 45
	if (hc->tx_seqbufc >= (sizeof(hc->tx_seqbuf) /
			       sizeof(struct ccid2_seq *)))
46 47 48
		return -ENOMEM;

	/* allocate buffer and initialize linked list */
G
Gerrit Renker 已提交
49
	seqp = kmalloc(CCID2_SEQBUF_LEN * sizeof(struct ccid2_seq), gfp_any());
50 51 52
	if (seqp == NULL)
		return -ENOMEM;

G
Gerrit Renker 已提交
53
	for (i = 0; i < (CCID2_SEQBUF_LEN - 1); i++) {
54 55 56
		seqp[i].ccid2s_next = &seqp[i + 1];
		seqp[i + 1].ccid2s_prev = &seqp[i];
	}
G
Gerrit Renker 已提交
57 58
	seqp[CCID2_SEQBUF_LEN - 1].ccid2s_next = seqp;
	seqp->ccid2s_prev = &seqp[CCID2_SEQBUF_LEN - 1];
59 60

	/* This is the first allocation.  Initiate the head and tail.  */
61 62
	if (hc->tx_seqbufc == 0)
		hc->tx_seqh = hc->tx_seqt = seqp;
63 64
	else {
		/* link the existing list with the one we just created */
65 66
		hc->tx_seqh->ccid2s_next = seqp;
		seqp->ccid2s_prev = hc->tx_seqh;
67

68 69
		hc->tx_seqt->ccid2s_prev = &seqp[CCID2_SEQBUF_LEN - 1];
		seqp[CCID2_SEQBUF_LEN - 1].ccid2s_next = hc->tx_seqt;
70 71 72
	}

	/* store the original pointer to the buffer so we can free it */
73 74
	hc->tx_seqbuf[hc->tx_seqbufc] = seqp;
	hc->tx_seqbufc++;
75 76 77 78

	return 0;
}

79
static int ccid2_hc_tx_send_packet(struct sock *sk, struct sk_buff *skb)
80
{
81
	struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
82

83
	if (hc->tx_pipe < hc->tx_cwnd)
84 85 86
		return 0;

	return 1; /* XXX CCID should dequeue when ready instead of polling */
87 88
}

89
static void ccid2_change_l_ack_ratio(struct sock *sk, u32 val)
90 91
{
	struct dccp_sock *dp = dccp_sk(sk);
92
	u32 max_ratio = DIV_ROUND_UP(ccid2_hc_tx_sk(sk)->tx_cwnd, 2);
93

94
	/*
95 96 97 98
	 * Ensure that Ack Ratio does not exceed ceil(cwnd/2), which is (2) from
	 * RFC 4341, 6.1.2. We ignore the statement that Ack Ratio 2 is always
	 * acceptable since this causes starvation/deadlock whenever cwnd < 2.
	 * The same problem arises when Ack Ratio is 0 (ie. Ack Ratio disabled).
99
	 */
100 101 102
	if (val == 0 || val > max_ratio) {
		DCCP_WARN("Limiting Ack Ratio (%u) to %u\n", val, max_ratio);
		val = max_ratio;
103
	}
104 105
	if (val > DCCPF_ACK_RATIO_MAX)
		val = DCCPF_ACK_RATIO_MAX;
106

107 108 109
	if (val == dp->dccps_l_ack_ratio)
		return;

110
	ccid2_pr_debug("changing local ack ratio to %u\n", val);
111 112 113 114 115 116
	dp->dccps_l_ack_ratio = val;
}

static void ccid2_hc_tx_rto_expire(unsigned long data)
{
	struct sock *sk = (struct sock *)data;
117
	struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
118 119 120

	bh_lock_sock(sk);
	if (sock_owned_by_user(sk)) {
121
		sk_reset_timer(sk, &hc->tx_rtotimer, jiffies + HZ / 5);
122 123 124 125 126 127
		goto out;
	}

	ccid2_pr_debug("RTO_EXPIRE\n");

	/* back-off timer */
128
	hc->tx_rto <<= 1;
129 130
	if (hc->tx_rto > DCCP_RTO_MAX)
		hc->tx_rto = DCCP_RTO_MAX;
131

132
	sk_reset_timer(sk, &hc->tx_rtotimer, jiffies + hc->tx_rto);
133 134

	/* adjust pipe, cwnd etc */
135 136 137
	hc->tx_ssthresh = hc->tx_cwnd / 2;
	if (hc->tx_ssthresh < 2)
		hc->tx_ssthresh = 2;
G
Gerrit Renker 已提交
138 139
	hc->tx_cwnd	= 1;
	hc->tx_pipe	= 0;
140 141

	/* clear state about stuff we sent */
142 143
	hc->tx_seqt = hc->tx_seqh;
	hc->tx_packets_acked = 0;
144 145

	/* clear ack ratio state. */
146 147
	hc->tx_rpseq    = 0;
	hc->tx_rpdupack = -1;
148 149 150
	ccid2_change_l_ack_ratio(sk, 1);
out:
	bh_unlock_sock(sk);
151
	sock_put(sk);
152 153
}

154
static void ccid2_hc_tx_packet_sent(struct sock *sk, int more, unsigned int len)
155 156
{
	struct dccp_sock *dp = dccp_sk(sk);
157
	struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
158
	struct ccid2_seq *next;
159

160
	hc->tx_pipe++;
161

162 163
	hc->tx_seqh->ccid2s_seq   = dp->dccps_gss;
	hc->tx_seqh->ccid2s_acked = 0;
164
	hc->tx_seqh->ccid2s_sent  = ccid2_time_stamp;
165

166
	next = hc->tx_seqh->ccid2s_next;
167
	/* check if we need to alloc more space */
168 169
	if (next == hc->tx_seqt) {
		if (ccid2_hc_tx_alloc_seq(hc)) {
G
Gerrit Renker 已提交
170 171 172 173
			DCCP_CRIT("packet history - out of memory!");
			/* FIXME: find a more graceful way to bail out */
			return;
		}
174 175
		next = hc->tx_seqh->ccid2s_next;
		BUG_ON(next == hc->tx_seqt);
176
	}
177
	hc->tx_seqh = next;
178

179
	ccid2_pr_debug("cwnd=%d pipe=%d\n", hc->tx_cwnd, hc->tx_pipe);
180

181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200
	/*
	 * FIXME: The code below is broken and the variables have been removed
	 * from the socket struct. The `ackloss' variable was always set to 0,
	 * and with arsent there are several problems:
	 *  (i) it doesn't just count the number of Acks, but all sent packets;
	 *  (ii) it is expressed in # of packets, not # of windows, so the
	 *  comparison below uses the wrong formula: Appendix A of RFC 4341
	 *  comes up with the number K = cwnd / (R^2 - R) of consecutive windows
	 *  of data with no lost or marked Ack packets. If arsent were the # of
	 *  consecutive Acks received without loss, then Ack Ratio needs to be
	 *  decreased by 1 when
	 *	      arsent >=  K * cwnd / R  =  cwnd^2 / (R^3 - R^2)
	 *  where cwnd / R is the number of Acks received per window of data
	 *  (cf. RFC 4341, App. A). The problems are that
	 *  - arsent counts other packets as well;
	 *  - the comparison uses a formula different from RFC 4341;
	 *  - computing a cubic/quadratic equation each time is too complicated.
	 *  Hence a different algorithm is needed.
	 */
#if 0
201
	/* Ack Ratio.  Need to maintain a concept of how many windows we sent */
202
	hc->tx_arsent++;
203
	/* We had an ack loss in this window... */
204 205 206 207
	if (hc->tx_ackloss) {
		if (hc->tx_arsent >= hc->tx_cwnd) {
			hc->tx_arsent  = 0;
			hc->tx_ackloss = 0;
208
		}
209 210
	} else {
		/* No acks lost up to now... */
211 212 213
		/* decrease ack ratio if enough packets were sent */
		if (dp->dccps_l_ack_ratio > 1) {
			/* XXX don't calculate denominator each time */
214 215
			int denom = dp->dccps_l_ack_ratio * dp->dccps_l_ack_ratio -
				    dp->dccps_l_ack_ratio;
216

217
			denom = hc->tx_cwnd * hc->tx_cwnd / denom;
218

219
			if (hc->tx_arsent >= denom) {
220
				ccid2_change_l_ack_ratio(sk, dp->dccps_l_ack_ratio - 1);
221
				hc->tx_arsent = 0;
222
			}
223 224
		} else {
			/* we can't increase ack ratio further [1] */
225
			hc->tx_arsent = 0; /* or maybe set it to cwnd*/
226 227
		}
	}
228
#endif
229

230
	sk_reset_timer(sk, &hc->tx_rtotimer, jiffies + hc->tx_rto);
231

232
#ifdef CONFIG_IP_DCCP_CCID2_DEBUG
233
	do {
234
		struct ccid2_seq *seqp = hc->tx_seqt;
235

236
		while (seqp != hc->tx_seqh) {
237
			ccid2_pr_debug("out seq=%llu acked=%d time=%u\n",
238
				       (unsigned long long)seqp->ccid2s_seq,
R
Randy Dunlap 已提交
239
				       seqp->ccid2s_acked, seqp->ccid2s_sent);
240 241
			seqp = seqp->ccid2s_next;
		}
242
	} while (0);
243 244 245 246
	ccid2_pr_debug("=========\n");
#endif
}

247 248 249
/* XXX Lame code duplication!
 * returns -1 if none was found.
 * else returns the next offset to use in the function call.
250
 */
251 252
static int ccid2_ackvector(struct sock *sk, struct sk_buff *skb, int offset,
			   unsigned char **vec, unsigned char *veclen)
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
	const struct dccp_hdr *dh = dccp_hdr(skb);
	unsigned char *options = (unsigned char *)dh + dccp_hdr_len(skb);
	unsigned char *opt_ptr;
	const unsigned char *opt_end = (unsigned char *)dh +
					(dh->dccph_doff * 4);
	unsigned char opt, len;
	unsigned char *value;

	BUG_ON(offset < 0);
	options += offset;
	opt_ptr = options;
	if (opt_ptr >= opt_end)
		return -1;

	while (opt_ptr != opt_end) {
		opt   = *opt_ptr++;
		len   = 0;
		value = NULL;

		/* Check if this isn't a single byte option */
		if (opt > DCCPO_MAX_RESERVED) {
			if (opt_ptr == opt_end)
				goto out_invalid_option;

			len = *opt_ptr++;
			if (len < 3)
				goto out_invalid_option;
281
			/*
282 283
			 * Remove the type and len fields, leaving
			 * just the value size
284
			 */
285 286 287
			len     -= 2;
			value   = opt_ptr;
			opt_ptr += len;
288

289 290
			if (opt_ptr > opt_end)
				goto out_invalid_option;
291 292
		}

293 294 295 296 297 298
		switch (opt) {
		case DCCPO_ACK_VECTOR_0:
		case DCCPO_ACK_VECTOR_1:
			*vec	= value;
			*veclen = len;
			return offset + (opt_ptr - options);
299 300 301
		}
	}

302
	return -1;
303

304 305 306
out_invalid_option:
	DCCP_BUG("Invalid option - this should not happen (previous parsing)!");
	return -1;
307 308
}

309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327
/**
 * ccid2_rtt_estimator - Sample RTT and compute RTO using RFC2988 algorithm
 * This code is almost identical with TCP's tcp_rtt_estimator(), since
 * - it has a higher sampling frequency (recommended by RFC 1323),
 * - the RTO does not collapse into RTT due to RTTVAR going towards zero,
 * - it is simple (cf. more complex proposals such as Eifel timer or research
 *   which suggests that the gain should be set according to window size),
 * - in tests it was found to work well with CCID2 [gerrit].
 */
static void ccid2_rtt_estimator(struct sock *sk, const long mrtt)
{
	struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
	long m = mrtt ? : 1;

	if (hc->tx_srtt == 0) {
		/* First measurement m */
		hc->tx_srtt = m << 3;
		hc->tx_mdev = m << 1;

328
		hc->tx_mdev_max = max(hc->tx_mdev, tcp_rto_min(sk));
329
		hc->tx_rttvar   = hc->tx_mdev_max;
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
		hc->tx_rtt_seq  = dccp_sk(sk)->dccps_gss;
	} else {
		/* Update scaled SRTT as SRTT += 1/8 * (m - SRTT) */
		m -= (hc->tx_srtt >> 3);
		hc->tx_srtt += m;

		/* Similarly, update scaled mdev with regard to |m| */
		if (m < 0) {
			m = -m;
			m -= (hc->tx_mdev >> 2);
			/*
			 * This neutralises RTO increase when RTT < SRTT - mdev
			 * (see P. Sarolahti, A. Kuznetsov,"Congestion Control
			 * in Linux TCP", USENIX 2002, pp. 49-62).
			 */
			if (m > 0)
				m >>= 3;
		} else {
			m -= (hc->tx_mdev >> 2);
		}
		hc->tx_mdev += m;

		if (hc->tx_mdev > hc->tx_mdev_max) {
			hc->tx_mdev_max = hc->tx_mdev;
			if (hc->tx_mdev_max > hc->tx_rttvar)
				hc->tx_rttvar = hc->tx_mdev_max;
		}

		/*
		 * Decay RTTVAR at most once per flight, exploiting that
		 *  1) pipe <= cwnd <= Sequence_Window = W  (RFC 4340, 7.5.2)
		 *  2) AWL = GSS-W+1 <= GAR <= GSS          (RFC 4340, 7.5.1)
		 * GAR is a useful bound for FlightSize = pipe.
		 * AWL is probably too low here, as it over-estimates pipe.
		 */
		if (after48(dccp_sk(sk)->dccps_gar, hc->tx_rtt_seq)) {
			if (hc->tx_mdev_max < hc->tx_rttvar)
				hc->tx_rttvar -= (hc->tx_rttvar -
						  hc->tx_mdev_max) >> 2;
			hc->tx_rtt_seq  = dccp_sk(sk)->dccps_gss;
371
			hc->tx_mdev_max = tcp_rto_min(sk);
372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389
		}
	}

	/*
	 * Set RTO from SRTT and RTTVAR
	 * As in TCP, 4 * RTTVAR >= TCP_RTO_MIN, giving a minimum RTO of 200 ms.
	 * This agrees with RFC 4341, 5:
	 *	"Because DCCP does not retransmit data, DCCP does not require
	 *	 TCP's recommended minimum timeout of one second".
	 */
	hc->tx_rto = (hc->tx_srtt >> 3) + hc->tx_rttvar;

	if (hc->tx_rto > DCCP_RTO_MAX)
		hc->tx_rto = DCCP_RTO_MAX;
}

static void ccid2_new_ack(struct sock *sk, struct ccid2_seq *seqp,
			  unsigned int *maxincr)
390
{
391
	struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
392

393 394 395 396 397
	if (hc->tx_cwnd < hc->tx_ssthresh) {
		if (*maxincr > 0 && ++hc->tx_packets_acked == 2) {
			hc->tx_cwnd += 1;
			*maxincr    -= 1;
			hc->tx_packets_acked = 0;
398
		}
399 400 401
	} else if (++hc->tx_packets_acked >= hc->tx_cwnd) {
			hc->tx_cwnd += 1;
			hc->tx_packets_acked = 0;
402
	}
403 404 405 406 407 408 409 410
	/*
	 * FIXME: RTT is sampled several times per acknowledgment (for each
	 * entry in the Ack Vector), instead of once per Ack (as in TCP SACK).
	 * This causes the RTT to be over-estimated, since the older entries
	 * in the Ack Vector have earlier sending times.
	 * The cleanest solution is to not use the ccid2s_sent field at all
	 * and instead use DCCP timestamps: requires changes in other places.
	 */
411
	ccid2_rtt_estimator(sk, ccid2_time_stamp - seqp->ccid2s_sent);
412 413 414 415
}

static void ccid2_congestion_event(struct sock *sk, struct ccid2_seq *seqp)
{
416
	struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
417

418
	if ((s32)(seqp->ccid2s_sent - hc->tx_last_cong) < 0) {
419 420
		ccid2_pr_debug("Multiple losses in an RTT---treating as one\n");
		return;
421
	}
422

423
	hc->tx_last_cong = ccid2_time_stamp;
424

425 426
	hc->tx_cwnd      = hc->tx_cwnd / 2 ? : 1U;
	hc->tx_ssthresh  = max(hc->tx_cwnd, 2U);
427 428

	/* Avoid spurious timeouts resulting from Ack Ratio > cwnd */
429 430
	if (dccp_sk(sk)->dccps_l_ack_ratio > hc->tx_cwnd)
		ccid2_change_l_ack_ratio(sk, hc->tx_cwnd);
431 432
}

433 434 435
static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
{
	struct dccp_sock *dp = dccp_sk(sk);
436
	struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
437 438
	u64 ackno, seqno;
	struct ccid2_seq *seqp;
439 440 441
	unsigned char *vector;
	unsigned char veclen;
	int offset = 0;
442 443 444 445 446 447 448 449 450 451 452
	int done = 0;
	unsigned int maxincr = 0;

	/* check reverse path congestion */
	seqno = DCCP_SKB_CB(skb)->dccpd_seq;

	/* XXX this whole "algorithm" is broken.  Need to fix it to keep track
	 * of the seqnos of the dupacks so that rpseq and rpdupack are correct
	 * -sorbo.
	 */
	/* need to bootstrap */
453 454 455
	if (hc->tx_rpdupack == -1) {
		hc->tx_rpdupack = 0;
		hc->tx_rpseq    = seqno;
456
	} else {
457
		/* check if packet is consecutive */
458 459
		if (dccp_delta_seqno(hc->tx_rpseq, seqno) == 1)
			hc->tx_rpseq = seqno;
460
		/* it's a later packet */
461 462
		else if (after48(seqno, hc->tx_rpseq)) {
			hc->tx_rpdupack++;
463 464

			/* check if we got enough dupacks */
465 466 467
			if (hc->tx_rpdupack >= NUMDUPACK) {
				hc->tx_rpdupack = -1; /* XXX lame */
				hc->tx_rpseq    = 0;
468

469
				ccid2_change_l_ack_ratio(sk, 2 * dp->dccps_l_ack_ratio);
470 471 472 473 474
			}
		}
	}

	/* check forward path congestion */
475
	/* still didn't send out new data packets */
476
	if (hc->tx_seqh == hc->tx_seqt)
477 478
		return;

479 480 481 482 483 484 485
	switch (DCCP_SKB_CB(skb)->dccpd_type) {
	case DCCP_PKT_ACK:
	case DCCP_PKT_DATAACK:
		break;
	default:
		return;
	}
486 487

	ackno = DCCP_SKB_CB(skb)->dccpd_ack_seq;
488 489
	if (after48(ackno, hc->tx_high_ack))
		hc->tx_high_ack = ackno;
A
Andrea Bittau 已提交
490

491
	seqp = hc->tx_seqt;
A
Andrea Bittau 已提交
492 493
	while (before48(seqp->ccid2s_seq, ackno)) {
		seqp = seqp->ccid2s_next;
494 495
		if (seqp == hc->tx_seqh) {
			seqp = hc->tx_seqh->ccid2s_prev;
A
Andrea Bittau 已提交
496 497 498
			break;
		}
	}
499

500 501 502 503
	/*
	 * In slow-start, cwnd can increase up to a maximum of Ack Ratio/2
	 * packets per acknowledgement. Rounding up avoids that cwnd is not
	 * advanced when Ack Ratio is 1 and gives a slight edge otherwise.
504
	 */
505
	if (hc->tx_cwnd < hc->tx_ssthresh)
506
		maxincr = DIV_ROUND_UP(dp->dccps_l_ack_ratio, 2);
507 508

	/* go through all ack vectors */
509 510
	while ((offset = ccid2_ackvector(sk, skb, offset,
					 &vector, &veclen)) != -1) {
511
		/* go through this ack vector */
512 513 514
		while (veclen--) {
			const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK;
			u64 ackno_end_rl = SUB48(ackno, rl);
515

516
			ccid2_pr_debug("ackvec start:%llu end:%llu\n",
R
Randy Dunlap 已提交
517
				       (unsigned long long)ackno,
518
				       (unsigned long long)ackno_end_rl);
519 520 521 522 523
			/* if the seqno we are analyzing is larger than the
			 * current ackno, then move towards the tail of our
			 * seqnos.
			 */
			while (after48(seqp->ccid2s_seq, ackno)) {
524
				if (seqp == hc->tx_seqt) {
525 526 527 528 529 530 531 532 533 534 535 536
					done = 1;
					break;
				}
				seqp = seqp->ccid2s_prev;
			}
			if (done)
				break;

			/* check all seqnos in the range of the vector
			 * run length
			 */
			while (between48(seqp->ccid2s_seq,ackno_end_rl,ackno)) {
537 538
				const u8 state = *vector &
						 DCCP_ACKVEC_STATE_MASK;
539 540

				/* new packet received or marked */
541
				if (state != DCCP_ACKVEC_STATE_NOT_RECEIVED &&
542
				    !seqp->ccid2s_acked) {
543 544
					if (state ==
					    DCCP_ACKVEC_STATE_ECN_MARKED) {
545
						ccid2_congestion_event(sk,
546
								       seqp);
547
					} else
548 549 550 551 552
						ccid2_new_ack(sk, seqp,
							      &maxincr);

					seqp->ccid2s_acked = 1;
					ccid2_pr_debug("Got ack for %llu\n",
R
Randy Dunlap 已提交
553
						       (unsigned long long)seqp->ccid2s_seq);
554
					hc->tx_pipe--;
555
				}
556
				if (seqp == hc->tx_seqt) {
557 558 559
					done = 1;
					break;
				}
560
				seqp = seqp->ccid2s_prev;
561 562 563 564
			}
			if (done)
				break;

565
			ackno = SUB48(ackno_end_rl, 1);
566
			vector++;
567 568 569 570 571 572 573 574
		}
		if (done)
			break;
	}

	/* The state about what is acked should be correct now
	 * Check for NUMDUPACK
	 */
575 576
	seqp = hc->tx_seqt;
	while (before48(seqp->ccid2s_seq, hc->tx_high_ack)) {
A
Andrea Bittau 已提交
577
		seqp = seqp->ccid2s_next;
578 579
		if (seqp == hc->tx_seqh) {
			seqp = hc->tx_seqh->ccid2s_prev;
A
Andrea Bittau 已提交
580 581 582
			break;
		}
	}
583 584 585 586
	done = 0;
	while (1) {
		if (seqp->ccid2s_acked) {
			done++;
587
			if (done == NUMDUPACK)
588 589
				break;
		}
590
		if (seqp == hc->tx_seqt)
591 592 593 594 595 596 597
			break;
		seqp = seqp->ccid2s_prev;
	}

	/* If there are at least 3 acknowledgements, anything unacknowledged
	 * below the last sequence number is considered lost
	 */
598
	if (done == NUMDUPACK) {
599 600 601 602 603
		struct ccid2_seq *last_acked = seqp;

		/* check for lost packets */
		while (1) {
			if (!seqp->ccid2s_acked) {
604
				ccid2_pr_debug("Packet lost: %llu\n",
R
Randy Dunlap 已提交
605
					       (unsigned long long)seqp->ccid2s_seq);
606 607 608 609
				/* XXX need to traverse from tail -> head in
				 * order to detect multiple congestion events in
				 * one ack vector.
				 */
610
				ccid2_congestion_event(sk, seqp);
611
				hc->tx_pipe--;
612
			}
613
			if (seqp == hc->tx_seqt)
614 615 616 617
				break;
			seqp = seqp->ccid2s_prev;
		}

618
		hc->tx_seqt = last_acked;
619 620 621
	}

	/* trim acked packets in tail */
622 623
	while (hc->tx_seqt != hc->tx_seqh) {
		if (!hc->tx_seqt->ccid2s_acked)
624 625
			break;

626
		hc->tx_seqt = hc->tx_seqt->ccid2s_next;
627
	}
628 629 630 631 632 633

	/* restart RTO timer if not all outstanding data has been acked */
	if (hc->tx_pipe == 0)
		sk_stop_timer(sk, &hc->tx_rtotimer);
	else
		sk_reset_timer(sk, &hc->tx_rtotimer, jiffies + hc->tx_rto);
634 635
}

636
static int ccid2_hc_tx_init(struct ccid *ccid, struct sock *sk)
637
{
638
	struct ccid2_hc_tx_sock *hc = ccid_priv(ccid);
639 640
	struct dccp_sock *dp = dccp_sk(sk);
	u32 max_ratio;
641

642
	/* RFC 4341, 5: initialise ssthresh to arbitrarily high (max) value */
643
	hc->tx_ssthresh = ~0U;
644

645 646
	/* Use larger initial windows (RFC 4341, section 5). */
	hc->tx_cwnd = rfc3390_bytes_to_packets(dp->dccps_mss_cache);
647 648

	/* Make sure that Ack Ratio is enabled and within bounds. */
649
	max_ratio = DIV_ROUND_UP(hc->tx_cwnd, 2);
650 651 652
	if (dp->dccps_l_ack_ratio == 0 || dp->dccps_l_ack_ratio > max_ratio)
		dp->dccps_l_ack_ratio = max_ratio;

653
	/* XXX init ~ to window size... */
654
	if (ccid2_hc_tx_alloc_seq(hc))
655
		return -ENOMEM;
656

657
	hc->tx_rto	 = DCCP_TIMEOUT_INIT;
658
	hc->tx_rpdupack  = -1;
659
	hc->tx_last_cong = ccid2_time_stamp;
660
	setup_timer(&hc->tx_rtotimer, ccid2_hc_tx_rto_expire,
661
			(unsigned long)sk);
662 663 664 665 666
	return 0;
}

static void ccid2_hc_tx_exit(struct sock *sk)
{
667
	struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
668
	int i;
669

670
	sk_stop_timer(sk, &hc->tx_rtotimer);
671

672 673 674
	for (i = 0; i < hc->tx_seqbufc; i++)
		kfree(hc->tx_seqbuf[i]);
	hc->tx_seqbufc = 0;
675 676 677 678 679
}

static void ccid2_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
{
	const struct dccp_sock *dp = dccp_sk(sk);
680
	struct ccid2_hc_rx_sock *hc = ccid2_hc_rx_sk(sk);
681 682 683 684

	switch (DCCP_SKB_CB(skb)->dccpd_type) {
	case DCCP_PKT_DATA:
	case DCCP_PKT_DATAACK:
685 686
		hc->rx_data++;
		if (hc->rx_data >= dp->dccps_r_ack_ratio) {
687
			dccp_send_ack(sk);
688
			hc->rx_data = 0;
689 690 691 692 693
		}
		break;
	}
}

694
struct ccid_operations ccid2_ops = {
695 696 697 698 699 700 701 702 703 704
	.ccid_id		= DCCPC_CCID2,
	.ccid_name		= "TCP-like",
	.ccid_hc_tx_obj_size	= sizeof(struct ccid2_hc_tx_sock),
	.ccid_hc_tx_init	= ccid2_hc_tx_init,
	.ccid_hc_tx_exit	= ccid2_hc_tx_exit,
	.ccid_hc_tx_send_packet	= ccid2_hc_tx_send_packet,
	.ccid_hc_tx_packet_sent	= ccid2_hc_tx_packet_sent,
	.ccid_hc_tx_packet_recv	= ccid2_hc_tx_packet_recv,
	.ccid_hc_rx_obj_size	= sizeof(struct ccid2_hc_rx_sock),
	.ccid_hc_rx_packet_recv	= ccid2_hc_rx_packet_recv,
705 706
};

707
#ifdef CONFIG_IP_DCCP_CCID2_DEBUG
708
module_param(ccid2_debug, bool, 0644);
709
MODULE_PARM_DESC(ccid2_debug, "Enable CCID-2 debug messages");
710
#endif