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