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 "lib/packet_history.h"
41 #include "lib/loss_interval.h"
45 * Reason for maths with 10 here is to avoid 32 bit overflow when a is big.
47 static inline u32 usecs_div(const u32 a, const u32 b)
49 const u32 tmp = a * (USEC_PER_SEC / 10);
50 return b > 20 ? tmp / (b / 10) : tmp;
53 static int ccid3_debug;
56 #define ccid3_pr_debug(format, a...) \
57 do { if (ccid3_debug) \
58 printk(KERN_DEBUG "%s: " format, __FUNCTION__, ##a); \
61 #define ccid3_pr_debug(format, a...)
64 static struct dccp_tx_hist *ccid3_tx_hist;
65 static struct dccp_rx_hist *ccid3_rx_hist;
66 static struct dccp_li_hist *ccid3_li_hist;
68 static int ccid3_init(struct sock *sk)
70 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
74 static void ccid3_exit(struct sock *sk)
76 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
79 /* TFRC sender states */
80 enum ccid3_hc_tx_states {
81 TFRC_SSTATE_NO_SENT = 1,
88 static const char *ccid3_tx_state_name(enum ccid3_hc_tx_states state)
90 static char *ccid3_state_names[] = {
91 [TFRC_SSTATE_NO_SENT] = "NO_SENT",
92 [TFRC_SSTATE_NO_FBACK] = "NO_FBACK",
93 [TFRC_SSTATE_FBACK] = "FBACK",
94 [TFRC_SSTATE_TERM] = "TERM",
97 return ccid3_state_names[state];
101 static inline void ccid3_hc_tx_set_state(struct sock *sk,
102 enum ccid3_hc_tx_states state)
104 struct dccp_sock *dp = dccp_sk(sk);
105 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
106 enum ccid3_hc_tx_states oldstate = hctx->ccid3hctx_state;
108 ccid3_pr_debug("%s(%p) %-8.8s -> %s\n",
109 dccp_role(sk), sk, ccid3_tx_state_name(oldstate),
110 ccid3_tx_state_name(state));
111 WARN_ON(state == oldstate);
112 hctx->ccid3hctx_state = state;
115 #define CALCX_ARRSIZE 500
117 #define CALCX_SPLIT 50000
118 /* equivalent to 0.05 */
120 static const u32 calcx_lookup[CALCX_ARRSIZE][2] = {
242 { 2976382 , 100134 },
243 { 3037850 , 100626 },
244 { 3100360 , 101117 },
245 { 3163924 , 101608 },
246 { 3228554 , 102097 },
247 { 3294263 , 102586 },
248 { 3361063 , 103073 },
249 { 3428966 , 103560 },
250 { 3497984 , 104045 },
251 { 3568131 , 104530 },
252 { 3639419 , 105014 },
253 { 3711860 , 105498 },
254 { 3785467 , 105980 },
255 { 3860253 , 106462 },
256 { 3936229 , 106942 },
257 { 4013410 , 107422 },
258 { 4091808 , 107902 },
259 { 4171435 , 108380 },
260 { 4252306 , 108858 },
261 { 4334431 , 109335 },
262 { 4417825 , 109811 },
263 { 4502501 , 110287 },
264 { 4588472 , 110762 },
265 { 4675750 , 111236 },
266 { 4764349 , 111709 },
267 { 4854283 , 112182 },
268 { 4945564 , 112654 },
269 { 5038206 , 113126 },
270 { 5132223 , 113597 },
271 { 5227627 , 114067 },
272 { 5324432 , 114537 },
273 { 5422652 , 115006 },
274 { 5522299 , 115474 },
275 { 5623389 , 115942 },
276 { 5725934 , 116409 },
277 { 5829948 , 116876 },
278 { 5935446 , 117342 },
279 { 6042439 , 117808 },
280 { 6150943 , 118273 },
281 { 6260972 , 118738 },
282 { 6372538 , 119202 },
283 { 6485657 , 119665 },
284 { 6600342 , 120128 },
285 { 6716607 , 120591 },
286 { 6834467 , 121053 },
287 { 6953935 , 121514 },
288 { 7075025 , 121976 },
289 { 7197752 , 122436 },
290 { 7322131 , 122896 },
291 { 7448175 , 123356 },
292 { 7575898 , 123815 },
293 { 7705316 , 124274 },
294 { 7836442 , 124733 },
295 { 7969291 , 125191 },
296 { 8103877 , 125648 },
297 { 8240216 , 126105 },
298 { 8378321 , 126562 },
299 { 8518208 , 127018 },
300 { 8659890 , 127474 },
301 { 8803384 , 127930 },
302 { 8948702 , 128385 },
303 { 9095861 , 128840 },
304 { 9244875 , 129294 },
305 { 9395760 , 129748 },
306 { 9548529 , 130202 },
307 { 9703198 , 130655 },
308 { 9859782 , 131108 },
309 { 10018296 , 131561 },
310 { 10178755 , 132014 },
311 { 10341174 , 132466 },
312 { 10505569 , 132917 },
313 { 10671954 , 133369 },
314 { 10840345 , 133820 },
315 { 11010757 , 134271 },
316 { 11183206 , 134721 },
317 { 11357706 , 135171 },
318 { 11534274 , 135621 },
319 { 11712924 , 136071 },
320 { 11893673 , 136520 },
321 { 12076536 , 136969 },
322 { 12261527 , 137418 },
323 { 12448664 , 137867 },
324 { 12637961 , 138315 },
325 { 12829435 , 138763 },
326 { 13023101 , 139211 },
327 { 13218974 , 139658 },
328 { 13417071 , 140106 },
329 { 13617407 , 140553 },
330 { 13819999 , 140999 },
331 { 14024862 , 141446 },
332 { 14232012 , 141892 },
333 { 14441465 , 142339 },
334 { 14653238 , 142785 },
335 { 14867346 , 143230 },
336 { 15083805 , 143676 },
337 { 15302632 , 144121 },
338 { 15523842 , 144566 },
339 { 15747453 , 145011 },
340 { 15973479 , 145456 },
341 { 16201939 , 145900 },
342 { 16432847 , 146345 },
343 { 16666221 , 146789 },
344 { 16902076 , 147233 },
345 { 17140429 , 147677 },
346 { 17381297 , 148121 },
347 { 17624696 , 148564 },
348 { 17870643 , 149007 },
349 { 18119154 , 149451 },
350 { 18370247 , 149894 },
351 { 18623936 , 150336 },
352 { 18880241 , 150779 },
353 { 19139176 , 151222 },
354 { 19400759 , 151664 },
355 { 19665007 , 152107 },
356 { 19931936 , 152549 },
357 { 20201564 , 152991 },
358 { 20473907 , 153433 },
359 { 20748982 , 153875 },
360 { 21026807 , 154316 },
361 { 21307399 , 154758 },
362 { 21590773 , 155199 },
363 { 21876949 , 155641 },
364 { 22165941 , 156082 },
365 { 22457769 , 156523 },
366 { 22752449 , 156964 },
367 { 23049999 , 157405 },
368 { 23350435 , 157846 },
369 { 23653774 , 158287 },
370 { 23960036 , 158727 },
371 { 24269236 , 159168 },
372 { 24581392 , 159608 },
373 { 24896521 , 160049 },
374 { 25214642 , 160489 },
375 { 25535772 , 160929 },
376 { 25859927 , 161370 },
377 { 26187127 , 161810 },
378 { 26517388 , 162250 },
379 { 26850728 , 162690 },
380 { 27187165 , 163130 },
381 { 27526716 , 163569 },
382 { 27869400 , 164009 },
383 { 28215234 , 164449 },
384 { 28564236 , 164889 },
385 { 28916423 , 165328 },
386 { 29271815 , 165768 },
387 { 29630428 , 166208 },
388 { 29992281 , 166647 },
389 { 30357392 , 167087 },
390 { 30725779 , 167526 },
391 { 31097459 , 167965 },
392 { 31472452 , 168405 },
393 { 31850774 , 168844 },
394 { 32232445 , 169283 },
395 { 32617482 , 169723 },
396 { 33005904 , 170162 },
397 { 33397730 , 170601 },
398 { 33792976 , 171041 },
399 { 34191663 , 171480 },
400 { 34593807 , 171919 },
401 { 34999428 , 172358 },
402 { 35408544 , 172797 },
403 { 35821174 , 173237 },
404 { 36237335 , 173676 },
405 { 36657047 , 174115 },
406 { 37080329 , 174554 },
407 { 37507197 , 174993 },
408 { 37937673 , 175433 },
409 { 38371773 , 175872 },
410 { 38809517 , 176311 },
411 { 39250924 , 176750 },
412 { 39696012 , 177190 },
413 { 40144800 , 177629 },
414 { 40597308 , 178068 },
415 { 41053553 , 178507 },
416 { 41513554 , 178947 },
417 { 41977332 , 179386 },
418 { 42444904 , 179825 },
419 { 42916290 , 180265 },
420 { 43391509 , 180704 },
421 { 43870579 , 181144 },
422 { 44353520 , 181583 },
423 { 44840352 , 182023 },
424 { 45331092 , 182462 },
425 { 45825761 , 182902 },
426 { 46324378 , 183342 },
427 { 46826961 , 183781 },
428 { 47333531 , 184221 },
429 { 47844106 , 184661 },
430 { 48358706 , 185101 },
431 { 48877350 , 185541 },
432 { 49400058 , 185981 },
433 { 49926849 , 186421 },
434 { 50457743 , 186861 },
435 { 50992759 , 187301 },
436 { 51531916 , 187741 },
437 { 52075235 , 188181 },
438 { 52622735 , 188622 },
439 { 53174435 , 189062 },
440 { 53730355 , 189502 },
441 { 54290515 , 189943 },
442 { 54854935 , 190383 },
443 { 55423634 , 190824 },
444 { 55996633 , 191265 },
445 { 56573950 , 191706 },
446 { 57155606 , 192146 },
447 { 57741621 , 192587 },
448 { 58332014 , 193028 },
449 { 58926806 , 193470 },
450 { 59526017 , 193911 },
451 { 60129666 , 194352 },
452 { 60737774 , 194793 },
453 { 61350361 , 195235 },
454 { 61967446 , 195677 },
455 { 62589050 , 196118 },
456 { 63215194 , 196560 },
457 { 63845897 , 197002 },
458 { 64481179 , 197444 },
459 { 65121061 , 197886 },
460 { 65765563 , 198328 },
461 { 66414705 , 198770 },
462 { 67068508 , 199213 },
463 { 67726992 , 199655 },
464 { 68390177 , 200098 },
465 { 69058085 , 200540 },
466 { 69730735 , 200983 },
467 { 70408147 , 201426 },
468 { 71090343 , 201869 },
469 { 71777343 , 202312 },
470 { 72469168 , 202755 },
471 { 73165837 , 203199 },
472 { 73867373 , 203642 },
473 { 74573795 , 204086 },
474 { 75285124 , 204529 },
475 { 76001380 , 204973 },
476 { 76722586 , 205417 },
477 { 77448761 , 205861 },
478 { 78179926 , 206306 },
479 { 78916102 , 206750 },
480 { 79657310 , 207194 },
481 { 80403571 , 207639 },
482 { 81154906 , 208084 },
483 { 81911335 , 208529 },
484 { 82672880 , 208974 },
485 { 83439562 , 209419 },
486 { 84211402 , 209864 },
487 { 84988421 , 210309 },
488 { 85770640 , 210755 },
489 { 86558080 , 211201 },
490 { 87350762 , 211647 },
491 { 88148708 , 212093 },
492 { 88951938 , 212539 },
493 { 89760475 , 212985 },
494 { 90574339 , 213432 },
495 { 91393551 , 213878 },
496 { 92218133 , 214325 },
497 { 93048107 , 214772 },
498 { 93883493 , 215219 },
499 { 94724314 , 215666 },
500 { 95570590 , 216114 },
501 { 96422343 , 216561 },
502 { 97279594 , 217009 },
503 { 98142366 , 217457 },
504 { 99010679 , 217905 },
505 { 99884556 , 218353 },
506 { 100764018 , 218801 },
507 { 101649086 , 219250 },
508 { 102539782 , 219698 },
509 { 103436128 , 220147 },
510 { 104338146 , 220596 },
511 { 105245857 , 221046 },
512 { 106159284 , 221495 },
513 { 107078448 , 221945 },
514 { 108003370 , 222394 },
515 { 108934074 , 222844 },
516 { 109870580 , 223294 },
517 { 110812910 , 223745 },
518 { 111761087 , 224195 },
519 { 112715133 , 224646 },
520 { 113675069 , 225097 },
521 { 114640918 , 225548 },
522 { 115612702 , 225999 },
523 { 116590442 , 226450 },
524 { 117574162 , 226902 },
525 { 118563882 , 227353 },
526 { 119559626 , 227805 },
527 { 120561415 , 228258 },
528 { 121569272 , 228710 },
529 { 122583219 , 229162 },
530 { 123603278 , 229615 },
531 { 124629471 , 230068 },
532 { 125661822 , 230521 },
533 { 126700352 , 230974 },
534 { 127745083 , 231428 },
535 { 128796039 , 231882 },
536 { 129853241 , 232336 },
537 { 130916713 , 232790 },
538 { 131986475 , 233244 },
539 { 133062553 , 233699 },
540 { 134144966 , 234153 },
541 { 135233739 , 234608 },
542 { 136328894 , 235064 },
543 { 137430453 , 235519 },
544 { 138538440 , 235975 },
545 { 139652876 , 236430 },
546 { 140773786 , 236886 },
547 { 141901190 , 237343 },
548 { 143035113 , 237799 },
549 { 144175576 , 238256 },
550 { 145322604 , 238713 },
551 { 146476218 , 239170 },
552 { 147636442 , 239627 },
553 { 148803298 , 240085 },
554 { 149976809 , 240542 },
555 { 151156999 , 241000 },
556 { 152343890 , 241459 },
557 { 153537506 , 241917 },
558 { 154737869 , 242376 },
559 { 155945002 , 242835 },
560 { 157158929 , 243294 },
561 { 158379673 , 243753 },
562 { 159607257 , 244213 },
563 { 160841704 , 244673 },
564 { 162083037 , 245133 },
565 { 163331279 , 245593 },
566 { 164586455 , 246054 },
567 { 165848586 , 246514 },
568 { 167117696 , 246975 },
569 { 168393810 , 247437 },
570 { 169676949 , 247898 },
571 { 170967138 , 248360 },
572 { 172264399 , 248822 },
573 { 173568757 , 249284 },
574 { 174880235 , 249747 },
575 { 176198856 , 250209 },
576 { 177524643 , 250672 },
577 { 178857621 , 251136 },
578 { 180197813 , 251599 },
579 { 181545242 , 252063 },
580 { 182899933 , 252527 },
581 { 184261908 , 252991 },
582 { 185631191 , 253456 },
583 { 187007807 , 253920 },
584 { 188391778 , 254385 },
585 { 189783129 , 254851 },
586 { 191181884 , 255316 },
587 { 192588065 , 255782 },
588 { 194001698 , 256248 },
589 { 195422805 , 256714 },
590 { 196851411 , 257181 },
591 { 198287540 , 257648 },
592 { 199731215 , 258115 },
593 { 201182461 , 258582 },
594 { 202641302 , 259050 },
595 { 204107760 , 259518 },
596 { 205581862 , 259986 },
597 { 207063630 , 260454 },
598 { 208553088 , 260923 },
599 { 210050262 , 261392 },
600 { 211555174 , 261861 },
601 { 213067849 , 262331 },
602 { 214588312 , 262800 },
603 { 216116586 , 263270 },
604 { 217652696 , 263741 },
605 { 219196666 , 264211 },
606 { 220748520 , 264682 },
607 { 222308282 , 265153 },
608 { 223875978 , 265625 },
609 { 225451630 , 266097 },
610 { 227035265 , 266569 },
611 { 228626905 , 267041 },
612 { 230226576 , 267514 },
613 { 231834302 , 267986 },
614 { 233450107 , 268460 },
615 { 235074016 , 268933 },
616 { 236706054 , 269407 },
617 { 238346244 , 269881 },
618 { 239994613 , 270355 },
619 { 241651183 , 270830 },
620 { 243315981 , 271305 }
623 /* Calculate the send rate as per section 3.1 of RFC3448
625 Returns send rate in bytes per second
627 Integer maths and lookups are used as not allowed floating point in kernel
629 The function for Xcalc as per section 3.1 of RFC3448 is:
632 -------------------------------------------------------------
633 R*sqrt(2*b*p/3) + (t_RTO * (3*sqrt(3*b*p/8) * p * (1+32*p^2)))
636 X is the trasmit rate in bytes/second
637 s is the packet size in bytes
638 R is the round trip time in seconds
639 p is the loss event rate, between 0 and 1.0, of the number of loss events
640 as a fraction of the number of packets transmitted
641 t_RTO is the TCP retransmission timeout value in seconds
642 b is the number of packets acknowledged by a single TCP acknowledgement
644 we can assume that b = 1 and t_RTO is 4 * R. With this the equation becomes:
647 -----------------------------------------------------------------------
648 R * sqrt(2 * p / 3) + (12 * R * (sqrt(3 * p / 8) * p * (1 + 32 * p^2)))
651 which we can break down into:
657 where f(p) = sqrt(2 * p / 3) + (12 * sqrt(3 * p / 8) * p * (1 + 32 * p * p))
662 p - loss rate (decimal fraction multiplied by 1,000,000)
664 Returns Xcalc in bytes per second
666 DON'T alter this code unless you run test cases against it as the code
667 has been manipulated to stop underflow/overlow.
670 static u32 ccid3_calc_x(u16 s, u32 R, u32 p)
677 index = (p / (CALCX_SPLIT / CALCX_ARRSIZE)) - 1;
679 index = (p / (1000000 / CALCX_ARRSIZE)) - 1;
682 /* p should be 0 unless there is a bug in my code */
686 R = 1; /* RTT can't be zero or else divide by zero */
688 BUG_ON(index >= CALCX_ARRSIZE);
690 if (p >= CALCX_SPLIT)
691 f = calcx_lookup[index][0];
693 f = calcx_lookup[index][1];
695 tmp1 = ((u64)s * 100000000);
696 tmp2 = ((u64)R * (u64)f);
699 /* don't alter above math unless you test due to overflow on 32 bit */
704 /* Calculate new t_ipi (inter packet interval) by t_ipi = s / X_inst */
705 static inline void ccid3_calc_new_t_ipi(struct ccid3_hc_tx_sock *hctx)
708 * If no feedback spec says t_ipi is 1 second (set elsewhere and then
709 * doubles after every no feedback timer (separate function)
711 if (hctx->ccid3hctx_state != TFRC_SSTATE_NO_FBACK)
712 hctx->ccid3hctx_t_ipi = usecs_div(hctx->ccid3hctx_s,
716 /* Calculate new delta by delta = min(t_ipi / 2, t_gran / 2) */
717 static inline void ccid3_calc_new_delta(struct ccid3_hc_tx_sock *hctx)
719 hctx->ccid3hctx_delta = min_t(u32, hctx->ccid3hctx_t_ipi / 2,
720 TFRC_OPSYS_HALF_TIME_GRAN);
726 * x_calc = calcX(s, R, p);
727 * X = max(min(X_calc, 2 * X_recv), s / t_mbi);
729 * If (now - tld >= R)
730 * X = max(min(2 * X, 2 * X_recv), s / R);
733 static void ccid3_hc_tx_update_x(struct sock *sk)
735 struct dccp_sock *dp = dccp_sk(sk);
736 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
738 /* To avoid large error in calcX */
739 if (hctx->ccid3hctx_p >= TFRC_SMALLEST_P) {
740 hctx->ccid3hctx_x_calc = ccid3_calc_x(hctx->ccid3hctx_s,
743 hctx->ccid3hctx_x = max_t(u32, min_t(u32, hctx->ccid3hctx_x_calc,
744 2 * hctx->ccid3hctx_x_recv),
746 TFRC_MAX_BACK_OFF_TIME));
750 do_gettimeofday(&now);
751 if (timeval_delta(&now, &hctx->ccid3hctx_t_ld) >=
752 hctx->ccid3hctx_rtt) {
753 hctx->ccid3hctx_x = max_t(u32, min_t(u32, hctx->ccid3hctx_x_recv,
754 hctx->ccid3hctx_x) * 2,
755 usecs_div(hctx->ccid3hctx_s,
756 hctx->ccid3hctx_rtt));
757 hctx->ccid3hctx_t_ld = now;
762 static void ccid3_hc_tx_no_feedback_timer(unsigned long data)
764 struct sock *sk = (struct sock *)data;
765 struct dccp_sock *dp = dccp_sk(sk);
766 unsigned long next_tmout = 0;
767 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
770 if (sock_owned_by_user(sk)) {
771 /* Try again later. */
772 /* XXX: set some sensible MIB */
773 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
778 ccid3_pr_debug("%s, sk=%p, state=%s\n", dccp_role(sk), sk,
779 ccid3_tx_state_name(hctx->ccid3hctx_state));
781 switch (hctx->ccid3hctx_state) {
782 case TFRC_SSTATE_TERM:
784 case TFRC_SSTATE_NO_FBACK:
785 /* Halve send rate */
786 hctx->ccid3hctx_x /= 2;
787 if (hctx->ccid3hctx_x < (hctx->ccid3hctx_s /
788 TFRC_MAX_BACK_OFF_TIME))
789 hctx->ccid3hctx_x = (hctx->ccid3hctx_s /
790 TFRC_MAX_BACK_OFF_TIME);
792 ccid3_pr_debug("%s, sk=%p, state=%s, updated tx rate to %d "
795 ccid3_tx_state_name(hctx->ccid3hctx_state),
797 next_tmout = max_t(u32, 2 * usecs_div(hctx->ccid3hctx_s,
799 TFRC_INITIAL_TIMEOUT);
801 * FIXME - not sure above calculation is correct. See section
802 * 5 of CCID3 11 should adjust tx_t_ipi and double that to
806 case TFRC_SSTATE_FBACK:
808 * Check if IDLE since last timeout and recv rate is less than
811 if (!hctx->ccid3hctx_idle ||
812 (hctx->ccid3hctx_x_recv >=
813 4 * usecs_div(hctx->ccid3hctx_s, hctx->ccid3hctx_rtt))) {
814 ccid3_pr_debug("%s, sk=%p, state=%s, not idle\n",
816 ccid3_tx_state_name(hctx->ccid3hctx_state));
817 /* Halve sending rate */
819 /* If (X_calc > 2 * X_recv)
820 * X_recv = max(X_recv / 2, s / (2 * t_mbi));
822 * X_recv = X_calc / 4;
824 BUG_ON(hctx->ccid3hctx_p >= TFRC_SMALLEST_P &&
825 hctx->ccid3hctx_x_calc == 0);
827 /* check also if p is zero -> x_calc is infinity? */
828 if (hctx->ccid3hctx_p < TFRC_SMALLEST_P ||
829 hctx->ccid3hctx_x_calc > 2 * hctx->ccid3hctx_x_recv)
830 hctx->ccid3hctx_x_recv = max_t(u32, hctx->ccid3hctx_x_recv / 2,
831 hctx->ccid3hctx_s / (2 * TFRC_MAX_BACK_OFF_TIME));
833 hctx->ccid3hctx_x_recv = hctx->ccid3hctx_x_calc / 4;
835 /* Update sending rate */
836 ccid3_hc_tx_update_x(sk);
839 * Schedule no feedback timer to expire in
840 * max(4 * R, 2 * s / X)
842 next_tmout = max_t(u32, hctx->ccid3hctx_t_rto,
843 2 * usecs_div(hctx->ccid3hctx_s,
847 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
848 __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
853 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
854 jiffies + max_t(u32, 1, usecs_to_jiffies(next_tmout)));
855 hctx->ccid3hctx_idle = 1;
861 static int ccid3_hc_tx_send_packet(struct sock *sk,
862 struct sk_buff *skb, int len)
864 struct dccp_sock *dp = dccp_sk(sk);
865 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
866 struct dccp_tx_hist_entry *new_packet;
871 /* Check if pure ACK or Terminating*/
874 * XXX: We only call this function for DATA and DATAACK, on, these
875 * packets can have zero length, but why the comment about "pure ACK"?
877 if (hctx == NULL || len == 0 ||
878 hctx->ccid3hctx_state == TFRC_SSTATE_TERM)
881 /* See if last packet allocated was not sent */
882 new_packet = dccp_tx_hist_head(&hctx->ccid3hctx_hist);
883 if (new_packet == NULL || new_packet->dccphtx_sent) {
884 new_packet = dccp_tx_hist_entry_new(ccid3_tx_hist,
888 if (new_packet == NULL) {
889 ccid3_pr_debug("%s, sk=%p, not enough mem to add "
890 "to history, send refused\n",
895 dccp_tx_hist_add_entry(&hctx->ccid3hctx_hist, new_packet);
898 do_gettimeofday(&now);
900 switch (hctx->ccid3hctx_state) {
901 case TFRC_SSTATE_NO_SENT:
902 ccid3_pr_debug("%s, sk=%p, first packet(%llu)\n",
903 dccp_role(sk), sk, dp->dccps_gss);
905 hctx->ccid3hctx_no_feedback_timer.function = ccid3_hc_tx_no_feedback_timer;
906 hctx->ccid3hctx_no_feedback_timer.data = (unsigned long)sk;
907 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
908 jiffies + usecs_to_jiffies(TFRC_INITIAL_TIMEOUT));
909 hctx->ccid3hctx_last_win_count = 0;
910 hctx->ccid3hctx_t_last_win_count = now;
911 ccid3_hc_tx_set_state(sk, TFRC_SSTATE_NO_FBACK);
912 hctx->ccid3hctx_t_ipi = TFRC_INITIAL_TIMEOUT;
914 /* Set nominal send time for initial packet */
915 hctx->ccid3hctx_t_nom = now;
916 timeval_add_usecs(&hctx->ccid3hctx_t_nom,
917 hctx->ccid3hctx_t_ipi);
918 ccid3_calc_new_delta(hctx);
921 case TFRC_SSTATE_NO_FBACK:
922 case TFRC_SSTATE_FBACK:
923 delay = (timeval_delta(&now, &hctx->ccid3hctx_t_nom) -
924 hctx->ccid3hctx_delta);
925 ccid3_pr_debug("send_packet delay=%ld\n", delay);
927 /* divide by -1000 is to convert to ms and get sign right */
928 rc = delay > 0 ? delay : 0;
931 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
932 __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
938 /* Can we send? if so add options and add to packet history */
940 new_packet->dccphtx_ccval =
941 DCCP_SKB_CB(skb)->dccpd_ccval =
942 hctx->ccid3hctx_last_win_count;
947 static void ccid3_hc_tx_packet_sent(struct sock *sk, int more, int len)
949 struct dccp_sock *dp = dccp_sk(sk);
950 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
953 BUG_ON(hctx == NULL);
955 if (hctx->ccid3hctx_state == TFRC_SSTATE_TERM) {
956 ccid3_pr_debug("%s, sk=%p, while state is TFRC_SSTATE_TERM!\n",
961 do_gettimeofday(&now);
963 /* check if we have sent a data packet */
965 unsigned long quarter_rtt;
966 struct dccp_tx_hist_entry *packet;
968 packet = dccp_tx_hist_head(&hctx->ccid3hctx_hist);
969 if (packet == NULL) {
970 printk(KERN_CRIT "%s: packet doesn't exists in "
971 "history!\n", __FUNCTION__);
974 if (packet->dccphtx_sent) {
975 printk(KERN_CRIT "%s: no unsent packet in history!\n",
979 packet->dccphtx_tstamp = now;
980 packet->dccphtx_seqno = dp->dccps_gss;
982 * Check if win_count have changed
983 * Algorithm in "8.1. Window Counter Valuer" in
984 * draft-ietf-dccp-ccid3-11.txt
986 quarter_rtt = timeval_delta(&now, &hctx->ccid3hctx_t_last_win_count);
987 if (likely(hctx->ccid3hctx_rtt > 8))
988 quarter_rtt /= hctx->ccid3hctx_rtt / 4;
990 if (quarter_rtt > 0) {
991 hctx->ccid3hctx_t_last_win_count = now;
992 hctx->ccid3hctx_last_win_count = (hctx->ccid3hctx_last_win_count +
993 min_t(unsigned long, quarter_rtt, 5)) % 16;
994 ccid3_pr_debug("%s, sk=%p, window changed from "
997 packet->dccphtx_ccval,
998 hctx->ccid3hctx_last_win_count);
1001 hctx->ccid3hctx_idle = 0;
1002 packet->dccphtx_rtt = hctx->ccid3hctx_rtt;
1003 packet->dccphtx_sent = 1;
1005 ccid3_pr_debug("%s, sk=%p, seqno=%llu NOT inserted!\n",
1006 dccp_role(sk), sk, dp->dccps_gss);
1008 switch (hctx->ccid3hctx_state) {
1009 case TFRC_SSTATE_NO_SENT:
1010 /* if first wasn't pure ack */
1012 printk(KERN_CRIT "%s: %s, First packet sent is noted "
1013 "as a data packet\n",
1014 __FUNCTION__, dccp_role(sk));
1016 case TFRC_SSTATE_NO_FBACK:
1017 case TFRC_SSTATE_FBACK:
1019 hctx->ccid3hctx_t_nom = now;
1020 ccid3_calc_new_t_ipi(hctx);
1021 ccid3_calc_new_delta(hctx);
1022 timeval_add_usecs(&hctx->ccid3hctx_t_nom,
1023 hctx->ccid3hctx_t_ipi);
1027 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1028 __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
1034 static void ccid3_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
1036 struct dccp_sock *dp = dccp_sk(sk);
1037 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1038 struct ccid3_options_received *opt_recv;
1039 struct dccp_tx_hist_entry *packet;
1040 unsigned long next_tmout;
1049 if (hctx->ccid3hctx_state == TFRC_SSTATE_TERM) {
1050 ccid3_pr_debug("%s, sk=%p, received a packet when "
1051 "terminating!\n", dccp_role(sk), sk);
1055 /* we are only interested in ACKs */
1056 if (!(DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_ACK ||
1057 DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_DATAACK))
1060 opt_recv = &hctx->ccid3hctx_options_received;
1062 t_elapsed = dp->dccps_options_received.dccpor_elapsed_time;
1063 x_recv = opt_recv->ccid3or_receive_rate;
1064 pinv = opt_recv->ccid3or_loss_event_rate;
1066 switch (hctx->ccid3hctx_state) {
1067 case TFRC_SSTATE_NO_SENT:
1068 /* FIXME: what to do here? */
1070 case TFRC_SSTATE_NO_FBACK:
1071 case TFRC_SSTATE_FBACK:
1072 /* Calculate new round trip sample by
1073 * R_sample = (now - t_recvdata) - t_delay */
1074 /* get t_recvdata from history */
1075 packet = dccp_tx_hist_find_entry(&hctx->ccid3hctx_hist,
1076 DCCP_SKB_CB(skb)->dccpd_ack_seq);
1077 if (packet == NULL) {
1078 ccid3_pr_debug("%s, sk=%p, seqno %llu(%s) does't "
1079 "exist in history!\n",
1081 DCCP_SKB_CB(skb)->dccpd_ack_seq,
1082 dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type));
1087 r_sample = timeval_now_delta(&packet->dccphtx_tstamp);
1089 // r_sample -= usecs_to_jiffies(t_elapsed * 10);
1091 /* Update RTT estimate by
1092 * If (No feedback recv)
1095 * R = q * R + (1 - q) * R_sample;
1097 * q is a constant, RFC 3448 recomments 0.9
1099 if (hctx->ccid3hctx_state == TFRC_SSTATE_NO_FBACK) {
1100 ccid3_hc_tx_set_state(sk, TFRC_SSTATE_FBACK);
1101 hctx->ccid3hctx_rtt = r_sample;
1103 hctx->ccid3hctx_rtt = (hctx->ccid3hctx_rtt * 9) / 10 +
1106 ccid3_pr_debug("%s, sk=%p, New RTT estimate=%uus, "
1107 "r_sample=%us\n", dccp_role(sk), sk,
1108 hctx->ccid3hctx_rtt, r_sample);
1110 /* Update timeout interval */
1111 hctx->ccid3hctx_t_rto = max_t(u32, 4 * hctx->ccid3hctx_rtt,
1114 /* Update receive rate */
1115 hctx->ccid3hctx_x_recv = x_recv;/* X_recv in bytes per sec */
1117 /* Update loss event rate */
1118 if (pinv == ~0 || pinv == 0)
1119 hctx->ccid3hctx_p = 0;
1121 hctx->ccid3hctx_p = 1000000 / pinv;
1123 if (hctx->ccid3hctx_p < TFRC_SMALLEST_P) {
1124 hctx->ccid3hctx_p = TFRC_SMALLEST_P;
1125 ccid3_pr_debug("%s, sk=%p, Smallest p used!\n",
1130 /* unschedule no feedback timer */
1131 sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer);
1133 /* Update sending rate */
1134 ccid3_hc_tx_update_x(sk);
1136 /* Update next send time */
1137 timeval_sub_usecs(&hctx->ccid3hctx_t_nom,
1138 hctx->ccid3hctx_t_ipi);
1139 ccid3_calc_new_t_ipi(hctx);
1140 timeval_add_usecs(&hctx->ccid3hctx_t_nom,
1141 hctx->ccid3hctx_t_ipi);
1142 ccid3_calc_new_delta(hctx);
1144 /* remove all packets older than the one acked from history */
1145 dccp_tx_hist_purge_older(ccid3_tx_hist,
1146 &hctx->ccid3hctx_hist, packet);
1149 * Schedule no feedback timer to expire in
1150 * max(4 * R, 2 * s / X)
1152 next_tmout = max(hctx->ccid3hctx_t_rto,
1153 2 * usecs_div(hctx->ccid3hctx_s,
1154 hctx->ccid3hctx_x));
1156 ccid3_pr_debug("%s, sk=%p, Scheduled no feedback timer to "
1157 "expire in %lu jiffies (%luus)\n",
1159 usecs_to_jiffies(next_tmout), next_tmout);
1161 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
1162 jiffies + max_t(u32, 1, usecs_to_jiffies(next_tmout)));
1165 hctx->ccid3hctx_idle = 1;
1168 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1169 __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
1175 static void ccid3_hc_tx_insert_options(struct sock *sk, struct sk_buff *skb)
1177 const struct dccp_sock *dp = dccp_sk(sk);
1178 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1180 if (hctx == NULL || !(sk->sk_state == DCCP_OPEN ||
1181 sk->sk_state == DCCP_PARTOPEN))
1184 DCCP_SKB_CB(skb)->dccpd_ccval = hctx->ccid3hctx_last_win_count;
1187 static int ccid3_hc_tx_parse_options(struct sock *sk, unsigned char option,
1188 unsigned char len, u16 idx,
1189 unsigned char *value)
1192 struct dccp_sock *dp = dccp_sk(sk);
1193 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1194 struct ccid3_options_received *opt_recv;
1199 opt_recv = &hctx->ccid3hctx_options_received;
1201 if (opt_recv->ccid3or_seqno != dp->dccps_gsr) {
1202 opt_recv->ccid3or_seqno = dp->dccps_gsr;
1203 opt_recv->ccid3or_loss_event_rate = ~0;
1204 opt_recv->ccid3or_loss_intervals_idx = 0;
1205 opt_recv->ccid3or_loss_intervals_len = 0;
1206 opt_recv->ccid3or_receive_rate = 0;
1210 case TFRC_OPT_LOSS_EVENT_RATE:
1212 ccid3_pr_debug("%s, sk=%p, invalid len for "
1213 "TFRC_OPT_LOSS_EVENT_RATE\n",
1217 opt_recv->ccid3or_loss_event_rate = ntohl(*(u32 *)value);
1218 ccid3_pr_debug("%s, sk=%p, LOSS_EVENT_RATE=%u\n",
1220 opt_recv->ccid3or_loss_event_rate);
1223 case TFRC_OPT_LOSS_INTERVALS:
1224 opt_recv->ccid3or_loss_intervals_idx = idx;
1225 opt_recv->ccid3or_loss_intervals_len = len;
1226 ccid3_pr_debug("%s, sk=%p, LOSS_INTERVALS=(%u, %u)\n",
1228 opt_recv->ccid3or_loss_intervals_idx,
1229 opt_recv->ccid3or_loss_intervals_len);
1231 case TFRC_OPT_RECEIVE_RATE:
1233 ccid3_pr_debug("%s, sk=%p, invalid len for "
1234 "TFRC_OPT_RECEIVE_RATE\n",
1238 opt_recv->ccid3or_receive_rate = ntohl(*(u32 *)value);
1239 ccid3_pr_debug("%s, sk=%p, RECEIVE_RATE=%u\n",
1241 opt_recv->ccid3or_receive_rate);
1249 static int ccid3_hc_tx_init(struct sock *sk)
1251 struct dccp_sock *dp = dccp_sk(sk);
1252 struct ccid3_hc_tx_sock *hctx;
1254 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1256 hctx = dp->dccps_hc_tx_ccid_private = kmalloc(sizeof(*hctx),
1261 memset(hctx, 0, sizeof(*hctx));
1263 if (dp->dccps_avg_packet_size >= TFRC_MIN_PACKET_SIZE &&
1264 dp->dccps_avg_packet_size <= TFRC_MAX_PACKET_SIZE)
1265 hctx->ccid3hctx_s = (u16)dp->dccps_avg_packet_size;
1267 hctx->ccid3hctx_s = TFRC_STD_PACKET_SIZE;
1269 /* Set transmission rate to 1 packet per second */
1270 hctx->ccid3hctx_x = hctx->ccid3hctx_s;
1271 hctx->ccid3hctx_t_rto = USEC_PER_SEC;
1272 hctx->ccid3hctx_state = TFRC_SSTATE_NO_SENT;
1273 INIT_LIST_HEAD(&hctx->ccid3hctx_hist);
1274 init_timer(&hctx->ccid3hctx_no_feedback_timer);
1279 static void ccid3_hc_tx_exit(struct sock *sk)
1281 struct dccp_sock *dp = dccp_sk(sk);
1282 struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1284 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1285 BUG_ON(hctx == NULL);
1287 ccid3_hc_tx_set_state(sk, TFRC_SSTATE_TERM);
1288 sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer);
1290 /* Empty packet history */
1291 dccp_tx_hist_purge(ccid3_tx_hist, &hctx->ccid3hctx_hist);
1293 kfree(dp->dccps_hc_tx_ccid_private);
1294 dp->dccps_hc_tx_ccid_private = NULL;
1298 * RX Half Connection methods
1301 /* TFRC receiver states */
1302 enum ccid3_hc_rx_states {
1303 TFRC_RSTATE_NO_DATA = 1,
1305 TFRC_RSTATE_TERM = 127,
1309 static const char *ccid3_rx_state_name(enum ccid3_hc_rx_states state)
1311 static char *ccid3_rx_state_names[] = {
1312 [TFRC_RSTATE_NO_DATA] = "NO_DATA",
1313 [TFRC_RSTATE_DATA] = "DATA",
1314 [TFRC_RSTATE_TERM] = "TERM",
1317 return ccid3_rx_state_names[state];
1321 static inline void ccid3_hc_rx_set_state(struct sock *sk,
1322 enum ccid3_hc_rx_states state)
1324 struct dccp_sock *dp = dccp_sk(sk);
1325 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1326 enum ccid3_hc_rx_states oldstate = hcrx->ccid3hcrx_state;
1328 ccid3_pr_debug("%s(%p) %-8.8s -> %s\n",
1329 dccp_role(sk), sk, ccid3_rx_state_name(oldstate),
1330 ccid3_rx_state_name(state));
1331 WARN_ON(state == oldstate);
1332 hcrx->ccid3hcrx_state = state;
1335 static int ccid3_hc_rx_add_hist(struct sock *sk,
1336 struct dccp_rx_hist_entry *packet)
1338 struct dccp_sock *dp = dccp_sk(sk);
1339 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1340 struct dccp_rx_hist_entry *entry, *next, *iter;
1343 iter = dccp_rx_hist_head(&hcrx->ccid3hcrx_hist);
1345 dccp_rx_hist_add_entry(&hcrx->ccid3hcrx_hist, packet);
1347 const u64 seqno = packet->dccphrx_seqno;
1349 if (after48(seqno, iter->dccphrx_seqno))
1350 dccp_rx_hist_add_entry(&hcrx->ccid3hcrx_hist, packet);
1352 if (dccp_rx_hist_entry_data_packet(iter))
1355 list_for_each_entry_continue(iter,
1356 &hcrx->ccid3hcrx_hist,
1358 if (after48(seqno, iter->dccphrx_seqno)) {
1359 dccp_rx_hist_add_entry(&iter->dccphrx_node,
1364 if (dccp_rx_hist_entry_data_packet(iter))
1367 if (num_later == TFRC_RECV_NUM_LATE_LOSS) {
1368 dccp_rx_hist_entry_delete(ccid3_rx_hist,
1370 ccid3_pr_debug("%s, sk=%p, packet"
1371 "(%llu) already lost!\n",
1378 if (num_later < TFRC_RECV_NUM_LATE_LOSS)
1379 dccp_rx_hist_add_entry(&hcrx->ccid3hcrx_hist,
1382 * FIXME: else what? should we destroy the packet
1390 * Trim history (remove all packets after the NUM_LATE_LOSS + 1
1393 num_later = TFRC_RECV_NUM_LATE_LOSS + 1;
1395 if (!list_empty(&hcrx->ccid3hcrx_li_hist)) {
1396 list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
1398 if (num_later == 0) {
1399 list_del_init(&entry->dccphrx_node);
1400 dccp_rx_hist_entry_delete(ccid3_rx_hist, entry);
1401 } else if (dccp_rx_hist_entry_data_packet(entry))
1406 u8 win_count = 0; /* Not needed, but lets shut up gcc */
1409 * We have no loss interval history so we need at least one
1410 * rtt:s of data packets to approximate rtt.
1412 list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
1414 if (num_later == 0) {
1418 /* OK, find next data packet */
1423 /* OK, find next data packet */
1425 win_count = entry->dccphrx_ccval;
1428 tmp = win_count - entry->dccphrx_ccval;
1430 tmp += TFRC_WIN_COUNT_LIMIT;
1431 if (tmp > TFRC_WIN_COUNT_PER_RTT + 1) {
1433 * We have found a packet older
1434 * than one rtt remove the rest
1437 } else /* OK, find next data packet */
1441 list_del_init(&entry->dccphrx_node);
1442 dccp_rx_hist_entry_delete(ccid3_rx_hist,
1446 } else if (dccp_rx_hist_entry_data_packet(entry))
1454 static void ccid3_hc_rx_send_feedback(struct sock *sk)
1456 struct dccp_sock *dp = dccp_sk(sk);
1457 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1458 struct dccp_rx_hist_entry *packet;
1461 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1463 do_gettimeofday(&now);
1465 switch (hcrx->ccid3hcrx_state) {
1466 case TFRC_RSTATE_NO_DATA:
1467 hcrx->ccid3hcrx_x_recv = 0;
1469 case TFRC_RSTATE_DATA: {
1470 const u32 delta = timeval_delta(&now,
1471 &hcrx->ccid3hcrx_tstamp_last_feedback);
1473 hcrx->ccid3hcrx_x_recv = (hcrx->ccid3hcrx_bytes_recv *
1475 if (likely(delta > 1))
1476 hcrx->ccid3hcrx_x_recv /= delta;
1480 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1481 __FUNCTION__, dccp_role(sk), sk, hcrx->ccid3hcrx_state);
1486 packet = dccp_rx_hist_find_data_packet(&hcrx->ccid3hcrx_hist);
1487 if (packet == NULL) {
1488 printk(KERN_CRIT "%s: %s, sk=%p, no data packet in history!\n",
1489 __FUNCTION__, dccp_role(sk), sk);
1494 hcrx->ccid3hcrx_tstamp_last_feedback = now;
1495 hcrx->ccid3hcrx_last_counter = packet->dccphrx_ccval;
1496 hcrx->ccid3hcrx_seqno_last_counter = packet->dccphrx_seqno;
1497 hcrx->ccid3hcrx_bytes_recv = 0;
1499 /* Convert to multiples of 10us */
1500 hcrx->ccid3hcrx_elapsed_time =
1501 timeval_delta(&now, &packet->dccphrx_tstamp) / 10;
1502 if (hcrx->ccid3hcrx_p == 0)
1503 hcrx->ccid3hcrx_pinv = ~0;
1505 hcrx->ccid3hcrx_pinv = 1000000 / hcrx->ccid3hcrx_p;
1509 static void ccid3_hc_rx_insert_options(struct sock *sk, struct sk_buff *skb)
1511 const struct dccp_sock *dp = dccp_sk(sk);
1513 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1515 if (hcrx == NULL || !(sk->sk_state == DCCP_OPEN ||
1516 sk->sk_state == DCCP_PARTOPEN))
1519 DCCP_SKB_CB(skb)->dccpd_ccval = hcrx->ccid3hcrx_last_counter;
1521 if (dccp_packet_without_ack(skb))
1524 if (hcrx->ccid3hcrx_elapsed_time != 0)
1525 dccp_insert_option_elapsed_time(sk, skb,
1526 hcrx->ccid3hcrx_elapsed_time);
1527 dccp_insert_option_timestamp(sk, skb);
1528 x_recv = htonl(hcrx->ccid3hcrx_x_recv);
1529 pinv = htonl(hcrx->ccid3hcrx_pinv);
1530 dccp_insert_option(sk, skb, TFRC_OPT_LOSS_EVENT_RATE,
1531 &pinv, sizeof(pinv));
1532 dccp_insert_option(sk, skb, TFRC_OPT_RECEIVE_RATE,
1533 &x_recv, sizeof(x_recv));
1537 * args: fvalue - function value to match
1538 * returns: p closest to that value
1540 * both fvalue and p are multiplied by 1,000,000 to use ints
1542 static u32 calcx_reverse_lookup(u32 fvalue) {
1546 if (fvalue < calcx_lookup[0][1])
1548 if (fvalue <= calcx_lookup[CALCX_ARRSIZE-1][1])
1550 else if (fvalue > calcx_lookup[CALCX_ARRSIZE-1][0])
1554 while (fvalue > calcx_lookup[ctr][small])
1557 return (CALCX_SPLIT * ctr / CALCX_ARRSIZE);
1559 return (1000000 * ctr / CALCX_ARRSIZE) ;
1562 /* calculate first loss interval
1564 * returns estimated loss interval in usecs */
1566 static u32 ccid3_hc_rx_calc_first_li(struct sock *sk)
1568 struct dccp_sock *dp = dccp_sk(sk);
1569 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1570 struct dccp_rx_hist_entry *entry, *next, *tail = NULL;
1571 u32 rtt, delta, x_recv, fval, p, tmp2;
1572 struct timeval tstamp = { 0, };
1578 list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
1580 if (dccp_rx_hist_entry_data_packet(entry)) {
1585 tstamp = entry->dccphrx_tstamp;
1586 win_count = entry->dccphrx_ccval;
1590 interval = win_count - entry->dccphrx_ccval;
1592 interval += TFRC_WIN_COUNT_LIMIT;
1601 printk(KERN_CRIT "%s: %s, sk=%p, packet history contains no "
1603 __FUNCTION__, dccp_role(sk), sk);
1607 if (interval == 0) {
1608 ccid3_pr_debug("%s, sk=%p, Could not find a win_count "
1609 "interval > 0. Defaulting to 1\n",
1614 rtt = timeval_delta(&tstamp, &tail->dccphrx_tstamp) * 4 / interval;
1615 ccid3_pr_debug("%s, sk=%p, approximated RTT to %uus\n",
1616 dccp_role(sk), sk, rtt);
1620 delta = timeval_now_delta(&hcrx->ccid3hcrx_tstamp_last_feedback);
1621 x_recv = hcrx->ccid3hcrx_bytes_recv * USEC_PER_SEC;
1622 if (likely(delta > 1))
1625 tmp1 = (u64)x_recv * (u64)rtt;
1626 do_div(tmp1,10000000);
1628 fval = (hcrx->ccid3hcrx_s * 100000) / tmp2;
1629 /* do not alter order above or you will get overflow on 32 bit */
1630 p = calcx_reverse_lookup(fval);
1631 ccid3_pr_debug("%s, sk=%p, receive rate=%u bytes/s, implied "
1632 "loss rate=%u\n", dccp_role(sk), sk, x_recv, p);
1640 static void ccid3_hc_rx_update_li(struct sock *sk, u64 seq_loss, u8 win_loss)
1642 struct dccp_sock *dp = dccp_sk(sk);
1643 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1645 if (seq_loss != DCCP_MAX_SEQNO + 1 &&
1646 list_empty(&hcrx->ccid3hcrx_li_hist)) {
1647 struct dccp_li_hist_entry *li_tail;
1649 li_tail = dccp_li_hist_interval_new(ccid3_li_hist,
1650 &hcrx->ccid3hcrx_li_hist,
1651 seq_loss, win_loss);
1652 if (li_tail == NULL)
1654 li_tail->dccplih_interval = ccid3_hc_rx_calc_first_li(sk);
1656 /* FIXME: find end of interval */
1659 static void ccid3_hc_rx_detect_loss(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, *packet;
1664 struct dccp_rx_hist_entry *a_loss = NULL;
1665 struct dccp_rx_hist_entry *b_loss = NULL;
1666 u64 seq_loss = DCCP_MAX_SEQNO + 1;
1668 u8 num_later = TFRC_RECV_NUM_LATE_LOSS;
1670 list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
1672 if (num_later == 0) {
1675 } else if (dccp_rx_hist_entry_data_packet(entry))
1684 list_for_each_entry_safe_continue(entry, next, &hcrx->ccid3hcrx_hist,
1686 if (num_later == 0) {
1689 } else if (dccp_rx_hist_entry_data_packet(entry))
1693 if (a_loss == NULL) {
1694 if (list_empty(&hcrx->ccid3hcrx_li_hist)) {
1695 /* no loss event have occured yet */
1696 LIMIT_NETDEBUG("%s: TODO: find a lost data packet by "
1697 "comparing to initial seqno\n",
1701 pr_info("%s: %s, sk=%p, ERROR! Less than 4 data "
1702 "packets in history",
1703 __FUNCTION__, dccp_role(sk), sk);
1708 /* Locate a lost data packet */
1709 entry = packet = b_loss;
1710 list_for_each_entry_safe_continue(entry, next, &hcrx->ccid3hcrx_hist,
1712 u64 delta = dccp_delta_seqno(entry->dccphrx_seqno,
1713 packet->dccphrx_seqno);
1716 if (dccp_rx_hist_entry_data_packet(packet))
1719 * FIXME: check this, probably this % usage is because
1720 * in earlier drafts the ndp count was just 8 bits
1721 * long, but now it cam be up to 24 bits long.
1724 if (delta % DCCP_NDP_LIMIT !=
1725 (packet->dccphrx_ndp -
1726 entry->dccphrx_ndp) % DCCP_NDP_LIMIT)
1729 packet->dccphrx_ndp - entry->dccphrx_ndp) {
1730 seq_loss = entry->dccphrx_seqno;
1731 dccp_inc_seqno(&seq_loss);
1735 if (packet == a_loss)
1739 if (seq_loss != DCCP_MAX_SEQNO + 1)
1740 win_loss = a_loss->dccphrx_ccval;
1743 ccid3_hc_rx_update_li(sk, seq_loss, win_loss);
1746 static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
1748 struct dccp_sock *dp = dccp_sk(sk);
1749 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1750 const struct dccp_options_received *opt_recv;
1751 struct dccp_rx_hist_entry *packet;
1760 BUG_ON(!(hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA ||
1761 hcrx->ccid3hcrx_state == TFRC_RSTATE_DATA));
1763 opt_recv = &dp->dccps_options_received;
1765 switch (DCCP_SKB_CB(skb)->dccpd_type) {
1767 if (hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA)
1769 case DCCP_PKT_DATAACK:
1770 if (opt_recv->dccpor_timestamp_echo == 0)
1772 p_prev = hcrx->ccid3hcrx_rtt;
1773 do_gettimeofday(&now);
1774 hcrx->ccid3hcrx_rtt = timeval_usecs(&now) -
1775 (opt_recv->dccpor_timestamp_echo -
1776 opt_recv->dccpor_elapsed_time) * 10;
1777 if (p_prev != hcrx->ccid3hcrx_rtt)
1778 ccid3_pr_debug("%s, New RTT=%luus, elapsed time=%u\n",
1779 dccp_role(sk), hcrx->ccid3hcrx_rtt,
1780 opt_recv->dccpor_elapsed_time);
1785 ccid3_pr_debug("%s, sk=%p, not DATA/DATAACK/ACK packet(%s)\n",
1787 dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type));
1791 packet = dccp_rx_hist_entry_new(ccid3_rx_hist, opt_recv->dccpor_ndp,
1793 if (packet == NULL) {
1794 ccid3_pr_debug("%s, sk=%p, Not enough mem to add rx packet "
1795 "to history (consider it lost)!",
1800 win_count = packet->dccphrx_ccval;
1802 ins = ccid3_hc_rx_add_hist(sk, packet);
1804 if (DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_ACK)
1807 switch (hcrx->ccid3hcrx_state) {
1808 case TFRC_RSTATE_NO_DATA:
1809 ccid3_pr_debug("%s, sk=%p(%s), skb=%p, sending initial "
1812 dccp_state_name(sk->sk_state), skb);
1813 ccid3_hc_rx_send_feedback(sk);
1814 ccid3_hc_rx_set_state(sk, TFRC_RSTATE_DATA);
1816 case TFRC_RSTATE_DATA:
1817 hcrx->ccid3hcrx_bytes_recv += skb->len -
1818 dccp_hdr(skb)->dccph_doff * 4;
1822 do_gettimeofday(&now);
1823 if (timeval_delta(&now, &hcrx->ccid3hcrx_tstamp_last_ack) >=
1824 hcrx->ccid3hcrx_rtt) {
1825 hcrx->ccid3hcrx_tstamp_last_ack = now;
1826 ccid3_hc_rx_send_feedback(sk);
1830 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1831 __FUNCTION__, dccp_role(sk), sk, hcrx->ccid3hcrx_state);
1836 /* Dealing with packet loss */
1837 ccid3_pr_debug("%s, sk=%p(%s), data loss! Reacting...\n",
1838 dccp_role(sk), sk, dccp_state_name(sk->sk_state));
1840 ccid3_hc_rx_detect_loss(sk);
1841 p_prev = hcrx->ccid3hcrx_p;
1843 /* Calculate loss event rate */
1844 if (!list_empty(&hcrx->ccid3hcrx_li_hist))
1845 /* Scaling up by 1000000 as fixed decimal */
1846 hcrx->ccid3hcrx_p = 1000000 / dccp_li_hist_calc_i_mean(&hcrx->ccid3hcrx_li_hist);
1848 if (hcrx->ccid3hcrx_p > p_prev) {
1849 ccid3_hc_rx_send_feedback(sk);
1854 static int ccid3_hc_rx_init(struct sock *sk)
1856 struct dccp_sock *dp = dccp_sk(sk);
1857 struct ccid3_hc_rx_sock *hcrx;
1859 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1861 hcrx = dp->dccps_hc_rx_ccid_private = kmalloc(sizeof(*hcrx),
1866 memset(hcrx, 0, sizeof(*hcrx));
1868 if (dp->dccps_avg_packet_size >= TFRC_MIN_PACKET_SIZE &&
1869 dp->dccps_avg_packet_size <= TFRC_MAX_PACKET_SIZE)
1870 hcrx->ccid3hcrx_s = (u16)dp->dccps_avg_packet_size;
1872 hcrx->ccid3hcrx_s = TFRC_STD_PACKET_SIZE;
1874 hcrx->ccid3hcrx_state = TFRC_RSTATE_NO_DATA;
1875 INIT_LIST_HEAD(&hcrx->ccid3hcrx_hist);
1876 INIT_LIST_HEAD(&hcrx->ccid3hcrx_li_hist);
1878 * XXX this seems to be paranoid, need to think more about this, for
1879 * now start with something different than zero. -acme
1881 hcrx->ccid3hcrx_rtt = USEC_PER_SEC / 5;
1885 static void ccid3_hc_rx_exit(struct sock *sk)
1887 struct dccp_sock *dp = dccp_sk(sk);
1888 struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1890 ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1895 ccid3_hc_rx_set_state(sk, TFRC_RSTATE_TERM);
1897 /* Empty packet history */
1898 dccp_rx_hist_purge(ccid3_rx_hist, &hcrx->ccid3hcrx_hist);
1900 /* Empty loss interval history */
1901 dccp_li_hist_purge(ccid3_li_hist, &hcrx->ccid3hcrx_li_hist);
1903 kfree(dp->dccps_hc_rx_ccid_private);
1904 dp->dccps_hc_rx_ccid_private = NULL;
1907 static void ccid3_hc_rx_get_info(struct sock *sk, struct tcp_info *info)
1909 const struct dccp_sock *dp = dccp_sk(sk);
1910 const struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1915 info->tcpi_ca_state = hcrx->ccid3hcrx_state;
1916 info->tcpi_options |= TCPI_OPT_TIMESTAMPS;
1917 info->tcpi_rcv_rtt = hcrx->ccid3hcrx_rtt;
1920 static void ccid3_hc_tx_get_info(struct sock *sk, struct tcp_info *info)
1922 const struct dccp_sock *dp = dccp_sk(sk);
1923 const struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1928 info->tcpi_rto = hctx->ccid3hctx_t_rto;
1929 info->tcpi_rtt = hctx->ccid3hctx_rtt;
1932 static struct ccid ccid3 = {
1934 .ccid_name = "ccid3",
1935 .ccid_owner = THIS_MODULE,
1936 .ccid_init = ccid3_init,
1937 .ccid_exit = ccid3_exit,
1938 .ccid_hc_tx_init = ccid3_hc_tx_init,
1939 .ccid_hc_tx_exit = ccid3_hc_tx_exit,
1940 .ccid_hc_tx_send_packet = ccid3_hc_tx_send_packet,
1941 .ccid_hc_tx_packet_sent = ccid3_hc_tx_packet_sent,
1942 .ccid_hc_tx_packet_recv = ccid3_hc_tx_packet_recv,
1943 .ccid_hc_tx_insert_options = ccid3_hc_tx_insert_options,
1944 .ccid_hc_tx_parse_options = ccid3_hc_tx_parse_options,
1945 .ccid_hc_rx_init = ccid3_hc_rx_init,
1946 .ccid_hc_rx_exit = ccid3_hc_rx_exit,
1947 .ccid_hc_rx_insert_options = ccid3_hc_rx_insert_options,
1948 .ccid_hc_rx_packet_recv = ccid3_hc_rx_packet_recv,
1949 .ccid_hc_rx_get_info = ccid3_hc_rx_get_info,
1950 .ccid_hc_tx_get_info = ccid3_hc_tx_get_info,
1953 module_param(ccid3_debug, int, 0444);
1954 MODULE_PARM_DESC(ccid3_debug, "Enable debug messages");
1956 static __init int ccid3_module_init(void)
1960 ccid3_rx_hist = dccp_rx_hist_new("ccid3");
1961 if (ccid3_rx_hist == NULL)
1964 ccid3_tx_hist = dccp_tx_hist_new("ccid3");
1965 if (ccid3_tx_hist == NULL)
1968 ccid3_li_hist = dccp_li_hist_new("ccid3");
1969 if (ccid3_li_hist == NULL)
1972 rc = ccid_register(&ccid3);
1974 goto out_free_loss_interval_history;
1978 out_free_loss_interval_history:
1979 dccp_li_hist_delete(ccid3_li_hist);
1980 ccid3_li_hist = NULL;
1982 dccp_tx_hist_delete(ccid3_tx_hist);
1983 ccid3_tx_hist = NULL;
1985 dccp_rx_hist_delete(ccid3_rx_hist);
1986 ccid3_rx_hist = NULL;
1989 module_init(ccid3_module_init);
1991 static __exit void ccid3_module_exit(void)
1993 #ifdef CONFIG_IP_DCCP_UNLOAD_HACK
1995 * Hack to use while developing, so that we get rid of the control
1996 * sock, that is what keeps a refcount on dccp.ko -acme
1998 extern void dccp_ctl_sock_exit(void);
2000 dccp_ctl_sock_exit();
2002 ccid_unregister(&ccid3);
2004 if (ccid3_tx_hist != NULL) {
2005 dccp_tx_hist_delete(ccid3_tx_hist);
2006 ccid3_tx_hist = NULL;
2008 if (ccid3_rx_hist != NULL) {
2009 dccp_rx_hist_delete(ccid3_rx_hist);
2010 ccid3_rx_hist = NULL;
2012 if (ccid3_li_hist != NULL) {
2013 dccp_li_hist_delete(ccid3_li_hist);
2014 ccid3_li_hist = NULL;
2017 module_exit(ccid3_module_exit);
2019 MODULE_AUTHOR("Ian McDonald <iam4@cs.waikato.ac.nz>, "
2020 "Arnaldo Carvalho de Melo <acme@ghostprotocols.net>");
2021 MODULE_DESCRIPTION("DCCP TFRC CCID3 CCID");
2022 MODULE_LICENSE("GPL");
2023 MODULE_ALIAS("net-dccp-ccid-3");