LXR linux/net/dccp/ccids/lib/tfrc

   1/*
   2 *  Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand.
   3 *  Copyright (c) 2005 Ian McDonald <ian.mcdonald@jandi.co.nz>
   4 *  Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
   5 *  Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
   6 *
   7 *  This program is free software; you can redistribute it and/or modify
   8 *  it under the terms of the GNU General Public License as published by
   9 *  the Free Software Foundation; either version 2 of the License, or
  10 *  (at your option) any later version.
  11 */
  12
  13#include <linux/module.h>
  14#include "../../dccp.h"
  15#include "tfrc.h"
  16
  17#define TFRC_CALC_X_ARRSIZE 500
  18#define TFRC_CALC_X_SPLIT   50000       /* 0.05 * 1000000, details below */
  19#define TFRC_SMALLEST_P     (TFRC_CALC_X_SPLIT/TFRC_CALC_X_ARRSIZE)
  20
  21/*
  22  TFRC TCP Reno Throughput Equation Lookup Table for f(p)
  23
  24  The following two-column lookup table implements a part of the TCP throughput
  25  equation from [RFC 3448, sec. 3.1]:
  26
  27                                     s
  28  X_calc  =  --------------------------------------------------------------
  29             R * sqrt(2*b*p/3) + (3 * t_RTO * sqrt(3*b*p/8) * (p + 32*p^3))
  30
  31  Where:
  32        X      is the transmit rate in bytes/second
  33        s      is the packet size in bytes
  34        R      is the round trip time in seconds
  35        p      is the loss event rate, between 0 and 1.0, of the number of loss
  36                      events as a fraction of the number of packets transmitted
  37        t_RTO  is the TCP retransmission timeout value in seconds
  38        b      is the number of packets acknowledged by a single TCP ACK
  39
  40  We can assume that b = 1 and t_RTO is 4 * R. The equation now becomes:
  41
  42                                     s
  43  X_calc  =  -------------------------------------------------------
  44             R * sqrt(p*2/3) + (12 * R * sqrt(p*3/8) * (p + 32*p^3))
  45
  46  which we can break down into:
  47
  48                      s
  49        X_calc  =  ---------
  50                    R * f(p)
  51
  52  where f(p) is given for 0 < p <= 1 by:
  53
  54        f(p)  =  sqrt(2*p/3) + 12 * sqrt(3*p/8) *  (p + 32*p^3)
  55
  56  Since this is kernel code, floating-point arithmetic is avoided in favour of
  57  integer arithmetic. This means that nearly all fractional parameters are
  58  scaled by 1000000:
  59    * the parameters p and R
  60    * the return result f(p)
  61  The lookup table therefore actually tabulates the following function g(q):
  62
  63        g(q)  =  1000000 * f(q/1000000)
  64
  65  Hence, when p <= 1, q must be less than or equal to 1000000. To achieve finer
  66  granularity for the practically more relevant case of small values of p (up to
  67  5%), the second column is used; the first one ranges up to 100%.  This split
  68  corresponds to the value of q = TFRC_CALC_X_SPLIT. At the same time this also
  69  determines the smallest resolution possible with this lookup table:
  70
  71    TFRC_SMALLEST_P   =  TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE
  72
  73  The entire table is generated by:
  74    for(i=0; i < TFRC_CALC_X_ARRSIZE; i++) {
  75        lookup[i][0]  =  g((i+1) * 1000000/TFRC_CALC_X_ARRSIZE);
  76        lookup[i][1]  =  g((i+1) * TFRC_CALC_X_SPLIT/TFRC_CALC_X_ARRSIZE);
  77    }
  78
  79  With the given configuration, we have, with M = TFRC_CALC_X_ARRSIZE-1,
  80    lookup[0][0]  =  g(1000000/(M+1))           = 1000000 * f(0.2%)
  81    lookup[M][0]  =  g(1000000)                 = 1000000 * f(100%)
  82    lookup[0][1]  =  g(TFRC_SMALLEST_P)         = 1000000 * f(0.01%)
  83    lookup[M][1]  =  g(TFRC_CALC_X_SPLIT)       = 1000000 * f(5%)
  84
  85  In summary, the two columns represent f(p) for the following ranges:
  86    * The first column is for   0.002  <= p <= 1.0
  87    * The second column is for  0.0001 <= p <= 0.05
  88  Where the columns overlap, the second (finer-grained) is given preference,
  89  i.e. the first column is used only for p >= 0.05.
  90 */
  91static const u32 tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE][2] = {
  92        {     37172,   8172 },
  93        {     53499,  11567 },
  94        {     66664,  14180 },
  95        {     78298,  16388 },
  96        {     89021,  18339 },
  97        {     99147,  20108 },
  98        {    108858,  21738 },
  99        {    118273,  23260 },
 100        {    127474,  24693 },
 101        {    136520,  26052 },
 102        {    145456,  27348 },
 103        {    154316,  28589 },
 104        {    163130,  29783 },
 105        {    171919,  30935 },
 106        {    180704,  32049 },
 107        {    189502,  33130 },
 108        {    198328,  34180 },
 109        {    207194,  35202 },
 110        {    216114,  36198 },
 111        {    225097,  37172 },
 112        {    234153,  38123 },
 113        {    243294,  39055 },
 114        {    252527,  39968 },
 115        {    261861,  40864 },
 116        {    271305,  41743 },
 117        {    280866,  42607 },
 118        {    290553,  43457 },
 119        {    300372,  44293 },
 120        {    310333,  45117 },
 121        {    320441,  45929 },
 122        {    330705,  46729 },
 123        {    341131,  47518 },
 124        {    351728,  48297 },
 125        {    362501,  49066 },
 126        {    373460,  49826 },
 127        {    384609,  50577 },
 128        {    395958,  51320 },
 129        {    407513,  52054 },
 130        {    419281,  52780 },
 131        {    431270,  53499 },
 132        {    443487,  54211 },
 133        {    455940,  54916 },
 134        {    468635,  55614 },
 135        {    481581,  56306 },
 136        {    494785,  56991 },
 137        {    508254,  57671 },
 138        {    521996,  58345 },
 139        {    536019,  59014 },
 140        {    550331,  59677 },
 141        {    564939,  60335 },
 142        {    579851,  60988 },
 143        {    595075,  61636 },
 144        {    610619,  62279 },
 145        {    626491,  62918 },
 146        {    642700,  63553 },
 147        {    659253,  64183 },
 148        {    676158,  64809 },
 149        {    693424,  65431 },
 150        {    711060,  66050 },
 151        {    729073,  66664 },
 152        {    747472,  67275 },
 153        {    766266,  67882 },
 154        {    785464,  68486 },
 155        {    805073,  69087 },
 156        {    825103,  69684 },
 157        {    845562,  70278 },
 158        {    866460,  70868 },
 159        {    887805,  71456 },
 160        {    909606,  72041 },
 161        {    931873,  72623 },
 162        {    954614,  73202 },
 163        {    977839,  73778 },
 164        {   1001557,  74352 },
 165        {   1025777,  74923 },
 166        {   1050508,  75492 },
 167        {   1075761,  76058 },
 168        {   1101544,  76621 },
 169        {   1127867,  77183 },
 170        {   1154739,  77741 },
 171        {   1182172,  78298 },
 172        {   1210173,  78852 },
 173        {   1238753,  79405 },
 174        {   1267922,  79955 },
 175        {   1297689,  80503 },
 176        {   1328066,  81049 },
 177        {   1359060,  81593 },
 178        {   1390684,  82135 },
 179        {   1422947,  82675 },
 180        {   1455859,  83213 },
 181        {   1489430,  83750 },
 182        {   1523671,  84284 },
 183        {   1558593,  84817 },
 184        {   1594205,  85348 },
 185        {   1630518,  85878 },
 186        {   1667543,  86406 },
 187        {   1705290,  86932 },
 188        {   1743770,  87457 },
 189        {   1782994,  87980 },
 190        {   1822973,  88501 },
 191        {   1863717,  89021 },
 192        {   1905237,  89540 },
 193        {   1947545,  90057 },
 194        {   1990650,  90573 },
 195        {   2034566,  91087 },
 196        {   2079301,  91600 },
 197        {   2124869,  92111 },
 198        {   2171279,  92622 },
 199        {   2218543,  93131 },
 200        {   2266673,  93639 },
 201        {   2315680,  94145 },
 202        {   2365575,  94650 },
 203        {   2416371,  95154 },
 204        {   2468077,  95657 },
 205        {   2520707,  96159 },
 206        {   2574271,  96660 },
 207        {   2628782,  97159 },
 208        {   2684250,  97658 },
 209        {   2740689,  98155 },
 210        {   2798110,  98651 },
 211        {   2856524,  99147 },
 212        {   2915944,  99641 },
 213        {   2976382, 100134 },
 214        {   3037850, 100626 },
 215        {   3100360, 101117 },
 216        {   3163924, 101608 },
 217        {   3228554, 102097 },
 218        {   3294263, 102586 },
 219        {   3361063, 103073 },
 220        {   3428966, 103560 },
 221        {   3497984, 104045 },
 222        {   3568131, 104530 },
 223        {   3639419, 105014 },
 224        {   3711860, 105498 },
 225        {   3785467, 105980 },
 226        {   3860253, 106462 },
 227        {   3936229, 106942 },
 228        {   4013410, 107422 },
 229        {   4091808, 107902 },
 230        {   4171435, 108380 },
 231        {   4252306, 108858 },
 232        {   4334431, 109335 },
 233        {   4417825, 109811 },
 234        {   4502501, 110287 },
 235        {   4588472, 110762 },
 236        {   4675750, 111236 },
 237        {   4764349, 111709 },
 238        {   4854283, 112182 },
 239        {   4945564, 112654 },
 240        {   5038206, 113126 },
 241        {   5132223, 113597 },
 242        {   5227627, 114067 },
 243        {   5324432, 114537 },
 244        {   5422652, 115006 },
 245        {   5522299, 115474 },
 246        {   5623389, 115942 },
 247        {   5725934, 116409 },
 248        {   5829948, 116876 },
 249        {   5935446, 117342 },
 250        {   6042439, 117808 },
 251        {   6150943, 118273 },
 252        {   6260972, 118738 },
 253        {   6372538, 119202 },
 254        {   6485657, 119665 },
 255        {   6600342, 120128 },
 256        {   6716607, 120591 },
 257        {   6834467, 121053 },
 258        {   6953935, 121514 },
 259        {   7075025, 121976 },
 260        {   7197752, 122436 },
 261        {   7322131, 122896 },
 262        {   7448175, 123356 },
 263        {   7575898, 123815 },
 264        {   7705316, 124274 },
 265        {   7836442, 124733 },
 266        {   7969291, 125191 },
 267        {   8103877, 125648 },
 268        {   8240216, 126105 },
 269        {   8378321, 126562 },
 270        {   8518208, 127018 },
 271        {   8659890, 127474 },
 272        {   8803384, 127930 },
 273        {   8948702, 128385 },
 274        {   9095861, 128840 },
 275        {   9244875, 129294 },
 276        {   9395760, 129748 },
 277        {   9548529, 130202 },
 278        {   9703198, 130655 },
 279        {   9859782, 131108 },
 280        {  10018296, 131561 },
 281        {  10178755, 132014 },
 282        {  10341174, 132466 },
 283        {  10505569, 132917 },
 284        {  10671954, 133369 },
 285        {  10840345, 133820 },
 286        {  11010757, 134271 },
 287        {  11183206, 134721 },
 288        {  11357706, 135171 },
 289        {  11534274, 135621 },
 290        {  11712924, 136071 },
 291        {  11893673, 136520 },
 292        {  12076536, 136969 },
 293        {  12261527, 137418 },
 294        {  12448664, 137867 },
 295        {  12637961, 138315 },
 296        {  12829435, 138763 },
 297        {  13023101, 139211 },
 298        {  13218974, 139658 },
 299        {  13417071, 140106 },
 300        {  13617407, 140553 },
 301        {  13819999, 140999 },
 302        {  14024862, 141446 },
 303        {  14232012, 141892 },
 304        {  14441465, 142339 },
 305        {  14653238, 142785 },
 306        {  14867346, 143230 },
 307        {  15083805, 143676 },
 308        {  15302632, 144121 },
 309        {  15523842, 144566 },
 310        {  15747453, 145011 },
 311        {  15973479, 145456 },
 312        {  16201939, 145900 },
 313        {  16432847, 146345 },
 314        {  16666221, 146789 },
 315        {  16902076, 147233 },
 316        {  17140429, 147677 },
 317        {  17381297, 148121 },
 318        {  17624696, 148564 },
 319        {  17870643, 149007 },
 320        {  18119154, 149451 },
 321        {  18370247, 149894 },
 322        {  18623936, 150336 },
 323        {  18880241, 150779 },
 324        {  19139176, 151222 },
 325        {  19400759, 151664 },
 326        {  19665007, 152107 },
 327        {  19931936, 152549 },
 328        {  20201564, 152991 },
 329        {  20473907, 153433 },
 330        {  20748982, 153875 },
 331        {  21026807, 154316 },
 332        {  21307399, 154758 },
 333        {  21590773, 155199 },
 334        {  21876949, 155641 },
 335        {  22165941, 156082 },
 336        {  22457769, 156523 },
 337        {  22752449, 156964 },
 338        {  23049999, 157405 },
 339        {  23350435, 157846 },
 340        {  23653774, 158287 },
 341        {  23960036, 158727 },
 342        {  24269236, 159168 },
 343        {  24581392, 159608 },
 344        {  24896521, 160049 },
 345        {  25214642, 160489 },
 346        {  25535772, 160929 },
 347        {  25859927, 161370 },
 348        {  26187127, 161810 },
 349        {  26517388, 162250 },
 350        {  26850728, 162690 },
 351        {  27187165, 163130 },
 352        {  27526716, 163569 },
 353        {  27869400, 164009 },
 354        {  28215234, 164449 },
 355        {  28564236, 164889 },
 356        {  28916423, 165328 },
 357        {  29271815, 165768 },
 358        {  29630428, 166208 },
 359        {  29992281, 166647 },
 360        {  30357392, 167087 },
 361        {  30725779, 167526 },
 362        {  31097459, 167965 },
 363        {  31472452, 168405 },
 364        {  31850774, 168844 },
 365        {  32232445, 169283 },
 366        {  32617482, 169723 },
 367        {  33005904, 170162 },
 368        {  33397730, 170601 },
 369        {  33792976, 171041 },
 370        {  34191663, 171480 },
 371        {  34593807, 171919 },
 372        {  34999428, 172358 },
 373        {  35408544, 172797 },
 374        {  35821174, 173237 },
 375        {  36237335, 173676 },
 376        {  36657047, 174115 },
 377        {  37080329, 174554 },
 378        {  37507197, 174993 },
 379        {  37937673, 175433 },
 380        {  38371773, 175872 },
 381        {  38809517, 176311 },
 382        {  39250924, 176750 },
 383        {  39696012, 177190 },
 384        {  40144800, 177629 },
 385        {  40597308, 178068 },
 386        {  41053553, 178507 },
 387        {  41513554, 178947 },
 388        {  41977332, 179386 },
 389        {  42444904, 179825 },
 390        {  42916290, 180265 },
 391        {  43391509, 180704 },
 392        {  43870579, 181144 },
 393        {  44353520, 181583 },
 394        {  44840352, 182023 },
 395        {  45331092, 182462 },
 396        {  45825761, 182902 },
 397        {  46324378, 183342 },
 398        {  46826961, 183781 },
 399        {  47333531, 184221 },
 400        {  47844106, 184661 },
 401        {  48358706, 185101 },
 402        {  48877350, 185541 },
 403        {  49400058, 185981 },
 404        {  49926849, 186421 },
 405        {  50457743, 186861 },
 406        {  50992759, 187301 },
 407        {  51531916, 187741 },
 408        {  52075235, 188181 },
 409        {  52622735, 188622 },
 410        {  53174435, 189062 },
 411        {  53730355, 189502 },
 412        {  54290515, 189943 },
 413        {  54854935, 190383 },
 414        {  55423634, 190824 },
 415        {  55996633, 191265 },
 416        {  56573950, 191706 },
 417        {  57155606, 192146 },
 418        {  57741621, 192587 },
 419        {  58332014, 193028 },
 420        {  58926806, 193470 },
 421        {  59526017, 193911 },
 422        {  60129666, 194352 },
 423        {  60737774, 194793 },
 424        {  61350361, 195235 },
 425        {  61967446, 195677 },
 426        {  62589050, 196118 },
 427        {  63215194, 196560 },
 428        {  63845897, 197002 },
 429        {  64481179, 197444 },
 430        {  65121061, 197886 },
 431        {  65765563, 198328 },
 432        {  66414705, 198770 },
 433        {  67068508, 199213 },
 434        {  67726992, 199655 },
 435        {  68390177, 200098 },
 436        {  69058085, 200540 },
 437        {  69730735, 200983 },
 438        {  70408147, 201426 },
 439        {  71090343, 201869 },
 440        {  71777343, 202312 },
 441        {  72469168, 202755 },
 442        {  73165837, 203199 },
 443        {  73867373, 203642 },
 444        {  74573795, 204086 },
 445        {  75285124, 204529 },
 446        {  76001380, 204973 },
 447        {  76722586, 205417 },
 448        {  77448761, 205861 },
 449        {  78179926, 206306 },
 450        {  78916102, 206750 },
 451        {  79657310, 207194 },
 452        {  80403571, 207639 },
 453        {  81154906, 208084 },
 454        {  81911335, 208529 },
 455        {  82672880, 208974 },
 456        {  83439562, 209419 },
 457        {  84211402, 209864 },
 458        {  84988421, 210309 },
 459        {  85770640, 210755 },
 460        {  86558080, 211201 },
 461        {  87350762, 211647 },
 462        {  88148708, 212093 },
 463        {  88951938, 212539 },
 464        {  89760475, 212985 },
 465        {  90574339, 213432 },
 466        {  91393551, 213878 },
 467        {  92218133, 214325 },
 468        {  93048107, 214772 },
 469        {  93883493, 215219 },
 470        {  94724314, 215666 },
 471        {  95570590, 216114 },
 472        {  96422343, 216561 },
 473        {  97279594, 217009 },
 474        {  98142366, 217457 },
 475        {  99010679, 217905 },
 476        {  99884556, 218353 },
 477        { 100764018, 218801 },
 478        { 101649086, 219250 },
 479        { 102539782, 219698 },
 480        { 103436128, 220147 },
 481        { 104338146, 220596 },
 482        { 105245857, 221046 },
 483        { 106159284, 221495 },
 484        { 107078448, 221945 },
 485        { 108003370, 222394 },
 486        { 108934074, 222844 },
 487        { 109870580, 223294 },
 488        { 110812910, 223745 },
 489        { 111761087, 224195 },
 490        { 112715133, 224646 },
 491        { 113675069, 225097 },
 492        { 114640918, 225548 },
 493        { 115612702, 225999 },
 494        { 116590442, 226450 },
 495        { 117574162, 226902 },
 496        { 118563882, 227353 },
 497        { 119559626, 227805 },
 498        { 120561415, 228258 },
 499        { 121569272, 228710 },
 500        { 122583219, 229162 },
 501        { 123603278, 229615 },
 502        { 124629471, 230068 },
 503        { 125661822, 230521 },
 504        { 126700352, 230974 },
 505        { 127745083, 231428 },
 506        { 128796039, 231882 },
 507        { 129853241, 232336 },
 508        { 130916713, 232790 },
 509        { 131986475, 233244 },
 510        { 133062553, 233699 },
 511        { 134144966, 234153 },
 512        { 135233739, 234608 },
 513        { 136328894, 235064 },
 514        { 137430453, 235519 },
 515        { 138538440, 235975 },
 516        { 139652876, 236430 },
 517        { 140773786, 236886 },
 518        { 141901190, 237343 },
 519        { 143035113, 237799 },
 520        { 144175576, 238256 },
 521        { 145322604, 238713 },
 522        { 146476218, 239170 },
 523        { 147636442, 239627 },
 524        { 148803298, 240085 },
 525        { 149976809, 240542 },
 526        { 151156999, 241000 },
 527        { 152343890, 241459 },
 528        { 153537506, 241917 },
 529        { 154737869, 242376 },
 530        { 155945002, 242835 },
 531        { 157158929, 243294 },
 532        { 158379673, 243753 },
 533        { 159607257, 244213 },
 534        { 160841704, 244673 },
 535        { 162083037, 245133 },
 536        { 163331279, 245593 },
 537        { 164586455, 246054 },
 538        { 165848586, 246514 },
 539        { 167117696, 246975 },
 540        { 168393810, 247437 },
 541        { 169676949, 247898 },
 542        { 170967138, 248360 },
 543        { 172264399, 248822 },
 544        { 173568757, 249284 },
 545        { 174880235, 249747 },
 546        { 176198856, 250209 },
 547        { 177524643, 250672 },
 548        { 178857621, 251136 },
 549        { 180197813, 251599 },
 550        { 181545242, 252063 },
 551        { 182899933, 252527 },
 552        { 184261908, 252991 },
 553        { 185631191, 253456 },
 554        { 187007807, 253920 },
 555        { 188391778, 254385 },
 556        { 189783129, 254851 },
 557        { 191181884, 255316 },
 558        { 192588065, 255782 },
 559        { 194001698, 256248 },
 560        { 195422805, 256714 },
 561        { 196851411, 257181 },
 562        { 198287540, 257648 },
 563        { 199731215, 258115 },
 564        { 201182461, 258582 },
 565        { 202641302, 259050 },
 566        { 204107760, 259518 },
 567        { 205581862, 259986 },
 568        { 207063630, 260454 },
 569        { 208553088, 260923 },
 570        { 210050262, 261392 },
 571        { 211555174, 261861 },
 572        { 213067849, 262331 },
 573        { 214588312, 262800 },
 574        { 216116586, 263270 },
 575        { 217652696, 263741 },
 576        { 219196666, 264211 },
 577        { 220748520, 264682 },
 578        { 222308282, 265153 },
 579        { 223875978, 265625 },
 580        { 225451630, 266097 },
 581        { 227035265, 266569 },
 582        { 228626905, 267041 },
 583        { 230226576, 267514 },
 584        { 231834302, 267986 },
 585        { 233450107, 268460 },
 586        { 235074016, 268933 },
 587        { 236706054, 269407 },
 588        { 238346244, 269881 },
 589        { 239994613, 270355 },
 590        { 241651183, 270830 },
 591        { 243315981, 271305 }
 592};
 593
 594/* return largest index i such that fval <= lookup[i][small] */
 595static inline u32 tfrc_binsearch(u32 fval, u8 small)
 596{
 597        u32 try, low = 0, high = TFRC_CALC_X_ARRSIZE - 1;
 598
 599        while (low < high) {
 600                try = (low + high) / 2;
 601                if (fval <= tfrc_calc_x_lookup[try][small])
 602                        high = try;
 603                else
 604                        low  = try + 1;
 605        }
 606        return high;
 607}
 608
 609/**
 610 * tfrc_calc_x - Calculate the send rate as per section 3.1 of RFC3448
 611 * @s: packet size          in bytes
 612 * @R: RTT                  scaled by 1000000   (i.e., microseconds)
 613 * @p: loss ratio estimate  scaled by 1000000
 614 *
 615 * Returns X_calc           in bytes per second (not scaled).
 616 */
 617u32 tfrc_calc_x(u16 s, u32 R, u32 p)
 618{
 619        u16 index;
 620        u32 f;
 621        u64 result;
 622
 623        /* check against invalid parameters and divide-by-zero   */
 624        BUG_ON(p >  1000000);           /* p must not exceed 100%   */
 625        BUG_ON(p == 0);                 /* f(0) = 0, divide by zero */
 626        if (R == 0) {                   /* possible  divide by zero */
 627                DCCP_CRIT("WARNING: RTT is 0, returning maximum X_calc.");
 628                return ~0U;
 629        }
 630
 631        if (p <= TFRC_CALC_X_SPLIT)             {     /* 0.0000 < p <= 0.05   */
 632                if (p < TFRC_SMALLEST_P) {            /* 0.0000 < p <  0.0001 */
 633                        DCCP_WARN("Value of p (%d) below resolution. "
 634                                  "Substituting %d\n", p, TFRC_SMALLEST_P);
 635                        index = 0;
 636                } else                                /* 0.0001 <= p <= 0.05  */
 637                        index =  p/TFRC_SMALLEST_P - 1;
 638
 639                f = tfrc_calc_x_lookup[index][1];
 640
 641        } else {                                      /* 0.05   <  p <= 1.00  */
 642                index = p/(1000000/TFRC_CALC_X_ARRSIZE) - 1;
 643
 644                f = tfrc_calc_x_lookup[index][0];
 645        }
 646
 647        /*
 648         * Compute X = s/(R*f(p)) in bytes per second.
 649         * Since f(p) and R are both scaled by 1000000, we need to multiply by
 650         * 1000000^2. To avoid overflow, the result is computed in two stages.
 651         * This works under almost all reasonable operational conditions, for a
 652         * wide range of parameters. Yet, should some strange combination of
 653         * parameters result in overflow, the use of scaled_div32 will catch
 654         * this and return UINT_MAX - which is a logically adequate consequence.
 655         */
 656        result = scaled_div(s, R);
 657        return scaled_div32(result, f);
 658}
 659
 660/**
 661 *  tfrc_calc_x_reverse_lookup  -  try to find p given f(p)
 662 *  @fvalue: function value to match, scaled by 1000000
 663 *
 664 *  Returns closest match for p, also scaled by 1000000
 665 */
 666u32 tfrc_calc_x_reverse_lookup(u32 fvalue)
 667{
 668        int index;
 669
 670        if (fvalue == 0)        /* f(p) = 0  whenever  p = 0 */
 671                return 0;
 672
 673        /* Error cases. */
 674        if (fvalue < tfrc_calc_x_lookup[0][1]) {
 675                DCCP_WARN("fvalue %u smaller than resolution\n", fvalue);
 676                return TFRC_SMALLEST_P;
 677        }
 678        if (fvalue > tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][0]) {
 679                DCCP_WARN("fvalue %u exceeds bounds!\n", fvalue);
 680                return 1000000;
 681        }
 682
 683        if (fvalue <= tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][1]) {
 684                index = tfrc_binsearch(fvalue, 1);
 685                return (index + 1) * TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE;
 686        }
 687
 688        /* else ... it must be in the coarse-grained column */
 689        index = tfrc_binsearch(fvalue, 0);
 690        return (index + 1) * 1000000 / TFRC_CALC_X_ARRSIZE;
 691}
 692
 693/**
 694 * tfrc_invert_loss_event_rate  -  Compute p so that 10^6 corresponds to 100%
 695 * When @loss_event_rate is large, there is a chance that p is truncated to 0.
 696 * To avoid re-entering slow-start in that case, we set p = TFRC_SMALLEST_P > 0.
 697 */
 698u32 tfrc_invert_loss_event_rate(u32 loss_event_rate)
 699{
 700        if (loss_event_rate == UINT_MAX)                /* see RFC 4342, 8.5 */
 701                return 0;
 702        if (unlikely(loss_event_rate == 0))             /* map 1/0 into 100% */
 703                return 1000000;
 704        return max_t(u32, scaled_div(1, loss_event_rate), TFRC_SMALLEST_P);
 705}
 706