Re: [patch] ND_COMPUTER_RTIME is not uniformly distributed

2017-05-29 Thread 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 @@ structllinfo_nd6 {
> > >  #define MIN_RANDOM_FACTOR512 /* 1024 * 0.5 */
> > >  #define MAX_RANDOM_FACTOR1536/* 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).
>

Re: [patch] ND_COMPUTER_RTIME is not uniformly distributed

2017-05-19 Thread Theo Buehler 
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).

Re: [patch] ND_COMPUTER_RTIME is not uniformly distributed

2017-05-15 Thread 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=144947731311613=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   3   /* msec */
>  #define RETRANS_TIMER1000/* msec */
>  #define MIN_RANDOM_FACTOR512 /* 1024 * 0.5 */
>  #define MAX_RANDOM_FACTOR1536/* 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;

Re: [patch] ND_COMPUTER_RTIME is not uniformly distributed

2017-05-15 Thread Mike Belopuhov 
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 @@ structllinfo_nd6 {
>  #define MIN_RANDOM_FACTOR512 /* 1024 * 0.5 */
>  #define MAX_RANDOM_FACTOR1536/* 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 @@ structllinfo_nd6 {
 #define REACHABLE_TIME 3   /* 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;

Re: [patch] ND_COMPUTER_RTIME is not uniformly distributed

2017-05-15 Thread 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 @@ structllinfo_nd6 {
>  #define MIN_RANDOM_FACTOR512 /* 1024 * 0.5 */
>  #define MAX_RANDOM_FACTOR1536/* 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 {

[patch] ND_COMPUTER_RTIME is not uniformly distributed

2017-05-07 Thread 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 {