Merge branch 'upstream-linus' of master.kernel.org:/pub/scm/linux/kernel/git/jgarzik...

[powerpc.git] / net / ipv4 / tcp_cubic.c

diff --git a/net/ipv4/tcp_cubic.c b/net/ipv4/tcp_cubic.c
index 9a582fb..1422448 100644 (file)
--- a/net/ipv4/tcp_cubic.c
+++ b/net/ipv4/tcp_cubic.c
@@ -1,5 +1,5 @@
 /*
- * TCP CUBIC: Binary Increase Congestion control for TCP v2.0
+ * TCP CUBIC: Binary Increase Congestion control for TCP v2.1
  *
  * This is from the implementation of CUBIC TCP in
  * Injong Rhee, Lisong Xu.
@@ -51,8 +51,6 @@ MODULE_PARM_DESC(bic_scale, "scale (scaled by 1024) value for bic function (bic_
 module_param(tcp_friendliness, int, 0644);
 MODULE_PARM_DESC(tcp_friendliness, "turn on/off tcp friendliness");
 
-#include <asm/div64.h>
-
 /* BIC TCP Parameters */
 struct bictcp {
        u32     cnt;            /* increase cwnd by 1 after ACKs */
@@ -93,50 +91,51 @@ static void bictcp_init(struct sock *sk)
                tcp_sk(sk)->snd_ssthresh = initial_ssthresh;
 }
 
-/* 64bit divisor, dividend and result. dynamic precision */
-static inline u_int64_t div64_64(u_int64_t dividend, u_int64_t divisor)
-{
-       u_int32_t d = divisor;
-
-       if (divisor > 0xffffffffULL) {
-               unsigned int shift = fls(divisor >> 32);
-
-               d = divisor >> shift;
-               dividend >>= shift;
-       }
-
-       /* avoid 64 bit division if possible */
-       if (dividend >> 32)
-               do_div(dividend, d);
-       else
-               dividend = (uint32_t) dividend / d;
-
-       return dividend;
-}
-
-/*
- * calculate the cubic root of x using Newton-Raphson
+/* calculate the cubic root of x using a table lookup followed by one
+ * Newton-Raphson iteration.
+ * Avg err ~= 0.195%
  */
 static u32 cubic_root(u64 a)
 {
-       u32 x, x1;
-
-       /* Initial estimate is based on:
-        * cbrt(x) = exp(log(x) / 3)
+       u32 x, b, shift;
+       /*
+        * cbrt(x) MSB values for x MSB values in [0..63].
+        * Precomputed then refined by hand - Willy Tarreau
+        *
+        * For x in [0..63],
+        *   v = cbrt(x << 18) - 1
+        *   cbrt(x) = (v[x] + 10) >> 6
         */
-       x = 1u << (fls64(a)/3);
+       static const u8 v[] = {
+               /* 0x00 */    0,   54,   54,   54,  118,  118,  118,  118,
+               /* 0x08 */  123,  129,  134,  138,  143,  147,  151,  156,
+               /* 0x10 */  157,  161,  164,  168,  170,  173,  176,  179,
+               /* 0x18 */  181,  185,  187,  190,  192,  194,  197,  199,
+               /* 0x20 */  200,  202,  204,  206,  209,  211,  213,  215,
+               /* 0x28 */  217,  219,  221,  222,  224,  225,  227,  229,
+               /* 0x30 */  231,  232,  234,  236,  237,  239,  240,  242,
+               /* 0x38 */  244,  245,  246,  248,  250,  251,  252,  254,
+       };
+
+       b = fls64(a);
+       if (b < 7) {
+               /* a in [0..63] */
+               return ((u32)v[(u32)a] + 35) >> 6;
+       }
+
+       b = ((b * 84) >> 8) - 1;
+       shift = (a >> (b * 3));
+
+       x = ((u32)(((u32)v[shift] + 10) << b)) >> 6;
 
        /*
-        * Iteration based on:
+        * Newton-Raphson iteration
         *                         2
         * x    = ( 2 * x  +  a / x  ) / 3
         *  k+1          k         k
         */
-       do {
-               x1 = x;
-               x = (2 * x + (uint32_t) div64_64(a, x*x)) / 3;
-       } while (abs(x1 - x) > 1);
-
+       x = (2 * x + (u32)div64_64(a, (u64)x * (u64)(x - 1)));
+       x = ((x * 341) >> 10);
        return x;
 }
 
@@ -215,7 +214,9 @@ static inline void bictcp_update(struct bictcp *ca, u32 cwnd)
        if (ca->delay_min > 0) {
                /* max increment = Smax * rtt / 0.1  */
                min_cnt = (cwnd * HZ * 8)/(10 * max_increment * ca->delay_min);
-               if (ca->cnt < min_cnt)
+
+               /* use concave growth when the target is above the origin */
+               if (ca->cnt < min_cnt && t >= ca->bic_K)
                        ca->cnt = min_cnt;
        }
 
@@ -333,7 +334,7 @@ static void bictcp_state(struct sock *sk, u8 new_state)
 /* Track delayed acknowledgment ratio using sliding window
  * ratio = (15*ratio + sample) / 16
  */
-static void bictcp_acked(struct sock *sk, u32 cnt)
+static void bictcp_acked(struct sock *sk, u32 cnt, ktime_t last)
 {
        const struct inet_connection_sock *icsk = inet_csk(sk);
 
@@ -401,4 +402,4 @@ module_exit(cubictcp_unregister);
 MODULE_AUTHOR("Sangtae Ha, Stephen Hemminger");
 MODULE_LICENSE("GPL");
 MODULE_DESCRIPTION("CUBIC TCP");
-MODULE_VERSION("2.0");
+MODULE_VERSION("2.1");