Skip to contentSkip to conversation

cttest-0.3 (conntrack hashing)

DISCUSSION Don Cohen 2 participants 2 messages Jul 9, 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 10 lines

From: Patrick Schaaf <[email protected]>
static u32 hash_abcd_host(struct ct_key *key)

{
        u32 res;

PER_HASH_TIMER_1(
res = 0x47441DFB * ntohl(key->sip)
+ 0x57655A7D * ntohl(key->dip)
+ 0x1C7F1D2D * ntohs(key->sport)
+ 0xDF91D738 * ntohs(key->dport)
+ key->proto;

Quoted 6 lines
);
        return res;
}

Slightly surprising, this code runs about half as fast as the normal abcd, on my little endian box.

I guess that shows that the ntohl/s's take about as much time as the rest.

Quoted 2 lines

Now there is http://bei.bof.de/cttest-0.5.tar.gz and an example presentation at http://bei.bof.de/ex4/

(Is this getting out of hand?)

Quoted 2 lines

BTW, it should be possible to gather reports generated by different people

...

I suggest that you collect up their original data sets so other people can experiment with those.

And finally, here's the current version of A-F which I am determined to make my LAST version. This is the result of a little more communication with my friendly crypto expert.

/* for 32866 entries table size: length of longest bucket

     256:158 512:89 1K:49 2K:30 4K:21 8K:13 16K:10 32K:8 64K:6 256K:4 */
  unsigned long long ls, ld, lp;
  long sum;
  ls = (unsigned long long) key->sip * A;
  ld = (unsigned long long) key->dip * B;
  lp = (unsigned long long) C * (u32)((u32)(key->sport << 16) + key->dport);
  sum = 
    (ls ^ (ls >> 32) +
     ld ^ (ld >> 32) +
     lp ^ (lp >> 32) +
     E * key->proto) ^ F;

return sum;

Quoted 4 lines

As nobody requested the tarball yet, I've remade it with the latest 64 bit ABCDEF code from Don. I also remade the ex4/ pictures, in the abcd series, Don's new hash is named abcd_long. Looks good, takes about 2.2 times as long as abcd.

(Darn. So 64 bit does take a lot longer.)

Quoted 1 line

I call it a night now. Take care.

Me too.

#2 lore raw
Quoted 4 lines
Quoted 2 lines

Now there is http://bei.bof.de/cttest-0.5.tar.gz and an example presentation at http://bei.bof.de/ex4/

(Is this getting out of hand?)

In what way? I'm having fun.

Quoted 6 lines
Quoted 2 lines

BTW, it should be possible to gather reports generated by different people

...

I suggest that you collect up their original data sets so other people can experiment with those.

I wouldn't want anybody else to look at my real datasets - they reflect business situations no outsider has got to see too closely. This is even true for the "mangled" dataset - one could guess to much from them, _and_ they modify the very bits we are trying to analyse.

However, if anybody wants to send me their real datasets, I will happily put them up for download and re-analysis. I'll add notes to this end when I ask the user mailing list.

Quoted 3 lines

And finally, here's the current version of A-F which I am determined to make my LAST version. This is the result of a little more communication with my friendly crypto expert.

Thank you! Will try out and incorporate.

If we go with one of these for the base kernel, could you, together with your friendly crypto buff, make a little documentary writeup on the properties of the finally selected algorithm? Something that would stand up to reading by other experts in the field?

Quoted 4 lines
Quoted 2 lines

Don's new hash is named abcd_long. Looks good,
takes about 2.2 times as long as abcd.

(Darn. So 64 bit does take a lot longer.)

That's not surprising; on 32 bit machines, 64 bit arithmetic tends to be a blob of unfollowable large code. The original abcd hash, compiled march=i686, takes about 64 byte in instruction size. The 64 bit variant takes over 256 byte.

But I wouldn't worry too much about that. The measured times for all of the pure calculating hashes are so small compared to the rest of the action around them, that the relative differences won't matter in reality. Also, with the recent ip_conntrack_core patch I sent to the list, I saved two hash calculations - so we have a 3x cost increase to the hash function for free :-)

On 64 bit machines, which will become more common over the Linux 2.6 timeframe, the difference goes away.

best regards
Patrick