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