aboutsummaryrefslogtreecommitdiffstats
path: root/net
diff options
context:
space:
mode:
authorGerrit Renker <gerrit@erg.abdn.ac.uk>2006-12-09 21:04:16 -0500
committerDavid S. Miller <davem@sunset.davemloft.net>2006-12-11 17:34:46 -0500
commitd63d8364cfe17fc9bb738f554f452595f76f21d2 (patch)
tree32bd2371deb9ddc8a7c7bd835f33c2290cc0e8bf /net
parent0f9e5b573f7249b0e04a03457b55081d1f60f2bf (diff)
[DCCP]: Simplify TFRC calculation
In migrating towards using the newer functions scaled_div/scaled_div32 for TFRC computations mapped from floating-point onto integer arithmetic, this completes the last stage of modifications. In particular, the overflow case for computing X_calc is circumvented by * breaking the computation into two stages * the first stage, res = (s*1E6)/R, cannot overflow due to use of u64 * in the second stage, res = (res*1E6)/f, overflow on u32 is avoided due to (i) returning UINT_MAX in this case (which is logically appropriate) and (ii) issuing a warning message into the system log (since very likely there is a problem somewhere else with the parameters) Lastly, all such scaling operations are now exported into tfrc.h, since actually this form of scaled computation is specific to TFRC and not to CCID3. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Acked-by: Ian McDonald <ian.mcdonald@jandi.co.nz> Signed-off-by: Arnaldo Carvalho de Melo <acme@mandriva.com>
Diffstat (limited to 'net')
-rw-r--r--net/dccp/ccids/ccid3.h19
-rw-r--r--net/dccp/ccids/lib/tfrc.h23
-rw-r--r--net/dccp/ccids/lib/tfrc_equation.c28
3 files changed, 35 insertions, 35 deletions
diff --git a/net/dccp/ccids/ccid3.h b/net/dccp/ccids/ccid3.h
index cd4fc542f73e..da0ca3c0a7b3 100644
--- a/net/dccp/ccids/ccid3.h
+++ b/net/dccp/ccids/ccid3.h
@@ -171,23 +171,4 @@ static inline struct ccid3_hc_rx_sock *ccid3_hc_rx_sk(const struct sock *sk)
171 return ccid_priv(dccp_sk(sk)->dccps_hc_rx_ccid); 171 return ccid_priv(dccp_sk(sk)->dccps_hc_rx_ccid);
172} 172}
173 173
174static inline u64 scaled_div(u64 a, u32 b)
175{
176 BUG_ON(b==0);
177 a *= 1000000;
178 do_div(a, b);
179 return a;
180}
181
182static inline u32 scaled_div32(u64 a, u32 b)
183{
184 u64 result = scaled_div(a, b);
185
186 if (result > UINT_MAX) {
187 DCCP_CRIT("Overflow: a(%llu)/b(%u) > ~0U",
188 (unsigned long long)a, b);
189 return UINT_MAX;
190 }
191 return result;
192}
193#endif /* _DCCP_CCID3_H_ */ 174#endif /* _DCCP_CCID3_H_ */
diff --git a/net/dccp/ccids/lib/tfrc.h b/net/dccp/ccids/lib/tfrc.h
index 45f30f59ea2a..faf5f7e219e3 100644
--- a/net/dccp/ccids/lib/tfrc.h
+++ b/net/dccp/ccids/lib/tfrc.h
@@ -13,8 +13,29 @@
13 * the Free Software Foundation; either version 2 of the License, or 13 * the Free Software Foundation; either version 2 of the License, or
14 * (at your option) any later version. 14 * (at your option) any later version.
15 */ 15 */
16
17#include <linux/types.h> 16#include <linux/types.h>
17#include <asm/div64.h>
18
19/* integer-arithmetic divisions of type (a * 1000000)/b */
20static inline u64 scaled_div(u64 a, u32 b)
21{
22 BUG_ON(b==0);
23 a *= 1000000;
24 do_div(a, b);
25 return a;
26}
27
28static inline u32 scaled_div32(u64 a, u32 b)
29{
30 u64 result = scaled_div(a, b);
31
32 if (result > UINT_MAX) {
33 DCCP_CRIT("Overflow: a(%llu)/b(%u) > ~0U",
34 (unsigned long long)a, b);
35 return UINT_MAX;
36 }
37 return result;
38}
18 39
19extern u32 tfrc_calc_x(u16 s, u32 R, u32 p); 40extern u32 tfrc_calc_x(u16 s, u32 R, u32 p);
20extern u32 tfrc_calc_x_reverse_lookup(u32 fvalue); 41extern u32 tfrc_calc_x_reverse_lookup(u32 fvalue);
diff --git a/net/dccp/ccids/lib/tfrc_equation.c b/net/dccp/ccids/lib/tfrc_equation.c
index ddac2c511e2f..90009fd77e15 100644
--- a/net/dccp/ccids/lib/tfrc_equation.c
+++ b/net/dccp/ccids/lib/tfrc_equation.c
@@ -13,7 +13,6 @@
13 */ 13 */
14 14
15#include <linux/module.h> 15#include <linux/module.h>
16#include <asm/div64.h>
17#include "../../dccp.h" 16#include "../../dccp.h"
18#include "tfrc.h" 17#include "tfrc.h"
19 18
@@ -616,15 +615,12 @@ static inline u32 tfrc_binsearch(u32 fval, u8 small)
616 * @R: RTT scaled by 1000000 (i.e., microseconds) 615 * @R: RTT scaled by 1000000 (i.e., microseconds)
617 * @p: loss ratio estimate scaled by 1000000 616 * @p: loss ratio estimate scaled by 1000000
618 * Returns X_calc in bytes per second (not scaled). 617 * Returns X_calc in bytes per second (not scaled).
619 *
620 * Note: DO NOT alter this code unless you run test cases against it,
621 * as the code has been optimized to stop underflow/overflow.
622 */ 618 */
623u32 tfrc_calc_x(u16 s, u32 R, u32 p) 619u32 tfrc_calc_x(u16 s, u32 R, u32 p)
624{ 620{
625 int index; 621 u16 index;
626 u32 f; 622 u32 f;
627 u64 tmp1, tmp2; 623 u64 result;
628 624
629 /* check against invalid parameters and divide-by-zero */ 625 /* check against invalid parameters and divide-by-zero */
630 BUG_ON(p > 1000000); /* p must not exceed 100% */ 626 BUG_ON(p > 1000000); /* p must not exceed 100% */
@@ -650,15 +646,17 @@ u32 tfrc_calc_x(u16 s, u32 R, u32 p)
650 f = tfrc_calc_x_lookup[index][0]; 646 f = tfrc_calc_x_lookup[index][0];
651 } 647 }
652 648
653 /* The following computes X = s/(R*f(p)) in bytes per second. Since f(p) 649 /*
654 * and R are both scaled by 1000000, we need to multiply by 1000000^2. 650 * Compute X = s/(R*f(p)) in bytes per second.
655 * ==> DO NOT alter this unless you test against overflow on 32 bit */ 651 * Since f(p) and R are both scaled by 1000000, we need to multiply by
656 tmp1 = ((u64)s * 100000000); 652 * 1000000^2. To avoid overflow, the result is computed in two stages.
657 tmp2 = ((u64)R * (u64)f); 653 * This works under almost all reasonable operational conditions, for a
658 do_div(tmp2, 10000); 654 * wide range of parameters. Yet, should some strange combination of
659 do_div(tmp1, tmp2); 655 * parameters result in overflow, the use of scaled_div32 will catch
660 656 * this and return UINT_MAX - which is a logically adequate consequence.
661 return (u32)tmp1; 657 */
658 result = scaled_div(s, R);
659 return scaled_div32(result, f);
662} 660}
663 661
664EXPORT_SYMBOL_GPL(tfrc_calc_x); 662EXPORT_SYMBOL_GPL(tfrc_calc_x);