diff mbox

[v4,5/7] ipv6 addrconf: implement RFC7559 router solicitation backoff

Message ID 1474801390-6891-6-git-send-email-zenczykowski@gmail.com
State Superseded, archived
Delegated to: David Miller
Headers show

Commit Message

Maciej Żenczykowski Sept. 25, 2016, 11:03 a.m. UTC 
From: Maciej Żenczykowski <maze@google.com>

This implements:
  https://tools.ietf.org/html/rfc7559

Backoff is performed according to RFC3315 section 14:
  https://tools.ietf.org/html/rfc3315#section-14

Signed-off-by: Maciej Żenczykowski <maze@google.com>
---
 include/net/if_inet6.h |  1 +
 net/ipv6/addrconf.c    | 31 +++++++++++++++++++++++++++----
 2 files changed, 28 insertions(+), 4 deletions(-)

Comments

Hannes Frederic Sowa Sept. 26, 2016, 1:53 p.m. UTC | #1 
On 25.09.2016 13:03, Maciej Żenczykowski wrote:
> +static inline s32 rfc3315_s14_backoff_init(s32 initial)
> +{
> +	u32 r = (9 << 20) / 10 + (prandom_u32() % ((2 << 20) / 10 + 1));

^

> +	s32 v = initial * (u64)r >> 20;       /* ~ multiply by 0.9 .. 1.1 */
> +	return v;
> +}
> +
> +static inline s32 rfc3315_s14_backoff_update(s32 cur, s32 ceiling)
> +{
> +	u32 r = (19 << 20) / 10 + (prandom_u32() % ((2 << 20) / 10 + 1));

Please just use do_div here and go back to the first version of the
patch. Variable names could be more aligned with the RFC maybe?

> +	s32 v = cur * (u64)r >> 20;           /* ~ multiply by 1.9 .. 2.1 */
> +	if (v > ceiling) {
> +		r -= 1 << 20;
> +		v = ceiling * (u64)r >> 20;   /* ~ multiply by 0.9 .. 1.1 */
> +	}
> +	return v;
> +}

Thanks,
Hannes
Maciej Żenczykowski Sept. 27, 2016, 9:42 a.m. UTC | #2 
> Please just use do_div here and go back to the first version of the
> patch. Variable names could be more aligned with the RFC maybe?

So I tried:

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;
 }

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) {
               /* multiply 'maximum retransmission time' by 0.9 .. 1.1 */
               tmp = (900000 + prandom_u32() % 200001) * (u64)mrt;
               do_div(tmp, 1000000);
        }
       return (s32)tmp;
}

but then building for i386 I get:

ERROR: "__udivdi3" [net/netfilter/xt_hashlimit.ko] undefined!

which happens even at net-next/master itself.

Anyway, I'll resubmit assuming the above is what you're looking for...
Maciej Żenczykowski Sept. 27, 2016, 9:52 a.m. UTC | #3 
Hi,

This patch series implements RFC7559 style backoff of IPv6 router
solicitation requests.

Patches 1 and 2 are minor cleanup and stand on their own.

Patch 3 allows a (potentially) infinite number of RS'es to be sent
when the rtr_solicits sysctl is set to -1 (this depends on patch 1).

Patch 4 is just boilerplate to add a new sysctl for the maximum
backoff period.

Patch 5 implements the backoff algorithm (and depends on the previous
patches).

Patches 6 and 7 switch the defaults over to enable this by default
(defaults come from the RFC).

[PATCH v5 1/7] ipv6 addrconf: enable use of proc_dointvec_minmax in
[PATCH v5 2/7] ipv6 addrconf: remove addrconf_sysctl_hop_limit()
[PATCH v5 3/7] ipv6 addrconf: rtr_solicits == -1 means unlimited
[PATCH v5 4/7] ipv6 addrconf: add new sysctl
[PATCH v5 5/7] ipv6 addrconf: implement RFC7559 router solicitation
[PATCH v5 6/7] ipv6 addrconf: change default
[PATCH v5 7/7] ipv6 addrconf: change default MAX_RTR_SOLICITATIONS

Changes v4->v5:
  added 'const' qualifier to extra1/2 constants - requires (void*) casting
  switched away from shifts by 20 to do_div(..., 1000000)
  switched to variable names from the rfc, elaborated a bit in the comments

Changes v3->v4:
  added subject line to cover letter

Changes v2->v3:
  added cover letter

Changes v1->v2:
  avoid 64-bit divisions to fix 32-bit build errors
Hannes Frederic Sowa Sept. 27, 2016, 9:58 a.m. UTC | #4 
On 27.09.2016 11:42, Maciej Żenczykowski wrote:
>> Please just use do_div here and go back to the first version of the
>> patch. Variable names could be more aligned with the RFC maybe?
> 
> So I tried:
> 
> 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;
>  }
> 
> 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) {
>                /* multiply 'maximum retransmission time' by 0.9 .. 1.1 */
>                tmp = (900000 + prandom_u32() % 200001) * (u64)mrt;
>                do_div(tmp, 1000000);
>         }
>        return (s32)tmp;
> }
> 
> but then building for i386 I get:
> 
> ERROR: "__udivdi3" [net/netfilter/xt_hashlimit.ko] undefined!
> 
> which happens even at net-next/master itself.
> 
> Anyway, I'll resubmit assuming the above is what you're looking for...

I think the __udivdi3 comes from the fact you are doing the modulo
operation and the reciprocal divide optimization doesn't work in this
case thus you end up with the call to libgcc.

Can you use the remainder from the do_div operation also?

u32 r = prandom_u32();
u64 tmp = (900000 + do_div(r,200001)) * (u64)irt;

Depending on if you keep the values in ms or jiffies, maybe it would
make sense to simply use msecs_to_jiffies and vice versa?

Thanks,
Hannes
Hannes Frederic Sowa Sept. 27, 2016, 10:20 a.m. UTC | #5 
[cc Vishwanath Pai]

On 27.09.2016 11:42, Maciej Żenczykowski wrote:
>> Please just use do_div here and go back to the first version of the
>> patch. Variable names could be more aligned with the RFC maybe?
> 
> So I tried:
> 
> 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;
>  }
> 
> 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) {
>                /* multiply 'maximum retransmission time' by 0.9 .. 1.1 */
>                tmp = (900000 + prandom_u32() % 200001) * (u64)mrt;
>                do_div(tmp, 1000000);
>         }
>        return (s32)tmp;
> }
> 
> but then building for i386 I get:
> 
> ERROR: "__udivdi3" [net/netfilter/xt_hashlimit.ko] undefined!

Hmm, evidently we have some u64 divisions in xt_hashlimit.c which should
be replaced by do_div?
diff mbox

Patch

diff --git a/include/net/if_inet6.h b/include/net/if_inet6.h
index 1c8b6820b694..515352c6280a 100644
--- a/include/net/if_inet6.h
+++ b/include/net/if_inet6.h
@@ -201,6 +201,7 @@  struct inet6_dev {
 	struct ipv6_devstat	stats;
 
 	struct timer_list	rs_timer;
+	__s32			rs_interval;	/* in jiffies */
 	__u8			rs_probes;
 
 	__u8			addr_gen_mode;
diff --git a/net/ipv6/addrconf.c b/net/ipv6/addrconf.c
index 255be34cdbce..6384a1cde056 100644
--- a/net/ipv6/addrconf.c
+++ b/net/ipv6/addrconf.c
@@ -112,6 +112,24 @@  static inline u32 cstamp_delta(unsigned long cstamp)
 	return (cstamp - INITIAL_JIFFIES) * 100UL / HZ;
 }
 
+static inline s32 rfc3315_s14_backoff_init(s32 initial)
+{
+	u32 r = (9 << 20) / 10 + (prandom_u32() % ((2 << 20) / 10 + 1));
+	s32 v = initial * (u64)r >> 20;       /* ~ multiply by 0.9 .. 1.1 */
+	return v;
+}
+
+static inline s32 rfc3315_s14_backoff_update(s32 cur, s32 ceiling)
+{
+	u32 r = (19 << 20) / 10 + (prandom_u32() % ((2 << 20) / 10 + 1));
+	s32 v = cur * (u64)r >> 20;           /* ~ multiply by 1.9 .. 2.1 */
+	if (v > ceiling) {
+		r -= 1 << 20;
+		v = ceiling * (u64)r >> 20;   /* ~ multiply by 0.9 .. 1.1 */
+	}
+	return v;
+}
+
 #ifdef CONFIG_SYSCTL
 static int addrconf_sysctl_register(struct inet6_dev *idev);
 static void addrconf_sysctl_unregister(struct inet6_dev *idev);
@@ -3698,11 +3716,13 @@  static void addrconf_rs_timer(unsigned long data)
 			goto put;
 
 		write_lock(&idev->lock);
+		idev->rs_interval = rfc3315_s14_backoff_update(
+			idev->rs_interval, idev->cnf.rtr_solicit_max_interval);
 		/* The wait after the last probe can be shorter */
 		addrconf_mod_rs_timer(idev, (idev->rs_probes ==
 					     idev->cnf.rtr_solicits) ?
 				      idev->cnf.rtr_solicit_delay :
-				      idev->cnf.rtr_solicit_interval);
+				      idev->rs_interval);
 	} else {
 		/*
 		 * Note: we do not support deprecated "all on-link"
@@ -3973,10 +3993,11 @@  static void addrconf_dad_completed(struct inet6_ifaddr *ifp)
 
 		write_lock_bh(&ifp->idev->lock);
 		spin_lock(&ifp->lock);
+		ifp->idev->rs_interval = rfc3315_s14_backoff_init(
+			ifp->idev->cnf.rtr_solicit_interval);
 		ifp->idev->rs_probes = 1;
 		ifp->idev->if_flags |= IF_RS_SENT;
-		addrconf_mod_rs_timer(ifp->idev,
-				      ifp->idev->cnf.rtr_solicit_interval);
+		addrconf_mod_rs_timer(ifp->idev, ifp->idev->rs_interval);
 		spin_unlock(&ifp->lock);
 		write_unlock_bh(&ifp->idev->lock);
 	}
@@ -5132,8 +5153,10 @@  update_lft:
 
 	if (update_rs) {
 		idev->if_flags |= IF_RS_SENT;
+		idev->rs_interval = rfc3315_s14_backoff_init(
+			idev->cnf.rtr_solicit_interval);
 		idev->rs_probes = 1;
-		addrconf_mod_rs_timer(idev, idev->cnf.rtr_solicit_interval);
+		addrconf_mod_rs_timer(idev, idev->rs_interval);
 	}
 
 	/* Well, that's kinda nasty ... */