netdev - Re: [NETFILTER] xt_hashlimit : speedups hash

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Sat, 15 Dec 2007 11:41:41 +0100
From:	Jarek Poplawski <jarkao2@...il.com>
To:	Eric Dumazet <dada1@...mosbay.com>
CC:	Patrick McHardy <kaber@...sh.net>, netfilter-devel@...r.kernel.org,
	netdev@...r.kernel.org
Subject: Re: [NETFILTER] xt_hashlimit : speedups hash_dst()

Eric Dumazet wrote, On 12/14/2007 10:37 PM:

> Jarek Poplawski a écrit :
>> Eric Dumazet wrote, On 12/14/2007 12:09 PM:
>> ...
>>
>>> +	/*
>>> +	 * Instead of returning hash % ht->cfg.size (implying a divide)
>>> +	 * we return the high 32 bits of the (hash * ht->cfg.size) that will
>>> +	 * give results between [0 and cfg.size-1] and same hash distribution,
>>> +	 * but using a multiply, less expensive than a divide
>>> +	 */
>>> +	return ((u64)hash * ht->cfg.size) >> 32;
>> Are we sure of the same hash distribution? Probably I miss something,
>> but: if this 'hash' is well distributed on 32 bits, and ht->cfg.size
>> is smaller than 32 bits, e.g. 256 (8 bits), then this multiplication
>> moves to the higher 32 of u64 only max. 8 bits of the most significant
>> byte, and the other three bytes are never used, while division is
>> always affected by all four bytes...
> 
> Not sure what you are saying... but if size=256, then, yes, we want a final 
> result between 0 and 255, so three bytes are nul.

Eric, it would be nice to acknowledge David's suggestion that this hash
size is always power of two here, because otherwise at least your words
about the same hash distribution according to the "%" variant could be
wrong (but I don't say the final result would be wrong). Maybe I mix
up these sizes, but it seems this could be set by a user, and I didn't
find anything about this power of two necessity?

Regards,
Jarek P.
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html