2 * net/dccp/ccids/ccid3.c
4 * Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand.
5 * Copyright (c) 2005 Ian McDonald <iam4@cs.waikato.ac.nz>
7 * An implementation of the DCCP protocol
9 * This code has been developed by the University of Waikato WAND
10 * research group. For further information please see http://www.wand.net.nz/
12 * This code also uses code from Lulea University, rereleased as GPL by its
14 * Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
16 * Changes to meet Linux coding standards, to make it meet latest ccid3 draft
17 * and to make it work as a loadable module in the DCCP stack written by
18 * Arnaldo Carvalho de Melo <acme@conectiva.com.br>.
20 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
22 * This program is free software; you can redistribute it and/or modify
23 * it under the terms of the GNU General Public License as published by
24 * the Free Software Foundation; either version 2 of the License, or
25 * (at your option) any later version.
27 * This program is distributed in the hope that it will be useful,
28 * but WITHOUT ANY WARRANTY; without even the implied warranty of
29 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 * GNU General Public License for more details.
32 * You should have received a copy of the GNU General Public License
33 * along with this program; if not, write to the Free Software
34 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
37 #include <linux/config.h>
40 #include "../packet_history.h"
44 extern int ccid3_debug;
46 #define ccid3_pr_debug(format, a...) \
47 do { if (ccid3_debug) \
48 printk(KERN_DEBUG "%s: " format, __FUNCTION__, ##a); \
51 #define ccid3_pr_debug(format, a...)
54 #define TFRC_MIN_PACKET_SIZE 16
55 #define TFRC_STD_PACKET_SIZE 256
56 #define TFRC_MAX_PACKET_SIZE 65535
58 #define TFRC_INITIAL_TIMEOUT (2 * USEC_PER_SEC)
59 /* two seconds as per CCID3 spec 11 */
61 #define TFRC_OPSYS_HALF_TIME_GRAN (USEC_PER_SEC / (2 * HZ))
62 /* above is in usecs - half the scheduling granularity as per RFC3448 4.6 */
64 #define TFRC_WIN_COUNT_PER_RTT 4
65 #define TFRC_WIN_COUNT_LIMIT 16
67 #define TFRC_MAX_BACK_OFF_TIME 64
68 /* above is in seconds */
70 #define TFRC_SMALLEST_P 40
72 #define TFRC_RECV_IVAL_F_LENGTH 8 /* length(w[]) */
74 /* Number of later packets received before one is considered lost */
75 #define TFRC_RECV_NUM_LATE_LOSS 3
78 TFRC_OPT_LOSS_EVENT_RATE = 192,
79 TFRC_OPT_LOSS_INTERVALS = 193,
80 TFRC_OPT_RECEIVE_RATE = 194,
83 static int ccid3_debug;
85 static struct dccp_tx_hist *ccid3_tx_hist;
86 static struct dccp_rx_hist *ccid3_rx_hist;
88 static kmem_cache_t *ccid3_loss_interval_hist_slab __read_mostly;
90 static inline struct ccid3_loss_interval_hist_entry *
91 ccid3_loss_interval_hist_entry_new(const unsigned int __nocast prio)
93 return kmem_cache_alloc(ccid3_loss_interval_hist_slab, prio);
96 static inline void ccid3_loss_interval_hist_entry_delete(struct ccid3_loss_interval_hist_entry *entry)
99 kmem_cache_free(ccid3_loss_interval_hist_slab, entry);
102 static void ccid3_loss_interval_history_delete(struct list_head *hist)
104 struct ccid3_loss_interval_hist_entry *entry, *next;
106 list_for_each_entry_safe(entry, next, hist, ccid3lih_node) {
107 list_del_init(&entry->ccid3lih_node);
108 kmem_cache_free(ccid3_loss_interval_hist_slab, entry);
112 static int ccid3_init(struct sock *sk)
114 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
118 static void ccid3_exit(struct sock *sk)
120 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
123 /* TFRC sender states */
124 enum ccid3_hc_tx_states {
125 TFRC_SSTATE_NO_SENT = 1,
126 TFRC_SSTATE_NO_FBACK,
132 static const char *ccid3_tx_state_name(enum ccid3_hc_tx_states state)
134 static char *ccid3_state_names[] = {
135 [TFRC_SSTATE_NO_SENT] = "NO_SENT",
136 [TFRC_SSTATE_NO_FBACK] = "NO_FBACK",
137 [TFRC_SSTATE_FBACK] = "FBACK",
138 [TFRC_SSTATE_TERM] = "TERM",
141 return ccid3_state_names[state];
145 static inline void ccid3_hc_tx_set_state(struct sock *sk,
146 enum ccid3_hc_tx_states state)
148 struct dccp_sock *dp = dccp_sk(sk);
149 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
150 enum ccid3_hc_tx_states oldstate = hctx->ccid3hctx_state;
152 ccid3_pr_debug("%s(%p) %-8.8s -> %s\n",
153 dccp_role(sk), sk, ccid3_tx_state_name(oldstate),
154 ccid3_tx_state_name(state));
155 WARN_ON(state == oldstate);
156 hctx->ccid3hctx_state = state;
159 #define CALCX_ARRSIZE 500
161 #define CALCX_SPLIT 50000
162 /* equivalent to 0.05 */
164 static const u32 calcx_lookup[CALCX_ARRSIZE][2] = {
286 { 2976382 , 100134 },
287 { 3037850 , 100626 },
288 { 3100360 , 101117 },
289 { 3163924 , 101608 },
290 { 3228554 , 102097 },
291 { 3294263 , 102586 },
292 { 3361063 , 103073 },
293 { 3428966 , 103560 },
294 { 3497984 , 104045 },
295 { 3568131 , 104530 },
296 { 3639419 , 105014 },
297 { 3711860 , 105498 },
298 { 3785467 , 105980 },
299 { 3860253 , 106462 },
300 { 3936229 , 106942 },
301 { 4013410 , 107422 },
302 { 4091808 , 107902 },
303 { 4171435 , 108380 },
304 { 4252306 , 108858 },
305 { 4334431 , 109335 },
306 { 4417825 , 109811 },
307 { 4502501 , 110287 },
308 { 4588472 , 110762 },
309 { 4675750 , 111236 },
310 { 4764349 , 111709 },
311 { 4854283 , 112182 },
312 { 4945564 , 112654 },
313 { 5038206 , 113126 },
314 { 5132223 , 113597 },
315 { 5227627 , 114067 },
316 { 5324432 , 114537 },
317 { 5422652 , 115006 },
318 { 5522299 , 115474 },
319 { 5623389 , 115942 },
320 { 5725934 , 116409 },
321 { 5829948 , 116876 },
322 { 5935446 , 117342 },
323 { 6042439 , 117808 },
324 { 6150943 , 118273 },
325 { 6260972 , 118738 },
326 { 6372538 , 119202 },
327 { 6485657 , 119665 },
328 { 6600342 , 120128 },
329 { 6716607 , 120591 },
330 { 6834467 , 121053 },
331 { 6953935 , 121514 },
332 { 7075025 , 121976 },
333 { 7197752 , 122436 },
334 { 7322131 , 122896 },
335 { 7448175 , 123356 },
336 { 7575898 , 123815 },
337 { 7705316 , 124274 },
338 { 7836442 , 124733 },
339 { 7969291 , 125191 },
340 { 8103877 , 125648 },
341 { 8240216 , 126105 },
342 { 8378321 , 126562 },
343 { 8518208 , 127018 },
344 { 8659890 , 127474 },
345 { 8803384 , 127930 },
346 { 8948702 , 128385 },
347 { 9095861 , 128840 },
348 { 9244875 , 129294 },
349 { 9395760 , 129748 },
350 { 9548529 , 130202 },
351 { 9703198 , 130655 },
352 { 9859782 , 131108 },
353 { 10018296 , 131561 },
354 { 10178755 , 132014 },
355 { 10341174 , 132466 },
356 { 10505569 , 132917 },
357 { 10671954 , 133369 },
358 { 10840345 , 133820 },
359 { 11010757 , 134271 },
360 { 11183206 , 134721 },
361 { 11357706 , 135171 },
362 { 11534274 , 135621 },
363 { 11712924 , 136071 },
364 { 11893673 , 136520 },
365 { 12076536 , 136969 },
366 { 12261527 , 137418 },
367 { 12448664 , 137867 },
368 { 12637961 , 138315 },
369 { 12829435 , 138763 },
370 { 13023101 , 139211 },
371 { 13218974 , 139658 },
372 { 13417071 , 140106 },
373 { 13617407 , 140553 },
374 { 13819999 , 140999 },
375 { 14024862 , 141446 },
376 { 14232012 , 141892 },
377 { 14441465 , 142339 },
378 { 14653238 , 142785 },
379 { 14867346 , 143230 },
380 { 15083805 , 143676 },
381 { 15302632 , 144121 },
382 { 15523842 , 144566 },
383 { 15747453 , 145011 },
384 { 15973479 , 145456 },
385 { 16201939 , 145900 },
386 { 16432847 , 146345 },
387 { 16666221 , 146789 },
388 { 16902076 , 147233 },
389 { 17140429 , 147677 },
390 { 17381297 , 148121 },
391 { 17624696 , 148564 },
392 { 17870643 , 149007 },
393 { 18119154 , 149451 },
394 { 18370247 , 149894 },
395 { 18623936 , 150336 },
396 { 18880241 , 150779 },
397 { 19139176 , 151222 },
398 { 19400759 , 151664 },
399 { 19665007 , 152107 },
400 { 19931936 , 152549 },
401 { 20201564 , 152991 },
402 { 20473907 , 153433 },
403 { 20748982 , 153875 },
404 { 21026807 , 154316 },
405 { 21307399 , 154758 },
406 { 21590773 , 155199 },
407 { 21876949 , 155641 },
408 { 22165941 , 156082 },
409 { 22457769 , 156523 },
410 { 22752449 , 156964 },
411 { 23049999 , 157405 },
412 { 23350435 , 157846 },
413 { 23653774 , 158287 },
414 { 23960036 , 158727 },
415 { 24269236 , 159168 },
416 { 24581392 , 159608 },
417 { 24896521 , 160049 },
418 { 25214642 , 160489 },
419 { 25535772 , 160929 },
420 { 25859927 , 161370 },
421 { 26187127 , 161810 },
422 { 26517388 , 162250 },
423 { 26850728 , 162690 },
424 { 27187165 , 163130 },
425 { 27526716 , 163569 },
426 { 27869400 , 164009 },
427 { 28215234 , 164449 },
428 { 28564236 , 164889 },
429 { 28916423 , 165328 },
430 { 29271815 , 165768 },
431 { 29630428 , 166208 },
432 { 29992281 , 166647 },
433 { 30357392 , 167087 },
434 { 30725779 , 167526 },
435 { 31097459 , 167965 },
436 { 31472452 , 168405 },
437 { 31850774 , 168844 },
438 { 32232445 , 169283 },
439 { 32617482 , 169723 },
440 { 33005904 , 170162 },
441 { 33397730 , 170601 },
442 { 33792976 , 171041 },
443 { 34191663 , 171480 },
444 { 34593807 , 171919 },
445 { 34999428 , 172358 },
446 { 35408544 , 172797 },
447 { 35821174 , 173237 },
448 { 36237335 , 173676 },
449 { 36657047 , 174115 },
450 { 37080329 , 174554 },
451 { 37507197 , 174993 },
452 { 37937673 , 175433 },
453 { 38371773 , 175872 },
454 { 38809517 , 176311 },
455 { 39250924 , 176750 },
456 { 39696012 , 177190 },
457 { 40144800 , 177629 },
458 { 40597308 , 178068 },
459 { 41053553 , 178507 },
460 { 41513554 , 178947 },
461 { 41977332 , 179386 },
462 { 42444904 , 179825 },
463 { 42916290 , 180265 },
464 { 43391509 , 180704 },
465 { 43870579 , 181144 },
466 { 44353520 , 181583 },
467 { 44840352 , 182023 },
468 { 45331092 , 182462 },
469 { 45825761 , 182902 },
470 { 46324378 , 183342 },
471 { 46826961 , 183781 },
472 { 47333531 , 184221 },
473 { 47844106 , 184661 },
474 { 48358706 , 185101 },
475 { 48877350 , 185541 },
476 { 49400058 , 185981 },
477 { 49926849 , 186421 },
478 { 50457743 , 186861 },
479 { 50992759 , 187301 },
480 { 51531916 , 187741 },
481 { 52075235 , 188181 },
482 { 52622735 , 188622 },
483 { 53174435 , 189062 },
484 { 53730355 , 189502 },
485 { 54290515 , 189943 },
486 { 54854935 , 190383 },
487 { 55423634 , 190824 },
488 { 55996633 , 191265 },
489 { 56573950 , 191706 },
490 { 57155606 , 192146 },
491 { 57741621 , 192587 },
492 { 58332014 , 193028 },
493 { 58926806 , 193470 },
494 { 59526017 , 193911 },
495 { 60129666 , 194352 },
496 { 60737774 , 194793 },
497 { 61350361 , 195235 },
498 { 61967446 , 195677 },
499 { 62589050 , 196118 },
500 { 63215194 , 196560 },
501 { 63845897 , 197002 },
502 { 64481179 , 197444 },
503 { 65121061 , 197886 },
504 { 65765563 , 198328 },
505 { 66414705 , 198770 },
506 { 67068508 , 199213 },
507 { 67726992 , 199655 },
508 { 68390177 , 200098 },
509 { 69058085 , 200540 },
510 { 69730735 , 200983 },
511 { 70408147 , 201426 },
512 { 71090343 , 201869 },
513 { 71777343 , 202312 },
514 { 72469168 , 202755 },
515 { 73165837 , 203199 },
516 { 73867373 , 203642 },
517 { 74573795 , 204086 },
518 { 75285124 , 204529 },
519 { 76001380 , 204973 },
520 { 76722586 , 205417 },
521 { 77448761 , 205861 },
522 { 78179926 , 206306 },
523 { 78916102 , 206750 },
524 { 79657310 , 207194 },
525 { 80403571 , 207639 },
526 { 81154906 , 208084 },
527 { 81911335 , 208529 },
528 { 82672880 , 208974 },
529 { 83439562 , 209419 },
530 { 84211402 , 209864 },
531 { 84988421 , 210309 },
532 { 85770640 , 210755 },
533 { 86558080 , 211201 },
534 { 87350762 , 211647 },
535 { 88148708 , 212093 },
536 { 88951938 , 212539 },
537 { 89760475 , 212985 },
538 { 90574339 , 213432 },
539 { 91393551 , 213878 },
540 { 92218133 , 214325 },
541 { 93048107 , 214772 },
542 { 93883493 , 215219 },
543 { 94724314 , 215666 },
544 { 95570590 , 216114 },
545 { 96422343 , 216561 },
546 { 97279594 , 217009 },
547 { 98142366 , 217457 },
548 { 99010679 , 217905 },
549 { 99884556 , 218353 },
550 { 100764018 , 218801 },
551 { 101649086 , 219250 },
552 { 102539782 , 219698 },
553 { 103436128 , 220147 },
554 { 104338146 , 220596 },
555 { 105245857 , 221046 },
556 { 106159284 , 221495 },
557 { 107078448 , 221945 },
558 { 108003370 , 222394 },
559 { 108934074 , 222844 },
560 { 109870580 , 223294 },
561 { 110812910 , 223745 },
562 { 111761087 , 224195 },
563 { 112715133 , 224646 },
564 { 113675069 , 225097 },
565 { 114640918 , 225548 },
566 { 115612702 , 225999 },
567 { 116590442 , 226450 },
568 { 117574162 , 226902 },
569 { 118563882 , 227353 },
570 { 119559626 , 227805 },
571 { 120561415 , 228258 },
572 { 121569272 , 228710 },
573 { 122583219 , 229162 },
574 { 123603278 , 229615 },
575 { 124629471 , 230068 },
576 { 125661822 , 230521 },
577 { 126700352 , 230974 },
578 { 127745083 , 231428 },
579 { 128796039 , 231882 },
580 { 129853241 , 232336 },
581 { 130916713 , 232790 },
582 { 131986475 , 233244 },
583 { 133062553 , 233699 },
584 { 134144966 , 234153 },
585 { 135233739 , 234608 },
586 { 136328894 , 235064 },
587 { 137430453 , 235519 },
588 { 138538440 , 235975 },
589 { 139652876 , 236430 },
590 { 140773786 , 236886 },
591 { 141901190 , 237343 },
592 { 143035113 , 237799 },
593 { 144175576 , 238256 },
594 { 145322604 , 238713 },
595 { 146476218 , 239170 },
596 { 147636442 , 239627 },
597 { 148803298 , 240085 },
598 { 149976809 , 240542 },
599 { 151156999 , 241000 },
600 { 152343890 , 241459 },
601 { 153537506 , 241917 },
602 { 154737869 , 242376 },
603 { 155945002 , 242835 },
604 { 157158929 , 243294 },
605 { 158379673 , 243753 },
606 { 159607257 , 244213 },
607 { 160841704 , 244673 },
608 { 162083037 , 245133 },
609 { 163331279 , 245593 },
610 { 164586455 , 246054 },
611 { 165848586 , 246514 },
612 { 167117696 , 246975 },
613 { 168393810 , 247437 },
614 { 169676949 , 247898 },
615 { 170967138 , 248360 },
616 { 172264399 , 248822 },
617 { 173568757 , 249284 },
618 { 174880235 , 249747 },
619 { 176198856 , 250209 },
620 { 177524643 , 250672 },
621 { 178857621 , 251136 },
622 { 180197813 , 251599 },
623 { 181545242 , 252063 },
624 { 182899933 , 252527 },
625 { 184261908 , 252991 },
626 { 185631191 , 253456 },
627 { 187007807 , 253920 },
628 { 188391778 , 254385 },
629 { 189783129 , 254851 },
630 { 191181884 , 255316 },
631 { 192588065 , 255782 },
632 { 194001698 , 256248 },
633 { 195422805 , 256714 },
634 { 196851411 , 257181 },
635 { 198287540 , 257648 },
636 { 199731215 , 258115 },
637 { 201182461 , 258582 },
638 { 202641302 , 259050 },
639 { 204107760 , 259518 },
640 { 205581862 , 259986 },
641 { 207063630 , 260454 },
642 { 208553088 , 260923 },
643 { 210050262 , 261392 },
644 { 211555174 , 261861 },
645 { 213067849 , 262331 },
646 { 214588312 , 262800 },
647 { 216116586 , 263270 },
648 { 217652696 , 263741 },
649 { 219196666 , 264211 },
650 { 220748520 , 264682 },
651 { 222308282 , 265153 },
652 { 223875978 , 265625 },
653 { 225451630 , 266097 },
654 { 227035265 , 266569 },
655 { 228626905 , 267041 },
656 { 230226576 , 267514 },
657 { 231834302 , 267986 },
658 { 233450107 , 268460 },
659 { 235074016 , 268933 },
660 { 236706054 , 269407 },
661 { 238346244 , 269881 },
662 { 239994613 , 270355 },
663 { 241651183 , 270830 },
664 { 243315981 , 271305 }
667 /* Calculate the send rate as per section 3.1 of RFC3448
669 Returns send rate in bytes per second
671 Integer maths and lookups are used as not allowed floating point in kernel
673 The function for Xcalc as per section 3.1 of RFC3448 is:
676 -------------------------------------------------------------
677 R*sqrt(2*b*p/3) + (t_RTO * (3*sqrt(3*b*p/8) * p * (1+32*p^2)))
680 X is the trasmit rate in bytes/second
681 s is the packet size in bytes
682 R is the round trip time in seconds
683 p is the loss event rate, between 0 and 1.0, of the number of loss events
684 as a fraction of the number of packets transmitted
685 t_RTO is the TCP retransmission timeout value in seconds
686 b is the number of packets acknowledged by a single TCP acknowledgement
688 we can assume that b = 1 and t_RTO is 4 * R. With this the equation becomes:
691 -----------------------------------------------------------------------
692 R * sqrt(2 * p / 3) + (12 * R * (sqrt(3 * p / 8) * p * (1 + 32 * p^2)))
695 which we can break down into:
701 where f(p) = sqrt(2 * p / 3) + (12 * sqrt(3 * p / 8) * p * (1 + 32 * p * p))
706 p - loss rate (decimal fraction multiplied by 1,000,000)
708 Returns Xcalc in bytes per second
710 DON'T alter this code unless you run test cases against it as the code
711 has been manipulated to stop underflow/overlow.
714 static u32 ccid3_calc_x(u16 s, u32 R, u32 p)
721 index = (p / (CALCX_SPLIT / CALCX_ARRSIZE)) - 1;
723 index = (p / (1000000 / CALCX_ARRSIZE)) - 1;
726 /* p should be 0 unless there is a bug in my code */
730 R = 1; /* RTT can't be zero or else divide by zero */
732 BUG_ON(index >= CALCX_ARRSIZE);
734 if (p >= CALCX_SPLIT)
735 f = calcx_lookup[index][0];
737 f = calcx_lookup[index][1];
739 tmp1 = ((u64)s * 100000000);
740 tmp2 = ((u64)R * (u64)f);
743 /* don't alter above math unless you test due to overflow on 32 bit */
748 /* Calculate new t_ipi (inter packet interval) by t_ipi = s / X_inst */
749 static inline void ccid3_calc_new_t_ipi(struct ccid3_hc_tx_sock *hctx)
751 if (hctx->ccid3hctx_state == TFRC_SSTATE_NO_FBACK)
753 /* if no feedback spec says t_ipi is 1 second (set elsewhere and then
754 * doubles after every no feedback timer (separate function) */
756 if (hctx->ccid3hctx_x < 10) {
757 ccid3_pr_debug("ccid3_calc_new_t_ipi - ccid3hctx_x < 10\n");
758 hctx->ccid3hctx_x = 10;
760 hctx->ccid3hctx_t_ipi = (hctx->ccid3hctx_s * 100000)
761 / (hctx->ccid3hctx_x / 10);
762 /* reason for above maths with 10 in there is to avoid 32 bit
763 * overflow for jumbo packets */
767 /* Calculate new delta by delta = min(t_ipi / 2, t_gran / 2) */
768 static inline void ccid3_calc_new_delta(struct ccid3_hc_tx_sock *hctx)
770 hctx->ccid3hctx_delta = min_t(u32, hctx->ccid3hctx_t_ipi / 2,
771 TFRC_OPSYS_HALF_TIME_GRAN);
778 * x_calc = calcX(s, R, p);
779 * X = max(min(X_calc, 2 * X_recv), s / t_mbi);
781 * If (now - tld >= R)
782 * X = max(min(2 * X, 2 * X_recv), s / R);
785 static void ccid3_hc_tx_update_x(struct sock *sk)
787 struct dccp_sock *dp = dccp_sk(sk);
788 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
790 /* To avoid large error in calcX */
791 if (hctx->ccid3hctx_p >= TFRC_SMALLEST_P) {
792 hctx->ccid3hctx_x_calc = ccid3_calc_x(hctx->ccid3hctx_s,
795 hctx->ccid3hctx_x = max_t(u32, min_t(u32, hctx->ccid3hctx_x_calc,
796 2 * hctx->ccid3hctx_x_recv),
798 TFRC_MAX_BACK_OFF_TIME));
802 do_gettimeofday(&now);
803 if (timeval_delta(&now, &hctx->ccid3hctx_t_ld) >=
804 hctx->ccid3hctx_rtt) {
805 /* Avoid divide by zero below */
806 const u32 rtt = max_t(u32, hctx->ccid3hctx_rtt, 10);
808 hctx->ccid3hctx_x = max_t(u32, min_t(u32, 2 * hctx->ccid3hctx_x_recv,
809 2 * hctx->ccid3hctx_x),
810 ((hctx->ccid3hctx_s * 100000) /
812 /* Using 100000 and 10 to avoid 32 bit overflow for jumbo frames */
813 hctx->ccid3hctx_t_ld = now;
817 if (hctx->ccid3hctx_x == 0) {
818 ccid3_pr_debug("ccid3hctx_x = 0!\n");
819 hctx->ccid3hctx_x = 1;
823 static void ccid3_hc_tx_no_feedback_timer(unsigned long data)
825 struct sock *sk = (struct sock *)data;
826 struct dccp_sock *dp = dccp_sk(sk);
827 unsigned long next_tmout = 0;
828 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
832 if (sock_owned_by_user(sk)) {
833 /* Try again later. */
834 /* XXX: set some sensible MIB */
835 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
840 ccid3_pr_debug("%s, sk=%p, state=%s\n", dccp_role(sk), sk,
841 ccid3_tx_state_name(hctx->ccid3hctx_state));
843 if (hctx->ccid3hctx_x < 10) {
844 ccid3_pr_debug("TFRC_SSTATE_NO_FBACK ccid3hctx_x < 10\n");
845 hctx->ccid3hctx_x = 10;
848 switch (hctx->ccid3hctx_state) {
849 case TFRC_SSTATE_TERM:
851 case TFRC_SSTATE_NO_FBACK:
852 /* Halve send rate */
853 hctx->ccid3hctx_x /= 2;
854 if (hctx->ccid3hctx_x <
855 (hctx->ccid3hctx_s / TFRC_MAX_BACK_OFF_TIME))
856 hctx->ccid3hctx_x = (hctx->ccid3hctx_s /
857 TFRC_MAX_BACK_OFF_TIME);
859 ccid3_pr_debug("%s, sk=%p, state=%s, updated tx rate to %d "
862 ccid3_tx_state_name(hctx->ccid3hctx_state),
864 next_tmout = max_t(u32, 2 * (hctx->ccid3hctx_s * 100000) / (hctx->ccid3hctx_x / 10),
865 TFRC_INITIAL_TIMEOUT);
866 /* do above maths with 100000 and 10 to prevent overflow on 32 bit */
868 * FIXME - not sure above calculation is correct. See section
869 * 5 of CCID3 11 should adjust tx_t_ipi and double that to
873 case TFRC_SSTATE_FBACK:
875 * Check if IDLE since last timeout and recv rate is less than
878 rtt = hctx->ccid3hctx_rtt;
881 /* stop divide by zero below */
882 if (!hctx->ccid3hctx_idle ||
883 (hctx->ccid3hctx_x_recv >= 4 * (hctx->ccid3hctx_s * 100000) / (rtt / 10))) {
884 ccid3_pr_debug("%s, sk=%p, state=%s, not idle\n",
886 ccid3_tx_state_name(hctx->ccid3hctx_state));
887 /* Halve sending rate */
889 /* If (X_calc > 2 * X_recv)
890 * X_recv = max(X_recv / 2, s / (2 * t_mbi));
892 * X_recv = X_calc / 4;
894 BUG_ON(hctx->ccid3hctx_p >= TFRC_SMALLEST_P &&
895 hctx->ccid3hctx_x_calc == 0);
897 /* check also if p is zero -> x_calc is infinity? */
898 if (hctx->ccid3hctx_p < TFRC_SMALLEST_P ||
899 hctx->ccid3hctx_x_calc > 2 * hctx->ccid3hctx_x_recv)
900 hctx->ccid3hctx_x_recv = max_t(u32, hctx->ccid3hctx_x_recv / 2,
901 hctx->ccid3hctx_s / (2 * TFRC_MAX_BACK_OFF_TIME));
903 hctx->ccid3hctx_x_recv = hctx->ccid3hctx_x_calc / 4;
905 /* Update sending rate */
906 ccid3_hc_tx_update_x(sk);
908 if (hctx->ccid3hctx_x == 0) {
909 ccid3_pr_debug("TFRC_SSTATE_FBACK ccid3hctx_x = 0!\n");
910 hctx->ccid3hctx_x = 10;
912 /* Schedule no feedback timer to expire in max(4 * R, 2 * s / X) */
913 next_tmout = max_t(u32, hctx->ccid3hctx_t_rto,
914 2 * (hctx->ccid3hctx_s * 100000) / (hctx->ccid3hctx_x / 10));
917 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
918 __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
923 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
924 jiffies + max_t(u32, 1, usecs_to_jiffies(next_tmout)));
925 hctx->ccid3hctx_idle = 1;
931 static int ccid3_hc_tx_send_packet(struct sock *sk,
932 struct sk_buff *skb, int len)
934 struct dccp_sock *dp = dccp_sk(sk);
935 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
936 struct dccp_tx_hist_entry *new_packet;
941 /* Check if pure ACK or Terminating*/
944 * XXX: We only call this function for DATA and DATAACK, on, these
945 * packets can have zero length, but why the comment about "pure ACK"?
947 if (hctx == NULL || len == 0 ||
948 hctx->ccid3hctx_state == TFRC_SSTATE_TERM)
951 /* See if last packet allocated was not sent */
952 new_packet = dccp_tx_hist_head(&hctx->ccid3hctx_hist);
953 if (new_packet == NULL || new_packet->dccphtx_sent) {
954 new_packet = dccp_tx_hist_entry_new(ccid3_tx_hist,
958 if (new_packet == NULL) {
959 ccid3_pr_debug("%s, sk=%p, not enough mem to add "
960 "to history, send refused\n",
965 dccp_tx_hist_add_entry(&hctx->ccid3hctx_hist, new_packet);
968 do_gettimeofday(&now);
970 switch (hctx->ccid3hctx_state) {
971 case TFRC_SSTATE_NO_SENT:
972 ccid3_pr_debug("%s, sk=%p, first packet(%llu)\n",
973 dccp_role(sk), sk, dp->dccps_gss);
975 hctx->ccid3hctx_no_feedback_timer.function = ccid3_hc_tx_no_feedback_timer;
976 hctx->ccid3hctx_no_feedback_timer.data = (unsigned long)sk;
977 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
978 jiffies + usecs_to_jiffies(TFRC_INITIAL_TIMEOUT));
979 hctx->ccid3hctx_last_win_count = 0;
980 hctx->ccid3hctx_t_last_win_count = now;
981 ccid3_hc_tx_set_state(sk, TFRC_SSTATE_NO_FBACK);
982 hctx->ccid3hctx_t_ipi = TFRC_INITIAL_TIMEOUT;
984 /* Set nominal send time for initial packet */
985 hctx->ccid3hctx_t_nom = now;
986 timeval_add_usecs(&hctx->ccid3hctx_t_nom,
987 hctx->ccid3hctx_t_ipi);
988 ccid3_calc_new_delta(hctx);
991 case TFRC_SSTATE_NO_FBACK:
992 case TFRC_SSTATE_FBACK:
993 delay = (timeval_delta(&now, &hctx->ccid3hctx_t_nom) -
994 hctx->ccid3hctx_delta);
995 ccid3_pr_debug("send_packet delay=%ld\n", delay);
997 /* divide by -1000 is to convert to ms and get sign right */
998 rc = delay > 0 ? delay : 0;
1001 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1002 __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
1008 /* Can we send? if so add options and add to packet history */
1010 new_packet->dccphtx_ccval =
1011 DCCP_SKB_CB(skb)->dccpd_ccval =
1012 hctx->ccid3hctx_last_win_count;
1017 static void ccid3_hc_tx_packet_sent(struct sock *sk, int more, int len)
1019 struct dccp_sock *dp = dccp_sk(sk);
1020 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1023 BUG_ON(hctx == NULL);
1025 if (hctx->ccid3hctx_state == TFRC_SSTATE_TERM) {
1026 ccid3_pr_debug("%s, sk=%p, while state is TFRC_SSTATE_TERM!\n",
1031 do_gettimeofday(&now);
1033 /* check if we have sent a data packet */
1035 unsigned long quarter_rtt;
1036 struct dccp_tx_hist_entry *packet;
1038 packet = dccp_tx_hist_head(&hctx->ccid3hctx_hist);
1039 if (packet == NULL) {
1040 printk(KERN_CRIT "%s: packet doesn't exists in "
1041 "history!\n", __FUNCTION__);
1044 if (packet->dccphtx_sent) {
1045 printk(KERN_CRIT "%s: no unsent packet in history!\n",
1049 packet->dccphtx_tstamp = now;
1050 packet->dccphtx_seqno = dp->dccps_gss;
1052 * Check if win_count have changed
1053 * Algorithm in "8.1. Window Counter Valuer" in
1054 * draft-ietf-dccp-ccid3-11.txt
1056 quarter_rtt = timeval_delta(&now, &hctx->ccid3hctx_t_last_win_count) /
1057 (hctx->ccid3hctx_rtt / 4);
1058 if (quarter_rtt > 0) {
1059 hctx->ccid3hctx_t_last_win_count = now;
1060 hctx->ccid3hctx_last_win_count = (hctx->ccid3hctx_last_win_count +
1061 min_t(unsigned long, quarter_rtt, 5)) % 16;
1062 ccid3_pr_debug("%s, sk=%p, window changed from "
1065 packet->dccphtx_ccval,
1066 hctx->ccid3hctx_last_win_count);
1069 hctx->ccid3hctx_idle = 0;
1070 packet->dccphtx_rtt = hctx->ccid3hctx_rtt;
1071 packet->dccphtx_sent = 1;
1073 ccid3_pr_debug("%s, sk=%p, seqno=%llu NOT inserted!\n",
1074 dccp_role(sk), sk, dp->dccps_gss);
1076 switch (hctx->ccid3hctx_state) {
1077 case TFRC_SSTATE_NO_SENT:
1078 /* if first wasn't pure ack */
1080 printk(KERN_CRIT "%s: %s, First packet sent is noted "
1081 "as a data packet\n",
1082 __FUNCTION__, dccp_role(sk));
1084 case TFRC_SSTATE_NO_FBACK:
1085 case TFRC_SSTATE_FBACK:
1087 hctx->ccid3hctx_t_nom = now;
1088 ccid3_calc_new_t_ipi(hctx);
1089 ccid3_calc_new_delta(hctx);
1090 timeval_add_usecs(&hctx->ccid3hctx_t_nom,
1091 hctx->ccid3hctx_t_ipi);
1095 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1096 __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
1102 static void ccid3_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
1104 struct dccp_sock *dp = dccp_sk(sk);
1105 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1106 struct ccid3_options_received *opt_recv;
1107 struct dccp_tx_hist_entry *packet;
1108 unsigned long next_tmout;
1117 if (hctx->ccid3hctx_state == TFRC_SSTATE_TERM) {
1118 ccid3_pr_debug("%s, sk=%p, received a packet when "
1119 "terminating!\n", dccp_role(sk), sk);
1123 /* we are only interested in ACKs */
1124 if (!(DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_ACK ||
1125 DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_DATAACK))
1128 opt_recv = &hctx->ccid3hctx_options_received;
1130 t_elapsed = dp->dccps_options_received.dccpor_elapsed_time;
1131 x_recv = opt_recv->ccid3or_receive_rate;
1132 pinv = opt_recv->ccid3or_loss_event_rate;
1134 switch (hctx->ccid3hctx_state) {
1135 case TFRC_SSTATE_NO_SENT:
1136 /* FIXME: what to do here? */
1138 case TFRC_SSTATE_NO_FBACK:
1139 case TFRC_SSTATE_FBACK:
1140 /* Calculate new round trip sample by
1141 * R_sample = (now - t_recvdata) - t_delay */
1142 /* get t_recvdata from history */
1143 packet = dccp_tx_hist_find_entry(&hctx->ccid3hctx_hist,
1144 DCCP_SKB_CB(skb)->dccpd_ack_seq);
1145 if (packet == NULL) {
1146 ccid3_pr_debug("%s, sk=%p, seqno %llu(%s) does't "
1147 "exist in history!\n",
1149 DCCP_SKB_CB(skb)->dccpd_ack_seq,
1150 dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type));
1155 r_sample = timeval_now_delta(&packet->dccphtx_tstamp);
1157 // r_sample -= usecs_to_jiffies(t_elapsed * 10);
1159 /* Update RTT estimate by
1160 * If (No feedback recv)
1163 * R = q * R + (1 - q) * R_sample;
1165 * q is a constant, RFC 3448 recomments 0.9
1167 if (hctx->ccid3hctx_state == TFRC_SSTATE_NO_FBACK) {
1168 ccid3_hc_tx_set_state(sk, TFRC_SSTATE_FBACK);
1169 hctx->ccid3hctx_rtt = r_sample;
1171 hctx->ccid3hctx_rtt = (hctx->ccid3hctx_rtt * 9) / 10 +
1175 * XXX: this is to avoid a division by zero in ccid3_hc_tx_packet_sent
1176 * implemention of the new window count.
1178 if (hctx->ccid3hctx_rtt < 4)
1179 hctx->ccid3hctx_rtt = 4;
1181 ccid3_pr_debug("%s, sk=%p, New RTT estimate=%uus, "
1182 "r_sample=%us\n", dccp_role(sk), sk,
1183 hctx->ccid3hctx_rtt, r_sample);
1185 /* Update timeout interval */
1186 hctx->ccid3hctx_t_rto = max_t(u32, 4 * hctx->ccid3hctx_rtt,
1189 /* Update receive rate */
1190 hctx->ccid3hctx_x_recv = x_recv;/* X_recv in bytes per sec */
1192 /* Update loss event rate */
1193 if (pinv == ~0 || pinv == 0)
1194 hctx->ccid3hctx_p = 0;
1196 hctx->ccid3hctx_p = 1000000 / pinv;
1198 if (hctx->ccid3hctx_p < TFRC_SMALLEST_P) {
1199 hctx->ccid3hctx_p = TFRC_SMALLEST_P;
1200 ccid3_pr_debug("%s, sk=%p, Smallest p used!\n",
1205 /* unschedule no feedback timer */
1206 sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer);
1208 /* Update sending rate */
1209 ccid3_hc_tx_update_x(sk);
1211 /* Update next send time */
1212 timeval_sub_usecs(&hctx->ccid3hctx_t_nom,
1213 hctx->ccid3hctx_t_ipi);
1214 ccid3_calc_new_t_ipi(hctx);
1215 timeval_add_usecs(&hctx->ccid3hctx_t_nom,
1216 hctx->ccid3hctx_t_ipi);
1217 ccid3_calc_new_delta(hctx);
1219 /* remove all packets older than the one acked from history */
1220 dccp_tx_hist_purge_older(ccid3_tx_hist,
1221 &hctx->ccid3hctx_hist, packet);
1223 if (hctx->ccid3hctx_x < 10) {
1224 ccid3_pr_debug("ccid3_hc_tx_packet_recv hctx_x < 10\n");
1225 hctx->ccid3hctx_x = 10;
1227 /* to prevent divide by zero below */
1230 * Schedule no feedback timer to expire in
1231 * max(4 * R, 2 * s / X)
1233 next_tmout = max(hctx->ccid3hctx_t_rto,
1234 (2 * (hctx->ccid3hctx_s * 100000) /
1235 (hctx->ccid3hctx_x / 10)));
1236 /* maths with 100000 and 10 is to prevent overflow with 32 bit */
1238 ccid3_pr_debug("%s, sk=%p, Scheduled no feedback timer to "
1239 "expire in %lu jiffies (%luus)\n",
1241 usecs_to_jiffies(next_tmout), next_tmout);
1243 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
1244 jiffies + max_t(u32, 1, usecs_to_jiffies(next_tmout)));
1247 hctx->ccid3hctx_idle = 1;
1250 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1251 __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
1257 static void ccid3_hc_tx_insert_options(struct sock *sk, struct sk_buff *skb)
1259 const struct dccp_sock *dp = dccp_sk(sk);
1260 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1262 if (hctx == NULL || !(sk->sk_state == DCCP_OPEN ||
1263 sk->sk_state == DCCP_PARTOPEN))
1266 DCCP_SKB_CB(skb)->dccpd_ccval = hctx->ccid3hctx_last_win_count;
1269 static int ccid3_hc_tx_parse_options(struct sock *sk, unsigned char option,
1270 unsigned char len, u16 idx,
1271 unsigned char *value)
1274 struct dccp_sock *dp = dccp_sk(sk);
1275 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1276 struct ccid3_options_received *opt_recv;
1281 opt_recv = &hctx->ccid3hctx_options_received;
1283 if (opt_recv->ccid3or_seqno != dp->dccps_gsr) {
1284 opt_recv->ccid3or_seqno = dp->dccps_gsr;
1285 opt_recv->ccid3or_loss_event_rate = ~0;
1286 opt_recv->ccid3or_loss_intervals_idx = 0;
1287 opt_recv->ccid3or_loss_intervals_len = 0;
1288 opt_recv->ccid3or_receive_rate = 0;
1292 case TFRC_OPT_LOSS_EVENT_RATE:
1294 ccid3_pr_debug("%s, sk=%p, invalid len for "
1295 "TFRC_OPT_LOSS_EVENT_RATE\n",
1299 opt_recv->ccid3or_loss_event_rate = ntohl(*(u32 *)value);
1300 ccid3_pr_debug("%s, sk=%p, LOSS_EVENT_RATE=%u\n",
1302 opt_recv->ccid3or_loss_event_rate);
1305 case TFRC_OPT_LOSS_INTERVALS:
1306 opt_recv->ccid3or_loss_intervals_idx = idx;
1307 opt_recv->ccid3or_loss_intervals_len = len;
1308 ccid3_pr_debug("%s, sk=%p, LOSS_INTERVALS=(%u, %u)\n",
1310 opt_recv->ccid3or_loss_intervals_idx,
1311 opt_recv->ccid3or_loss_intervals_len);
1313 case TFRC_OPT_RECEIVE_RATE:
1315 ccid3_pr_debug("%s, sk=%p, invalid len for "
1316 "TFRC_OPT_RECEIVE_RATE\n",
1320 opt_recv->ccid3or_receive_rate = ntohl(*(u32 *)value);
1321 ccid3_pr_debug("%s, sk=%p, RECEIVE_RATE=%u\n",
1323 opt_recv->ccid3or_receive_rate);
1331 static int ccid3_hc_tx_init(struct sock *sk)
1333 struct dccp_sock *dp = dccp_sk(sk);
1334 struct ccid3_hc_tx_sock *hctx;
1336 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1338 hctx = dp->dccps_hc_tx_ccid_private = kmalloc(sizeof(*hctx),
1343 memset(hctx, 0, sizeof(*hctx));
1345 if (dp->dccps_avg_packet_size >= TFRC_MIN_PACKET_SIZE &&
1346 dp->dccps_avg_packet_size <= TFRC_MAX_PACKET_SIZE)
1347 hctx->ccid3hctx_s = (u16)dp->dccps_avg_packet_size;
1349 hctx->ccid3hctx_s = TFRC_STD_PACKET_SIZE;
1351 /* Set transmission rate to 1 packet per second */
1352 hctx->ccid3hctx_x = hctx->ccid3hctx_s;
1353 /* See ccid3_hc_tx_packet_sent win_count calculatation */
1354 hctx->ccid3hctx_rtt = 4;
1355 hctx->ccid3hctx_t_rto = USEC_PER_SEC;
1356 hctx->ccid3hctx_state = TFRC_SSTATE_NO_SENT;
1357 INIT_LIST_HEAD(&hctx->ccid3hctx_hist);
1358 init_timer(&hctx->ccid3hctx_no_feedback_timer);
1363 static void ccid3_hc_tx_exit(struct sock *sk)
1365 struct dccp_sock *dp = dccp_sk(sk);
1366 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1368 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1369 BUG_ON(hctx == NULL);
1371 ccid3_hc_tx_set_state(sk, TFRC_SSTATE_TERM);
1372 sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer);
1374 /* Empty packet history */
1375 dccp_tx_hist_purge(ccid3_tx_hist, &hctx->ccid3hctx_hist);
1377 kfree(dp->dccps_hc_tx_ccid_private);
1378 dp->dccps_hc_tx_ccid_private = NULL;
1382 * RX Half Connection methods
1385 /* TFRC receiver states */
1386 enum ccid3_hc_rx_states {
1387 TFRC_RSTATE_NO_DATA = 1,
1389 TFRC_RSTATE_TERM = 127,
1393 static const char *ccid3_rx_state_name(enum ccid3_hc_rx_states state)
1395 static char *ccid3_rx_state_names[] = {
1396 [TFRC_RSTATE_NO_DATA] = "NO_DATA",
1397 [TFRC_RSTATE_DATA] = "DATA",
1398 [TFRC_RSTATE_TERM] = "TERM",
1401 return ccid3_rx_state_names[state];
1405 static inline void ccid3_hc_rx_set_state(struct sock *sk,
1406 enum ccid3_hc_rx_states state)
1408 struct dccp_sock *dp = dccp_sk(sk);
1409 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1410 enum ccid3_hc_rx_states oldstate = hcrx->ccid3hcrx_state;
1412 ccid3_pr_debug("%s(%p) %-8.8s -> %s\n",
1413 dccp_role(sk), sk, ccid3_rx_state_name(oldstate),
1414 ccid3_rx_state_name(state));
1415 WARN_ON(state == oldstate);
1416 hcrx->ccid3hcrx_state = state;
1419 static int ccid3_hc_rx_add_hist(struct sock *sk,
1420 struct dccp_rx_hist_entry *packet)
1422 struct dccp_sock *dp = dccp_sk(sk);
1423 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1424 struct dccp_rx_hist_entry *entry, *next, *iter;
1427 iter = dccp_rx_hist_head(&hcrx->ccid3hcrx_hist);
1429 dccp_rx_hist_add_entry(&hcrx->ccid3hcrx_hist, packet);
1431 const u64 seqno = packet->dccphrx_seqno;
1433 if (after48(seqno, iter->dccphrx_seqno))
1434 dccp_rx_hist_add_entry(&hcrx->ccid3hcrx_hist, packet);
1436 if (dccp_rx_hist_entry_data_packet(iter))
1439 list_for_each_entry_continue(iter,
1440 &hcrx->ccid3hcrx_hist,
1442 if (after48(seqno, iter->dccphrx_seqno)) {
1443 dccp_rx_hist_add_entry(&iter->dccphrx_node,
1448 if (dccp_rx_hist_entry_data_packet(iter))
1451 if (num_later == TFRC_RECV_NUM_LATE_LOSS) {
1452 dccp_rx_hist_entry_delete(ccid3_rx_hist,
1454 ccid3_pr_debug("%s, sk=%p, packet"
1455 "(%llu) already lost!\n",
1462 if (num_later < TFRC_RECV_NUM_LATE_LOSS)
1463 dccp_rx_hist_add_entry(&hcrx->ccid3hcrx_hist,
1466 * FIXME: else what? should we destroy the packet
1474 * Trim history (remove all packets after the NUM_LATE_LOSS + 1
1477 num_later = TFRC_RECV_NUM_LATE_LOSS + 1;
1479 if (!list_empty(&hcrx->ccid3hcrx_loss_interval_hist)) {
1480 list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
1482 if (num_later == 0) {
1483 list_del_init(&entry->dccphrx_node);
1484 dccp_rx_hist_entry_delete(ccid3_rx_hist, entry);
1485 } else if (dccp_rx_hist_entry_data_packet(entry))
1490 u8 win_count = 0; /* Not needed, but lets shut up gcc */
1493 * We have no loss interval history so we need at least one
1494 * rtt:s of data packets to approximate rtt.
1496 list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
1498 if (num_later == 0) {
1502 /* OK, find next data packet */
1507 /* OK, find next data packet */
1509 win_count = entry->dccphrx_ccval;
1512 tmp = win_count - entry->dccphrx_ccval;
1514 tmp += TFRC_WIN_COUNT_LIMIT;
1515 if (tmp > TFRC_WIN_COUNT_PER_RTT + 1) {
1517 * We have found a packet older
1518 * than one rtt remove the rest
1521 } else /* OK, find next data packet */
1525 list_del_init(&entry->dccphrx_node);
1526 dccp_rx_hist_entry_delete(ccid3_rx_hist,
1530 } else if (dccp_rx_hist_entry_data_packet(entry))
1538 static void ccid3_hc_rx_send_feedback(struct sock *sk)
1540 struct dccp_sock *dp = dccp_sk(sk);
1541 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1542 struct dccp_rx_hist_entry *packet;
1545 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1547 do_gettimeofday(&now);
1549 switch (hcrx->ccid3hcrx_state) {
1550 case TFRC_RSTATE_NO_DATA:
1551 hcrx->ccid3hcrx_x_recv = 0;
1553 case TFRC_RSTATE_DATA: {
1554 const u32 delta = timeval_delta(&now,
1555 &hcrx->ccid3hcrx_tstamp_last_feedback);
1557 hcrx->ccid3hcrx_x_recv = (hcrx->ccid3hcrx_bytes_recv *
1559 if (likely(delta > 1))
1560 hcrx->ccid3hcrx_x_recv /= delta;
1564 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1565 __FUNCTION__, dccp_role(sk), sk, hcrx->ccid3hcrx_state);
1570 packet = dccp_rx_hist_find_data_packet(&hcrx->ccid3hcrx_hist);
1571 if (packet == NULL) {
1572 printk(KERN_CRIT "%s: %s, sk=%p, no data packet in history!\n",
1573 __FUNCTION__, dccp_role(sk), sk);
1578 hcrx->ccid3hcrx_tstamp_last_feedback = now;
1579 hcrx->ccid3hcrx_last_counter = packet->dccphrx_ccval;
1580 hcrx->ccid3hcrx_seqno_last_counter = packet->dccphrx_seqno;
1581 hcrx->ccid3hcrx_bytes_recv = 0;
1583 /* Convert to multiples of 10us */
1584 hcrx->ccid3hcrx_elapsed_time =
1585 timeval_delta(&now, &packet->dccphrx_tstamp) / 10;
1586 if (hcrx->ccid3hcrx_p == 0)
1587 hcrx->ccid3hcrx_pinv = ~0;
1589 hcrx->ccid3hcrx_pinv = 1000000 / hcrx->ccid3hcrx_p;
1593 static void ccid3_hc_rx_insert_options(struct sock *sk, struct sk_buff *skb)
1595 const struct dccp_sock *dp = dccp_sk(sk);
1597 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1599 if (hcrx == NULL || !(sk->sk_state == DCCP_OPEN ||
1600 sk->sk_state == DCCP_PARTOPEN))
1603 DCCP_SKB_CB(skb)->dccpd_ccval = hcrx->ccid3hcrx_last_counter;
1605 if (dccp_packet_without_ack(skb))
1608 if (hcrx->ccid3hcrx_elapsed_time != 0)
1609 dccp_insert_option_elapsed_time(sk, skb,
1610 hcrx->ccid3hcrx_elapsed_time);
1611 dccp_insert_option_timestamp(sk, skb);
1612 x_recv = htonl(hcrx->ccid3hcrx_x_recv);
1613 pinv = htonl(hcrx->ccid3hcrx_pinv);
1614 dccp_insert_option(sk, skb, TFRC_OPT_LOSS_EVENT_RATE,
1615 &pinv, sizeof(pinv));
1616 dccp_insert_option(sk, skb, TFRC_OPT_RECEIVE_RATE,
1617 &x_recv, sizeof(x_recv));
1620 /* Weights used to calculate loss event rate */
1622 * These are integers as per section 8 of RFC3448. We can then divide by 4 *
1625 static const int ccid3_hc_rx_w[TFRC_RECV_IVAL_F_LENGTH] = {
1626 4, 4, 4, 4, 3, 2, 1, 1,
1630 * args: fvalue - function value to match
1631 * returns: p closest to that value
1633 * both fvalue and p are multiplied by 1,000,000 to use ints
1635 static u32 calcx_reverse_lookup(u32 fvalue) {
1639 if (fvalue < calcx_lookup[0][1])
1641 if (fvalue <= calcx_lookup[CALCX_ARRSIZE-1][1])
1643 else if (fvalue > calcx_lookup[CALCX_ARRSIZE-1][0])
1647 while (fvalue > calcx_lookup[ctr][small])
1650 return (CALCX_SPLIT * ctr / CALCX_ARRSIZE);
1652 return (1000000 * ctr / CALCX_ARRSIZE) ;
1655 /* calculate first loss interval
1657 * returns estimated loss interval in usecs */
1659 static u32 ccid3_hc_rx_calc_first_li(struct sock *sk)
1661 struct dccp_sock *dp = dccp_sk(sk);
1662 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1663 struct dccp_rx_hist_entry *entry, *next, *tail = NULL;
1664 u32 rtt, delta, x_recv, fval, p, tmp2;
1665 struct timeval tstamp = { 0, };
1671 list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
1673 if (dccp_rx_hist_entry_data_packet(entry)) {
1678 tstamp = entry->dccphrx_tstamp;
1679 win_count = entry->dccphrx_ccval;
1683 interval = win_count - entry->dccphrx_ccval;
1685 interval += TFRC_WIN_COUNT_LIMIT;
1694 printk(KERN_CRIT "%s: %s, sk=%p, packet history contains no "
1696 __FUNCTION__, dccp_role(sk), sk);
1700 if (interval == 0) {
1701 ccid3_pr_debug("%s, sk=%p, Could not find a win_count "
1702 "interval > 0. Defaulting to 1\n",
1707 rtt = timeval_delta(&tstamp, &tail->dccphrx_tstamp) * 4 / interval;
1708 ccid3_pr_debug("%s, sk=%p, approximated RTT to %uus\n",
1709 dccp_role(sk), sk, rtt);
1713 delta = timeval_now_delta(&hcrx->ccid3hcrx_tstamp_last_feedback);
1714 x_recv = hcrx->ccid3hcrx_bytes_recv * USEC_PER_SEC;
1715 if (likely(delta > 1))
1718 tmp1 = (u64)x_recv * (u64)rtt;
1719 do_div(tmp1,10000000);
1721 fval = (hcrx->ccid3hcrx_s * 100000) / tmp2;
1722 /* do not alter order above or you will get overflow on 32 bit */
1723 p = calcx_reverse_lookup(fval);
1724 ccid3_pr_debug("%s, sk=%p, receive rate=%u bytes/s, implied "
1725 "loss rate=%u\n", dccp_role(sk), sk, x_recv, p);
1733 static void ccid3_hc_rx_update_li(struct sock *sk, u64 seq_loss, u8 win_loss)
1735 struct dccp_sock *dp = dccp_sk(sk);
1736 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1737 struct ccid3_loss_interval_hist_entry *li_entry;
1739 if (seq_loss != DCCP_MAX_SEQNO + 1) {
1740 ccid3_pr_debug("%s, sk=%p, seq_loss=%llu, win_loss=%u, "
1741 "packet loss detected\n",
1742 dccp_role(sk), sk, seq_loss, win_loss);
1744 if (list_empty(&hcrx->ccid3hcrx_loss_interval_hist)) {
1745 struct ccid3_loss_interval_hist_entry *li_tail = NULL;
1748 ccid3_pr_debug("%s, sk=%p, first loss event detected, "
1749 "creating history\n",
1751 for (i = 0; i <= TFRC_RECV_IVAL_F_LENGTH; ++i) {
1752 li_entry = ccid3_loss_interval_hist_entry_new(SLAB_ATOMIC);
1753 if (li_entry == NULL) {
1754 ccid3_loss_interval_history_delete(&hcrx->ccid3hcrx_loss_interval_hist);
1755 ccid3_pr_debug("%s, sk=%p, not enough "
1761 if (li_tail == NULL)
1763 list_add(&li_entry->ccid3lih_node,
1764 &hcrx->ccid3hcrx_loss_interval_hist);
1767 li_entry->ccid3lih_seqno = seq_loss;
1768 li_entry->ccid3lih_win_count = win_loss;
1770 li_tail->ccid3lih_interval = ccid3_hc_rx_calc_first_li(sk);
1773 /* FIXME: find end of interval */
1776 static void ccid3_hc_rx_detect_loss(struct sock *sk)
1778 struct dccp_sock *dp = dccp_sk(sk);
1779 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1780 struct dccp_rx_hist_entry *entry, *next, *packet;
1781 struct dccp_rx_hist_entry *a_loss = NULL;
1782 struct dccp_rx_hist_entry *b_loss = NULL;
1783 u64 seq_loss = DCCP_MAX_SEQNO + 1;
1785 u8 num_later = TFRC_RECV_NUM_LATE_LOSS;
1787 list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
1789 if (num_later == 0) {
1792 } else if (dccp_rx_hist_entry_data_packet(entry))
1801 list_for_each_entry_safe_continue(entry, next, &hcrx->ccid3hcrx_hist,
1803 if (num_later == 0) {
1806 } else if (dccp_rx_hist_entry_data_packet(entry))
1810 if (a_loss == NULL) {
1811 if (list_empty(&hcrx->ccid3hcrx_loss_interval_hist)) {
1812 /* no loss event have occured yet */
1813 ccid3_pr_debug("%s, sk=%p, TODO: find a lost data "
1814 "packet by comparing to initial "
1819 pr_info("%s: %s, sk=%p, ERROR! Less than 4 data "
1820 "packets in history",
1821 __FUNCTION__, dccp_role(sk), sk);
1826 /* Locate a lost data packet */
1827 entry = packet = b_loss;
1828 list_for_each_entry_safe_continue(entry, next, &hcrx->ccid3hcrx_hist,
1830 u64 delta = dccp_delta_seqno(entry->dccphrx_seqno,
1831 packet->dccphrx_seqno);
1834 if (dccp_rx_hist_entry_data_packet(packet))
1837 * FIXME: check this, probably this % usage is because
1838 * in earlier drafts the ndp count was just 8 bits
1839 * long, but now it cam be up to 24 bits long.
1842 if (delta % DCCP_NDP_LIMIT !=
1843 (packet->dccphrx_ndp -
1844 entry->dccphrx_ndp) % DCCP_NDP_LIMIT)
1847 packet->dccphrx_ndp - entry->dccphrx_ndp) {
1848 seq_loss = entry->dccphrx_seqno;
1849 dccp_inc_seqno(&seq_loss);
1853 if (packet == a_loss)
1857 if (seq_loss != DCCP_MAX_SEQNO + 1)
1858 win_loss = a_loss->dccphrx_ccval;
1861 ccid3_hc_rx_update_li(sk, seq_loss, win_loss);
1864 static u32 ccid3_hc_rx_calc_i_mean(struct sock *sk)
1866 struct dccp_sock *dp = dccp_sk(sk);
1867 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1868 struct ccid3_loss_interval_hist_entry *li_entry, *li_next;
1875 list_for_each_entry_safe(li_entry, li_next,
1876 &hcrx->ccid3hcrx_loss_interval_hist,
1878 if (i < TFRC_RECV_IVAL_F_LENGTH) {
1879 i_tot0 += li_entry->ccid3lih_interval * ccid3_hc_rx_w[i];
1880 w_tot += ccid3_hc_rx_w[i];
1884 i_tot1 += li_entry->ccid3lih_interval * ccid3_hc_rx_w[i - 1];
1886 if (++i > TFRC_RECV_IVAL_F_LENGTH)
1890 if (i != TFRC_RECV_IVAL_F_LENGTH) {
1891 pr_info("%s: %s, sk=%p, ERROR! Missing entry in "
1892 "interval history!\n",
1893 __FUNCTION__, dccp_role(sk), sk);
1897 i_tot = max(i_tot0, i_tot1);
1899 /* FIXME: Why do we do this? -Ian McDonald */
1900 if (i_tot * 4 < w_tot)
1903 return i_tot * 4 / w_tot;
1906 static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
1908 struct dccp_sock *dp = dccp_sk(sk);
1909 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1910 const struct dccp_options_received *opt_recv;
1911 struct dccp_rx_hist_entry *packet;
1920 BUG_ON(!(hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA ||
1921 hcrx->ccid3hcrx_state == TFRC_RSTATE_DATA));
1923 opt_recv = &dp->dccps_options_received;
1925 switch (DCCP_SKB_CB(skb)->dccpd_type) {
1927 if (hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA)
1929 case DCCP_PKT_DATAACK:
1930 if (opt_recv->dccpor_timestamp_echo == 0)
1932 p_prev = hcrx->ccid3hcrx_rtt;
1933 do_gettimeofday(&now);
1934 hcrx->ccid3hcrx_rtt = timeval_usecs(&now) -
1935 (opt_recv->dccpor_timestamp_echo -
1936 opt_recv->dccpor_elapsed_time) * 10;
1937 if (p_prev != hcrx->ccid3hcrx_rtt)
1938 ccid3_pr_debug("%s, New RTT=%luus, elapsed time=%u\n",
1939 dccp_role(sk), hcrx->ccid3hcrx_rtt,
1940 opt_recv->dccpor_elapsed_time);
1945 ccid3_pr_debug("%s, sk=%p, not DATA/DATAACK/ACK packet(%s)\n",
1947 dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type));
1951 packet = dccp_rx_hist_entry_new(ccid3_rx_hist, opt_recv->dccpor_ndp,
1953 if (packet == NULL) {
1954 ccid3_pr_debug("%s, sk=%p, Not enough mem to add rx packet "
1955 "to history (consider it lost)!",
1960 win_count = packet->dccphrx_ccval;
1962 ins = ccid3_hc_rx_add_hist(sk, packet);
1964 if (DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_ACK)
1967 switch (hcrx->ccid3hcrx_state) {
1968 case TFRC_RSTATE_NO_DATA:
1969 ccid3_pr_debug("%s, sk=%p(%s), skb=%p, sending initial "
1972 dccp_state_name(sk->sk_state), skb);
1973 ccid3_hc_rx_send_feedback(sk);
1974 ccid3_hc_rx_set_state(sk, TFRC_RSTATE_DATA);
1976 case TFRC_RSTATE_DATA:
1977 hcrx->ccid3hcrx_bytes_recv += skb->len -
1978 dccp_hdr(skb)->dccph_doff * 4;
1982 do_gettimeofday(&now);
1983 if (timeval_delta(&now, &hcrx->ccid3hcrx_tstamp_last_ack) >=
1984 hcrx->ccid3hcrx_rtt) {
1985 hcrx->ccid3hcrx_tstamp_last_ack = now;
1986 ccid3_hc_rx_send_feedback(sk);
1990 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1991 __FUNCTION__, dccp_role(sk), sk, hcrx->ccid3hcrx_state);
1996 /* Dealing with packet loss */
1997 ccid3_pr_debug("%s, sk=%p(%s), data loss! Reacting...\n",
1998 dccp_role(sk), sk, dccp_state_name(sk->sk_state));
2000 ccid3_hc_rx_detect_loss(sk);
2001 p_prev = hcrx->ccid3hcrx_p;
2003 /* Calculate loss event rate */
2004 if (!list_empty(&hcrx->ccid3hcrx_loss_interval_hist))
2005 /* Scaling up by 1000000 as fixed decimal */
2006 hcrx->ccid3hcrx_p = 1000000 / ccid3_hc_rx_calc_i_mean(sk);
2008 if (hcrx->ccid3hcrx_p > p_prev) {
2009 ccid3_hc_rx_send_feedback(sk);
2014 static int ccid3_hc_rx_init(struct sock *sk)
2016 struct dccp_sock *dp = dccp_sk(sk);
2017 struct ccid3_hc_rx_sock *hcrx;
2019 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
2021 hcrx = dp->dccps_hc_rx_ccid_private = kmalloc(sizeof(*hcrx),
2026 memset(hcrx, 0, sizeof(*hcrx));
2028 if (dp->dccps_avg_packet_size >= TFRC_MIN_PACKET_SIZE &&
2029 dp->dccps_avg_packet_size <= TFRC_MAX_PACKET_SIZE)
2030 hcrx->ccid3hcrx_s = (u16)dp->dccps_avg_packet_size;
2032 hcrx->ccid3hcrx_s = TFRC_STD_PACKET_SIZE;
2034 hcrx->ccid3hcrx_state = TFRC_RSTATE_NO_DATA;
2035 INIT_LIST_HEAD(&hcrx->ccid3hcrx_hist);
2036 INIT_LIST_HEAD(&hcrx->ccid3hcrx_loss_interval_hist);
2038 * XXX this seems to be paranoid, need to think more about this, for
2039 * now start with something different than zero. -acme
2041 hcrx->ccid3hcrx_rtt = USEC_PER_SEC / 5;
2045 static void ccid3_hc_rx_exit(struct sock *sk)
2047 struct dccp_sock *dp = dccp_sk(sk);
2048 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
2050 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
2055 ccid3_hc_rx_set_state(sk, TFRC_RSTATE_TERM);
2057 /* Empty packet history */
2058 dccp_rx_hist_purge(ccid3_rx_hist, &hcrx->ccid3hcrx_hist);
2060 /* Empty loss interval history */
2061 ccid3_loss_interval_history_delete(&hcrx->ccid3hcrx_loss_interval_hist);
2063 kfree(dp->dccps_hc_rx_ccid_private);
2064 dp->dccps_hc_rx_ccid_private = NULL;
2067 static void ccid3_hc_rx_get_info(struct sock *sk, struct tcp_info *info)
2069 const struct dccp_sock *dp = dccp_sk(sk);
2070 const struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
2075 info->tcpi_ca_state = hcrx->ccid3hcrx_state;
2076 info->tcpi_options |= TCPI_OPT_TIMESTAMPS;
2077 info->tcpi_rcv_rtt = hcrx->ccid3hcrx_rtt;
2080 static void ccid3_hc_tx_get_info(struct sock *sk, struct tcp_info *info)
2082 const struct dccp_sock *dp = dccp_sk(sk);
2083 const struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
2088 info->tcpi_rto = hctx->ccid3hctx_t_rto;
2089 info->tcpi_rtt = hctx->ccid3hctx_rtt;
2092 static struct ccid ccid3 = {
2094 .ccid_name = "ccid3",
2095 .ccid_owner = THIS_MODULE,
2096 .ccid_init = ccid3_init,
2097 .ccid_exit = ccid3_exit,
2098 .ccid_hc_tx_init = ccid3_hc_tx_init,
2099 .ccid_hc_tx_exit = ccid3_hc_tx_exit,
2100 .ccid_hc_tx_send_packet = ccid3_hc_tx_send_packet,
2101 .ccid_hc_tx_packet_sent = ccid3_hc_tx_packet_sent,
2102 .ccid_hc_tx_packet_recv = ccid3_hc_tx_packet_recv,
2103 .ccid_hc_tx_insert_options = ccid3_hc_tx_insert_options,
2104 .ccid_hc_tx_parse_options = ccid3_hc_tx_parse_options,
2105 .ccid_hc_rx_init = ccid3_hc_rx_init,
2106 .ccid_hc_rx_exit = ccid3_hc_rx_exit,
2107 .ccid_hc_rx_insert_options = ccid3_hc_rx_insert_options,
2108 .ccid_hc_rx_packet_recv = ccid3_hc_rx_packet_recv,
2109 .ccid_hc_rx_get_info = ccid3_hc_rx_get_info,
2110 .ccid_hc_tx_get_info = ccid3_hc_tx_get_info,
2113 module_param(ccid3_debug, int, 0444);
2114 MODULE_PARM_DESC(ccid3_debug, "Enable debug messages");
2116 static __init int ccid3_module_init(void)
2120 ccid3_rx_hist = dccp_rx_hist_new("ccid3");
2121 if (ccid3_rx_hist == NULL)
2124 ccid3_tx_hist = dccp_tx_hist_new("ccid3");
2125 if (ccid3_tx_hist == NULL)
2128 ccid3_loss_interval_hist_slab = kmem_cache_create("li_hist_ccid3",
2129 sizeof(struct ccid3_loss_interval_hist_entry),
2130 0, SLAB_HWCACHE_ALIGN,
2132 if (ccid3_loss_interval_hist_slab == NULL)
2135 rc = ccid_register(&ccid3);
2137 goto out_free_loss_interval_history;
2141 out_free_loss_interval_history:
2142 kmem_cache_destroy(ccid3_loss_interval_hist_slab);
2143 ccid3_loss_interval_hist_slab = NULL;
2145 dccp_tx_hist_delete(ccid3_tx_hist);
2146 ccid3_tx_hist = NULL;
2148 dccp_rx_hist_delete(ccid3_rx_hist);
2149 ccid3_rx_hist = NULL;
2152 module_init(ccid3_module_init);
2154 static __exit void ccid3_module_exit(void)
2156 #ifdef CONFIG_IP_DCCP_UNLOAD_HACK
2158 * Hack to use while developing, so that we get rid of the control
2159 * sock, that is what keeps a refcount on dccp.ko -acme
2161 extern void dccp_ctl_sock_exit(void);
2163 dccp_ctl_sock_exit();
2165 ccid_unregister(&ccid3);
2167 if (ccid3_tx_hist != NULL) {
2168 dccp_tx_hist_delete(ccid3_tx_hist);
2169 ccid3_tx_hist = NULL;
2171 if (ccid3_rx_hist != NULL) {
2172 dccp_rx_hist_delete(ccid3_rx_hist);
2173 ccid3_rx_hist = NULL;
2175 if (ccid3_loss_interval_hist_slab != NULL) {
2176 kmem_cache_destroy(ccid3_loss_interval_hist_slab);
2177 ccid3_loss_interval_hist_slab = NULL;
2180 module_exit(ccid3_module_exit);
2182 MODULE_AUTHOR("Ian McDonald <iam4@cs.waikato.ac.nz>, "
2183 "Arnaldo Carvalho de Melo <acme@ghostprotocols.net>");
2184 MODULE_DESCRIPTION("DCCP TFRC CCID3 CCID");
2185 MODULE_LICENSE("GPL");
2186 MODULE_ALIAS("net-dccp-ccid-3");