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

On Tue, 2012-08-07 at 13:11 +0400, Pavel Emelyanov wrote:

On 08/07/2012 12:44 AM, David Miller wrote:

quoted

From: Pavel Emelyanov <redacted>
Date: Mon, 06 Aug 2012 18:13:47 +0400

quoted

@@ -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()