path: root/net/dccp/ackvec.c

/*
 *  net/dccp/ackvec.c
 *
 *  An implementation of the DCCP protocol
 *  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/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 kmem_cache_t *dccp_ackvec_slab;
static kmem_cache_t *dccp_ackvec_record_slab;

static struct dccp_ackvec_record *dccp_ackvec_record_new(void)
{
	struct dccp_ackvec_record *avr =
			kmem_cache_alloc(dccp_ackvec_record_slab, GFP_ATOMIC);

	if (avr != NULL)
		INIT_LIST_HEAD(&avr->dccpavr_node);

	return avr;
}

static void dccp_ackvec_record_delete(struct dccp_ackvec_record *avr)
{
	if (unlikely(avr == NULL))
		return;
	/* Check if deleting a linked record */
	WARN_ON(!list_empty(&avr->dccpavr_node));
	kmem_cache_free(dccp_ackvec_record_slab, avr);
}

static void dccp_ackvec_insert_avr(struct dccp_ackvec *av,
				   struct dccp_ackvec_record *avr)
{
	/*
	 * AVRs are sorted by seqno. Since we are sending them in order, we
	 * just add the AVR at the head of the list.
	 * -sorbo.
	 */
	if (!list_empty(&av->dccpav_records)) {
		const struct dccp_ackvec_record *head =
					list_entry(av->dccpav_records.next,
						   struct dccp_ackvec_record,
						   dccpavr_node);
		BUG_ON(before48(avr->dccpavr_ack_seqno,
				head->dccpavr_ack_seqno));
	}

	list_add(&avr->dccpavr_node, &av->dccpav_records);
}

int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb)
{
	struct dccp_sock *dp = dccp_sk(sk);
	struct dccp_ackvec *av = dp->dccps_hc_rx_ackvec;
	/* Figure out how many options do we need to represent the ackvec */
	const u16 nr_opts = (av->dccpav_vec_len +
			     DCCP_MAX_ACKVEC_OPT_LEN - 1) /
			    DCCP_MAX_ACKVEC_OPT_LEN;
	u16 len = av->dccpav_vec_len + 2 * nr_opts, i;
	struct timeval now;
	u32 elapsed_time;
	const unsigned char *tail, *from;
	unsigned char *to;
	struct dccp_ackvec_record *avr;

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

	dccp_timestamp(sk, &now);
	elapsed_time = timeval_delta(&now, &av->dccpav_time) / 10;

	if (elapsed_time != 0 &&
	    dccp_insert_option_elapsed_time(sk, skb, elapsed_time))
		return -1;

	avr = dccp_ackvec_record_new();
	if (avr == NULL)
		return -1;

	DCCP_SKB_CB(skb)->dccpd_opt_len += len;

	to   = skb_push(skb, len);
	len  = av->dccpav_vec_len;
	from = av->dccpav_buf + av->dccpav_buf_head;
	tail = av->dccpav_buf + DCCP_MAX_ACKVEC_LEN;

	for (i = 0; i < nr_opts; ++i) {
		int copylen = len;

		if (len > DCCP_MAX_ACKVEC_OPT_LEN)
			copylen = DCCP_MAX_ACKVEC_OPT_LEN;

		*to++ = DCCPO_ACK_VECTOR_0;
		*to++ = copylen + 2;

		/* Check if buf_head wraps */
		if (from + copylen > tail) {
			const u16 tailsize = tail - from;

			memcpy(to, from, tailsize);
			to	+= tailsize;
			len	-= tailsize;
			copylen	-= tailsize;
			from	= av->dccpav_buf;
		}

		memcpy(to, from, copylen);
		from += copylen;
		to   += copylen;
		len  -= copylen;
	}

	/*
	 *	From RFC 4340, A.2:
	 *
	 *	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
	 *	buf_head; ack_ackno will equal buf_ackno; and ack_nonce will
	 *	equal buf_nonce.
	 */
	avr->dccpavr_ack_seqno = DCCP_SKB_CB(skb)->dccpd_seq;
	avr->dccpavr_ack_ptr   = av->dccpav_buf_head;
	avr->dccpavr_ack_ackno = av->dccpav_buf_ackno;
	avr->dccpavr_ack_nonce = av->dccpav_buf_nonce;
	avr->dccpavr_sent_len  = av->dccpav_vec_len;

	dccp_ackvec_insert_avr(av, avr);

	dccp_pr_debug("%s ACK Vector 0, len=%d, ack_seqno=%llu, "
		      "ack_ackno=%llu\n",
		      dccp_role(sk), avr->dccpavr_sent_len,
		      (unsigned long long)avr->dccpavr_ack_seqno,
		      (unsigned long long)avr->dccpavr_ack_ackno);
	return 0;
}

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

	if (av != NULL) {
		av->dccpav_buf_head	= DCCP_MAX_ACKVEC_LEN - 1;
		av->dccpav_buf_ackno	= DCCP_MAX_SEQNO + 1;
		av->dccpav_buf_nonce = av->dccpav_buf_nonce = 0;
		av->dccpav_time.tv_sec	= 0;
		av->dccpav_time.tv_usec	= 0;
		av->dccpav_vec_len	= 0;
		INIT_LIST_HEAD(&av->dccpav_records);
	}

	return av;
}

void dccp_ackvec_free(struct dccp_ackvec *av)
{
	if (unlikely(av == NULL))
		return;

	if (!list_empty(&av->dccpav_records)) {
		struct dccp_ackvec_record *avr, *next;

		list_for_each_entry_safe(avr, next, &av->dccpav_records,
					 dccpavr_node) {
			list_del_init(&avr->dccpavr_node);
			dccp_ackvec_record_delete(avr);
		}
	}

	kmem_cache_free(dccp_ackvec_slab, av);
}

static inline u8 dccp_ackvec_state(const struct dccp_ackvec *av,
				   const u32 index)
{
	return av->dccpav_buf[index] & DCCP_ACKVEC_STATE_MASK;
}

static inline u8 dccp_ackvec_len(const struct dccp_ackvec *av,
				 const u32 index)
{
	return av->dccpav_buf[index] & DCCP_ACKVEC_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_ackvec_set_buf_head_state(struct dccp_ackvec *av,
						 const unsigned int packets,
						 const unsigned char state)
{
	unsigned int gap;
	long new_head;

	if (av->dccpav_vec_len + packets > DCCP_MAX_ACKVEC_LEN)
		return -ENOBUFS;

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

	if (new_head < 0) {
		if (gap > 0) {
			memset(av->dccpav_buf, DCCP_ACKVEC_STATE_NOT_RECEIVED,
			       gap + new_head + 1);
			gap = -new_head;
		}
		new_head += DCCP_MAX_ACKVEC_LEN;
	} 

	av->dccpav_buf_head = new_head;

	if (gap > 0)
		memset(av->dccpav_buf + av->dccpav_buf_head + 1,
		       DCCP_ACKVEC_STATE_NOT_RECEIVED, gap);

	av->dccpav_buf[av->dccpav_buf_head] = state;
	av->dccpav_vec_len += packets;
	return 0;
}

/*
 * Implements the RFC 4340, Appendix A
 */
int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock<