[net-next-2.6.git] / net / dccp / ackvec.c

/*
 *  net/dccp/ackvec.c
 *
 *  An implementation of Ack Vectors for the DCCP protocol
 *  Copyright (c) 2007 University of Aberdeen, Scotland, UK
 *  Copyright (c) 2005 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; version 2 of the License;
 */

#include "ackvec.h"
#include "dccp.h"

#include <linux/init.h>
#include <linux/errno.h>
#include <linux/kernel.h>
#include <linux/skbuff.h>
#include <linux/slab.h>

#include <net/sock.h>

static struct kmem_cache *dccp_ackvec_slab;
static struct kmem_cache *dccp_ackvec_record_slab;

struct dccp_ackvec *dccp_ackvec_alloc(const gfp_t priority)
{
	struct dccp_ackvec *av = kmem_cache_zalloc(dccp_ackvec_slab, priority);

	if (av != NULL) {
		av->av_buf_head	= DCCPAV_MAX_ACKVEC_LEN - 1;
		INIT_LIST_HEAD(&av->av_records);
	}
	return av;
}

static void dccp_ackvec_purge_records(struct dccp_ackvec *av)
{
	struct dccp_ackvec_record *cur, *next;

	list_for_each_entry_safe(cur, next, &av->av_records, avr_node)
		kmem_cache_free(dccp_ackvec_record_slab, cur);
	INIT_LIST_HEAD(&av->av_records);
}

void dccp_ackvec_free(struct dccp_ackvec *av)
{
	if (likely(av != NULL)) {
		dccp_ackvec_purge_records(av);
		kmem_cache_free(dccp_ackvec_slab, av);
	}
}

/**
 * dccp_ackvec_update_records  -  Record information about sent Ack Vectors
 * @av:		Ack Vector records to update
 * @seqno:	Sequence number of the packet carrying the Ack Vector just sent
 * @nonce_sum:	The sum of all buffer nonces contained in the Ack Vector
 */
int dccp_ackvec_update_records(struct dccp_ackvec *av, u64 seqno, u8 nonce_sum)
{
	struct dccp_ackvec_record *avr;

	avr = kmem_cache_alloc(dccp_ackvec_record_slab, GFP_ATOMIC);
	if (avr == NULL)
		return -ENOBUFS;

	avr->avr_ack_seqno  = seqno;
	avr->avr_ack_ptr    = av->av_buf_head;
	avr->avr_ack_ackno  = av->av_buf_ackno;
	avr->avr_ack_nonce  = nonce_sum;
	avr->avr_ack_runlen = dccp_ackvec_runlen(av->av_buf + av->av_buf_head);
	/*
	 * Since GSS is incremented for each packet, the list is automatically
	 * arranged in descending order of @ack_seqno.
	 */
	list_add(&avr->avr_node, &av->av_records);

	dccp_pr_debug("Added Vector, ack_seqno=%llu, ack_ackno=%llu (rl=%u)\n",
		      (unsigned long long)avr->avr_ack_seqno,
		      (unsigned long long)avr->avr_ack_ackno,
		      avr->avr_ack_runlen);
	return 0;
}

/*
 * 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_ackvec_set_buf_head_state(struct dccp_ackvec *av,
						 const unsigned int packets,
						 const unsigned char state)
{
	long gap;
	long new_head;

	if (av->av_vec_len + packets > DCCPAV_MAX_ACKVEC_LEN)
		return -ENOBUFS;

	gap	 = packets - 1;
	new_head = av->av_buf_head - packets;

	if (new_head < 0) {
		if (gap > 0) {
			memset(av->av_buf, DCCPAV_NOT_RECEIVED,
			       gap + new_head + 1);
			gap = -new_head;
		}
		new_head += DCCPAV_MAX_ACKVEC_LEN;
	}

	av->av_buf_head = new_head;

	if (gap > 0)
		memset(av->av_buf + av->av_buf_head + 1,
		       DCCPAV_NOT_RECEIVED, gap);

	av->av_buf[av->av_buf_head] = state;
	av->av_vec_len += packets;
	return 0;
}

/*
 * Implements the RFC 4340, Appendix A
 */
int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk,
		    const u64 ackno, const u8 state)
{
	u8 *cur_head = av->av_buf + av->av_buf_head,
	   *buf_end  = av->av_buf + DCCPAV_MAX_ACKVEC_LEN;
	/*
	 * 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 av_buf.
	 *
	 * We may well decide to do buffer compression, etc, but for now lets
	 * just drop.
	 *
	 * From Appendix A.1.1 (`New Packets'):
	 *
	 *	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.
	 */

	/* See if this is the first ackno being inserted */
	if (av->av_vec_len == 0) {
		*cur_head = state;
		av->av_vec_len = 1;
	} else if (after48(ackno, av->av_buf_ackno)) {
		const u64 delta = dccp_delta_seqno(av->av_buf_ackno, ackno);

		/*
		 * Look if the state of this packet is the same as the
		 * previous ackno and if so if we can bump the head len.
		 */
		if (delta == 1 && dccp_ackvec_state(cur_head) == state &&
		    dccp_ackvec_runlen(cur_head) < DCCPAV_MAX_RUNLEN)
			*cur_head += 1;
		else if (dccp_ackvec_set_buf_head_state(av, delta, state))
			return -ENOBUFS;
	} else {
		/*
		 * A.1.2.  Old Packets
		 *
		 *	When a packet with Sequence Number S <= buf_ackno
		 *	arrives, the HC-Receiver will scan the table for
		 *	the byte corresponding to S. (Indexing structures
		 *	could reduce the complexity of this scan.)
		 */
		u64 delta = dccp_delta_seqno(ackno, av->av_buf_ackno);

		while (1) {
			const u8 len = dccp_ackvec_runlen(cur_head);
			/*
			 * valid packets not yet in av_buf have a reserved
			 * entry, with a len equal to 0.
			 */
			if (*cur_head == DCCPAV_NOT_RECEIVED && delta == 0) {
				dccp_pr_debug("Found %llu reserved seat!\n",
					      (unsigned long long)ackno);
				*cur_head = state;
				goto out;
			}
			/* len == 0 means one packet */
			if (delta < len + 1)
				goto out_duplicate;

			delta -= len + 1;
			if (++cur_head == buf_end)
				cur_head = av->av_buf;
		}
	}

	av->av_buf_ackno = ackno;
out:
	return 0;

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

static void dccp_ackvec_throw_record(struct dccp_ackvec *av,
				     struct dccp_ackvec_record *avr)
{
	struct dccp_ackvec_record *next;

	/* sort out vector length */
	if (av->av_buf_head <= avr->avr_ack_ptr)
		av->av_vec_len = avr->avr_ack_ptr - av->av_buf_head;
	else
		av->av_vec_len = DCCPAV_MAX_ACKVEC_LEN - 1 -
				 av->av_buf_head + avr->avr_ack_ptr;

	/* free records */
	list_for_each_entry_safe_from(avr, next, &av->av_records, avr_node) {
		list_del(&avr->avr_node);
		kmem_cache_free(dccp_ackvec_record_slab, avr);
	}
}

void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec *av, struct sock *sk,
				 const u64 ackno)
{
	struct dccp_ackvec_record *avr;

	/*
	 * If we traverse backwards, it should be faster when we have large
	 * windows. We will be receiving ACKs for stuff we sent a while back
	 * -sorbo.
	 */
	list_for_each_entry_reverse(avr, &av->av_records, avr_node) {
		if (ackno == avr->avr_ack_seqno) {
			dccp_pr_debug("%s ACK packet 0, len=%d, ack_seqno=%llu, "
				      "ack_ackno=%llu, ACKED!\n",
				      dccp_role(sk), avr->avr_ack_runlen,
				      (unsigned long long)avr->avr_ack_seqno,
				      (unsigned long long)avr->avr_ack_ackno);
			dccp_ackvec_throw_record(av, avr);
			break;
		} else if (avr->avr_ack_seqno > ackno)
			break; /* old news */
	}
}

static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec *av,
					    struct sock *sk, u64 *ackno,
					    const unsigned char len,
					    const unsigned char *vector)
{
	unsigned char i;
	struct dccp_ackvec_record *avr;

	/* Check if we actually sent an ACK vector */
	if (list_empty(&av->av_records))
		return;

	i = len;
	/*
	 * XXX
	 * I think it might be more efficient to work backwards. See comment on
	 * rcv_ackno. -sorbo.
	 */
	avr = list_entry(av->av_records.next, struct dccp_ackvec_record, avr_node);
	while (i--) {
		const u8 rl = dccp_ackvec_runlen(vector);
		u64 ackno_end_rl;

		dccp_set_seqno(&ackno_end_rl, *ackno - rl);

		/*
		 * If our AVR sequence number is greater than the ack, go
		 * forward in the AVR list until it is not so.
		 */
		list_for_each_entry_from(avr, &av->av_records, avr_node) {
			if (!after48(avr->avr_ack_seqno, *ackno))
				goto found;
		}
		/* End of the av_records list, not found, exit */
		break;
found:
		if (between48(avr->avr_ack_seqno, ackno_end_rl, *ackno)) {
			if (dccp_ackvec_state(vector) != DCCPAV_NOT_RECEIVED) {
				dccp_pr_debug("%s ACK vector 0, len=%d, "
					      "ack_seqno=%llu, ack_ackno=%llu, "
					      "ACKED!\n",
					      dccp_role(sk), len,
					      (unsigned long long)
					      avr->avr_ack_seqno,
					      (unsigned long long)
					      avr->avr_ack_ackno);
				dccp_ackvec_throw_record(av, avr);
				break;
			}
			/*
			 * If it wasn't received, continue scanning... we might
			 * find another one.
			 */
		}

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

int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb,
		      u64 *ackno, const u8 opt, const u8 *value, const u8 len)
{
	if (len > DCCP_SINGLE_OPT_MAXLEN)
		return -1;

	/* dccp_ackvector_print(DCCP_SKB_CB(skb)->dccpd_ack_seq, value, len); */
	dccp_ackvec_check_rcv_ackvector(dccp_sk(sk)->dccps_hc_rx_ackvec, sk,
					ackno, len, value);
	return 0;
}

int __init dccp_ackvec_init(void)
{
	dccp_ackvec_slab = kmem_cache_create("dccp_ackvec",
					     sizeof(struct dccp_ackvec), 0,
					     SLAB_HWCACHE_ALIGN, NULL);
	if (dccp_ackvec_slab == NULL)
		goto out_err;

	dccp_ackvec_record_slab = kmem_cache_create("dccp_ackvec_record",
					     sizeof(struct dccp_ackvec_record),
					     0, SLAB_HWCACHE_ALIGN, NULL);
	if (dccp_ackvec_record_slab == NULL)
		goto out_destroy_slab;

	return 0;

out_destroy_slab:
	kmem_cache_destroy(dccp_ackvec_slab);
	dccp_ackvec_slab = NULL;
out_err:
	DCCP_CRIT("Unable to create Ack Vector slab cache");
	return -ENOBUFS;
}

void dccp_ackvec_exit(void)
{
	if (dccp_ackvec_slab != NULL) {
		kmem_cache_destroy(dccp_ackvec_slab);
		dccp_ackvec_slab = NULL;
	}
	if (dccp_ackvec_record_slab != NULL) {
		kmem_cache_destroy(dccp_ackvec_record_slab);
		dccp_ackvec_record_slab = NULL;
	}
}
Commit	Line	Data
ae31c339 ACM	1	/*
	2	* net/dccp/ackvec.c
	3	*
f17a37c9 GR	4	* An implementation of Ack Vectors for the DCCP protocol
f17a37c9 GR	5	* Copyright (c) 2007 University of Aberdeen, Scotland, UK
ae31c339 ACM	6	* Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@ghostprotocols.net>
	7	*
	8	* This program is free software; you can redistribute it and/or modify it
	9	* under the terms of the GNU General Public License as published by the
	10	* Free Software Foundation; version 2 of the License;
	11	*/
	12
	13	#include "ackvec.h"
	14	#include "dccp.h"
	15
9b07ef5d ACM	16	#include <linux/init.h>
	17	#include <linux/errno.h>
	18	#include <linux/kernel.h>
ae31c339	19	#include <linux/skbuff.h>
9b07ef5d	20	#include <linux/slab.h>
ae31c339 ACM	21
	22	#include <net/sock.h>
	23
e18b890b CL	24	static struct kmem_cache *dccp_ackvec_slab;
e18b890b CL	25	static struct kmem_cache *dccp_ackvec_record_slab;
02bcf28c	26
f17a37c9	27	struct dccp_ackvec *dccp_ackvec_alloc(const gfp_t priority)
02bcf28c	28	{
f17a37c9 GR	29	struct dccp_ackvec *av = kmem_cache_zalloc(dccp_ackvec_slab, priority);
	30
	31	if (av != NULL) {
	32	av->av_buf_head = DCCPAV_MAX_ACKVEC_LEN - 1;
	33	INIT_LIST_HEAD(&av->av_records);
	34	}
	35	return av;
	36	}
02bcf28c	37
f17a37c9 GR	38	static void dccp_ackvec_purge_records(struct dccp_ackvec *av)
	39	{
	40	struct dccp_ackvec_record cur, next;
02bcf28c	41
f17a37c9 GR	42	list_for_each_entry_safe(cur, next, &av->av_records, avr_node)
	43	kmem_cache_free(dccp_ackvec_record_slab, cur);
	44	INIT_LIST_HEAD(&av->av_records);
02bcf28c AB	45	}
02bcf28c AB	46
f17a37c9	47	void dccp_ackvec_free(struct dccp_ackvec *av)
02bcf28c	48	{
f17a37c9 GR	49	if (likely(av != NULL)) {
	50	dccp_ackvec_purge_records(av);
	51	kmem_cache_free(dccp_ackvec_slab, av);
	52	}
02bcf28c AB	53	}
02bcf28c AB	54
7d870936 GR	55	/**
	56	* dccp_ackvec_update_records - Record information about sent Ack Vectors
	57	* @av: Ack Vector records to update
	58	* @seqno: Sequence number of the packet carrying the Ack Vector just sent
	59	* @nonce_sum: The sum of all buffer nonces contained in the Ack Vector
	60	*/
	61	int dccp_ackvec_update_records(struct dccp_ackvec *av, u64 seqno, u8 nonce_sum)
ae31c339	62	{
02bcf28c AB	63	struct dccp_ackvec_record *avr;
02bcf28c AB	64
f17a37c9	65	avr = kmem_cache_alloc(dccp_ackvec_record_slab, GFP_ATOMIC);
2d0817d1	66	if (avr == NULL)
7d870936	67	return -ENOBUFS;
ae31c339	68
7d870936	69	avr->avr_ack_seqno = seqno;
f17a37c9 GR	70	avr->avr_ack_ptr = av->av_buf_head;
f17a37c9 GR	71	avr->avr_ack_ackno = av->av_buf_ackno;
7d870936	72	avr->avr_ack_nonce = nonce_sum;
f17a37c9	73	avr->avr_ack_runlen = dccp_ackvec_runlen(av->av_buf + av->av_buf_head);
7d870936 GR	74	/*
	75	* Since GSS is incremented for each packet, the list is automatically
	76	* arranged in descending order of @ack_seqno.
	77	*/
	78	list_add(&avr->avr_node, &av->av_records);
02bcf28c	79
7d870936	80	dccp_pr_debug("Added Vector, ack_seqno=%llu, ack_ackno=%llu (rl=%u)\n",
a47c5104	81	(unsigned long long)avr->avr_ack_seqno,
7d870936 GR	82	(unsigned long long)avr->avr_ack_ackno,
7d870936 GR	83	avr->avr_ack_runlen);
02bcf28c	84	return 0;
ae31c339 ACM	85	}
ae31c339 ACM	86
ae31c339 ACM	87	/*
	88	* If several packets are missing, the HC-Receiver may prefer to enter multiple
	89	* bytes with run length 0, rather than a single byte with a larger run length;
	90	* this simplifies table updates if one of the missing packets arrives.
	91	*/
	92	static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec *av,
	93	const unsigned int packets,
e4dfd449	94	const unsigned char state)
ae31c339	95	{
8e64159d	96	long gap;
a8fc3d8d	97	long new_head;
ae31c339	98
f17a37c9	99	if (av->av_vec_len + packets > DCCPAV_MAX_ACKVEC_LEN)
ae31c339 ACM	100	return -ENOBUFS;
	101
	102	gap = packets - 1;
a47c5104	103	new_head = av->av_buf_head - packets;
ae31c339 ACM	104
	105	if (new_head < 0) {
	106	if (gap > 0) {
f17a37c9	107	memset(av->av_buf, DCCPAV_NOT_RECEIVED,
ae31c339 ACM	108	gap + new_head + 1);
	109	gap = -new_head;
	110	}
f17a37c9	111	new_head += DCCPAV_MAX_ACKVEC_LEN;
8109b02b	112	}
ae31c339	113
a47c5104	114	av->av_buf_head = new_head;
ae31c339 ACM	115
ae31c339 ACM	116	if (gap > 0)
a47c5104	117	memset(av->av_buf + av->av_buf_head + 1,
f17a37c9	118	DCCPAV_NOT_RECEIVED, gap);
ae31c339	119
a47c5104 GR	120	av->av_buf[av->av_buf_head] = state;
a47c5104 GR	121	av->av_vec_len += packets;
ae31c339 ACM	122	return 0;
	123	}
	124
	125	/*
0e64e94e	126	* Implements the RFC 4340, Appendix A
ae31c339 ACM	127	*/
	128	int dccp_ackvec_add(struct dccp_ackvec av, const struct sock sk,
	129	const u64 ackno, const u8 state)
	130	{
f17a37c9 GR	131	u8 *cur_head = av->av_buf + av->av_buf_head,
f17a37c9 GR	132	*buf_end = av->av_buf + DCCPAV_MAX_ACKVEC_LEN;
ae31c339 ACM	133	/*
	134	* Check at the right places if the buffer is full, if it is, tell the
	135	* caller to start dropping packets till the HC-Sender acks our ACK
a47c5104	136	* vectors, when we will free up space in av_buf.
ae31c339 ACM	137	*
	138	* We may well decide to do buffer compression, etc, but for now lets
	139	* just drop.
	140	*
0e64e94e	141	* From Appendix A.1.1 (`New Packets'):
ae31c339 ACM	142	*
	143	* Of course, the circular buffer may overflow, either when the
	144	* HC-Sender is sending data at a very high rate, when the
	145	* HC-Receiver's acknowledgements are not reaching the HC-Sender,
	146	* or when the HC-Sender is forgetting to acknowledge those acks
	147	* (so the HC-Receiver is unable to clean up old state). In this
	148	* case, the HC-Receiver should either compress the buffer (by
	149	* increasing run lengths when possible), transfer its state to
	150	* a larger buffer, or, as a last resort, drop all received
	151	* packets, without processing them whatsoever, until its buffer
	152	* shrinks again.
	153	*/
	154
	155	/* See if this is the first ackno being inserted */
a47c5104	156	if (av->av_vec_len == 0) {
f17a37c9	157	*cur_head = state;
a47c5104 GR	158	av->av_vec_len = 1;
	159	} else if (after48(ackno, av->av_buf_ackno)) {
	160	const u64 delta = dccp_delta_seqno(av->av_buf_ackno, ackno);
ae31c339 ACM	161
	162	/*
	163	* Look if the state of this packet is the same as the
	164	* previous ackno and if so if we can bump the head len.
	165	*/
f17a37c9 GR	166	if (delta == 1 && dccp_ackvec_state(cur_head) == state &&
	167	dccp_ackvec_runlen(cur_head) < DCCPAV_MAX_RUNLEN)
	168	*cur_head += 1;
ae31c339 ACM	169	else if (dccp_ackvec_set_buf_head_state(av, delta, state))
	170	return -ENOBUFS;
	171	} else {
	172	/*
	173	* A.1.2. Old Packets
	174	*
0e64e94e GR	175	* When a packet with Sequence Number S <= buf_ackno
	176	* arrives, the HC-Receiver will scan the table for
	177	* the byte corresponding to S. (Indexing structures
ae31c339 ACM	178	* could reduce the complexity of this scan.)
ae31c339 ACM	179	*/
a47c5104	180	u64 delta = dccp_delta_seqno(ackno, av->av_buf_ackno);
ae31c339 ACM	181
ae31c339 ACM	182	while (1) {
f17a37c9	183	const u8 len = dccp_ackvec_runlen(cur_head);
ae31c339	184	/*
a47c5104	185	* valid packets not yet in av_buf have a reserved
ae31c339 ACM	186	* entry, with a len equal to 0.
ae31c339 ACM	187	*/
f17a37c9	188	if (*cur_head == DCCPAV_NOT_RECEIVED && delta == 0) {
ae31c339 ACM	189	dccp_pr_debug("Found %llu reserved seat!\n",
ae31c339 ACM	190	(unsigned long long)ackno);
f17a37c9	191	*cur_head = state;
ae31c339 ACM	192	goto out;
	193	}
	194	/* len == 0 means one packet */
	195	if (delta < len + 1)
	196	goto out_duplicate;
	197
	198	delta -= len + 1;
f17a37c9 GR	199	if (++cur_head == buf_end)
f17a37c9 GR	200	cur_head = av->av_buf;
ae31c339 ACM	201	}
	202	}
	203
a47c5104	204	av->av_buf_ackno = ackno;
ae31c339	205	out:
ae31c339 ACM	206	return 0;
	207
	208	out_duplicate:
	209	/* Duplicate packet */
	210	dccp_pr_debug("Received a dup or already considered lost "
	211	"packet: %llu\n", (unsigned long long)ackno);
	212	return -EILSEQ;
	213	}
	214
02bcf28c AB	215	static void dccp_ackvec_throw_record(struct dccp_ackvec *av,
02bcf28c AB	216	struct dccp_ackvec_record *avr)
ae31c339	217	{
02bcf28c AB	218	struct dccp_ackvec_record *next;
02bcf28c AB	219
23d06e3b	220	/* sort out vector length */
a47c5104 GR	221	if (av->av_buf_head <= avr->avr_ack_ptr)
a47c5104 GR	222	av->av_vec_len = avr->avr_ack_ptr - av->av_buf_head;
23d06e3b	223	else
f17a37c9	224	av->av_vec_len = DCCPAV_MAX_ACKVEC_LEN - 1 -
a47c5104	225	av->av_buf_head + avr->avr_ack_ptr;
02bcf28c AB	226
02bcf28c AB	227	/* free records */
a47c5104	228	list_for_each_entry_safe_from(avr, next, &av->av_records, avr_node) {
f17a37c9 GR	229	list_del(&avr->avr_node);
f17a37c9 GR	230	kmem_cache_free(dccp_ackvec_record_slab, avr);
02bcf28c	231	}
ae31c339 ACM	232	}
	233
	234	void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec av, struct sock sk,
	235	const u64 ackno)
	236	{
02bcf28c	237	struct dccp_ackvec_record *avr;
ae31c339	238
02bcf28c AB	239	/*
	240	* If we traverse backwards, it should be faster when we have large
	241	* windows. We will be receiving ACKs for stuff we sent a while back
	242	* -sorbo.
	243	*/
a47c5104 GR	244	list_for_each_entry_reverse(avr, &av->av_records, avr_node) {
a47c5104 GR	245	if (ackno == avr->avr_ack_seqno) {
09dbc389	246	dccp_pr_debug("%s ACK packet 0, len=%d, ack_seqno=%llu, "
02bcf28c	247	"ack_ackno=%llu, ACKED!\n",
f17a37c9	248	dccp_role(sk), avr->avr_ack_runlen,
a47c5104 GR	249	(unsigned long long)avr->avr_ack_seqno,
a47c5104 GR	250	(unsigned long long)avr->avr_ack_ackno);
02bcf28c AB	251	dccp_ackvec_throw_record(av, avr);
02bcf28c AB	252	break;
a47c5104	253	} else if (avr->avr_ack_seqno > ackno)
d23ca15a	254	break; /* old news */
ae31c339 ACM	255	}
	256	}
	257
	258	static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec *av,
bdf13d20	259	struct sock sk, u64 ackno,
ae31c339 ACM	260	const unsigned char len,
	261	const unsigned char *vector)
	262	{
	263	unsigned char i;
02bcf28c	264	struct dccp_ackvec_record *avr;
ae31c339 ACM	265
ae31c339 ACM	266	/* Check if we actually sent an ACK vector */
a47c5104	267	if (list_empty(&av->av_records))
ae31c339	268	return;
ae31c339 ACM	269
ae31c339 ACM	270	i = len;
02bcf28c AB	271	/*
	272	* XXX
	273	* I think it might be more efficient to work backwards. See comment on
	274	* rcv_ackno. -sorbo.
	275	*/
a47c5104	276	avr = list_entry(av->av_records.next, struct dccp_ackvec_record, avr_node);
ae31c339	277	while (i--) {
f17a37c9	278	const u8 rl = dccp_ackvec_runlen(vector);
ae31c339 ACM	279	u64 ackno_end_rl;
ae31c339 ACM	280
bdf13d20	281	dccp_set_seqno(&ackno_end_rl, *ackno - rl);
ae31c339 ACM	282
ae31c339 ACM	283	/*
02bcf28c AB	284	* If our AVR sequence number is greater than the ack, go
02bcf28c AB	285	* forward in the AVR list until it is not so.
ae31c339	286	*/
a47c5104 GR	287	list_for_each_entry_from(avr, &av->av_records, avr_node) {
a47c5104 GR	288	if (!after48(avr->avr_ack_seqno, *ackno))
02bcf28c AB	289	goto found;
02bcf28c AB	290	}
a47c5104	291	/* End of the av_records list, not found, exit */
02bcf28c AB	292	break;
02bcf28c AB	293	found:
a47c5104	294	if (between48(avr->avr_ack_seqno, ackno_end_rl, *ackno)) {
f17a37c9	295	if (dccp_ackvec_state(vector) != DCCPAV_NOT_RECEIVED) {
09dbc389	296	dccp_pr_debug("%s ACK vector 0, len=%d, "
ae31c339 ACM	297	"ack_seqno=%llu, ack_ackno=%llu, "
ae31c339 ACM	298	"ACKED!\n",
09dbc389	299	dccp_role(sk), len,
ae31c339	300	(unsigned long long)
a47c5104	301	avr->avr_ack_seqno,
ae31c339	302	(unsigned long long)
a47c5104	303	avr->avr_ack_ackno);
02bcf28c	304	dccp_ackvec_throw_record(av, avr);
afec35e3	305	break;
ae31c339 ACM	306	}
ae31c339 ACM	307	/*
02bcf28c AB	308	* If it wasn't received, continue scanning... we might
02bcf28c AB	309	* find another one.
ae31c339	310	*/
ae31c339	311	}
ae31c339	312
bdf13d20	313	dccp_set_seqno(ackno, ackno_end_rl - 1);
ae31c339 ACM	314	++vector;
	315	}
	316	}
	317
	318	int dccp_ackvec_parse(struct sock sk, const struct sk_buff skb,
bdf13d20	319	u64 ackno, const u8 opt, const u8 value, const u8 len)
ae31c339	320	{
b20a9c24	321	if (len > DCCP_SINGLE_OPT_MAXLEN)
ae31c339 ACM	322	return -1;
	323
	324	/* dccp_ackvector_print(DCCP_SKB_CB(skb)->dccpd_ack_seq, value, len); */
	325	dccp_ackvec_check_rcv_ackvector(dccp_sk(sk)->dccps_hc_rx_ackvec, sk,
bdf13d20	326	ackno, len, value);
ae31c339 ACM	327	return 0;
ae31c339 ACM	328	}
9b07ef5d	329
9b07ef5d ACM	330	int __init dccp_ackvec_init(void)
	331	{
	332	dccp_ackvec_slab = kmem_cache_create("dccp_ackvec",
	333	sizeof(struct dccp_ackvec), 0,
20c2df83	334	SLAB_HWCACHE_ALIGN, NULL);
02bcf28c AB	335	if (dccp_ackvec_slab == NULL)
	336	goto out_err;
	337
f17a37c9 GR	338	dccp_ackvec_record_slab = kmem_cache_create("dccp_ackvec_record",
	339	sizeof(struct dccp_ackvec_record),
	340	0, SLAB_HWCACHE_ALIGN, NULL);
02bcf28c AB	341	if (dccp_ackvec_record_slab == NULL)
02bcf28c AB	342	goto out_destroy_slab;
9b07ef5d ACM	343
9b07ef5d ACM	344	return 0;
02bcf28c AB	345
	346	out_destroy_slab:
	347	kmem_cache_destroy(dccp_ackvec_slab);
	348	dccp_ackvec_slab = NULL;
	349	out_err:
59348b19	350	DCCP_CRIT("Unable to create Ack Vector slab cache");
02bcf28c	351	return -ENOBUFS;
9b07ef5d ACM	352	}
	353
	354	void dccp_ackvec_exit(void)
	355	{
	356	if (dccp_ackvec_slab != NULL) {
	357	kmem_cache_destroy(dccp_ackvec_slab);
	358	dccp_ackvec_slab = NULL;
	359	}
02bcf28c AB	360	if (dccp_ackvec_record_slab != NULL) {
	361	kmem_cache_destroy(dccp_ackvec_record_slab);
	362	dccp_ackvec_record_slab = NULL;
	363	}
9b07ef5d	364	}