Root/
1 | /* |
2 | * net/dccp/ackvec.c |
3 | * |
4 | * An implementation of the DCCP protocol |
5 | * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@ghostprotocols.net> |
6 | * |
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; |
10 | */ |
11 | |
12 | #include "ackvec.h" |
13 | #include "dccp.h" |
14 | |
15 | #include <linux/init.h> |
16 | #include <linux/errno.h> |
17 | #include <linux/kernel.h> |
18 | #include <linux/skbuff.h> |
19 | #include <linux/slab.h> |
20 | |
21 | #include <net/sock.h> |
22 | |
23 | static struct kmem_cache *dccp_ackvec_slab; |
24 | static struct kmem_cache *dccp_ackvec_record_slab; |
25 | |
26 | static struct dccp_ackvec_record *dccp_ackvec_record_new(void) |
27 | { |
28 | struct dccp_ackvec_record *avr = |
29 | kmem_cache_alloc(dccp_ackvec_record_slab, GFP_ATOMIC); |
30 | |
31 | if (avr != NULL) |
32 | INIT_LIST_HEAD(&avr->avr_node); |
33 | |
34 | return avr; |
35 | } |
36 | |
37 | static void dccp_ackvec_record_delete(struct dccp_ackvec_record *avr) |
38 | { |
39 | if (unlikely(avr == NULL)) |
40 | return; |
41 | /* Check if deleting a linked record */ |
42 | WARN_ON(!list_empty(&avr->avr_node)); |
43 | kmem_cache_free(dccp_ackvec_record_slab, avr); |
44 | } |
45 | |
46 | static void dccp_ackvec_insert_avr(struct dccp_ackvec *av, |
47 | struct dccp_ackvec_record *avr) |
48 | { |
49 | /* |
50 | * AVRs are sorted by seqno. Since we are sending them in order, we |
51 | * just add the AVR at the head of the list. |
52 | * -sorbo. |
53 | */ |
54 | if (!list_empty(&av->av_records)) { |
55 | const struct dccp_ackvec_record *head = |
56 | list_entry(av->av_records.next, |
57 | struct dccp_ackvec_record, |
58 | avr_node); |
59 | BUG_ON(before48(avr->avr_ack_seqno, head->avr_ack_seqno)); |
60 | } |
61 | |
62 | list_add(&avr->avr_node, &av->av_records); |
63 | } |
64 | |
65 | int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb) |
66 | { |
67 | struct dccp_sock *dp = dccp_sk(sk); |
68 | struct dccp_ackvec *av = dp->dccps_hc_rx_ackvec; |
69 | /* Figure out how many options do we need to represent the ackvec */ |
70 | const u8 nr_opts = DIV_ROUND_UP(av->av_vec_len, DCCP_SINGLE_OPT_MAXLEN); |
71 | u16 len = av->av_vec_len + 2 * nr_opts, i; |
72 | u32 elapsed_time; |
73 | const unsigned char *tail, *from; |
74 | unsigned char *to; |
75 | struct dccp_ackvec_record *avr; |
76 | suseconds_t delta; |
77 | |
78 | if (DCCP_SKB_CB(skb)->dccpd_opt_len + len > DCCP_MAX_OPT_LEN) |
79 | return -1; |
80 | |
81 | delta = ktime_us_delta(ktime_get_real(), av->av_time); |
82 | elapsed_time = delta / 10; |
83 | |
84 | if (elapsed_time != 0 && |
85 | dccp_insert_option_elapsed_time(skb, elapsed_time)) |
86 | return -1; |
87 | |
88 | avr = dccp_ackvec_record_new(); |
89 | if (avr == NULL) |
90 | return -1; |
91 | |
92 | DCCP_SKB_CB(skb)->dccpd_opt_len += len; |
93 | |
94 | to = skb_push(skb, len); |
95 | len = av->av_vec_len; |
96 | from = av->av_buf + av->av_buf_head; |
97 | tail = av->av_buf + DCCP_MAX_ACKVEC_LEN; |
98 | |
99 | for (i = 0; i < nr_opts; ++i) { |
100 | int copylen = len; |
101 | |
102 | if (len > DCCP_SINGLE_OPT_MAXLEN) |
103 | copylen = DCCP_SINGLE_OPT_MAXLEN; |
104 | |
105 | *to++ = DCCPO_ACK_VECTOR_0; |
106 | *to++ = copylen + 2; |
107 | |
108 | /* Check if buf_head wraps */ |
109 | if (from + copylen > tail) { |
110 | const u16 tailsize = tail - from; |
111 | |
112 | memcpy(to, from, tailsize); |
113 | to += tailsize; |
114 | len -= tailsize; |
115 | copylen -= tailsize; |
116 | from = av->av_buf; |
117 | } |
118 | |
119 | memcpy(to, from, copylen); |
120 | from += copylen; |
121 | to += copylen; |
122 | len -= copylen; |
123 | } |
124 | |
125 | /* |
126 | * From RFC 4340, A.2: |
127 | * |
128 | * For each acknowledgement it sends, the HC-Receiver will add an |
129 | * acknowledgement record. ack_seqno will equal the HC-Receiver |
130 | * sequence number it used for the ack packet; ack_ptr will equal |
131 | * buf_head; ack_ackno will equal buf_ackno; and ack_nonce will |
132 | * equal buf_nonce. |
133 | */ |
134 | avr->avr_ack_seqno = DCCP_SKB_CB(skb)->dccpd_seq; |
135 | avr->avr_ack_ptr = av->av_buf_head; |
136 | avr->avr_ack_ackno = av->av_buf_ackno; |
137 | avr->avr_ack_nonce = av->av_buf_nonce; |
138 | avr->avr_sent_len = av->av_vec_len; |
139 | |
140 | dccp_ackvec_insert_avr(av, avr); |
141 | |
142 | dccp_pr_debug("%s ACK Vector 0, len=%d, ack_seqno=%llu, " |
143 | "ack_ackno=%llu\n", |
144 | dccp_role(sk), avr->avr_sent_len, |
145 | (unsigned long long)avr->avr_ack_seqno, |
146 | (unsigned long long)avr->avr_ack_ackno); |
147 | return 0; |
148 | } |
149 | |
150 | struct dccp_ackvec *dccp_ackvec_alloc(const gfp_t priority) |
151 | { |
152 | struct dccp_ackvec *av = kmem_cache_alloc(dccp_ackvec_slab, priority); |
153 | |
154 | if (av != NULL) { |
155 | av->av_buf_head = DCCP_MAX_ACKVEC_LEN - 1; |
156 | av->av_buf_ackno = UINT48_MAX + 1; |
157 | av->av_buf_nonce = 0; |
158 | av->av_time = ktime_set(0, 0); |
159 | av->av_vec_len = 0; |
160 | INIT_LIST_HEAD(&av->av_records); |
161 | } |
162 | |
163 | return av; |
164 | } |
165 | |
166 | void dccp_ackvec_free(struct dccp_ackvec *av) |
167 | { |
168 | if (unlikely(av == NULL)) |
169 | return; |
170 | |
171 | if (!list_empty(&av->av_records)) { |
172 | struct dccp_ackvec_record *avr, *next; |
173 | |
174 | list_for_each_entry_safe(avr, next, &av->av_records, avr_node) { |
175 | list_del_init(&avr->avr_node); |
176 | dccp_ackvec_record_delete(avr); |
177 | } |
178 | } |
179 | |
180 | kmem_cache_free(dccp_ackvec_slab, av); |
181 | } |
182 | |
183 | static inline u8 dccp_ackvec_state(const struct dccp_ackvec *av, |
184 | const u32 index) |
185 | { |
186 | return av->av_buf[index] & DCCP_ACKVEC_STATE_MASK; |
187 | } |
188 | |
189 | static inline u8 dccp_ackvec_len(const struct dccp_ackvec *av, |
190 | const u32 index) |
191 | { |
192 | return av->av_buf[index] & DCCP_ACKVEC_LEN_MASK; |
193 | } |
194 | |
195 | /* |
196 | * If several packets are missing, the HC-Receiver may prefer to enter multiple |
197 | * bytes with run length 0, rather than a single byte with a larger run length; |
198 | * this simplifies table updates if one of the missing packets arrives. |
199 | */ |
200 | static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec *av, |
201 | const unsigned int packets, |
202 | const unsigned char state) |
203 | { |
204 | long gap; |
205 | long new_head; |
206 | |
207 | if (av->av_vec_len + packets > DCCP_MAX_ACKVEC_LEN) |
208 | return -ENOBUFS; |
209 | |
210 | gap = packets - 1; |
211 | new_head = av->av_buf_head - packets; |
212 | |
213 | if (new_head < 0) { |
214 | if (gap > 0) { |
215 | memset(av->av_buf, DCCP_ACKVEC_STATE_NOT_RECEIVED, |
216 | gap + new_head + 1); |
217 | gap = -new_head; |
218 | } |
219 | new_head += DCCP_MAX_ACKVEC_LEN; |
220 | } |
221 | |
222 | av->av_buf_head = new_head; |
223 | |
224 | if (gap > 0) |
225 | memset(av->av_buf + av->av_buf_head + 1, |
226 | DCCP_ACKVEC_STATE_NOT_RECEIVED, gap); |
227 | |
228 | av->av_buf[av->av_buf_head] = state; |
229 | av->av_vec_len += packets; |
230 | return 0; |
231 | } |
232 | |
233 | /* |
234 | * Implements the RFC 4340, Appendix A |
235 | */ |
236 | int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk, |
237 | const u64 ackno, const u8 state) |
238 | { |
239 | /* |
240 | * Check at the right places if the buffer is full, if it is, tell the |
241 | * caller to start dropping packets till the HC-Sender acks our ACK |
242 | * vectors, when we will free up space in av_buf. |
243 | * |
244 | * We may well decide to do buffer compression, etc, but for now lets |
245 | * just drop. |
246 | * |
247 | * From Appendix A.1.1 (`New Packets'): |
248 | * |
249 | * Of course, the circular buffer may overflow, either when the |
250 | * HC-Sender is sending data at a very high rate, when the |
251 | * HC-Receiver's acknowledgements are not reaching the HC-Sender, |
252 | * or when the HC-Sender is forgetting to acknowledge those acks |
253 | * (so the HC-Receiver is unable to clean up old state). In this |
254 | * case, the HC-Receiver should either compress the buffer (by |
255 | * increasing run lengths when possible), transfer its state to |
256 | * a larger buffer, or, as a last resort, drop all received |
257 | * packets, without processing them whatsoever, until its buffer |
258 | * shrinks again. |
259 | */ |
260 | |
261 | /* See if this is the first ackno being inserted */ |
262 | if (av->av_vec_len == 0) { |
263 | av->av_buf[av->av_buf_head] = state; |
264 | av->av_vec_len = 1; |
265 | } else if (after48(ackno, av->av_buf_ackno)) { |
266 | const u64 delta = dccp_delta_seqno(av->av_buf_ackno, ackno); |
267 | |
268 | /* |
269 | * Look if the state of this packet is the same as the |
270 | * previous ackno and if so if we can bump the head len. |
271 | */ |
272 | if (delta == 1 && |
273 | dccp_ackvec_state(av, av->av_buf_head) == state && |
274 | dccp_ackvec_len(av, av->av_buf_head) < DCCP_ACKVEC_LEN_MASK) |
275 | av->av_buf[av->av_buf_head]++; |
276 | else if (dccp_ackvec_set_buf_head_state(av, delta, state)) |
277 | return -ENOBUFS; |
278 | } else { |
279 | /* |
280 | * A.1.2. Old Packets |
281 | * |
282 | * When a packet with Sequence Number S <= buf_ackno |
283 | * arrives, the HC-Receiver will scan the table for |
284 | * the byte corresponding to S. (Indexing structures |
285 | * could reduce the complexity of this scan.) |
286 | */ |
287 | u64 delta = dccp_delta_seqno(ackno, av->av_buf_ackno); |
288 | u32 index = av->av_buf_head; |
289 | |
290 | while (1) { |
291 | const u8 len = dccp_ackvec_len(av, index); |
292 | const u8 av_state = dccp_ackvec_state(av, index); |
293 | /* |
294 | * valid packets not yet in av_buf have a reserved |
295 | * entry, with a len equal to 0. |
296 | */ |
297 | if (av_state == DCCP_ACKVEC_STATE_NOT_RECEIVED && |
298 | len == 0 && delta == 0) { /* Found our |
299 | reserved seat! */ |
300 | dccp_pr_debug("Found %llu reserved seat!\n", |
301 | (unsigned long long)ackno); |
302 | av->av_buf[index] = state; |
303 | goto out; |
304 | } |
305 | /* len == 0 means one packet */ |
306 | if (delta < len + 1) |
307 | goto out_duplicate; |
308 | |
309 | delta -= len + 1; |
310 | if (++index == DCCP_MAX_ACKVEC_LEN) |
311 | index = 0; |
312 | } |
313 | } |
314 | |
315 | av->av_buf_ackno = ackno; |
316 | av->av_time = ktime_get_real(); |
317 | out: |
318 | return 0; |
319 | |
320 | out_duplicate: |
321 | /* Duplicate packet */ |
322 | dccp_pr_debug("Received a dup or already considered lost " |
323 | "packet: %llu\n", (unsigned long long)ackno); |
324 | return -EILSEQ; |
325 | } |
326 | |
327 | static void dccp_ackvec_throw_record(struct dccp_ackvec *av, |
328 | struct dccp_ackvec_record *avr) |
329 | { |
330 | struct dccp_ackvec_record *next; |
331 | |
332 | /* sort out vector length */ |
333 | if (av->av_buf_head <= avr->avr_ack_ptr) |
334 | av->av_vec_len = avr->avr_ack_ptr - av->av_buf_head; |
335 | else |
336 | av->av_vec_len = DCCP_MAX_ACKVEC_LEN - 1 - |
337 | av->av_buf_head + avr->avr_ack_ptr; |
338 | |
339 | /* free records */ |
340 | list_for_each_entry_safe_from(avr, next, &av->av_records, avr_node) { |
341 | list_del_init(&avr->avr_node); |
342 | dccp_ackvec_record_delete(avr); |
343 | } |
344 | } |
345 | |
346 | void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec *av, struct sock *sk, |
347 | const u64 ackno) |
348 | { |
349 | struct dccp_ackvec_record *avr; |
350 | |
351 | /* |
352 | * If we traverse backwards, it should be faster when we have large |
353 | * windows. We will be receiving ACKs for stuff we sent a while back |
354 | * -sorbo. |
355 | */ |
356 | list_for_each_entry_reverse(avr, &av->av_records, avr_node) { |
357 | if (ackno == avr->avr_ack_seqno) { |
358 | dccp_pr_debug("%s ACK packet 0, len=%d, ack_seqno=%llu, " |
359 | "ack_ackno=%llu, ACKED!\n", |
360 | dccp_role(sk), 1, |
361 | (unsigned long long)avr->avr_ack_seqno, |
362 | (unsigned long long)avr->avr_ack_ackno); |
363 | dccp_ackvec_throw_record(av, avr); |
364 | break; |
365 | } else if (avr->avr_ack_seqno > ackno) |
366 | break; /* old news */ |
367 | } |
368 | } |
369 | |
370 | static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec *av, |
371 | struct sock *sk, u64 *ackno, |
372 | const unsigned char len, |
373 | const unsigned char *vector) |
374 | { |
375 | unsigned char i; |
376 | struct dccp_ackvec_record *avr; |
377 | |
378 | /* Check if we actually sent an ACK vector */ |
379 | if (list_empty(&av->av_records)) |
380 | return; |
381 | |
382 | i = len; |
383 | /* |
384 | * XXX |
385 | * I think it might be more efficient to work backwards. See comment on |
386 | * rcv_ackno. -sorbo. |
387 | */ |
388 | avr = list_entry(av->av_records.next, struct dccp_ackvec_record, avr_node); |
389 | while (i--) { |
390 | const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK; |
391 | u64 ackno_end_rl; |
392 | |
393 | dccp_set_seqno(&ackno_end_rl, *ackno - rl); |
394 | |
395 | /* |
396 | * If our AVR sequence number is greater than the ack, go |
397 | * forward in the AVR list until it is not so. |
398 | */ |
399 | list_for_each_entry_from(avr, &av->av_records, avr_node) { |
400 | if (!after48(avr->avr_ack_seqno, *ackno)) |
401 | goto found; |
402 | } |
403 | /* End of the av_records list, not found, exit */ |
404 | break; |
405 | found: |
406 | if (between48(avr->avr_ack_seqno, ackno_end_rl, *ackno)) { |
407 | const u8 state = *vector & DCCP_ACKVEC_STATE_MASK; |
408 | if (state != DCCP_ACKVEC_STATE_NOT_RECEIVED) { |
409 | dccp_pr_debug("%s ACK vector 0, len=%d, " |
410 | "ack_seqno=%llu, ack_ackno=%llu, " |
411 | "ACKED!\n", |
412 | dccp_role(sk), len, |
413 | (unsigned long long) |
414 | avr->avr_ack_seqno, |
415 | (unsigned long long) |
416 | avr->avr_ack_ackno); |
417 | dccp_ackvec_throw_record(av, avr); |
418 | break; |
419 | } |
420 | /* |
421 | * If it wasn't received, continue scanning... we might |
422 | * find another one. |
423 | */ |
424 | } |
425 | |
426 | dccp_set_seqno(ackno, ackno_end_rl - 1); |
427 | ++vector; |
428 | } |
429 | } |
430 | |
431 | int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb, |
432 | u64 *ackno, const u8 opt, const u8 *value, const u8 len) |
433 | { |
434 | if (len > DCCP_SINGLE_OPT_MAXLEN) |
435 | return -1; |
436 | |
437 | /* dccp_ackvector_print(DCCP_SKB_CB(skb)->dccpd_ack_seq, value, len); */ |
438 | dccp_ackvec_check_rcv_ackvector(dccp_sk(sk)->dccps_hc_rx_ackvec, sk, |
439 | ackno, len, value); |
440 | return 0; |
441 | } |
442 | |
443 | int __init dccp_ackvec_init(void) |
444 | { |
445 | dccp_ackvec_slab = kmem_cache_create("dccp_ackvec", |
446 | sizeof(struct dccp_ackvec), 0, |
447 | SLAB_HWCACHE_ALIGN, NULL); |
448 | if (dccp_ackvec_slab == NULL) |
449 | goto out_err; |
450 | |
451 | dccp_ackvec_record_slab = |
452 | kmem_cache_create("dccp_ackvec_record", |
453 | sizeof(struct dccp_ackvec_record), |
454 | 0, SLAB_HWCACHE_ALIGN, NULL); |
455 | if (dccp_ackvec_record_slab == NULL) |
456 | goto out_destroy_slab; |
457 | |
458 | return 0; |
459 | |
460 | out_destroy_slab: |
461 | kmem_cache_destroy(dccp_ackvec_slab); |
462 | dccp_ackvec_slab = NULL; |
463 | out_err: |
464 | DCCP_CRIT("Unable to create Ack Vector slab cache"); |
465 | return -ENOBUFS; |
466 | } |
467 | |
468 | void dccp_ackvec_exit(void) |
469 | { |
470 | if (dccp_ackvec_slab != NULL) { |
471 | kmem_cache_destroy(dccp_ackvec_slab); |
472 | dccp_ackvec_slab = NULL; |
473 | } |
474 | if (dccp_ackvec_record_slab != NULL) { |
475 | kmem_cache_destroy(dccp_ackvec_record_slab); |
476 | dccp_ackvec_record_slab = NULL; |
477 | } |
478 | } |
479 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9