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 | ||
7d870936 GR |
55 | /** |
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 | |
60 | */ | |
61 | int dccp_ackvec_update_records(struct dccp_ackvec *av, u64 seqno, u8 nonce_sum) | |
ae31c339 | 62 | { |
02bcf28c AB |
63 | struct dccp_ackvec_record *avr; |
64 | ||
f17a37c9 | 65 | avr = kmem_cache_alloc(dccp_ackvec_record_slab, GFP_ATOMIC); |
2d0817d1 | 66 | if (avr == NULL) |
7d870936 | 67 | return -ENOBUFS; |
ae31c339 | 68 | |
7d870936 | 69 | avr->avr_ack_seqno = seqno; |
f17a37c9 GR |
70 | avr->avr_ack_ptr = av->av_buf_head; |
71 | avr->avr_ack_ackno = av->av_buf_ackno; | |
7d870936 | 72 | avr->avr_ack_nonce = nonce_sum; |
f17a37c9 | 73 | avr->avr_ack_runlen = dccp_ackvec_runlen(av->av_buf + av->av_buf_head); |
7d870936 GR |
74 | /* |
75 | * Since GSS is incremented for each packet, the list is automatically | |
76 | * arranged in descending order of @ack_seqno. | |
77 | */ | |
78 | list_add(&avr->avr_node, &av->av_records); | |
02bcf28c | 79 | |
7d870936 | 80 | dccp_pr_debug("Added Vector, ack_seqno=%llu, ack_ackno=%llu (rl=%u)\n", |
a47c5104 | 81 | (unsigned long long)avr->avr_ack_seqno, |
7d870936 GR |
82 | (unsigned long long)avr->avr_ack_ackno, |
83 | avr->avr_ack_runlen); | |
02bcf28c | 84 | return 0; |
ae31c339 ACM |
85 | } |
86 | ||
ae31c339 ACM |
87 | /* |
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. | |
91 | */ | |
92 | static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec *av, | |
93 | const unsigned int packets, | |
e4dfd449 | 94 | const unsigned char state) |
ae31c339 | 95 | { |
8e64159d | 96 | long gap; |
a8fc3d8d | 97 | long new_head; |
ae31c339 | 98 | |
f17a37c9 | 99 | if (av->av_vec_len + packets > DCCPAV_MAX_ACKVEC_LEN) |
ae31c339 ACM |
100 | return -ENOBUFS; |
101 | ||
102 | gap = packets - 1; | |
a47c5104 | 103 | new_head = av->av_buf_head - packets; |
ae31c339 ACM |
104 | |
105 | if (new_head < 0) { | |
106 | if (gap > 0) { | |
f17a37c9 | 107 | memset(av->av_buf, DCCPAV_NOT_RECEIVED, |
ae31c339 ACM |
108 | gap + new_head + 1); |
109 | gap = -new_head; | |
110 | } | |
f17a37c9 | 111 | new_head += DCCPAV_MAX_ACKVEC_LEN; |
8109b02b | 112 | } |
ae31c339 | 113 | |
a47c5104 | 114 | av->av_buf_head = new_head; |
ae31c339 ACM |
115 | |
116 | if (gap > 0) | |
a47c5104 | 117 | memset(av->av_buf + av->av_buf_head + 1, |
f17a37c9 | 118 | DCCPAV_NOT_RECEIVED, gap); |
ae31c339 | 119 | |
a47c5104 GR |
120 | av->av_buf[av->av_buf_head] = state; |
121 | av->av_vec_len += packets; | |
ae31c339 ACM |
122 | return 0; |
123 | } | |
124 | ||
125 | /* | |
0e64e94e | 126 | * Implements the RFC 4340, Appendix A |
ae31c339 ACM |
127 | */ |
128 | int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk, | |
129 | const u64 ackno, const u8 state) | |
130 | { | |
f17a37c9 GR |
131 | u8 *cur_head = av->av_buf + av->av_buf_head, |
132 | *buf_end = av->av_buf + DCCPAV_MAX_ACKVEC_LEN; | |
ae31c339 ACM |
133 | /* |
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 | |
a47c5104 | 136 | * vectors, when we will free up space in av_buf. |
ae31c339 ACM |
137 | * |
138 | * We may well decide to do buffer compression, etc, but for now lets | |
139 | * just drop. | |
140 | * | |
0e64e94e | 141 | * From Appendix A.1.1 (`New Packets'): |
ae31c339 ACM |
142 | * |
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 | |
152 | * shrinks again. | |
153 | */ | |
154 | ||
155 | /* See if this is the first ackno being inserted */ | |
a47c5104 | 156 | if (av->av_vec_len == 0) { |
f17a37c9 | 157 | *cur_head = state; |
a47c5104 GR |
158 | av->av_vec_len = 1; |
159 | } else if (after48(ackno, av->av_buf_ackno)) { | |
160 | const u64 delta = dccp_delta_seqno(av->av_buf_ackno, ackno); | |
ae31c339 ACM |
161 | |
162 | /* | |
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. | |
165 | */ | |
f17a37c9 GR |
166 | if (delta == 1 && dccp_ackvec_state(cur_head) == state && |
167 | dccp_ackvec_runlen(cur_head) < DCCPAV_MAX_RUNLEN) | |
168 | *cur_head += 1; | |
ae31c339 ACM |
169 | else if (dccp_ackvec_set_buf_head_state(av, delta, state)) |
170 | return -ENOBUFS; | |
171 | } else { | |
172 | /* | |
173 | * A.1.2. Old Packets | |
174 | * | |
0e64e94e GR |
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 | |
ae31c339 ACM |
178 | * could reduce the complexity of this scan.) |
179 | */ | |
a47c5104 | 180 | u64 delta = dccp_delta_seqno(ackno, av->av_buf_ackno); |
ae31c339 ACM |
181 | |
182 | while (1) { | |
f17a37c9 | 183 | const u8 len = dccp_ackvec_runlen(cur_head); |
ae31c339 | 184 | /* |
a47c5104 | 185 | * valid packets not yet in av_buf have a reserved |
ae31c339 ACM |
186 | * entry, with a len equal to 0. |
187 | */ | |
f17a37c9 | 188 | if (*cur_head == DCCPAV_NOT_RECEIVED && delta == 0) { |
ae31c339 ACM |
189 | dccp_pr_debug("Found %llu reserved seat!\n", |
190 | (unsigned long long)ackno); | |
f17a37c9 | 191 | *cur_head = state; |
ae31c339 ACM |
192 | goto out; |
193 | } | |
194 | /* len == 0 means one packet */ | |
195 | if (delta < len + 1) | |
196 | goto out_duplicate; | |
197 | ||
198 | delta -= len + 1; | |
f17a37c9 GR |
199 | if (++cur_head == buf_end) |
200 | cur_head = av->av_buf; | |
ae31c339 ACM |
201 | } |
202 | } | |
203 | ||
a47c5104 | 204 | av->av_buf_ackno = ackno; |
ae31c339 | 205 | out: |
ae31c339 ACM |
206 | return 0; |
207 | ||
208 | out_duplicate: | |
209 | /* Duplicate packet */ | |
210 | dccp_pr_debug("Received a dup or already considered lost " | |
211 | "packet: %llu\n", (unsigned long long)ackno); | |
212 | return -EILSEQ; | |
213 | } | |
214 | ||
02bcf28c AB |
215 | static void dccp_ackvec_throw_record(struct dccp_ackvec *av, |
216 | struct dccp_ackvec_record *avr) | |
ae31c339 | 217 | { |
02bcf28c AB |
218 | struct dccp_ackvec_record *next; |
219 | ||
23d06e3b | 220 | /* sort out vector length */ |
a47c5104 GR |
221 | if (av->av_buf_head <= avr->avr_ack_ptr) |
222 | av->av_vec_len = avr->avr_ack_ptr - av->av_buf_head; | |
23d06e3b | 223 | else |
f17a37c9 | 224 | av->av_vec_len = DCCPAV_MAX_ACKVEC_LEN - 1 - |
a47c5104 | 225 | av->av_buf_head + avr->avr_ack_ptr; |
02bcf28c AB |
226 | |
227 | /* free records */ | |
a47c5104 | 228 | list_for_each_entry_safe_from(avr, next, &av->av_records, avr_node) { |
f17a37c9 GR |
229 | list_del(&avr->avr_node); |
230 | kmem_cache_free(dccp_ackvec_record_slab, avr); | |
02bcf28c | 231 | } |
ae31c339 ACM |
232 | } |
233 | ||
234 | void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec *av, struct sock *sk, | |
235 | const u64 ackno) | |
236 | { | |
02bcf28c | 237 | struct dccp_ackvec_record *avr; |
ae31c339 | 238 | |
02bcf28c AB |
239 | /* |
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 | |
242 | * -sorbo. | |
243 | */ | |
a47c5104 GR |
244 | list_for_each_entry_reverse(avr, &av->av_records, avr_node) { |
245 | if (ackno == avr->avr_ack_seqno) { | |
09dbc389 | 246 | dccp_pr_debug("%s ACK packet 0, len=%d, ack_seqno=%llu, " |
02bcf28c | 247 | "ack_ackno=%llu, ACKED!\n", |
f17a37c9 | 248 | dccp_role(sk), avr->avr_ack_runlen, |
a47c5104 GR |
249 | (unsigned long long)avr->avr_ack_seqno, |
250 | (unsigned long long)avr->avr_ack_ackno); | |
02bcf28c AB |
251 | dccp_ackvec_throw_record(av, avr); |
252 | break; | |
a47c5104 | 253 | } else if (avr->avr_ack_seqno > ackno) |
d23ca15a | 254 | break; /* old news */ |
ae31c339 ACM |
255 | } |
256 | } | |
257 | ||
258 | static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec *av, | |
bdf13d20 | 259 | struct sock *sk, u64 *ackno, |
ae31c339 ACM |
260 | const unsigned char len, |
261 | const unsigned char *vector) | |
262 | { | |
263 | unsigned char i; | |
02bcf28c | 264 | struct dccp_ackvec_record *avr; |
ae31c339 ACM |
265 | |
266 | /* Check if we actually sent an ACK vector */ | |
a47c5104 | 267 | if (list_empty(&av->av_records)) |
ae31c339 | 268 | return; |
ae31c339 ACM |
269 | |
270 | i = len; | |
02bcf28c AB |
271 | /* |
272 | * XXX | |
273 | * I think it might be more efficient to work backwards. See comment on | |
274 | * rcv_ackno. -sorbo. | |
275 | */ | |
a47c5104 | 276 | avr = list_entry(av->av_records.next, struct dccp_ackvec_record, avr_node); |
ae31c339 | 277 | while (i--) { |
f17a37c9 | 278 | const u8 rl = dccp_ackvec_runlen(vector); |
ae31c339 ACM |
279 | u64 ackno_end_rl; |
280 | ||
bdf13d20 | 281 | dccp_set_seqno(&ackno_end_rl, *ackno - rl); |
ae31c339 ACM |
282 | |
283 | /* | |
02bcf28c AB |
284 | * If our AVR sequence number is greater than the ack, go |
285 | * forward in the AVR list until it is not so. | |
ae31c339 | 286 | */ |
a47c5104 GR |
287 | list_for_each_entry_from(avr, &av->av_records, avr_node) { |
288 | if (!after48(avr->avr_ack_seqno, *ackno)) | |
02bcf28c AB |
289 | goto found; |
290 | } | |
a47c5104 | 291 | /* End of the av_records list, not found, exit */ |
02bcf28c AB |
292 | break; |
293 | found: | |
a47c5104 | 294 | if (between48(avr->avr_ack_seqno, ackno_end_rl, *ackno)) { |
f17a37c9 | 295 | if (dccp_ackvec_state(vector) != DCCPAV_NOT_RECEIVED) { |
09dbc389 | 296 | dccp_pr_debug("%s ACK vector 0, len=%d, " |
ae31c339 ACM |
297 | "ack_seqno=%llu, ack_ackno=%llu, " |
298 | "ACKED!\n", | |
09dbc389 | 299 | dccp_role(sk), len, |
ae31c339 | 300 | (unsigned long long) |
a47c5104 | 301 | avr->avr_ack_seqno, |
ae31c339 | 302 | (unsigned long long) |
a47c5104 | 303 | avr->avr_ack_ackno); |
02bcf28c | 304 | dccp_ackvec_throw_record(av, avr); |
afec35e3 | 305 | break; |
ae31c339 ACM |
306 | } |
307 | /* | |
02bcf28c AB |
308 | * If it wasn't received, continue scanning... we might |
309 | * find another one. | |
ae31c339 | 310 | */ |
ae31c339 | 311 | } |
ae31c339 | 312 | |
bdf13d20 | 313 | dccp_set_seqno(ackno, ackno_end_rl - 1); |
ae31c339 ACM |
314 | ++vector; |
315 | } | |
316 | } | |
317 | ||
318 | int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb, | |
bdf13d20 | 319 | u64 *ackno, const u8 opt, const u8 *value, const u8 len) |
ae31c339 | 320 | { |
b20a9c24 | 321 | if (len > DCCP_SINGLE_OPT_MAXLEN) |
ae31c339 ACM |
322 | return -1; |
323 | ||
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, | |
bdf13d20 | 326 | ackno, len, value); |
ae31c339 ACM |
327 | return 0; |
328 | } | |
9b07ef5d | 329 | |
9b07ef5d ACM |
330 | int __init dccp_ackvec_init(void) |
331 | { | |
332 | dccp_ackvec_slab = kmem_cache_create("dccp_ackvec", | |
333 | sizeof(struct dccp_ackvec), 0, | |
20c2df83 | 334 | SLAB_HWCACHE_ALIGN, NULL); |
02bcf28c AB |
335 | if (dccp_ackvec_slab == NULL) |
336 | goto out_err; | |
337 | ||
f17a37c9 GR |
338 | dccp_ackvec_record_slab = kmem_cache_create("dccp_ackvec_record", |
339 | sizeof(struct dccp_ackvec_record), | |
340 | 0, SLAB_HWCACHE_ALIGN, NULL); | |
02bcf28c AB |
341 | if (dccp_ackvec_record_slab == NULL) |
342 | goto out_destroy_slab; | |
9b07ef5d ACM |
343 | |
344 | return 0; | |
02bcf28c AB |
345 | |
346 | out_destroy_slab: | |
347 | kmem_cache_destroy(dccp_ackvec_slab); | |
348 | dccp_ackvec_slab = NULL; | |
349 | out_err: | |
59348b19 | 350 | DCCP_CRIT("Unable to create Ack Vector slab cache"); |
02bcf28c | 351 | return -ENOBUFS; |
9b07ef5d ACM |
352 | } |
353 | ||
354 | void dccp_ackvec_exit(void) | |
355 | { | |
356 | if (dccp_ackvec_slab != NULL) { | |
357 | kmem_cache_destroy(dccp_ackvec_slab); | |
358 | dccp_ackvec_slab = NULL; | |
359 | } | |
02bcf28c AB |
360 | if (dccp_ackvec_record_slab != NULL) { |
361 | kmem_cache_destroy(dccp_ackvec_record_slab); | |
362 | dccp_ackvec_record_slab = NULL; | |
363 | } | |
9b07ef5d | 364 | } |