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