4 * An implementation of the DCCP protocol
5 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@ghostprotocols.net>
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;
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>
24 static struct kmem_cache
*dccp_ackvec_slab
;
25 static struct kmem_cache
*dccp_ackvec_record_slab
;
27 static struct dccp_ackvec_record
*dccp_ackvec_record_new(void)
29 struct dccp_ackvec_record
*avr
=
30 kmem_cache_alloc(dccp_ackvec_record_slab
, GFP_ATOMIC
);
33 INIT_LIST_HEAD(&avr
->dccpavr_node
);
38 static void dccp_ackvec_record_delete(struct dccp_ackvec_record
*avr
)
40 if (unlikely(avr
== NULL
))
42 /* Check if deleting a linked record */
43 WARN_ON(!list_empty(&avr
->dccpavr_node
));
44 kmem_cache_free(dccp_ackvec_record_slab
, avr
);
47 static void dccp_ackvec_insert_avr(struct dccp_ackvec
*av
,
48 struct dccp_ackvec_record
*avr
)
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.
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
,
60 BUG_ON(before48(avr
->dccpavr_ack_seqno
,
61 head
->dccpavr_ack_seqno
));
64 list_add(&avr
->dccpavr_node
, &av
->dccpav_records
);
67 int dccp_insert_option_ackvec(struct sock
*sk
, struct sk_buff
*skb
)
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
;
77 const unsigned char *tail
, *from
;
79 struct dccp_ackvec_record
*avr
;
82 if (DCCP_SKB_CB(skb
)->dccpd_opt_len
+ len
> DCCP_MAX_OPT_LEN
)
85 delta
= ktime_us_delta(ktime_get_real(), av
->dccpav_time
);
86 elapsed_time
= delta
/ 10;
88 if (elapsed_time
!= 0 &&
89 dccp_insert_option_elapsed_time(sk
, skb
, elapsed_time
))
92 avr
= dccp_ackvec_record_new();
96 DCCP_SKB_CB(skb
)->dccpd_opt_len
+= len
;
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
;
103 for (i
= 0; i
< nr_opts
; ++i
) {
106 if (len
> DCCP_MAX_ACKVEC_OPT_LEN
)
107 copylen
= DCCP_MAX_ACKVEC_OPT_LEN
;
109 *to
++ = DCCPO_ACK_VECTOR_0
;
112 /* Check if buf_head wraps */
113 if (from
+ copylen
> tail
) {
114 const u16 tailsize
= tail
- from
;
116 memcpy(to
, from
, tailsize
);
120 from
= av
->dccpav_buf
;
123 memcpy(to
, from
, copylen
);
130 * From RFC 4340, A.2:
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
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
;
144 dccp_ackvec_insert_avr(av
, avr
);
146 dccp_pr_debug("%s ACK Vector 0, len=%d, ack_seqno=%llu, "
148 dccp_role(sk
), avr
->dccpavr_sent_len
,
149 (unsigned long long)avr
->dccpavr_ack_seqno
,
150 (unsigned long long)avr
->dccpavr_ack_ackno
);
154 struct dccp_ackvec
*dccp_ackvec_alloc(const gfp_t priority
)
156 struct dccp_ackvec
*av
= kmem_cache_alloc(dccp_ackvec_slab
, priority
);
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
= ktime_set(0, 0);
163 av
->dccpav_vec_len
= 0;
164 INIT_LIST_HEAD(&av
->dccpav_records
);
170 void dccp_ackvec_free(struct dccp_ackvec
*av
)
172 if (unlikely(av
== NULL
))
175 if (!list_empty(&av
->dccpav_records
)) {
176 struct dccp_ackvec_record
*avr
, *next
;
178 list_for_each_entry_safe(avr
, next
, &av
->dccpav_records
,
180 list_del_init(&avr
->dccpavr_node
);
181 dccp_ackvec_record_delete(avr
);
185 kmem_cache_free(dccp_ackvec_slab
, av
);
188 static inline u8
dccp_ackvec_state(const struct dccp_ackvec
*av
,
191 return av
->dccpav_buf
[index
] & DCCP_ACKVEC_STATE_MASK
;
194 static inline u8
dccp_ackvec_len(const struct dccp_ackvec
*av
,
197 return av
->dccpav_buf
[index
] & DCCP_ACKVEC_LEN_MASK
;
201 * If several packets are missing, the HC-Receiver may prefer to enter multiple
202 * bytes with run length 0, rather than a single byte with a larger run length;
203 * this simplifies table updates if one of the missing packets arrives.
205 static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec
*av
,
206 const unsigned int packets
,
207 const unsigned char state
)
212 if (av
->dccpav_vec_len
+ packets
> DCCP_MAX_ACKVEC_LEN
)
216 new_head
= av
->dccpav_buf_head
- packets
;
220 memset(av
->dccpav_buf
, DCCP_ACKVEC_STATE_NOT_RECEIVED
,
224 new_head
+= DCCP_MAX_ACKVEC_LEN
;
227 av
->dccpav_buf_head
= new_head
;
230 memset(av
->dccpav_buf
+ av
->dccpav_buf_head
+ 1,
231 DCCP_ACKVEC_STATE_NOT_RECEIVED
, gap
);
233 av
->dccpav_buf
[av
->dccpav_buf_head
] = state
;
234 av
->dccpav_vec_len
+= packets
;
239 * Implements the RFC 4340, Appendix A
241 int dccp_ackvec_add(struct dccp_ackvec
*av
, const struct sock
*sk
,
242 const u64 ackno
, const u8 state
)
245 * Check at the right places if the buffer is full, if it is, tell the
246 * caller to start dropping packets till the HC-Sender acks our ACK
247 * vectors, when we will free up space in dccpav_buf.
249 * We may well decide to do buffer compression, etc, but for now lets
252 * From Appendix A.1.1 (`New Packets'):
254 * Of course, the circular buffer may overflow, either when the
255 * HC-Sender is sending data at a very high rate, when the
256 * HC-Receiver's acknowledgements are not reaching the HC-Sender,
257 * or when the HC-Sender is forgetting to acknowledge those acks
258 * (so the HC-Receiver is unable to clean up old state). In this
259 * case, the HC-Receiver should either compress the buffer (by
260 * increasing run lengths when possible), transfer its state to
261 * a larger buffer, or, as a last resort, drop all received
262 * packets, without processing them whatsoever, until its buffer
266 /* See if this is the first ackno being inserted */
267 if (av
->dccpav_vec_len
== 0) {
268 av
->dccpav_buf
[av
->dccpav_buf_head
] = state
;
269 av
->dccpav_vec_len
= 1;
270 } else if (after48(ackno
, av
->dccpav_buf_ackno
)) {
271 const u64 delta
= dccp_delta_seqno(av
->dccpav_buf_ackno
,
275 * Look if the state of this packet is the same as the
276 * previous ackno and if so if we can bump the head len.
279 dccp_ackvec_state(av
, av
->dccpav_buf_head
) == state
&&
280 (dccp_ackvec_len(av
, av
->dccpav_buf_head
) <
281 DCCP_ACKVEC_LEN_MASK
))
282 av
->dccpav_buf
[av
->dccpav_buf_head
]++;
283 else if (dccp_ackvec_set_buf_head_state(av
, delta
, state
))
289 * When a packet with Sequence Number S <= buf_ackno
290 * arrives, the HC-Receiver will scan the table for
291 * the byte corresponding to S. (Indexing structures
292 * could reduce the complexity of this scan.)
294 u64 delta
= dccp_delta_seqno(ackno
, av
->dccpav_buf_ackno
);
295 u32 index
= av
->dccpav_buf_head
;
298 const u8 len
= dccp_ackvec_len(av
, index
);
299 const u8 state
= dccp_ackvec_state(av
, index
);
301 * valid packets not yet in dccpav_buf have a reserved
302 * entry, with a len equal to 0.
304 if (state
== DCCP_ACKVEC_STATE_NOT_RECEIVED
&&
305 len
== 0 && delta
== 0) { /* Found our
307 dccp_pr_debug("Found %llu reserved seat!\n",
308 (unsigned long long)ackno
);
309 av
->dccpav_buf
[index
] = state
;
312 /* len == 0 means one packet */
317 if (++index
== DCCP_MAX_ACKVEC_LEN
)
322 av
->dccpav_buf_ackno
= ackno
;
323 av
->dccpav_time
= ktime_get_real();
328 /* Duplicate packet */
329 dccp_pr_debug("Received a dup or already considered lost "
330 "packet: %llu\n", (unsigned long long)ackno
);
334 #ifdef CONFIG_IP_DCCP_DEBUG
335 void dccp_ackvector_print(const u64 ackno
, const unsigned char *vector
, int len
)
337 dccp_pr_debug_cat("ACK vector len=%d, ackno=%llu |", len
,
338 (unsigned long long)ackno
);
341 const u8 state
= (*vector
& DCCP_ACKVEC_STATE_MASK
) >> 6;
342 const u8 rl
= *vector
& DCCP_ACKVEC_LEN_MASK
;
344 dccp_pr_debug_cat("%d,%d|", state
, rl
);
348 dccp_pr_debug_cat("\n");
351 void dccp_ackvec_print(const struct dccp_ackvec
*av
)
353 dccp_ackvector_print(av
->dccpav_buf_ackno
,
354 av
->dccpav_buf
+ av
->dccpav_buf_head
,
359 static void dccp_ackvec_throw_record(struct dccp_ackvec
*av
,
360 struct dccp_ackvec_record
*avr
)
362 struct dccp_ackvec_record
*next
;
364 /* sort out vector length */
365 if (av
->dccpav_buf_head
<= avr
->dccpavr_ack_ptr
)
366 av
->dccpav_vec_len
= avr
->dccpavr_ack_ptr
- av
->dccpav_buf_head
;
368 av
->dccpav_vec_len
= DCCP_MAX_ACKVEC_LEN
- 1
369 - av
->dccpav_buf_head
370 + avr
->dccpavr_ack_ptr
;
373 list_for_each_entry_safe_from(avr
, next
, &av
->dccpav_records
,
375 list_del_init(&avr
->dccpavr_node
);
376 dccp_ackvec_record_delete(avr
);
380 void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec
*av
, struct sock
*sk
,
383 struct dccp_ackvec_record
*avr
;
386 * If we traverse backwards, it should be faster when we have large
387 * windows. We will be receiving ACKs for stuff we sent a while back
390 list_for_each_entry_reverse(avr
, &av
->dccpav_records
, dccpavr_node
) {
391 if (ackno
== avr
->dccpavr_ack_seqno
) {
392 dccp_pr_debug("%s ACK packet 0, len=%d, ack_seqno=%llu, "
393 "ack_ackno=%llu, ACKED!\n",
395 (unsigned long long)avr
->dccpavr_ack_seqno
,
396 (unsigned long long)avr
->dccpavr_ack_ackno
);
397 dccp_ackvec_throw_record(av
, avr
);
399 } else if (avr
->dccpavr_ack_seqno
> ackno
)
400 break; /* old news */
404 static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec
*av
,
405 struct sock
*sk
, u64
*ackno
,
406 const unsigned char len
,
407 const unsigned char *vector
)
410 struct dccp_ackvec_record
*avr
;
412 /* Check if we actually sent an ACK vector */
413 if (list_empty(&av
->dccpav_records
))
419 * I think it might be more efficient to work backwards. See comment on
422 avr
= list_entry(av
->dccpav_records
.next
, struct dccp_ackvec_record
,
425 const u8 rl
= *vector
& DCCP_ACKVEC_LEN_MASK
;
428 dccp_set_seqno(&ackno_end_rl
, *ackno
- rl
);
431 * If our AVR sequence number is greater than the ack, go
432 * forward in the AVR list until it is not so.
434 list_for_each_entry_from(avr
, &av
->dccpav_records
,
436 if (!after48(avr
->dccpavr_ack_seqno
, *ackno
))
439 /* End of the dccpav_records list, not found, exit */
442 if (between48(avr
->dccpavr_ack_seqno
, ackno_end_rl
, *ackno
)) {
443 const u8 state
= *vector
& DCCP_ACKVEC_STATE_MASK
;
444 if (state
!= DCCP_ACKVEC_STATE_NOT_RECEIVED
) {
445 dccp_pr_debug("%s ACK vector 0, len=%d, "
446 "ack_seqno=%llu, ack_ackno=%llu, "
450 avr
->dccpavr_ack_seqno
,
452 avr
->dccpavr_ack_ackno
);
453 dccp_ackvec_throw_record(av
, avr
);
457 * If it wasn't received, continue scanning... we might
462 dccp_set_seqno(ackno
, ackno_end_rl
- 1);
467 int dccp_ackvec_parse(struct sock
*sk
, const struct sk_buff
*skb
,
468 u64
*ackno
, const u8 opt
, const u8
*value
, const u8 len
)
470 if (len
> DCCP_MAX_ACKVEC_OPT_LEN
)
473 /* dccp_ackvector_print(DCCP_SKB_CB(skb)->dccpd_ack_seq, value, len); */
474 dccp_ackvec_check_rcv_ackvector(dccp_sk(sk
)->dccps_hc_rx_ackvec
, sk
,
479 int __init
dccp_ackvec_init(void)
481 dccp_ackvec_slab
= kmem_cache_create("dccp_ackvec",
482 sizeof(struct dccp_ackvec
), 0,
483 SLAB_HWCACHE_ALIGN
, NULL
);
484 if (dccp_ackvec_slab
== NULL
)
487 dccp_ackvec_record_slab
=
488 kmem_cache_create("dccp_ackvec_record",
489 sizeof(struct dccp_ackvec_record
),
490 0, SLAB_HWCACHE_ALIGN
, NULL
);
491 if (dccp_ackvec_record_slab
== NULL
)
492 goto out_destroy_slab
;
497 kmem_cache_destroy(dccp_ackvec_slab
);
498 dccp_ackvec_slab
= NULL
;
500 DCCP_CRIT("Unable to create Ack Vector slab cache");
504 void dccp_ackvec_exit(void)
506 if (dccp_ackvec_slab
!= NULL
) {
507 kmem_cache_destroy(dccp_ackvec_slab
);
508 dccp_ackvec_slab
= NULL
;
510 if (dccp_ackvec_record_slab
!= NULL
) {
511 kmem_cache_destroy(dccp_ackvec_record_slab
);
512 dccp_ackvec_record_slab
= NULL
;