Hi all,
here is the next version of my cttest.c conntrack test program.
Thanks go to Don Cohen for noticing that my parser was fucked up.
I did not notice that we sometimes have the [XXX] state marker
between the two tuples, and sometimes we have it after both tuples.
How ugly... This is now fixed by skipping a field when the second
tuple starts with '['.
Incidentally, the occasional overly long chains (140 entry lists etc.)
are now gone gone gone. They were an artifact of the misparsing...
A small fix I also did, was to (correctly) parse the ports into network
byte order. Now the "original" hash function should really match what's
in the kernel.
We now see a nice "spread" of list lengths for both the original hash
function, as well as the crc32 one, without strange outliers. For my
bucket count of 7168 (default for a 1GB RAM non-highmem machine...),
the original hash is still much worse than the crc32 one.
At this point, I implemented some new options to the cttest program:
Use the new '-P' flag (no arguments) to automatically choose a prime
number of hash buckets, just a bit larger than the number you selected
with '-s NUMBER'. When I do that, the large difference between the
original and crc32 hashes almost vanishes - sometimes our original
hash even looks _better_ (by chance)! This is a strong indication
that we want the "prime select" in the kernel!
You can now use '-c NUMBER' to set a seed for the CRC32 hash. You can now
use '-C' (without parameter) to set a random seed for the CRC32 hash.
These options are for testing the idea of "attack compensation by
inserting local variance". I'd like to hear opinions on this.
best regards
Patrick
/* cttest.c - parse /proc/net/ip_conntrack, compute bucket occupation
*
* This is how lines look:
*
* udp 17 0 src=213.6.73.215 dst=62.104.191.241 sport=1858 dport=53
src=62.104.191.241 dst=213.6.73.215 sport=53 dport=1858 use=1
* tcp 6 114 TIME_WAIT src=62.104.211.64 dst=212.7.144.66 sport=34685 dport=80
src=212.7.144.66 dst=62.104.211.64 sport=80 dport=34685 [ASSURED] use=1
*/
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
#include <getopt.h>
#include <errno.h>
#include <time.h>
#include <netinet/in.h>
#include <arpa/inet.h>
typedef unsigned long u32;
typedef unsigned short u16;
typedef unsigned char u8;
struct ct_key {
u32 sip;
u32 dip;
u16 sport;
u16 dport;
u8 proto;
};
static u32 hash_conntrack(struct ct_key *key)
{
return ntohl(key->sip + key->dip
+ key->sport + key->dport
+ key->proto)
+ ntohs(key->sport);
}
#include "crc32.c"
static u32 crc32_seed;
static u32 hash_crc32(struct ct_key *key)
{
u32 crc = crc32_seed;
u32 v32;
u16 v16;
crc = crc32(crc, (const char *) &key->proto, sizeof(key->proto));
v32 = ntohl(key->sip);
crc = crc32(crc, (const char *) &v32, sizeof(v32));
v32 = ntohl(key->dip);
crc = crc32(crc, (const char *) &v32, sizeof(v32));
v16 = ntohs(key->sport);
crc = crc32(crc, (const char *) &v16, sizeof(v16));
v16 = ntohs(key->dport);
crc = crc32(crc, (const char *) &v16, sizeof(v16));
return crc;
}
static u32 hash_random(struct ct_key *key)
{
return (u32) random();
}
struct hash_def {
char *name;
u32 (*hash_f)(struct ct_key *);
};
#define NR_HASHES (sizeof(hashes)/sizeof(hashes[0]))
static struct hash_def hashes[] = {
{ "original", hash_conntrack },
{ "random", hash_random },
{ "crc32", hash_crc32 },
};
static u32 htable_size = 7168;
static u32 *occupation;
static struct hash_def *test_hash = hashes;
static void do_init(void)
{
u32 idx;
occupation = malloc(sizeof(*occupation) * htable_size);
for (idx=0; idx<htable_size; idx++)
occupation[idx] = 0;
}
static int display_target = -1;
static int do_count(struct ct_key *key)
{
u32 idx = test_hash->hash_f(key) % htable_size;
occupation[idx]++;
return ((int)idx) == display_target;
}
static u32 parse_ip(char *t)
{
char *p = strchr(t, '=');
if (!p++) return 0;
return inet_addr(p);
}
static u16 parse_port(char *t)
{
char *p = strchr(t, '=');
if (!p++) return 0;
return htons((u16) strtoul(p, 0, 10));
}
static u32 ignore_tcp_timeout_bound = 0;
static int ignore_by_timeout(struct ct_key *key, char *tok)
{
return key->proto == 6
&& strtoul(tok, 0, 10) < ignore_tcp_timeout_bound;
}
static int unidir;
static int process(char *p)
{
struct ct_key key[1];
char *tok;
int res;
strtok(p, " \t\n"); /* prot text */
tok = strtok(0, " \t\n");
key->proto = (u8) strtoul(tok, 0, 10); /* prot num */
tok = strtok(0, " \t\n"); /* timeout */
if (ignore_by_timeout(key, tok)) return 0;
switch (key->proto) {
case 6: strtok(0, " \t\n"); /* tcp state */
case 17: break;
default: return 0;
}
/* forward */
tok = strtok(0, " \t\n"); key->sip = parse_ip(tok); /* src ip */
tok = strtok(0, " \t\n"); key->dip = parse_ip(tok); /* dst ip */
tok = strtok(0, " \t\n"); key->sport = parse_port(tok); /* src port */
tok = strtok(0, " \t\n"); key->dport = parse_port(tok); /* dst port */
res = do_count(key);
if (unidir) return res;
/* reverse */
tok = strtok(0, " \t\n");
if (*tok == '[') tok = strtok(0, " \t\n");
key->sip = parse_ip(tok); /* src ip */
tok = strtok(0, " \t\n"); key->dip = parse_ip(tok); /* dst ip */
tok = strtok(0, " \t\n"); key->sport = parse_port(tok); /* src port */
tok = strtok(0, " \t\n"); key->dport = parse_port(tok); /* dst port */
return res | do_count(key);
}
static int occupation_target = -1;
static void show_occupation(void)
{
u32 idx, maxlen, total, partial, *agg;
for (maxlen=0, total=0, idx=0; idx<htable_size; idx++) {
total += occupation[idx];
if (occupation[idx] > maxlen)
maxlen = occupation[idx];
}
printf("maximum bucket list length: %lu\n", maxlen);
printf("total number of entries: %lu\n", total);
agg = malloc(sizeof(*agg) * (maxlen+1));
for (idx=0; idx<=maxlen; idx++)
agg[idx] = 0;
for (idx=0; idx<htable_size; idx++) {
agg[occupation[idx]]++;
if (((int)occupation[idx]) == occupation_target) {
printf("occupation target %d at %lu\n",
occupation_target, idx);
occupation_target = -1;
}
}
printf("Count\tLength\tCT\n");
for (partial=0, idx=maxlen; idx>0; idx--) {
double d;
if (agg[idx] == 0) continue;
partial += idx * agg[idx];
d = (100.0 * partial) / (1.0 * total);
printf("%lu\t%lu\t%.02f%%\n", agg[idx], idx, d);
}
printf("%lu\t0\t100.00%%\n", agg[idx]);
}
static struct hash_def *find_hash(char *name)
{
u32 idx;
for (idx=0; idx<NR_HASHES; idx++)
if (0 == strcmp(name, hashes[idx].name))
return hashes+idx;
fprintf(stderr, "no hash function named '%s'\n", name);
return 0;
}
static void usage(void)
{
fprintf(stderr, "Usage: not written\n");
exit(1);
}
static u32 prime_select(u32);
int main(int argc, char **argv)
{
int c;
char buf[512], copy[512];
char *filename = "/proc/net/ip_conntrack";
FILE *fp;
int select_prime = 0;
while (EOF!=(c=getopt(argc, argv, "f:s:h:i:t:b:c:CPu"))) switch(c) {
case 'f': filename = optarg; break;
case 'u': unidir = 1; break;
case 's': htable_size = strtoul(optarg, 0, 10); break;
case 'P': select_prime = 1; break;
case 'h': test_hash = find_hash(optarg); break;
case 'i': display_target = strtol(optarg, 0, 10); break;
case 't': occupation_target = strtol(optarg, 0, 10); break;
case 'b': ignore_tcp_timeout_bound = strtoul(optarg, 0, 10); break;
case 'c': crc32_seed = strtoul(optarg, 0, 10); break;
case 'C': srandom(time(0)); crc32_seed = random(); break;
default: usage();
}
if (!test_hash) return 1;
fp = (0 == strcmp(filename, "-")) ? stdin : fopen(filename, "r");
if (!fp) {
fprintf(stderr, "%s: %s\n", filename, strerror(errno));
exit(1);
}
if (select_prime) htable_size = prime_select(htable_size);
printf("filename: %s\n", filename);
printf("hash function: %s\n", test_hash->name);
printf("number of buckets: %lu\n", htable_size);
if (ignore_tcp_timeout_bound)
printf("ignore TCP conntracks with timeout less than %lu\n",
ignore_tcp_timeout_bound);
if (crc32_seed)
printf("CRC32 seed %lu\n", crc32_seed);
do_init();
while (fgets(buf, sizeof(buf), fp)) {
if (display_target != -1)
strcpy(copy, buf);
if (process(buf))
printf("[%d]\t%s", display_target, copy);
}
if (fp != stdin) fclose(fp);
show_occupation();
return 0;
}
static u32 prime_sizes[] = {
3, /* 2^2-1 */
7, /* 2^3-1 */
13,
31, /* 2^5-1 */
61,
127, /* 2^7-1 */
251,
509,
1021,
2039,
4093,
8191, /* 2^13-1 */
16381,
32749,
65521,
131071, /* 2^17-1 */
262139,
524287, /* 2^19-1 */
1048571,
2097157,
4194301,
8388581,
};
#define NR_PRIME_SIZES (sizeof(prime_sizes)/sizeof(prime_sizes[0]))
static u32 prime_select(u32 val)
{
u32 idx;
for (idx=0; idx<NR_PRIME_SIZES; idx++)
if (val < prime_sizes[idx])
return prime_sizes[idx];
return prime_sizes[NR_PRIME_SIZES-1];
}
/* crc32.c -- compute the CRC-32 of a data stream
* Copyright (C) 1995-2002 Mark Adler
* stolen from zlib CVS
*/
/* @(#) $Id: crc32.c,v 1.2.2.1 2002/03/12 09:34:29 werner Exp $ */
/* ========================================================================
* Table of CRC-32's of all single-byte values (made by make_crc_table)
*/
static const u32 crc_table[256] = {
0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
0x2d02ef8dL
};
/* ========================================================================= */
#define DO1(buf) crc = crc_table[((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8);
#define DO2(buf) DO1(buf); DO1(buf);
#define DO4(buf) DO2(buf); DO2(buf);
#define DO8(buf) DO4(buf); DO4(buf);
/* ========================================================================= */
u32 crc32(crc, buf, len)
u32 crc;
const char *buf;
int len;
{
crc = crc ^ 0xffffffffL;
while (len >= 8)
{
DO8(buf);
len -= 8;
}
if (len) do {
DO1(buf);
} while (--len);
return crc ^ 0xffffffffL;
}
