[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