4 * An implementation of Ack Vectors for the DCCP protocol
5 * Copyright (c) 2007 University of Aberdeen, Scotland, UK
6 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@ghostprotocols.net>
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;
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>
24 static struct kmem_cache
*dccp_ackvec_slab
;
25 static struct kmem_cache
*dccp_ackvec_record_slab
;
27 struct dccp_ackvec
*dccp_ackvec_alloc(const gfp_t priority
)
29 struct dccp_ackvec
*av
= kmem_cache_zalloc(dccp_ackvec_slab
, priority
);
32 av
->av_buf_head
= DCCPAV_MAX_ACKVEC_LEN
- 1;
33 INIT_LIST_HEAD(&av
->av_records
);
38 static void dccp_ackvec_purge_records(struct dccp_ackvec
*av
)
40 struct dccp_ackvec_record
*cur
, *next
;
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
);
47 void dccp_ackvec_free(struct dccp_ackvec
*av
)
49 if (likely(av
!= NULL
)) {
50 dccp_ackvec_purge_records(av
);
51 kmem_cache_free(dccp_ackvec_slab
, av
);
55 static void dccp_ackvec_insert_avr(struct dccp_ackvec
*av
,
56 struct dccp_ackvec_record
*avr
)
59 * AVRs are sorted by seqno. Since we are sending them in order, we
60 * just add the AVR at the head of the list.
63 if (!list_empty(&av
->av_records
)) {
64 const struct dccp_ackvec_record
*head
=
65 list_entry(av
->av_records
.next
,
66 struct dccp_ackvec_record
,
68 BUG_ON(before48(avr
->avr_ack_seqno
, head
->avr_ack_seqno
));
71 list_add(&avr
->avr_node
, &av
->av_records
);
74 int dccp_insert_option_ackvec(struct sock
*sk
, struct sk_buff
*skb
)
76 struct dccp_sock
*dp
= dccp_sk(sk
);
77 struct dccp_ackvec
*av
= dp
->dccps_hc_rx_ackvec
;
78 /* Figure out how many options do we need to represent the ackvec */
79 const u8 nr_opts
= DIV_ROUND_UP(av
->av_vec_len
, DCCP_SINGLE_OPT_MAXLEN
);
80 u16 len
= av
->av_vec_len
+ 2 * nr_opts
;
82 const unsigned char *tail
, *from
;
84 struct dccp_ackvec_record
*avr
;
86 if (DCCP_SKB_CB(skb
)->dccpd_opt_len
+ len
> DCCP_MAX_OPT_LEN
)
89 avr
= kmem_cache_alloc(dccp_ackvec_record_slab
, GFP_ATOMIC
);
93 DCCP_SKB_CB(skb
)->dccpd_opt_len
+= len
;
95 to
= skb_push(skb
, len
);
97 from
= av
->av_buf
+ av
->av_buf_head
;
98 tail
= av
->av_buf
+ DCCPAV_MAX_ACKVEC_LEN
;
100 for (i
= 0; i
< nr_opts
; ++i
) {
103 if (len
> DCCP_SINGLE_OPT_MAXLEN
)
104 copylen
= DCCP_SINGLE_OPT_MAXLEN
;
107 * RFC 4340, 12.2: Encode the Nonce Echo for this Ack Vector via
108 * its type; ack_nonce is the sum of all individual buf_nonce's.
110 nonce
^= av
->av_buf_nonce
[i
];
112 *to
++ = DCCPO_ACK_VECTOR_0
+ av
->av_buf_nonce
[i
];
115 /* Check if buf_head wraps */
116 if (from
+ copylen
> tail
) {
117 const u16 tailsize
= tail
- from
;
119 memcpy(to
, from
, tailsize
);
126 memcpy(to
, from
, copylen
);
133 * Each sent Ack Vector is recorded in the list, as per A.2 of RFC 4340.
135 avr
->avr_ack_seqno
= DCCP_SKB_CB(skb
)->dccpd_seq
;
136 avr
->avr_ack_ptr
= av
->av_buf_head
;
137 avr
->avr_ack_ackno
= av
->av_buf_ackno
;
138 avr
->avr_ack_nonce
= nonce
;
139 avr
->avr_ack_runlen
= dccp_ackvec_runlen(av
->av_buf
+ av
->av_buf_head
);
141 dccp_ackvec_insert_avr(av
, avr
);
143 dccp_pr_debug("%s ACK Vector 0, len=%d, ack_seqno=%llu, "
145 dccp_role(sk
), avr
->avr_ack_runlen
,
146 (unsigned long long)avr
->avr_ack_seqno
,
147 (unsigned long long)avr
->avr_ack_ackno
);
152 * If several packets are missing, the HC-Receiver may prefer to enter multiple
153 * bytes with run length 0, rather than a single byte with a larger run length;
154 * this simplifies table updates if one of the missing packets arrives.
156 static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec
*av
,
157 const unsigned int packets
,
158 const unsigned char state
)
163 if (av
->av_vec_len
+ packets
> DCCPAV_MAX_ACKVEC_LEN
)
167 new_head
= av
->av_buf_head
- packets
;
171 memset(av
->av_buf
, DCCPAV_NOT_RECEIVED
,
175 new_head
+= DCCPAV_MAX_ACKVEC_LEN
;
178 av
->av_buf_head
= new_head
;
181 memset(av
->av_buf
+ av
->av_buf_head
+ 1,
182 DCCPAV_NOT_RECEIVED
, gap
);
184 av
->av_buf
[av
->av_buf_head
] = state
;
185 av
->av_vec_len
+= packets
;
190 * Implements the RFC 4340, Appendix A
192 int dccp_ackvec_add(struct dccp_ackvec
*av
, const struct sock
*sk
,
193 const u64 ackno
, const u8 state
)
195 u8
*cur_head
= av
->av_buf
+ av
->av_buf_head
,
196 *buf_end
= av
->av_buf
+ DCCPAV_MAX_ACKVEC_LEN
;
198 * Check at the right places if the buffer is full, if it is, tell the
199 * caller to start dropping packets till the HC-Sender acks our ACK
200 * vectors, when we will free up space in av_buf.
202 * We may well decide to do buffer compression, etc, but for now lets
205 * From Appendix A.1.1 (`New Packets'):
207 * Of course, the circular buffer may overflow, either when the
208 * HC-Sender is sending data at a very high rate, when the
209 * HC-Receiver's acknowledgements are not reaching the HC-Sender,
210 * or when the HC-Sender is forgetting to acknowledge those acks
211 * (so the HC-Receiver is unable to clean up old state). In this
212 * case, the HC-Receiver should either compress the buffer (by
213 * increasing run lengths when possible), transfer its state to
214 * a larger buffer, or, as a last resort, drop all received
215 * packets, without processing them whatsoever, until its buffer
219 /* See if this is the first ackno being inserted */
220 if (av
->av_vec_len
== 0) {
223 } else if (after48(ackno
, av
->av_buf_ackno
)) {
224 const u64 delta
= dccp_delta_seqno(av
->av_buf_ackno
, ackno
);
227 * Look if the state of this packet is the same as the
228 * previous ackno and if so if we can bump the head len.
230 if (delta
== 1 && dccp_ackvec_state(cur_head
) == state
&&
231 dccp_ackvec_runlen(cur_head
) < DCCPAV_MAX_RUNLEN
)
233 else if (dccp_ackvec_set_buf_head_state(av
, delta
, state
))
239 * When a packet with Sequence Number S <= buf_ackno
240 * arrives, the HC-Receiver will scan the table for
241 * the byte corresponding to S. (Indexing structures
242 * could reduce the complexity of this scan.)
244 u64 delta
= dccp_delta_seqno(ackno
, av
->av_buf_ackno
);
247 const u8 len
= dccp_ackvec_runlen(cur_head
);
249 * valid packets not yet in av_buf have a reserved
250 * entry, with a len equal to 0.
252 if (*cur_head
== DCCPAV_NOT_RECEIVED
&& delta
== 0) {
253 dccp_pr_debug("Found %llu reserved seat!\n",
254 (unsigned long long)ackno
);
258 /* len == 0 means one packet */
263 if (++cur_head
== buf_end
)
264 cur_head
= av
->av_buf
;
268 av
->av_buf_ackno
= ackno
;
273 /* Duplicate packet */
274 dccp_pr_debug("Received a dup or already considered lost "
275 "packet: %llu\n", (unsigned long long)ackno
);
279 static void dccp_ackvec_throw_record(struct dccp_ackvec
*av
,
280 struct dccp_ackvec_record
*avr
)
282 struct dccp_ackvec_record
*next
;
284 /* sort out vector length */
285 if (av
->av_buf_head
<= avr
->avr_ack_ptr
)
286 av
->av_vec_len
= avr
->avr_ack_ptr
- av
->av_buf_head
;
288 av
->av_vec_len
= DCCPAV_MAX_ACKVEC_LEN
- 1 -
289 av
->av_buf_head
+ avr
->avr_ack_ptr
;
292 list_for_each_entry_safe_from(avr
, next
, &av
->av_records
, avr_node
) {
293 list_del(&avr
->avr_node
);
294 kmem_cache_free(dccp_ackvec_record_slab
, avr
);
298 void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec
*av
, struct sock
*sk
,
301 struct dccp_ackvec_record
*avr
;
304 * If we traverse backwards, it should be faster when we have large
305 * windows. We will be receiving ACKs for stuff we sent a while back
308 list_for_each_entry_reverse(avr
, &av
->av_records
, avr_node
) {
309 if (ackno
== avr
->avr_ack_seqno
) {
310 dccp_pr_debug("%s ACK packet 0, len=%d, ack_seqno=%llu, "
311 "ack_ackno=%llu, ACKED!\n",
312 dccp_role(sk
), avr
->avr_ack_runlen
,
313 (unsigned long long)avr
->avr_ack_seqno
,
314 (unsigned long long)avr
->avr_ack_ackno
);
315 dccp_ackvec_throw_record(av
, avr
);
317 } else if (avr
->avr_ack_seqno
> ackno
)
318 break; /* old news */
322 static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec
*av
,
323 struct sock
*sk
, u64
*ackno
,
324 const unsigned char len
,
325 const unsigned char *vector
)
328 struct dccp_ackvec_record
*avr
;
330 /* Check if we actually sent an ACK vector */
331 if (list_empty(&av
->av_records
))
337 * I think it might be more efficient to work backwards. See comment on
340 avr
= list_entry(av
->av_records
.next
, struct dccp_ackvec_record
, avr_node
);
342 const u8 rl
= dccp_ackvec_runlen(vector
);
345 dccp_set_seqno(&ackno_end_rl
, *ackno
- rl
);
348 * If our AVR sequence number is greater than the ack, go
349 * forward in the AVR list until it is not so.
351 list_for_each_entry_from(avr
, &av
->av_records
, avr_node
) {
352 if (!after48(avr
->avr_ack_seqno
, *ackno
))
355 /* End of the av_records list, not found, exit */
358 if (between48(avr
->avr_ack_seqno
, ackno_end_rl
, *ackno
)) {
359 if (dccp_ackvec_state(vector
) != DCCPAV_NOT_RECEIVED
) {
360 dccp_pr_debug("%s ACK vector 0, len=%d, "
361 "ack_seqno=%llu, ack_ackno=%llu, "
368 dccp_ackvec_throw_record(av
, avr
);
372 * If it wasn't received, continue scanning... we might
377 dccp_set_seqno(ackno
, ackno_end_rl
- 1);
382 int dccp_ackvec_parse(struct sock
*sk
, const struct sk_buff
*skb
,
383 u64
*ackno
, const u8 opt
, const u8
*value
, const u8 len
)
385 if (len
> DCCP_SINGLE_OPT_MAXLEN
)
388 /* dccp_ackvector_print(DCCP_SKB_CB(skb)->dccpd_ack_seq, value, len); */
389 dccp_ackvec_check_rcv_ackvector(dccp_sk(sk
)->dccps_hc_rx_ackvec
, sk
,
394 int __init
dccp_ackvec_init(void)
396 dccp_ackvec_slab
= kmem_cache_create("dccp_ackvec",
397 sizeof(struct dccp_ackvec
), 0,
398 SLAB_HWCACHE_ALIGN
, NULL
);
399 if (dccp_ackvec_slab
== NULL
)
402 dccp_ackvec_record_slab
= kmem_cache_create("dccp_ackvec_record",
403 sizeof(struct dccp_ackvec_record
),
404 0, SLAB_HWCACHE_ALIGN
, NULL
);
405 if (dccp_ackvec_record_slab
== NULL
)
406 goto out_destroy_slab
;
411 kmem_cache_destroy(dccp_ackvec_slab
);
412 dccp_ackvec_slab
= NULL
;
414 DCCP_CRIT("Unable to create Ack Vector slab cache");
418 void dccp_ackvec_exit(void)
420 if (dccp_ackvec_slab
!= NULL
) {
421 kmem_cache_destroy(dccp_ackvec_slab
);
422 dccp_ackvec_slab
= NULL
;
424 if (dccp_ackvec_record_slab
!= NULL
) {
425 kmem_cache_destroy(dccp_ackvec_record_slab
);
426 dccp_ackvec_record_slab
= NULL
;