1
2
3
4
5
6
7
8
9
10
11
12#include "ackvec.h"
13#include "dccp.h"
14
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>
21
22#include <net/sock.h>
23
24static struct kmem_cache *dccp_ackvec_slab;
25static struct kmem_cache *dccp_ackvec_record_slab;
26
27static struct dccp_ackvec_record *dccp_ackvec_record_new(void)
28{
29 struct dccp_ackvec_record *avr =
30 kmem_cache_alloc(dccp_ackvec_record_slab, GFP_ATOMIC);
31
32 if (avr != NULL)
33 INIT_LIST_HEAD(&avr->dccpavr_node);
34
35 return avr;
36}
37
38static void dccp_ackvec_record_delete(struct dccp_ackvec_record *avr)
39{
40 if (unlikely(avr == NULL))
41 return;
42
43 WARN_ON(!list_empty(&avr->dccpavr_node));
44 kmem_cache_free(dccp_ackvec_record_slab, avr);
45}
46
47static void dccp_ackvec_insert_avr(struct dccp_ackvec *av,
48 struct dccp_ackvec_record *avr)
49{
50
51
52
53
54
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,
59 dccpavr_node);
60 BUG_ON(before48(avr->dccpavr_ack_seqno,
61 head->dccpavr_ack_seqno));
62 }
63
64 list_add(&avr->dccpavr_node, &av->dccpav_records);
65}
66
67int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb)
68{
69 struct dccp_sock *dp = dccp_sk(sk);
70 struct dccp_ackvec *av = dp->dccps_hc_rx_ackvec;
71
72 const u16 nr_opts = DIV_ROUND_UP(av->dccpav_vec_len,
73 DCCP_MAX_ACKVEC_OPT_LEN);
74 u16 len = av->dccpav_vec_len + 2 * nr_opts, i;
75 u32 elapsed_time;
76 const unsigned char *tail, *from;
77 unsigned char *to;
78 struct dccp_ackvec_record *avr;
79 suseconds_t delta;
80
81 if (DCCP_SKB_CB(skb)->dccpd_opt_len + len > DCCP_MAX_OPT_LEN)
82 return -1;
83
84 delta = ktime_us_delta(ktime_get_real(), av->dccpav_time);
85 elapsed_time = delta / 10;
86
87 if (elapsed_time != 0 &&
88 dccp_insert_option_elapsed_time(sk, skb, elapsed_time))
89 return -1;
90
91 avr = dccp_ackvec_record_new();
92 if (avr == NULL)
93 return -1;
94
95 DCCP_SKB_CB(skb)->dccpd_opt_len += len;
96
97 to = skb_push(skb, len);
98 len = av->dccpav_vec_len;
99 from = av->dccpav_buf + av->dccpav_buf_head;
100 tail = av->dccpav_buf + DCCP_MAX_ACKVEC_LEN;
101
102 for (i = 0; i < nr_opts; ++i) {
103 int copylen = len;
104
105 if (len > DCCP_MAX_ACKVEC_OPT_LEN)
106 copylen = DCCP_MAX_ACKVEC_OPT_LEN;
107
108 *to++ = DCCPO_ACK_VECTOR_0;
109 *to++ = copylen + 2;
110
111
112 if (from + copylen > tail) {
113 const u16 tailsize = tail - from;
114
115 memcpy(to, from, tailsize);
116 to += tailsize;
117 len -= tailsize;
118 copylen -= tailsize;
119 from = av->dccpav_buf;
120 }
121
122 memcpy(to, from, copylen);
123 from += copylen;
124 to += copylen;
125 len -= copylen;
126 }
127
128
129
130
131
132
133
134
135
136
137 avr->dccpavr_ack_seqno = DCCP_SKB_CB(skb)->dccpd_seq;
138 avr->dccpavr_ack_ptr = av->dccpav_buf_head;
139 avr->dccpavr_ack_ackno = av->dccpav_buf_ackno;
140 avr->dccpavr_ack_nonce = av->dccpav_buf_nonce;
141 avr->dccpavr_sent_len = av->dccpav_vec_len;
142
143 dccp_ackvec_insert_avr(av, avr);
144
145 dccp_pr_debug("%s ACK Vector 0, len=%d, ack_seqno=%llu, "
146 "ack_ackno=%llu\n",
147 dccp_role(sk), avr->dccpavr_sent_len,
148 (unsigned long long)avr->dccpavr_ack_seqno,
149 (unsigned long long)avr->dccpavr_ack_ackno);
150 return 0;
151}
152
153struct dccp_ackvec *dccp_ackvec_alloc(const gfp_t priority)
154{
155 struct dccp_ackvec *av = kmem_cache_alloc(dccp_ackvec_slab, priority);
156
157 if (av != NULL) {
158 av->dccpav_buf_head = DCCP_MAX_ACKVEC_LEN - 1;
159 av->dccpav_buf_ackno = UINT48_MAX + 1;
160 av->dccpav_buf_nonce = av->dccpav_buf_nonce = 0;
161 av->dccpav_time = ktime_set(0, 0);
162 av->dccpav_vec_len = 0;
163 INIT_LIST_HEAD(&av->dccpav_records);
164 }
165
166 return av;
167}
168
169void dccp_ackvec_free(struct dccp_ackvec *av)
170{
171 if (unlikely(av == NULL))
172 return;
173
174 if (!list_empty(&av->dccpav_records)) {
175 struct dccp_ackvec_record *avr, *next;
176
177 list_for_each_entry_safe(avr, next, &av->dccpav_records,
178 dccpavr_node) {
179 list_del_init(&avr->dccpavr_node);
180 dccp_ackvec_record_delete(avr);
181 }
182 }
183
184 kmem_cache_free(dccp_ackvec_slab, av);
185}
186
187static inline u8 dccp_ackvec_state(const struct dccp_ackvec *av,
188 const u32 index)
189{
190 return av->dccpav_buf[index] & DCCP_ACKVEC_STATE_MASK;
191}
192
193static inline u8 dccp_ackvec_len(const struct dccp_ackvec *av,
194 const u32 index)
195{
196 return av->dccpav_buf[index] & DCCP_ACKVEC_LEN_MASK;
197}
198
199
200
201
202
203
204static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec *av,
205 const unsigned int packets,
206 const unsigned char state)
207{
208 unsigned int gap;
209 long new_head;
210
211 if (av->dccpav_vec_len + packets > DCCP_MAX_ACKVEC_LEN)
212 return -ENOBUFS;
213
214 gap = packets - 1;
215 new_head = av->dccpav_buf_head - packets;
216
217 if (new_head < 0) {
218 if (gap > 0) {
219 memset(av->dccpav_buf, DCCP_ACKVEC_STATE_NOT_RECEIVED,
220 gap + new_head + 1);
221 gap = -new_head;
222 }
223 new_head += DCCP_MAX_ACKVEC_LEN;
224 }
225
226 av->dccpav_buf_head = new_head;
227
228 if (gap > 0)
229 memset(av->dccpav_buf + av->dccpav_buf_head + 1,
230 DCCP_ACKVEC_STATE_NOT_RECEIVED, gap);
231
232 av->dccpav_buf[av->dccpav_buf_head] = state;
233 av->dccpav_vec_len += packets;
234 return 0;
235}
236
237
238
239
240int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk,
241 const u64 ackno, const u8 state)
242{
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266 if (av->dccpav_vec_len == 0) {
267 av->dccpav_buf[av->dccpav_buf_head] = state;
268 av->dccpav_vec_len = 1;
269 } else if (after48(ackno, av->dccpav_buf_ackno)) {
270 const u64 delta = dccp_delta_seqno(av->dccpav_buf_ackno,
271 ackno);
272
273
274
275
276
277 if (delta == 1 &&
278 dccp_ackvec_state(av, av->dccpav_buf_head) == state &&
279 (dccp_ackvec_len(av, av->dccpav_buf_head) <
280 DCCP_ACKVEC_LEN_MASK))
281 av->dccpav_buf[av->dccpav_buf_head]++;
282 else if (dccp_ackvec_set_buf_head_state(av, delta, state))
283 return -ENOBUFS;
284 } else {
285
286
287
288
289
290
291
292
293 u64 delta = dccp_delta_seqno(ackno, av->dccpav_buf_ackno);
294 u32 index = av->dccpav_buf_head;
295
296 while (1) {
297 const u8 len = dccp_ackvec_len(av, index);
298 const u8 state = dccp_ackvec_state(av, index);
299
300
301
302
303 if (state == DCCP_ACKVEC_STATE_NOT_RECEIVED &&
304 len == 0 && delta == 0) {
305
306 dccp_pr_debug("Found %llu reserved seat!\n",
307 (unsigned long long)ackno);
308 av->dccpav_buf[index] = state;
309 goto out;
310 }
311
312 if (delta < len + 1)
313 goto out_duplicate;
314
315 delta -= len + 1;
316 if (++index == DCCP_MAX_ACKVEC_LEN)
317 index = 0;
318 }
319 }
320
321 av->dccpav_buf_ackno = ackno;
322 av->dccpav_time = ktime_get_real();
323out:
324 return 0;
325
326out_duplicate:
327
328 dccp_pr_debug("Received a dup or already considered lost "
329 "packet: %llu\n", (unsigned long long)ackno);
330 return -EILSEQ;
331}
332
333#ifdef CONFIG_IP_DCCP_DEBUG
334void dccp_ackvector_print(const u64 ackno, const unsigned char *vector, int len)
335{
336 dccp_pr_debug_cat("ACK vector len=%d, ackno=%llu |", len,
337 (unsigned long long)ackno);
338
339 while (len--) {
340 const u8 state = (*vector & DCCP_ACKVEC_STATE_MASK) >> 6;
341 const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK;
342
343 dccp_pr_debug_cat("%d,%d|", state, rl);
344 ++vector;
345 }
346
347 dccp_pr_debug_cat("\n");
348}
349
350void dccp_ackvec_print(const struct dccp_ackvec *av)
351{
352 dccp_ackvector_print(av->dccpav_buf_ackno,
353 av->dccpav_buf + av->dccpav_buf_head,
354 av->dccpav_vec_len);
355}
356#endif
357
358static void dccp_ackvec_throw_record(struct dccp_ackvec *av,
359 struct dccp_ackvec_record *avr)
360{
361 struct dccp_ackvec_record *next;
362
363
364 if (av->dccpav_buf_head <= avr->dccpavr_ack_ptr)
365 av->dccpav_vec_len = avr->dccpavr_ack_ptr - av->dccpav_buf_head;
366 else
367 av->dccpav_vec_len = DCCP_MAX_ACKVEC_LEN - 1
368 - av->dccpav_buf_head
369 + avr->dccpavr_ack_ptr;
370
371
372 list_for_each_entry_safe_from(avr, next, &av->dccpav_records,
373 dccpavr_node) {
374 list_del_init(&avr->dccpavr_node);
375 dccp_ackvec_record_delete(avr);
376 }
377}
378
379void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec *av, struct sock *sk,
380 const u64 ackno)
381{
382 struct dccp_ackvec_record *avr;
383
384
385
386
387
388
389 list_for_each_entry_reverse(avr, &av->dccpav_records, dccpavr_node) {
390 if (ackno == avr->dccpavr_ack_seqno) {
391 dccp_pr_debug("%s ACK packet 0, len=%d, ack_seqno=%llu, "
392 "ack_ackno=%llu, ACKED!\n",
393 dccp_role(sk), 1,
394 (unsigned long long)avr->dccpavr_ack_seqno,
395 (unsigned long long)avr->dccpavr_ack_ackno);
396 dccp_ackvec_throw_record(av, avr);
397 break;
398 } else if (avr->dccpavr_ack_seqno > ackno)
399 break;
400 }
401}
402
403static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec *av,
404 struct sock *sk, u64 *ackno,
405 const unsigned char len,
406 const unsigned char *vector)
407{
408 unsigned char i;
409 struct dccp_ackvec_record *avr;
410
411
412 if (list_empty(&av->dccpav_records))
413 return;
414
415 i = len;
416
417
418
419
420
421 avr = list_entry(av->dccpav_records.next, struct dccp_ackvec_record,
422 dccpavr_node);
423 while (i--) {
424 const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK;
425 u64 ackno_end_rl;
426
427 dccp_set_seqno(&ackno_end_rl, *ackno - rl);
428
429
430
431
432
433 list_for_each_entry_from(avr, &av->dccpav_records,
434 dccpavr_node) {
435 if (!after48(avr->dccpavr_ack_seqno, *ackno))
436 goto found;
437 }
438
439 break;
440found:
441 if (between48(avr->dccpavr_ack_seqno, ackno_end_rl, *ackno)) {
442 const u8 state = *vector & DCCP_ACKVEC_STATE_MASK;
443 if (state != DCCP_ACKVEC_STATE_NOT_RECEIVED) {
444 dccp_pr_debug("%s ACK vector 0, len=%d, "
445 "ack_seqno=%llu, ack_ackno=%llu, "
446 "ACKED!\n",
447 dccp_role(sk), len,
448 (unsigned long long)
449 avr->dccpavr_ack_seqno,
450 (unsigned long long)
451 avr->dccpavr_ack_ackno);
452 dccp_ackvec_throw_record(av, avr);
453 break;
454 }
455
456
457
458
459 }
460
461 dccp_set_seqno(ackno, ackno_end_rl - 1);
462 ++vector;
463 }
464}
465
466int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb,
467 u64 *ackno, const u8 opt, const u8 *value, const u8 len)
468{
469 if (len > DCCP_MAX_ACKVEC_OPT_LEN)
470 return -1;
471
472
473 dccp_ackvec_check_rcv_ackvector(dccp_sk(sk)->dccps_hc_rx_ackvec, sk,
474 ackno, len, value);
475 return 0;
476}
477
478int __init dccp_ackvec_init(void)
479{
480 dccp_ackvec_slab = kmem_cache_create("dccp_ackvec",
481 sizeof(struct dccp_ackvec), 0,
482 SLAB_HWCACHE_ALIGN, NULL);
483 if (dccp_ackvec_slab == NULL)
484 goto out_err;
485
486 dccp_ackvec_record_slab =
487 kmem_cache_create("dccp_ackvec_record",
488 sizeof(struct dccp_ackvec_record),
489 0, SLAB_HWCACHE_ALIGN, NULL);
490 if (dccp_ackvec_record_slab == NULL)
491 goto out_destroy_slab;
492
493 return 0;
494
495out_destroy_slab:
496 kmem_cache_destroy(dccp_ackvec_slab);
497 dccp_ackvec_slab = NULL;
498out_err:
499 DCCP_CRIT("Unable to create Ack Vector slab cache");
500 return -ENOBUFS;
501}
502
503void dccp_ackvec_exit(void)
504{
505 if (dccp_ackvec_slab != NULL) {
506 kmem_cache_destroy(dccp_ackvec_slab);
507 dccp_ackvec_slab = NULL;
508 }
509 if (dccp_ackvec_record_slab != NULL) {
510 kmem_cache_destroy(dccp_ackvec_record_slab);
511 dccp_ackvec_record_slab = NULL;
512 }
513}
514