Re: [RFC PATCH v1 18/50] net/ipv6/addrconf.c: Use prandom_u32_max for rfc3315 backoff time computation

Re: [RFC PATCH v1 18/50] net/ipv6/addrconf.c: Use prandom_u32_max for rfc3315 backoff time computation

[Maciej Żenczykowski]

>         /* multiply 'initial retransmission time' by 0.9 .. 1.1 */
> -       u64 tmp = (900000 + prandom_u32() % 200001) * (u64)irt;
> -       do_div(tmp, 1000000);
> -       return (s32)tmp;
> +       s32 range = irt / 5;
> +       return irt - (s32)(range/2) + (s32)prandom_u32_max(range);

The cast on range/2 looks entirely spurious

>         /* multiply 'retransmission timeout' by 1.9 .. 2.1 */
> -       u64 tmp = (1900000 + prandom_u32() % 200001) * (u64)rt;
> -       do_div(tmp, 1000000);
> -       if ((s32)tmp > mrt) {
> +       s32 range = rt / 5;
> +       s32 tmp = 2*rt - (s32)(range/2) + (s32)prandom_u32_max(range);

Here as well.  Honestly the cast on prandom might also not be
necessary, but that at least has a reason.

> +       if (tmp > mrt) {
>                 /* multiply 'maximum retransmission time' by 0.9 .. 1.1 */
> -               tmp = (900000 + prandom_u32() % 200001) * (u64)mrt;
> -               do_div(tmp, 1000000);
> +               range = mrt / 5;
> +               tmp = mrt - (s32)(range/2) + (s32)prandom_u32_max(range);

Ditto.

>         }
>         return (s32)tmp;
>  }

- Maciej

Re: [RFC PATCH v1 18/50] net/ipv6/addrconf.c: Use prandom_u32_max for rfc3315 backoff time computation

[George Spelvin]

On Sat, Mar 28, 2020 at 09:56:58AM -0700, Maciej ?enczykowski wrote:
>>         /* multiply 'initial retransmission time' by 0.9 .. 1.1 */
>> -       u64 tmp = (900000 + prandom_u32() % 200001) * (u64)irt;
>> -       do_div(tmp, 1000000);
>> -       return (s32)tmp;
>> +       s32 range = irt / 5;
>> +       return irt - (s32)(range/2) + (s32)prandom_u32_max(range);
> 
> The cast on range/2 looks entirely spurious

You're absolutely right; sorry about that.  I was trying to
preserve the previous code's mixture of signed and unsigned types
and managed to confuse myself.

(I think I got distracted researching whether the inputs could be
negative.)

>>         /* multiply 'retransmission timeout' by 1.9 .. 2.1 */
>> -       u64 tmp = (1900000 + prandom_u32() % 200001) * (u64)rt;
>> -       do_div(tmp, 1000000);
>> -       if ((s32)tmp > mrt) {
>> +       s32 range = rt / 5;
>> +       s32 tmp = 2*rt - (s32)(ran\f\fge/2) + (s32)prandom_u32_max(range);
> 
> Here as well.  Honestly the cast on prandom might also not be
> necessary, but that at least has a reason.

The whole thing should go.   How about just doing it all in unsigned:

static inline s32 rfc3315_s14_backoff_init(s32 irt)
{
	/* multiply 'initial retransmission time' by 0.9 .. 1.1 */
	u32 range = irt / 5u;
	return irt - range/2 + prandom_u32_max(range);
}

static inline s32 rfc3315_s14_backoff_update(s32 rt, s32 mrt)
{
	/* multiply 'retransmission timeout' by 1.9 .. 2.1 */
	 u32 range = rt / 5u;
	 u32 tmp = 2u*rt - range/2 + prandom_u32_max(range);
	 if (tmp > mrt) {
		 /* multiply 'maximum retransmission time' by 0.9 .. 1.1 */
		  range = mrt / 5u;
		  tmp = mrt - range/2 + prandom_u32_max(range);
	}
	return tmp;
}

That lets "range/2" be implemented as a 1-bit shift.

An interesting question for the latter is whether
"prandom_u32_max(range) - range/2" can be considered a common
subexpression, or is they have to be *independent* random values.

[RFC PATCH v1 18/50] net/ipv6/addrconf.c: Use prandom_u32_max for rfc3315 backoff time computation

[George Spelvin]

There's no need for 64-bit intermediate values and do_div.

(Actually, the algorithm isn't changing much, except that the old
code used a scaling factor of 1 million.  prandom_u32_max uses
a factor of 2^32, making the final division more efficient.)

One thing that concerns me a bit is that the data types are all
signed.  The old code cast the inputs to unsigned and produced
strange overflowed results if they were negative, so presumably
that never happens in practice.

The new code works the same for positive inputs, but produces
different strange overflowed results if fed negative inputs.

Signed-off-by: George Spelvin <lkml@sdf.org>
Cc: Maciej Żenczykowski <maze@google.com>
Cc: "David S. Miller" <davem@davemloft.net>
Cc: Alexey Kuznetsov <kuznet@ms2.inr.ac.ru>
Cc: Hideaki YOSHIFUJI <yoshfuji@linux-ipv6.org>
Cc: netdev@vger.kernel.org
---
 net/ipv6/addrconf.c | 15 +++++++--------
 1 file changed, 7 insertions(+), 8 deletions(-)

diff --git a/net/ipv6/addrconf.c b/net/ipv6/addrconf.c
index ec3f472bc5a8f..5172f1f874363 100644
--- a/net/ipv6/addrconf.c
+++ b/net/ipv6/addrconf.c
@@ -103,20 +103,19 @@ static inline u32 cstamp_delta(unsigned long cstamp)
 static inline s32 rfc3315_s14_backoff_init(s32 irt)
 {
 	/* multiply 'initial retransmission time' by 0.9 .. 1.1 */
-	u64 tmp = (900000 + prandom_u32() % 200001) * (u64)irt;
-	do_div(tmp, 1000000);
-	return (s32)tmp;
+	s32 range = irt / 5;
+	return irt - (s32)(range/2) + (s32)prandom_u32_max(range);
 }
 
 static inline s32 rfc3315_s14_backoff_update(s32 rt, s32 mrt)
 {
 	/* multiply 'retransmission timeout' by 1.9 .. 2.1 */
-	u64 tmp = (1900000 + prandom_u32() % 200001) * (u64)rt;
-	do_div(tmp, 1000000);
-	if ((s32)tmp > mrt) {
+	s32 range = rt / 5;
+	s32 tmp = 2*rt - (s32)(range/2) + (s32)prandom_u32_max(range);
+	if (tmp > mrt) {
 		/* multiply 'maximum retransmission time' by 0.9 .. 1.1 */
-		tmp = (900000 + prandom_u32() % 200001) * (u64)mrt;
-		do_div(tmp, 1000000);
+		range = mrt / 5;
+		tmp = mrt - (s32)(range/2) + (s32)prandom_u32_max(range);
 	}
 	return (s32)tmp;
 }
-- 
2.26.0