SAFE public projects git trees. - safe/jmp/linux-2.6/blob - net/dccp/ccids/ccid3.c

   1 /*
   2  *  net/dccp/ccids/ccid3.c
   3  *
   4  *  Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand.
   5  *  Copyright (c) 2005 Ian McDonald <iam4@cs.waikato.ac.nz>
   6  *
   7  *  An implementation of the DCCP protocol
   8  *
   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/
  11  *
  12  *  This code also uses code from Lulea University, rereleased as GPL by its
  13  *  authors:
  14  *  Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
  15  *
  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>.
  19  *
  20  *  Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
  21  *
  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.
  26  *
  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.
  31  *
  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.
  35  */
  36
  37 #include <linux/config.h>
  38 #include "../ccid.h"
  39 #include "../dccp.h"
  40 #include "../packet_history.h"
  41 #include "lib/loss_interval.h"
  42 #include "ccid3.h"
  43
  44 /*
  45  * Reason for maths with 10 here is to avoid 32 bit overflow when a is big.
  46  */
  47 static inline u32 usecs_div(const u32 a, const u32 b)
  48 {
  49         const u32 tmp = a * (USEC_PER_SEC / 10);
  50         return b > 20 ? tmp / (b / 10) : tmp;
  51 }
  52
  53 static int ccid3_debug;
  54
  55 #ifdef CCID3_DEBUG
  56 #define ccid3_pr_debug(format, a...) \
  57         do { if (ccid3_debug) \
  58                 printk(KERN_DEBUG "%s: " format, __FUNCTION__, ##a); \
  59         } while (0)
  60 #else
  61 #define ccid3_pr_debug(format, a...)
  62 #endif
  63
  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;
  67
  68 static int ccid3_init(struct sock *sk)
  69 {
  70         ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
  71         return 0;
  72 }
  73
  74 static void ccid3_exit(struct sock *sk)
  75 {
  76         ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
  77 }
  78
  79 /* TFRC sender states */
  80 enum ccid3_hc_tx_states {
  81         TFRC_SSTATE_NO_SENT = 1,
  82         TFRC_SSTATE_NO_FBACK,
  83         TFRC_SSTATE_FBACK,
  84         TFRC_SSTATE_TERM,
  85 };
  86
  87 #ifdef CCID3_DEBUG
  88 static const char *ccid3_tx_state_name(enum ccid3_hc_tx_states state)
  89 {
  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",
  95         };
  96
  97         return ccid3_state_names[state];
  98 }
  99 #endif
 100
 101 static inline void ccid3_hc_tx_set_state(struct sock *sk,
 102                                          enum ccid3_hc_tx_states state)
 103 {
 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;
 107
 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;
 113 }
 114
 115 #define CALCX_ARRSIZE 500
 116
 117 #define CALCX_SPLIT 50000
 118 /* equivalent to 0.05 */
 119
 120 static const u32 calcx_lookup[CALCX_ARRSIZE][2] = {
 121         { 37172 , 8172 },
 122         { 53499 , 11567 },
 123         { 66664 , 14180 },
 124         { 78298 , 16388 },
 125         { 89021 , 18339 },
 126         { 99147 , 20108 },
 127         { 108858 , 21738 },
 128         { 118273 , 23260 },
 129         { 127474 , 24693 },
 130         { 136520 , 26052 },
 131         { 145456 , 27348 },
 132         { 154316 , 28589 },
 133         { 163130 , 29783 },
 134         { 171919 , 30935 },
 135         { 180704 , 32049 },
 136         { 189502 , 33130 },
 137         { 198328 , 34180 },
 138         { 207194 , 35202 },
 139         { 216114 , 36198 },
 140         { 225097 , 37172 },
 141         { 234153 , 38123 },
 142         { 243294 , 39055 },
 143         { 252527 , 39968 },
 144         { 261861 , 40864 },
 145         { 271305 , 41743 },
 146         { 280866 , 42607 },
 147         { 290553 , 43457 },
 148         { 300372 , 44293 },
 149         { 310333 , 45117 },
 150         { 320441 , 45929 },
 151         { 330705 , 46729 },
 152         { 341131 , 47518 },
 153         { 351728 , 48297 },
 154         { 362501 , 49066 },
 155         { 373460 , 49826 },
 156         { 384609 , 50577 },
 157         { 395958 , 51320 },
 158         { 407513 , 52054 },
 159         { 419281 , 52780 },
 160         { 431270 , 53499 },
 161         { 443487 , 54211 },
 162         { 455940 , 54916 },
 163         { 468635 , 55614 },
 164         { 481581 , 56306 },
 165         { 494785 , 56991 },
 166         { 508254 , 57671 },
 167         { 521996 , 58345 },
 168         { 536019 , 59014 },
 169         { 550331 , 59677 },
 170         { 564939 , 60335 },
 171         { 579851 , 60988 },
 172         { 595075 , 61636 },
 173         { 610619 , 62279 },
 174         { 626491 , 62918 },
 175         { 642700 , 63553 },
 176         { 659253 , 64183 },
 177         { 676158 , 64809 },
 178         { 693424 , 65431 },
 179         { 711060 , 66050 },
 180         { 729073 , 66664 },
 181         { 747472 , 67275 },
 182         { 766266 , 67882 },
 183         { 785464 , 68486 },
 184         { 805073 , 69087 },
 185         { 825103 , 69684 },
 186         { 845562 , 70278 },
 187         { 866460 , 70868 },
 188         { 887805 , 71456 },
 189         { 909606 , 72041 },
 190         { 931873 , 72623 },
 191         { 954614 , 73202 },
 192         { 977839 , 73778 },
 193         { 1001557 , 74352 },
 194         { 1025777 , 74923 },
 195         { 1050508 , 75492 },
 196         { 1075761 , 76058 },
 197         { 1101544 , 76621 },
 198         { 1127867 , 77183 },
 199         { 1154739 , 77741 },
 200         { 1182172 , 78298 },
 201         { 1210173 , 78852 },
 202         { 1238753 , 79405 },
 203         { 1267922 , 79955 },
 204         { 1297689 , 80503 },
 205         { 1328066 , 81049 },
 206         { 1359060 , 81593 },
 207         { 1390684 , 82135 },
 208         { 1422947 , 82675 },
 209         { 1455859 , 83213 },
 210         { 1489430 , 83750 },
 211         { 1523671 , 84284 },
 212         { 1558593 , 84817 },
 213         { 1594205 , 85348 },
 214         { 1630518 , 85878 },
 215         { 1667543 , 86406 },
 216         { 1705290 , 86932 },
 217         { 1743770 , 87457 },
 218         { 1782994 , 87980 },
 219         { 1822973 , 88501 },
 220         { 1863717 , 89021 },
 221         { 1905237 , 89540 },
 222         { 1947545 , 90057 },
 223         { 1990650 , 90573 },
 224         { 2034566 , 91087 },
 225         { 2079301 , 91600 },
 226         { 2124869 , 92111 },
 227         { 2171279 , 92622 },
 228         { 2218543 , 93131 },
 229         { 2266673 , 93639 },
 230         { 2315680 , 94145 },
 231         { 2365575 , 94650 },
 232         { 2416371 , 95154 },
 233         { 2468077 , 95657 },
 234         { 2520707 , 96159 },
 235         { 2574271 , 96660 },
 236         { 2628782 , 97159 },
 237         { 2684250 , 97658 },
 238         { 2740689 , 98155 },
 239         { 2798110 , 98651 },
 240         { 2856524 , 99147 },
 241         { 2915944 , 99641 },
 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 }
 621 };
 622
 623 /* Calculate the send rate as per section 3.1 of RFC3448
 624
 625 Returns send rate in bytes per second
 626
 627 Integer maths and lookups are used as not allowed floating point in kernel
 628
 629 The function for Xcalc as per section 3.1 of RFC3448 is:
 630
 631 X =                            s
 632      -------------------------------------------------------------
 633      R*sqrt(2*b*p/3) + (t_RTO * (3*sqrt(3*b*p/8) * p * (1+32*p^2)))
 634
 635 where
 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
 643
 644 we can assume that b = 1 and t_RTO is 4 * R. With this the equation becomes:
 645
 646 X =                            s
 647      -----------------------------------------------------------------------
 648      R * sqrt(2 * p / 3) + (12 * R * (sqrt(3 * p / 8) * p * (1 + 32 * p^2)))
 649
 650
 651 which we can break down into:
 652
 653 X =     s
 654      --------
 655      R * f(p)
 656
 657 where f(p) = sqrt(2 * p / 3) + (12 * sqrt(3 * p / 8) * p * (1 + 32 * p * p))
 658
 659 Function parameters:
 660 s - bytes
 661 R - RTT in usecs
 662 p - loss rate (decimal fraction multiplied by 1,000,000)
 663
 664 Returns Xcalc in bytes per second
 665
 666 DON'T alter this code unless you run test cases against it as the code
 667 has been manipulated to stop underflow/overlow.
 668
 669 */
 670 static u32 ccid3_calc_x(u16 s, u32 R, u32 p)
 671 {
 672         int index;
 673         u32 f;
 674         u64 tmp1, tmp2;
 675
 676         if (p < CALCX_SPLIT)
 677                 index = (p / (CALCX_SPLIT / CALCX_ARRSIZE)) - 1;
 678         else
 679                 index = (p / (1000000 / CALCX_ARRSIZE)) - 1;
 680
 681         if (index < 0)
 682                 /* p should be 0 unless there is a bug in my code */
 683                 index = 0;
 684
 685         if (R == 0)
 686                 R = 1; /* RTT can't be zero or else divide by zero */
 687
 688         BUG_ON(index >= CALCX_ARRSIZE);
 689
 690         if (p >= CALCX_SPLIT)
 691                 f = calcx_lookup[index][0];
 692         else
 693                 f = calcx_lookup[index][1];
 694
 695         tmp1 = ((u64)s * 100000000);
 696         tmp2 = ((u64)R * (u64)f);
 697         do_div(tmp2,10000);
 698         do_div(tmp1,tmp2);
 699         /* don't alter above math unless you test due to overflow on 32 bit */
 700
 701         return (u32)tmp1;
 702 }
 703
 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)
 706 {
 707         /*
 708          * If no feedback spec says t_ipi is 1 second (set elsewhere and then
 709          * doubles after every no feedback timer (separate function)
 710          */
 711         if (hctx->ccid3hctx_state != TFRC_SSTATE_NO_FBACK)
 712                 hctx->ccid3hctx_t_ipi = usecs_div(hctx->ccid3hctx_s,
 713                                                   hctx->ccid3hctx_x);
 714 }
 715
 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)
 718 {
 719         hctx->ccid3hctx_delta = min_t(u32, hctx->ccid3hctx_t_ipi / 2,
 720                                            TFRC_OPSYS_HALF_TIME_GRAN);
 721 }
 722
 723 /*
 724  * Update X by
 725  *    If (p > 0)
 726  *       x_calc = calcX(s, R, p);
 727  *       X = max(min(X_calc, 2 * X_recv), s / t_mbi);
 728  *    Else
 729  *       If (now - tld >= R)
 730  *          X = max(min(2 * X, 2 * X_recv), s / R);
 731  *          tld = now;
 732  */
 733 static void ccid3_hc_tx_update_x(struct sock *sk)
 734 {
 735         struct dccp_sock *dp = dccp_sk(sk);
 736         struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
 737
 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,
 741                                                       hctx->ccid3hctx_rtt,
 742                                                       hctx->ccid3hctx_p);
 743                 hctx->ccid3hctx_x = max_t(u32, min_t(u32, hctx->ccid3hctx_x_calc,
 744                                                           2 * hctx->ccid3hctx_x_recv),
 745                                                (hctx->ccid3hctx_s /
 746                                                 TFRC_MAX_BACK_OFF_TIME));
 747         } else {
 748                 struct timeval now;
 749
 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;
 758                 }
 759         }
 760 }
 761
 762 static void ccid3_hc_tx_no_feedback_timer(unsigned long data)
 763 {
 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;
 768
 769         bh_lock_sock(sk);
 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,
 774                                jiffies + HZ / 5);
 775                 goto out;
 776         }
 777
 778         ccid3_pr_debug("%s, sk=%p, state=%s\n", dccp_role(sk), sk,
 779                        ccid3_tx_state_name(hctx->ccid3hctx_state));
 780
 781         switch (hctx->ccid3hctx_state) {
 782         case TFRC_SSTATE_TERM:
 783                 goto out;
 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);
 791
 792                 ccid3_pr_debug("%s, sk=%p, state=%s, updated tx rate to %d "
 793                                "bytes/s\n",
 794                                dccp_role(sk), sk,
 795                                ccid3_tx_state_name(hctx->ccid3hctx_state),
 796                                hctx->ccid3hctx_x);
 797                 next_tmout = max_t(u32, 2 * usecs_div(hctx->ccid3hctx_s,
 798                                                       hctx->ccid3hctx_x),
 799                                         TFRC_INITIAL_TIMEOUT);
 800                 /*
 801                  * FIXME - not sure above calculation is correct. See section
 802                  * 5 of CCID3 11 should adjust tx_t_ipi and double that to
 803                  * achieve it really
 804                  */
 805                 break;
 806         case TFRC_SSTATE_FBACK:
 807                 /*
 808                  * Check if IDLE since last timeout and recv rate is less than
 809                  * 4 packets per RTT
 810                  */
 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",
 815                                        dccp_role(sk), sk,
 816                                        ccid3_tx_state_name(hctx->ccid3hctx_state));
 817                         /* Halve sending rate */
 818
 819                         /*  If (X_calc > 2 * X_recv)
 820                          *    X_recv = max(X_recv / 2, s / (2 * t_mbi));
 821                          *  Else
 822                          *    X_recv = X_calc / 4;
 823                          */
 824                         BUG_ON(hctx->ccid3hctx_p >= TFRC_SMALLEST_P &&
 825                                hctx->ccid3hctx_x_calc == 0);
 826
 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));
 832                         else
 833                                 hctx->ccid3hctx_x_recv = hctx->ccid3hctx_x_calc / 4;
 834
 835                         /* Update sending rate */
 836                         ccid3_hc_tx_update_x(sk);
 837                 }
 838                 /*
 839                  * Schedule no feedback timer to expire in
 840                  * max(4 * R, 2 * s / X)
 841                  */
 842                 next_tmout = max_t(u32, hctx->ccid3hctx_t_rto,
 843                                         2 * usecs_div(hctx->ccid3hctx_s,
 844                                                       hctx->ccid3hctx_x));
 845                 break;
 846         default:
 847                 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
 848                        __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
 849                 dump_stack();
 850                 goto out;
 851         }
 852
 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;
 856 out:
 857         bh_unlock_sock(sk);
 858         sock_put(sk);
 859 }
 860
 861 static int ccid3_hc_tx_send_packet(struct sock *sk,
 862                                    struct sk_buff *skb, int len)
 863 {
 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;
 867         struct timeval now;
 868         long delay;
 869         int rc = -ENOTCONN;
 870
 871         /* Check if pure ACK or Terminating*/
 872
 873         /*
 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"?
 876          */
 877         if (hctx == NULL || len == 0 ||
 878             hctx->ccid3hctx_state == TFRC_SSTATE_TERM)
 879                 goto out;
 880
 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,
 885                                                     SLAB_ATOMIC);
 886
 887                 rc = -ENOBUFS;
 888                 if (new_packet == NULL) {
 889                         ccid3_pr_debug("%s, sk=%p, not enough mem to add "
 890                                        "to history, send refused\n",
 891                                        dccp_role(sk), sk);
 892                         goto out;
 893                 }
 894
 895                 dccp_tx_hist_add_entry(&hctx->ccid3hctx_hist, new_packet);
 896         }
 897
 898         do_gettimeofday(&now);
 899
 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);
 904
 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;
 913
 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);
 919                 rc = 0;
 920                 break;
 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);
 926                 delay /= -1000;
 927                 /* divide by -1000 is to convert to ms and get sign right */
 928                 rc = delay > 0 ? delay : 0;
 929                 break;
 930         default:
 931                 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
 932                        __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
 933                 dump_stack();
 934                 rc = -EINVAL;
 935                 break;
 936         }
 937
 938         /* Can we send? if so add options and add to packet history */
 939         if (rc == 0)
 940                 new_packet->dccphtx_ccval =
 941                         DCCP_SKB_CB(skb)->dccpd_ccval =
 942                                 hctx->ccid3hctx_last_win_count;
 943 out:
 944         return rc;
 945 }
 946
 947 static void ccid3_hc_tx_packet_sent(struct sock *sk, int more, int len)
 948 {
 949         struct dccp_sock *dp = dccp_sk(sk);
 950         struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
 951         struct timeval now;
 952
 953         BUG_ON(hctx == NULL);
 954
 955         if (hctx->ccid3hctx_state == TFRC_SSTATE_TERM) {
 956                 ccid3_pr_debug("%s, sk=%p, while state is TFRC_SSTATE_TERM!\n",
 957                                dccp_role(sk), sk);
 958                 return;
 959         }
 960
 961         do_gettimeofday(&now);
 962
 963         /* check if we have sent a data packet */
 964         if (len > 0) {
 965                 unsigned long quarter_rtt;
 966                 struct dccp_tx_hist_entry *packet;
 967
 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__);
 972                         return;
 973                 }
 974                 if (packet->dccphtx_sent) {
 975                         printk(KERN_CRIT "%s: no unsent packet in history!\n",
 976                                __FUNCTION__);
 977                         return;
 978                 }
 979                 packet->dccphtx_tstamp = now;
 980                 packet->dccphtx_seqno  = dp->dccps_gss;
 981                 /*
 982                  * Check if win_count have changed
 983                  * Algorithm in "8.1. Window Counter Valuer" in
 984                  * draft-ietf-dccp-ccid3-11.txt
 985                  */
 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;
 989
 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 "
 995                                        "%u to %u!\n",
 996                                        dccp_role(sk), sk,
 997                                        packet->dccphtx_ccval,
 998                                        hctx->ccid3hctx_last_win_count);
 999                 }
1000
1001                 hctx->ccid3hctx_idle = 0;
1002                 packet->dccphtx_rtt  = hctx->ccid3hctx_rtt;
1003                 packet->dccphtx_sent = 1;
1004         } else
1005                 ccid3_pr_debug("%s, sk=%p, seqno=%llu NOT inserted!\n",
1006                                dccp_role(sk), sk, dp->dccps_gss);
1007
1008         switch (hctx->ccid3hctx_state) {
1009         case TFRC_SSTATE_NO_SENT:
1010                 /* if first wasn't pure ack */
1011                 if (len != 0)
1012                         printk(KERN_CRIT "%s: %s, First packet sent is noted "
1013                                          "as a data packet\n",
1014                                __FUNCTION__, dccp_role(sk));
1015                 return;
1016         case TFRC_SSTATE_NO_FBACK:
1017         case TFRC_SSTATE_FBACK:
1018                 if (len > 0) {
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);
1024                 }
1025                 break;
1026         default:
1027                 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1028                        __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
1029                 dump_stack();
1030                 break;
1031         }
1032 }
1033
1034 static void ccid3_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
1035 {
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;
1041         u32 t_elapsed;
1042         u32 pinv;
1043         u32 x_recv;
1044         u32 r_sample;
1045
1046         if (hctx == NULL)
1047                 return;
1048
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);
1052                 return;
1053         }
1054
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))
1058                 return;
1059
1060         opt_recv = &hctx->ccid3hctx_options_received;
1061
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;
1065
1066         switch (hctx->ccid3hctx_state) {
1067         case TFRC_SSTATE_NO_SENT:
1068                 /* FIXME: what to do here? */
1069                 return;
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",
1080                                        dccp_role(sk), sk,
1081                                        DCCP_SKB_CB(skb)->dccpd_ack_seq,
1082                                        dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type));
1083                         return;
1084                 }
1085
1086                 /* Update RTT */
1087                 r_sample = timeval_now_delta(&packet->dccphtx_tstamp);
1088                 /* FIXME: */
1089                 // r_sample -= usecs_to_jiffies(t_elapsed * 10);
1090
1091                 /* Update RTT estimate by
1092                  * If (No feedback recv)
1093                  *    R = R_sample;
1094                  * Else
1095                  *    R = q * R + (1 - q) * R_sample;
1096                  *
1097                  * q is a constant, RFC 3448 recomments 0.9
1098                  */
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;
1102                 } else
1103                         hctx->ccid3hctx_rtt = (hctx->ccid3hctx_rtt * 9) / 10 +
1104                                               r_sample / 10;
1105
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);
1109
1110                 /* Update timeout interval */
1111                 hctx->ccid3hctx_t_rto = max_t(u32, 4 * hctx->ccid3hctx_rtt,
1112                                               USEC_PER_SEC);
1113
1114                 /* Update receive rate */
1115                 hctx->ccid3hctx_x_recv = x_recv;/* X_recv in bytes per sec */
1116
1117                 /* Update loss event rate */
1118                 if (pinv == ~0 || pinv == 0)
1119                         hctx->ccid3hctx_p = 0;
1120                 else {
1121                         hctx->ccid3hctx_p = 1000000 / pinv;
1122
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",
1126                                                dccp_role(sk), sk);
1127                         }
1128                 }
1129
1130                 /* unschedule no feedback timer */
1131                 sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer);
1132
1133                 /* Update sending rate */
1134                 ccid3_hc_tx_update_x(sk);
1135
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);
1143
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);
1147
1148                 /*
1149                  * Schedule no feedback timer to expire in
1150                  * max(4 * R, 2 * s / X)
1151                  */
1152                 next_tmout = max(hctx->ccid3hctx_t_rto,
1153                                  2 * usecs_div(hctx->ccid3hctx_s,
1154                                                hctx->ccid3hctx_x));
1155
1156                 ccid3_pr_debug("%s, sk=%p, Scheduled no feedback timer to "
1157                                "expire in %lu jiffies (%luus)\n",
1158                                dccp_role(sk), sk,
1159                                usecs_to_jiffies(next_tmout), next_tmout);
1160
1161                 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
1162                                jiffies + max_t(u32, 1, usecs_to_jiffies(next_tmout)));
1163
1164                 /* set idle flag */
1165                 hctx->ccid3hctx_idle = 1;
1166                 break;
1167         default:
1168                 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1169                        __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
1170                 dump_stack();
1171                 break;
1172         }
1173 }
1174
1175 static void ccid3_hc_tx_insert_options(struct sock *sk, struct sk_buff *skb)
1176 {
1177         const struct dccp_sock *dp = dccp_sk(sk);
1178         struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1179
1180         if (hctx == NULL || !(sk->sk_state == DCCP_OPEN ||
1181                               sk->sk_state == DCCP_PARTOPEN))
1182                 return;
1183
1184          DCCP_SKB_CB(skb)->dccpd_ccval = hctx->ccid3hctx_last_win_count;
1185 }
1186
1187 static int ccid3_hc_tx_parse_options(struct sock *sk, unsigned char option,
1188                                      unsigned char len, u16 idx,
1189                                      unsigned char *value)
1190 {
1191         int rc = 0;
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;
1195
1196         if (hctx == NULL)
1197                 return 0;
1198
1199         opt_recv = &hctx->ccid3hctx_options_received;
1200
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;
1207         }
1208
1209         switch (option) {
1210         case TFRC_OPT_LOSS_EVENT_RATE:
1211                 if (len != 4) {
1212                         ccid3_pr_debug("%s, sk=%p, invalid len for "
1213                                        "TFRC_OPT_LOSS_EVENT_RATE\n",
1214                                        dccp_role(sk), sk);
1215                         rc = -EINVAL;
1216                 } else {
1217                         opt_recv->ccid3or_loss_event_rate = ntohl(*(u32 *)value);
1218                         ccid3_pr_debug("%s, sk=%p, LOSS_EVENT_RATE=%u\n",
1219                                        dccp_role(sk), sk,
1220                                        opt_recv->ccid3or_loss_event_rate);
1221                 }
1222                 break;
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",
1227                                dccp_role(sk), sk,
1228                                opt_recv->ccid3or_loss_intervals_idx,
1229                                opt_recv->ccid3or_loss_intervals_len);
1230                 break;
1231         case TFRC_OPT_RECEIVE_RATE:
1232                 if (len != 4) {
1233                         ccid3_pr_debug("%s, sk=%p, invalid len for "
1234                                        "TFRC_OPT_RECEIVE_RATE\n",
1235                                        dccp_role(sk), sk);
1236                         rc = -EINVAL;
1237                 } else {
1238                         opt_recv->ccid3or_receive_rate = ntohl(*(u32 *)value);
1239                         ccid3_pr_debug("%s, sk=%p, RECEIVE_RATE=%u\n",
1240                                        dccp_role(sk), sk,
1241                                        opt_recv->ccid3or_receive_rate);
1242                 }
1243                 break;
1244         }
1245
1246         return rc;
1247 }
1248
1249 static int ccid3_hc_tx_init(struct sock *sk)
1250 {
1251         struct dccp_sock *dp = dccp_sk(sk);
1252         struct ccid3_hc_tx_sock *hctx;
1253
1254         ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1255
1256         hctx = dp->dccps_hc_tx_ccid_private = kmalloc(sizeof(*hctx),
1257                                                       gfp_any());
1258         if (hctx == NULL)
1259                 return -ENOMEM;
1260
1261         memset(hctx, 0, sizeof(*hctx));
1262
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;
1266         else
1267                 hctx->ccid3hctx_s = TFRC_STD_PACKET_SIZE;
1268
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);
1275
1276         return 0;
1277 }
1278
1279 static void ccid3_hc_tx_exit(struct sock *sk)
1280 {
1281         struct dccp_sock *dp = dccp_sk(sk);
1282         struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1283
1284         ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1285         BUG_ON(hctx == NULL);
1286
1287         ccid3_hc_tx_set_state(sk, TFRC_SSTATE_TERM);
1288         sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer);
1289
1290         /* Empty packet history */
1291         dccp_tx_hist_purge(ccid3_tx_hist, &hctx->ccid3hctx_hist);
1292
1293         kfree(dp->dccps_hc_tx_ccid_private);
1294         dp->dccps_hc_tx_ccid_private = NULL;
1295 }
1296
1297 /*
1298  * RX Half Connection methods
1299  */
1300
1301 /* TFRC receiver states */
1302 enum ccid3_hc_rx_states {
1303         TFRC_RSTATE_NO_DATA = 1,
1304         TFRC_RSTATE_DATA,
1305         TFRC_RSTATE_TERM    = 127,
1306 };
1307
1308 #ifdef CCID3_DEBUG
1309 static const char *ccid3_rx_state_name(enum ccid3_hc_rx_states state)
1310 {
1311         static char *ccid3_rx_state_names[] = {
1312         [TFRC_RSTATE_NO_DATA] = "NO_DATA",
1313         [TFRC_RSTATE_DATA]    = "DATA",
1314         [TFRC_RSTATE_TERM]    = "TERM",
1315         };
1316
1317         return ccid3_rx_state_names[state];
1318 }
1319 #endif
1320
1321 static inline void ccid3_hc_rx_set_state(struct sock *sk,
1322                                          enum ccid3_hc_rx_states state)
1323 {
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;
1327
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;
1333 }
1334
1335 static int ccid3_hc_rx_add_hist(struct sock *sk,
1336                                 struct dccp_rx_hist_entry *packet)
1337 {
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;
1341         u8 num_later = 0;
1342
1343         iter = dccp_rx_hist_head(&hcrx->ccid3hcrx_hist);
1344         if (iter == NULL)
1345                 dccp_rx_hist_add_entry(&hcrx->ccid3hcrx_hist, packet);
1346         else {
1347                 const u64 seqno = packet->dccphrx_seqno;
1348
1349                 if (after48(seqno, iter->dccphrx_seqno))
1350                         dccp_rx_hist_add_entry(&hcrx->ccid3hcrx_hist, packet);
1351                 else {
1352                         if (dccp_rx_hist_entry_data_packet(iter))
1353                                 num_later = 1;
1354
1355                         list_for_each_entry_continue(iter,
1356                                                      &hcrx->ccid3hcrx_hist,
1357                                                      dccphrx_node) {
1358                                 if (after48(seqno, iter->dccphrx_seqno)) {
1359                                         dccp_rx_hist_add_entry(&iter->dccphrx_node,
1360                                                                packet);
1361                                         goto trim_history;
1362                                 }
1363
1364                                 if (dccp_rx_hist_entry_data_packet(iter))
1365                                         num_later++;
1366
1367                                 if (num_later == TFRC_RECV_NUM_LATE_LOSS) {
1368                                         dccp_rx_hist_entry_delete(ccid3_rx_hist,
1369                                                                   packet);
1370                                         ccid3_pr_debug("%s, sk=%p, packet"
1371                                                        "(%llu) already lost!\n",
1372                                                        dccp_role(sk), sk,
1373                                                        seqno);
1374                                         return 1;
1375                                 }
1376                         }
1377
1378                         if (num_later < TFRC_RECV_NUM_LATE_LOSS)
1379                                 dccp_rx_hist_add_entry(&hcrx->ccid3hcrx_hist,
1380                                                        packet);
1381                         /*
1382                          * FIXME: else what? should we destroy the packet
1383                          * like above?
1384                          */
1385                 }
1386         }
1387
1388 trim_history:
1389         /*
1390          * Trim history (remove all packets after the NUM_LATE_LOSS + 1
1391          * data packets)
1392          */
1393         num_later = TFRC_RECV_NUM_LATE_LOSS + 1;
1394
1395         if (!list_empty(&hcrx->ccid3hcrx_li_hist)) {
1396                 list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
1397                                          dccphrx_node) {
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))
1402                                 --num_later;
1403                 }
1404         } else {
1405                 int step = 0;
1406                 u8 win_count = 0; /* Not needed, but lets shut up gcc */
1407                 int tmp;
1408                 /*
1409                  * We have no loss interval history so we need at least one
1410                  * rtt:s of data packets to approximate rtt.
1411                  */
1412                 list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
1413                                          dccphrx_node) {
1414                         if (num_later == 0) {
1415                                 switch (step) {
1416                                 case 0:
1417                                         step = 1;
1418                                         /* OK, find next data packet */
1419                                         num_later = 1;
1420                                         break;
1421                                 case 1:
1422                                         step = 2;
1423                                         /* OK, find next data packet */
1424                                         num_later = 1;
1425                                         win_count = entry->dccphrx_ccval;
1426                                         break;
1427                                 case 2:
1428                                         tmp = win_count - entry->dccphrx_ccval;
1429                                         if (tmp < 0)
1430                                                 tmp += TFRC_WIN_COUNT_LIMIT;
1431                                         if (tmp > TFRC_WIN_COUNT_PER_RTT + 1) {
1432                                                 /*
1433                                                  * We have found a packet older
1434                                                  * than one rtt remove the rest
1435                                                  */
1436                                                 step = 3;
1437                                         } else /* OK, find next data packet */
1438                                                 num_later = 1;
1439                                         break;
1440                                 case 3:
1441                                         list_del_init(&entry->dccphrx_node);
1442                                         dccp_rx_hist_entry_delete(ccid3_rx_hist,
1443                                                                   entry);
1444                                         break;
1445                                 }
1446                         } else if (dccp_rx_hist_entry_data_packet(entry))
1447                                 --num_later;
1448                 }
1449         }
1450
1451         return 0;
1452 }
1453
1454 static void ccid3_hc_rx_send_feedback(struct sock *sk)
1455 {
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;
1459         struct timeval now;
1460
1461         ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1462
1463         do_gettimeofday(&now);
1464
1465         switch (hcrx->ccid3hcrx_state) {
1466         case TFRC_RSTATE_NO_DATA:
1467                 hcrx->ccid3hcrx_x_recv = 0;
1468                 break;
1469         case TFRC_RSTATE_DATA: {
1470                 const u32 delta = timeval_delta(&now,
1471                                         &hcrx->ccid3hcrx_tstamp_last_feedback);
1472
1473                 hcrx->ccid3hcrx_x_recv = (hcrx->ccid3hcrx_bytes_recv *
1474                                           USEC_PER_SEC);
1475                 if (likely(delta > 1))
1476                         hcrx->ccid3hcrx_x_recv /= delta;
1477         }
1478                 break;
1479         default:
1480                 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1481                        __FUNCTION__, dccp_role(sk), sk, hcrx->ccid3hcrx_state);
1482                 dump_stack();
1483                 return;
1484         }
1485
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);
1490                 dump_stack();
1491                 return;
1492         }
1493
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;
1498
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;
1504         else
1505                 hcrx->ccid3hcrx_pinv = 1000000 / hcrx->ccid3hcrx_p;
1506         dccp_send_ack(sk);
1507 }
1508
1509 static void ccid3_hc_rx_insert_options(struct sock *sk, struct sk_buff *skb)
1510 {
1511         const struct dccp_sock *dp = dccp_sk(sk);
1512         u32 x_recv, pinv;
1513         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1514
1515         if (hcrx == NULL || !(sk->sk_state == DCCP_OPEN ||
1516                               sk->sk_state == DCCP_PARTOPEN))
1517                 return;
1518
1519         DCCP_SKB_CB(skb)->dccpd_ccval = hcrx->ccid3hcrx_last_counter;
1520
1521         if (dccp_packet_without_ack(skb))
1522                 return;
1523
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));
1534 }
1535
1536 /*
1537  * args: fvalue - function value to match
1538  * returns:  p  closest to that value
1539  *
1540  * both fvalue and p are multiplied by 1,000,000 to use ints
1541  */
1542 static u32 calcx_reverse_lookup(u32 fvalue) {
1543         int ctr = 0;
1544         int small;
1545
1546         if (fvalue < calcx_lookup[0][1])
1547                 return 0;
1548         if (fvalue <= calcx_lookup[CALCX_ARRSIZE-1][1])
1549                 small = 1;
1550         else if (fvalue > calcx_lookup[CALCX_ARRSIZE-1][0])
1551                 return 1000000;
1552         else
1553                 small = 0;
1554         while (fvalue > calcx_lookup[ctr][small])
1555                 ctr++;
1556         if (small)
1557                 return (CALCX_SPLIT * ctr / CALCX_ARRSIZE);
1558         else
1559                 return (1000000 * ctr / CALCX_ARRSIZE) ;
1560 }
1561
1562 /* calculate first loss interval
1563  *
1564  * returns estimated loss interval in usecs */
1565
1566 static u32 ccid3_hc_rx_calc_first_li(struct sock *sk)
1567 {
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, };
1573         int interval = 0;
1574         int win_count = 0;
1575         int step = 0;
1576         u64 tmp1;
1577
1578         list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
1579                                  dccphrx_node) {
1580                 if (dccp_rx_hist_entry_data_packet(entry)) {
1581                         tail = entry;
1582
1583                         switch (step) {
1584                         case 0:
1585                                 tstamp    = entry->dccphrx_tstamp;
1586                                 win_count = entry->dccphrx_ccval;
1587                                 step = 1;
1588                                 break;
1589                         case 1:
1590                                 interval = win_count - entry->dccphrx_ccval;
1591                                 if (interval < 0)
1592                                         interval += TFRC_WIN_COUNT_LIMIT;
1593                                 if (interval > 4)
1594                                         goto found;
1595                                 break;
1596                         }
1597                 }
1598         }
1599
1600         if (step == 0) {
1601                 printk(KERN_CRIT "%s: %s, sk=%p, packet history contains no "
1602                                  "data packets!\n",
1603                        __FUNCTION__, dccp_role(sk), sk);
1604                 return ~0;
1605         }
1606
1607         if (interval == 0) {
1608                 ccid3_pr_debug("%s, sk=%p, Could not find a win_count "
1609                                "interval > 0. Defaulting to 1\n",
1610                                dccp_role(sk), sk);
1611                 interval = 1;
1612         }
1613 found:
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);
1617         if (rtt == 0)
1618                 rtt = 1;
1619
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))
1623                 x_recv /= delta;
1624
1625         tmp1 = (u64)x_recv * (u64)rtt;
1626         do_div(tmp1,10000000);
1627         tmp2 = (u32)tmp1;
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);
1633
1634         if (p == 0)
1635                 return ~0;
1636         else
1637                 return 1000000 / p;
1638 }
1639
1640 static void ccid3_hc_rx_update_li(struct sock *sk, u64 seq_loss, u8 win_loss)
1641 {
1642         struct dccp_sock *dp = dccp_sk(sk);
1643         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1644
1645         if (seq_loss != DCCP_MAX_SEQNO + 1 &&
1646             list_empty(&hcrx->ccid3hcrx_li_hist)) {
1647                 struct dccp_li_hist_entry *li_tail;
1648
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)
1653                         return;
1654                 li_tail->dccplih_interval = ccid3_hc_rx_calc_first_li(sk);
1655         }
1656         /* FIXME: find end of interval */
1657 }
1658
1659 static void ccid3_hc_rx_detect_loss(struct sock *sk)
1660 {
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;
1667         u8 win_loss = 0;
1668         u8 num_later = TFRC_RECV_NUM_LATE_LOSS;
1669
1670         list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
1671                                  dccphrx_node) {
1672                 if (num_later == 0) {
1673                         b_loss = entry;
1674                         break;
1675                 } else if (dccp_rx_hist_entry_data_packet(entry))
1676                         --num_later;
1677         }
1678
1679         if (b_loss == NULL)
1680                 goto out_update_li;
1681
1682         num_later = 1;
1683
1684         list_for_each_entry_safe_continue(entry, next, &hcrx->ccid3hcrx_hist,
1685                                           dccphrx_node) {
1686                 if (num_later == 0) {
1687                         a_loss = entry;
1688                         break;
1689                 } else if (dccp_rx_hist_entry_data_packet(entry))
1690                         --num_later;
1691         }
1692
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",
1698                                        dccp_role(sk));
1699                         goto out_update_li;
1700                 } else {
1701                         pr_info("%s: %s, sk=%p, ERROR! Less than 4 data "
1702                                 "packets in history",
1703                                 __FUNCTION__, dccp_role(sk), sk);
1704                         return;
1705                 }
1706         }
1707
1708         /* Locate a lost data packet */
1709         entry = packet = b_loss;
1710         list_for_each_entry_safe_continue(entry, next, &hcrx->ccid3hcrx_hist,
1711                                           dccphrx_node) {
1712                 u64 delta = dccp_delta_seqno(entry->dccphrx_seqno,
1713                                              packet->dccphrx_seqno);
1714
1715                 if (delta != 0) {
1716                         if (dccp_rx_hist_entry_data_packet(packet))
1717                                 --delta;
1718                         /*
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.
1722                          */
1723 #if 0
1724                         if (delta % DCCP_NDP_LIMIT !=
1725                             (packet->dccphrx_ndp -
1726                              entry->dccphrx_ndp) % DCCP_NDP_LIMIT)
1727 #endif
1728                         if (delta !=
1729                              packet->dccphrx_ndp - entry->dccphrx_ndp) {
1730                                 seq_loss = entry->dccphrx_seqno;
1731                                 dccp_inc_seqno(&seq_loss);
1732                         }
1733                 }
1734                 packet = entry;
1735                 if (packet == a_loss)
1736                         break;
1737         }
1738
1739         if (seq_loss != DCCP_MAX_SEQNO + 1)
1740                 win_loss = a_loss->dccphrx_ccval;
1741
1742 out_update_li:
1743         ccid3_hc_rx_update_li(sk, seq_loss, win_loss);
1744 }
1745
1746 static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
1747 {
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;
1752         struct timeval now;
1753         u8 win_count;
1754         u32 p_prev;
1755         int ins;
1756
1757         if (hcrx == NULL)
1758                 return;
1759
1760         BUG_ON(!(hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA ||
1761                  hcrx->ccid3hcrx_state == TFRC_RSTATE_DATA));
1762
1763         opt_recv = &dp->dccps_options_received;
1764
1765         switch (DCCP_SKB_CB(skb)->dccpd_type) {
1766         case DCCP_PKT_ACK:
1767                 if (hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA)
1768                         return;
1769         case DCCP_PKT_DATAACK:
1770                 if (opt_recv->dccpor_timestamp_echo == 0)
1771                         break;
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);
1781                 break;
1782         case DCCP_PKT_DATA:
1783                 break;
1784         default:
1785                 ccid3_pr_debug("%s, sk=%p, not DATA/DATAACK/ACK packet(%s)\n",
1786                                dccp_role(sk), sk,
1787                                dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type));
1788                 return;
1789         }
1790
1791         packet = dccp_rx_hist_entry_new(ccid3_rx_hist, opt_recv->dccpor_ndp,
1792                                         skb, SLAB_ATOMIC);
1793         if (packet == NULL) {
1794                 ccid3_pr_debug("%s, sk=%p, Not enough mem to add rx packet "
1795                                "to history (consider it lost)!",
1796                                dccp_role(sk), sk);
1797                 return;
1798         }
1799
1800         win_count = packet->dccphrx_ccval;
1801
1802         ins = ccid3_hc_rx_add_hist(sk, packet);
1803
1804         if (DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_ACK)
1805                 return;
1806
1807         switch (hcrx->ccid3hcrx_state) {
1808         case TFRC_RSTATE_NO_DATA:
1809                 ccid3_pr_debug("%s, sk=%p(%s), skb=%p, sending initial "
1810                                "feedback\n",
1811                                dccp_role(sk), sk,
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);
1815                 return;
1816         case TFRC_RSTATE_DATA:
1817                 hcrx->ccid3hcrx_bytes_recv += skb->len -
1818                                               dccp_hdr(skb)->dccph_doff * 4;
1819                 if (ins != 0)
1820                         break;
1821
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);
1827                 }
1828                 return;
1829         default:
1830                 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1831                        __FUNCTION__, dccp_role(sk), sk, hcrx->ccid3hcrx_state);
1832                 dump_stack();
1833                 return;
1834         }
1835
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));
1839
1840         ccid3_hc_rx_detect_loss(sk);
1841         p_prev = hcrx->ccid3hcrx_p;
1842
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);
1847
1848         if (hcrx->ccid3hcrx_p > p_prev) {
1849                 ccid3_hc_rx_send_feedback(sk);
1850                 return;
1851         }
1852 }
1853
1854 static int ccid3_hc_rx_init(struct sock *sk)
1855 {
1856         struct dccp_sock *dp = dccp_sk(sk);
1857         struct ccid3_hc_rx_sock *hcrx;
1858
1859         ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1860
1861         hcrx = dp->dccps_hc_rx_ccid_private = kmalloc(sizeof(*hcrx),
1862                                                       gfp_any());
1863         if (hcrx == NULL)
1864                 return -ENOMEM;
1865
1866         memset(hcrx, 0, sizeof(*hcrx));
1867
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;
1871         else
1872                 hcrx->ccid3hcrx_s = TFRC_STD_PACKET_SIZE;
1873
1874         hcrx->ccid3hcrx_state = TFRC_RSTATE_NO_DATA;
1875         INIT_LIST_HEAD(&hcrx->ccid3hcrx_hist);
1876         INIT_LIST_HEAD(&hcrx->ccid3hcrx_li_hist);
1877         /*
1878          * XXX this seems to be paranoid, need to think more about this, for
1879          * now start with something different than zero. -acme
1880          */
1881         hcrx->ccid3hcrx_rtt = USEC_PER_SEC / 5;
1882         return 0;
1883 }
1884
1885 static void ccid3_hc_rx_exit(struct sock *sk)
1886 {
1887         struct dccp_sock *dp = dccp_sk(sk);
1888         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1889
1890         ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1891
1892         if (hcrx == NULL)
1893                 return;
1894
1895         ccid3_hc_rx_set_state(sk, TFRC_RSTATE_TERM);
1896
1897         /* Empty packet history */
1898         dccp_rx_hist_purge(ccid3_rx_hist, &hcrx->ccid3hcrx_hist);
1899
1900         /* Empty loss interval history */
1901         dccp_li_hist_purge(ccid3_li_hist, &hcrx->ccid3hcrx_li_hist);
1902
1903         kfree(dp->dccps_hc_rx_ccid_private);
1904         dp->dccps_hc_rx_ccid_private = NULL;
1905 }
1906
1907 static void ccid3_hc_rx_get_info(struct sock *sk, struct tcp_info *info)
1908 {
1909         const struct dccp_sock *dp = dccp_sk(sk);
1910         const struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1911
1912         if (hcrx == NULL)
1913                 return;
1914
1915         info->tcpi_ca_state     = hcrx->ccid3hcrx_state;
1916         info->tcpi_options      |= TCPI_OPT_TIMESTAMPS;
1917         info->tcpi_rcv_rtt      = hcrx->ccid3hcrx_rtt;
1918 }
1919
1920 static void ccid3_hc_tx_get_info(struct sock *sk, struct tcp_info *info)
1921 {
1922         const struct dccp_sock *dp = dccp_sk(sk);
1923         const struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1924
1925         if (hctx == NULL)
1926                 return;
1927
1928         info->tcpi_rto = hctx->ccid3hctx_t_rto;
1929         info->tcpi_rtt = hctx->ccid3hctx_rtt;
1930 }
1931
1932 static struct ccid ccid3 = {
1933         .ccid_id                   = 3,
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,
1951 };
1952
1953 module_param(ccid3_debug, int, 0444);
1954 MODULE_PARM_DESC(ccid3_debug, "Enable debug messages");
1955
1956 static __init int ccid3_module_init(void)
1957 {
1958         int rc = -ENOBUFS;
1959
1960         ccid3_rx_hist = dccp_rx_hist_new("ccid3");
1961         if (ccid3_rx_hist == NULL)
1962                 goto out;
1963
1964         ccid3_tx_hist = dccp_tx_hist_new("ccid3");
1965         if (ccid3_tx_hist == NULL)
1966                 goto out_free_rx;
1967
1968         ccid3_li_hist = dccp_li_hist_new("ccid3");
1969         if (ccid3_li_hist == NULL)
1970                 goto out_free_tx;
1971
1972         rc = ccid_register(&ccid3);
1973         if (rc != 0)
1974                 goto out_free_loss_interval_history;
1975 out:
1976         return rc;
1977
1978 out_free_loss_interval_history:
1979         dccp_li_hist_delete(ccid3_li_hist);
1980         ccid3_li_hist = NULL;
1981 out_free_tx:
1982         dccp_tx_hist_delete(ccid3_tx_hist);
1983         ccid3_tx_hist = NULL;
1984 out_free_rx:
1985         dccp_rx_hist_delete(ccid3_rx_hist);
1986         ccid3_rx_hist = NULL;
1987         goto out;
1988 }
1989 module_init(ccid3_module_init);
1990
1991 static __exit void ccid3_module_exit(void)
1992 {
1993 #ifdef CONFIG_IP_DCCP_UNLOAD_HACK
1994         /*
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
1997          */
1998         extern void dccp_ctl_sock_exit(void);
1999
2000         dccp_ctl_sock_exit();
2001 #endif
2002         ccid_unregister(&ccid3);
2003
2004         if (ccid3_tx_hist != NULL) {
2005                 dccp_tx_hist_delete(ccid3_tx_hist);
2006                 ccid3_tx_hist = NULL;
2007         }
2008         if (ccid3_rx_hist != NULL) {
2009                 dccp_rx_hist_delete(ccid3_rx_hist);
2010                 ccid3_rx_hist = NULL;
2011         }
2012         if (ccid3_li_hist != NULL) {
2013                 dccp_li_hist_delete(ccid3_li_hist);
2014                 ccid3_li_hist = NULL;
2015         }
2016 }
2017 module_exit(ccid3_module_exit);
2018
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");