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 */ 91 static 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] */ 595 static 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 */ 617 u32 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 */ 666 u32 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 */ 698 u32 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