1/*
2 *  net/dccp/ackvec.c
3 *
4 *  An implementation of the DCCP protocol
5 *  Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@ghostprotocols.net>
6 *
7 *      This program is free software; you can redistribute it and/or modify it
8 *      under the terms of the GNU General Public License as published by the
9 *      Free Software Foundation; version 2 of the License;
10 */
11
12#include "ackvec.h"
13#include "dccp.h"
14
15#include <linux/dccp.h>
16#include <linux/init.h>
17#include <linux/errno.h>
18#include <linux/kernel.h>
19#include <linux/skbuff.h>
20#include <linux/slab.h>
21
22#include <net/sock.h>
23
24static struct kmem_cache *dccp_ackvec_slab;
25static struct kmem_cache *dccp_ackvec_record_slab;
26
27static struct dccp_ackvec_record *dccp_ackvec_record_new(void)
28{
29	struct dccp_ackvec_record *avr =
30			kmem_cache_alloc(dccp_ackvec_record_slab, GFP_ATOMIC);
31
32	if (avr != NULL)
33		INIT_LIST_HEAD(&avr->dccpavr_node);
34
35	return avr;
36}
37
38static void dccp_ackvec_record_delete(struct dccp_ackvec_record *avr)
39{
40	if (unlikely(avr == NULL))
41		return;
42	/* Check if deleting a linked record */
43	WARN_ON(!list_empty(&avr->dccpavr_node));
44	kmem_cache_free(dccp_ackvec_record_slab, avr);
45}
46
47static void dccp_ackvec_insert_avr(struct dccp_ackvec *av,
48				   struct dccp_ackvec_record *avr)
49{
50	/*
51	 * AVRs are sorted by seqno. Since we are sending them in order, we
52	 * just add the AVR at the head of the list.
53	 * -sorbo.
54	 */
55	if (!list_empty(&av->dccpav_records)) {
56		const struct dccp_ackvec_record *head =
57					list_entry(av->dccpav_records.next,
58						   struct dccp_ackvec_record,
59						   dccpavr_node);
60		BUG_ON(before48(avr->dccpavr_ack_seqno,
61				head->dccpavr_ack_seqno));
62	}
63
64	list_add(&avr->dccpavr_node, &av->dccpav_records);
65}
66
67int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb)
68{
69	struct dccp_sock *dp = dccp_sk(sk);
70	struct dccp_ackvec *av = dp->dccps_hc_rx_ackvec;
71	/* Figure out how many options do we need to represent the ackvec */
72	const u16 nr_opts = (av->dccpav_vec_len +
73			     DCCP_MAX_ACKVEC_OPT_LEN - 1) /
74			    DCCP_MAX_ACKVEC_OPT_LEN;
75	u16 len = av->dccpav_vec_len + 2 * nr_opts, i;
76	struct timeval now;
77	u32 elapsed_time;
78	const unsigned char *tail, *from;
79	unsigned char *to;
80	struct dccp_ackvec_record *avr;
81
82	if (DCCP_SKB_CB(skb)->dccpd_opt_len + len > DCCP_MAX_OPT_LEN)
83		return -1;
84
85	dccp_timestamp(sk, &now);
86	elapsed_time = timeval_delta(&now, &av->dccpav_time) / 10;
87
88	if (elapsed_time != 0 &&
89	    dccp_insert_option_elapsed_time(sk, skb, elapsed_time))
90		return -1;
91
92	avr = dccp_ackvec_record_new();
93	if (avr == NULL)
94		return -1;
95
96	DCCP_SKB_CB(skb)->dccpd_opt_len += len;
97
98	to   = skb_push(skb, len);
99	len  = av->dccpav_vec_len;
100	from = av->dccpav_buf + av->dccpav_buf_head;
101	tail = av->dccpav_buf + DCCP_MAX_ACKVEC_LEN;
102
103	for (i = 0; i < nr_opts; ++i) {
104		int copylen = len;
105
106		if (len > DCCP_MAX_ACKVEC_OPT_LEN)
107			copylen = DCCP_MAX_ACKVEC_OPT_LEN;
108
109		*to++ = DCCPO_ACK_VECTOR_0;
110		*to++ = copylen + 2;
111
112		/* Check if buf_head wraps */
113		if (from + copylen > tail) {
114			const u16 tailsize = tail - from;
115
116			memcpy(to, from, tailsize);
117			to	+= tailsize;
118			len	-= tailsize;
119			copylen	-= tailsize;
120			from	= av->dccpav_buf;
121		}
122
123		memcpy(to, from, copylen);
124		from += copylen;
125		to   += copylen;
126		len  -= copylen;
127	}
128
129	/*
130	 *	From RFC 4340, A.2:
131	 *
132	 *	For each acknowledgement it sends, the HC-Receiver will add an
133	 *	acknowledgement record.  ack_seqno will equal the HC-Receiver
134	 *	sequence number it used for the ack packet; ack_ptr will equal
135	 *	buf_head; ack_ackno will equal buf_ackno; and ack_nonce will
136	 *	equal buf_nonce.
137	 */
138	avr->dccpavr_ack_seqno = DCCP_SKB_CB(skb)->dccpd_seq;
139	avr->dccpavr_ack_ptr   = av->dccpav_buf_head;
140	avr->dccpavr_ack_ackno = av->dccpav_buf_ackno;
141	avr->dccpavr_ack_nonce = av->dccpav_buf_nonce;
142	avr->dccpavr_sent_len  = av->dccpav_vec_len;
143
144	dccp_ackvec_insert_avr(av, avr);
145
146	dccp_pr_debug("%s ACK Vector 0, len=%d, ack_seqno=%llu, "
147		      "ack_ackno=%llu\n",
148		      dccp_role(sk), avr->dccpavr_sent_len,
149		      (unsigned long long)avr->dccpavr_ack_seqno,
150		      (unsigned long long)avr->dccpavr_ack_ackno);
151	return 0;
152}
153
154struct dccp_ackvec *dccp_ackvec_alloc(const gfp_t priority)
155{
156	struct dccp_ackvec *av = kmem_cache_alloc(dccp_ackvec_slab, priority);
157
158	if (av != NULL) {
159		av->dccpav_buf_head	= DCCP_MAX_ACKVEC_LEN - 1;
160		av->dccpav_buf_ackno	= UINT48_MAX + 1;
161		av->dccpav_buf_nonce = av->dccpav_buf_nonce = 0;
162		av->dccpav_time.tv_sec	= 0;
163		av->dccpav_time.tv_usec	= 0;
164		av->dccpav_vec_len	= 0;
165		INIT_LIST_HEAD(&av->dccpav_records);
166	}
167
168	return av;
169}
170
171void dccp_ackvec_free(struct dccp_ackvec *av)
172{
173	if (unlikely(av == NULL))
174		return;
175
176	if (!list_empty(&av->dccpav_records)) {
177		struct dccp_ackvec_record *avr, *next;
178
179		list_for_each_entry_safe(avr, next, &av->dccpav_records,
180					 dccpavr_node) {
181			list_del_init(&avr->dccpavr_node);
182			dccp_ackvec_record_delete(avr);
183		}
184	}
185
186	kmem_cache_free(dccp_ackvec_slab, av);
187}
188
189static inline u8 dccp_ackvec_state(const struct dccp_ackvec *av,
190				   const u32 index)
191{
192	return av->dccpav_buf[index] & DCCP_ACKVEC_STATE_MASK;
193}
194
195static inline u8 dccp_ackvec_len(const struct dccp_ackvec *av,
196				 const u32 index)
197{
198	return av->dccpav_buf[index] & DCCP_ACKVEC_LEN_MASK;
199}
200
201/*
202 * If several packets are missing, the HC-Receiver may prefer to enter multiple
203 * bytes with run length 0, rather than a single byte with a larger run length;
204 * this simplifies table updates if one of the missing packets arrives.
205 */
206static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec *av,
207						 const unsigned int packets,
208						 const unsigned char state)
209{
210	unsigned int gap;
211	long new_head;
212
213	if (av->dccpav_vec_len + packets > DCCP_MAX_ACKVEC_LEN)
214		return -ENOBUFS;
215
216	gap	 = packets - 1;
217	new_head = av->dccpav_buf_head - packets;
218
219	if (new_head < 0) {
220		if (gap > 0) {
221			memset(av->dccpav_buf, DCCP_ACKVEC_STATE_NOT_RECEIVED,
222			       gap + new_head + 1);
223			gap = -new_head;
224		}
225		new_head += DCCP_MAX_ACKVEC_LEN;
226	}
227
228	av->dccpav_buf_head = new_head;
229
230	if (gap > 0)
231		memset(av->dccpav_buf + av->dccpav_buf_head + 1,
232		       DCCP_ACKVEC_STATE_NOT_RECEIVED, gap);
233
234	av->dccpav_buf[av->dccpav_buf_head] = state;
235	av->dccpav_vec_len += packets;
236	return 0;
237}
238
239/*
240 * Implements the RFC 4340, Appendix A
241 */
242int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk,
243		    const u64 ackno, const u8 state)
244{
245	/*
246	 * Check at the right places if the buffer is full, if it is, tell the
247	 * caller to start dropping packets till the HC-Sender acks our ACK
248	 * vectors, when we will free up space in dccpav_buf.
249	 *
250	 * We may well decide to do buffer compression, etc, but for now lets
251	 * just drop.
252	 *
253	 * From Appendix A.1.1 (`New Packets'):
254	 *
255	 *	Of course, the circular buffer may overflow, either when the
256	 *	HC-Sender is sending data at a very high rate, when the
257	 *	HC-Receiver's acknowledgements are not reaching the HC-Sender,
258	 *	or when the HC-Sender is forgetting to acknowledge those acks
259	 *	(so the HC-Receiver is unable to clean up old state). In this
260	 *	case, the HC-Receiver should either compress the buffer (by
261	 *	increasing run lengths when possible), transfer its state to
262	 *	a larger buffer, or, as a last resort, drop all received
263	 *	packets, without processing them whatsoever, until its buffer
264	 *	shrinks again.
265	 */
266
267	/* See if this is the first ackno being inserted */
268	if (av->dccpav_vec_len == 0) {
269		av->dccpav_buf[av->dccpav_buf_head] = state;
270		av->dccpav_vec_len = 1;
271	} else if (after48(ackno, av->dccpav_buf_ackno)) {
272		const u64 delta = dccp_delta_seqno(av->dccpav_buf_ackno,
273						   ackno);
274
275		/*
276		 * Look if the state of this packet is the same as the
277		 * previous ackno and if so if we can bump the head len.
278		 */
279		if (delta == 1 &&
280		    dccp_ackvec_state(av, av->dccpav_buf_head) == state &&
281		    (dccp_ackvec_len(av, av->dccpav_buf_head) <
282		     DCCP_ACKVEC_LEN_MASK))
283			av->dccpav_buf[av->dccpav_buf_head]++;
284		else if (dccp_ackvec_set_buf_head_state(av, delta, state))
285			return -ENOBUFS;
286	} else {
287		/*
288		 * A.1.2.  Old Packets
289		 *
290		 *	When a packet with Sequence Number S <= buf_ackno
291		 *	arrives, the HC-Receiver will scan the table for
292		 *	the byte corresponding to S. (Indexing structures
293		 *	could reduce the complexity of this scan.)
294		 */
295		u64 delta = dccp_delta_seqno(ackno, av->dccpav_buf_ackno);
296		u32 index = av->dccpav_buf_head;
297
298		while (1) {
299			const u8 len = dccp_ackvec_len(av, index);
300			const u8 state = dccp_ackvec_state(av, index);
301			/*
302			 * valid packets not yet in dccpav_buf have a reserved
303			 * entry, with a len equal to 0.
304			 */
305			if (state == DCCP_ACKVEC_STATE_NOT_RECEIVED &&
306			    len == 0 && delta == 0) { /* Found our
307							 reserved seat! */
308				dccp_pr_debug("Found %llu reserved seat!\n",
309					      (unsigned long long)ackno);
310				av->dccpav_buf[index] = state;
311				goto out;
312			}
313			/* len == 0 means one packet */
314			if (delta < len + 1)
315				goto out_duplicate;
316
317			delta -= len + 1;
318			if (++index == DCCP_MAX_ACKVEC_LEN)
319				index = 0;
320		}
321	}
322
323	av->dccpav_buf_ackno = ackno;
324	dccp_timestamp(sk, &av->dccpav_time);
325out:
326	return 0;
327
328out_duplicate:
329	/* Duplicate packet */
330	dccp_pr_debug("Received a dup or already considered lost "
331		      "packet: %llu\n", (unsigned long long)ackno);
332	return -EILSEQ;
333}
334
335#ifdef CONFIG_IP_DCCP_DEBUG
336void dccp_ackvector_print(const u64 ackno, const unsigned char *vector, int len)
337{
338	dccp_pr_debug_cat("ACK vector len=%d, ackno=%llu |", len,
339			 (unsigned long long)ackno);
340
341	while (len--) {
342		const u8 state = (*vector & DCCP_ACKVEC_STATE_MASK) >> 6;
343		const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK;
344
345		dccp_pr_debug_cat("%d,%d|", state, rl);
346		++vector;
347	}
348
349	dccp_pr_debug_cat("\n");
350}
351
352void dccp_ackvec_print(const struct dccp_ackvec *av)
353{
354	dccp_ackvector_print(av->dccpav_buf_ackno,
355			     av->dccpav_buf + av->dccpav_buf_head,
356			     av->dccpav_vec_len);
357}
358#endif
359
360static void dccp_ackvec_throw_record(struct dccp_ackvec *av,
361				     struct dccp_ackvec_record *avr)
362{
363	struct dccp_ackvec_record *next;
364
365	/* sort out vector length */
366	if (av->dccpav_buf_head <= avr->dccpavr_ack_ptr)
367		av->dccpav_vec_len = avr->dccpavr_ack_ptr - av->dccpav_buf_head;
368	else
369		av->dccpav_vec_len = DCCP_MAX_ACKVEC_LEN - 1
370				     - av->dccpav_buf_head
371				     + avr->dccpavr_ack_ptr;
372
373	/* free records */
374	list_for_each_entry_safe_from(avr, next, &av->dccpav_records,
375				      dccpavr_node) {
376		list_del_init(&avr->dccpavr_node);
377		dccp_ackvec_record_delete(avr);
378	}
379}
380
381void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec *av, struct sock *sk,
382				 const u64 ackno)
383{
384	struct dccp_ackvec_record *avr;
385
386	/*
387	 * If we traverse backwards, it should be faster when we have large
388	 * windows. We will be receiving ACKs for stuff we sent a while back
389	 * -sorbo.
390	 */
391	list_for_each_entry_reverse(avr, &av->dccpav_records, dccpavr_node) {
392		if (ackno == avr->dccpavr_ack_seqno) {
393			dccp_pr_debug("%s ACK packet 0, len=%d, ack_seqno=%llu, "
394				      "ack_ackno=%llu, ACKED!\n",
395				      dccp_role(sk), 1,
396				      (unsigned long long)avr->dccpavr_ack_seqno,
397				      (unsigned long long)avr->dccpavr_ack_ackno);
398			dccp_ackvec_throw_record(av, avr);
399			break;
400		} else if (avr->dccpavr_ack_seqno > ackno)
401			break; /* old news */
402	}
403}
404
405static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec *av,
406					    struct sock *sk, u64 *ackno,
407					    const unsigned char len,
408					    const unsigned char *vector)
409{
410	unsigned char i;
411	struct dccp_ackvec_record *avr;
412
413	/* Check if we actually sent an ACK vector */
414	if (list_empty(&av->dccpav_records))
415		return;
416
417	i = len;
418	avr = list_entry(av->dccpav_records.next, struct dccp_ackvec_record,
419			 dccpavr_node);
420	while (i--) {
421		const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK;
422		u64 ackno_end_rl;
423
424		dccp_set_seqno(&ackno_end_rl, *ackno - rl);
425
426		/*
427		 * If our AVR sequence number is greater than the ack, go
428		 * forward in the AVR list until it is not so.
429		 */
430		list_for_each_entry_from(avr, &av->dccpav_records,
431					 dccpavr_node) {
432			if (!after48(avr->dccpavr_ack_seqno, *ackno))
433				goto found;
434		}
435		/* End of the dccpav_records list, not found, exit */
436		break;
437found:
438		if (between48(avr->dccpavr_ack_seqno, ackno_end_rl, *ackno)) {
439			const u8 state = *vector & DCCP_ACKVEC_STATE_MASK;
440			if (state != DCCP_ACKVEC_STATE_NOT_RECEIVED) {
441				dccp_pr_debug("%s ACK vector 0, len=%d, "
442					      "ack_seqno=%llu, ack_ackno=%llu, "
443					      "ACKED!\n",
444					      dccp_role(sk), len,
445					      (unsigned long long)
446					      avr->dccpavr_ack_seqno,
447					      (unsigned long long)
448					      avr->dccpavr_ack_ackno);
449				dccp_ackvec_throw_record(av, avr);
450				break;
451			}
452			/*
453			 * If it wasn't received, continue scanning... we might
454			 * find another one.
455			 */
456		}
457
458		dccp_set_seqno(ackno, ackno_end_rl - 1);
459		++vector;
460	}
461}
462
463int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb,
464		      u64 *ackno, const u8 opt, const u8 *value, const u8 len)
465{
466	if (len > DCCP_MAX_ACKVEC_OPT_LEN)
467		return -1;
468
469	/* dccp_ackvector_print(DCCP_SKB_CB(skb)->dccpd_ack_seq, value, len); */
470	dccp_ackvec_check_rcv_ackvector(dccp_sk(sk)->dccps_hc_rx_ackvec, sk,
471					ackno, len, value);
472	return 0;
473}
474
475int __init dccp_ackvec_init(void)
476{
477	dccp_ackvec_slab = kmem_cache_create("dccp_ackvec",
478					     sizeof(struct dccp_ackvec), 0,
479					     SLAB_HWCACHE_ALIGN, NULL, NULL);
480	if (dccp_ackvec_slab == NULL)
481		goto out_err;
482
483	dccp_ackvec_record_slab =
484			kmem_cache_create("dccp_ackvec_record",
485					  sizeof(struct dccp_ackvec_record),
486					  0, SLAB_HWCACHE_ALIGN, NULL, NULL);
487	if (dccp_ackvec_record_slab == NULL)
488		goto out_destroy_slab;
489
490	return 0;
491
492out_destroy_slab:
493	kmem_cache_destroy(dccp_ackvec_slab);
494	dccp_ackvec_slab = NULL;
495out_err:
496	DCCP_CRIT("Unable to create Ack Vector slab cache");
497	return -ENOBUFS;
498}
499
500void dccp_ackvec_exit(void)
501{
502	if (dccp_ackvec_slab != NULL) {
503		kmem_cache_destroy(dccp_ackvec_slab);
504		dccp_ackvec_slab = NULL;
505	}
506	if (dccp_ackvec_record_slab != NULL) {
507		kmem_cache_destroy(dccp_ackvec_record_slab);
508		dccp_ackvec_record_slab = NULL;
509	}
510}
511