Commit | Line | Data |
---|---|---|
ae31c339 ACM |
1 | /* |
2 | * net/dccp/ackvec.c | |
3 | * | |
f17a37c9 GR |
4 | * An implementation of Ack Vectors for the DCCP protocol |
5 | * Copyright (c) 2007 University of Aberdeen, Scotland, UK | |
ae31c339 ACM |
6 | * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@ghostprotocols.net> |
7 | * | |
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; | |
11 | */ | |
12 | ||
13 | #include "ackvec.h" | |
14 | #include "dccp.h" | |
15 | ||
9b07ef5d ACM |
16 | #include <linux/init.h> |
17 | #include <linux/errno.h> | |
18 | #include <linux/kernel.h> | |
ae31c339 | 19 | #include <linux/skbuff.h> |
9b07ef5d | 20 | #include <linux/slab.h> |
ae31c339 ACM |
21 | |
22 | #include <net/sock.h> | |
23 | ||
e18b890b CL |
24 | static struct kmem_cache *dccp_ackvec_slab; |
25 | static struct kmem_cache *dccp_ackvec_record_slab; | |
02bcf28c | 26 | |
f17a37c9 | 27 | struct dccp_ackvec *dccp_ackvec_alloc(const gfp_t priority) |
02bcf28c | 28 | { |
f17a37c9 GR |
29 | struct dccp_ackvec *av = kmem_cache_zalloc(dccp_ackvec_slab, priority); |
30 | ||
31 | if (av != NULL) { | |
32 | av->av_buf_head = DCCPAV_MAX_ACKVEC_LEN - 1; | |
33 | INIT_LIST_HEAD(&av->av_records); | |
34 | } | |
35 | return av; | |
36 | } | |
02bcf28c | 37 | |
f17a37c9 GR |
38 | static void dccp_ackvec_purge_records(struct dccp_ackvec *av) |
39 | { | |
40 | struct dccp_ackvec_record *cur, *next; | |
02bcf28c | 41 | |
f17a37c9 GR |
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); | |
02bcf28c AB |
45 | } |
46 | ||
f17a37c9 | 47 | void dccp_ackvec_free(struct dccp_ackvec *av) |
02bcf28c | 48 | { |
f17a37c9 GR |
49 | if (likely(av != NULL)) { |
50 | dccp_ackvec_purge_records(av); | |
51 | kmem_cache_free(dccp_ackvec_slab, av); | |
52 | } | |
02bcf28c AB |
53 | } |
54 | ||
55 | static void dccp_ackvec_insert_avr(struct dccp_ackvec *av, | |
56 | struct dccp_ackvec_record *avr) | |
57 | { | |
58 | /* | |
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. | |
61 | * -sorbo. | |
62 | */ | |
a47c5104 | 63 | if (!list_empty(&av->av_records)) { |
02bcf28c | 64 | const struct dccp_ackvec_record *head = |
a47c5104 | 65 | list_entry(av->av_records.next, |
02bcf28c | 66 | struct dccp_ackvec_record, |
a47c5104 GR |
67 | avr_node); |
68 | BUG_ON(before48(avr->avr_ack_seqno, head->avr_ack_seqno)); | |
02bcf28c AB |
69 | } |
70 | ||
a47c5104 | 71 | list_add(&avr->avr_node, &av->av_records); |
02bcf28c | 72 | } |
9b07ef5d | 73 | |
ae31c339 ACM |
74 | int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb) |
75 | { | |
76 | struct dccp_sock *dp = dccp_sk(sk); | |
77 | struct dccp_ackvec *av = dp->dccps_hc_rx_ackvec; | |
522f1d09 | 78 | /* Figure out how many options do we need to represent the ackvec */ |
b20a9c24 | 79 | const u8 nr_opts = DIV_ROUND_UP(av->av_vec_len, DCCP_SINGLE_OPT_MAXLEN); |
f17a37c9 GR |
80 | u16 len = av->av_vec_len + 2 * nr_opts; |
81 | u8 i, nonce = 0; | |
522f1d09 AB |
82 | const unsigned char *tail, *from; |
83 | unsigned char *to; | |
02bcf28c AB |
84 | struct dccp_ackvec_record *avr; |
85 | ||
86 | if (DCCP_SKB_CB(skb)->dccpd_opt_len + len > DCCP_MAX_OPT_LEN) | |
87 | return -1; | |
88 | ||
f17a37c9 | 89 | avr = kmem_cache_alloc(dccp_ackvec_record_slab, GFP_ATOMIC); |
2d0817d1 ACM |
90 | if (avr == NULL) |
91 | return -1; | |
ae31c339 | 92 | |
ae31c339 ACM |
93 | DCCP_SKB_CB(skb)->dccpd_opt_len += len; |
94 | ||
522f1d09 | 95 | to = skb_push(skb, len); |
a47c5104 GR |
96 | len = av->av_vec_len; |
97 | from = av->av_buf + av->av_buf_head; | |
f17a37c9 | 98 | tail = av->av_buf + DCCPAV_MAX_ACKVEC_LEN; |
522f1d09 AB |
99 | |
100 | for (i = 0; i < nr_opts; ++i) { | |
101 | int copylen = len; | |
102 | ||
b20a9c24 GR |
103 | if (len > DCCP_SINGLE_OPT_MAXLEN) |
104 | copylen = DCCP_SINGLE_OPT_MAXLEN; | |
522f1d09 | 105 | |
f17a37c9 GR |
106 | /* |
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. | |
109 | */ | |
110 | nonce ^= av->av_buf_nonce[i]; | |
111 | ||
112 | *to++ = DCCPO_ACK_VECTOR_0 + av->av_buf_nonce[i]; | |
522f1d09 AB |
113 | *to++ = copylen + 2; |
114 | ||
115 | /* Check if buf_head wraps */ | |
116 | if (from + copylen > tail) { | |
117 | const u16 tailsize = tail - from; | |
ae31c339 | 118 | |
522f1d09 AB |
119 | memcpy(to, from, tailsize); |
120 | to += tailsize; | |
121 | len -= tailsize; | |
122 | copylen -= tailsize; | |
a47c5104 | 123 | from = av->av_buf; |
522f1d09 | 124 | } |
ae31c339 | 125 | |
522f1d09 AB |
126 | memcpy(to, from, copylen); |
127 | from += copylen; | |
128 | to += copylen; | |
129 | len -= copylen; | |
ae31c339 ACM |
130 | } |
131 | ||
ae31c339 | 132 | /* |
f17a37c9 | 133 | * Each sent Ack Vector is recorded in the list, as per A.2 of RFC 4340. |
ae31c339 | 134 | */ |
f17a37c9 GR |
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); | |
02bcf28c AB |
140 | |
141 | dccp_ackvec_insert_avr(av, avr); | |
ae31c339 | 142 | |
09dbc389 | 143 | dccp_pr_debug("%s ACK Vector 0, len=%d, ack_seqno=%llu, " |
ae31c339 | 144 | "ack_ackno=%llu\n", |
f17a37c9 | 145 | dccp_role(sk), avr->avr_ack_runlen, |
a47c5104 GR |
146 | (unsigned long long)avr->avr_ack_seqno, |
147 | (unsigned long long)avr->avr_ack_ackno); | |
02bcf28c | 148 | return 0; |
ae31c339 ACM |
149 | } |
150 | ||
ae31c339 ACM |
151 | /* |
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. | |
155 | */ | |
156 | static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec *av, | |
157 | const unsigned int packets, | |
e4dfd449 | 158 | const unsigned char state) |
ae31c339 | 159 | { |
8e64159d | 160 | long gap; |
a8fc3d8d | 161 | long new_head; |
ae31c339 | 162 | |
f17a37c9 | 163 | if (av->av_vec_len + packets > DCCPAV_MAX_ACKVEC_LEN) |
ae31c339 ACM |
164 | return -ENOBUFS; |
165 | ||
166 | gap = packets - 1; | |
a47c5104 | 167 | new_head = av->av_buf_head - packets; |
ae31c339 ACM |
168 | |
169 | if (new_head < 0) { | |
170 | if (gap > 0) { | |
f17a37c9 | 171 | memset(av->av_buf, DCCPAV_NOT_RECEIVED, |
ae31c339 ACM |
172 | gap + new_head + 1); |
173 | gap = -new_head; | |
174 | } | |
f17a37c9 | 175 | new_head += DCCPAV_MAX_ACKVEC_LEN; |
8109b02b | 176 | } |
ae31c339 | 177 | |
a47c5104 | 178 | av->av_buf_head = new_head; |
ae31c339 ACM |
179 | |
180 | if (gap > 0) | |
a47c5104 | 181 | memset(av->av_buf + av->av_buf_head + 1, |
f17a37c9 | 182 | DCCPAV_NOT_RECEIVED, gap); |
ae31c339 | 183 | |
a47c5104 GR |
184 | av->av_buf[av->av_buf_head] = state; |
185 | av->av_vec_len += packets; | |
ae31c339 ACM |
186 | return 0; |
187 | } | |
188 | ||
189 | /* | |
0e64e94e | 190 | * Implements the RFC 4340, Appendix A |
ae31c339 ACM |
191 | */ |
192 | int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk, | |
193 | const u64 ackno, const u8 state) | |
194 | { | |
f17a37c9 GR |
195 | u8 *cur_head = av->av_buf + av->av_buf_head, |
196 | *buf_end = av->av_buf + DCCPAV_MAX_ACKVEC_LEN; | |
ae31c339 ACM |
197 | /* |
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 | |
a47c5104 | 200 | * vectors, when we will free up space in av_buf. |
ae31c339 ACM |
201 | * |
202 | * We may well decide to do buffer compression, etc, but for now lets | |
203 | * just drop. | |
204 | * | |
0e64e94e | 205 | * From Appendix A.1.1 (`New Packets'): |
ae31c339 ACM |
206 | * |
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 | |
216 | * shrinks again. | |
217 | */ | |
218 | ||
219 | /* See if this is the first ackno being inserted */ | |
a47c5104 | 220 | if (av->av_vec_len == 0) { |
f17a37c9 | 221 | *cur_head = state; |
a47c5104 GR |
222 | av->av_vec_len = 1; |
223 | } else if (after48(ackno, av->av_buf_ackno)) { | |
224 | const u64 delta = dccp_delta_seqno(av->av_buf_ackno, ackno); | |
ae31c339 ACM |
225 | |
226 | /* | |
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. | |
229 | */ | |
f17a37c9 GR |
230 | if (delta == 1 && dccp_ackvec_state(cur_head) == state && |
231 | dccp_ackvec_runlen(cur_head) < DCCPAV_MAX_RUNLEN) | |
232 | *cur_head += 1; | |
ae31c339 ACM |
233 | else if (dccp_ackvec_set_buf_head_state(av, delta, state)) |
234 | return -ENOBUFS; | |
235 | } else { | |
236 | /* | |
237 | * A.1.2. Old Packets | |
238 | * | |
0e64e94e GR |
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 | |
ae31c339 ACM |
242 | * could reduce the complexity of this scan.) |
243 | */ | |
a47c5104 | 244 | u64 delta = dccp_delta_seqno(ackno, av->av_buf_ackno); |
ae31c339 ACM |
245 | |
246 | while (1) { | |
f17a37c9 | 247 | const u8 len = dccp_ackvec_runlen(cur_head); |
ae31c339 | 248 | /* |
a47c5104 | 249 | * valid packets not yet in av_buf have a reserved |
ae31c339 ACM |
250 | * entry, with a len equal to 0. |
251 | */ | |
f17a37c9 | 252 | if (*cur_head == DCCPAV_NOT_RECEIVED && delta == 0) { |
ae31c339 ACM |
253 | dccp_pr_debug("Found %llu reserved seat!\n", |
254 | (unsigned long long)ackno); | |
f17a37c9 | 255 | *cur_head = state; |
ae31c339 ACM |
256 | goto out; |
257 | } | |
258 | /* len == 0 means one packet */ | |
259 | if (delta < len + 1) | |
260 | goto out_duplicate; | |
261 | ||
262 | delta -= len + 1; | |
f17a37c9 GR |
263 | if (++cur_head == buf_end) |
264 | cur_head = av->av_buf; | |
ae31c339 ACM |
265 | } |
266 | } | |
267 | ||
a47c5104 | 268 | av->av_buf_ackno = ackno; |
ae31c339 | 269 | out: |
ae31c339 ACM |
270 | return 0; |
271 | ||
272 | out_duplicate: | |
273 | /* Duplicate packet */ | |
274 | dccp_pr_debug("Received a dup or already considered lost " | |
275 | "packet: %llu\n", (unsigned long long)ackno); | |
276 | return -EILSEQ; | |
277 | } | |
278 | ||
02bcf28c AB |
279 | static void dccp_ackvec_throw_record(struct dccp_ackvec *av, |
280 | struct dccp_ackvec_record *avr) | |
ae31c339 | 281 | { |
02bcf28c AB |
282 | struct dccp_ackvec_record *next; |
283 | ||
23d06e3b | 284 | /* sort out vector length */ |
a47c5104 GR |
285 | if (av->av_buf_head <= avr->avr_ack_ptr) |
286 | av->av_vec_len = avr->avr_ack_ptr - av->av_buf_head; | |
23d06e3b | 287 | else |
f17a37c9 | 288 | av->av_vec_len = DCCPAV_MAX_ACKVEC_LEN - 1 - |
a47c5104 | 289 | av->av_buf_head + avr->avr_ack_ptr; |
02bcf28c AB |
290 | |
291 | /* free records */ | |
a47c5104 | 292 | list_for_each_entry_safe_from(avr, next, &av->av_records, avr_node) { |
f17a37c9 GR |
293 | list_del(&avr->avr_node); |
294 | kmem_cache_free(dccp_ackvec_record_slab, avr); | |
02bcf28c | 295 | } |
ae31c339 ACM |
296 | } |
297 | ||
298 | void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec *av, struct sock *sk, | |
299 | const u64 ackno) | |
300 | { | |
02bcf28c | 301 | struct dccp_ackvec_record *avr; |
ae31c339 | 302 | |
02bcf28c AB |
303 | /* |
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 | |
306 | * -sorbo. | |
307 | */ | |
a47c5104 GR |
308 | list_for_each_entry_reverse(avr, &av->av_records, avr_node) { |
309 | if (ackno == avr->avr_ack_seqno) { | |
09dbc389 | 310 | dccp_pr_debug("%s ACK packet 0, len=%d, ack_seqno=%llu, " |
02bcf28c | 311 | "ack_ackno=%llu, ACKED!\n", |
f17a37c9 | 312 | dccp_role(sk), avr->avr_ack_runlen, |
a47c5104 GR |
313 | (unsigned long long)avr->avr_ack_seqno, |
314 | (unsigned long long)avr->avr_ack_ackno); | |
02bcf28c AB |
315 | dccp_ackvec_throw_record(av, avr); |
316 | break; | |
a47c5104 | 317 | } else if (avr->avr_ack_seqno > ackno) |
d23ca15a | 318 | break; /* old news */ |
ae31c339 ACM |
319 | } |
320 | } | |
321 | ||
322 | static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec *av, | |
bdf13d20 | 323 | struct sock *sk, u64 *ackno, |
ae31c339 ACM |
324 | const unsigned char len, |
325 | const unsigned char *vector) | |
326 | { | |
327 | unsigned char i; | |
02bcf28c | 328 | struct dccp_ackvec_record *avr; |
ae31c339 ACM |
329 | |
330 | /* Check if we actually sent an ACK vector */ | |
a47c5104 | 331 | if (list_empty(&av->av_records)) |
ae31c339 | 332 | return; |
ae31c339 ACM |
333 | |
334 | i = len; | |
02bcf28c AB |
335 | /* |
336 | * XXX | |
337 | * I think it might be more efficient to work backwards. See comment on | |
338 | * rcv_ackno. -sorbo. | |
339 | */ | |
a47c5104 | 340 | avr = list_entry(av->av_records.next, struct dccp_ackvec_record, avr_node); |
ae31c339 | 341 | while (i--) { |
f17a37c9 | 342 | const u8 rl = dccp_ackvec_runlen(vector); |
ae31c339 ACM |
343 | u64 ackno_end_rl; |
344 | ||
bdf13d20 | 345 | dccp_set_seqno(&ackno_end_rl, *ackno - rl); |
ae31c339 ACM |
346 | |
347 | /* | |
02bcf28c AB |
348 | * If our AVR sequence number is greater than the ack, go |
349 | * forward in the AVR list until it is not so. | |
ae31c339 | 350 | */ |
a47c5104 GR |
351 | list_for_each_entry_from(avr, &av->av_records, avr_node) { |
352 | if (!after48(avr->avr_ack_seqno, *ackno)) | |
02bcf28c AB |
353 | goto found; |
354 | } | |
a47c5104 | 355 | /* End of the av_records list, not found, exit */ |
02bcf28c AB |
356 | break; |
357 | found: | |
a47c5104 | 358 | if (between48(avr->avr_ack_seqno, ackno_end_rl, *ackno)) { |
f17a37c9 | 359 | if (dccp_ackvec_state(vector) != DCCPAV_NOT_RECEIVED) { |
09dbc389 | 360 | dccp_pr_debug("%s ACK vector 0, len=%d, " |
ae31c339 ACM |
361 | "ack_seqno=%llu, ack_ackno=%llu, " |
362 | "ACKED!\n", | |
09dbc389 | 363 | dccp_role(sk), len, |
ae31c339 | 364 | (unsigned long long) |
a47c5104 | 365 | avr->avr_ack_seqno, |
ae31c339 | 366 | (unsigned long long) |
a47c5104 | 367 | avr->avr_ack_ackno); |
02bcf28c | 368 | dccp_ackvec_throw_record(av, avr); |
afec35e3 | 369 | break; |
ae31c339 ACM |
370 | } |
371 | /* | |
02bcf28c AB |
372 | * If it wasn't received, continue scanning... we might |
373 | * find another one. | |
ae31c339 | 374 | */ |
ae31c339 | 375 | } |
ae31c339 | 376 | |
bdf13d20 | 377 | dccp_set_seqno(ackno, ackno_end_rl - 1); |
ae31c339 ACM |
378 | ++vector; |
379 | } | |
380 | } | |
381 | ||
382 | int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb, | |
bdf13d20 | 383 | u64 *ackno, const u8 opt, const u8 *value, const u8 len) |
ae31c339 | 384 | { |
b20a9c24 | 385 | if (len > DCCP_SINGLE_OPT_MAXLEN) |
ae31c339 ACM |
386 | return -1; |
387 | ||
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, | |
bdf13d20 | 390 | ackno, len, value); |
ae31c339 ACM |
391 | return 0; |
392 | } | |
9b07ef5d | 393 | |
9b07ef5d ACM |
394 | int __init dccp_ackvec_init(void) |
395 | { | |
396 | dccp_ackvec_slab = kmem_cache_create("dccp_ackvec", | |
397 | sizeof(struct dccp_ackvec), 0, | |
20c2df83 | 398 | SLAB_HWCACHE_ALIGN, NULL); |
02bcf28c AB |
399 | if (dccp_ackvec_slab == NULL) |
400 | goto out_err; | |
401 | ||
f17a37c9 GR |
402 | dccp_ackvec_record_slab = kmem_cache_create("dccp_ackvec_record", |
403 | sizeof(struct dccp_ackvec_record), | |
404 | 0, SLAB_HWCACHE_ALIGN, NULL); | |
02bcf28c AB |
405 | if (dccp_ackvec_record_slab == NULL) |
406 | goto out_destroy_slab; | |
9b07ef5d ACM |
407 | |
408 | return 0; | |
02bcf28c AB |
409 | |
410 | out_destroy_slab: | |
411 | kmem_cache_destroy(dccp_ackvec_slab); | |
412 | dccp_ackvec_slab = NULL; | |
413 | out_err: | |
59348b19 | 414 | DCCP_CRIT("Unable to create Ack Vector slab cache"); |
02bcf28c | 415 | return -ENOBUFS; |
9b07ef5d ACM |
416 | } |
417 | ||
418 | void dccp_ackvec_exit(void) | |
419 | { | |
420 | if (dccp_ackvec_slab != NULL) { | |
421 | kmem_cache_destroy(dccp_ackvec_slab); | |
422 | dccp_ackvec_slab = NULL; | |
423 | } | |
02bcf28c AB |
424 | if (dccp_ackvec_record_slab != NULL) { |
425 | kmem_cache_destroy(dccp_ackvec_record_slab); | |
426 | dccp_ackvec_record_slab = NULL; | |
427 | } | |
9b07ef5d | 428 | } |