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