Re: conntrack performance/DoS formula

[Patrick Schaaf <bof@bof.de>]

[-- Attachment #1: Type: text/plain, Size: 1682 bytes --]

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


[-- Attachment #2: cttest.c --]
[-- Type: text/plain, Size: 7297 bytes --]

/* 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];
}

[-- Attachment #3: crc32.c --]
[-- Type: text/plain, Size: 4400 bytes --]

/* 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;
}