: Fine-grained sending rate resolution / division errors
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_ */
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_calcandX_recvback 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
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_calcandX_recvback 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
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
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
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_recvwhich acts as cache in [RFC 3448, 4.4] - lots of division operations where the value needs to be stored afterwards again. SoX_calcwould 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)
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