Skip to contentSkip to conversation

conntrack hash function

DISCUSSION Don Cohen 3 participants 3 messages Jun 25, 2002 – Jul 5, 2002 1 message not in the archive netfilter

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

Don Cohen

author
#1 lore raw
Quoted 17 lines

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.
- % 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.
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.

#2 lore raw

hi,

just FYI, hash was already discussed in a previous thread:
'connection tracking scaling' [19 March 2002] sorry if you were aware of it.

Quoted 18 lines
Quoted 17 lines

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 }

Quoted 5 lines

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).

Quoted 3 lines

- % 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.

Quoted 5 lines

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-

#3 lore raw
In reply to Don Cohen
Quoted 5 lines · Don Cohen

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.

so what happens in case of NAT? The tuples are not the same in this case...

Signature · 5 lines
Live long and prosper
- Harald Welte / [email protected]               http://www.gnumonks.org/
============================================================================
GCS/E/IT d- s-: a-- C+++ UL++++$ P+++ L++++$ E--- W- N++ o? K- w--- O- M- 
V-- PS+ PE-- Y+ PGP++ t++ 5-- !X !R tv-- b+++ DI? !D G+ e* h+ r% y+(*)