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

Simon Kelley simon at thekelleys.org.uk
Tue Apr 13 09:27:41 BST 2010


Paul Smith wrote:
> On Mon, 2010-04-12 at 19:13 -0400, Paul Smith wrote:
>> But, on my test of 192 MACs, the sdbm hash function worked perfectly: I
>> got 192 unique IP address offsets.  Funnily enough of all the hash
>> functions this one is closest in concept to your current one... but it
>> uses shifts of 6 bits and 16 bits (plus a subtract) instead of 8 and 16.
>>
>> I'll send a patch later tonight so you can see it. 
> 
> Patch is below (not sure if you prefer an attachment or not; let me know
> if so).  You can find this algorithm by searching for SDBM hash.
> 
> I was looking into fixing up the collision handling algorithm as well.
> 
> --- dnsmasq-2.52/src/dhcp.c	2010-01-15 05:13:49.000000000 -0500
> +++ dnsmasq/src/dhcp.c	2010-04-13 02:08:13.002012929 -0400
> @@ -559,9 +559,10 @@
>    int i, pass;
>    unsigned int j; 
>  
> -  /* hash hwaddr */
> +  /* hash hwaddr: use the SDBM hashing algorithm.  Seems to give good
> +     dispersal even with similarly-valued "strings". */
>    for (j = 0, i = 0; i < hw_len; i++)
> -    j += hwaddr[i] + (hwaddr[i] << 8) + (hwaddr[i] << 16);
> +    j += hwaddr[i] + (j << 6) + (j << 16) - j;
>    
>    for (pass = 0; pass <= 1; pass++)
>      for (c = context; c; c = c->current)
> 

That looks good. I Googled "SDBM hash" and found this:

http://www.cse.yorku.ca/~oz/hash.html

which also tells me that my original function is called "lose lose". I'm
suitably chastised!

Patch applied.

Simon.






More information about the Dnsmasq-discuss mailing list