ccid3: Simplify calculation for reverse lookup of p
PATCH 8/22 ccid3: Simplify calculation for reverse lookup of p
This simplifies the calculation of a value p for a given fval when the first loss interval is computed (RFC 3448, 6.3.1). It makes use of the two new functions scaled_div/scaled_div32 to provide overflow protection.
Additionally, protection against divide-by-zero is extended - in this case the function will return the maximally possible value of p0%.
Background:
The maximum fval, f(100%), is approximately 244, i.e. the scaled value of fval should never exceed 244E6, which fits easily into u32. The problem is the scaling by 10^6, since additionally R(TT) is in microseconds.
This is resolved by breaking the division into two stages: the first stage computes fval=(s*10^6)/R, stores that into u64; the second stage computes fval = (fval*10^6)/X_recv and complains if overflow is reached for u32. This case is safe since the TFRC reverse-lookup routine then returns p0%.
--- net/dccp/ccids/ccid3.c | 39 ++++++++++++++++++++++----------------- 1 files changed, 22 insertions(+), 17 deletions(-)
net/dccp/ccids/ccid3.c +22 -17
@@ -785,12 +785,12 @@ static u32 ccid3_hc_rx_calc_first_li(str {struct ccid3_hc_rx_sock *hcrx =ccid3_hc_rx_sk (sk);struct dccp_rx_hist_entry *entry, *next, *tail =NULL ; -u32 rtt, delta, x_recv, fval, p, tmp2; +u32 rtt, delta, x_recv, p;struct timeval tstamp = {0 , };int interval =0 ;int win_count =0 ;int step =0 ; -u64 tmp1; +u64 fval;list_for_each_entry_safe (entry, next, &hcrx->ccid3hcrx_hist, dccphrx_node) {
@@ -834,30 +834,35 @@ found:ccid3_pr_debug ("%s, sk=%p, approximated RTT to %uus\n" ,dccp_role (sk), sk, rtt); -if (rtt =0 ) { -DCCP_WARN ("RTT=0, setting to 1\n" ); - rtt =1 ; +/* +* Determine the length of the first loss interval via inverse lookup. +* Assume that X_recv can be computed by the throughput equation +* s +* X_recv = -------- +* R * fval +* Find some p such that f(p) = fval; return 1/p [RFC 3448, 6.3.1]. +*/ +if (rtt =0 ) {/* would result in divide-by-zero */ +DCCP_WARN ("RTT=0, returning 1/p = 1\n" ); +return 1000000 ; }dccp_timestamp (sk, &tstamp); delta =timeval_delta (&tstamp, &hcrx->ccid3hcrx_tstamp_last_feedback); x_recv =scaled_div32 (hcrx->ccid3hcrx_bytes_recv, delta); -if (x_recv =0 ) - x_recv = hcrx->ccid3hcrx_x_recv; - - tmp1 = (u64 )x_recv * (u64 )rtt; -do_div (tmp1,10000000 ); - tmp2 = (u32 )tmp1; - -if (!tmp2) { -DCCP_CRIT ("tmp2 = 0, x_recv = %u, rtt =%u\n" , x_recv, rtt); -return ~0 ; +if (x_recv =0 ) {/* would also trigger divide-by-zero */ +DCCP_WARN ("X_recv=0\n" ); +if ((x_recv = hcrx->ccid3hcrx_x_recv) =0 ) { +DCCP_BUG ("stored value of X_recv is zero" ); +return 1000000 ; + } } - fval = (hcrx->ccid3hcrx_s *100000 ) / tmp2; -/* do not alter order above or you will get overflow on 32 bit */ + fval =scaled_div (hcrx->ccid3hcrx_s, rtt); + fval =scaled_div32 (fval, x_recv); p =tfrc_calc_x_reverse_lookup (fval); +ccid3_pr_debug ("%s, sk=%p, receive rate=%u bytes/s, implied " "loss rate=%u\n" ,dccp_role (sk), sk, x_recv, p);
Signature · 1 line
1.4.2.1.g3d5c
Quoted 7 lines · Arnaldo Carvalho de Melo
This simplifies the calculation of a value p for a given fval when the first loss interval is computed (RFC 3448, 6.3.1). It makes use of the two new functions scaled_div/scaled_div32 to provide overflow protection.
Additionally, protection against divide-by-zero is extended - in this case the function will return the maximally possible value of p0%.
Just discovered an error in this patch. If we can't determine the loss rate we should set the interval to ~0 as used by dccp_li_hist_calc_i_mean. We definitely should not use 1000000 as this signifies we got 1 million packets without loss and will cause performance to be ramped up in the face of problems! Possibly we should use 1 as a case if we want to signify we should slow down things. Thinking about this and writing a patch shortly.
Ian
Quoted 20 lines
net/dccp/ccids/ccid3.c +9
-0@@ -785,12 +785,12 @@ static u32 ccid3_hc_rx_calc_first_li(str@@ -834,30 +834,35 @@ found: +if (rtt =0 ) {/* would result in divide-by-zero */ +DCCP_WARN ("RTT=0, returning 1/p = 1\n" ); +return 1000000 ; } +if (x_recv =0 ) {/* would also trigger divide-by-zero */ +DCCP_WARN ("X_recv=0\n" ); +if ((x_recv = hcrx->ccid3hcrx_x_recv) =0 ) { +DCCP_BUG ("stored value of X_recv is zero" ); +return 1000000 ; + } }
Signature · 3 lines
Web: http://wand.net.nz/~iam4 Blog: http://imcdnzl.blogspot.com WAND Network Research Group