tcp: correct srtt and mdev_us calculation
Subsystems (3)
RFC PATCH 1/1 tcp: correct srtt and mdev_us calculation
From the comments we can see that, rtt = 7/8 rtt + 1/8 new, but there is an mistake,
m -= (srtt >> 3);
srtt += m;
explain:
m -= (srtt >> 3); //use t stands for new m
t = m - srtt/8;
srtt = srtt + t
= srtt + m - srtt/8
= srtt 7/8 + m
Test code:
#include<stdio.h>
#define u32 unsigned int
static void test_old(u32 srtt, long mrtt_us)
{
long m = mrtt_us;
u32 old = srtt;
m -= (srtt >> 3);
srtt += m;
printf("%s old_srtt: %u mrtt_us: %ld new_srtt: %u\n", __func__, old, mrtt_us, srtt);
}static void test_new(u32 srtt, long mrtt_us)
{
long m = mrtt_us;
u32 old = srtt;
m = ((m - srtt) >> 3);
srtt += m;
printf("%s old_srtt: %u mrtt_us: %ld new_srtt: %u\n", __func__, old, mrtt_us, srtt);
}int main(int argc, char **argv)
{
u32 srtt = 100;
long mrtt_us = 90;
test_old(srtt, mrtt_us);
test_new(srtt, mrtt_us);
return 0;
}./a.outtest_old old_srtt: 100 mrtt_us: 90 new_srtt: 178 test_new old_srtt: 100 mrtt_us: 90 new_srtt: 98
--- net/ipv4/tcp_input.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
net/ipv4/tcp_input.c +2 -2
@@ -848,7 +848,7 @@ static void tcp_rtt_estimator(struct sock *sk, long mrtt_us)* that VJ failed to avoid. 8) */ if (srtt !=0 ) { - m -= (srtt >>3 );/* m is now error in rtt est */ + m = (m - srtt >>3 );/* m is now error in rtt est */ srtt += m;/* rtt = 7/8 rtt + 1/8 new */ if (m <0 ) { m = -m;/* m is now abs(error) */
@@ -864,7 +864,7 @@ static void tcp_rtt_estimator(struct sock *sk, long mrtt_us)if (m >0 ) m >>=3 ; }else { - m -= (tp->mdev_us >>2 );/* similar update on mdev */ + m = (m - tp->mdev_us >>2 );/* similar update on mdev */ } tp->mdev_us += m;/* mdev = 3/4 mdev + 1/4 new */ if (tp->mdev_us > tp->mdev_max_us) {
Signature · 1 line
2.34.1
Quoted 86 lines · Weiping Zhang
From the comments we can see that, rtt = 7/8 rtt + 1/8 new, but there is an mistake,
m -= (srtt >> 3);
srtt += m;explain:
m -= (srtt >> 3); //use t stands for new m
t = m - srtt/8;srtt = srtt + t
= srtt + m - srtt/8
= srtt 7/8 + mTest code:
#include<stdio.h>
#define u32 unsigned int
static void
test_old(u32 srtt, long mrtt_us){ long m = mrtt_us; u32 old = srtt; m -= (srtt >> 3); srtt += m; printf("%s old_srtt: %u mrtt_us: %ld new_srtt: %u\n", __func__, old, mrtt_us, srtt); }static void
test_new(u32 srtt, long mrtt_us){ long m = mrtt_us; u32 old = srtt; m = ((m - srtt) >> 3); srtt += m; printf("%s old_srtt: %u mrtt_us: %ld new_srtt: %u\n", __func__, old, mrtt_us, srtt); }int
main(int argc, char **argv){ u32 srtt = 100; long mrtt_us = 90; test_old(srtt, mrtt_us); test_new(srtt, mrtt_us); return 0; }./a.out
test_oldold_srtt: 100mrtt_us: 90new_srtt: 178test_newold_srtt: 100mrtt_us: 90new_srtt: 98Signed-off-by Weiping Zhang <[email protected]>--- net/ipv4/tcp_input.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)net/ipv4/tcp_input.c +2
-3@@ -848,7 +848,7 @@ static void tcp_rtt_estimator(struct sock *sk, long mrtt_us)* that VJ failed to avoid. 8) */ if (srtt !=0 ) { - m -= (srtt >>3 );/* m is now error in rtt est */ + m = (m - srtt >>3 );/* m is now error in rtt est */ srtt += m;/* rtt = 7/8 rtt + 1/8 new */ if (m <0 ) { m = -m;/* m is now abs(error) */ @@ -864,7 +864,7 @@ static void tcp_rtt_estimator(struct sock *sk, long mrtt_us)if (m >0 ) m >>=3 ; }else { - m -= (tp->mdev_us >>2 );/* similar update on mdev */ + m = (m - tp->mdev_us >>2 );/* similar update on mdev */ } tp->mdev_us += m;/* mdev = 3/4 mdev + 1/4 new */ if (tp->mdev_us > tp->mdev_max_us) { --
Quoted 2 lines
2.34.1
Sorry, this makes no sense to me.
Neal Cardwell
maintainerQuoted 54 lines · Weiping Zhang
From the comments we can see that, rtt = 7/8 rtt + 1/8 new, but there is an mistake,
m -= (srtt >> 3);
srtt += m;explain:
m -= (srtt >> 3); //use t stands for new m
t = m - srtt/8;srtt = srtt + t
= srtt + m - srtt/8
= srtt 7/8 + mTest code:
#include<stdio.h>
#define u32 unsigned int
static void
test_old(u32 srtt, long mrtt_us){ long m = mrtt_us; u32 old = srtt; m -= (srtt >> 3); srtt += m; printf("%s old_srtt: %u mrtt_us: %ld new_srtt: %u\n", __func__, old, mrtt_us, srtt); }static void
test_new(u32 srtt, long mrtt_us){ long m = mrtt_us; u32 old = srtt; m = ((m - srtt) >> 3); srtt += m; printf("%s old_srtt: %u mrtt_us: %ld new_srtt: %u\n", __func__, old, mrtt_us, srtt); }int
main(int argc, char **argv){ u32 srtt = 100; long mrtt_us = 90; test_old(srtt, mrtt_us); test_new(srtt, mrtt_us); return 0; }
Quoted 5 lines
./a.out
test_oldold_srtt: 100mrtt_us: 90new_srtt: 178test_newold_srtt: 100mrtt_us: 90new_srtt: 98Signed-off-by Weiping Zhang <[email protected]>
Please note that this analysis and this test program do not take account of the fact that srtt in the Linux kernel is maintained in a form where it is shifted left by 3 bits, to maintain a 3-bit fractional part. That is why at first glance it would seem there is a missing multiplication of the new sample by 1/8. By not shifting the new sample when it is added to srtt, the new sample is *implicitly* multiplied by 1/8.
Quoted 26 lines
net/ipv4/tcp_input.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)net/ipv4/tcp_input.c +2
-3@@ -848,7 +848,7 @@ static void tcp_rtt_estimator(struct sock *sk, long mrtt_us)* that VJ failed to avoid. 8) */ if (srtt !=0 ) { - m -= (srtt >>3 );/* m is now error in rtt est */ + m = (m - srtt >>3 );/* m is now error in rtt est */ srtt += m;/* rtt = 7/8 rtt + 1/8 new */ if (m <0 ) { m = -m;/* m is now abs(error) */ @@ -864,7 +864,7 @@ static void tcp_rtt_estimator(struct sock *sk, long mrtt_us)if (m >0 ) m >>=3 ; }else { - m -= (tp->mdev_us >>2 );/* similar update on mdev */ + m = (m - tp->mdev_us >>2 );/* similar update on mdev */ } tp->mdev_us += m;/* mdev = 3/4 mdev + 1/4 new */ if (tp->mdev_us > tp->mdev_max_us) { --
Quoted 1 line
2.34.1
AFAICT this proposed patch does not change the behavior of the code but merely expresses the same operations with slightly different syntax. Am I missing something? :-)
thanks,
neal
Quoted 62 lines · Neal Cardwell
Quoted 54 lines · Weiping Zhang
From the comments we can see that, rtt = 7/8 rtt + 1/8 new, but there is an mistake,
m -= (srtt >> 3);
srtt += m;explain:
m -= (srtt >> 3); //use t stands for new m
t = m - srtt/8;srtt = srtt + t
= srtt + m - srtt/8
= srtt 7/8 + mTest code:
#include<stdio.h>
#define u32 unsigned int
static void
test_old(u32 srtt, long mrtt_us){ long m = mrtt_us; u32 old = srtt; m -= (srtt >> 3); srtt += m; printf("%s old_srtt: %u mrtt_us: %ld new_srtt: %u\n", __func__, old, mrtt_us, srtt); }static void
test_new(u32 srtt, long mrtt_us){ long m = mrtt_us; u32 old = srtt; m = ((m - srtt) >> 3); srtt += m; printf("%s old_srtt: %u mrtt_us: %ld new_srtt: %u\n", __func__, old, mrtt_us, srtt); }int
main(int argc, char **argv){ u32 srtt = 100; long mrtt_us = 90; test_old(srtt, mrtt_us); test_new(srtt, mrtt_us); return 0; }Quoted 5 lines
./a.out
test_oldold_srtt: 100mrtt_us: 90new_srtt: 178test_newold_srtt: 100mrtt_us: 90new_srtt: 98Signed-off-by Weiping Zhang <[email protected]>
Quoted 7 lines
Please note that this analysis and this test program do not take account of the fact that srtt in the Linux kernel is maintained in a form where it is shifted left by 3 bits, to maintain a 3-bit fractional part. That is why at first glance it would seem there is a missing multiplication of the new sample by 1/8. By not shifting the new sample when it is added to srtt, the new sample is *implicitly* multiplied by 1/8.
Nifty. And it's documented.
struct tcp_sock {
…
u32 srtt_us; /* smoothed round trip time << 3 in usecs */
Thanks for the hint.
Quoted 23 lines
Quoted 23 lines
net/ipv4/tcp_input.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)net/ipv4/tcp_input.c +2
-2@@ -848,7 +848,7 @@ static void tcp_rtt_estimator(struct sock *sk, long mrtt_us)* that VJ failed to avoid. 8) */ if (srtt !=0 ) { - m -= (srtt >>3 );/* m is now error in rtt est */ + m = (m - srtt >>3 );/* m is now error in rtt est */ srtt += m;/* rtt = 7/8 rtt + 1/8 new */ if (m <0 ) { m = -m;/* m is now abs(error) */ @@ -864,7 +864,7 @@ static void tcp_rtt_estimator(struct sock *sk, long mrtt_us)if (m >0 ) m >>=3 ; }else { - m -= (tp->mdev_us >>2 );/* similar update on mdev */ + m = (m - tp->mdev_us >>2 );/* similar update on mdev */ }
Quoted 8 lines
Quoted 4 lines
net/ipv4/tcp_input.c +0
-1tp->mdev_us += m;/* mdev = 3/4 mdev + 1/4 new */ if (tp->mdev_us > tp->mdev_max_us) { --2.34.1
AFAICT this proposed patch does not change the behavior of the code but merely expresses the same operations with slightly different syntax. Am I missing something? :-)
I've been wondering about that too. There's a change hiding behind operator precedence. Would be better expressed with explicitly placed parenthesis:
m = (m - srtt) >> 3; /* m is now error in rtt est */
Sorry to reply to late caused by bad cold,
Quoted 80 lines · Jakub Sitnicki
Quoted 62 lines · Neal Cardwell
Quoted 54 lines · Weiping Zhang
From the comments we can see that, rtt = 7/8 rtt + 1/8 new, but there is an mistake,
m -= (srtt >> 3);
srtt += m;explain:
m -= (srtt >> 3); //use t stands for new m
t = m - srtt/8;srtt = srtt + t
= srtt + m - srtt/8
= srtt 7/8 + mTest code:
#include<stdio.h>
#define u32 unsigned int
static void
test_old(u32 srtt, long mrtt_us){ long m = mrtt_us; u32 old = srtt; m -= (srtt >> 3); srtt += m; printf("%s old_srtt: %u mrtt_us: %ld new_srtt: %u\n", __func__, old, mrtt_us, srtt); }static void
test_new(u32 srtt, long mrtt_us){ long m = mrtt_us; u32 old = srtt; m = ((m - srtt) >> 3); srtt += m; printf("%s old_srtt: %u mrtt_us: %ld new_srtt: %u\n", __func__, old, mrtt_us, srtt); }int
main(int argc, char **argv){ u32 srtt = 100; long mrtt_us = 90; test_old(srtt, mrtt_us); test_new(srtt, mrtt_us); return 0; }Quoted 5 lines
./a.out
test_oldold_srtt: 100mrtt_us: 90new_srtt: 178test_newold_srtt: 100mrtt_us: 90new_srtt: 98Signed-off-by Weiping Zhang <[email protected]>Quoted 7 lines
Please note that this analysis and this test program do not take account of the fact that srtt in the Linux kernel is maintained in a form where it is shifted left by 3 bits, to maintain a 3-bit fractional part. That is why at first glance it would seem there is a missing multiplication of the new sample by 1/8. By not shifting the new sample when it is added to srtt, the new sample is *implicitly* multiplied by 1/8.
Nifty. And it's documented.
struct
tcp_sock{
…
u32srtt_us; /* smoothed round trip time << 3 in usecs */Thanks for the hint.
Quoted 8 lines
Quoted 8 lines
net/ipv4/tcp_input.c static void tcp_rtt_estimator(struct sock *sk, long mrtt_us)
Quoted 8 lines
net/ipv4/tcp_input.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)net/ipv4/tcp_input.c +0
-0@@ -848,7 +848,7 @@ static void tcp_rtt_estimator(struct sock *sk, long mrtt_us)
As comments by Neal, srtt use lowest 3bits for fraction part, the @mrtt_us does not include fraction part,
so m - srtt is not suitable, since m -= (srtt >> 3) will get the delta which exclude fraction part, and m will also be
used to calculate mdev_us.
if we calculate srtt by: srtt = srtt *7/8 + (mrtt_us << 3)* 1 / 8, it's more readable, append 3bits 0 for fraction part.
srtt = srtt *7/8 + (mrtt_us << 3)* 1 / 8
srtt *7/8 => srtt - srtt >> 3
(mrtt_us << 3)* 1 / 8 => mrtt_us
then
srtt = srtt - srtt >> 3 + mrtt_us;
srtt = srtt + mrtt_us - srtt >> 3
it's same as current code^_^
my previous patch does not consider the fraction part, it generates a wrong result.
I write a new test code to decode the fraction part:
test_old old_srtt: 100 => 12.4 mrtt_us: 90 new_srtt: 178 => 22.2 test_new old_srtt: 100 => 12.4 mrtt_us: 90 new_srtt: 98 => 12.2
#include<stdio.h>
#include<stdlib.h>
#define u32 unsigned int
static void test_old(u32 srtt, long mrtt_us)
{
long m = mrtt_us;
u32 old = srtt;
m -= (srtt >> 3);
srtt += m;
printf("%s old_srtt: %8u => %8u.%u mrtt_us: %8ld new_srtt: %8u
=> %8u.%u\n", __func__, old, old >> 3, old & 7, mrtt_us, srtt, srtt>>3, srtt & 7);
//printf("%s old_srtt>>3: %8u mrtt_us: %8ld new_srtt>>3: %u\n", __func__, old>>3, mrtt_us, srtt>>3);
}
static void test_new(u32 srtt, long mrtt_us)
{
long m = mrtt_us;
u32 old = srtt;
m = ((m - srtt) >> 3);
srtt += m;
printf("%s old_srtt: %8u => %8u.%u mrtt_us: %8ld new_srtt: %8u
=> %8u.%u\n", __func__, old, old >> 3, old & 7, mrtt_us, srtt, srtt>>3, srtt & 7);
//printf("%s old_srtt>>3: %8u mrtt_us: %8ld new_srtt>>3: %u\n", __func__, old>>3, mrtt_us, srtt>>3);
}
int main(int argc, char **argv)
{
u32 srtt = atoi(argv[1]);
long mrtt_us = atoi(argv[2]);
test_old(srtt, mrtt_us);test_new(srtt, mrtt_us);
return 0;
}
Quoted 29 lines
Quoted 15 lines
Quoted 15 lines
net/ipv4/tcp_input.c +2
-2* that VJ failed to avoid. 8) */ if (srtt !=0 ) { - m -= (srtt >>3 );/* m is now error in rtt est */ + m = (m - srtt >>3 );/* m is now error in rtt est */ srtt += m;/* rtt = 7/8 rtt + 1/8 new */ if (m <0 ) { m = -m;/* m is now abs(error) */ @@ -864,7 +864,7 @@ static void tcp_rtt_estimator(struct sock *sk, long mrtt_us)if (m >0 ) m >>=3 ; }else { - m -= (tp->mdev_us >>2 );/* similar update on mdev */ + m = (m - tp->mdev_us >>2 );/* similar update on mdev */ }Quoted 8 lines
Quoted 4 lines
net/ipv4/tcp_input.c +0
-1tp->mdev_us += m;/* mdev = 3/4 mdev + 1/4 new */ if (tp->mdev_us > tp->mdev_max_us) { --2.34.1
AFAICT this proposed patch does not change the behavior of the code but merely expresses the same operations with slightly different syntax. Am I missing something? :-)
I've been wondering about that too. There's a change hiding behind operator precedence. Would be better expressed with explicitly placed parenthesis:
m = (m - srtt) >> 3; /* m is now error in rtt est */
Quoted 7 lines · Jakub Sitnicki
Nifty. And it's documented.
struct
tcp_sock{
…
u32srtt_us; /* smoothed round trip time << 3 in usecs */Thanks for the hint.
The >> 3 is all over the place... So even without a formal comment, anyone familiar with TCP stack would spot this...
include/net/tcp.h:700: return usecs_to_jiffies((tp->srtt_us >> 3) + tp->rttvar_us);include/trace/events/tcp.h:286: __entry->srtt = tp->srtt_us >> 3;include/uapi/linux/bpf.h:6038: __u32 srtt_us; /* smoothed
round trip time << 3 in usecs */include/uapi/linux/bpf.h:6396: __u32 srtt_us; /* Averaged
RTT << 3 in usecs */et/ipv4/tcp.c:3906: info->tcpi_rtt = tp->srtt_us >> 3;net/ipv4/tcp.c:4045: nla_put_u32(stats, TCP_NLA_SRTT, tp->srtt_us >> 3);net/ipv4/tcp_bbr.c:273: if (tp->srtt_us) { /* any RTT
sample yet? */net/ipv4/tcp_bbr.c:274: rtt_us = max(tp->srtt_us >> 3, 1U);
...
Quoted 5 lines · On Sat, 10 Dec 2022 18:45:56 +0100 Eric Dumazet <[email protected]> wrote:
Quoted 2 lines · Jakub Sitnicki
Nifty. And it's documented.
Quoted 8 lines
Quoted 5 lines
struct
tcp_sock{
…
u32srtt_us; /* smoothed round trip time << 3 in usecs */Thanks for the hint.
The >> 3 is all over the place... So even without a formal comment, anyone familiar with TCP stack would spot this...
And it should be in every text book already and is in BSD as well. Maybe a link to the SIGCOMM paper would be good for those google deprived people?