options.c 22.4 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 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
/*
 *  net/dccp/options.c
 *
 *  An implementation of the DCCP protocol
 *  Aristeu Sergio Rozanski Filho <aris@cathedrallabs.org>
 *  Arnaldo Carvalho de Melo <acme@ghostprotocols.net>
 *
 *      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.
 */
#include <linux/config.h>
#include <linux/dccp.h>
#include <linux/module.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/skbuff.h>

#include "ccid.h"
#include "dccp.h"

static void dccp_ackpkts_check_rcv_ackvector(struct dccp_ackpkts *ap,
					     struct sock *sk,
					     const u64 ackno,
					     const unsigned char len,
					     const unsigned char *vector);

/* stores the default values for new connection. may be changed with sysctl */
static const struct dccp_options dccpo_default_values = {
	.dccpo_sequence_window	  = DCCPF_INITIAL_SEQUENCE_WINDOW,
	.dccpo_ccid		  = DCCPF_INITIAL_CCID,
	.dccpo_send_ack_vector	  = DCCPF_INITIAL_SEND_ACK_VECTOR,
	.dccpo_send_ndp_count	  = DCCPF_INITIAL_SEND_NDP_COUNT,
};

void dccp_options_init(struct dccp_options *dccpo)
{
	memcpy(dccpo, &dccpo_default_values, sizeof(*dccpo));
}

static u32 dccp_decode_value_var(const unsigned char *bf, const u8 len)
{
	u32 value = 0;

	if (len > 3)
		value += *bf++ << 24;
	if (len > 2)
		value += *bf++ << 16;
	if (len > 1)
		value += *bf++ << 8;
	if (len > 0)
		value += *bf;

	return value;
}

int dccp_parse_options(struct sock *sk, struct sk_buff *skb)
{
	struct dccp_sock *dp = dccp_sk(sk);
61
#ifdef CONFIG_IP_DCCP_DEBUG
62 63
	const char *debug_prefix = dp->dccps_role == DCCP_ROLE_CLIENT ?
					"CLIENT rx opt: " : "server rx opt: ";
64 65 66 67 68
#endif
	const struct dccp_hdr *dh = dccp_hdr(skb);
	const u8 pkt_type = DCCP_SKB_CB(skb)->dccpd_type;
	unsigned char *options = (unsigned char *)dh + dccp_hdr_len(skb);
	unsigned char *opt_ptr = options;
69 70
	const unsigned char *opt_end = (unsigned char *)dh +
					(dh->dccph_doff * 4);
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
	struct dccp_options_received *opt_recv = &dp->dccps_options_received;
	unsigned char opt, len;
	unsigned char *value;

	memset(opt_recv, 0, sizeof(*opt_recv));

	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;
			/*
			 * Remove the type and len fields, leaving
			 * just the value size
			 */
			len	-= 2;
			value	= opt_ptr;
			opt_ptr += len;

			if (opt_ptr > opt_end)
				goto out_invalid_option;
		}

		switch (opt) {
		case DCCPO_PADDING:
			break;
		case DCCPO_NDP_COUNT:
			if (len > 3)
				goto out_invalid_option;

			opt_recv->dccpor_ndp = dccp_decode_value_var(value, len);
110 111
			dccp_pr_debug("%sNDP count=%d\n", debug_prefix,
				      opt_recv->dccpor_ndp);
112 113 114 115 116 117 118 119 120 121 122 123
			break;
		case DCCPO_ACK_VECTOR_0:
			if (len > DCCP_MAX_ACK_VECTOR_LEN)
				goto out_invalid_option;

			if (pkt_type == DCCP_PKT_DATA)
				continue;

			opt_recv->dccpor_ack_vector_len = len;
			opt_recv->dccpor_ack_vector_idx = value - options;

			dccp_pr_debug("%sACK vector 0, len=%d, ack_ackno=%llu\n",
124 125 126
				      debug_prefix, len,
				      (unsigned long long)
				      DCCP_SKB_CB(skb)->dccpd_ack_seq);
127 128
			dccp_ackvector_print(DCCP_SKB_CB(skb)->dccpd_ack_seq,
					     value, len);
129 130 131
			dccp_ackpkts_check_rcv_ackvector(dp->dccps_hc_rx_ackpkts,
							 sk,
						 DCCP_SKB_CB(skb)->dccpd_ack_seq,
132 133 134 135 136 137 138 139 140 141 142 143 144
							 len, value);
			break;
		case DCCPO_TIMESTAMP:
			if (len != 4)
				goto out_invalid_option;

			opt_recv->dccpor_timestamp = ntohl(*(u32 *)value);

			dp->dccps_timestamp_echo = opt_recv->dccpor_timestamp;
			dp->dccps_timestamp_time = jiffies;

			dccp_pr_debug("%sTIMESTAMP=%u, ackno=%llu\n",
				      debug_prefix, opt_recv->dccpor_timestamp,
145
				      (unsigned long long)
146 147 148 149 150 151 152 153
				      DCCP_SKB_CB(skb)->dccpd_ack_seq);
			break;
		case DCCPO_TIMESTAMP_ECHO:
			if (len < 4 || len > 8)
				goto out_invalid_option;

			opt_recv->dccpor_timestamp_echo = ntohl(*(u32 *)value);

154 155 156 157
			dccp_pr_debug("%sTIMESTAMP_ECHO=%u, len=%d, ackno=%llu, "
				      "diff=%u\n",
				      debug_prefix,
				      opt_recv->dccpor_timestamp_echo,
158 159 160
				      len + 2,
				      (unsigned long long)
				      DCCP_SKB_CB(skb)->dccpd_ack_seq,
161 162 163 164 165 166 167 168
				      (tcp_time_stamp -
				       opt_recv->dccpor_timestamp_echo));

			opt_recv->dccpor_elapsed_time =
					dccp_decode_value_var(value + 4,
							     len - 4);
			dccp_pr_debug("%sTIMESTAMP_ECHO ELAPSED_TIME=%d\n",
				      debug_prefix,
169 170 171 172 173 174 175 176
				      opt_recv->dccpor_elapsed_time);
			break;
		case DCCPO_ELAPSED_TIME:
			if (len > 4)
				goto out_invalid_option;

			if (pkt_type == DCCP_PKT_DATA)
				continue;
177 178
			opt_recv->dccpor_elapsed_time =
					dccp_decode_value_var(value, len);
179 180 181 182 183 184
			dccp_pr_debug("%sELAPSED_TIME=%d\n", debug_prefix,
				      opt_recv->dccpor_elapsed_time);
			break;
			/*
			 * From draft-ietf-dccp-spec-11.txt:
			 *
185 186 187 188 189
			 *	Option numbers 128 through 191 are for
			 *	options sent from the HC-Sender to the
			 *	HC-Receiver; option numbers 192 through 255
			 *	are for options sent from the HC-Receiver to
			 *	the HC-Sender.
190 191 192 193
			 */
		case 128 ... 191: {
			const u16 idx = value - options;

194 195 196
			if (ccid_hc_rx_parse_options(dp->dccps_hc_rx_ccid, sk,
						     opt, len, idx,
						     value) != 0)
197 198 199 200 201 202
				goto out_invalid_option;
		}
			break;
		case 192 ... 255: {
			const u16 idx = value - options;

203 204 205
			if (ccid_hc_tx_parse_options(dp->dccps_hc_tx_ccid, sk,
						     opt, len, idx,
						     value) != 0)
206 207 208 209
				goto out_invalid_option;
		}
			break;
		default:
210 211
			pr_info("DCCP(%p): option %d(len=%d) not "
				"implemented, ignoring\n",
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
				sk, opt, len);
			break;
	        }
	}

	return 0;

out_invalid_option:
	DCCP_INC_STATS_BH(DCCP_MIB_INVALIDOPT);
	DCCP_SKB_CB(skb)->dccpd_reset_code = DCCP_RESET_CODE_OPTION_ERROR;
	pr_info("DCCP(%p): invalid option %d, len=%d\n", sk, opt, len);
	return -1;
}

static void dccp_encode_value_var(const u32 value, unsigned char *to,
				  const unsigned int len)
{
	if (len > 3)
		*to++ = (value & 0xFF000000) >> 24;
	if (len > 2)
		*to++ = (value & 0xFF0000) >> 16;
	if (len > 1)
		*to++ = (value & 0xFF00) >> 8;
	if (len > 0)
		*to++ = (value & 0xFF);
}

static inline int dccp_ndp_len(const int ndp)
{
	return likely(ndp <= 0xFF) ? 1 : ndp <= 0xFFFF ? 2 : 3;
}

void dccp_insert_option(struct sock *sk, struct sk_buff *skb,
			const unsigned char option,
			const void *value, const unsigned char len)
{
	unsigned char *to;

	if (DCCP_SKB_CB(skb)->dccpd_opt_len + len + 2 > DCCP_MAX_OPT_LEN) {
251 252
		LIMIT_NETDEBUG(KERN_INFO "DCCP: packet too small to insert "
			       "%d option!\n", option);
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
		return;
	}

	DCCP_SKB_CB(skb)->dccpd_opt_len += len + 2;

	to    = skb_push(skb, len + 2);
	*to++ = option;
	*to++ = len + 2;

	memcpy(to, value, len);
}

EXPORT_SYMBOL_GPL(dccp_insert_option);

static void dccp_insert_option_ndp(struct sock *sk, struct sk_buff *skb)
{
	struct dccp_sock *dp = dccp_sk(sk);
	int ndp = dp->dccps_ndp_count;

	if (dccp_non_data_packet(skb))
		++dp->dccps_ndp_count;
	else
		dp->dccps_ndp_count = 0;

	if (ndp > 0) {
		unsigned char *ptr;
		const int ndp_len = dccp_ndp_len(ndp);
		const int len = ndp_len + 2;

		if (DCCP_SKB_CB(skb)->dccpd_opt_len + len > DCCP_MAX_OPT_LEN)
			return;

		DCCP_SKB_CB(skb)->dccpd_opt_len += len;

		ptr = skb_push(skb, len);
		*ptr++ = DCCPO_NDP_COUNT;
		*ptr++ = len;
		dccp_encode_value_var(ndp, ptr, ndp_len);
	}
}

static inline int dccp_elapsed_time_len(const u32 elapsed_time)
{
296
	return elapsed_time == 0 ? 0 : elapsed_time <= 0xFFFF ? 2 : 4;
297 298 299 300 301 302
}

void dccp_insert_option_elapsed_time(struct sock *sk,
				     struct sk_buff *skb,
				     u32 elapsed_time)
{
303
#ifdef CONFIG_IP_DCCP_DEBUG
304
	struct dccp_sock *dp = dccp_sk(sk);
305 306
	const char *debug_prefix = dp->dccps_role == DCCP_ROLE_CLIENT ?
					"CLIENT TX opt: " : "server TX opt: ";
307 308 309 310 311 312 313 314 315 316
#endif
	const int elapsed_time_len = dccp_elapsed_time_len(elapsed_time);
	const int len = 2 + elapsed_time_len;
	unsigned char *to;

	/* If elapsed_time == 0... */
	if (elapsed_time_len == 2)
		return;

	if (DCCP_SKB_CB(skb)->dccpd_opt_len + len > DCCP_MAX_OPT_LEN) {
317 318
		LIMIT_NETDEBUG(KERN_INFO "DCCP: packet too small to "
					 "insert elapsed time!\n");
319 320 321 322 323 324 325 326 327 328 329 330 331
		return;
	}

	DCCP_SKB_CB(skb)->dccpd_opt_len += len;

	to    = skb_push(skb, len);
	*to++ = DCCPO_ELAPSED_TIME;
	*to++ = len;

	dccp_encode_value_var(elapsed_time, to, elapsed_time_len);

	dccp_pr_debug("%sELAPSED_TIME=%u, len=%d, seqno=%llu\n",
		      debug_prefix, elapsed_time,
332 333
		      len,
		      (unsigned long long) DCCP_SKB_CB(skb)->dccpd_seq);
334 335 336 337 338 339 340
}

EXPORT_SYMBOL(dccp_insert_option_elapsed_time);

static void dccp_insert_option_ack_vector(struct sock *sk, struct sk_buff *skb)
{
	struct dccp_sock *dp = dccp_sk(sk);
341
#ifdef CONFIG_IP_DCCP_DEBUG
342 343
	const char *debug_prefix = dp->dccps_role == DCCP_ROLE_CLIENT ?
					"CLIENT TX opt: " : "server TX opt: ";
344 345 346 347 348 349 350 351 352 353
#endif
	struct dccp_ackpkts *ap = dp->dccps_hc_rx_ackpkts;
	int len = ap->dccpap_buf_vector_len + 2;
	const u32 elapsed_time = jiffies_to_usecs(jiffies - ap->dccpap_time) / 10;
	unsigned char *to, *from;

	if (elapsed_time != 0)
		dccp_insert_option_elapsed_time(sk, skb, elapsed_time);

	if (DCCP_SKB_CB(skb)->dccpd_opt_len + len > DCCP_MAX_OPT_LEN) {
354 355
		LIMIT_NETDEBUG(KERN_INFO "DCCP: packet too small to "
					 "insert ACK Vector!\n");
356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379
		return;
	}

	/*
	 * XXX: now we have just one ack vector sent record, so
	 * we have to wait for it to be cleared.
	 *
	 * Of course this is not acceptable, but this is just for
	 * basic testing now.
	 */
	if (ap->dccpap_ack_seqno != DCCP_MAX_SEQNO + 1)
		return;

	DCCP_SKB_CB(skb)->dccpd_opt_len += len;

	to    = skb_push(skb, len);
	*to++ = DCCPO_ACK_VECTOR_0;
	*to++ = len;

	len  = ap->dccpap_buf_vector_len;
	from = ap->dccpap_buf + ap->dccpap_buf_head;

	/* Check if buf_head wraps */
	if (ap->dccpap_buf_head + len > ap->dccpap_buf_len) {
380 381
		const unsigned int tailsize = (ap->dccpap_buf_len -
					       ap->dccpap_buf_head);
382 383 384 385 386 387 388 389 390 391 392 393 394 395

		memcpy(to, from, tailsize);
		to   += tailsize;
		len  -= tailsize;
		from = ap->dccpap_buf;
	}

	memcpy(to, from, len);
	/*
	 *	From draft-ietf-dccp-spec-11.txt:
	 *
	 *	For each acknowledgement it sends, the HC-Receiver will add an
	 *	acknowledgement record.  ack_seqno will equal the HC-Receiver
	 *	sequence number it used for the ack packet; ack_ptr will equal
396 397
	 *	buf_head; ack_ackno will equal buf_ackno; and ack_nonce will
	 *	equal buf_nonce.
398 399 400 401 402 403 404 405 406
	 *
	 * This implemention uses just one ack record for now.
	 */
	ap->dccpap_ack_seqno	  = DCCP_SKB_CB(skb)->dccpd_seq;
	ap->dccpap_ack_ptr	  = ap->dccpap_buf_head;
	ap->dccpap_ack_ackno	  = ap->dccpap_buf_ackno;
	ap->dccpap_ack_nonce	  = ap->dccpap_buf_nonce;
	ap->dccpap_ack_vector_len = ap->dccpap_buf_vector_len;

407 408
	dccp_pr_debug("%sACK Vector 0, len=%d, ack_seqno=%llu, "
		      "ack_ackno=%llu\n",
409
		      debug_prefix, ap->dccpap_ack_vector_len,
410 411
		      (unsigned long long) ap->dccpap_ack_seqno,
		      (unsigned long long) ap->dccpap_ack_ackno);
412 413
}

414 415
static inline void dccp_insert_option_timestamp(struct sock *sk,
						struct sk_buff *skb)
416 417 418 419 420
{
	const u32 now = htonl(tcp_time_stamp);
	dccp_insert_option(sk, skb, DCCPO_TIMESTAMP, &now, sizeof(now));
}

421 422
static void dccp_insert_option_timestamp_echo(struct sock *sk,
					      struct sk_buff *skb)
423 424
{
	struct dccp_sock *dp = dccp_sk(sk);
425
#ifdef CONFIG_IP_DCCP_DEBUG
426 427
	const char *debug_prefix = dp->dccps_role == DCCP_ROLE_CLIENT ?
					"CLIENT TX opt: " : "server TX opt: ";
428 429
#endif
	u32 tstamp_echo;
430 431
	const u32 elapsed_time = jiffies_to_usecs(jiffies -
						  dp->dccps_timestamp_time) / 10;
432 433 434 435 436
	const int elapsed_time_len = dccp_elapsed_time_len(elapsed_time);
	const int len = 6 + elapsed_time_len;
	unsigned char *to;

	if (DCCP_SKB_CB(skb)->dccpd_opt_len + len > DCCP_MAX_OPT_LEN) {
437 438
		LIMIT_NETDEBUG(KERN_INFO "DCCP: packet too small to insert "
					 "timestamp echo!\n");
439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454
		return;
	}

	DCCP_SKB_CB(skb)->dccpd_opt_len += len;

	to    = skb_push(skb, len);
	*to++ = DCCPO_TIMESTAMP_ECHO;
	*to++ = len;

	tstamp_echo = htonl(dp->dccps_timestamp_echo);
	memcpy(to, &tstamp_echo, 4);
	to += 4;
	dccp_encode_value_var(elapsed_time, to, elapsed_time_len);

	dccp_pr_debug("%sTIMESTAMP_ECHO=%u, len=%d, seqno=%llu\n",
		      debug_prefix, dp->dccps_timestamp_echo,
455 456
		      len,
		      (unsigned long long) DCCP_SKB_CB(skb)->dccpd_seq);
457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472

	dp->dccps_timestamp_echo = 0;
	dp->dccps_timestamp_time = 0;
}

void dccp_insert_options(struct sock *sk, struct sk_buff *skb)
{
	struct dccp_sock *dp = dccp_sk(sk);

	DCCP_SKB_CB(skb)->dccpd_opt_len = 0;

	if (dp->dccps_options.dccpo_send_ndp_count)
		dccp_insert_option_ndp(sk, skb);

	if (!dccp_packet_without_ack(skb)) {
		if (dp->dccps_options.dccpo_send_ack_vector &&
473 474
		    (dp->dccps_hc_rx_ackpkts->dccpap_buf_ackno !=
		     DCCP_MAX_SEQNO + 1))
475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498
			dccp_insert_option_ack_vector(sk, skb);

		dccp_insert_option_timestamp(sk, skb);
		if (dp->dccps_timestamp_echo != 0)
			dccp_insert_option_timestamp_echo(sk, skb);
	}

	ccid_hc_rx_insert_options(dp->dccps_hc_rx_ccid, sk, skb);
	ccid_hc_tx_insert_options(dp->dccps_hc_tx_ccid, sk, skb);

	/* XXX: insert other options when appropriate */

	if (DCCP_SKB_CB(skb)->dccpd_opt_len != 0) {
		/* The length of all options has to be a multiple of 4 */
		int padding = DCCP_SKB_CB(skb)->dccpd_opt_len % 4;

		if (padding != 0) {
			padding = 4 - padding;
			memset(skb_push(skb, padding), 0, padding);
			DCCP_SKB_CB(skb)->dccpd_opt_len += padding;
		}
	}
}

499 500
struct dccp_ackpkts *dccp_ackpkts_alloc(const unsigned int len,
				        const unsigned int __nocast priority)
501 502 503 504
{
	struct dccp_ackpkts *ap = kmalloc(sizeof(*ap) + len, priority);

	if (ap != NULL) {
505
#ifdef CONFIG_IP_DCCP_DEBUG
506 507
		memset(ap->dccpap_buf, 0xFF, len);
#endif
508 509 510 511 512 513 514 515 516 517
		ap->dccpap_buf_len   = len;
		ap->dccpap_buf_head  =
			ap->dccpap_buf_tail =
				ap->dccpap_buf_len - 1;
		ap->dccpap_buf_ackno =
			ap->dccpap_ack_ackno =
				ap->dccpap_ack_seqno = DCCP_MAX_SEQNO + 1;
		ap->dccpap_buf_nonce = ap->dccpap_buf_nonce = 0;
		ap->dccpap_ack_ptr   = 0;
		ap->dccpap_time	     = 0;
518 519 520 521 522 523 524 525 526
		ap->dccpap_buf_vector_len = ap->dccpap_ack_vector_len = 0;
	}

	return ap;
}

void dccp_ackpkts_free(struct dccp_ackpkts *ap)
{
	if (ap != NULL) {
527
#ifdef CONFIG_IP_DCCP_DEBUG
528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598
		memset(ap, 0xFF, sizeof(*ap) + ap->dccpap_buf_len);
#endif
		kfree(ap);
	}
}

static inline u8 dccp_ackpkts_state(const struct dccp_ackpkts *ap,
				    const unsigned int index)
{
	return ap->dccpap_buf[index] & DCCP_ACKPKTS_STATE_MASK;
}

static inline u8 dccp_ackpkts_len(const struct dccp_ackpkts *ap,
				  const unsigned int index)
{
	return ap->dccpap_buf[index] & DCCP_ACKPKTS_LEN_MASK;
}

/*
 * If several packets are missing, the HC-Receiver may prefer to enter multiple
 * bytes with run length 0, rather than a single byte with a larger run length;
 * this simplifies table updates if one of the missing packets arrives.
 */
static inline int dccp_ackpkts_set_buf_head_state(struct dccp_ackpkts *ap,
						  const unsigned int packets,
						  const unsigned char state)
{
	unsigned int gap;
	signed long new_head;

	if (ap->dccpap_buf_vector_len + packets > ap->dccpap_buf_len)
		return -ENOBUFS;

	gap	 = packets - 1;
	new_head = ap->dccpap_buf_head - packets;

	if (new_head < 0) {
		if (gap > 0) {
			memset(ap->dccpap_buf, DCCP_ACKPKTS_STATE_NOT_RECEIVED,
			       gap + new_head + 1);
			gap = -new_head;
		}
		new_head += ap->dccpap_buf_len;
	} 

	ap->dccpap_buf_head = new_head;

	if (gap > 0)
		memset(ap->dccpap_buf + ap->dccpap_buf_head + 1,
		       DCCP_ACKPKTS_STATE_NOT_RECEIVED, gap);

	ap->dccpap_buf[ap->dccpap_buf_head] = state;
	ap->dccpap_buf_vector_len += packets;
	return 0;
}

/*
 * Implements the draft-ietf-dccp-spec-11.txt Appendix A
 */
int dccp_ackpkts_add(struct dccp_ackpkts *ap, u64 ackno, u8 state)
{
	/*
	 * Check at the right places if the buffer is full, if it is, tell the
	 * caller to start dropping packets till the HC-Sender acks our ACK
	 * vectors, when we will free up space in dccpap_buf.
	 *
	 * We may well decide to do buffer compression, etc, but for now lets
	 * just drop.
	 *
	 * From Appendix A:
	 *
599 600 601 602 603 604 605 606 607 608
	 *	Of course, the circular buffer may overflow, either when the
	 *	HC-Sender is sending data at a very high rate, when the
	 *	HC-Receiver's acknowledgements are not reaching the HC-Sender,
	 *	or when the HC-Sender is forgetting to acknowledge those acks
	 *	(so the HC-Receiver is unable to clean up old state). In this
	 *	case, the HC-Receiver should either compress the buffer (by
	 *	increasing run lengths when possible), transfer its state to
	 *	a larger buffer, or, as a last resort, drop all received
	 *	packets, without processing them whatsoever, until its buffer
	 *	shrinks again.
609 610 611 612 613 614 615
	 */

	/* See if this is the first ackno being inserted */
	if (ap->dccpap_buf_vector_len == 0) {
		ap->dccpap_buf[ap->dccpap_buf_head] = state;
		ap->dccpap_buf_vector_len = 1;
	} else if (after48(ackno, ap->dccpap_buf_ackno)) {
616 617
		const u64 delta = dccp_delta_seqno(ap->dccpap_buf_ackno,
						   ackno);
618 619

		/*
620 621
		 * Look if the state of this packet is the same as the
		 * previous ackno and if so if we can bump the head len.
622 623 624
		 */
		if (delta == 1 &&
		    dccp_ackpkts_state(ap, ap->dccpap_buf_head) == state &&
625 626
		    (dccp_ackpkts_len(ap, ap->dccpap_buf_head) <
		     DCCP_ACKPKTS_LEN_MASK))
627 628 629 630 631 632 633
			ap->dccpap_buf[ap->dccpap_buf_head]++;
		else if (dccp_ackpkts_set_buf_head_state(ap, delta, state))
			return -ENOBUFS;
	} else {
		/*
		 * A.1.2.  Old Packets
		 *
634 635 636 637
		 *	When a packet with Sequence Number S arrives, and
		 *	S <= buf_ackno, the HC-Receiver will scan the table
		 *	for the byte corresponding to S. (Indexing structures
		 *	could reduce the complexity of this scan.)
638 639 640 641 642 643 644 645
		 */
		u64 delta = dccp_delta_seqno(ackno, ap->dccpap_buf_ackno);
		unsigned int index = ap->dccpap_buf_head;

		while (1) {
			const u8 len = dccp_ackpkts_len(ap, index);
			const u8 state = dccp_ackpkts_state(ap, index);
			/*
646 647
			 * valid packets not yet in dccpap_buf have a reserved
			 * entry, with a len equal to 0.
648 649
			 */
			if (state == DCCP_ACKPKTS_STATE_NOT_RECEIVED &&
650 651
			    len == 0 && delta == 0) { /* Found our
							 reserved seat! */
652 653
				dccp_pr_debug("Found %llu reserved seat!\n",
					      (unsigned long long) ackno);
654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675
				ap->dccpap_buf[index] = state;
				goto out;
			}
			/* len == 0 means one packet */
			if (delta < len + 1)
				goto out_duplicate;

			delta -= len + 1;
			if (++index == ap->dccpap_buf_len)
				index = 0;
		}
	}

	ap->dccpap_buf_ackno = ackno;
	ap->dccpap_time = jiffies;
out:
	dccp_pr_debug("");
	dccp_ackpkts_print(ap);
	return 0;

out_duplicate:
	/* Duplicate packet */
676 677
	dccp_pr_debug("Received a dup or already considered lost "
		      "packet: %llu\n", (unsigned long long) ackno);
678 679 680
	return -EILSEQ;
}

681
#ifdef CONFIG_IP_DCCP_DEBUG
682 683
void dccp_ackvector_print(const u64 ackno, const unsigned char *vector,
			  int len)
684 685 686 687
{
	if (!dccp_debug)
		return;

688 689
	printk("ACK vector len=%d, ackno=%llu |", len,
	       (unsigned long long) ackno);
690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715

	while (len--) {
		const u8 state = (*vector & DCCP_ACKPKTS_STATE_MASK) >> 6;
		const u8 rl = (*vector & DCCP_ACKPKTS_LEN_MASK);

		printk("%d,%d|", state, rl);
		++vector;
	}

	printk("\n");
}

void dccp_ackpkts_print(const struct dccp_ackpkts *ap)
{
	dccp_ackvector_print(ap->dccpap_buf_ackno,
			     ap->dccpap_buf + ap->dccpap_buf_head,
			     ap->dccpap_buf_vector_len);
}
#endif

static void dccp_ackpkts_trow_away_ack_record(struct dccp_ackpkts *ap)
{
	/*
	 * As we're keeping track of the ack vector size
	 * (dccpap_buf_vector_len) and the sent ack vector size
	 * (dccpap_ack_vector_len) we don't need dccpap_buf_tail at all, but
716 717 718
	 * keep this code here as in the future we'll implement a vector of
	 * ack records, as suggested in draft-ietf-dccp-spec-11.txt
	 * Appendix A. -acme
719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735
	 */
#if 0
	ap->dccpap_buf_tail = ap->dccpap_ack_ptr + 1;
	if (ap->dccpap_buf_tail >= ap->dccpap_buf_len)
		ap->dccpap_buf_tail -= ap->dccpap_buf_len;
#endif
	ap->dccpap_buf_vector_len -= ap->dccpap_ack_vector_len;
}

void dccp_ackpkts_check_rcv_ackno(struct dccp_ackpkts *ap, struct sock *sk,
				 u64 ackno)
{
	/* Check if we actually sent an ACK vector */
	if (ap->dccpap_ack_seqno == DCCP_MAX_SEQNO + 1)
		return;

	if (ackno == ap->dccpap_ack_seqno) {
736
#ifdef CONFIG_IP_DCCP_DEBUG
737
		struct dccp_sock *dp = dccp_sk(sk);
738 739
		const char *debug_prefix = dp->dccps_role == DCCP_ROLE_CLIENT ?
					"CLIENT rx ack: " : "server rx ack: ";
740
#endif
741 742
		dccp_pr_debug("%sACK packet 0, len=%d, ack_seqno=%llu, "
			      "ack_ackno=%llu, ACKED!\n",
743
			      debug_prefix, 1,
744 745
			      (unsigned long long) ap->dccpap_ack_seqno,
			      (unsigned long long) ap->dccpap_ack_ackno);
746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761
		dccp_ackpkts_trow_away_ack_record(ap);
		ap->dccpap_ack_seqno = DCCP_MAX_SEQNO + 1;
	}
}

static void dccp_ackpkts_check_rcv_ackvector(struct dccp_ackpkts *ap,
					     struct sock *sk, u64 ackno,
					     const unsigned char len,
					     const unsigned char *vector)
{
	unsigned char i;

	/* Check if we actually sent an ACK vector */
	if (ap->dccpap_ack_seqno == DCCP_MAX_SEQNO + 1)
		return;
	/*
762 763 764
	 * We're in the receiver half connection, so if the received an ACK
	 * vector ackno (e.g. 50) before dccpap_ack_seqno (e.g. 52), we're
	 * not interested.
765 766 767 768 769 770
	 *
	 * Extra explanation with example:
	 * 
	 * if we received an ACK vector with ackno 50, it can only be acking
	 * 50, 49, 48, etc, not 52 (the seqno for the ACK vector we sent).
	 */
771
	/* dccp_pr_debug("is %llu < %llu? ", ackno, ap->dccpap_ack_seqno); */
772
	if (before48(ackno, ap->dccpap_ack_seqno)) {
773
		/* dccp_pr_debug_cat("yes\n"); */
774 775
		return;
	}
776
	/* dccp_pr_debug_cat("no\n"); */
777 778 779 780 781 782 783 784

	i = len;
	while (i--) {
		const u8 rl = (*vector & DCCP_ACKPKTS_LEN_MASK);
		u64 ackno_end_rl;

		dccp_set_seqno(&ackno_end_rl, ackno - rl);

785 786 787 788
		/*
		 * dccp_pr_debug("is %llu <= %llu <= %llu? ", ackno_end_rl,
		 * ap->dccpap_ack_seqno, ackno);
		 */
789
		if (between48(ap->dccpap_ack_seqno, ackno_end_rl, ackno)) {
790 791 792
			const u8 state = (*vector &
					  DCCP_ACKPKTS_STATE_MASK) >> 6;
			/* dccp_pr_debug_cat("yes\n"); */
793 794

			if (state != DCCP_ACKPKTS_STATE_NOT_RECEIVED) {
795
#ifdef CONFIG_IP_DCCP_DEBUG
796
				struct dccp_sock *dp = dccp_sk(sk);
797 798 799
				const char *debug_prefix =
					dp->dccps_role == DCCP_ROLE_CLIENT ?
					"CLIENT rx ack: " : "server rx ack: ";
800
#endif
801 802 803
				dccp_pr_debug("%sACK vector 0, len=%d, "
					      "ack_seqno=%llu, ack_ackno=%llu, "
					      "ACKED!\n",
804
					      debug_prefix, len,
805 806 807 808
					      (unsigned long long)
					      ap->dccpap_ack_seqno,
					      (unsigned long long)
					      ap->dccpap_ack_ackno);
809 810 811
				dccp_ackpkts_trow_away_ack_record(ap);
			}
			/*
812 813
			 * If dccpap_ack_seqno was not received, no problem
			 * we'll send another ACK vector.
814 815 816 817
			 */
			ap->dccpap_ack_seqno = DCCP_MAX_SEQNO + 1;
			break;
		}
818
		/* dccp_pr_debug_cat("no\n"); */
819 820 821 822 823

		dccp_set_seqno(&ackno, ackno_end_rl - 1);
		++vector;
	}
}