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

   1 /*
   2  *  net/dccp/ccids/ccid3.c
   3  *
   4  *  Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand.
   5  *  Copyright (c) 2005 Ian McDonald <iam4@cs.waikato.ac.nz>
   6  *
   7  *  An implementation of the DCCP protocol
   8  *
   9  *  This code has been developed by the University of Waikato WAND
  10  *  research group. For further information please see http://www.wand.net.nz/
  11  *
  12  *  This code also uses code from Lulea University, rereleased as GPL by its
  13  *  authors:
  14  *  Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
  15  *
  16  *  Changes to meet Linux coding standards, to make it meet latest ccid3 draft
  17  *  and to make it work as a loadable module in the DCCP stack written by
  18  *  Arnaldo Carvalho de Melo <acme@conectiva.com.br>.
  19  *
  20  *  Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
  21  *
  22  *  This program is free software; you can redistribute it and/or modify
  23  *  it under the terms of the GNU General Public License as published by
  24  *  the Free Software Foundation; either version 2 of the License, or
  25  *  (at your option) any later version.
  26  *
  27  *  This program is distributed in the hope that it will be useful,
  28  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  29  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  30  *  GNU General Public License for more details.
  31  *
  32  *  You should have received a copy of the GNU General Public License
  33  *  along with this program; if not, write to the Free Software
  34  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  35  */
  36
  37 #include <linux/config.h>
  38 #include "../ccid.h"
  39 #include "../dccp.h"
  40 #include "../packet_history.h"
  41 #include "ccid3.h"
  42
  43 #ifdef CCID3_DEBUG
  44 extern int ccid3_debug;
  45
  46 #define ccid3_pr_debug(format, a...) \
  47         do { if (ccid3_debug) \
  48                 printk(KERN_DEBUG "%s: " format, __FUNCTION__, ##a); \
  49         } while (0)
  50 #else
  51 #define ccid3_pr_debug(format, a...)
  52 #endif
  53
  54 #define TFRC_MIN_PACKET_SIZE       16
  55 #define TFRC_STD_PACKET_SIZE      256
  56 #define TFRC_MAX_PACKET_SIZE    65535
  57
  58 #define TFRC_INITIAL_TIMEOUT       (2 * USEC_PER_SEC)
  59 /* two seconds as per CCID3 spec 11 */
  60
  61 #define TFRC_OPSYS_HALF_TIME_GRAN       (USEC_PER_SEC / (2 * HZ))
  62 /* above is in usecs - half the scheduling granularity as per RFC3448 4.6 */
  63
  64 #define TFRC_WIN_COUNT_PER_RTT      4
  65 #define TFRC_WIN_COUNT_LIMIT       16
  66
  67 #define TFRC_MAX_BACK_OFF_TIME     64
  68 /* above is in seconds */
  69
  70 #define TFRC_SMALLEST_P            40
  71
  72 #define TFRC_RECV_IVAL_F_LENGTH     8          /* length(w[]) */
  73
  74 /* Number of later packets received before one is considered lost */
  75 #define TFRC_RECV_NUM_LATE_LOSS 3
  76
  77 enum ccid3_options {
  78         TFRC_OPT_LOSS_EVENT_RATE = 192,
  79         TFRC_OPT_LOSS_INTERVALS  = 193,
  80         TFRC_OPT_RECEIVE_RATE    = 194,
  81 };
  82
  83 static int ccid3_debug;
  84
  85 static struct dccp_tx_hist *ccid3_tx_hist;
  86 static struct dccp_rx_hist *ccid3_rx_hist;
  87
  88 static kmem_cache_t *ccid3_loss_interval_hist_slab __read_mostly;
  89
  90 static inline struct ccid3_loss_interval_hist_entry *
  91         ccid3_loss_interval_hist_entry_new(const unsigned int __nocast prio)
  92 {
  93         return kmem_cache_alloc(ccid3_loss_interval_hist_slab, prio);
  94 }
  95
  96 static inline void ccid3_loss_interval_hist_entry_delete(struct ccid3_loss_interval_hist_entry *entry)
  97 {
  98         if (entry != NULL)
  99                 kmem_cache_free(ccid3_loss_interval_hist_slab, entry);
 100 }
 101
 102 static void ccid3_loss_interval_history_delete(struct list_head *hist)
 103 {
 104         struct ccid3_loss_interval_hist_entry *entry, *next;
 105
 106         list_for_each_entry_safe(entry, next, hist, ccid3lih_node) {
 107                 list_del_init(&entry->ccid3lih_node);
 108                 kmem_cache_free(ccid3_loss_interval_hist_slab, entry);
 109         }
 110 }
 111
 112 static int ccid3_init(struct sock *sk)
 113 {
 114         ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
 115         return 0;
 116 }
 117
 118 static void ccid3_exit(struct sock *sk)
 119 {
 120         ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
 121 }
 122
 123 /* TFRC sender states */
 124 enum ccid3_hc_tx_states {
 125         TFRC_SSTATE_NO_SENT = 1,
 126         TFRC_SSTATE_NO_FBACK,
 127         TFRC_SSTATE_FBACK,
 128         TFRC_SSTATE_TERM,
 129 };
 130
 131 #ifdef CCID3_DEBUG
 132 static const char *ccid3_tx_state_name(enum ccid3_hc_tx_states state)
 133 {
 134         static char *ccid3_state_names[] = {
 135         [TFRC_SSTATE_NO_SENT]  = "NO_SENT",
 136         [TFRC_SSTATE_NO_FBACK] = "NO_FBACK",
 137         [TFRC_SSTATE_FBACK]    = "FBACK",
 138         [TFRC_SSTATE_TERM]     = "TERM",
 139         };
 140
 141         return ccid3_state_names[state];
 142 }
 143 #endif
 144
 145 static inline void ccid3_hc_tx_set_state(struct sock *sk, 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, hctx->ccid3hctx_t_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 ? delay : 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         BUG_ON(hctx == NULL);
1014
1015         if (hctx->ccid3hctx_state == TFRC_SSTATE_TERM) {
1016                 ccid3_pr_debug("%s, sk=%p, while state is TFRC_SSTATE_TERM!\n",
1017                                dccp_role(sk), sk);
1018                 return;
1019         }
1020
1021         do_gettimeofday(&now);
1022
1023         /* check if we have sent a data packet */
1024         if (len > 0) {
1025                 unsigned long quarter_rtt;
1026                 struct dccp_tx_hist_entry *packet;
1027
1028                 packet = dccp_tx_hist_head(&hctx->ccid3hctx_hist);
1029                 if (packet == NULL) {
1030                         printk(KERN_CRIT "%s: packet doesn't exists in history!\n", __FUNCTION__);
1031                         return;
1032                 }
1033                 if (packet->dccphtx_sent) {
1034                         printk(KERN_CRIT "%s: no unsent packet in history!\n", __FUNCTION__);
1035                         return;
1036                 }
1037                 packet->dccphtx_tstamp = now;
1038                 packet->dccphtx_seqno  = dp->dccps_gss;
1039 #if 0
1040                 ccid3_pr_debug("%s, sk=%p, seqno=%llu inserted!\n",
1041                                dccp_role(sk), sk, packet->dccphtx_seqno);
1042 #endif
1043                 /*
1044                  * Check if win_count have changed */
1045                 /* COMPLIANCE_BEGIN
1046                  * Algorithm in "8.1. Window Counter Valuer" in draft-ietf-dccp-ccid3-11.txt
1047                  */
1048                 quarter_rtt = now_delta(hctx->ccid3hctx_t_last_win_count) / (hctx->ccid3hctx_rtt / 4);
1049                 if (quarter_rtt > 0) {
1050                         hctx->ccid3hctx_t_last_win_count = now;
1051                         hctx->ccid3hctx_last_win_count   = (hctx->ccid3hctx_last_win_count +
1052                                                             min_t(unsigned long, quarter_rtt, 5)) % 16;
1053                         ccid3_pr_debug("%s, sk=%p, window changed from %u to %u!\n",
1054                                        dccp_role(sk), sk,
1055                                        packet->dccphtx_ccval,
1056                                        hctx->ccid3hctx_last_win_count);
1057                 }
1058                 /* COMPLIANCE_END */
1059 #if 0
1060                 ccid3_pr_debug("%s, sk=%p, packet sent (%llu,%u)\n",
1061                                dccp_role(sk), sk,
1062                                packet->dccphtx_seqno,
1063                                packet->dccphtx_ccval);
1064 #endif
1065                 hctx->ccid3hctx_idle = 0;
1066                 packet->dccphtx_rtt  = hctx->ccid3hctx_rtt;
1067                 packet->dccphtx_sent = 1;
1068         } else
1069                 ccid3_pr_debug("%s, sk=%p, seqno=%llu NOT inserted!\n",
1070                                dccp_role(sk), sk, dp->dccps_gss);
1071
1072         switch (hctx->ccid3hctx_state) {
1073         case TFRC_SSTATE_NO_SENT:
1074                 /* if first wasn't pure ack */
1075                 if (len != 0)
1076                         printk(KERN_CRIT "%s: %s, First packet sent is noted as a data packet\n",
1077                                __FUNCTION__, dccp_role(sk));
1078                 return;
1079         case TFRC_SSTATE_NO_FBACK:
1080         case TFRC_SSTATE_FBACK:
1081                 if (len > 0) {
1082                         hctx->ccid3hctx_t_nom = now;
1083                         ccid3_calc_new_t_ipi(hctx);
1084                         ccid3_calc_new_delta(hctx);
1085                         (hctx->ccid3hctx_t_nom).tv_usec += hctx->ccid3hctx_t_ipi;
1086                         timeval_fix(&(hctx->ccid3hctx_t_nom));
1087                 }
1088                 break;
1089         default:
1090                 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1091                        __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
1092                 dump_stack();
1093                 break;
1094         }
1095 }
1096
1097 static void ccid3_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
1098 {
1099         struct dccp_sock *dp = dccp_sk(sk);
1100         struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1101         struct ccid3_options_received *opt_recv;
1102         struct dccp_tx_hist_entry *packet;
1103         unsigned long next_tmout;
1104         u32 t_elapsed;
1105         u32 pinv;
1106         u32 x_recv;
1107         u32 r_sample;
1108 #if 0
1109         ccid3_pr_debug("%s, sk=%p(%s), skb=%p(%s)\n",
1110                        dccp_role(sk), sk, dccp_state_name(sk->sk_state),
1111                        skb, dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type));
1112 #endif
1113         if (hctx == NULL)
1114                 return;
1115
1116         if (hctx->ccid3hctx_state == TFRC_SSTATE_TERM) {
1117                 ccid3_pr_debug("%s, sk=%p, received a packet when terminating!\n", dccp_role(sk), sk);
1118                 return;
1119         }
1120
1121         /* we are only interested in ACKs */
1122         if (!(DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_ACK ||
1123               DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_DATAACK))
1124                 return;
1125
1126         opt_recv = &hctx->ccid3hctx_options_received;
1127
1128         t_elapsed = dp->dccps_options_received.dccpor_elapsed_time;
1129         x_recv = opt_recv->ccid3or_receive_rate;
1130         pinv = opt_recv->ccid3or_loss_event_rate;
1131
1132         switch (hctx->ccid3hctx_state) {
1133         case TFRC_SSTATE_NO_SENT:
1134                 /* FIXME: what to do here? */
1135                 return;
1136         case TFRC_SSTATE_NO_FBACK:
1137         case TFRC_SSTATE_FBACK:
1138                 /* Calculate new round trip sample by
1139                  * R_sample = (now - t_recvdata) - t_delay */
1140                 /* get t_recvdata from history */
1141                 packet = dccp_tx_hist_find_entry(&hctx->ccid3hctx_hist,
1142                                                  DCCP_SKB_CB(skb)->dccpd_ack_seq);
1143                 if (packet == NULL) {
1144                         ccid3_pr_debug("%s, sk=%p, seqno %llu(%s) does't exist in history!\n",
1145                                        dccp_role(sk), sk, DCCP_SKB_CB(skb)->dccpd_ack_seq,
1146                                        dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type));
1147                         return;
1148                 }
1149
1150                 /* Update RTT */
1151                 r_sample = now_delta(packet->dccphtx_tstamp);
1152                 /* FIXME: */
1153                 // r_sample -= usecs_to_jiffies(t_elapsed * 10);
1154
1155                 /* Update RTT estimate by
1156                  * If (No feedback recv)
1157                  *    R = R_sample;
1158                  * Else
1159                  *    R = q * R + (1 - q) * R_sample;
1160                  *
1161                  * q is a constant, RFC 3448 recomments 0.9
1162                  */
1163                 if (hctx->ccid3hctx_state == TFRC_SSTATE_NO_FBACK) {
1164                         ccid3_hc_tx_set_state(sk, TFRC_SSTATE_FBACK);
1165                         hctx->ccid3hctx_rtt = r_sample;
1166                 } else
1167                         hctx->ccid3hctx_rtt = (hctx->ccid3hctx_rtt * 9) / 10 + r_sample / 10;
1168
1169                 /*
1170                  * XXX: this is to avoid a division by zero in ccid3_hc_tx_packet_sent
1171                  *      implemention of the new window count.
1172                  */
1173                 if (hctx->ccid3hctx_rtt < 4)
1174                         hctx->ccid3hctx_rtt = 4;
1175
1176                 ccid3_pr_debug("%s, sk=%p, New RTT estimate=%uus, r_sample=%us\n",
1177                                dccp_role(sk), sk,
1178                                hctx->ccid3hctx_rtt,
1179                                r_sample);
1180
1181                 /* Update timeout interval */
1182                 hctx->ccid3hctx_t_rto = max_t(u32, 4 * hctx->ccid3hctx_rtt,
1183                                               USEC_PER_SEC);
1184
1185                 /* Update receive rate */
1186                 hctx->ccid3hctx_x_recv = x_recv;   /* x_recv in bytes per second */
1187
1188                 /* Update loss event rate */
1189                 if (pinv == ~0 || pinv == 0)
1190                         hctx->ccid3hctx_p = 0;
1191                 else {
1192                         hctx->ccid3hctx_p = 1000000 / pinv;
1193
1194                         if (hctx->ccid3hctx_p < TFRC_SMALLEST_P) {
1195                                 hctx->ccid3hctx_p = TFRC_SMALLEST_P;
1196                                 ccid3_pr_debug("%s, sk=%p, Smallest p used!\n", dccp_role(sk), sk);
1197                         }
1198                 }
1199
1200                 /* unschedule no feedback timer */
1201                 sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer);
1202
1203                 /* Update sending rate */
1204                 ccid3_hc_tx_update_x(sk);
1205
1206                 /* Update next send time */
1207                 if (hctx->ccid3hctx_t_ipi > (hctx->ccid3hctx_t_nom).tv_usec) {
1208                         hctx->ccid3hctx_t_nom.tv_usec += USEC_PER_SEC;
1209                         (hctx->ccid3hctx_t_nom).tv_sec--;
1210                 }
1211                 /* FIXME - if no feedback then t_ipi can go > 1 second */
1212                 (hctx->ccid3hctx_t_nom).tv_usec -= hctx->ccid3hctx_t_ipi;
1213                 ccid3_calc_new_t_ipi(hctx);
1214                 (hctx->ccid3hctx_t_nom).tv_usec += hctx->ccid3hctx_t_ipi;
1215                 timeval_fix(&(hctx->ccid3hctx_t_nom));
1216                 ccid3_calc_new_delta(hctx);
1217
1218                 /* remove all packets older than the one acked from history */
1219                 dccp_tx_hist_purge_older(ccid3_tx_hist,
1220                                          &hctx->ccid3hctx_hist, packet);
1221
1222                 if (hctx->ccid3hctx_x < 10) {
1223                         ccid3_pr_debug("ccid3_hc_tx_packet_recv hctx->ccid3hctx_x < 10\n");
1224                         hctx->ccid3hctx_x = 10;
1225                 }
1226                 /* to prevent divide by zero below */
1227
1228                 /* Schedule no feedback timer to expire in max(4 * R, 2 * s / X) */
1229                 next_tmout = max(hctx->ccid3hctx_t_rto,
1230                                  (2 * (hctx->ccid3hctx_s * 100000) /
1231                                   (hctx->ccid3hctx_x / 10)));
1232                 /* maths with 100000 and 10 is to prevent overflow with 32 bit */
1233
1234                 ccid3_pr_debug("%s, sk=%p, Scheduled no feedback timer to expire in %lu jiffies (%luus)\n",
1235                                dccp_role(sk), sk, usecs_to_jiffies(next_tmout), next_tmout);
1236
1237                 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
1238                                 jiffies + max_t(u32,1,usecs_to_jiffies(next_tmout)));
1239
1240                 /* set idle flag */
1241                 hctx->ccid3hctx_idle = 1;
1242                 break;
1243         default:
1244                 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1245                        __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state);
1246                 dump_stack();
1247                 break;
1248         }
1249 }
1250
1251 static void ccid3_hc_tx_insert_options(struct sock *sk, struct sk_buff *skb)
1252 {
1253         const struct dccp_sock *dp = dccp_sk(sk);
1254         struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1255
1256         if (hctx == NULL || !(sk->sk_state == DCCP_OPEN || sk->sk_state == DCCP_PARTOPEN))
1257                 return;
1258
1259          DCCP_SKB_CB(skb)->dccpd_ccval = hctx->ccid3hctx_last_win_count;
1260 }
1261
1262 static int ccid3_hc_tx_parse_options(struct sock *sk, unsigned char option,
1263                                    unsigned char len, u16 idx, unsigned char *value)
1264 {
1265         int rc = 0;
1266         struct dccp_sock *dp = dccp_sk(sk);
1267         struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1268         struct ccid3_options_received *opt_recv;
1269
1270         if (hctx == NULL)
1271                 return 0;
1272
1273         opt_recv = &hctx->ccid3hctx_options_received;
1274
1275         if (opt_recv->ccid3or_seqno != dp->dccps_gsr) {
1276                 opt_recv->ccid3or_seqno              = dp->dccps_gsr;
1277                 opt_recv->ccid3or_loss_event_rate    = ~0;
1278                 opt_recv->ccid3or_loss_intervals_idx = 0;
1279                 opt_recv->ccid3or_loss_intervals_len = 0;
1280                 opt_recv->ccid3or_receive_rate       = 0;
1281         }
1282
1283         switch (option) {
1284         case TFRC_OPT_LOSS_EVENT_RATE:
1285                 if (len != 4) {
1286                         ccid3_pr_debug("%s, sk=%p, invalid len for TFRC_OPT_LOSS_EVENT_RATE\n",
1287                                        dccp_role(sk), sk);
1288                         rc = -EINVAL;
1289                 } else {
1290                         opt_recv->ccid3or_loss_event_rate = ntohl(*(u32 *)value);
1291                         ccid3_pr_debug("%s, sk=%p, LOSS_EVENT_RATE=%u\n",
1292                                        dccp_role(sk), sk,
1293                                        opt_recv->ccid3or_loss_event_rate);
1294                 }
1295                 break;
1296         case TFRC_OPT_LOSS_INTERVALS:
1297                 opt_recv->ccid3or_loss_intervals_idx = idx;
1298                 opt_recv->ccid3or_loss_intervals_len = len;
1299                 ccid3_pr_debug("%s, sk=%p, LOSS_INTERVALS=(%u, %u)\n",
1300                                dccp_role(sk), sk,
1301                                opt_recv->ccid3or_loss_intervals_idx,
1302                                opt_recv->ccid3or_loss_intervals_len);
1303                 break;
1304         case TFRC_OPT_RECEIVE_RATE:
1305                 if (len != 4) {
1306                         ccid3_pr_debug("%s, sk=%p, invalid len for TFRC_OPT_RECEIVE_RATE\n",
1307                                        dccp_role(sk), sk);
1308                         rc = -EINVAL;
1309                 } else {
1310                         opt_recv->ccid3or_receive_rate = ntohl(*(u32 *)value);
1311                         ccid3_pr_debug("%s, sk=%p, RECEIVE_RATE=%u\n",
1312                                        dccp_role(sk), sk,
1313                                        opt_recv->ccid3or_receive_rate);
1314                 }
1315                 break;
1316         }
1317
1318         return rc;
1319 }
1320
1321 static int ccid3_hc_tx_init(struct sock *sk)
1322 {
1323         struct dccp_sock *dp = dccp_sk(sk);
1324         struct ccid3_hc_tx_sock *hctx;
1325
1326         ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1327
1328         hctx = dp->dccps_hc_tx_ccid_private = kmalloc(sizeof(*hctx), gfp_any());
1329         if (hctx == NULL)
1330                 return -ENOMEM;
1331
1332         memset(hctx, 0, sizeof(*hctx));
1333
1334         if (dp->dccps_avg_packet_size >= TFRC_MIN_PACKET_SIZE &&
1335             dp->dccps_avg_packet_size <= TFRC_MAX_PACKET_SIZE)
1336                 hctx->ccid3hctx_s = (u16)dp->dccps_avg_packet_size;
1337         else
1338                 hctx->ccid3hctx_s = TFRC_STD_PACKET_SIZE;
1339
1340         hctx->ccid3hctx_x     = hctx->ccid3hctx_s; /* set transmission rate to 1 packet per second */
1341         hctx->ccid3hctx_rtt   = 4; /* See ccid3_hc_tx_packet_sent win_count calculatation */
1342         hctx->ccid3hctx_t_rto = USEC_PER_SEC;
1343         hctx->ccid3hctx_state = TFRC_SSTATE_NO_SENT;
1344         INIT_LIST_HEAD(&hctx->ccid3hctx_hist);
1345         init_timer(&hctx->ccid3hctx_no_feedback_timer);
1346
1347         return 0;
1348 }
1349
1350 static void ccid3_hc_tx_exit(struct sock *sk)
1351 {
1352         struct dccp_sock *dp = dccp_sk(sk);
1353         struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
1354
1355         ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1356         BUG_ON(hctx == NULL);
1357
1358         ccid3_hc_tx_set_state(sk, TFRC_SSTATE_TERM);
1359         sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer);
1360
1361         /* Empty packet history */
1362         dccp_tx_hist_purge(ccid3_tx_hist, &hctx->ccid3hctx_hist);
1363
1364         kfree(dp->dccps_hc_tx_ccid_private);
1365         dp->dccps_hc_tx_ccid_private = NULL;
1366 }
1367
1368 /*
1369  * RX Half Connection methods
1370  */
1371
1372 /* TFRC receiver states */
1373 enum ccid3_hc_rx_states {
1374         TFRC_RSTATE_NO_DATA = 1,
1375         TFRC_RSTATE_DATA,
1376         TFRC_RSTATE_TERM    = 127,
1377 };
1378
1379 #ifdef CCID3_DEBUG
1380 static const char *ccid3_rx_state_name(enum ccid3_hc_rx_states state)
1381 {
1382         static char *ccid3_rx_state_names[] = {
1383         [TFRC_RSTATE_NO_DATA] = "NO_DATA",
1384         [TFRC_RSTATE_DATA]    = "DATA",
1385         [TFRC_RSTATE_TERM]    = "TERM",
1386         };
1387
1388         return ccid3_rx_state_names[state];
1389 }
1390 #endif
1391
1392 static inline void ccid3_hc_rx_set_state(struct sock *sk, enum ccid3_hc_rx_states state)
1393 {
1394         struct dccp_sock *dp = dccp_sk(sk);
1395         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1396         enum ccid3_hc_rx_states oldstate = hcrx->ccid3hcrx_state;
1397
1398         ccid3_pr_debug("%s(%p) %-8.8s -> %s\n",
1399                        dccp_role(sk), sk, ccid3_rx_state_name(oldstate), ccid3_rx_state_name(state));
1400         WARN_ON(state == oldstate);
1401         hcrx->ccid3hcrx_state = state;
1402 }
1403
1404 static int ccid3_hc_rx_add_hist(struct sock *sk,
1405                                 struct dccp_rx_hist_entry *packet)
1406 {
1407         struct dccp_sock *dp = dccp_sk(sk);
1408         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1409         struct dccp_rx_hist_entry *entry, *next, *iter;
1410         u8 num_later = 0;
1411
1412         iter = dccp_rx_hist_head(&hcrx->ccid3hcrx_hist);
1413         if (iter == NULL)
1414                 dccp_rx_hist_add_entry(&hcrx->ccid3hcrx_hist, packet);
1415         else {
1416                 const u64 seqno = packet->dccphrx_seqno;
1417
1418                 if (after48(seqno, iter->dccphrx_seqno))
1419                         dccp_rx_hist_add_entry(&hcrx->ccid3hcrx_hist, packet);
1420                 else {
1421                         if (dccp_rx_hist_entry_data_packet(iter))
1422                                 num_later = 1;
1423
1424                         list_for_each_entry_continue(iter,
1425                                                      &hcrx->ccid3hcrx_hist,
1426                                                      dccphrx_node) {
1427                                 if (after48(seqno, iter->dccphrx_seqno)) {
1428                                         dccp_rx_hist_add_entry(&iter->dccphrx_node,
1429                                                                packet);
1430                                         goto trim_history;
1431                                 }
1432
1433                                 if (dccp_rx_hist_entry_data_packet(iter))
1434                                         num_later++;
1435
1436                                 if (num_later == TFRC_RECV_NUM_LATE_LOSS) {
1437                                         dccp_rx_hist_entry_delete(ccid3_rx_hist, packet);
1438                                         ccid3_pr_debug("%s, sk=%p, packet(%llu) already lost!\n",
1439                                                        dccp_role(sk), sk, seqno);
1440                                         return 1;
1441                                 }
1442                         }
1443
1444                         if (num_later < TFRC_RECV_NUM_LATE_LOSS)
1445                                 dccp_rx_hist_add_entry(&hcrx->ccid3hcrx_hist,
1446                                                        packet);
1447                         /* FIXME: else what? should we destroy the packet like above? */
1448                 }
1449         }
1450
1451 trim_history:
1452         /* Trim history (remove all packets after the NUM_LATE_LOSS + 1 data packets) */
1453         num_later = TFRC_RECV_NUM_LATE_LOSS + 1;
1454
1455         if (!list_empty(&hcrx->ccid3hcrx_loss_interval_hist)) {
1456                 list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
1457                                          dccphrx_node) {
1458                         if (num_later == 0) {
1459                                 list_del_init(&entry->dccphrx_node);
1460                                 dccp_rx_hist_entry_delete(ccid3_rx_hist, entry);
1461                         } else if (dccp_rx_hist_entry_data_packet(entry))
1462                                 --num_later;
1463                 }
1464         } else {
1465                 int step = 0;
1466                 u8 win_count = 0; /* Not needed, but lets shut up gcc */
1467                 int tmp;
1468                 /*
1469                  * We have no loss interval history so we need at least one
1470                  * rtt:s of data packets to approximate rtt.
1471                  */
1472                 list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
1473                                          dccphrx_node) {
1474                         if (num_later == 0) {
1475                                 switch (step) {
1476                                 case 0:
1477                                         step = 1;
1478                                         /* OK, find next data packet */
1479                                         num_later = 1;
1480                                         break;
1481                                 case 1:
1482                                         step = 2;
1483                                         /* OK, find next data packet */
1484                                         num_later = 1;
1485                                         win_count = entry->dccphrx_ccval;
1486                                         break;
1487                                 case 2:
1488                                         tmp = win_count - entry->dccphrx_ccval;
1489                                         if (tmp < 0)
1490                                                 tmp += TFRC_WIN_COUNT_LIMIT;
1491                                         if (tmp > TFRC_WIN_COUNT_PER_RTT + 1) {
1492                                                 /* we have found a packet older than one rtt
1493                                                  * remove the rest */
1494                                                 step = 3;
1495                                         } else /* OK, find next data packet */
1496                                                 num_later = 1;
1497                                         break;
1498                                 case 3:
1499                                         list_del_init(&entry->dccphrx_node);
1500                                         dccp_rx_hist_entry_delete(ccid3_rx_hist, entry);
1501                                         break;
1502                                 }
1503                         } else if (dccp_rx_hist_entry_data_packet(entry))
1504                                 --num_later;
1505                 }
1506         }
1507
1508         return 0;
1509 }
1510
1511 static void ccid3_hc_rx_send_feedback(struct sock *sk)
1512 {
1513         struct dccp_sock *dp = dccp_sk(sk);
1514         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1515         struct dccp_rx_hist_entry *packet;
1516
1517         ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
1518
1519         switch (hcrx->ccid3hcrx_state) {
1520         case TFRC_RSTATE_NO_DATA:
1521                 hcrx->ccid3hcrx_x_recv = 0;
1522                 break;
1523         case TFRC_RSTATE_DATA: {
1524                 u32 delta = now_delta(hcrx->ccid3hcrx_tstamp_last_feedback);
1525
1526                 if (delta == 0)
1527                         delta = 1; /* to prevent divide by zero */
1528                 hcrx->ccid3hcrx_x_recv = (hcrx->ccid3hcrx_bytes_recv *
1529                                           USEC_PER_SEC) / delta;
1530         }
1531                 break;
1532         default:
1533                 printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n",
1534                        __FUNCTION__, dccp_role(sk), sk, hcrx->ccid3hcrx_state);
1535                 dump_stack();
1536                 return;
1537         }
1538
1539         packet = dccp_rx_hist_find_data_packet(&hcrx->ccid3hcrx_hist);
1540         if (packet == NULL) {
1541                 printk(KERN_CRIT "%s: %s, sk=%p, no data packet in history!\n",
1542                        __FUNCTION__, dccp_role(sk), sk);
1543                 dump_stack();
1544                 return;
1545         }
1546
1547         do_gettimeofday(&(hcrx->ccid3hcrx_tstamp_last_feedback));
1548         hcrx->ccid3hcrx_last_counter         = packet->dccphrx_ccval;
1549         hcrx->ccid3hcrx_seqno_last_counter   = packet->dccphrx_seqno;
1550         hcrx->ccid3hcrx_bytes_recv           = 0;
1551
1552         /* Convert to multiples of 10us */
1553         hcrx->ccid3hcrx_elapsed_time = now_delta(packet->dccphrx_tstamp) / 10;
1554         if (hcrx->ccid3hcrx_p == 0)
1555                 hcrx->ccid3hcrx_pinv = ~0;
1556         else
1557                 hcrx->ccid3hcrx_pinv = 1000000 / hcrx->ccid3hcrx_p;
1558         dccp_send_ack(sk);
1559 }
1560
1561 static void ccid3_hc_rx_insert_options(struct sock *sk, struct sk_buff *skb)
1562 {
1563         const struct dccp_sock *dp = dccp_sk(sk);
1564         u32 x_recv, pinv;
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         DCCP_SKB_CB(skb)->dccpd_ccval = hcrx->ccid3hcrx_last_counter;
1571
1572         if (dccp_packet_without_ack(skb))
1573                 return;
1574
1575         if (hcrx->ccid3hcrx_elapsed_time != 0)
1576                 dccp_insert_option_elapsed_time(sk, skb,
1577                                                 hcrx->ccid3hcrx_elapsed_time);
1578         dccp_insert_option_timestamp(sk, skb);
1579         x_recv = htonl(hcrx->ccid3hcrx_x_recv);
1580         pinv   = htonl(hcrx->ccid3hcrx_pinv);
1581         dccp_insert_option(sk, skb, TFRC_OPT_LOSS_EVENT_RATE,
1582                            &pinv, sizeof(pinv));
1583         dccp_insert_option(sk, skb, TFRC_OPT_RECEIVE_RATE,
1584                            &x_recv, sizeof(x_recv));
1585 }
1586
1587 /* Weights used to calculate loss event rate */
1588 /*
1589  * These are integers as per section 8 of RFC3448. We can then divide by 4 *
1590  * when we use it.
1591  */
1592 static const int ccid3_hc_rx_w[TFRC_RECV_IVAL_F_LENGTH] = {
1593         4, 4, 4, 4, 3, 2, 1, 1,
1594 };
1595
1596 /*
1597  * args: fvalue - function value to match
1598  * returns:  p  closest to that value
1599  *
1600  * both fvalue and p are multiplied by 1,000,000 to use ints
1601  */
1602 static u32 calcx_reverse_lookup(u32 fvalue) {
1603         int ctr = 0;
1604         int small;
1605
1606         if (fvalue < calcx_lookup[0][1])
1607                 return 0;
1608         if (fvalue <= calcx_lookup[CALCX_ARRSIZE-1][1])
1609                 small = 1;
1610         else if (fvalue > calcx_lookup[CALCX_ARRSIZE-1][0])
1611                 return 1000000;
1612         else
1613                 small = 0;
1614         while (fvalue > calcx_lookup[ctr][small])
1615                 ctr++;
1616         if (small)
1617                 return (CALCX_SPLIT * ctr / CALCX_ARRSIZE);
1618         else
1619                 return (1000000 * ctr / CALCX_ARRSIZE) ;
1620 }
1621
1622 /* calculate first loss interval
1623  *
1624  * returns estimated loss interval in usecs */
1625
1626 static u32 ccid3_hc_rx_calc_first_li(struct sock *sk)
1627 {
1628         struct dccp_sock *dp = dccp_sk(sk);
1629         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1630         struct dccp_rx_hist_entry *entry, *next, *tail = NULL;
1631         u32 rtt, delta, x_recv, fval, p, tmp2;
1632         struct timeval tstamp = { 0 }, tmp_tv;
1633         int interval = 0;
1634         int win_count = 0;
1635         int step = 0;
1636         u64 tmp1;
1637
1638         list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
1639                                  dccphrx_node) {
1640                 if (dccp_rx_hist_entry_data_packet(entry)) {
1641                         tail = entry;
1642
1643                         switch (step) {
1644                         case 0:
1645                                 tstamp    = entry->dccphrx_tstamp;
1646                                 win_count = entry->dccphrx_ccval;
1647                                 step = 1;
1648                                 break;
1649                         case 1:
1650                                 interval = win_count - entry->dccphrx_ccval;
1651                                 if (interval < 0)
1652                                         interval += TFRC_WIN_COUNT_LIMIT;
1653                                 if (interval > 4)
1654                                         goto found;
1655                                 break;
1656                         }
1657                 }
1658         }
1659
1660         if (step == 0) {
1661                 printk(KERN_CRIT "%s: %s, sk=%p, packet history contains no data packets!\n",
1662                        __FUNCTION__, dccp_role(sk), sk);
1663                 return ~0;
1664         }
1665
1666         if (interval == 0) {
1667                 ccid3_pr_debug("%s, sk=%p, Could not find a win_count interval > 0. Defaulting to 1\n",
1668                                dccp_role(sk), sk);
1669                 interval = 1;
1670         }
1671 found:
1672         timeval_sub(tstamp,tail->dccphrx_tstamp,&tmp_tv);
1673         rtt = (tmp_tv.tv_sec * USEC_PER_SEC + tmp_tv.tv_usec) * 4 / interval;
1674         ccid3_pr_debug("%s, sk=%p, approximated RTT to %uus\n",
1675                        dccp_role(sk), sk, rtt);
1676         if (rtt == 0)
1677                 rtt = 1;
1678
1679         delta = now_delta(hcrx->ccid3hcrx_tstamp_last_feedback);
1680         if (delta == 0)
1681                 delta = 1;
1682
1683         x_recv = (hcrx->ccid3hcrx_bytes_recv * USEC_PER_SEC) / delta;
1684
1685         tmp1 = (u64)x_recv * (u64)rtt;
1686         do_div(tmp1,10000000);
1687         tmp2 = (u32)tmp1;
1688         fval = (hcrx->ccid3hcrx_s * 100000) / tmp2;
1689         /* do not alter order above or you will get overflow on 32 bit */
1690         p = calcx_reverse_lookup(fval);
1691         ccid3_pr_debug("%s, sk=%p, receive rate=%u bytes/s, implied loss rate=%u\n",\
1692                         dccp_role(sk), sk, x_recv, p);
1693
1694         if (p == 0)
1695                 return ~0;
1696         else
1697                 return 1000000 / p;
1698 }
1699
1700 static void ccid3_hc_rx_update_li(struct sock *sk, u64 seq_loss, u8 win_loss)
1701 {
1702         struct dccp_sock *dp = dccp_sk(sk);
1703         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1704         struct ccid3_loss_interval_hist_entry *li_entry;
1705
1706         if (seq_loss != DCCP_MAX_SEQNO + 1) {
1707                 ccid3_pr_debug("%s, sk=%p, seq_loss=%llu, win_loss=%u, packet loss detected\n",
1708                                dccp_role(sk), sk, seq_loss, win_loss);
1709
1710                 if (list_empty(&hcrx->ccid3hcrx_loss_interval_hist)) {
1711                         struct ccid3_loss_interval_hist_entry *li_tail = NULL;
1712                         int i;
1713
1714                         ccid3_pr_debug("%s, sk=%p, first loss event detected, creating history\n", dccp_role(sk), sk);
1715                         for (i = 0; i <= TFRC_RECV_IVAL_F_LENGTH; ++i) {
1716                                 li_entry = ccid3_loss_interval_hist_entry_new(SLAB_ATOMIC);
1717                                 if (li_entry == NULL) {
1718                                         ccid3_loss_interval_history_delete(&hcrx->ccid3hcrx_loss_interval_hist);
1719                                         ccid3_pr_debug("%s, sk=%p, not enough mem for creating history\n",
1720                                                        dccp_role(sk), sk);
1721                                         return;
1722                                 }
1723                                 if (li_tail == NULL)
1724                                         li_tail = li_entry;
1725                                 list_add(&li_entry->ccid3lih_node, &hcrx->ccid3hcrx_loss_interval_hist);
1726                         }
1727
1728                         li_entry->ccid3lih_seqno     = seq_loss;
1729                         li_entry->ccid3lih_win_count = win_loss;
1730
1731                         li_tail->ccid3lih_interval   = ccid3_hc_rx_calc_first_li(sk);
1732                 }
1733         }
1734         /* FIXME: find end of interval */
1735 }
1736
1737 static void ccid3_hc_rx_detect_loss(struct sock *sk)
1738 {
1739         struct dccp_sock *dp = dccp_sk(sk);
1740         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1741         struct dccp_rx_hist_entry *entry, *next, *packet;
1742         struct dccp_rx_hist_entry *a_loss = NULL;
1743         struct dccp_rx_hist_entry *b_loss = NULL;
1744         u64 seq_loss = DCCP_MAX_SEQNO + 1;
1745         u8 win_loss = 0;
1746         u8 num_later = TFRC_RECV_NUM_LATE_LOSS;
1747
1748         list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist,
1749                                  dccphrx_node) {
1750                 if (num_later == 0) {
1751                         b_loss = entry;
1752                         break;
1753                 } else if (dccp_rx_hist_entry_data_packet(entry))
1754                         --num_later;
1755         }
1756
1757         if (b_loss == NULL)
1758                 goto out_update_li;
1759
1760         num_later = 1;
1761
1762         list_for_each_entry_safe_continue(entry, next, &hcrx->ccid3hcrx_hist,
1763                                           dccphrx_node) {
1764                 if (num_later == 0) {
1765                         a_loss = entry;
1766                         break;
1767                 } else if (dccp_rx_hist_entry_data_packet(entry))
1768                         --num_later;
1769         }
1770
1771         if (a_loss == NULL) {
1772                 if (list_empty(&hcrx->ccid3hcrx_loss_interval_hist)) {
1773                         /* no loss event have occured yet */
1774                         ccid3_pr_debug("%s, sk=%p, TODO: find a lost data "
1775                                         "packet by comparing to initial seqno\n",
1776                                        dccp_role(sk), sk);
1777                         goto out_update_li;
1778                 } else {
1779                         pr_info("%s: %s, sk=%p, ERROR! Less than 4 data packets in history",
1780                                 __FUNCTION__, dccp_role(sk), sk);
1781                         return;
1782                 }
1783         }
1784
1785         /* Locate a lost data packet */
1786         entry = packet = b_loss;
1787         list_for_each_entry_safe_continue(entry, next, &hcrx->ccid3hcrx_hist,
1788                                           dccphrx_node) {
1789                 u64 delta = dccp_delta_seqno(entry->dccphrx_seqno,
1790                                              packet->dccphrx_seqno);
1791
1792                 if (delta != 0) {
1793                         if (dccp_rx_hist_entry_data_packet(packet))
1794                                 --delta;
1795                         /*
1796                          * FIXME: check this, probably this % usage is because
1797                          * in earlier drafts the ndp count was just 8 bits
1798                          * long, but now it cam be up to 24 bits long.
1799                          */
1800 #if 0
1801                         if (delta % DCCP_NDP_LIMIT !=
1802                             (packet->dccphrx_ndp -
1803                              entry->dccphrx_ndp) % DCCP_NDP_LIMIT)
1804 #endif
1805                         if (delta !=
1806                              packet->dccphrx_ndp - entry->dccphrx_ndp) {
1807                                 seq_loss = entry->dccphrx_seqno;
1808                                 dccp_inc_seqno(&seq_loss);
1809                         }
1810                 }
1811                 packet = entry;
1812                 if (packet == a_loss)
1813                         break;
1814         }
1815
1816         if (seq_loss != DCCP_MAX_SEQNO + 1)
1817                 win_loss = a_loss->dccphrx_ccval;
1818
1819 out_update_li:
1820         ccid3_hc_rx_update_li(sk, seq_loss, win_loss);
1821 }
1822
1823 static u32 ccid3_hc_rx_calc_i_mean(struct sock *sk)
1824 {
1825         struct dccp_sock *dp = dccp_sk(sk);
1826         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1827         struct ccid3_loss_interval_hist_entry *li_entry, *li_next;
1828         int i = 0;
1829         u32 i_tot;
1830         u32 i_tot0 = 0;
1831         u32 i_tot1 = 0;
1832         u32 w_tot  = 0;
1833
1834         list_for_each_entry_safe(li_entry, li_next, &hcrx->ccid3hcrx_loss_interval_hist, ccid3lih_node) {
1835                 if (i < TFRC_RECV_IVAL_F_LENGTH) {
1836                         i_tot0 += li_entry->ccid3lih_interval * ccid3_hc_rx_w[i];
1837                         w_tot  += ccid3_hc_rx_w[i];
1838                 }
1839
1840                 if (i != 0)
1841                         i_tot1 += li_entry->ccid3lih_interval * ccid3_hc_rx_w[i - 1];
1842
1843                 if (++i > TFRC_RECV_IVAL_F_LENGTH)
1844                         break;
1845         }
1846
1847         if (i != TFRC_RECV_IVAL_F_LENGTH) {
1848                 pr_info("%s: %s, sk=%p, ERROR! Missing entry in interval history!\n",
1849                         __FUNCTION__, dccp_role(sk), sk);
1850                 return 0;
1851         }
1852
1853         i_tot = max(i_tot0, i_tot1);
1854
1855         /* FIXME: Why do we do this? -Ian McDonald */
1856         if (i_tot * 4 < w_tot)
1857                 i_tot = w_tot * 4;
1858
1859         return i_tot * 4 / w_tot;
1860 }
1861
1862 static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
1863 {
1864         struct dccp_sock *dp = dccp_sk(sk);
1865         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
1866         const struct dccp_options_received *opt_recv;
1867         struct dccp_rx_hist_entry *packet;
1868         struct timeval now;
1869         u32 now_usecs;
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         opt_recv = &dp->dccps_options_received;
1885
1886         switch (DCCP_SKB_CB(skb)->dccpd_type) {
1887         case DCCP_PKT_ACK:
1888                 if (hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA)
1889                         return;
1890         case DCCP_PKT_DATAACK:
1891                 if (opt_recv->dccpor_timestamp_echo == 0)
1892                         break;
1893                 p_prev = hcrx->ccid3hcrx_rtt;
1894                 do_gettimeofday(&now);
1895                 now_usecs = now.tv_sec * USEC_PER_SEC + now.tv_usec;
1896                 hcrx->ccid3hcrx_rtt = now_usecs -
1897                                      (opt_recv->dccpor_timestamp_echo -
1898                                       opt_recv->dccpor_elapsed_time) * 10;
1899                 if (p_prev != hcrx->ccid3hcrx_rtt)
1900                         ccid3_pr_debug("%s, New RTT=%luus, elapsed time=%u\n",
1901                                        dccp_role(sk), hcrx->ccid3hcrx_rtt,
1902                                        opt_recv->dccpor_elapsed_time);
1903                 break;
1904         case DCCP_PKT_DATA:
1905                 break;
1906         default:
1907                 ccid3_pr_debug("%s, sk=%p, not DATA/DATAACK/ACK packet(%s)\n",
1908                                dccp_role(sk), sk,
1909                                dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type));
1910                 return;
1911         }
1912
1913         packet = dccp_rx_hist_entry_new(ccid3_rx_hist, opt_recv->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                         if (now_delta(hcrx->ccid3hcrx_tstamp_last_ack) >=
1939                             hcrx->ccid3hcrx_rtt) {
1940                                 do_gettimeofday(&hcrx->ccid3hcrx_tstamp_last_ack);
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), data loss! Reacting...\n",
1955                        dccp_role(sk), sk, dccp_state_name(sk->sk_state));
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          * XXX this seems to be paranoid, need to think more about this, for
1995          * now start with something different than zero. -acme
1996          */
1997         hcrx->ccid3hcrx_rtt = USEC_PER_SEC / 5;
1998         return 0;
1999 }
2000
2001 static void ccid3_hc_rx_exit(struct sock *sk)
2002 {
2003         struct dccp_sock *dp = dccp_sk(sk);
2004         struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
2005
2006         ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk);
2007
2008         if (hcrx == NULL)
2009                 return;
2010
2011         ccid3_hc_rx_set_state(sk, TFRC_RSTATE_TERM);
2012
2013         /* Empty packet history */
2014         dccp_rx_hist_purge(ccid3_rx_hist, &hcrx->ccid3hcrx_hist);
2015
2016         /* Empty loss interval history */
2017         ccid3_loss_interval_history_delete(&hcrx->ccid3hcrx_loss_interval_hist);
2018
2019         kfree(dp->dccps_hc_rx_ccid_private);
2020         dp->dccps_hc_rx_ccid_private = NULL;
2021 }
2022
2023 static void ccid3_hc_rx_get_info(struct sock *sk, struct tcp_info *info)
2024 {
2025         const struct dccp_sock *dp = dccp_sk(sk);
2026         const struct ccid3_hc_rx_sock *hcrx = dp->dccps_hc_rx_ccid_private;
2027
2028         if (hcrx == NULL)
2029                 return;
2030
2031         info->tcpi_ca_state     = hcrx->ccid3hcrx_state;
2032         info->tcpi_options      |= TCPI_OPT_TIMESTAMPS;
2033         info->tcpi_rcv_rtt      = hcrx->ccid3hcrx_rtt;
2034 }
2035
2036 static void ccid3_hc_tx_get_info(struct sock *sk, struct tcp_info *info)
2037 {
2038         const struct dccp_sock *dp = dccp_sk(sk);
2039         const struct ccid3_hc_tx_sock *hctx = dp->dccps_hc_tx_ccid_private;
2040
2041         if (hctx == NULL)
2042                 return;
2043
2044         info->tcpi_rto = hctx->ccid3hctx_t_rto;
2045         info->tcpi_rtt = hctx->ccid3hctx_rtt;
2046 }
2047
2048 static struct ccid ccid3 = {
2049         .ccid_id                   = 3,
2050         .ccid_name                 = "ccid3",
2051         .ccid_owner                = THIS_MODULE,
2052         .ccid_init                 = ccid3_init,
2053         .ccid_exit                 = ccid3_exit,
2054         .ccid_hc_tx_init           = ccid3_hc_tx_init,
2055         .ccid_hc_tx_exit           = ccid3_hc_tx_exit,
2056         .ccid_hc_tx_send_packet    = ccid3_hc_tx_send_packet,
2057         .ccid_hc_tx_packet_sent    = ccid3_hc_tx_packet_sent,
2058         .ccid_hc_tx_packet_recv    = ccid3_hc_tx_packet_recv,
2059         .ccid_hc_tx_insert_options = ccid3_hc_tx_insert_options,
2060         .ccid_hc_tx_parse_options  = ccid3_hc_tx_parse_options,
2061         .ccid_hc_rx_init           = ccid3_hc_rx_init,
2062         .ccid_hc_rx_exit           = ccid3_hc_rx_exit,
2063         .ccid_hc_rx_insert_options = ccid3_hc_rx_insert_options,
2064         .ccid_hc_rx_packet_recv    = ccid3_hc_rx_packet_recv,
2065         .ccid_hc_rx_get_info       = ccid3_hc_rx_get_info,
2066         .ccid_hc_tx_get_info       = ccid3_hc_tx_get_info,
2067 };
2068
2069 module_param(ccid3_debug, int, 0444);
2070 MODULE_PARM_DESC(ccid3_debug, "Enable debug messages");
2071
2072 static __init int ccid3_module_init(void)
2073 {
2074         int rc = -ENOBUFS;
2075
2076         ccid3_rx_hist = dccp_rx_hist_new("ccid3");
2077         if (ccid3_rx_hist == NULL)
2078                 goto out;
2079
2080         ccid3_tx_hist = dccp_tx_hist_new("ccid3");
2081         if (ccid3_tx_hist == NULL)
2082                 goto out_free_rx;
2083
2084         ccid3_loss_interval_hist_slab = kmem_cache_create("li_hist_ccid3",
2085                                   sizeof(struct ccid3_loss_interval_hist_entry),
2086                                                           0, SLAB_HWCACHE_ALIGN,
2087                                                           NULL, NULL);
2088         if (ccid3_loss_interval_hist_slab == NULL)
2089                 goto out_free_tx;
2090
2091         rc = ccid_register(&ccid3);
2092         if (rc != 0)
2093                 goto out_free_loss_interval_history;
2094 out:
2095         return rc;
2096
2097 out_free_loss_interval_history:
2098         kmem_cache_destroy(ccid3_loss_interval_hist_slab);
2099         ccid3_loss_interval_hist_slab = NULL;
2100 out_free_tx:
2101         dccp_tx_hist_delete(ccid3_tx_hist);
2102         ccid3_tx_hist = NULL;
2103 out_free_rx:
2104         dccp_rx_hist_delete(ccid3_rx_hist);
2105         ccid3_rx_hist = NULL;
2106         goto out;
2107 }
2108 module_init(ccid3_module_init);
2109
2110 static __exit void ccid3_module_exit(void)
2111 {
2112 #ifdef CONFIG_IP_DCCP_UNLOAD_HACK
2113         /*
2114          * Hack to use while developing, so that we get rid of the control
2115          * sock, that is what keeps a refcount on dccp.ko -acme
2116          */
2117         extern void dccp_ctl_sock_exit(void);
2118
2119         dccp_ctl_sock_exit();
2120 #endif
2121         ccid_unregister(&ccid3);
2122
2123         if (ccid3_tx_hist != NULL) {
2124                 dccp_tx_hist_delete(ccid3_tx_hist);
2125                 ccid3_tx_hist = NULL;
2126         }
2127         if (ccid3_rx_hist != NULL) {
2128                 dccp_rx_hist_delete(ccid3_rx_hist);
2129                 ccid3_rx_hist = NULL;
2130         }
2131         if (ccid3_loss_interval_hist_slab != NULL) {
2132                 kmem_cache_destroy(ccid3_loss_interval_hist_slab);
2133                 ccid3_loss_interval_hist_slab = NULL;
2134         }
2135 }
2136 module_exit(ccid3_module_exit);
2137
2138 MODULE_AUTHOR("Ian McDonald <iam4@cs.waikato.ac.nz> & Arnaldo Carvalho de Melo <acme@ghostprotocols.net>");
2139 MODULE_DESCRIPTION("DCCP TFRC CCID3 CCID");
2140 MODULE_LICENSE("GPL");
2141 MODULE_ALIAS("net-dccp-ccid-3");