[patch] ND_COMPUTER_RTIME is not uniformly distributed

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

[patch] ND_COMPUTER_RTIME is not uniformly distributed

Matthew Martin
RFC 4861 specifies ReachableTime "should be a uniformly distributed
random value between MIN_RANDOM_FACTOR and MAX_RANDOM_FACTOR times
BaseReachableTime milliseconds." I think the author intended to do the
multiplication by (x>>10) outside the mask, but it's still missing a -1.

- Matthew Martin



diff --git nd6.h nd6.h
index 4274cd4dd07..8eea089a40c 100644
--- nd6.h
+++ nd6.h
@@ -162,8 +162,8 @@ struct llinfo_nd6 {
 #define MIN_RANDOM_FACTOR 512 /* 1024 * 0.5 */
 #define MAX_RANDOM_FACTOR 1536 /* 1024 * 1.5 */
 #define ND_COMPUTE_RTIME(x) \
- (((MIN_RANDOM_FACTOR * (x >> 10)) + (arc4random() & \
- ((MAX_RANDOM_FACTOR - MIN_RANDOM_FACTOR) * (x >> 10)))) /1000)
+ (((arc4random() & (MAX_RANDOM_FACTOR - MIN_RANDOM_FACTOR - 1)) \
+ + MIN_RANDOM_FACTOR) * (x >> 10) / 1000)
 
 TAILQ_HEAD(nd_drhead, nd_defrouter);
 struct nd_defrouter {

Reply | Threaded
Open this post in threaded view
|

Re: [patch] ND_COMPUTER_RTIME is not uniformly distributed

Matthew Martin
ping

On Sun, May 07, 2017 at 06:59:12PM -0500, Matthew Martin wrote:

> RFC 4861 specifies ReachableTime "should be a uniformly distributed
> random value between MIN_RANDOM_FACTOR and MAX_RANDOM_FACTOR times
> BaseReachableTime milliseconds." I think the author intended to do the
> multiplication by (x>>10) outside the mask, but it's still missing a -1.
>
> - Matthew Martin
>
>
>
> diff --git nd6.h nd6.h
> index 4274cd4dd07..8eea089a40c 100644
> --- nd6.h
> +++ nd6.h
> @@ -162,8 +162,8 @@ struct llinfo_nd6 {
>  #define MIN_RANDOM_FACTOR 512 /* 1024 * 0.5 */
>  #define MAX_RANDOM_FACTOR 1536 /* 1024 * 1.5 */
>  #define ND_COMPUTE_RTIME(x) \
> - (((MIN_RANDOM_FACTOR * (x >> 10)) + (arc4random() & \
> - ((MAX_RANDOM_FACTOR - MIN_RANDOM_FACTOR) * (x >> 10)))) /1000)
> + (((arc4random() & (MAX_RANDOM_FACTOR - MIN_RANDOM_FACTOR - 1)) \
> + + MIN_RANDOM_FACTOR) * (x >> 10) / 1000)
>  
>  TAILQ_HEAD(nd_drhead, nd_defrouter);
>  struct nd_defrouter {

Reply | Threaded
Open this post in threaded view
|

Re: [patch] ND_COMPUTER_RTIME is not uniformly distributed

Mike Belopuhov-5
In reply to this post by Matthew Martin
On Sun, May 07, 2017 at 18:59 -0500, Matthew Martin wrote:

> RFC 4861 specifies ReachableTime "should be a uniformly distributed
> random value between MIN_RANDOM_FACTOR and MAX_RANDOM_FACTOR times
> BaseReachableTime milliseconds." I think the author intended to do the
> multiplication by (x>>10) outside the mask, but it's still missing a -1.
>
> - Matthew Martin
>
>
>
> diff --git nd6.h nd6.h
> index 4274cd4dd07..8eea089a40c 100644
> --- nd6.h
> +++ nd6.h
> @@ -162,8 +162,8 @@ struct llinfo_nd6 {
>  #define MIN_RANDOM_FACTOR 512 /* 1024 * 0.5 */
>  #define MAX_RANDOM_FACTOR 1536 /* 1024 * 1.5 */
>  #define ND_COMPUTE_RTIME(x) \
> - (((MIN_RANDOM_FACTOR * (x >> 10)) + (arc4random() & \
> - ((MAX_RANDOM_FACTOR - MIN_RANDOM_FACTOR) * (x >> 10)))) /1000)
> + (((arc4random() & (MAX_RANDOM_FACTOR - MIN_RANDOM_FACTOR - 1)) \
> + + MIN_RANDOM_FACTOR) * (x >> 10) / 1000)
>  
>  TAILQ_HEAD(nd_drhead, nd_defrouter);
>  struct nd_defrouter {
>

Hmm, how about we use an arc4random_uniform here?  It will generate
numbers less than the upper bound specified as an argument so I don't
need to -1 there.

I don't think they wanted to do a multiplication by (x>>10) outside
the mask and in this case as well we want arc4random_uniform to operate
on an extended range.

Does this look good?

diff --git sys/netinet6/nd6.h sys/netinet6/nd6.h
index 4274cd4dd07..01c0fe2c7af 100644
--- sys/netinet6/nd6.h
+++ sys/netinet6/nd6.h
@@ -160,12 +160,12 @@ struct llinfo_nd6 {
 #define REACHABLE_TIME 30000 /* msec */
 #define RETRANS_TIMER 1000 /* msec */
 #define MIN_RANDOM_FACTOR 512 /* 1024 * 0.5 */
 #define MAX_RANDOM_FACTOR 1536 /* 1024 * 1.5 */
 #define ND_COMPUTE_RTIME(x) \
- (((MIN_RANDOM_FACTOR * (x >> 10)) + (arc4random() & \
- ((MAX_RANDOM_FACTOR - MIN_RANDOM_FACTOR) * (x >> 10)))) /1000)
+ ((arc4random_uniform((MAX_RANDOM_FACTOR - MIN_RANDOM_FACTOR) * \
+ (x >> 10)) + MIN_RANDOM_FACTOR * (x >> 10)) / 1000)
 
 TAILQ_HEAD(nd_drhead, nd_defrouter);
 struct nd_defrouter {
  TAILQ_ENTRY(nd_defrouter) dr_entry;
  struct in6_addr rtaddr;

Reply | Threaded
Open this post in threaded view
|

Re: [patch] ND_COMPUTER_RTIME is not uniformly distributed

Matthew Martin
On Mon, May 15, 2017 at 03:49:55PM +0200, Mike Belopuhov wrote:

> On Sun, May 07, 2017 at 18:59 -0500, Matthew Martin wrote:
> > RFC 4861 specifies ReachableTime "should be a uniformly distributed
> > random value between MIN_RANDOM_FACTOR and MAX_RANDOM_FACTOR times
> > BaseReachableTime milliseconds." I think the author intended to do the
> > multiplication by (x>>10) outside the mask, but it's still missing a -1.
> >
> > - Matthew Martin
> >
> >
> >
> > diff --git nd6.h nd6.h
> > index 4274cd4dd07..8eea089a40c 100644
> > --- nd6.h
> > +++ nd6.h
> > @@ -162,8 +162,8 @@ struct llinfo_nd6 {
> >  #define MIN_RANDOM_FACTOR 512 /* 1024 * 0.5 */
> >  #define MAX_RANDOM_FACTOR 1536 /* 1024 * 1.5 */
> >  #define ND_COMPUTE_RTIME(x) \
> > - (((MIN_RANDOM_FACTOR * (x >> 10)) + (arc4random() & \
> > - ((MAX_RANDOM_FACTOR - MIN_RANDOM_FACTOR) * (x >> 10)))) /1000)
> > + (((arc4random() & (MAX_RANDOM_FACTOR - MIN_RANDOM_FACTOR - 1)) \
> > + + MIN_RANDOM_FACTOR) * (x >> 10) / 1000)
> >  
> >  TAILQ_HEAD(nd_drhead, nd_defrouter);
> >  struct nd_defrouter {
> >
>
> Hmm, how about we use an arc4random_uniform here?  It will generate
> numbers less than the upper bound specified as an argument so I don't
> need to -1 there.
>
> I don't think they wanted to do a multiplication by (x>>10) outside
> the mask and in this case as well we want arc4random_uniform to operate
> on an extended range.
>
> Does this look good?

Sure. In the past[1] tb@ had raised concern about using
arc4random_uniform in the kernel since it can loop indefinitely. If
that's not a concern here, the only reason to possibly not go with
arc4random_uniform is for portability with other projects that use the
KAME code which appears to have arc4random but not arc4random_uniform.

1: http://marc.info/?l=openbsd-tech&m=144947731311613&w=2

> diff --git sys/netinet6/nd6.h sys/netinet6/nd6.h
> index 4274cd4dd07..01c0fe2c7af 100644
> --- sys/netinet6/nd6.h
> +++ sys/netinet6/nd6.h
> @@ -160,12 +160,12 @@ struct llinfo_nd6 {
>  #define REACHABLE_TIME 30000 /* msec */
>  #define RETRANS_TIMER 1000 /* msec */
>  #define MIN_RANDOM_FACTOR 512 /* 1024 * 0.5 */
>  #define MAX_RANDOM_FACTOR 1536 /* 1024 * 1.5 */
>  #define ND_COMPUTE_RTIME(x) \
> - (((MIN_RANDOM_FACTOR * (x >> 10)) + (arc4random() & \
> - ((MAX_RANDOM_FACTOR - MIN_RANDOM_FACTOR) * (x >> 10)))) /1000)
> + ((arc4random_uniform((MAX_RANDOM_FACTOR - MIN_RANDOM_FACTOR) * \
> + (x >> 10)) + MIN_RANDOM_FACTOR * (x >> 10)) / 1000)
>  
>  TAILQ_HEAD(nd_drhead, nd_defrouter);
>  struct nd_defrouter {
>   TAILQ_ENTRY(nd_defrouter) dr_entry;
>   struct in6_addr rtaddr;

Reply | Threaded
Open this post in threaded view
|

Re: [patch] ND_COMPUTER_RTIME is not uniformly distributed

Theo Buehler
In reply to this post by Mike Belopuhov-5
On Mon, May 15, 2017 at 03:49:55PM +0200, Mike Belopuhov wrote:

> On Sun, May 07, 2017 at 18:59 -0500, Matthew Martin wrote:
> > RFC 4861 specifies ReachableTime "should be a uniformly distributed
> > random value between MIN_RANDOM_FACTOR and MAX_RANDOM_FACTOR times
> > BaseReachableTime milliseconds." I think the author intended to do the
> > multiplication by (x>>10) outside the mask, but it's still missing a -1.
> >
> > - Matthew Martin
> >
> >
> >
> > diff --git nd6.h nd6.h
> > index 4274cd4dd07..8eea089a40c 100644
> > --- nd6.h
> > +++ nd6.h
> > @@ -162,8 +162,8 @@ struct llinfo_nd6 {
> >  #define MIN_RANDOM_FACTOR 512 /* 1024 * 0.5 */
> >  #define MAX_RANDOM_FACTOR 1536 /* 1024 * 1.5 */
> >  #define ND_COMPUTE_RTIME(x) \
> > - (((MIN_RANDOM_FACTOR * (x >> 10)) + (arc4random() & \
> > - ((MAX_RANDOM_FACTOR - MIN_RANDOM_FACTOR) * (x >> 10)))) /1000)
> > + (((arc4random() & (MAX_RANDOM_FACTOR - MIN_RANDOM_FACTOR - 1)) \
> > + + MIN_RANDOM_FACTOR) * (x >> 10) / 1000)
> >  
> >  TAILQ_HEAD(nd_drhead, nd_defrouter);
> >  struct nd_defrouter {
> >
>
> Hmm, how about we use an arc4random_uniform here?  It will generate
> numbers less than the upper bound specified as an argument so I don't
> need to -1 there.
>
> I don't think they wanted to do a multiplication by (x>>10) outside
> the mask and in this case as well we want arc4random_uniform to operate
> on an extended range.
>
> Does this look good?

Your version is better than what's currently there and would seem to
match the intention of the code as it was written. Sine there was no
objection:

ok tb


However, for whatever that's worth, I initially read the cited passage
the same way as Matthew, but the more I look at it, the more unclear it
becomes what is actually meant. Your interpretation is definitely
possible.

DragonFly, FreeBSD and NetBSD all have versions of what we currently
have, while Linux does something that looks suspiciously like the analog of

        arc4random() % (x >> 10) + (x >> 10).

Reply | Threaded
Open this post in threaded view
|

Re: [patch] ND_COMPUTER_RTIME is not uniformly distributed

Theo Buehler
On Fri, May 19, 2017 at 09:05:38AM +0200, Theo Buehler wrote:

> On Mon, May 15, 2017 at 03:49:55PM +0200, Mike Belopuhov wrote:
> > On Sun, May 07, 2017 at 18:59 -0500, Matthew Martin wrote:
> > > RFC 4861 specifies ReachableTime "should be a uniformly distributed
> > > random value between MIN_RANDOM_FACTOR and MAX_RANDOM_FACTOR times
> > > BaseReachableTime milliseconds." I think the author intended to do the
> > > multiplication by (x>>10) outside the mask, but it's still missing a -1.
> > >
> > > - Matthew Martin
> > >
> > >
> > >
> > > diff --git nd6.h nd6.h
> > > index 4274cd4dd07..8eea089a40c 100644
> > > --- nd6.h
> > > +++ nd6.h
> > > @@ -162,8 +162,8 @@ struct llinfo_nd6 {
> > >  #define MIN_RANDOM_FACTOR 512 /* 1024 * 0.5 */
> > >  #define MAX_RANDOM_FACTOR 1536 /* 1024 * 1.5 */
> > >  #define ND_COMPUTE_RTIME(x) \
> > > - (((MIN_RANDOM_FACTOR * (x >> 10)) + (arc4random() & \
> > > - ((MAX_RANDOM_FACTOR - MIN_RANDOM_FACTOR) * (x >> 10)))) /1000)
> > > + (((arc4random() & (MAX_RANDOM_FACTOR - MIN_RANDOM_FACTOR - 1)) \
> > > + + MIN_RANDOM_FACTOR) * (x >> 10) / 1000)
> > >  
> > >  TAILQ_HEAD(nd_drhead, nd_defrouter);
> > >  struct nd_defrouter {
> > >
> >
> > Hmm, how about we use an arc4random_uniform here?  It will generate
> > numbers less than the upper bound specified as an argument so I don't
> > need to -1 there.
> >
> > I don't think they wanted to do a multiplication by (x>>10) outside
> > the mask and in this case as well we want arc4random_uniform to operate
> > on an extended range.
> >
> > Does this look good?
>
> Your version is better than what's currently there and would seem to
> match the intention of the code as it was written. Sine there was no
> objection:
>
> ok tb

Are you going to commit this or should I?

>
>
> However, for whatever that's worth, I initially read the cited passage
> the same way as Matthew, but the more I look at it, the more unclear it
> becomes what is actually meant. Your interpretation is definitely
> possible.
>
> DragonFly, FreeBSD and NetBSD all have versions of what we currently
> have, while Linux does something that looks suspiciously like the analog of
>
> arc4random() % (x >> 10) + (x >> 10).
>