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 kmem_cache_t
*dccp_ackvec_slab
;
25 static kmem_cache_t
*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 int len
= av
->dccpav_vec_len
+ 2;
74 unsigned char *to
, *from
;
75 struct dccp_ackvec_record
*avr
;
77 if (DCCP_SKB_CB(skb
)->dccpd_opt_len
+ len
> DCCP_MAX_OPT_LEN
)
80 dccp_timestamp(sk
, &now
);
81 elapsed_time
= timeval_delta(&now
, &av
->dccpav_time
) / 10;
83 if (elapsed_time
!= 0 &&
84 dccp_insert_option_elapsed_time(sk
, skb
, elapsed_time
))
87 avr
= dccp_ackvec_record_new();
91 DCCP_SKB_CB(skb
)->dccpd_opt_len
+= len
;
93 to
= skb_push(skb
, len
);
94 *to
++ = DCCPO_ACK_VECTOR_0
;
97 len
= av
->dccpav_vec_len
;
98 from
= av
->dccpav_buf
+ av
->dccpav_buf_head
;
100 /* Check if buf_head wraps */
101 if ((int)av
->dccpav_buf_head
+ len
> DCCP_MAX_ACKVEC_LEN
) {
102 const u32 tailsize
= DCCP_MAX_ACKVEC_LEN
- av
->dccpav_buf_head
;
104 memcpy(to
, from
, tailsize
);
107 from
= av
->dccpav_buf
;
110 memcpy(to
, from
, len
);
112 * From RFC 4340, A.2:
114 * For each acknowledgement it sends, the HC-Receiver will add an
115 * acknowledgement record. ack_seqno will equal the HC-Receiver
116 * sequence number it used for the ack packet; ack_ptr will equal
117 * buf_head; ack_ackno will equal buf_ackno; and ack_nonce will
120 avr
->dccpavr_ack_seqno
= DCCP_SKB_CB(skb
)->dccpd_seq
;
121 avr
->dccpavr_ack_ptr
= av
->dccpav_buf_head
;
122 avr
->dccpavr_ack_ackno
= av
->dccpav_buf_ackno
;
123 avr
->dccpavr_ack_nonce
= av
->dccpav_buf_nonce
;
124 avr
->dccpavr_sent_len
= av
->dccpav_vec_len
;
126 dccp_ackvec_insert_avr(av
, avr
);
128 dccp_pr_debug("%s ACK Vector 0, len=%d, ack_seqno=%llu, "
130 dccp_role(sk
), avr
->dccpavr_sent_len
,
131 (unsigned long long)avr
->dccpavr_ack_seqno
,
132 (unsigned long long)avr
->dccpavr_ack_ackno
);
136 struct dccp_ackvec
*dccp_ackvec_alloc(const gfp_t priority
)
138 struct dccp_ackvec
*av
= kmem_cache_alloc(dccp_ackvec_slab
, priority
);
141 av
->dccpav_buf_head
= DCCP_MAX_ACKVEC_LEN
- 1;
142 av
->dccpav_buf_ackno
= DCCP_MAX_SEQNO
+ 1;
143 av
->dccpav_buf_nonce
= av
->dccpav_buf_nonce
= 0;
144 av
->dccpav_ack_ptr
= 0;
145 av
->dccpav_time
.tv_sec
= 0;
146 av
->dccpav_time
.tv_usec
= 0;
147 av
->dccpav_vec_len
= 0;
148 INIT_LIST_HEAD(&av
->dccpav_records
);
154 void dccp_ackvec_free(struct dccp_ackvec
*av
)
156 if (unlikely(av
== NULL
))
159 if (!list_empty(&av
->dccpav_records
)) {
160 struct dccp_ackvec_record
*avr
, *next
;
162 list_for_each_entry_safe(avr
, next
, &av
->dccpav_records
,
164 list_del_init(&avr
->dccpavr_node
);
165 dccp_ackvec_record_delete(avr
);
169 kmem_cache_free(dccp_ackvec_slab
, av
);
172 static inline u8
dccp_ackvec_state(const struct dccp_ackvec
*av
,
175 return av
->dccpav_buf
[index
] & DCCP_ACKVEC_STATE_MASK
;
178 static inline u8
dccp_ackvec_len(const struct dccp_ackvec
*av
,
181 return av
->dccpav_buf
[index
] & DCCP_ACKVEC_LEN_MASK
;
185 * If several packets are missing, the HC-Receiver may prefer to enter multiple
186 * bytes with run length 0, rather than a single byte with a larger run length;
187 * this simplifies table updates if one of the missing packets arrives.
189 static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec
*av
,
190 const unsigned int packets
,
191 const unsigned char state
)
196 if (av
->dccpav_vec_len
+ packets
> DCCP_MAX_ACKVEC_LEN
)
200 new_head
= av
->dccpav_buf_head
- packets
;
204 memset(av
->dccpav_buf
, DCCP_ACKVEC_STATE_NOT_RECEIVED
,
208 new_head
+= DCCP_MAX_ACKVEC_LEN
;
211 av
->dccpav_buf_head
= new_head
;
214 memset(av
->dccpav_buf
+ av
->dccpav_buf_head
+ 1,
215 DCCP_ACKVEC_STATE_NOT_RECEIVED
, gap
);
217 av
->dccpav_buf
[av
->dccpav_buf_head
] = state
;
218 av
->dccpav_vec_len
+= packets
;
223 * Implements the RFC 4340, Appendix A
225 int dccp_ackvec_add(struct dccp_ackvec
*av
, const struct sock
*sk
,
226 const u64 ackno
, const u8 state
)
229 * Check at the right places if the buffer is full, if it is, tell the
230 * caller to start dropping packets till the HC-Sender acks our ACK
231 * vectors, when we will free up space in dccpav_buf.
233 * We may well decide to do buffer compression, etc, but for now lets
236 * From Appendix A.1.1 (`New Packets'):
238 * Of course, the circular buffer may overflow, either when the
239 * HC-Sender is sending data at a very high rate, when the
240 * HC-Receiver's acknowledgements are not reaching the HC-Sender,
241 * or when the HC-Sender is forgetting to acknowledge those acks
242 * (so the HC-Receiver is unable to clean up old state). In this
243 * case, the HC-Receiver should either compress the buffer (by
244 * increasing run lengths when possible), transfer its state to
245 * a larger buffer, or, as a last resort, drop all received
246 * packets, without processing them whatsoever, until its buffer
250 /* See if this is the first ackno being inserted */
251 if (av
->dccpav_vec_len
== 0) {
252 av
->dccpav_buf
[av
->dccpav_buf_head
] = state
;
253 av
->dccpav_vec_len
= 1;
254 } else if (after48(ackno
, av
->dccpav_buf_ackno
)) {
255 const u64 delta
= dccp_delta_seqno(av
->dccpav_buf_ackno
,
259 * Look if the state of this packet is the same as the
260 * previous ackno and if so if we can bump the head len.
263 dccp_ackvec_state(av
, av
->dccpav_buf_head
) == state
&&
264 (dccp_ackvec_len(av
, av
->dccpav_buf_head
) <
265 DCCP_ACKVEC_LEN_MASK
))
266 av
->dccpav_buf
[av
->dccpav_buf_head
]++;
267 else if (dccp_ackvec_set_buf_head_state(av
, delta
, state
))
273 * When a packet with Sequence Number S <= buf_ackno
274 * arrives, the HC-Receiver will scan the table for
275 * the byte corresponding to S. (Indexing structures
276 * could reduce the complexity of this scan.)
278 u64 delta
= dccp_delta_seqno(ackno
, av
->dccpav_buf_ackno
);
279 u8 index
= av
->dccpav_buf_head
;
282 const u8 len
= dccp_ackvec_len(av
, index
);
283 const u8 state
= dccp_ackvec_state(av
, index
);
285 * valid packets not yet in dccpav_buf have a reserved
286 * entry, with a len equal to 0.
288 if (state
== DCCP_ACKVEC_STATE_NOT_RECEIVED
&&
289 len
== 0 && delta
== 0) { /* Found our
291 dccp_pr_debug("Found %llu reserved seat!\n",
292 (unsigned long long)ackno
);
293 av
->dccpav_buf
[index
] = state
;
296 /* len == 0 means one packet */
301 if (++index
== DCCP_MAX_ACKVEC_LEN
)
306 av
->dccpav_buf_ackno
= ackno
;
307 dccp_timestamp(sk
, &av
->dccpav_time
);
312 /* Duplicate packet */
313 dccp_pr_debug("Received a dup or already considered lost "
314 "packet: %llu\n", (unsigned long long)ackno
);
318 #ifdef CONFIG_IP_DCCP_DEBUG
319 void dccp_ackvector_print(const u64 ackno
, const unsigned char *vector
, int len
)
321 dccp_pr_debug_cat("ACK vector len=%d, ackno=%llu |", len
,
322 (unsigned long long)ackno
);
325 const u8 state
= (*vector
& DCCP_ACKVEC_STATE_MASK
) >> 6;
326 const u8 rl
= *vector
& DCCP_ACKVEC_LEN_MASK
;
328 dccp_pr_debug_cat("%d,%d|", state
, rl
);
332 dccp_pr_debug_cat("\n");
335 void dccp_ackvec_print(const struct dccp_ackvec
*av
)
337 dccp_ackvector_print(av
->dccpav_buf_ackno
,
338 av
->dccpav_buf
+ av
->dccpav_buf_head
,
343 static void dccp_ackvec_throw_record(struct dccp_ackvec
*av
,
344 struct dccp_ackvec_record
*avr
)
346 struct dccp_ackvec_record
*next
;
348 /* sort out vector length */
349 if (av
->dccpav_buf_head
<= avr
->dccpavr_ack_ptr
)
350 av
->dccpav_vec_len
= avr
->dccpavr_ack_ptr
- av
->dccpav_buf_head
;
352 av
->dccpav_vec_len
= DCCP_MAX_ACKVEC_LEN
- 1
353 - av
->dccpav_buf_head
354 + avr
->dccpavr_ack_ptr
;
357 list_for_each_entry_safe_from(avr
, next
, &av
->dccpav_records
,
359 list_del_init(&avr
->dccpavr_node
);
360 dccp_ackvec_record_delete(avr
);
364 void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec
*av
, struct sock
*sk
,
367 struct dccp_ackvec_record
*avr
;
370 * If we traverse backwards, it should be faster when we have large
371 * windows. We will be receiving ACKs for stuff we sent a while back
374 list_for_each_entry_reverse(avr
, &av
->dccpav_records
, dccpavr_node
) {
375 if (ackno
== avr
->dccpavr_ack_seqno
) {
376 dccp_pr_debug("%s ACK packet 0, len=%d, ack_seqno=%llu, "
377 "ack_ackno=%llu, ACKED!\n",
379 (unsigned long long)avr
->dccpavr_ack_seqno
,
380 (unsigned long long)avr
->dccpavr_ack_ackno
);
381 dccp_ackvec_throw_record(av
, avr
);
383 } else if (avr
->dccpavr_ack_seqno
> ackno
)
384 break; /* old news */
388 static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec
*av
,
389 struct sock
*sk
, u64 ackno
,
390 const unsigned char len
,
391 const unsigned char *vector
)
394 struct dccp_ackvec_record
*avr
;
396 /* Check if we actually sent an ACK vector */
397 if (list_empty(&av
->dccpav_records
))
403 * I think it might be more efficient to work backwards. See comment on
406 avr
= list_entry(av
->dccpav_records
.next
, struct dccp_ackvec_record
,
409 const u8 rl
= *vector
& DCCP_ACKVEC_LEN_MASK
;
412 dccp_set_seqno(&ackno_end_rl
, ackno
- rl
);
415 * If our AVR sequence number is greater than the ack, go
416 * forward in the AVR list until it is not so.
418 list_for_each_entry_from(avr
, &av
->dccpav_records
,
420 if (!after48(avr
->dccpavr_ack_seqno
, ackno
))
423 /* End of the dccpav_records list, not found, exit */
426 if (between48(avr
->dccpavr_ack_seqno
, ackno_end_rl
, ackno
)) {
427 const u8 state
= *vector
& DCCP_ACKVEC_STATE_MASK
;
428 if (state
!= DCCP_ACKVEC_STATE_NOT_RECEIVED
) {
429 dccp_pr_debug("%s ACK vector 0, len=%d, "
430 "ack_seqno=%llu, ack_ackno=%llu, "
434 avr
->dccpavr_ack_seqno
,
436 avr
->dccpavr_ack_ackno
);
437 dccp_ackvec_throw_record(av
, avr
);
441 * If it wasn't received, continue scanning... we might
446 dccp_set_seqno(&ackno
, ackno_end_rl
- 1);
451 int dccp_ackvec_parse(struct sock
*sk
, const struct sk_buff
*skb
,
452 const u8 opt
, const u8
*value
, const u8 len
)
454 if (len
> DCCP_MAX_ACKVEC_LEN
)
457 /* dccp_ackvector_print(DCCP_SKB_CB(skb)->dccpd_ack_seq, value, len); */
458 dccp_ackvec_check_rcv_ackvector(dccp_sk(sk
)->dccps_hc_rx_ackvec
, sk
,
459 DCCP_SKB_CB(skb
)->dccpd_ack_seq
,
464 int __init
dccp_ackvec_init(void)
466 dccp_ackvec_slab
= kmem_cache_create("dccp_ackvec",
467 sizeof(struct dccp_ackvec
), 0,
468 SLAB_HWCACHE_ALIGN
, NULL
, NULL
);
469 if (dccp_ackvec_slab
== NULL
)
472 dccp_ackvec_record_slab
=
473 kmem_cache_create("dccp_ackvec_record",
474 sizeof(struct dccp_ackvec_record
),
475 0, SLAB_HWCACHE_ALIGN
, NULL
, NULL
);
476 if (dccp_ackvec_record_slab
== NULL
)
477 goto out_destroy_slab
;
482 kmem_cache_destroy(dccp_ackvec_slab
);
483 dccp_ackvec_slab
= NULL
;
485 DCCP_CRIT("Unable to create Ack Vector slab cache");
489 void dccp_ackvec_exit(void)
491 if (dccp_ackvec_slab
!= NULL
) {
492 kmem_cache_destroy(dccp_ackvec_slab
);
493 dccp_ackvec_slab
= NULL
;
495 if (dccp_ackvec_record_slab
!= NULL
) {
496 kmem_cache_destroy(dccp_ackvec_record_slab
);
497 dccp_ackvec_record_slab
= NULL
;