net/dccp/ccids/ccid3.c

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