Merge master.kernel.org:/pub/scm/linux/kernel/git/davej/agpgart
[linux-2.6] / net / dccp / ccids / lib / tfrc_equation.c
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);