[Dnsmasq-discuss] Why is dnsmasq handing out the same IP to different MACs?

[Paul Smith]

On Tue, 2010-04-13 at 09:22 +0100, Simon Kelley wrote:
> > Is it important to preserve reproducibility in this case?  Would a
> > random number be OK?  In order to ensure good behavior I recommend that
> > we add a random number then, if that's taken, start adding 1 until we
> > find a free spot.
> 
> It's not important to preserve reproducibility in this case, once you
> have collisions you've lost that anyway. What is important is that:
> 
> 1) In the case that there is only one free address, the rehash should
> eventually find it and terminate.
> 
> 2) Even if there are no free addresses, the algorithm should
> terminate.
> 
> 2) can be done by keeping a count of free addresses, but producing
> something amenable to static analysis to prove 1) is difficult.

I don't think so actually: you just add a random number on the first
iteration through the loop, then add 1 every time after that.  You have
to mod by the size of the result set of course, but if you know where to
stop you're guaranteed to walk each address once (with the exception of
the original hash result which you'll hit twice but no big deal).

"Knowing where to stop" can be accomplished by either remembering the
first random address and stopping when you hit it again, or, as you say,
counting how many you've tried.

I think it would be pretty straightforward to implement, looking at the
code, but if you don't think it's worthwhile that's OK too.

-- 
-------------------------------------------------------------------------------
 Paul D. Smith <psmith at gnu.org>          Find some GNU make tips at:
 http://www.gnu.org                      http://make.mad-scientist.net
 "Please remain calm...I may be mad, but I am a professional." --Mad Scientist