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