hi,
just FYI, hash was already discussed in a previous thread:
'connection tracking scaling' [19 March 2002]
sorry if you were aware of it.
> > From: "Jean-Michel Hemstedt" <[EMAIL PROTECTED]>
>
> > 98 static inline u_int32_t
> > 99 hash_conntrack(const struct ip_conntrack_tuple *tuple)
> > 100 {
> > 101 #if 0
> > 102 dump_tuple(tuple);
> > 103 #endif
> > 104 /* ntohl because more differences in low bits. */
> > 105 /* To ensure that halves of the same connection don't hash
> > 106 clash, we add the source per-proto again. */
> > 107 return (ntohl(tuple->src.ip + tuple->dst.ip
> > 108 + tuple->src.u.all + tuple->dst.u.all
> > 109 + tuple->dst.protonum)
> > 110 + ntohs(tuple->src.u.all))
> > 111 % ip_conntrack_htable_size;
> > 112 }
>
> A few questions here:
> - Why make the two halves of the connection hash to different buckets?
> I'd think you'd want to consider the two halves to be the same
> connection. So you want them to hash the same. It would make the
> comparison a little more expensive, but save half the space.
and would even avoid a second key computation (modulo may be costly on
prime numbers for instance) and it would also avoid a second collision
list scanning (interresting in case of large number of collisions).
> - % table size seems not quite ideal. Especially since the table size
> is likely a power of 2, which means that you effectively ignore all
> but the low order bits of the addresses and ports.
yes, modulo is slower but more robust than bit masking (&), and
is generally considered a good tradeoff between computation time
and element distribution.
Another common practice consists in bitshifting src and dst
(i.e: ipa+ipa<<20+ipa<<13) to enforce domain LSB variations.
> Perhaps one less than table size if it's even, which will lose the
> use of one bucket but then use all of the data bits in the hash.
> Of course, the low order bits might well be good enough.
> Then again, that depends on what the -per-proto data looks like,
> and for some protos this might not vary in the low order bits.
-jmhe-
