Hello,
In a transport protocol I'm implementing, I've adapted this TCP hashing
function:
static __inline__ int dcp_hashfn(__u32 laddr, __u16 lport,
__u32 faddr, __u16 fport)
{
int h = ((laddr ^ lport) ^ (faddr ^ fport));
h ^= h>>16;
h ^= h>>8;
/* make it always < size : */
return h & (MY_HTABLE_SIZE - 1); /* MY_HT... = 128 */
}
Although I am treating it as a blackbox and it works fine for me, my
professor pointed the following about this function:
[...]
If both IP addresses have the same upper 16 bits (like 155.246.10.5 and
155.246.120.30), then the 1st 4-way XOR will put 16 bits of zero in h.
Then "h ^= h>>16" will preserve the upper 16 bits as zero. Then
"h ^= h>>8" will preserve the upper 24 bits!
[...]
Also, he says:
[...]
Having the same class B network number seems like a common case. In
that case, I don't see much difference between doing the last two
XORs and leaving them out.
[...]
It is indeed true that in mentioned case one will end up with many zeros.
Does it mean this function is in-efficient? Having many sockets linked to
the same hash entry means long lookups... Or is there another reason for
this function being implemented this way?
What are yours opinions?
-marek
On Thu, Mar 28, 2002 at 08:11:27PM -0500, Marek Zawadzki wrote:
> Hello,
Hello. Please leave the mailing list you're posting to
in the To: field of your message.
> In a transport protocol I'm implementing, I've adapted this TCP hashing
> function:
>
> static __inline__ int dcp_hashfn(__u32 laddr, __u16 lport,
> __u32 faddr, __u16 fport)
> {
> int h = ((laddr ^ lport) ^ (faddr ^ fport));
> h ^= h>>16;
> h ^= h>>8;
> /* make it always < size : */
> return h & (MY_HTABLE_SIZE - 1); /* MY_HT... = 128 */
> }
>
> Although I am treating it as a blackbox and it works fine for me, my
> professor pointed the following about this function:
If you're a student, you should probably try to figure
this out for yourself; it's the only way to learn.
> [...]
> If both IP addresses have the same upper 16 bits (like 155.246.10.5 and
> 155.246.120.30), then the 1st 4-way XOR will put 16 bits of zero in h.
> Then "h ^= h>>16" will preserve the upper 16 bits as zero. Then
> "h ^= h>>8" will preserve the upper 24 bits!
> [...]
This comment makes an assumption about the architecture
of the machine, and the way IP addresses are stored
into __u32s.
Consider the following code fragment:
printf("%x %x\n",
inet_addr("1.0.0.0"),
inet_addr("0.0.0.1"));
-neil
On Fri, Mar 29, 2002 at 12:08:18AM -0800, Neil Spring wrote:
> On Thu, Mar 28, 2002 at 08:11:27PM -0500, Marek Zawadzki wrote:
> > Hello,
>
> > static __inline__ int dcp_hashfn(__u32 laddr, __u16 lport,
> > __u32 faddr, __u16 fport)
> > {
> > int h = ((laddr ^ lport) ^ (faddr ^ fport));
> > h ^= h>>16;
> > h ^= h>>8;
> > /* make it always < size : */
> > return h & (MY_HTABLE_SIZE - 1); /* MY_HT... = 128 */
> > }
> >
> > Although I am treating it as a blackbox and it works fine for me, my
> > professor pointed the following about this function:
>
> If you're a student, you should probably try to figure
> this out for yourself; it's the only way to learn.
Add one to the homework on the list tally.
> > If both IP addresses have the same upper 16 bits (like 155.246.10.5 and
> > 155.246.120.30), then the 1st 4-way XOR will put 16 bits of zero in h.
> > Then "h ^= h>>16" will preserve the upper 16 bits as zero. Then
> > "h ^= h>>8" will preserve the upper 24 bits!
> > [...]
Look at the size and see why it doesn't matter.