Merge branch 'upstream' of git://ftp.linux-mips.org/pub/scm/upstream-linus

[linux-drm-fsl-dcu.git] / net / dccp / ccids / lib / tfrc_equation.c

diff --git a/net/dccp/ccids/lib/tfrc_equation.c b/net/dccp/ccids/lib/tfrc_equation.c
index ddac2c511e2f288014ad1650881586b514472eec..e4e64b76c10ca8335aa71328e6f40cb462239ddf 100644 (file)
--- a/net/dccp/ccids/lib/tfrc_equation.c
+++ b/net/dccp/ccids/lib/tfrc_equation.c
@@ -13,7 +13,6 @@
  */
 
 #include <linux/module.h>
-#include <asm/div64.h>
 #include "../../dccp.h"
 #include "tfrc.h"
 
@@ -27,7 +26,7 @@
   The following two-column lookup table implements a part of the TCP throughput
   equation from [RFC 3448, sec. 3.1]:
 
-                                    s
+                                    s
   X_calc  =  --------------------------------------------------------------
             R * sqrt(2*b*p/3) + (3 * t_RTO * sqrt(3*b*p/8) * (p + 32*p^3))
 
@@ -36,7 +35,7 @@
        s      is the packet size in bytes
        R      is the round trip time in seconds
        p      is the loss event rate, between 0 and 1.0, of the number of loss
-                     events as a fraction of the number of packets transmitted
+                     events as a fraction of the number of packets transmitted
        t_RTO  is the TCP retransmission timeout value in seconds
        b      is the number of packets acknowledged by a single TCP ACK
 
@@ -48,9 +47,9 @@
 
   which we can break down into:
 
-                      s
+                     s
        X_calc  =  ---------
-                   R * f(p)
+                   R * f(p)
 
   where f(p) is given for 0 < p <= 1 by:
 
@@ -63,7 +62,7 @@
     * the return result f(p)
   The lookup table therefore actually tabulates the following function g(q):
 
-       g(q)  =  1000000 * f(q/1000000)
+       g(q)  =  1000000 * f(q/1000000)
 
   Hence, when p <= 1, q must be less than or equal to 1000000. To achieve finer
   granularity for the practically more relevant case of small values of p (up to
@@ -616,15 +615,12 @@ static inline u32 tfrc_binsearch(u32 fval, u8 small)
  *  @R: RTT                  scaled by 1000000   (i.e., microseconds)
  *  @p: loss ratio estimate  scaled by 1000000
  *  Returns X_calc           in bytes per second (not scaled).
- *
- * Note: DO NOT alter this code unless you run test cases against it,
- *       as the code has been optimized to stop underflow/overflow.
  */
 u32 tfrc_calc_x(u16 s, u32 R, u32 p)
 {
-       int index;
+       u16 index;
        u32 f;
-       u64 tmp1, tmp2;
+       u64 result;
 
        /* check against invalid parameters and divide-by-zero   */
        BUG_ON(p >  1000000);           /* p must not exceed 100%   */
@@ -632,7 +628,7 @@ u32 tfrc_calc_x(u16 s, u32 R, u32 p)
        if (R == 0) {                   /* possible  divide by zero */
                DCCP_CRIT("WARNING: RTT is 0, returning maximum X_calc.");
                return ~0U;
-       }
+       }
 
        if (p <= TFRC_CALC_X_SPLIT)             {     /* 0.0000 < p <= 0.05   */
                if (p < TFRC_SMALLEST_P) {            /* 0.0000 < p <  0.0001 */
@@ -642,7 +638,7 @@ u32 tfrc_calc_x(u16 s, u32 R, u32 p)
                } else                                /* 0.0001 <= p <= 0.05  */
                        index =  p/TFRC_SMALLEST_P - 1;
 
-               f = tfrc_calc_x_lookup[index][1];
+               f = tfrc_calc_x_lookup[index][1];
 
        } else {                                      /* 0.05   <  p <= 1.00  */
                index = p/(1000000/TFRC_CALC_X_ARRSIZE) - 1;
@@ -650,15 +646,17 @@ u32 tfrc_calc_x(u16 s, u32 R, u32 p)
                f = tfrc_calc_x_lookup[index][0];
        }
 
-       /* The following computes X = s/(R*f(p)) in bytes per second. Since f(p)
-        * and R are both scaled by 1000000, we need to multiply by 1000000^2.
-        * ==> DO NOT alter this unless you test against overflow on 32 bit   */
-       tmp1 = ((u64)s * 100000000);
-       tmp2 = ((u64)R * (u64)f);
-       do_div(tmp2, 10000);
-       do_div(tmp1, tmp2); 
-
-       return (u32)tmp1; 
+       /*
+        * Compute X = s/(R*f(p)) in bytes per second.
+        * Since f(p) and R are both scaled by 1000000, we need to multiply by
+        * 1000000^2. To avoid overflow, the result is computed in two stages.
+        * This works under almost all reasonable operational conditions, for a
+        * wide range of parameters. Yet, should some strange combination of
+        * parameters result in overflow, the use of scaled_div32 will catch
+        * this and return UINT_MAX - which is a logically adequate consequence.
+        */
+       result = scaled_div(s, R);
+       return scaled_div32(result, f);
 }
 
 EXPORT_SYMBOL_GPL(tfrc_calc_x);
@@ -689,8 +687,8 @@ u32 tfrc_calc_x_reverse_lookup(u32 fvalue)
        if (fvalue <= tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][1]) {
                index = tfrc_binsearch(fvalue, 1);
                return (index + 1) * TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE;
-       }
- 
+       }
+
        /* else ... it must be in the coarse-grained column */
        index = tfrc_binsearch(fvalue, 0);
        return (index + 1) * 1000000 / TFRC_CALC_X_ARRSIZE;