net/dccp/ccids/ccid3.c

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