Skip to contentSkip to conversation

: Fine-grained sending rate resolution / division errors

RFC PATCH In review Gerrit Renker 3 participants 7 messages Nov 29, 2006 – Dec 4, 2006 Networking

lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 : Fine-grained sending rate resolution / division errors

Here is now the patch, I have had a hard time due to division of u64 by u32. I have also checked again - it is feasible to prune X_calc and X_recv back to u32. If you prefer that, I can change the patch.

I'd welcome suggestions about how to improve the division, I had wanted to at least not throw away the remainder.

Maybe in future time everything could be scaled by powers of 2, would make things easier.

Gerrit
-------------------------> Commit Message <--------------------------- [DCCP]: Resolve lower sending rates, avoid integer division error

This patch
* resolves a bug in CCID 3 where packets smaller than 32/64 bytes resulted in sending rates of 0
* resolves sending rates for all practically applicable cases
* simplifies the problem that, due to the necessary scaling, overflow is likely
* it implements the strategy from
http://www.mail-archive.com/[email protected]/msg00938.html

---
 include/linux/tfrc.h   |   11 +++++--
 net/dccp/ccids/ccid3.c |   70 +++++++++++++++++++------------------------------
 net/dccp/ccids/ccid3.h |   20 +++++++++-----
 3 files changed, 49 insertions(+), 52 deletions(-)
include/linux/tfrc.h +8 -3
@@ -37,11 +37,16 @@ struct tfrc_rx_info {
  * 	@tfrctx_p:	current loss event rate (5.4)
  * 	@tfrctx_rto:	estimate of RTO, equals 4*RTT (4.3)
  * 	@tfrctx_ipi:	inter-packet interval (4.6)
+ *
+ *  NOTE: The sender needs to store fractional sending rates in the range 1/64
+ *  (smallest sending rate: a packet of 1 byte every 64 seconds) up to 4 Gbyte
+ *  per second (IPv6 max jumbogram). Hence we store _all_ sending rates in units
+ *  of 64 * bytes/second - hence the use of __u64.
  */
 struct tfrc_tx_info {
-	__u32 tfrctx_x;
-	__u32 tfrctx_x_recv;
-	__u32 tfrctx_x_calc;
+	__u64 tfrctx_x;
+	__u64 tfrctx_x_recv;
+	__u64 tfrctx_x_calc;
 	__u32 tfrctx_rtt;
 	__u32 tfrctx_p;
 	__u32 tfrctx_rto;
net/dccp/ccids/ccid3.c +27 -41

154 lines not on this page · raw message

net/dccp/ccids/ccid3.h +13 -7
@@ -75,14 +75,14 @@ enum ccid3_hc_tx_states {
 
 /** struct ccid3_hc_tx_sock - CCID3 sender half-connection socket
  *
- * @ccid3hctx_x - Current sending rate
- * @ccid3hctx_x_recv - Receive rate in bytes per second
- * @ccid3hctx_x_calc - Calculated send rate (RFC 3448, 3.1)
- * @ccid3hctx_rtt - Estimate of current round trip time in usecs
+ * @ccid3hctx_x - Current sending rate in 64 * bytes per second
+ * @ccid3hctx_x_recv - Receive rate    in 64 * bytes per second
+ * @ccid3hctx_x_calc - Calculated rate in 64 * bytes per second
+ * @ccid3hctx_rtt - Estimate of current round trip time           in usecs
  * @ccid3hctx_p - Current loss event rate (0-1) scaled by 1000000
- * @ccid3hctx_s - Packet size
- * @ccid3hctx_t_rto - Retransmission Timeout (RFC 3448, 3.1)
- * @ccid3hctx_t_ipi - Interpacket (send) interval (RFC 3448, 4.6)
+ * @ccid3hctx_s - Packet size in bytes
+ * @ccid3hctx_t_rto - Retransmission Timeout (RFC 3448, 3.1)      in usecs
+ * @ccid3hctx_t_ipi - Interpacket (send) interval (RFC 3448, 4.6) in usecs
  * @ccid3hctx_state - Sender state, one of %ccid3_hc_tx_states
  * @ccid3hctx_last_win_count - Last window counter sent
  * @ccid3hctx_t_last_win_count - Timestamp of earliest packet
@@ -171,4 +171,10 @@ static inline struct ccid3_hc_rx_sock *c
     return ccid_priv(dccp_sk(sk)->dccps_hc_rx_ccid);
 }
 
+static inline u64 scaled_div(u64 a, u32 b)
+{
+	a *= 1000000;
+	do_div(a, b);
+	return a;
+}
 #endif /* _DCCP_CCID3_H_ */
#1 lore raw
Quoted 3 lines · Gerrit Renker

Here is now the patch, I have had a hard time due to division of u64 by u32. I have also checked again - it is feasible to prune X_calc and X_recv back to u32. If you prefer that, I can change the patch.

If it is possible, its better, minus 8 bytes per half connection on a (hey, I really, really wanna see this real) _real busy_ DCCP server :-)

Quoted 2 lines

I'd welcome suggestions about how to improve the division, I had wanted to at least not throw away the remainder.

Just got back from a "my dog took me to do some exercise" session, will have to read this tomorrow again, but I liked what I saw from the first skim of it :-)

- Arnaldo

Acked-by on v1 1/1
#2 lore raw
In reply to Gerrit Renker
Quoted 4 lines · Gerrit Renker

Here is now the patch, I have had a hard time due to division of u64 by u32. I have also checked again - it is feasible to prune X_calc and X_recv back to u32. If you prefer that, I can change the patch.

Yes I remember having great difficulty with that too when I converted the code from FreeBSD to Linux (and they had floating point as well...) I never got further than what went into the code.

This all looks good in theory. Still trying to resolve earlier DCCP CCID3 issues.

Ian

Signature · 3 lines
Web: http://wand.net.nz/~iam4
Blog: http://imcdnzl.blogspot.com
WAND Network Research Group
#3 lore raw
In reply to Gerrit Renker

Quoting Arnaldo Carvalho de Melo:

|  > Here is now the patch, I have had a hard time due to division of u64 by
|  > u32. I have also checked again - it is feasible to prune X_calc and
|  > X_recv back to u32. If you prefer that, I can change the patch.
|  
|  If it is possible, its better, minus 8 bytes per half connection

I have checked again - the best that seems possible is 4 bytes less. This is due to X_recv which acts as cache in [RFC 3448, 4.4] - lots of division operations where the value needs to be stored afterwards again. So X_calc would remain as 32bit, I will write up how I think it should look like and revise the patch - tomorrow, since the bug hunting took some time away.

Ian I am sorry for the time lost in bisecting through the patches. There are however more issues to resolve where your help and advice will be sorely needed. With this bug I felt somehow responsible since in a way I had caused it.

Gerrit

#4 lore raw
In reply to Gerrit Renker
Quoted 4 lines · Gerrit Renker

Ian I am sorry for the time lost in bisecting through the patches. There are however more issues to resolve where your help and advice will be sorely needed. With this bug I felt somehow responsible since in a way I had caused it.

Gerrit - that is OK. That's part of the community - finding bugs etc. I've caused just as much grief to others! I appreciate you saying so though.

Ian

Signature · 3 lines
Web: http://wand.net.nz/~iam4
Blog: http://imcdnzl.blogspot.com
WAND Network Research Group
#5 lore raw
In reply to Gerrit Renker
Quoted 6 lines · Gerrit Renker

Quoting Arnaldo Carvalho de Melo:

|  > Here is now the patch, I have had a hard time due to division of u64 by
|  > u32. I have also checked again - it is feasible to prune X_calc and
|  > X_recv back to u32. If you prefer that, I can change the patch.
|
|  If it is possible, its better, minus 8 bytes per half connection
Quoted 6 lines

I have checked again - the best that seems possible is 4 bytes less. This is due to X_recv which acts as cache in [RFC 3448, 4.4] - lots of division operations where the value needs to be stored afterwards again. So X_calc would remain as 32bit, I will write up how I think it should look like and revise the patch - tomorrow, since the bug hunting took some time away.

OK, take your time.

Quoted 3 lines

Ian I am sorry for the time lost in bisecting through the patches. There are however more issues to resolve where your help and advice will be sorely

needed.

s/sorely/surely/g

<joke>
No need to inflict pain on Ian, not at this level! </joke>

:o)

#6 lore raw
In reply to Gerrit Renker

Quoting Arnaldo Carvalho de Melo:
o:

|  > |  > Here is now the patch, I have had a hard time due to division of u64 by
|  > |  > u32. I have also checked again - it is feasible to prune X_calc and
|  > |  > X_recv back to u32. If you prefer that, I can change the patch.
|  > |
|  > |  If it is possible, its better, minus 8 bytes per half connection
|  > I have checked again - the best that seems possible is 4 bytes less. This
|  > is due to X_recv which acts as cache in [RFC 3448, 4.4] - lots of division
|  > operations where the value needs to be stored afterwards again.
|  > So X_calc would remain as 32bit, I will write up how I think it should look
|  > like and revise the patch - tomorrow, since the bug hunting took some time
|  > away.
|  
|  OK, take your time.

Please find attached, below, the revised plan for finer-grained resolution; I am using ' << 6' for all scaling operations, for consistency. Patch to codify this follows later.

Revised approach to achieve finer-grained resolution of sending rates
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

I) Summary
----------
The sending rate X and the cached value X_recv of the receiver-estimated sending rate are both scaled by 64 (2^6) in order to:
* cope with low sending rates (minimally 1 byte/second)
* allow upgrading to a packets-per-second sending principle
* avoid calculation errors due to integer arithmetic
The following data types are used:
* u32 X_calc - is maintained in bytes/second
* u64 X - is maintained in 64 * bytes/second
* u64 X_recv - is maintained in 64 * bytes/second
This choice is a compromise between minimising the size of sender data structures and requirements. X needs to be u64 to avoid overflow, X_recv needs a finer granularity to avoid underflow when modifying the cached value via the nofeedback timer [RFC 3448, 4.4].

Furthermore, the usecs_div() function should be replaced by:
* u64 scaled_div(u64 a, u32 b) -- where u64 is safe
* u32 scaled_div32(u64 a, u32 b) -- which tests against overflow

II) Initialisation [RFC 3448, 4.2]
----------------------------------
Set X[/s] to 64 * 1 packet / second (i.e., X = s << 6)

III) Sender behaviour when a feedback packet is received
--------------------------------------------------------
(a) Scale X_recv when it is received:

X_recv = hctx->packet_options_x_recv << 6

(b) Step (4) of [RFC 3448, 4.3]:

If (p > 0) {

X_calc = calcX(s, R, p)

X = min(X_calc << 6, 2 * X_recv) /* X_recv is already scaled */
X = max(X, (s << 6)/t_mbi)

  		} Else If(t_now - tld >= R) {
  			X  =  2 * min(X, X_recv)
  			X  =  max(X, scaled_div(s << 6, R))	/*  R in microseconds */

tld = t_now
}

(c) Step (5) of [RFC 3448, 4.3]:
The nofeedback timer is set to expire in
t_nfb = max(4 * R, scaled_div32(2 * s, X >> 6))

	IV) Expiration of the nofeedback timer [RFC 3448, 4.4]
	------------------------------------------------------
	(a) If the sender has previously received feedback from the receiver
		
		If (p = 0 ||  
		    X_calc > (X_recv >> 5))   		/* divided by 2^6, multiplied by 2^1 */
		
			X_recv  =  max(X_recv/2, (s << 6)/(2*t_mbi))

		Else
				
			X_recv  =  X_calc << 4		/* scaled by 2^6, divided by 2^2 */
			
	
		/* recalculate X according to [RFC 3448, 4.3]   */
		
		/* expire the nofeedback timer after: */
		t_nfb = max(4 * R, scaled_div32(2 * s, X >> 6))
					  
					  
	(b) If the sender does not yet have feedback
	
		X  =  max(X/2, (s << 6)/t_mbi)
		
		/* set the nofeedback timer to expire after 2 seconds */

					  

	V) Scheduling of Packet Transmissions [RFC 3448, 4.6]
	-----------------------------------------------------
	        
	        t_ipi   =   scaled_div(s, X >> 6)           /* microseconds */
      
	VI) Larger initial windows [RFC 4342, sec. 5]
	---------------------------------------------
            w_init  =  min(4*s , max(2*s, 4380))
            X       =  scaled_div(w_init << 6, R)
            

	VII) Overflow analysis of scaled_div/scaled_div32
	-------------------------------------------------
	The way the functions are used as above is safe, since:
	
	IIIb):  X  =  max(X, scaled_div(s << 6, R))
	        Is safe since (2^32 - 1)*64*1E6 fit in u64
	        
	IIIc):  t_nfb = max(4 * R, scaled_div32(2 * s, X >> 6))
			This can overflow (e.g. s=(2^32 -1) and X>>6 = 1),
			hence we need the overflow test of scaled_div32
			
	IVa):   analogous to IIIc
	
	V):     t_ipi = scaled_div(s, X >> 6)
			This is safe on u32, since s <= 2^32 -1 and X > 0
			Hence we do not need scaled_div32() here
			
	VI):    X  =  scaled_div(w_init << 6, R)
			This is safe, since 4380*64*1E6 fit in u64 (worst case with
			R=1 and w_initC80) 
		
	
	VIII) Further simplification
	----------------------------
	Since the constant t_mbi = 64 is a power of two, the following
	simplifications are additionally possible:
		* (s << 6)/t_mbi      can be replaced with s
		* (s << 6)/(2*t_mbi)  can be replaced with s/2