de84dd34c93fdf4751a31f0c27b8b0b49680cc50
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
);
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
61 int dccp_ackvec_update_records(struct dccp_ackvec
*av
, u64 seqno
, u8 nonce_sum
)
63 struct dccp_ackvec_record
*avr
;
65 avr
= kmem_cache_alloc(dccp_ackvec_record_slab
, GFP_ATOMIC
);
69 avr
->avr_ack_seqno
= seqno
;
70 avr
->avr_ack_ptr
= av
->av_buf_head
;
71 avr
->avr_ack_ackno
= av
->av_buf_ackno
;
72 avr
->avr_ack_nonce
= nonce_sum
;
73 avr
->avr_ack_runlen
= dccp_ackvec_runlen(av
->av_buf
+ av
->av_buf_head
);
75 * Since GSS is incremented for each packet, the list is automatically
76 * arranged in descending order of @ack_seqno.
78 list_add(&avr
->avr_node
, &av
->av_records
);
80 dccp_pr_debug("Added Vector, ack_seqno=%llu, ack_ackno=%llu (rl=%u)\n",
81 (unsigned long long)avr
->avr_ack_seqno
,
82 (unsigned long long)avr
->avr_ack_ackno
,
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.
92 static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec
*av
,
93 const unsigned int packets
,
94 const unsigned char state
)
99 if (av
->av_vec_len
+ packets
> DCCPAV_MAX_ACKVEC_LEN
)
103 new_head
= av
->av_buf_head
- packets
;
107 memset(av
->av_buf
, DCCPAV_NOT_RECEIVED
,
111 new_head
+= DCCPAV_MAX_ACKVEC_LEN
;
114 av
->av_buf_head
= new_head
;
117 memset(av
->av_buf
+ av
->av_buf_head
+ 1,
118 DCCPAV_NOT_RECEIVED
, gap
);
120 av
->av_buf
[av
->av_buf_head
] = state
;
121 av
->av_vec_len
+= packets
;
126 * Implements the RFC 4340, Appendix A
128 int dccp_ackvec_add(struct dccp_ackvec
*av
, const struct sock
*sk
,
129 const u64 ackno
, const u8 state
)
131 u8
*cur_head
= av
->av_buf
+ av
->av_buf_head
,
132 *buf_end
= av
->av_buf
+ DCCPAV_MAX_ACKVEC_LEN
;
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
136 * vectors, when we will free up space in av_buf.
138 * We may well decide to do buffer compression, etc, but for now lets
141 * From Appendix A.1.1 (`New Packets'):
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
155 /* See if this is the first ackno being inserted */
156 if (av
->av_vec_len
== 0) {
159 } else if (after48(ackno
, av
->av_buf_ackno
)) {
160 const u64 delta
= dccp_delta_seqno(av
->av_buf_ackno
, ackno
);
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.
166 if (delta
== 1 && dccp_ackvec_state(cur_head
) == state
&&
167 dccp_ackvec_runlen(cur_head
) < DCCPAV_MAX_RUNLEN
)
169 else if (dccp_ackvec_set_buf_head_state(av
, delta
, state
))
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
178 * could reduce the complexity of this scan.)
180 u64 delta
= dccp_delta_seqno(ackno
, av
->av_buf_ackno
);
183 const u8 len
= dccp_ackvec_runlen(cur_head
);
185 * valid packets not yet in av_buf have a reserved
186 * entry, with a len equal to 0.
188 if (*cur_head
== DCCPAV_NOT_RECEIVED
&& delta
== 0) {
189 dccp_pr_debug("Found %llu reserved seat!\n",
190 (unsigned long long)ackno
);
194 /* len == 0 means one packet */
199 if (++cur_head
== buf_end
)
200 cur_head
= av
->av_buf
;
204 av
->av_buf_ackno
= ackno
;
209 /* Duplicate packet */
210 dccp_pr_debug("Received a dup or already considered lost "
211 "packet: %llu\n", (unsigned long long)ackno
);
215 static void dccp_ackvec_throw_record(struct dccp_ackvec
*av
,
216 struct dccp_ackvec_record
*avr
)
218 struct dccp_ackvec_record
*next
;
220 /* sort out vector length */
221 if (av
->av_buf_head
<= avr
->avr_ack_ptr
)
222 av
->av_vec_len
= avr
->avr_ack_ptr
- av
->av_buf_head
;
224 av
->av_vec_len
= DCCPAV_MAX_ACKVEC_LEN
- 1 -
225 av
->av_buf_head
+ avr
->avr_ack_ptr
;
228 list_for_each_entry_safe_from(avr
, next
, &av
->av_records
, avr_node
) {
229 list_del(&avr
->avr_node
);
230 kmem_cache_free(dccp_ackvec_record_slab
, avr
);
234 void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec
*av
, struct sock
*sk
,
237 struct dccp_ackvec_record
*avr
;
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
244 list_for_each_entry_reverse(avr
, &av
->av_records
, avr_node
) {
245 if (ackno
== avr
->avr_ack_seqno
) {
246 dccp_pr_debug("%s ACK packet 0, len=%d, ack_seqno=%llu, "
247 "ack_ackno=%llu, ACKED!\n",
248 dccp_role(sk
), avr
->avr_ack_runlen
,
249 (unsigned long long)avr
->avr_ack_seqno
,
250 (unsigned long long)avr
->avr_ack_ackno
);
251 dccp_ackvec_throw_record(av
, avr
);
253 } else if (avr
->avr_ack_seqno
> ackno
)
254 break; /* old news */
258 static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec
*av
,
259 struct sock
*sk
, u64
*ackno
,
260 const unsigned char len
,
261 const unsigned char *vector
)
264 struct dccp_ackvec_record
*avr
;
266 /* Check if we actually sent an ACK vector */
267 if (list_empty(&av
->av_records
))
273 * I think it might be more efficient to work backwards. See comment on
276 avr
= list_entry(av
->av_records
.next
, struct dccp_ackvec_record
, avr_node
);
278 const u8 rl
= dccp_ackvec_runlen(vector
);
281 dccp_set_seqno(&ackno_end_rl
, *ackno
- rl
);
284 * If our AVR sequence number is greater than the ack, go
285 * forward in the AVR list until it is not so.
287 list_for_each_entry_from(avr
, &av
->av_records
, avr_node
) {
288 if (!after48(avr
->avr_ack_seqno
, *ackno
))
291 /* End of the av_records list, not found, exit */
294 if (between48(avr
->avr_ack_seqno
, ackno_end_rl
, *ackno
)) {
295 if (dccp_ackvec_state(vector
) != DCCPAV_NOT_RECEIVED
) {
296 dccp_pr_debug("%s ACK vector 0, len=%d, "
297 "ack_seqno=%llu, ack_ackno=%llu, "
304 dccp_ackvec_throw_record(av
, avr
);
308 * If it wasn't received, continue scanning... we might
313 dccp_set_seqno(ackno
, ackno_end_rl
- 1);
318 int dccp_ackvec_parse(struct sock
*sk
, const struct sk_buff
*skb
,
319 u64
*ackno
, const u8 opt
, const u8
*value
, const u8 len
)
321 if (len
> DCCP_SINGLE_OPT_MAXLEN
)
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
,
330 int __init
dccp_ackvec_init(void)
332 dccp_ackvec_slab
= kmem_cache_create("dccp_ackvec",
333 sizeof(struct dccp_ackvec
), 0,
334 SLAB_HWCACHE_ALIGN
, NULL
);
335 if (dccp_ackvec_slab
== NULL
)
338 dccp_ackvec_record_slab
= kmem_cache_create("dccp_ackvec_record",
339 sizeof(struct dccp_ackvec_record
),
340 0, SLAB_HWCACHE_ALIGN
, NULL
);
341 if (dccp_ackvec_record_slab
== NULL
)
342 goto out_destroy_slab
;
347 kmem_cache_destroy(dccp_ackvec_slab
);
348 dccp_ackvec_slab
= NULL
;
350 DCCP_CRIT("Unable to create Ack Vector slab cache");
354 void dccp_ackvec_exit(void)
356 if (dccp_ackvec_slab
!= NULL
) {
357 kmem_cache_destroy(dccp_ackvec_slab
);
358 dccp_ackvec_slab
= NULL
;
360 if (dccp_ackvec_record_slab
!= NULL
) {
361 kmem_cache_destroy(dccp_ackvec_record_slab
);
362 dccp_ackvec_record_slab
= NULL
;
This page took 0.03922 seconds and 4 git commands to generate.