Re: conntrack performance/DoS formula

[Patrick Schaaf <bof@bof.de>]

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

Hi again,

one more elaboration of the cttest program, before I go offline in preparation
for the fourth German football world championship...

This version adds a '-b X' option. If you specify that, all TCP conntracks
with timeouts less than X get ignored. For example, use "-b 431940" to only
count the conntracks active within the last 60 seconds.

Incidentally, this makes the current ip_conntrack hash function look a lot
less bad than before. I appears that the "long bucket" packets mostly belong
to some kind of port scan. They will time out eventually, and they will NOT
contribute significantly to CPU usage, because they will be rarely hit.

All is well, it seems. At least looking at my 33000 entry sample from
yesterday. I'm looking forward to results from other workloads!

best regards
  Patrick

[-- Attachment #2: cttest.c --]
[-- Type: text/plain, Size: 6095 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 <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 hash_crc32(struct ct_key *key)
{
	u32 crc = crc32(0, (const char *) &key->proto, sizeof(key->proto));
	u32 v32;
	u16 v16;
	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 (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"); 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("hash function: %s\n", test_hash->name);
	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);
}

int main(int argc, char **argv)
{
	int c;
	char buf[512], copy[512];
	char *filename = "/proc/net/ip_conntrack";
	FILE *fp;

	while (EOF != (c = getopt(argc, argv, "f:us:h:i:t:b:"))) switch(c) {
		case 'f': filename = optarg; break;
		case 'u': unidir = 1; break;
		case 's': htable_size = strtoul(optarg, 0, 10); 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;
		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);
	}
	printf("filename: %s\n", filename);
	if (ignore_tcp_timeout_bound)
		printf("ignore TCP conntracks with timeout less than %lu\n",
			ignore_tcp_timeout_bound);
	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;
}

[-- 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;
}