netdev - Re: [PATCH 1/6] hash: Introduce ptr_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:	Tue, 07 Aug 2012 13:11:41 +0400
From:	Pavel Emelyanov <xemul@...allels.com>
To:	David Miller <davem@...emloft.net>,
	"eric.dumazet@...il.com" <eric.dumazet@...il.com>
CC:	"ebiederm@...ssion.com" <ebiederm@...ssion.com>,
	"netdev@...r.kernel.org" <netdev@...r.kernel.org>
Subject: Re: [PATCH 1/6] hash: Introduce ptr_hash_mix routine

On 08/07/2012 12:44 AM, David Miller wrote:
> From: Pavel Emelyanov <xemul@...allels.com>
> Date: Mon, 06 Aug 2012 18:13:47 +0400
> 
>> @@ -67,4 +68,13 @@ static inline unsigned long hash_ptr(const void *ptr, unsigned int bits)
>>  {
>>  	return hash_long((unsigned long)ptr, bits);
>>  }
>> +
>> +static inline u32 ptr_hash_mix(const void *ptr)
>> +{
>> +#if BITS_PER_LONG == 32
>> +	return (u32)(unsigned long)ptr;
>> +#else
>> +	return (u32)((unsigned long)ptr >> L1_CACHE_SHIFT);
>> +#endif
>> +}
>>  #endif /* _LINUX_HASH_H */
> 
> This doesn't make much sense to me.
> 
> If the whole 32-bits of the pointer is useful for entropy on 32-bit
> why isn't the whole 64-bits useful on 64-bit?
> 
> I would, instead, expect something like:
> 
> 	ptr ^ (ptr >> 32)
> 
> for the 64-bit case.
> 
> Also, that L1_CACHE_SHIFT is something callers can decide to do.
> 
> Only they know the size of their structure, the alignment used to
> allocate such objects, and thus what bits are "less relevant" and
> therefore profitable to elide from the bottom of the value.
> .

Maybe it would be better to change the way neigh_table->hash work more
significantly then? Currently it is used like

	hash = tbl->hash(key, dev, tbl->rnd);
	hash >>= (32 - tbl->hash_shift);

i.e. the caller asks for u32 hash value and then trims some lower bits.
It can be changed like

	hash = tbl->hash(key, dev, tbl->rnd, tbl->hash_shift);

making the hash fn trim the bits itself. This will allow us to use the
existing (declared to be proven to be effective) hash_ptr() routine for
the net_device pointer hashing (it requires the number of bits to use).

E.g. the arp hash might look like

static u32 arp_hashfn(u32 key, struct net_device *dev, u32 hash_rnd,
		unsigned int bits)
{
	return hash_ptr(dev, bits) ^ hash_32(key * hash_rnd, bits);
}

and the ndisc one like

static u32 ndisc_hashfn(u32 *pkey, struct net_device *dev, u32 *hash_rnd,
		unsigned int bits)
{
	return hash_ptr(dev, bits) ^
		hash_32(key[0] * hash_rnd[0], bits) ^
		hash_32(key[1] * hash_rnd[1], bits) ^
		hash_32(key[2] * hash_rnd[2], bits) ^
		hash_32(key[3] * hash_rnd[3], bits);
}

What do you think?

Thanks,
Pavel
--
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