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 "ccid3.h"
  42
  43 #ifdef CCID3_DEBUG
  44 extern int ccid3_debug;
  45
  46 #define ccid3_pr_debug(format, a...) \
  47         do { if (ccid3_debug) \
  48                 printk(KERN_DEBUG "%s: " format, __FUNCTION__, ##a); \
  49         } while (0)
  50 #else
  51 #define ccid3_pr_debug(format, a...)
  52 #endif
  53
  54 #define TFRC_MIN_PACKET_SIZE       16
  55 #define TFRC_STD_PACKET_SIZE      256
  56 #define TFRC_MAX_PACKET_SIZE    65535
  57
  58 #define TFRC_INITIAL_TIMEOUT       (2 * USEC_PER_SEC)
  59 /* two seconds as per CCID3 spec 11 */
  60
  61 #define TFRC_OPSYS_HALF_TIME_GRAN       (USEC_PER_SEC / (2 * HZ))
  62 /* above is in usecs - half the scheduling granularity as per RFC3448 4.6 */
  63
  64 #define TFRC_WIN_COUNT_PER_RTT      4
  65 #define TFRC_WIN_COUNT_LIMIT       16
  66
  67 #define TFRC_MAX_BACK_OFF_TIME     64
  68 /* above is in seconds */
  69
  70 #define TFRC_SMALLEST_P            40
  71
  72 #define TFRC_RECV_IVAL_F_LENGTH     8          /* length(w[]) */
  73
  74 /* Number of later packets received before one is considered lost */
  75 #define TFRC_RECV_NUM_LATE_LOSS 3
  76
  77 enum ccid3_options {
  78         TFRC_OPT_LOSS_EVENT_RATE = 192,
  79         TFRC_OPT_LOSS_INTERVALS  = 193,
  80         TFRC_OPT_RECEIVE_RATE    = 194,
  81 };
  82
  83 static int ccid3_debug;
  84
  85 static struct dccp_tx_hist *ccid3_tx_hist;
  86 static struct dccp_rx_hist *ccid3_rx_hist;
  87
  88 static kmem_cache_t *ccid3_loss_interval_hist_slab __read_mostly;
  89
  90 static inline struct ccid3_loss_interval_hist_entry *
  91         ccid3_loss_interval_hist_entry_new(const unsigned int __nocast prio)
  92 {
  93         return kmem_cache_alloc(ccid3_loss_interval_hist_slab, prio);
  94 }
  95
  96 static inline void ccid3_loss_interval_hist_entry_delete(struct ccid3_loss_interval_hist_entry *entry)
  97 {
  98         if (entry != NULL)
  99                 kmem_cache_free(ccid3_loss_interval_hist_slab, entry);
 100 }
 101
 102 static void ccid3_loss_interval_history_delete(struct list_head *hist)
 103 {
 104         struct ccid3_loss_interval_hist_entry *entry, *next;
 105
 106         list_for_each_entry_safe(entry, next, hist, ccid3lih_node) {
 107                 list_del_init(&entry->ccid3lih_node);
 108                 kmem_cache_free(ccid3_loss_interval_hist_slab, entry);
 109         }
 110 }
 111
 112 static int ccid3_init(struct sock *sk)
 113 {
 114         ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
 115         return 0;
 116 }
 117
 118 static void ccid3_exit(struct sock *sk)
 119 {
 120         ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
 121 }
 122
 123 /* TFRC sender states */
 124 enum ccid3_hc_tx_states {
 125         TFRC_SSTATE_NO_SENT = 1,
 126         TFRC_SSTATE_NO_FBACK,
 127         TFRC_SSTATE_FBACK,
 128         TFRC_SSTATE_TERM,
 129 };
 130
 131 #ifdef CCID3_DEBUG
 132 static const char *ccid3_tx_state_name(enum ccid3_hc_tx_states state)
 133 {
 134         static char *ccid3_state_names[] = {
 135         [TFRC_SSTATE_NO_SENT]  = "NO_SENT",
 136         [TFRC_SSTATE_NO_FBACK] = "NO_FBACK",
 137         [TFRC_SSTATE_FBACK]    = "FBACK",
 138         [TFRC_SSTATE_TERM]     = "TERM",
 139         };
 140
 141         return ccid3_state_names[state];
 142 }
 143 #endif
 144
 145 static inline void ccid3_hc_tx_set_state(struct sock *sk,
 146                                          enum ccid3_hc_tx_states state)
 147 {
 148         struct dccp_sock *dp = dccp_sk(sk);
 149         struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
 150         enum ccid3_hc_tx_states oldstate = hctx->ccid3hctx_state;
 151
 152         ccid3_pr_debug("%s(%p) %-8.8s -> %s\n",
 153                        dccp_role(sk), sk, ccid3_tx_state_name(oldstate),
 154                        ccid3_tx_state_name(state));
 155         WARN_ON(state == oldstate);
 156         hctx->ccid3hctx_state = state;
 157 }
 158
 159 #define CALCX_ARRSIZE 500
 160
 161 #define CALCX_SPLIT 50000
 162 /* equivalent to 0.05 */
 163
 164 static const u32 calcx_lookup[CALCX_ARRSIZE][2] = {
 165         { 37172 , 8172 },
 166         { 53499 , 11567 },
 167         { 66664 , 14180 },
 168         { 78298 , 16388 },
 169         { 89021 , 18339 },
 170         { 99147 , 20108 },
 171         { 108858 , 21738 },
 172         { 118273 , 23260 },
 173         { 127474 , 24693 },
 174         { 136520 , 26052 },
 175         { 145456 , 27348 },
 176         { 154316 , 28589 },
 177         { 163130 , 29783 },
 178         { 171919 , 30935 },
 179         { 180704 , 32049 },
 180         { 189502 , 33130 },
 181         { 198328 , 34180 },
 182         { 207194 , 35202 },
 183         { 216114 , 36198 },
 184         { 225097 , 37172 },
 185         { 234153 , 38123 },
 186         { 243294 , 39055 },
 187         { 252527 , 39968 },
 188         { 261861 , 40864 },
 189         { 271305 , 41743 },
 190         { 280866 , 42607 },
 191         { 290553 , 43457 },
 192         { 300372 , 44293 },
 193         { 310333 , 45117 },
 194         { 320441 , 45929 },
 195         { 330705 , 46729 },
 196         { 341131 , 47518 },
 197         { 351728 , 48297 },
 198         { 362501 , 49066 },
 199         { 373460 , 49826 },
 200         { 384609 , 50577 },
 201         { 395958 , 51320 },
 202         { 407513 , 52054 },
 203         { 419281 , 52780 },
 204         { 431270 , 53499 },
 205         { 443487 , 54211 },
 206         { 455940 , 54916 },
 207         { 468635 , 55614 },
 208         { 481581 , 56306 },
 209         { 494785 , 56991 },
 210         { 508254 , 57671 },
 211         { 521996 , 58345 },
 212         { 536019 , 59014 },
 213         { 550331 , 59677 },
 214         { 564939 , 60335 },
 215         { 579851 , 60988 },
 216         { 595075 , 61636 },
 217         { 610619 , 62279 },
 218         { 626491 , 62918 },
 219         { 642700 , 63553 },
 220         { 659253 , 64183 },
 221         { 676158 , 64809 },
 222         { 693424 , 65431 },
 223         { 711060 , 66050 },
 224         { 729073 , 66664 },
 225         { 747472 , 67275 },
 226         { 766266 , 67882 },
 227         { 785464 , 68486 },
 228         { 805073 , 69087 },
 229         { 825103 , 69684 },
 230         { 845562 , 70278 },
 231         { 866460 , 70868 },
 232         { 887805 , 71456 },
 233         { 909606 , 72041 },
 234         { 931873 , 72623 },
 235         { 954614 , 73202 },
 236         { 977839 , 73778 },
 237         { 1001557 , 74352 },
 238         { 1025777 , 74923 },
 239         { 1050508 , 75492 },
 240         { 1075761 , 76058 },
 241         { 1101544 , 76621 },
 242         { 1127867 , 77183 },
 243         { 1154739 , 77741 },
 244         { 1182172 , 78298 },
 245         { 1210173 , 78852 },
 246         { 1238753 , 79405 },
 247         { 1267922 , 79955 },
 248         { 1297689 , 80503 },
 249         { 1328066 , 81049 },
 250         { 1359060 , 81593 },
 251         { 1390684 , 82135 },
 252         { 1422947 , 82675 },
 253         { 1455859 , 83213 },
 254         { 1489430 , 83750 },
 255         { 1523671 , 84284 },
 256         { 1558593 , 84817 },
 257         { 1594205 , 85348 },
 258         { 1630518 , 85878 },
 259         { 1667543 , 86406 },
 260         { 1705290 , 86932 },
 261         { 1743770 , 87457 },
 262         { 1782994 , 87980 },
 263         { 1822973 , 88501 },
 264         { 1863717 , 89021 },
 265         { 1905237 , 89540 },
 266         { 1947545 , 90057 },
 267         { 1990650 , 90573 },
 268         { 2034566 , 91087 },
 269         { 2079301 , 91600 },
 270         { 2124869 , 92111 },
 271         { 2171279 , 92622 },
 272         { 2218543 , 93131 },
 273         { 2266673 , 93639 },
 274         { 2315680 , 94145 },
 275         { 2365575 , 94650 },
 276         { 2416371 , 95154 },
 277         { 2468077 , 95657 },
 278         { 2520707 , 96159 },
 279         { 2574271 , 96660 },
 280         { 2628782 , 97159 },
 281         { 2684250 , 97658 },
 282         { 2740689 , 98155 },
 283         { 2798110 , 98651 },
 284         { 2856524 , 99147 },
 285         { 2915944 , 99641 },
 286         { 2976382 , 100134 },
 287         { 3037850 , 100626 },
 288         { 3100360 , 101117 },
 289         { 3163924 , 101608 },
 290         { 3228554 , 102097 },
 291         { 3294263 , 102586 },
 292         { 3361063 , 103073 },
 293         { 3428966 , 103560 },
 294         { 3497984 , 104045 },
 295         { 3568131 , 104530 },
 296         { 3639419 , 105014 },
 297         { 3711860 , 105498 },
 298         { 3785467 , 105980 },
 299         { 3860253 , 106462 },
 300         { 3936229 , 106942 },
 301         { 4013410 , 107422 },
 302         { 4091808 , 107902 },
 303         { 4171435 , 108380 },
 304         { 4252306 , 108858 },
 305         { 4334431 , 109335 },
 306         { 4417825 , 109811 },
 307         { 4502501 , 110287 },
 308         { 4588472 , 110762 },
 309         { 4675750 , 111236 },
 310         { 4764349 , 111709 },
 311         { 4854283 , 112182 },
 312         { 4945564 , 112654 },
 313         { 5038206 , 113126 },
 314         { 5132223 , 113597 },
 315         { 5227627 , 114067 },
 316         { 5324432 , 114537 },
 317         { 5422652 , 115006 },
 318         { 5522299 , 115474 },
 319         { 5623389 , 115942 },
 320         { 5725934 , 116409 },
 321         { 5829948 , 116876 },
 322         { 5935446 , 117342 },
 323         { 6042439 , 117808 },
 324         { 6150943 , 118273 },
 325         { 6260972 , 118738 },
 326         { 6372538 , 119202 },
 327         { 6485657 , 119665 },
 328         { 6600342 , 120128 },
 329         { 6716607 , 120591 },
 330         { 6834467 , 121053 },
 331         { 6953935 , 121514 },
 332         { 7075025 , 121976 },
 333         { 7197752 , 122436 },
 334         { 7322131 , 122896 },
 335         { 7448175 , 123356 },
 336         { 7575898 , 123815 },
 337         { 7705316 , 124274 },
 338         { 7836442 , 124733 },
 339         { 7969291 , 125191 },
 340         { 8103877 , 125648 },
 341         { 8240216 , 126105 },
 342         { 8378321 , 126562 },
 343         { 8518208 , 127018 },
 344         { 8659890 , 127474 },
 345         { 8803384 , 127930 },
 346         { 8948702 , 128385 },
 347         { 9095861 , 128840 },
 348         { 9244875 , 129294 },
 349         { 9395760 , 129748 },
 350         { 9548529 , 130202 },
 351         { 9703198 , 130655 },
 352         { 9859782 , 131108 },
 353         { 10018296 , 131561 },
 354         { 10178755 , 132014 },
 355         { 10341174 , 132466 },
 356         { 10505569 , 132917 },
 357         { 10671954 , 133369 },
 358         { 10840345 , 133820 },
 359         { 11010757 , 134271 },
 360         { 11183206 , 134721 },
 361         { 11357706 , 135171 },
 362         { 11534274 , 135621 },
 363         { 11712924 , 136071 },
 364         { 11893673 , 136520 },
 365         { 12076536 , 136969 },
 366         { 12261527 , 137418 },
 367         { 12448664 , 137867 },
 368         { 12637961 , 138315 },
 369         { 12829435 , 138763 },
 370         { 13023101 , 139211 },
 371         { 13218974 , 139658 },
 372         { 13417071 , 140106 },
 373         { 13617407 , 140553 },
 374         { 13819999 , 140999 },
 375         { 14024862 , 141446 },
 376         { 14232012 , 141892 },
 377         { 14441465 , 142339 },
 378         { 14653238 , 142785 },
 379         { 14867346 , 143230 },
 380         { 15083805 , 143676 },
 381         { 15302632 , 144121 },
 382         { 15523842 , 144566 },
 383         { 15747453 , 145011 },
 384         { 15973479 , 145456 },
 385         { 16201939 , 145900 },
 386         { 16432847 , 146345 },
 387         { 16666221 , 146789 },
 388         { 16902076 , 147233 },
 389         { 17140429 , 147677 },
 390         { 17381297 , 148121 },
 391         { 17624696 , 148564 },
 392         { 17870643 , 149007 },
 393         { 18119154 , 149451 },
 394         { 18370247 , 149894 },
 395         { 18623936 , 150336 },
 396         { 18880241 , 150779 },
 397         { 19139176 , 151222 },
 398         { 19400759 , 151664 },
 399         { 19665007 , 152107 },
 400         { 19931936 , 152549 },
 401         { 20201564 , 152991 },
 402         { 20473907 , 153433 },
 403         { 20748982 , 153875 },
 404         { 21026807 , 154316 },
 405         { 21307399 , 154758 },
 406         { 21590773 , 155199 },
 407         { 21876949 , 155641 },
 408         { 22165941 , 156082 },
 409         { 22457769 , 156523 },
 410         { 22752449 , 156964 },
 411         { 23049999 , 157405 },
 412         { 23350435 , 157846 },
 413         { 23653774 , 158287 },
 414         { 23960036 , 158727 },
 415         { 24269236 , 159168 },
 416         { 24581392 , 159608 },
 417         { 24896521 , 160049 },
 418         { 25214642 , 160489 },
 419         { 25535772 , 160929 },
 420         { 25859927 , 161370 },
 421         { 26187127 , 161810 },
 422         { 26517388 , 162250 },
 423         { 26850728 , 162690 },
 424         { 27187165 , 163130 },
 425         { 27526716 , 163569 },
 426         { 27869400 , 164009 },
 427         { 28215234 , 164449 },
 428         { 28564236 , 164889 },
 429         { 28916423 , 165328 },
 430         { 29271815 , 165768 },
 431         { 29630428 , 166208 },
 432         { 29992281 , 166647 },
 433         { 30357392 , 167087 },
 434         { 30725779 , 167526 },
 435         { 31097459 , 167965 },
 436         { 31472452 , 168405 },
 437         { 31850774 , 168844 },
 438         { 32232445 , 169283 },
 439         { 32617482 , 169723 },
 440         { 33005904 , 170162 },
 441         { 33397730 , 170601 },
 442         { 33792976 , 171041 },
 443         { 34191663 , 171480 },
 444         { 34593807 , 171919 },
 445         { 34999428 , 172358 },
 446         { 35408544 , 172797 },
 447         { 35821174 , 173237 },
 448         { 36237335 , 173676 },
 449         { 36657047 , 174115 },
 450         { 37080329 , 174554 },
 451         { 37507197 , 174993 },
 452         { 37937673 , 175433 },
 453         { 38371773 , 175872 },
 454         { 38809517 , 176311 },
 455         { 39250924 , 176750 },
 456         { 39696012 , 177190 },
 457         { 40144800 , 177629 },
 458         { 40597308 , 178068 },
 459         { 41053553 , 178507 },
 460         { 41513554 , 178947 },
 461         { 41977332 , 179386 },
 462         { 42444904 , 179825 },
 463         { 42916290 , 180265 },
 464         { 43391509 , 180704 },
 465         { 43870579 , 181144 },
 466         { 44353520 , 181583 },
 467         { 44840352 , 182023 },
 468         { 45331092 , 182462 },
 469         { 45825761 , 182902 },
 470         { 46324378 , 183342 },
 471         { 46826961 , 183781 },
 472         { 47333531 , 184221 },
 473         { 47844106 , 184661 },
 474         { 48358706 , 185101 },
 475         { 48877350 , 185541 },
 476         { 49400058 , 185981 },
 477         { 49926849 , 186421 },
 478         { 50457743 , 186861 },
 479         { 50992759 , 187301 },
 480         { 51531916 , 187741 },
 481         { 52075235 , 188181 },
 482         { 52622735 , 188622 },
 483         { 53174435 , 189062 },
 484         { 53730355 , 189502 },
 485         { 54290515 , 189943 },
 486         { 54854935 , 190383 },
 487         { 55423634 , 190824 },
 488         { 55996633 , 191265 },
 489         { 56573950 , 191706 },
 490         { 57155606 , 192146 },
 491         { 57741621 , 192587 },
 492         { 58332014 , 193028 },
 493         { 58926806 , 193470 },
 494         { 59526017 , 193911 },
 495         { 60129666 , 194352 },
 496         { 60737774 , 194793 },
 497         { 61350361 , 195235 },
 498         { 61967446 , 195677 },
 499         { 62589050 , 196118 },
 500         { 63215194 , 196560 },
 501         { 63845897 , 197002 },
 502         { 64481179 , 197444 },
 503         { 65121061 , 197886 },
 504         { 65765563 , 198328 },
 505         { 66414705 , 198770 },
 506         { 67068508 , 199213 },
 507         { 67726992 , 199655 },
 508         { 68390177 , 200098 },
 509         { 69058085 , 200540 },
 510         { 69730735 , 200983 },
 511         { 70408147 , 201426 },
 512         { 71090343 , 201869 },
 513         { 71777343 , 202312 },
 514         { 72469168 , 202755 },
 515         { 73165837 , 203199 },
 516         { 73867373 , 203642 },
 517         { 74573795 , 204086 },
 518         { 75285124 , 204529 },
 519         { 76001380 , 204973 },
 520         { 76722586 , 205417 },
 521         { 77448761 , 205861 },
 522         { 78179926 , 206306 },
 523         { 78916102 , 206750 },
 524         { 79657310 , 207194 },
 525         { 80403571 , 207639 },
 526         { 81154906 , 208084 },
 527         { 81911335 , 208529 },
 528         { 82672880 , 208974 },
 529         { 83439562 , 209419 },
 530         { 84211402 , 209864 },
 531         { 84988421 , 210309 },
 532         { 85770640 , 210755 },
 533         { 86558080 , 211201 },
 534         { 87350762 , 211647 },
 535         { 88148708 , 212093 },
 536         { 88951938 , 212539 },
 537         { 89760475 , 212985 },
 538         { 90574339 , 213432 },
 539         { 91393551 , 213878 },
 540         { 92218133 , 214325 },
 541         { 93048107 , 214772 },
 542         { 93883493 , 215219 },
 543         { 94724314 , 215666 },
 544         { 95570590 , 216114 },
 545         { 96422343 , 216561 },
 546         { 97279594 , 217009 },
 547         { 98142366 , 217457 },
 548         { 99010679 , 217905 },
 549         { 99884556 , 218353 },
 550         { 100764018 , 218801 },
 551         { 101649086 , 219250 },
 552         { 102539782 , 219698 },
 553         { 103436128 , 220147 },
 554         { 104338146 , 220596 },
 555         { 105245857 , 221046 },
 556         { 106159284 , 221495 },
 557         { 107078448 , 221945 },
 558         { 108003370 , 222394 },
 559         { 108934074 , 222844 },
 560         { 109870580 , 223294 },
 561         { 110812910 , 223745 },
 562         { 111761087 , 224195 },
 563         { 112715133 , 224646 },
 564         { 113675069 , 225097 },
 565         { 114640918 , 225548 },
 566         { 115612702 , 225999 },
 567         { 116590442 , 226450 },
 568         { 117574162 , 226902 },
 569         { 118563882 , 227353 },
 570         { 119559626 , 227805 },
 571         { 120561415 , 228258 },
 572         { 121569272 , 228710 },
 573         { 122583219 , 229162 },
 574         { 123603278 , 229615 },
 575         { 124629471 , 230068 },
 576         { 125661822 , 230521 },
 577         { 126700352 , 230974 },
 578         { 127745083 , 231428 },
 579         { 128796039 , 231882 },
 580         { 129853241 , 232336 },
 581         { 130916713 , 232790 },
 582         { 131986475 , 233244 },
 583         { 133062553 , 233699 },
 584         { 134144966 , 234153 },
 585         { 135233739 , 234608 },
 586         { 136328894 , 235064 },
 587         { 137430453 , 235519 },
 588         { 138538440 , 235975 },
 589         { 139652876 , 236430 },
 590         { 140773786 , 236886 },
 591         { 141901190 , 237343 },
 592         { 143035113 , 237799 },
 593         { 144175576 , 238256 },
 594         { 145322604 , 238713 },
 595         { 146476218 , 239170 },
 596         { 147636442 , 239627 },
 597         { 148803298 , 240085 },
 598         { 149976809 , 240542 },
 599         { 151156999 , 241000 },
 600         { 152343890 , 241459 },
 601         { 153537506 , 241917 },
 602         { 154737869 , 242376 },
 603         { 155945002 , 242835 },
 604         { 157158929 , 243294 },
 605         { 158379673 , 243753 },
 606         { 159607257 , 244213 },
 607         { 160841704 , 244673 },
 608         { 162083037 , 245133 },
 609         { 163331279 , 245593 },
 610         { 164586455 , 246054 },
 611         { 165848586 , 246514 },
 612         { 167117696 , 246975 },
 613         { 168393810 , 247437 },
 614         { 169676949 , 247898 },
 615         { 170967138 , 248360 },
 616         { 172264399 , 248822 },
 617         { 173568757 , 249284 },
 618         { 174880235 , 249747 },
 619         { 176198856 , 250209 },
 620         { 177524643 , 250672 },
 621         { 178857621 , 251136 },
 622         { 180197813 , 251599 },
 623         { 181545242 , 252063 },
 624         { 182899933 , 252527 },
 625         { 184261908 , 252991 },
 626         { 185631191 , 253456 },
 627         { 187007807 , 253920 },
 628         { 188391778 , 254385 },
 629         { 189783129 , 254851 },
 630         { 191181884 , 255316 },
 631         { 192588065 , 255782 },
 632         { 194001698 , 256248 },
 633         { 195422805 , 256714 },
 634         { 196851411 , 257181 },
 635         { 198287540 , 257648 },
 636         { 199731215 , 258115 },
 637         { 201182461 , 258582 },
 638         { 202641302 , 259050 },
 639         { 204107760 , 259518 },
 640         { 205581862 , 259986 },
 641         { 207063630 , 260454 },
 642         { 208553088 , 260923 },
 643         { 210050262 , 261392 },
 644         { 211555174 , 261861 },
 645         { 213067849 , 262331 },
 646         { 214588312 , 262800 },
 647         { 216116586 , 263270 },
 648         { 217652696 , 263741 },
 649         { 219196666 , 264211 },
 650         { 220748520 , 264682 },
 651         { 222308282 , 265153 },
 652         { 223875978 , 265625 },
 653         { 225451630 , 266097 },
 654         { 227035265 , 266569 },
 655         { 228626905 , 267041 },
 656         { 230226576 , 267514 },
 657         { 231834302 , 267986 },
 658         { 233450107 , 268460 },
 659         { 235074016 , 268933 },
 660         { 236706054 , 269407 },
 661         { 238346244 , 269881 },
 662         { 239994613 , 270355 },
 663         { 241651183 , 270830 },
 664         { 243315981 , 271305 }
 665 };
 666
 667 /* Calculate the send rate as per section 3.1 of RFC3448
 668
 669 Returns send rate in bytes per second
 670
 671 Integer maths and lookups are used as not allowed floating point in kernel
 672
 673 The function for Xcalc as per section 3.1 of RFC3448 is:
 674
 675 X =                            s
 676      -------------------------------------------------------------
 677      R*sqrt(2*b*p/3) + (t_RTO * (3*sqrt(3*b*p/8) * p * (1+32*p^2)))
 678
 679 where
 680 X is the trasmit rate in bytes/second
 681 s is the packet size in bytes
 682 R is the round trip time in seconds
 683 p is the loss event rate, between 0 and 1.0, of the number of loss events
 684   as a fraction of the number of packets transmitted
 685 t_RTO is the TCP retransmission timeout value in seconds
 686 b is the number of packets acknowledged by a single TCP acknowledgement
 687
 688 we can assume that b = 1 and t_RTO is 4 * R. With this the equation becomes:
 689
 690 X =                            s
 691      -----------------------------------------------------------------------
 692      R * sqrt(2 * p / 3) + (12 * R * (sqrt(3 * p / 8) * p * (1 + 32 * p^2)))
 693
 694
 695 which we can break down into:
 696
 697 X =     s
 698      --------
 699      R * f(p)
 700
 701 where f(p) = sqrt(2 * p / 3) + (12 * sqrt(3 * p / 8) * p * (1 + 32 * p * p))
 702
 703 Function parameters:
 704 s - bytes
 705 R - RTT in usecs
 706 p - loss rate (decimal fraction multiplied by 1,000,000)
 707
 708 Returns Xcalc in bytes per second
 709
 710 DON'T alter this code unless you run test cases against it as the code
 711 has been manipulated to stop underflow/overlow.
 712
 713 */
 714 static u32 ccid3_calc_x(u16 s, u32 R, u32 p)
 715 {
 716         int index;
 717         u32 f;
 718         u64 tmp1, tmp2;
 719
 720         if (p < CALCX_SPLIT)
 721                 index = (p / (CALCX_SPLIT / CALCX_ARRSIZE)) - 1;
 722         else
 723                 index = (p / (1000000 / CALCX_ARRSIZE)) - 1;
 724
 725         if (index < 0)
 726                 /* p should be 0 unless there is a bug in my code */
 727                 index = 0;
 728
 729         if (R == 0)
 730                 R = 1; /* RTT can't be zero or else divide by zero */
 731
 732         BUG_ON(index >= CALCX_ARRSIZE);
 733
 734         if (p >= CALCX_SPLIT)
 735                 f = calcx_lookup[index][0];
 736         else
 737                 f = calcx_lookup[index][1];
 738
 739         tmp1 = ((u64)s * 100000000);
 740         tmp2 = ((u64)R * (u64)f);
 741         do_div(tmp2,10000);
 742         do_div(tmp1,tmp2);
 743         /* don't alter above math unless you test due to overflow on 32 bit */
 744
 745         return (u32)tmp1;
 746 }
 747
 748 /* Calculate new t_ipi (inter packet interval) by t_ipi = s / X_inst */
 749 static inline void ccid3_calc_new_t_ipi(struct ccid3_hc_tx_sock *hctx)
 750 {
 751         if (hctx->ccid3hctx_state == TFRC_SSTATE_NO_FBACK)
 752                 return;
 753         /* if no feedback spec says t_ipi is 1 second (set elsewhere and then
 754          * doubles after every no feedback timer (separate function) */
 755
 756         if (hctx->ccid3hctx_x < 10) {
 757                 ccid3_pr_debug("ccid3_calc_new_t_ipi - ccid3hctx_x < 10\n");
 758                 hctx->ccid3hctx_x = 10;
 759         }
 760         hctx->ccid3hctx_t_ipi = (hctx->ccid3hctx_s * 100000)
 761                 / (hctx->ccid3hctx_x / 10);
 762         /* reason for above maths with 10 in there is to avoid 32 bit
 763          * overflow for jumbo packets */
 764
 765 }
 766
 767 /* Calculate new delta by delta = min(t_ipi / 2, t_gran / 2) */
 768 static inline void ccid3_calc_new_delta(struct ccid3_hc_tx_sock *hctx)
 769 {
 770         hctx->ccid3hctx_delta = min_t(u32, hctx->ccid3hctx_t_ipi / 2,
 771                                            TFRC_OPSYS_HALF_TIME_GRAN);
 772
 773 }
 774
 775 /*
 776  * Update X by
 777  *    If (p > 0)
 778  *       x_calc = calcX(s, R, p);
 779  *       X = max(min(X_calc, 2 * X_recv), s / t_mbi);
 780  *    Else
 781  *       If (now - tld >= R)
 782  *          X = max(min(2 * X, 2 * X_recv), s / R);
 783  *          tld = now;
 784  */
 785 static void ccid3_hc_tx_update_x(struct sock *sk)
 786 {
 787         struct dccp_sock *dp = dccp_sk(sk);
 788         struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
 789
 790         /* To avoid large error in calcX */
 791         if (hctx->ccid3hctx_p >= TFRC_SMALLEST_P) {
 792                 hctx->ccid3hctx_x_calc = ccid3_calc_x(hctx->ccid3hctx_s,
 793                                                       hctx->ccid3hctx_rtt,
 794                                                       hctx->ccid3hctx_p);
 795                 hctx->ccid3hctx_x = max_t(u32, min_t(u32, hctx->ccid3hctx_x_calc,
 796                                                           2 * hctx->ccid3hctx_x_recv),
 797                                                (hctx->ccid3hctx_s /
 798                                                 TFRC_MAX_BACK_OFF_TIME));
 799         } else {
 800                 struct timeval now;
 801
 802                 do_gettimeofday(&now);
 803                 if (timeval_delta(&now, &hctx->ccid3hctx_t_ld) >=
 804                     hctx->ccid3hctx_rtt) {
 805                         /* Avoid divide by zero below */
 806                         const u32 rtt = max_t(u32, hctx->ccid3hctx_rtt, 10);
 807
 808                         hctx->ccid3hctx_x = max_t(u32, min_t(u32, 2 * hctx->ccid3hctx_x_recv,
 809                                                                   2 * hctx->ccid3hctx_x),
 810                                                        ((hctx->ccid3hctx_s * 100000) /
 811                                                         (rtt / 10)));
 812                         /* Using 100000 and 10 to avoid 32 bit overflow for jumbo frames */
 813                         hctx->ccid3hctx_t_ld = now;
 814                 }
 815         }
 816
 817         if (hctx->ccid3hctx_x == 0) {
 818                 ccid3_pr_debug("ccid3hctx_x = 0!\n");
 819                 hctx->ccid3hctx_x = 1;
 820         }
 821 }
 822
 823 static void ccid3_hc_tx_no_feedback_timer(unsigned long data)
 824 {
 825         struct sock *sk = (struct sock *)data;
 826         struct dccp_sock *dp = dccp_sk(sk);
 827         unsigned long next_tmout = 0;
 828         struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
 829         u32 rtt;
 830
 831         bh_lock_sock(sk);
 832         if (sock_owned_by_user(sk)) {
 833                 /* Try again later. */
 834                 /* XXX: set some sensible MIB */
 835                 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
 836                                jiffies + HZ / 5);
 837                 goto out;
 838         }
 839
 840         ccid3_pr_debug("%s, sk=%p, state=%s\n", dccp_role(sk), sk,
 841                        ccid3_tx_state_name(hctx->ccid3hctx_state));
 842
 843         if (hctx->ccid3hctx_x < 10) {
 844                 ccid3_pr_debug("TFRC_SSTATE_NO_FBACK ccid3hctx_x < 10\n");
 845                 hctx->ccid3hctx_x = 10;
 846         }
 847
 848         switch (hctx->ccid3hctx_state) {
 849         case TFRC_SSTATE_TERM:
 850                 goto out;
 851         case TFRC_SSTATE_NO_FBACK:
 852                 /* Halve send rate */
 853                 hctx->ccid3hctx_x /= 2;
 854                 if (hctx->ccid3hctx_x <
 855                     (hctx->ccid3hctx_s / TFRC_MAX_BACK_OFF_TIME))
 856                         hctx->ccid3hctx_x = (hctx->ccid3hctx_s /
 857                                              TFRC_MAX_BACK_OFF_TIME);
 858
 859                 ccid3_pr_debug("%s, sk=%p, state=%s, updated tx rate to %d "
 860                                "bytes/s\n",
 861                                dccp_role(sk), sk,
 862                                ccid3_tx_state_name(hctx->ccid3hctx_state),
 863                                hctx->ccid3hctx_x);
 864                 next_tmout = max_t(u32, 2 * (hctx->ccid3hctx_s * 100000) / (hctx->ccid3hctx_x / 10),
 865                                         TFRC_INITIAL_TIMEOUT);
 866                 /* do above maths with 100000 and 10 to prevent overflow on 32 bit */
 867                 /*
 868                  * FIXME - not sure above calculation is correct. See section
 869                  * 5 of CCID3 11 should adjust tx_t_ipi and double that to
 870                  * achieve it really
 871                  */
 872                 break;
 873         case TFRC_SSTATE_FBACK:
 874                 /*
 875                  * Check if IDLE since last timeout and recv rate is less than
 876                  * 4 packets per RTT
 877                  */
 878                 rtt = hctx->ccid3hctx_rtt;
 879                 if (rtt < 10)
 880                         rtt = 10;
 881                 /* stop divide by zero below */
 882                 if (!hctx->ccid3hctx_idle ||
 883                     (hctx->ccid3hctx_x_recv >= 4 * (hctx->ccid3hctx_s * 100000) / (rtt / 10))) {
 884                         ccid3_pr_debug("%s, sk=%p, state=%s, not idle\n",
 885                                        dccp_role(sk), sk,
 886                                        ccid3_tx_state_name(hctx->ccid3hctx_state));
 887                         /* Halve sending rate */
 888
 889                         /*  If (X_calc > 2 * X_recv)
 890                          *    X_recv = max(X_recv / 2, s / (2 * t_mbi));
 891                          *  Else
 892                          *    X_recv = X_calc / 4;
 893                          */
 894                         BUG_ON(hctx->ccid3hctx_p >= TFRC_SMALLEST_P &&
 895                                hctx->ccid3hctx_x_calc == 0);
 896
 897                         /* check also if p is zero -> x_calc is infinity? */
 898                         if (hctx->ccid3hctx_p < TFRC_SMALLEST_P ||
 899                             hctx->ccid3hctx_x_calc > 2 * hctx->ccid3hctx_x_recv)
 900                                 hctx->ccid3hctx_x_recv = max_t(u32, hctx->ccid3hctx_x_recv / 2,
 901                                                                     hctx->ccid3hctx_s / (2 * TFRC_MAX_BACK_OFF_TIME));
 902                         else
 903                                 hctx->ccid3hctx_x_recv = hctx->ccid3hctx_x_calc / 4;
 904
 905                         /* Update sending rate */
 906                         ccid3_hc_tx_update_x(sk);
 907                 }
 908                 if (hctx->ccid3hctx_x == 0) {
 909                         ccid3_pr_debug("TFRC_SSTATE_FBACK ccid3hctx_x = 0!\n");
 910                         hctx->ccid3hctx_x = 10;
 911                 }
 912                 /* Schedule no feedback timer to expire in max(4 * R, 2 * s / X) */
 913                 next_tmout = max_t(u32, hctx->ccid3hctx_t_rto,
 914                                    2 * (hctx->ccid3hctx_s * 100000) / (hctx->ccid3hctx_x / 10));
 915                 break;
 916         default:
 917                 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
 918                        __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
 919                 dump_stack();
 920                 goto out;
 921         }
 922
 923         sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
 924                       jiffies + max_t(u32, 1, usecs_to_jiffies(next_tmout)));
 925         hctx->ccid3hctx_idle = 1;
 926 out:
 927         bh_unlock_sock(sk);
 928         sock_put(sk);
 929 }
 930
 931 static int ccid3_hc_tx_send_packet(struct sock *sk,
 932                                    struct sk_buff *skb, int len)
 933 {
 934         struct dccp_sock *dp = dccp_sk(sk);
 935         struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
 936         struct dccp_tx_hist_entry *new_packet;
 937         struct timeval now;
 938         long delay;
 939         int rc = -ENOTCONN;
 940
 941         /* Check if pure ACK or Terminating*/
 942
 943         /*
 944          * XXX: We only call this function for DATA and DATAACK, on, these
 945          * packets can have zero length, but why the comment about "pure ACK"?
 946          */
 947         if (hctx == NULL || len == 0 ||
 948             hctx->ccid3hctx_state == TFRC_SSTATE_TERM)
 949                 goto out;
 950
 951         /* See if last packet allocated was not sent */
 952         new_packet = dccp_tx_hist_head(&hctx->ccid3hctx_hist);
 953         if (new_packet == NULL || new_packet->dccphtx_sent) {
 954                 new_packet = dccp_tx_hist_entry_new(ccid3_tx_hist,
 955                                                     SLAB_ATOMIC);
 956
 957                 rc = -ENOBUFS;
 958                 if (new_packet == NULL) {
 959                         ccid3_pr_debug("%s, sk=%p, not enough mem to add "
 960                                        "to history, send refused\n",
 961                                        dccp_role(sk), sk);
 962                         goto out;
 963                 }
 964
 965                 dccp_tx_hist_add_entry(&hctx->ccid3hctx_hist, new_packet);
 966         }
 967
 968         do_gettimeofday(&now);
 969
 970         switch (hctx->ccid3hctx_state) {
 971         case TFRC_SSTATE_NO_SENT:
 972                 ccid3_pr_debug("%s, sk=%p, first packet(%llu)\n",
 973                                dccp_role(sk), sk, dp->dccps_gss);
 974
 975                 hctx->ccid3hctx_no_feedback_timer.function = ccid3_hc_tx_no_feedback_timer;
 976                 hctx->ccid3hctx_no_feedback_timer.data     = (unsigned long)sk;
 977                 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
 978                                jiffies + usecs_to_jiffies(TFRC_INITIAL_TIMEOUT));
 979                 hctx->ccid3hctx_last_win_count   = 0;
 980                 hctx->ccid3hctx_t_last_win_count = now;
 981                 ccid3_hc_tx_set_state(sk, TFRC_SSTATE_NO_FBACK);
 982                 hctx->ccid3hctx_t_ipi = TFRC_INITIAL_TIMEOUT;
 983
 984                 /* Set nominal send time for initial packet */
 985                 hctx->ccid3hctx_t_nom = now;
 986                 timeval_add_usecs(&hctx->ccid3hctx_t_nom,
 987                                   hctx->ccid3hctx_t_ipi);
 988                 ccid3_calc_new_delta(hctx);
 989                 rc = 0;
 990                 break;
 991         case TFRC_SSTATE_NO_FBACK:
 992         case TFRC_SSTATE_FBACK:
 993                 delay = (timeval_delta(&now, &hctx->ccid3hctx_t_nom) -
 994                          hctx->ccid3hctx_delta);
 995                 ccid3_pr_debug("send_packet delay=%ld\n", delay);
 996                 delay /= -1000;
 997                 /* divide by -1000 is to convert to ms and get sign right */
 998                 rc = delay > 0 ? delay : 0;
 999                 break;
1000         default:
1001                 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1002                        __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
1003                 dump_stack();
1004                 rc = -EINVAL;
1005                 break;
1006         }
1007
1008         /* Can we send? if so add options and add to packet history */
1009         if (rc == 0)
1010                 new_packet->dccphtx_ccval =
1011                         DCCP_SKB_CB(skb)->dccpd_ccval =
1012                                 hctx->ccid3hctx_last_win_count;
1013 out:
1014         return rc;
1015 }
1016
1017 static void ccid3_hc_tx_packet_sent(struct sock *sk, int more, int len)
1018 {
1019         struct dccp_sock *dp = dccp_sk(sk);
1020         struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1021         struct timeval now;
1022
1023         BUG_ON(hctx == NULL);
1024
1025         if (hctx->ccid3hctx_state == TFRC_SSTATE_TERM) {
1026                 ccid3_pr_debug("%s, sk=%p, while state is TFRC_SSTATE_TERM!\n",
1027                                dccp_role(sk), sk);
1028                 return;
1029         }
1030
1031         do_gettimeofday(&now);
1032
1033         /* check if we have sent a data packet */
1034         if (len > 0) {
1035                 unsigned long quarter_rtt;
1036                 struct dccp_tx_hist_entry *packet;
1037
1038                 packet = dccp_tx_hist_head(&hctx->ccid3hctx_hist);
1039                 if (packet == NULL) {
1040                         printk(KERN_CRIT "%s: packet doesn't exists in "
1041                                          "history!\n", __FUNCTION__);
1042                         return;
1043                 }
1044                 if (packet->dccphtx_sent) {
1045                         printk(KERN_CRIT "%s: no unsent packet in history!\n",
1046                                __FUNCTION__);
1047                         return;
1048                 }
1049                 packet->dccphtx_tstamp = now;
1050                 packet->dccphtx_seqno  = dp->dccps_gss;
1051                 /*
1052                  * Check if win_count have changed
1053                  * Algorithm in "8.1. Window Counter Valuer" in
1054                  * draft-ietf-dccp-ccid3-11.txt
1055                  */
1056                 quarter_rtt = timeval_delta(&now, &hctx->ccid3hctx_t_last_win_count) /
1057                               (hctx->ccid3hctx_rtt / 4);
1058                 if (quarter_rtt > 0) {
1059                         hctx->ccid3hctx_t_last_win_count = now;
1060                         hctx->ccid3hctx_last_win_count   = (hctx->ccid3hctx_last_win_count +
1061                                                             min_t(unsigned long, quarter_rtt, 5)) % 16;
1062                         ccid3_pr_debug("%s, sk=%p, window changed from "
1063                                        "%u to %u!\n",
1064                                        dccp_role(sk), sk,
1065                                        packet->dccphtx_ccval,
1066                                        hctx->ccid3hctx_last_win_count);
1067                 }
1068
1069                 hctx->ccid3hctx_idle = 0;
1070                 packet->dccphtx_rtt  = hctx->ccid3hctx_rtt;
1071                 packet->dccphtx_sent = 1;
1072         } else
1073                 ccid3_pr_debug("%s, sk=%p, seqno=%llu NOT inserted!\n",
1074                                dccp_role(sk), sk, dp->dccps_gss);
1075
1076         switch (hctx->ccid3hctx_state) {
1077         case TFRC_SSTATE_NO_SENT:
1078                 /* if first wasn't pure ack */
1079                 if (len != 0)
1080                         printk(KERN_CRIT "%s: %s, First packet sent is noted "
1081                                          "as a data packet\n",
1082                                __FUNCTION__, dccp_role(sk));
1083                 return;
1084         case TFRC_SSTATE_NO_FBACK:
1085         case TFRC_SSTATE_FBACK:
1086                 if (len > 0) {
1087                         hctx->ccid3hctx_t_nom = now;
1088                         ccid3_calc_new_t_ipi(hctx);
1089                         ccid3_calc_new_delta(hctx);
1090                         timeval_add_usecs(&hctx->ccid3hctx_t_nom,
1091                                           hctx->ccid3hctx_t_ipi);
1092                 }
1093                 break;
1094         default:
1095                 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1096                        __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
1097                 dump_stack();
1098                 break;
1099         }
1100 }
1101
1102 static void ccid3_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
1103 {
1104         struct dccp_sock *dp = dccp_sk(sk);
1105         struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1106         struct ccid3_options_received *opt_recv;
1107         struct dccp_tx_hist_entry *packet;
1108         unsigned long next_tmout;
1109         u32 t_elapsed;
1110         u32 pinv;
1111         u32 x_recv;
1112         u32 r_sample;
1113
1114         if (hctx == NULL)
1115                 return;
1116
1117         if (hctx->ccid3hctx_state == TFRC_SSTATE_TERM) {
1118                 ccid3_pr_debug("%s, sk=%p, received a packet when "
1119                                "terminating!\n", dccp_role(sk), sk);
1120                 return;
1121         }
1122
1123         /* we are only interested in ACKs */
1124         if (!(DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_ACK ||
1125               DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_DATAACK))
1126                 return;
1127
1128         opt_recv = &hctx->ccid3hctx_options_received;
1129
1130         t_elapsed = dp->dccps_options_received.dccpor_elapsed_time;
1131         x_recv = opt_recv->ccid3or_receive_rate;
1132         pinv = opt_recv->ccid3or_loss_event_rate;
1133
1134         switch (hctx->ccid3hctx_state) {
1135         case TFRC_SSTATE_NO_SENT:
1136                 /* FIXME: what to do here? */
1137                 return;
1138         case TFRC_SSTATE_NO_FBACK:
1139         case TFRC_SSTATE_FBACK:
1140                 /* Calculate new round trip sample by
1141                  * R_sample = (now - t_recvdata) - t_delay */
1142                 /* get t_recvdata from history */
1143                 packet = dccp_tx_hist_find_entry(&hctx->ccid3hctx_hist,
1144                                                  DCCP_SKB_CB(skb)->dccpd_ack_seq);
1145                 if (packet == NULL) {
1146                         ccid3_pr_debug("%s, sk=%p, seqno %llu(%s) does't "
1147                                        "exist in history!\n",
1148                                        dccp_role(sk), sk,
1149                                        DCCP_SKB_CB(skb)->dccpd_ack_seq,
1150                                        dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type));
1151                         return;
1152                 }
1153
1154                 /* Update RTT */
1155                 r_sample = timeval_now_delta(&packet->dccphtx_tstamp);
1156                 /* FIXME: */
1157                 // r_sample -= usecs_to_jiffies(t_elapsed * 10);
1158
1159                 /* Update RTT estimate by
1160                  * If (No feedback recv)
1161                  *    R = R_sample;
1162                  * Else
1163                  *    R = q * R + (1 - q) * R_sample;
1164                  *
1165                  * q is a constant, RFC 3448 recomments 0.9
1166                  */
1167                 if (hctx->ccid3hctx_state == TFRC_SSTATE_NO_FBACK) {
1168                         ccid3_hc_tx_set_state(sk, TFRC_SSTATE_FBACK);
1169                         hctx->ccid3hctx_rtt = r_sample;
1170                 } else
1171                         hctx->ccid3hctx_rtt = (hctx->ccid3hctx_rtt * 9) / 10 +
1172                                               r_sample / 10;
1173
1174                 /*
1175                  * XXX: this is to avoid a division by zero in ccid3_hc_tx_packet_sent
1176                  *      implemention of the new window count.
1177                  */
1178                 if (hctx->ccid3hctx_rtt < 4)
1179                         hctx->ccid3hctx_rtt = 4;
1180
1181                 ccid3_pr_debug("%s, sk=%p, New RTT estimate=%uus, "
1182                                "r_sample=%us\n", dccp_role(sk), sk,
1183                                hctx->ccid3hctx_rtt, r_sample);
1184
1185                 /* Update timeout interval */
1186                 hctx->ccid3hctx_t_rto = max_t(u32, 4 * hctx->ccid3hctx_rtt,
1187                                               USEC_PER_SEC);
1188
1189                 /* Update receive rate */
1190                 hctx->ccid3hctx_x_recv = x_recv;/* X_recv in bytes per sec */
1191
1192                 /* Update loss event rate */
1193                 if (pinv == ~0 || pinv == 0)
1194                         hctx->ccid3hctx_p = 0;
1195                 else {
1196                         hctx->ccid3hctx_p = 1000000 / pinv;
1197
1198                         if (hctx->ccid3hctx_p < TFRC_SMALLEST_P) {
1199                                 hctx->ccid3hctx_p = TFRC_SMALLEST_P;
1200                                 ccid3_pr_debug("%s, sk=%p, Smallest p used!\n",
1201                                                dccp_role(sk), sk);
1202                         }
1203                 }
1204
1205                 /* unschedule no feedback timer */
1206                 sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer);
1207
1208                 /* Update sending rate */
1209                 ccid3_hc_tx_update_x(sk);
1210
1211                 /* Update next send time */
1212                 timeval_sub_usecs(&hctx->ccid3hctx_t_nom,
1213                                   hctx->ccid3hctx_t_ipi);
1214                 ccid3_calc_new_t_ipi(hctx);
1215                 timeval_add_usecs(&hctx->ccid3hctx_t_nom,
1216                                   hctx->ccid3hctx_t_ipi);
1217                 ccid3_calc_new_delta(hctx);
1218
1219                 /* remove all packets older than the one acked from history */
1220                 dccp_tx_hist_purge_older(ccid3_tx_hist,
1221                                          &hctx->ccid3hctx_hist, packet);
1222
1223                 if (hctx->ccid3hctx_x < 10) {
1224                         ccid3_pr_debug("ccid3_hc_tx_packet_recv hctx_x < 10\n");
1225                         hctx->ccid3hctx_x = 10;
1226                 }
1227                 /* to prevent divide by zero below */
1228
1229                 /*
1230                  * Schedule no feedback timer to expire in
1231                  * max(4 * R, 2 * s / X)
1232                  */
1233                 next_tmout = max(hctx->ccid3hctx_t_rto,
1234                                  (2 * (hctx->ccid3hctx_s * 100000) /
1235                                   (hctx->ccid3hctx_x / 10)));
1236                 /* maths with 100000 and 10 is to prevent overflow with 32 bit */
1237
1238                 ccid3_pr_debug("%s, sk=%p, Scheduled no feedback timer to "
1239                                "expire in %lu jiffies (%luus)\n",
1240                                dccp_role(sk), sk,
1241                                usecs_to_jiffies(next_tmout), next_tmout);
1242
1243                 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
1244                                jiffies + max_t(u32, 1, usecs_to_jiffies(next_tmout)));
1245
1246                 /* set idle flag */
1247                 hctx->ccid3hctx_idle = 1;
1248                 break;
1249         default:
1250                 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1251                        __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
1252                 dump_stack();
1253                 break;
1254         }
1255 }
1256
1257 static void ccid3_hc_tx_insert_options(struct sock *sk, struct sk_buff *skb)
1258 {
1259         const struct dccp_sock *dp = dccp_sk(sk);
1260         struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1261
1262         if (hctx == NULL || !(sk->sk_state == DCCP_OPEN ||
1263                               sk->sk_state == DCCP_PARTOPEN))
1264                 return;
1265
1266          DCCP_SKB_CB(skb)->dccpd_ccval = hctx->ccid3hctx_last_win_count;
1267 }
1268
1269 static int ccid3_hc_tx_parse_options(struct sock *sk, unsigned char option,
1270                                      unsigned char len, u16 idx,
1271                                      unsigned char *value)
1272 {
1273         int rc = 0;
1274         struct dccp_sock *dp = dccp_sk(sk);
1275         struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1276         struct ccid3_options_received *opt_recv;
1277
1278         if (hctx == NULL)
1279                 return 0;
1280
1281         opt_recv = &hctx->ccid3hctx_options_received;
1282
1283         if (opt_recv->ccid3or_seqno != dp->dccps_gsr) {
1284                 opt_recv->ccid3or_seqno              = dp->dccps_gsr;
1285                 opt_recv->ccid3or_loss_event_rate    = ~0;
1286                 opt_recv->ccid3or_loss_intervals_idx = 0;
1287                 opt_recv->ccid3or_loss_intervals_len = 0;
1288                 opt_recv->ccid3or_receive_rate       = 0;
1289         }
1290
1291         switch (option) {
1292         case TFRC_OPT_LOSS_EVENT_RATE:
1293                 if (len != 4) {
1294                         ccid3_pr_debug("%s, sk=%p, invalid len for "
1295                                        "TFRC_OPT_LOSS_EVENT_RATE\n",
1296                                        dccp_role(sk), sk);
1297                         rc = -EINVAL;
1298                 } else {
1299                         opt_recv->ccid3or_loss_event_rate = ntohl(*(u32 *)value);
1300                         ccid3_pr_debug("%s, sk=%p, LOSS_EVENT_RATE=%u\n",
1301                                        dccp_role(sk), sk,
1302                                        opt_recv->ccid3or_loss_event_rate);
1303                 }
1304                 break;
1305         case TFRC_OPT_LOSS_INTERVALS:
1306                 opt_recv->ccid3or_loss_intervals_idx = idx;
1307                 opt_recv->ccid3or_loss_intervals_len = len;
1308                 ccid3_pr_debug("%s, sk=%p, LOSS_INTERVALS=(%u, %u)\n",
1309                                dccp_role(sk), sk,
1310                                opt_recv->ccid3or_loss_intervals_idx,
1311                                opt_recv->ccid3or_loss_intervals_len);
1312                 break;
1313         case TFRC_OPT_RECEIVE_RATE:
1314                 if (len != 4) {
1315                         ccid3_pr_debug("%s, sk=%p, invalid len for "
1316                                        "TFRC_OPT_RECEIVE_RATE\n",
1317                                        dccp_role(sk), sk);
1318                         rc = -EINVAL;
1319                 } else {
1320                         opt_recv->ccid3or_receive_rate = ntohl(*(u32 *)value);
1321                         ccid3_pr_debug("%s, sk=%p, RECEIVE_RATE=%u\n",
1322                                        dccp_role(sk), sk,
1323                                        opt_recv->ccid3or_receive_rate);
1324                 }
1325                 break;
1326         }
1327
1328         return rc;
1329 }
1330
1331 static int ccid3_hc_tx_init(struct sock *sk)
1332 {
1333         struct dccp_sock *dp = dccp_sk(sk);
1334         struct ccid3_hc_tx_sock *hctx;
1335
1336         ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1337
1338         hctx = dp->dccps_hc_tx_ccid_private = kmalloc(sizeof(*hctx),
1339                                                       gfp_any());
1340         if (hctx == NULL)
1341                 return -ENOMEM;
1342
1343         memset(hctx, 0, sizeof(*hctx));
1344
1345         if (dp->dccps_avg_packet_size >= TFRC_MIN_PACKET_SIZE &&
1346             dp->dccps_avg_packet_size <= TFRC_MAX_PACKET_SIZE)
1347                 hctx->ccid3hctx_s = (u16)dp->dccps_avg_packet_size;
1348         else
1349                 hctx->ccid3hctx_s = TFRC_STD_PACKET_SIZE;
1350
1351         /* Set transmission rate to 1 packet per second */
1352         hctx->ccid3hctx_x     = hctx->ccid3hctx_s;
1353         /* See ccid3_hc_tx_packet_sent win_count calculatation */
1354         hctx->ccid3hctx_rtt   = 4;
1355         hctx->ccid3hctx_t_rto = USEC_PER_SEC;
1356         hctx->ccid3hctx_state = TFRC_SSTATE_NO_SENT;
1357         INIT_LIST_HEAD(&hctx->ccid3hctx_hist);
1358         init_timer(&hctx->ccid3hctx_no_feedback_timer);
1359
1360         return 0;
1361 }
1362
1363 static void ccid3_hc_tx_exit(struct sock *sk)
1364 {
1365         struct dccp_sock *dp = dccp_sk(sk);
1366         struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1367
1368         ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1369         BUG_ON(hctx == NULL);
1370
1371         ccid3_hc_tx_set_state(sk, TFRC_SSTATE_TERM);
1372         sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer);
1373
1374         /* Empty packet history */
1375         dccp_tx_hist_purge(ccid3_tx_hist, &hctx->ccid3hctx_hist);
1376
1377         kfree(dp->dccps_hc_tx_ccid_private);
1378         dp->dccps_hc_tx_ccid_private = NULL;
1379 }
1380
1381 /*
1382  * RX Half Connection methods
1383  */
1384
1385 /* TFRC receiver states */
1386 enum ccid3_hc_rx_states {
1387         TFRC_RSTATE_NO_DATA = 1,
1388         TFRC_RSTATE_DATA,
1389         TFRC_RSTATE_TERM    = 127,
1390 };
1391
1392 #ifdef CCID3_DEBUG
1393 static const char *ccid3_rx_state_name(enum ccid3_hc_rx_states state)
1394 {
1395         static char *ccid3_rx_state_names[] = {
1396         [TFRC_RSTATE_NO_DATA] = "NO_DATA",
1397         [TFRC_RSTATE_DATA]    = "DATA",
1398         [TFRC_RSTATE_TERM]    = "TERM",
1399         };
1400
1401         return ccid3_rx_state_names[state];
1402 }
1403 #endif
1404
1405 static inline void ccid3_hc_rx_set_state(struct sock *sk,
1406                                          enum ccid3_hc_rx_states state)
1407 {
1408         struct dccp_sock *dp = dccp_sk(sk);
1409         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1410         enum ccid3_hc_rx_states oldstate = hcrx->ccid3hcrx_state;
1411
1412         ccid3_pr_debug("%s(%p) %-8.8s -> %s\n",
1413                        dccp_role(sk), sk, ccid3_rx_state_name(oldstate),
1414                        ccid3_rx_state_name(state));
1415         WARN_ON(state == oldstate);
1416         hcrx->ccid3hcrx_state = state;
1417 }
1418
1419 static int ccid3_hc_rx_add_hist(struct sock *sk,
1420                                 struct dccp_rx_hist_entry *packet)
1421 {
1422         struct dccp_sock *dp = dccp_sk(sk);
1423         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1424         struct dccp_rx_hist_entry *entry, *next, *iter;
1425         u8 num_later = 0;
1426
1427         iter = dccp_rx_hist_head(&hcrx->ccid3hcrx_hist);
1428         if (iter == NULL)
1429                 dccp_rx_hist_add_entry(&hcrx->ccid3hcrx_hist, packet);
1430         else {
1431                 const u64 seqno = packet->dccphrx_seqno;
1432
1433                 if (after48(seqno, iter->dccphrx_seqno))
1434                         dccp_rx_hist_add_entry(&hcrx->ccid3hcrx_hist, packet);
1435                 else {
1436                         if (dccp_rx_hist_entry_data_packet(iter))
1437                                 num_later = 1;
1438
1439                         list_for_each_entry_continue(iter,
1440                                                      &hcrx->ccid3hcrx_hist,
1441                                                      dccphrx_node) {
1442                                 if (after48(seqno, iter->dccphrx_seqno)) {
1443                                         dccp_rx_hist_add_entry(&iter->dccphrx_node,
1444                                                                packet);
1445                                         goto trim_history;
1446                                 }
1447
1448                                 if (dccp_rx_hist_entry_data_packet(iter))
1449                                         num_later++;
1450
1451                                 if (num_later == TFRC_RECV_NUM_LATE_LOSS) {
1452                                         dccp_rx_hist_entry_delete(ccid3_rx_hist,
1453                                                                   packet);
1454                                         ccid3_pr_debug("%s, sk=%p, packet"
1455                                                        "(%llu) already lost!\n",
1456                                                        dccp_role(sk), sk,
1457                                                        seqno);
1458                                         return 1;
1459                                 }
1460                         }
1461
1462                         if (num_later < TFRC_RECV_NUM_LATE_LOSS)
1463                                 dccp_rx_hist_add_entry(&hcrx->ccid3hcrx_hist,
1464                                                        packet);
1465                         /*
1466                          * FIXME: else what? should we destroy the packet
1467                          * like above?
1468                          */
1469                 }
1470         }
1471
1472 trim_history:
1473         /*
1474          * Trim history (remove all packets after the NUM_LATE_LOSS + 1
1475          * data packets)
1476          */
1477         num_later = TFRC_RECV_NUM_LATE_LOSS + 1;
1478
1479         if (!list_empty(&hcrx->ccid3hcrx_loss_interval_hist)) {
1480                 list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
1481                                          dccphrx_node) {
1482                         if (num_later == 0) {
1483                                 list_del_init(&entry->dccphrx_node);
1484                                 dccp_rx_hist_entry_delete(ccid3_rx_hist, entry);
1485                         } else if (dccp_rx_hist_entry_data_packet(entry))
1486                                 --num_later;
1487                 }
1488         } else {
1489                 int step = 0;
1490                 u8 win_count = 0; /* Not needed, but lets shut up gcc */
1491                 int tmp;
1492                 /*
1493                  * We have no loss interval history so we need at least one
1494                  * rtt:s of data packets to approximate rtt.
1495                  */
1496                 list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
1497                                          dccphrx_node) {
1498                         if (num_later == 0) {
1499                                 switch (step) {
1500                                 case 0:
1501                                         step = 1;
1502                                         /* OK, find next data packet */
1503                                         num_later = 1;
1504                                         break;
1505                                 case 1:
1506                                         step = 2;
1507                                         /* OK, find next data packet */
1508                                         num_later = 1;
1509                                         win_count = entry->dccphrx_ccval;
1510                                         break;
1511                                 case 2:
1512                                         tmp = win_count - entry->dccphrx_ccval;
1513                                         if (tmp < 0)
1514                                                 tmp += TFRC_WIN_COUNT_LIMIT;
1515                                         if (tmp > TFRC_WIN_COUNT_PER_RTT + 1) {
1516                                                 /*
1517                                                  * We have found a packet older
1518                                                  * than one rtt remove the rest
1519                                                  */
1520                                                 step = 3;
1521                                         } else /* OK, find next data packet */
1522                                                 num_later = 1;
1523                                         break;
1524                                 case 3:
1525                                         list_del_init(&entry->dccphrx_node);
1526                                         dccp_rx_hist_entry_delete(ccid3_rx_hist,
1527                                                                   entry);
1528                                         break;
1529                                 }
1530                         } else if (dccp_rx_hist_entry_data_packet(entry))
1531                                 --num_later;
1532                 }
1533         }
1534
1535         return 0;
1536 }
1537
1538 static void ccid3_hc_rx_send_feedback(struct sock *sk)
1539 {
1540         struct dccp_sock *dp = dccp_sk(sk);
1541         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1542         struct dccp_rx_hist_entry *packet;
1543         struct timeval now;
1544
1545         ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1546
1547         do_gettimeofday(&now);
1548
1549         switch (hcrx->ccid3hcrx_state) {
1550         case TFRC_RSTATE_NO_DATA:
1551                 hcrx->ccid3hcrx_x_recv = 0;
1552                 break;
1553         case TFRC_RSTATE_DATA: {
1554                 const u32 delta = timeval_delta(&now,
1555                                         &hcrx->ccid3hcrx_tstamp_last_feedback);
1556
1557                 hcrx->ccid3hcrx_x_recv = (hcrx->ccid3hcrx_bytes_recv *
1558                                           USEC_PER_SEC);
1559                 if (likely(delta > 1))
1560                         hcrx->ccid3hcrx_x_recv /= delta;
1561         }
1562                 break;
1563         default:
1564                 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1565                        __FUNCTION__, dccp_role(sk), sk, hcrx->ccid3hcrx_state);
1566                 dump_stack();
1567                 return;
1568         }
1569
1570         packet = dccp_rx_hist_find_data_packet(&hcrx->ccid3hcrx_hist);
1571         if (packet == NULL) {
1572                 printk(KERN_CRIT "%s: %s, sk=%p, no data packet in history!\n",
1573                        __FUNCTION__, dccp_role(sk), sk);
1574                 dump_stack();
1575                 return;
1576         }
1577
1578         hcrx->ccid3hcrx_tstamp_last_feedback = now;
1579         hcrx->ccid3hcrx_last_counter         = packet->dccphrx_ccval;
1580         hcrx->ccid3hcrx_seqno_last_counter   = packet->dccphrx_seqno;
1581         hcrx->ccid3hcrx_bytes_recv           = 0;
1582
1583         /* Convert to multiples of 10us */
1584         hcrx->ccid3hcrx_elapsed_time =
1585                         timeval_delta(&now, &packet->dccphrx_tstamp) / 10;
1586         if (hcrx->ccid3hcrx_p == 0)
1587                 hcrx->ccid3hcrx_pinv = ~0;
1588         else
1589                 hcrx->ccid3hcrx_pinv = 1000000 / hcrx->ccid3hcrx_p;
1590         dccp_send_ack(sk);
1591 }
1592
1593 static void ccid3_hc_rx_insert_options(struct sock *sk, struct sk_buff *skb)
1594 {
1595         const struct dccp_sock *dp = dccp_sk(sk);
1596         u32 x_recv, pinv;
1597         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1598
1599         if (hcrx == NULL || !(sk->sk_state == DCCP_OPEN ||
1600                               sk->sk_state == DCCP_PARTOPEN))
1601                 return;
1602
1603         DCCP_SKB_CB(skb)->dccpd_ccval = hcrx->ccid3hcrx_last_counter;
1604
1605         if (dccp_packet_without_ack(skb))
1606                 return;
1607
1608         if (hcrx->ccid3hcrx_elapsed_time != 0)
1609                 dccp_insert_option_elapsed_time(sk, skb,
1610                                                 hcrx->ccid3hcrx_elapsed_time);
1611         dccp_insert_option_timestamp(sk, skb);
1612         x_recv = htonl(hcrx->ccid3hcrx_x_recv);
1613         pinv   = htonl(hcrx->ccid3hcrx_pinv);
1614         dccp_insert_option(sk, skb, TFRC_OPT_LOSS_EVENT_RATE,
1615                            &pinv, sizeof(pinv));
1616         dccp_insert_option(sk, skb, TFRC_OPT_RECEIVE_RATE,
1617                            &x_recv, sizeof(x_recv));
1618 }
1619
1620 /* Weights used to calculate loss event rate */
1621 /*
1622  * These are integers as per section 8 of RFC3448. We can then divide by 4 *
1623  * when we use it.
1624  */
1625 static const int ccid3_hc_rx_w[TFRC_RECV_IVAL_F_LENGTH] = {
1626         4, 4, 4, 4, 3, 2, 1, 1,
1627 };
1628
1629 /*
1630  * args: fvalue - function value to match
1631  * returns:  p  closest to that value
1632  *
1633  * both fvalue and p are multiplied by 1,000,000 to use ints
1634  */
1635 static u32 calcx_reverse_lookup(u32 fvalue) {
1636         int ctr = 0;
1637         int small;
1638
1639         if (fvalue < calcx_lookup[0][1])
1640                 return 0;
1641         if (fvalue <= calcx_lookup[CALCX_ARRSIZE-1][1])
1642                 small = 1;
1643         else if (fvalue > calcx_lookup[CALCX_ARRSIZE-1][0])
1644                 return 1000000;
1645         else
1646                 small = 0;
1647         while (fvalue > calcx_lookup[ctr][small])
1648                 ctr++;
1649         if (small)
1650                 return (CALCX_SPLIT * ctr / CALCX_ARRSIZE);
1651         else
1652                 return (1000000 * ctr / CALCX_ARRSIZE) ;
1653 }
1654
1655 /* calculate first loss interval
1656  *
1657  * returns estimated loss interval in usecs */
1658
1659 static u32 ccid3_hc_rx_calc_first_li(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, *tail = NULL;
1664         u32 rtt, delta, x_recv, fval, p, tmp2;
1665         struct timeval tstamp = { 0, };
1666         int interval = 0;
1667         int win_count = 0;
1668         int step = 0;
1669         u64 tmp1;
1670
1671         list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
1672                                  dccphrx_node) {
1673                 if (dccp_rx_hist_entry_data_packet(entry)) {
1674                         tail = entry;
1675
1676                         switch (step) {
1677                         case 0:
1678                                 tstamp    = entry->dccphrx_tstamp;
1679                                 win_count = entry->dccphrx_ccval;
1680                                 step = 1;
1681                                 break;
1682                         case 1:
1683                                 interval = win_count - entry->dccphrx_ccval;
1684                                 if (interval < 0)
1685                                         interval += TFRC_WIN_COUNT_LIMIT;
1686                                 if (interval > 4)
1687                                         goto found;
1688                                 break;
1689                         }
1690                 }
1691         }
1692
1693         if (step == 0) {
1694                 printk(KERN_CRIT "%s: %s, sk=%p, packet history contains no "
1695                                  "data packets!\n",
1696                        __FUNCTION__, dccp_role(sk), sk);
1697                 return ~0;
1698         }
1699
1700         if (interval == 0) {
1701                 ccid3_pr_debug("%s, sk=%p, Could not find a win_count "
1702                                "interval > 0. Defaulting to 1\n",
1703                                dccp_role(sk), sk);
1704                 interval = 1;
1705         }
1706 found:
1707         rtt = timeval_delta(&tstamp, &tail->dccphrx_tstamp) * 4 / interval;
1708         ccid3_pr_debug("%s, sk=%p, approximated RTT to %uus\n",
1709                        dccp_role(sk), sk, rtt);
1710         if (rtt == 0)
1711                 rtt = 1;
1712
1713         delta = timeval_now_delta(&hcrx->ccid3hcrx_tstamp_last_feedback);
1714         x_recv = hcrx->ccid3hcrx_bytes_recv * USEC_PER_SEC;
1715         if (likely(delta > 1))
1716                 x_recv /= delta;
1717
1718         tmp1 = (u64)x_recv * (u64)rtt;
1719         do_div(tmp1,10000000);
1720         tmp2 = (u32)tmp1;
1721         fval = (hcrx->ccid3hcrx_s * 100000) / tmp2;
1722         /* do not alter order above or you will get overflow on 32 bit */
1723         p = calcx_reverse_lookup(fval);
1724         ccid3_pr_debug("%s, sk=%p, receive rate=%u bytes/s, implied "
1725                        "loss rate=%u\n", dccp_role(sk), sk, x_recv, p);
1726
1727         if (p == 0)
1728                 return ~0;
1729         else
1730                 return 1000000 / p;
1731 }
1732
1733 static void ccid3_hc_rx_update_li(struct sock *sk, u64 seq_loss, u8 win_loss)
1734 {
1735         struct dccp_sock *dp = dccp_sk(sk);
1736         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1737         struct ccid3_loss_interval_hist_entry *li_entry;
1738
1739         if (seq_loss != DCCP_MAX_SEQNO + 1) {
1740                 ccid3_pr_debug("%s, sk=%p, seq_loss=%llu, win_loss=%u, "
1741                                "packet loss detected\n",
1742                                dccp_role(sk), sk, seq_loss, win_loss);
1743
1744                 if (list_empty(&hcrx->ccid3hcrx_loss_interval_hist)) {
1745                         struct ccid3_loss_interval_hist_entry *li_tail = NULL;
1746                         int i;
1747
1748                         ccid3_pr_debug("%s, sk=%p, first loss event detected, "
1749                                        "creating history\n",
1750                                        dccp_role(sk), sk);
1751                         for (i = 0; i <= TFRC_RECV_IVAL_F_LENGTH; ++i) {
1752                                 li_entry = ccid3_loss_interval_hist_entry_new(SLAB_ATOMIC);
1753                                 if (li_entry == NULL) {
1754                                         ccid3_loss_interval_history_delete(&hcrx->ccid3hcrx_loss_interval_hist);
1755                                         ccid3_pr_debug("%s, sk=%p, not enough "
1756                                                        "mem for creating "
1757                                                        "history\n",
1758                                                        dccp_role(sk), sk);
1759                                         return;
1760                                 }
1761                                 if (li_tail == NULL)
1762                                         li_tail = li_entry;
1763                                 list_add(&li_entry->ccid3lih_node,
1764                                          &hcrx->ccid3hcrx_loss_interval_hist);
1765                         }
1766
1767                         li_entry->ccid3lih_seqno     = seq_loss;
1768                         li_entry->ccid3lih_win_count = win_loss;
1769
1770                         li_tail->ccid3lih_interval   = ccid3_hc_rx_calc_first_li(sk);
1771                 }
1772         }
1773         /* FIXME: find end of interval */
1774 }
1775
1776 static void ccid3_hc_rx_detect_loss(struct sock *sk)
1777 {
1778         struct dccp_sock *dp = dccp_sk(sk);
1779         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1780         struct dccp_rx_hist_entry *entry, *next, *packet;
1781         struct dccp_rx_hist_entry *a_loss = NULL;
1782         struct dccp_rx_hist_entry *b_loss = NULL;
1783         u64 seq_loss = DCCP_MAX_SEQNO + 1;
1784         u8 win_loss = 0;
1785         u8 num_later = TFRC_RECV_NUM_LATE_LOSS;
1786
1787         list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
1788                                  dccphrx_node) {
1789                 if (num_later == 0) {
1790                         b_loss = entry;
1791                         break;
1792                 } else if (dccp_rx_hist_entry_data_packet(entry))
1793                         --num_later;
1794         }
1795
1796         if (b_loss == NULL)
1797                 goto out_update_li;
1798
1799         num_later = 1;
1800
1801         list_for_each_entry_safe_continue(entry, next, &hcrx->ccid3hcrx_hist,
1802                                           dccphrx_node) {
1803                 if (num_later == 0) {
1804                         a_loss = entry;
1805                         break;
1806                 } else if (dccp_rx_hist_entry_data_packet(entry))
1807                         --num_later;
1808         }
1809
1810         if (a_loss == NULL) {
1811                 if (list_empty(&hcrx->ccid3hcrx_loss_interval_hist)) {
1812                         /* no loss event have occured yet */
1813                         ccid3_pr_debug("%s, sk=%p, TODO: find a lost data "
1814                                         "packet by comparing to initial "
1815                                         "seqno\n",
1816                                        dccp_role(sk), sk);
1817                         goto out_update_li;
1818                 } else {
1819                         pr_info("%s: %s, sk=%p, ERROR! Less than 4 data "
1820                                 "packets in history",
1821                                 __FUNCTION__, dccp_role(sk), sk);
1822                         return;
1823                 }
1824         }
1825
1826         /* Locate a lost data packet */
1827         entry = packet = b_loss;
1828         list_for_each_entry_safe_continue(entry, next, &hcrx->ccid3hcrx_hist,
1829                                           dccphrx_node) {
1830                 u64 delta = dccp_delta_seqno(entry->dccphrx_seqno,
1831                                              packet->dccphrx_seqno);
1832
1833                 if (delta != 0) {
1834                         if (dccp_rx_hist_entry_data_packet(packet))
1835                                 --delta;
1836                         /*
1837                          * FIXME: check this, probably this % usage is because
1838                          * in earlier drafts the ndp count was just 8 bits
1839                          * long, but now it cam be up to 24 bits long.
1840                          */
1841 #if 0
1842                         if (delta % DCCP_NDP_LIMIT !=
1843                             (packet->dccphrx_ndp -
1844                              entry->dccphrx_ndp) % DCCP_NDP_LIMIT)
1845 #endif
1846                         if (delta !=
1847                              packet->dccphrx_ndp - entry->dccphrx_ndp) {
1848                                 seq_loss = entry->dccphrx_seqno;
1849                                 dccp_inc_seqno(&seq_loss);
1850                         }
1851                 }
1852                 packet = entry;
1853                 if (packet == a_loss)
1854                         break;
1855         }
1856
1857         if (seq_loss != DCCP_MAX_SEQNO + 1)
1858                 win_loss = a_loss->dccphrx_ccval;
1859
1860 out_update_li:
1861         ccid3_hc_rx_update_li(sk, seq_loss, win_loss);
1862 }
1863
1864 static u32 ccid3_hc_rx_calc_i_mean(struct sock *sk)
1865 {
1866         struct dccp_sock *dp = dccp_sk(sk);
1867         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1868         struct ccid3_loss_interval_hist_entry *li_entry, *li_next;
1869         int i = 0;
1870         u32 i_tot;
1871         u32 i_tot0 = 0;
1872         u32 i_tot1 = 0;
1873         u32 w_tot  = 0;
1874
1875         list_for_each_entry_safe(li_entry, li_next,
1876                                  &hcrx->ccid3hcrx_loss_interval_hist,
1877                                  ccid3lih_node) {
1878                 if (i < TFRC_RECV_IVAL_F_LENGTH) {
1879                         i_tot0 += li_entry->ccid3lih_interval * ccid3_hc_rx_w[i];
1880                         w_tot  += ccid3_hc_rx_w[i];
1881                 }
1882
1883                 if (i != 0)
1884                         i_tot1 += li_entry->ccid3lih_interval * ccid3_hc_rx_w[i - 1];
1885
1886                 if (++i > TFRC_RECV_IVAL_F_LENGTH)
1887                         break;
1888         }
1889
1890         if (i != TFRC_RECV_IVAL_F_LENGTH) {
1891                 pr_info("%s: %s, sk=%p, ERROR! Missing entry in "
1892                         "interval history!\n",
1893                         __FUNCTION__, dccp_role(sk), sk);
1894                 return 0;
1895         }
1896
1897         i_tot = max(i_tot0, i_tot1);
1898
1899         /* FIXME: Why do we do this? -Ian McDonald */
1900         if (i_tot * 4 < w_tot)
1901                 i_tot = w_tot * 4;
1902
1903         return i_tot * 4 / w_tot;
1904 }
1905
1906 static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
1907 {
1908         struct dccp_sock *dp = dccp_sk(sk);
1909         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1910         const struct dccp_options_received *opt_recv;
1911         struct dccp_rx_hist_entry *packet;
1912         struct timeval now;
1913         u8 win_count;
1914         u32 p_prev;
1915         int ins;
1916
1917         if (hcrx == NULL)
1918                 return;
1919
1920         BUG_ON(!(hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA ||
1921                  hcrx->ccid3hcrx_state == TFRC_RSTATE_DATA));
1922
1923         opt_recv = &dp->dccps_options_received;
1924
1925         switch (DCCP_SKB_CB(skb)->dccpd_type) {
1926         case DCCP_PKT_ACK:
1927                 if (hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA)
1928                         return;
1929         case DCCP_PKT_DATAACK:
1930                 if (opt_recv->dccpor_timestamp_echo == 0)
1931                         break;
1932                 p_prev = hcrx->ccid3hcrx_rtt;
1933                 do_gettimeofday(&now);
1934                 hcrx->ccid3hcrx_rtt = timeval_usecs(&now) -
1935                                      (opt_recv->dccpor_timestamp_echo -
1936                                       opt_recv->dccpor_elapsed_time) * 10;
1937                 if (p_prev != hcrx->ccid3hcrx_rtt)
1938                         ccid3_pr_debug("%s, New RTT=%luus, elapsed time=%u\n",
1939                                        dccp_role(sk), hcrx->ccid3hcrx_rtt,
1940                                        opt_recv->dccpor_elapsed_time);
1941                 break;
1942         case DCCP_PKT_DATA:
1943                 break;
1944         default:
1945                 ccid3_pr_debug("%s, sk=%p, not DATA/DATAACK/ACK packet(%s)\n",
1946                                dccp_role(sk), sk,
1947                                dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type));
1948                 return;
1949         }
1950
1951         packet = dccp_rx_hist_entry_new(ccid3_rx_hist, opt_recv->dccpor_ndp,
1952                                         skb, SLAB_ATOMIC);
1953         if (packet == NULL) {
1954                 ccid3_pr_debug("%s, sk=%p, Not enough mem to add rx packet "
1955                                "to history (consider it lost)!",
1956                                dccp_role(sk), sk);
1957                 return;
1958         }
1959
1960         win_count = packet->dccphrx_ccval;
1961
1962         ins = ccid3_hc_rx_add_hist(sk, packet);
1963
1964         if (DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_ACK)
1965                 return;
1966
1967         switch (hcrx->ccid3hcrx_state) {
1968         case TFRC_RSTATE_NO_DATA:
1969                 ccid3_pr_debug("%s, sk=%p(%s), skb=%p, sending initial "
1970                                "feedback\n",
1971                                dccp_role(sk), sk,
1972                                dccp_state_name(sk->sk_state), skb);
1973                 ccid3_hc_rx_send_feedback(sk);
1974                 ccid3_hc_rx_set_state(sk, TFRC_RSTATE_DATA);
1975                 return;
1976         case TFRC_RSTATE_DATA:
1977                 hcrx->ccid3hcrx_bytes_recv += skb->len -
1978                                               dccp_hdr(skb)->dccph_doff * 4;
1979                 if (ins != 0)
1980                         break;
1981
1982                 do_gettimeofday(&now);
1983                 if (timeval_delta(&now, &hcrx->ccid3hcrx_tstamp_last_ack) >=
1984                     hcrx->ccid3hcrx_rtt) {
1985                         hcrx->ccid3hcrx_tstamp_last_ack = now;
1986                         ccid3_hc_rx_send_feedback(sk);
1987                 }
1988                 return;
1989         default:
1990                 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1991                        __FUNCTION__, dccp_role(sk), sk, hcrx->ccid3hcrx_state);
1992                 dump_stack();
1993                 return;
1994         }
1995
1996         /* Dealing with packet loss */
1997         ccid3_pr_debug("%s, sk=%p(%s), data loss! Reacting...\n",
1998                        dccp_role(sk), sk, dccp_state_name(sk->sk_state));
1999
2000         ccid3_hc_rx_detect_loss(sk);
2001         p_prev = hcrx->ccid3hcrx_p;
2002
2003         /* Calculate loss event rate */
2004         if (!list_empty(&hcrx->ccid3hcrx_loss_interval_hist))
2005                 /* Scaling up by 1000000 as fixed decimal */
2006                 hcrx->ccid3hcrx_p = 1000000 / ccid3_hc_rx_calc_i_mean(sk);
2007
2008         if (hcrx->ccid3hcrx_p > p_prev) {
2009                 ccid3_hc_rx_send_feedback(sk);
2010                 return;
2011         }
2012 }
2013
2014 static int ccid3_hc_rx_init(struct sock *sk)
2015 {
2016         struct dccp_sock *dp = dccp_sk(sk);
2017         struct ccid3_hc_rx_sock *hcrx;
2018
2019         ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
2020
2021         hcrx = dp->dccps_hc_rx_ccid_private = kmalloc(sizeof(*hcrx),
2022                                                       gfp_any());
2023         if (hcrx == NULL)
2024                 return -ENOMEM;
2025
2026         memset(hcrx, 0, sizeof(*hcrx));
2027
2028         if (dp->dccps_avg_packet_size >= TFRC_MIN_PACKET_SIZE &&
2029             dp->dccps_avg_packet_size <= TFRC_MAX_PACKET_SIZE)
2030                 hcrx->ccid3hcrx_s = (u16)dp->dccps_avg_packet_size;
2031         else
2032                 hcrx->ccid3hcrx_s = TFRC_STD_PACKET_SIZE;
2033
2034         hcrx->ccid3hcrx_state = TFRC_RSTATE_NO_DATA;
2035         INIT_LIST_HEAD(&hcrx->ccid3hcrx_hist);
2036         INIT_LIST_HEAD(&hcrx->ccid3hcrx_loss_interval_hist);
2037         /*
2038          * XXX this seems to be paranoid, need to think more about this, for
2039          * now start with something different than zero. -acme
2040          */
2041         hcrx->ccid3hcrx_rtt = USEC_PER_SEC / 5;
2042         return 0;
2043 }
2044
2045 static void ccid3_hc_rx_exit(struct sock *sk)
2046 {
2047         struct dccp_sock *dp = dccp_sk(sk);
2048         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
2049
2050         ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
2051
2052         if (hcrx == NULL)
2053                 return;
2054
2055         ccid3_hc_rx_set_state(sk, TFRC_RSTATE_TERM);
2056
2057         /* Empty packet history */
2058         dccp_rx_hist_purge(ccid3_rx_hist, &hcrx->ccid3hcrx_hist);
2059
2060         /* Empty loss interval history */
2061         ccid3_loss_interval_history_delete(&hcrx->ccid3hcrx_loss_interval_hist);
2062
2063         kfree(dp->dccps_hc_rx_ccid_private);
2064         dp->dccps_hc_rx_ccid_private = NULL;
2065 }
2066
2067 static void ccid3_hc_rx_get_info(struct sock *sk, struct tcp_info *info)
2068 {
2069         const struct dccp_sock *dp = dccp_sk(sk);
2070         const struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
2071
2072         if (hcrx == NULL)
2073                 return;
2074
2075         info->tcpi_ca_state     = hcrx->ccid3hcrx_state;
2076         info->tcpi_options      |= TCPI_OPT_TIMESTAMPS;
2077         info->tcpi_rcv_rtt      = hcrx->ccid3hcrx_rtt;
2078 }
2079
2080 static void ccid3_hc_tx_get_info(struct sock *sk, struct tcp_info *info)
2081 {
2082         const struct dccp_sock *dp = dccp_sk(sk);
2083         const struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
2084
2085         if (hctx == NULL)
2086                 return;
2087
2088         info->tcpi_rto = hctx->ccid3hctx_t_rto;
2089         info->tcpi_rtt = hctx->ccid3hctx_rtt;
2090 }
2091
2092 static struct ccid ccid3 = {
2093         .ccid_id                   = 3,
2094         .ccid_name                 = "ccid3",
2095         .ccid_owner                = THIS_MODULE,
2096         .ccid_init                 = ccid3_init,
2097         .ccid_exit                 = ccid3_exit,
2098         .ccid_hc_tx_init           = ccid3_hc_tx_init,
2099         .ccid_hc_tx_exit           = ccid3_hc_tx_exit,
2100         .ccid_hc_tx_send_packet    = ccid3_hc_tx_send_packet,
2101         .ccid_hc_tx_packet_sent    = ccid3_hc_tx_packet_sent,
2102         .ccid_hc_tx_packet_recv    = ccid3_hc_tx_packet_recv,
2103         .ccid_hc_tx_insert_options = ccid3_hc_tx_insert_options,
2104         .ccid_hc_tx_parse_options  = ccid3_hc_tx_parse_options,
2105         .ccid_hc_rx_init           = ccid3_hc_rx_init,
2106         .ccid_hc_rx_exit           = ccid3_hc_rx_exit,
2107         .ccid_hc_rx_insert_options = ccid3_hc_rx_insert_options,
2108         .ccid_hc_rx_packet_recv    = ccid3_hc_rx_packet_recv,
2109         .ccid_hc_rx_get_info       = ccid3_hc_rx_get_info,
2110         .ccid_hc_tx_get_info       = ccid3_hc_tx_get_info,
2111 };
2112
2113 module_param(ccid3_debug, int, 0444);
2114 MODULE_PARM_DESC(ccid3_debug, "Enable debug messages");
2115
2116 static __init int ccid3_module_init(void)
2117 {
2118         int rc = -ENOBUFS;
2119
2120         ccid3_rx_hist = dccp_rx_hist_new("ccid3");
2121         if (ccid3_rx_hist == NULL)
2122                 goto out;
2123
2124         ccid3_tx_hist = dccp_tx_hist_new("ccid3");
2125         if (ccid3_tx_hist == NULL)
2126                 goto out_free_rx;
2127
2128         ccid3_loss_interval_hist_slab = kmem_cache_create("li_hist_ccid3",
2129                                   sizeof(struct ccid3_loss_interval_hist_entry),
2130                                                           0, SLAB_HWCACHE_ALIGN,
2131                                                           NULL, NULL);
2132         if (ccid3_loss_interval_hist_slab == NULL)
2133                 goto out_free_tx;
2134
2135         rc = ccid_register(&ccid3);
2136         if (rc != 0)
2137                 goto out_free_loss_interval_history;
2138 out:
2139         return rc;
2140
2141 out_free_loss_interval_history:
2142         kmem_cache_destroy(ccid3_loss_interval_hist_slab);
2143         ccid3_loss_interval_hist_slab = NULL;
2144 out_free_tx:
2145         dccp_tx_hist_delete(ccid3_tx_hist);
2146         ccid3_tx_hist = NULL;
2147 out_free_rx:
2148         dccp_rx_hist_delete(ccid3_rx_hist);
2149         ccid3_rx_hist = NULL;
2150         goto out;
2151 }
2152 module_init(ccid3_module_init);
2153
2154 static __exit void ccid3_module_exit(void)
2155 {
2156 #ifdef CONFIG_IP_DCCP_UNLOAD_HACK
2157         /*
2158          * Hack to use while developing, so that we get rid of the control
2159          * sock, that is what keeps a refcount on dccp.ko -acme
2160          */
2161         extern void dccp_ctl_sock_exit(void);
2162
2163         dccp_ctl_sock_exit();
2164 #endif
2165         ccid_unregister(&ccid3);
2166
2167         if (ccid3_tx_hist != NULL) {
2168                 dccp_tx_hist_delete(ccid3_tx_hist);
2169                 ccid3_tx_hist = NULL;
2170         }
2171         if (ccid3_rx_hist != NULL) {
2172                 dccp_rx_hist_delete(ccid3_rx_hist);
2173                 ccid3_rx_hist = NULL;
2174         }
2175         if (ccid3_loss_interval_hist_slab != NULL) {
2176                 kmem_cache_destroy(ccid3_loss_interval_hist_slab);
2177                 ccid3_loss_interval_hist_slab = NULL;
2178         }
2179 }
2180 module_exit(ccid3_module_exit);
2181
2182 MODULE_AUTHOR("Ian McDonald <iam4@cs.waikato.ac.nz>, "
2183               "Arnaldo Carvalho de Melo <acme@ghostprotocols.net>");
2184 MODULE_DESCRIPTION("DCCP TFRC CCID3 CCID");
2185 MODULE_LICENSE("GPL");
2186 MODULE_ALIAS("net-dccp-ccid-3");