public inbox for netdev@vger.kernel.org 
 help / color / mirror / Atom feed

From: Pavel Emelyanov <xemul@parallels•com>
To: David Miller <davem@davemloft•net>,
	"eric.dumazet@gmail•com" <eric.dumazet@gmail•com>
Cc: "ebiederm@xmission•com" <ebiederm@xmission•com>,
	"netdev@vger•kernel.org" <netdev@vger•kernel.org>
Subject: Re: [PATCH 1/6] hash: Introduce ptr_hash_mix routine
Date: Tue, 07 Aug 2012 13:11:41 +0400	[thread overview]
Message-ID: <5020DBCD.7040806@parallels.com> (raw)
In-Reply-To: <20120806.134459.954167716448843820.davem@davemloft.net>

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?

Thanks,
Pavel

next prev parent reply	other threads:[~2012-08-07  9:11 UTC|newest]

Thread overview: 28+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2012-08-06 14:13 [PATCH net-next 0/6] Per-net and on-demand link indices (and related) v2 Pavel Emelyanov
2012-08-06 14:13 ` [PATCH 1/6] hash: Introduce ptr_hash_mix routine Pavel Emelyanov
2012-08-06 20:44   ` David Miller
2012-08-07  9:11     ` Pavel Emelyanov [this message]
2012-08-07  9:28       ` Eric Dumazet
2012-08-07  9:55         ` Pavel Emelyanov
2012-08-07 10:30           ` Eric Dumazet
2012-08-07 21:39       ` David Miller
2012-08-06 14:14 ` [PATCH 2/6] net: Dont use ifindices in hash fns Pavel Emelyanov
2012-08-06 14:14 ` [PATCH 3/6] net: Allow to create links with given ifindex Pavel Emelyanov
2012-08-07 11:01   ` [PATCH 2/5 (resend)] " Pavel Emelyanov
2012-08-07 13:14     ` Eric Dumazet
2012-08-07 21:42     ` David Miller
2012-08-06 14:14 ` [PATCH 4/6] veth: Allow to create peer link " Pavel Emelyanov
2012-08-07 11:02   ` [PATCH 3/5 (resend)] " Pavel Emelyanov
2012-08-07 13:14     ` Eric Dumazet
2012-08-07 18:36     ` Ben Hutchings
2012-08-08  9:00       ` Pavel Emelyanov
2012-08-08 13:25         ` Ben Hutchings
2012-08-08 13:38           ` Pavel Emelyanov
2012-08-06 14:14 ` [PATCH 5/6] net: Make ifindex generation per-net namespace Pavel Emelyanov
2012-08-07 11:02   ` [PATCH 4/5 (resend)] " Pavel Emelyanov
2012-08-07 12:11     ` Eric Dumazet
2012-08-07 12:37       ` [PATCH 4/5 (resend)] net: Make ifindex generation per-net namespace (v2) Pavel Emelyanov
2012-08-07 13:13         ` Eric Dumazet
2012-08-06 14:15 ` [PATCH 6/6] net: Loopback ifindex is constant now Pavel Emelyanov
2012-08-07 11:02   ` [PATCH 5/5 (resend)] " Pavel Emelyanov
2012-08-07 13:13     ` Eric Dumazet

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=5020DBCD.7040806@parallels.com \
    --to=xemul@parallels$(echo .)com \
    --cc=davem@davemloft$(echo .)net \
    --cc=ebiederm@xmission$(echo .)com \
    --cc=eric.dumazet@gmail$(echo .)com \
    --cc=netdev@vger$(echo .)kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox