netdev - Re: [RFC PATCH] tcp: correct srtt and mdev

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <87mt805181.fsf@cloudflare.com>
Date:   Tue, 06 Dec 2022 10:11:11 +0100
From:   Jakub Sitnicki <jakub@...udflare.com>
To:     Neal Cardwell <ncardwell@...gle.com>
Cc:     Weiping Zhang <zhangweiping@...iglobal.com>, edumazet@...gle.com,
        davem@...emloft.net, yoshfuji@...ux-ipv6.org, dsahern@...nel.org,
        kuba@...nel.org, pabeni@...hat.com, netdev@...r.kernel.org,
        zwp10758@...il.com
Subject: Re: [RFC PATCH] tcp: correct srtt and mdev_us calculation

On Mon, Dec 05, 2022 at 02:15 PM -05, Neal Cardwell wrote:
> On Mon, Dec 5, 2022 at 1:02 PM Weiping Zhang
> <zhangweiping@...iglobal.com> wrote:
>>
>> 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.out
>> test_old old_srtt: 100 mrtt_us: 90 new_srtt: 178
>> test_new old_srtt: 100 mrtt_us: 90 new_srtt: 98
>>
>> Signed-off-by: Weiping Zhang <zhangweiping@...iglobal.com>
>
> 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.

>>  net/ipv4/tcp_input.c | 4 ++--
>>  1 file changed, 2 insertions(+), 2 deletions(-)
>>
>> diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
>> index 0640453fce54..0242bb31e1ce 100644
>> --- a/net/ipv4/tcp_input.c
>> +++ b/net/ipv4/tcp_input.c
>> @@ -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) {
>> --
>> 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 */