From 3294f202dc1acd82223e83ef59f272bd87bb06b2 Mon Sep 17 00:00:00 2001 From: Gerrit Renker Date: Wed, 11 Jun 2008 11:19:09 +0100 Subject: dccp ccid-3: Bug-Fix - Zero RTT is possible In commit $(825de27d9e40b3117b29a79d412b7a4b78c5d815) (from 27th May, commit message `dccp ccid-3: Fix "t_ipi explosion" bug'), the CCID-3 window counter computation was fixed to cope with RTTs < 4 microseconds. Such RTTs can be found e.g. when running CCID-3 over loopback. The fix removed a check against RTT < 4, but introduced a divide-by-zero bug. All steady-state RTTs in DCCP are filtered using dccp_sample_rtt(), which ensures non-zero samples. However, a zero RTT is possible on initialisation, when there is no RTT sample from the Request/Response exchange. The fix is to use the fallback-RTT from RFC 4340, 3.4. This is also better than just fixing update_win_count() since it allows other parts of the code to always assume that the RTT is non-zero during the time that the CCID is used. Signed-off-by: Gerrit Renker --- net/dccp/ccids/ccid3.c | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-) (limited to 'net/dccp/ccids') diff --git a/net/dccp/ccids/ccid3.c b/net/dccp/ccids/ccid3.c index f813077234b7..0474f4c5707a 100644 --- a/net/dccp/ccids/ccid3.c +++ b/net/dccp/ccids/ccid3.c @@ -329,8 +329,14 @@ static int ccid3_hc_tx_send_packet(struct sock *sk, struct sk_buff *skb) hctx->ccid3hctx_x = rfc3390_initial_rate(sk); hctx->ccid3hctx_t_ld = now; } else { - /* Sender does not have RTT sample: X_pps = 1 pkt/sec */ - hctx->ccid3hctx_x = hctx->ccid3hctx_s; + /* + * Sender does not have RTT sample: + * - set fallback RTT (RFC 4340, 3.4) since a RTT value + * is needed in several parts (e.g. window counter); + * - set sending rate X_pps = 1pps as per RFC 3448, 4.2. + */ + hctx->ccid3hctx_rtt = DCCP_FALLBACK_RTT; + hctx->ccid3hctx_x = hctx->ccid3hctx_s; hctx->ccid3hctx_x <<= 6; } ccid3_update_send_interval(hctx); -- cgit v1.2.3 From 1e2f0e5e8376f2a0ada8760fc9d3104e1a81382b Mon Sep 17 00:00:00 2001 From: Gerrit Renker Date: Wed, 11 Jun 2008 11:19:09 +0100 Subject: dccp: Fix sparse warnings This patch fixes the following sparse warnings: * nested min(max()) expression: net/dccp/ccids/ccid3.c:91:21: warning: symbol '__x' shadows an earlier one net/dccp/ccids/ccid3.c:91:21: warning: symbol '__y' shadows an earlier one * Declaration of function prototypes in .c instead of .h file, resulting in "should it be static?" warnings. * Declared "struct dccpw" static (local to dccp_probe). * Disabled dccp_delayed_ack() - not fully removed due to RFC 4340, 11.3 ("Receivers SHOULD implement delayed acknowledgement timers ..."). * Used a different local variable name to avoid net/dccp/ackvec.c:293:13: warning: symbol 'state' shadows an earlier one net/dccp/ackvec.c:238:33: originally declared here * Removed unused functions `dccp_ackvector_print' and `dccp_ackvec_print'. Signed-off-by: Gerrit Renker --- net/dccp/ccids/ccid3.c | 4 ++-- net/dccp/ccids/lib/tfrc.c | 8 -------- net/dccp/ccids/lib/tfrc.h | 11 +++++++++-- 3 files changed, 11 insertions(+), 12 deletions(-) (limited to 'net/dccp/ccids') diff --git a/net/dccp/ccids/ccid3.c b/net/dccp/ccids/ccid3.c index 0474f4c5707a..a1929f33d703 100644 --- a/net/dccp/ccids/ccid3.c +++ b/net/dccp/ccids/ccid3.c @@ -159,8 +159,8 @@ static void ccid3_hc_tx_update_x(struct sock *sk, ktime_t *stamp) } else if (ktime_us_delta(now, hctx->ccid3hctx_t_ld) - (s64)hctx->ccid3hctx_rtt >= 0) { - hctx->ccid3hctx_x = - max(min(2 * hctx->ccid3hctx_x, min_rate), + hctx->ccid3hctx_x = min(2 * hctx->ccid3hctx_x, min_rate); + hctx->ccid3hctx_x = max(hctx->ccid3hctx_x, scaled_div(((__u64)hctx->ccid3hctx_s) << 6, hctx->ccid3hctx_rtt)); hctx->ccid3hctx_t_ld = now; diff --git a/net/dccp/ccids/lib/tfrc.c b/net/dccp/ccids/lib/tfrc.c index d1dfbb8de64c..97ecec0a8e76 100644 --- a/net/dccp/ccids/lib/tfrc.c +++ b/net/dccp/ccids/lib/tfrc.c @@ -14,14 +14,6 @@ module_param(tfrc_debug, bool, 0444); MODULE_PARM_DESC(tfrc_debug, "Enable debug messages"); #endif -extern int tfrc_tx_packet_history_init(void); -extern void tfrc_tx_packet_history_exit(void); -extern int tfrc_rx_packet_history_init(void); -extern void tfrc_rx_packet_history_exit(void); - -extern int tfrc_li_init(void); -extern void tfrc_li_exit(void); - static int __init tfrc_module_init(void) { int rc = tfrc_li_init(); diff --git a/net/dccp/ccids/lib/tfrc.h b/net/dccp/ccids/lib/tfrc.h index 1fb1187bbf1c..ddd8107b927f 100644 --- a/net/dccp/ccids/lib/tfrc.h +++ b/net/dccp/ccids/lib/tfrc.h @@ -58,7 +58,14 @@ static inline u32 tfrc_ewma(const u32 avg, const u32 newval, const u8 weight) return avg ? (weight * avg + (10 - weight) * newval) / 10 : newval; } -extern u32 tfrc_calc_x(u16 s, u32 R, u32 p); -extern u32 tfrc_calc_x_reverse_lookup(u32 fvalue); +extern u32 tfrc_calc_x(u16 s, u32 R, u32 p); +extern u32 tfrc_calc_x_reverse_lookup(u32 fvalue); +extern int tfrc_tx_packet_history_init(void); +extern void tfrc_tx_packet_history_exit(void); +extern int tfrc_rx_packet_history_init(void); +extern void tfrc_rx_packet_history_exit(void); + +extern int tfrc_li_init(void); +extern void tfrc_li_exit(void); #endif /* _TFRC_H_ */ -- cgit v1.2.3 From 1e8a287c79f64226541f5c44aa52d4698bb84cf5 Mon Sep 17 00:00:00 2001 From: Gerrit Renker Date: Wed, 11 Jun 2008 11:19:10 +0100 Subject: dccp ccid-3: TFRC reverse-lookup Bug-Fix This fixes a bug in the reverse lookup of p: given a value f(p), instead of p, the function returned the smallest tabulated value f(p). The smallest tabulated value of 10^6 * f(p) = sqrt(2*p/3) + 12 * sqrt(3*p/8) * (32 * p^3 + p) for p=0.0001 is 8172. Since this value is scaled by 10^6, the outcome of this bug is that a loss of 8172/10^6 = 0.8172% was reported whenever the input was below the table resolution of 0.01%. This means that the value was over 80 times too high, resulting in large spikes of the initial loss interval, thus unnecessarily reducing the throughput. Also corrected the printk format (%u for u32). Signed-off-by: Gerrit Renker --- net/dccp/ccids/lib/tfrc_equation.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'net/dccp/ccids') diff --git a/net/dccp/ccids/lib/tfrc_equation.c b/net/dccp/ccids/lib/tfrc_equation.c index e4e64b76c10c..2f20a29cffe4 100644 --- a/net/dccp/ccids/lib/tfrc_equation.c +++ b/net/dccp/ccids/lib/tfrc_equation.c @@ -661,7 +661,7 @@ u32 tfrc_calc_x(u16 s, u32 R, u32 p) EXPORT_SYMBOL_GPL(tfrc_calc_x); -/* +/** * tfrc_calc_x_reverse_lookup - try to find p given f(p) * * @fvalue: function value to match, scaled by 1000000 @@ -676,11 +676,11 @@ u32 tfrc_calc_x_reverse_lookup(u32 fvalue) /* Error cases. */ if (fvalue < tfrc_calc_x_lookup[0][1]) { - DCCP_WARN("fvalue %d smaller than resolution\n", fvalue); - return tfrc_calc_x_lookup[0][1]; + DCCP_WARN("fvalue %u smaller than resolution\n", fvalue); + return TFRC_SMALLEST_P; } if (fvalue > tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][0]) { - DCCP_WARN("fvalue %d exceeds bounds!\n", fvalue); + DCCP_WARN("fvalue %u exceeds bounds!\n", fvalue); return 1000000; } -- cgit v1.2.3 From 7deb0f851003287d7e259bf6b33548b144c0f2d5 Mon Sep 17 00:00:00 2001 From: Gerrit Renker Date: Wed, 11 Jun 2008 11:19:10 +0100 Subject: dccp ccid-3: X truncated due to type conversion This fixes a bug in computing the inter-packet-interval t_ipi = s/X: scaled_div32(a, b) uses u32 for b, but in "scaled_div32(s, X)" the type of the sending rate `X' is u64. Since X is scaled by 2^6, this truncates rates greater than 2^26 Bps (~537 Mbps). Using full 64-bit division now. Signed-off-by: Gerrit Renker --- net/dccp/ccids/lib/tfrc.h | 14 ++++++-------- 1 file changed, 6 insertions(+), 8 deletions(-) (limited to 'net/dccp/ccids') diff --git a/net/dccp/ccids/lib/tfrc.h b/net/dccp/ccids/lib/tfrc.h index ddd8107b927f..ed9857527acf 100644 --- a/net/dccp/ccids/lib/tfrc.h +++ b/net/dccp/ccids/lib/tfrc.h @@ -15,7 +15,7 @@ * (at your option) any later version. */ #include -#include +#include #include "../../dccp.h" /* internal includes that this module exports: */ #include "loss_interval.h" @@ -29,21 +29,19 @@ extern int tfrc_debug; #endif /* integer-arithmetic divisions of type (a * 1000000)/b */ -static inline u64 scaled_div(u64 a, u32 b) +static inline u64 scaled_div(u64 a, u64 b) { BUG_ON(b==0); - a *= 1000000; - do_div(a, b); - return a; + return div64_u64(a * 1000000, b); } -static inline u32 scaled_div32(u64 a, u32 b) +static inline u32 scaled_div32(u64 a, u64 b) { u64 result = scaled_div(a, b); if (result > UINT_MAX) { - DCCP_CRIT("Overflow: a(%llu)/b(%u) > ~0U", - (unsigned long long)a, b); + DCCP_CRIT("Overflow: %llu/%llu > UINT_MAX", + (unsigned long long)a, (unsigned long long)b); return UINT_MAX; } return result; -- cgit v1.2.3