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