Re: [PATCH 1/6] hash: Introduce ptr_hash_mix routine

[Eric Dumazet <eric.dumazet@gmail.com>]

On Tue, 2012-08-07 at 13:11 +0400, Pavel Emelyanov wrote:
> On 08/07/2012 12:44 AM, David Miller wrote:
> > From: Pavel Emelyanov <xemul@parallels.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?

I think we should avoid hash_ptr() because its quite expensive

David suggested to not use the L1_CACHE_SHIFT and instead do a plain :

static inline u32 ptr_hash_mix(const void *ptr)
{
	unsigned long val = (unsigned long)ptr;

#if BITS_PER_LONG == 64
	val ^= (val >> 32);
#endif
	return (u32)val;
}

By the way we could name this hash32_ptr() instead of ptr_hash_mix()