From: Patrick Schaaf Subject: Re: conntrack performance/DoS formula Date: Sun, 30 Jun 2002 10:31:31 +0200 Sender: netfilter-devel-admin@lists.samba.org Message-ID: <20020630103131.X4136@oknodo.bof.de> References: <20020628082339.I2890@oknodo.bof.de> <15644.41633.528107.723418@isis.cs3-inc.com> <20020628203624.A4136@oknodo.bof.de> <15644.45834.373409.220647@isis.cs3-inc.com> <20020628213520.C4136@oknodo.bof.de> <15644.53466.193145.914415@isis.cs3-inc.com> <20020628232819.H4136@oknodo.bof.de> <15644.58258.483223.56527@isis.cs3-inc.com> <20020629140729.N4136@oknodo.bof.de> <20020629143406.O4136@oknodo.bof.de> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="tEFtbjk+mNEviIIX" Cc: netfilter-devel@lists.samba.org Return-path: To: don-nf@isis.cs3-inc.com Content-Disposition: inline In-Reply-To: <20020629143406.O4136@oknodo.bof.de>; from bof@bof.de on Sat, Jun 29, 2002 at 02:34:06PM +0200 Errors-To: netfilter-devel-admin@lists.samba.org List-Help: List-Post: List-Subscribe: , List-Unsubscribe: , List-Archive: List-Id: netfilter-devel.vger.kernel.org --tEFtbjk+mNEviIIX Content-Type: text/plain; charset=us-ascii Content-Disposition: inline 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 --tEFtbjk+mNEviIIX Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="cttest.c" /* 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 #include #include #include #include #include #include #include #include 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; idxhash_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 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; idx0; 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; idxname); 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> 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; } --tEFtbjk+mNEviIIX--