[netfilter-cvslog] r6560 - trunk/hashtrie
kadlec at netfilter.org
kadlec at netfilter.org
Tue Mar 28 14:14:52 CEST 2006
Author: kadlec at netfilter.org
Date: 2006-03-28 14:14:46 +0200 (Tue, 28 Mar 2006)
New Revision: 6560
Added:
trunk/hashtrie/graphs
trunk/hashtrie/hasharray.c
trunk/hashtrie/hasharray.h
trunk/hashtrie/hashes.c
trunk/hashtrie/hashtable.c
trunk/hashtrie/hashtable.h
trunk/hashtrie/hashtrie.c
trunk/hashtrie/hashtrie.h
trunk/hashtrie/hashtrie_var.c
trunk/hashtrie/hashtrie_var.h
trunk/hashtrie/rdtsc2.h
trunk/hashtrie/runme
trunk/hashtrie/sfhash.h
trunk/hashtrie/shared_node.c
trunk/hashtrie/shared_node.h
trunk/hashtrie/tables.c
trunk/hashtrie/tables.h
Removed:
trunk/hashtrie/newtable.c
trunk/hashtrie/newtable.h
trunk/hashtrie/newtest.c
trunk/hashtrie/oldtable.c
trunk/hashtrie/oldtable.h
trunk/hashtrie/oldtest.c
trunk/hashtrie/rdtsc2.c
Modified:
trunk/hashtrie/Makefile
trunk/hashtrie/conntrack.h
Log:
Changes in hashtrie finally committed (JK).
Modified: trunk/hashtrie/Makefile
===================================================================
--- trunk/hashtrie/Makefile 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/Makefile 2006-03-28 12:14:46 UTC (rev 6560)
@@ -1,8 +1,67 @@
-all: newtest oldtest
+KERNEL_DIR:=/usr/src/2.6.15.3/linux
+CFLAGS:=-Wall -O2 -g -D__KERNEL__
+ifdef KERNEL_DIR
+CFLAGS += -I$(KERNEL_DIR)/include
+endif
-newtest: newtest.c misc.h jhash.h conntrack.h newtable.c newtable.h rdtsc2.c
- gcc -Wall -O2 -g -D__KERNEL__ -o $@ newtest.c newtable.c
+OPT:=-march=i686 -mtune=pentium4
-oldtest: oldtest.c misc.h jhash.h conntrack.h oldtable.c oldtable.h rdtsc2.c
- gcc -Wall -O2 -g -D__KERNEL__ -DOLDTABLE -o $@ oldtest.c oldtable.c
+OFILES:=tables.o
+OFILES+=hashtable.o hashtable_sf.o
+OFILES+=hashtrie64.o hashtrie32.o hashtrie16.o hashtrie8.o hashtrie4.o
+OFILES+=hashtrie_var0.o hashtrie_var1.o hashtrie_var2.o
+OFILES+=hasharray8.o hasharray4.o
+OFILES+=shared_node.o
+all: tables hashes
+
+clean:
+ rm tables hashes *.o
+
+hashtable.o: hashtable.c hashtable.h tables.h misc.h jhash.h sfhash.h conntrack.h
+ gcc $(CFLAGS) -o hashtable.o -c hashtable.c
+
+hashtable_sf.o: hashtable.c hashtable.h tables.h misc.h jhash.h sfhash.h conntrack.h
+ gcc -DSFHASH $(CFLAGS) -o hashtable_sf.o -c hashtable.c
+
+hashtrie64.o: hashtrie.c hashtrie.h tables.h jhash.h conntrack.h
+ gcc $(CFLAGS) -o hashtrie64.o -c hashtrie.c
+
+hashtrie32.o: hashtrie.c hashtrie.h tables.h jhash.h conntrack.h
+ gcc -DHASHSHIFT=5 $(CFLAGS) -o hashtrie32.o -c hashtrie.c
+
+hashtrie16.o: hashtrie.c hashtrie.h tables.h jhash.h conntrack.h
+ gcc -DHASHSHIFT=4 $(CFLAGS) -o hashtrie16.o -c hashtrie.c
+
+hashtrie8.o: hashtrie.c hashtrie.h tables.h jhash.h conntrack.h
+ gcc -DHASHSHIFT=3 $(CFLAGS) -o hashtrie8.o -c hashtrie.c
+
+hashtrie4.o: hashtrie.c hashtrie.h tables.h jhash.h conntrack.h
+ gcc -DHASHSHIFT=2 $(CFLAGS) -o hashtrie4.o -c hashtrie.c
+
+hashtrie_var0.o: hashtrie_var.c hashtrie_var.h tables.h jhash.h conntrack.h
+ gcc -DHASHSHIFT0=14 -DHASHSHIFT1=3 -DHASHSHIFT2=2 $(CFLAGS) -o hashtrie_var0.o -c hashtrie_var.c
+
+hashtrie_var1.o: hashtrie_var.c hashtrie_var.h tables.h jhash.h conntrack.h
+ gcc -DHASHSHIFT0=8 -DHASHSHIFT1=6 -DHASHSHIFT2=4 $(CFLAGS) -o hashtrie_var1.o -c hashtrie_var.c
+
+hashtrie_var2.o: hashtrie_var.c hashtrie_var.h tables.h jhash.h conntrack.h
+ gcc -DHASHSHIFT0=12 -DHASHSHIFT1=6 -DHASHSHIFT2=2 $(CFLAGS) -o hashtrie_var2.o -c hashtrie_var.c
+
+hasharray8.o: hasharray.c hasharray.h tables.h jhash.h conntrack.h
+ gcc $(CFLAGS) -o hasharray8.o -c hasharray.c
+
+hasharray4.o: hasharray.c hasharray.h tables.h jhash.h conntrack.h
+ gcc -DNUMENTRY=4 $(CFLAGS) -o hasharray4.o -c hasharray.c
+
+shared_node.o: shared_node.c shared_node.h tables.h jhash.h conntrack.h
+ gcc $(CFLAGS) -o shared_node.o -c shared_node.c
+
+tables.o: tables.c tables.h misc.h jhash.h conntrack.h rdtsc2.h
+ gcc $(CFLAGS) -o tables.o -c tables.c
+
+tables: $(OFILES)
+ gcc -o tables $(OFILES)
+
+hashes: hashes.c jhash.h sfhash.h conntrack.h rdtsc2.h
+ gcc $(CFLAGS) $(OPT) -o hashes hashes.c
Modified: trunk/hashtrie/conntrack.h
===================================================================
--- trunk/hashtrie/conntrack.h 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/conntrack.h 2006-03-28 12:14:46 UTC (rev 6560)
@@ -5,6 +5,7 @@
#include "misc.h"
#include "list.h"
#include "jhash.h"
+#include "sfhash.h"
enum ip_conntrack_dir
{
@@ -40,13 +41,8 @@
};
/* This contains the information to distinguish a connection. */
-struct ip_conntrack_tuple
+struct ip_conntrack_tuple_generic
{
-#ifdef OLDTABLE
- struct list_head list;
-#else
- struct ip_conntrack_tuple **hashpointer;
-#endif
struct ip_conntrack_manip src;
/* These are the parts of the tuple which are fixed. */
@@ -78,14 +74,16 @@
} dst;
};
-struct ip_conntrack
+struct ip_conntrack_generic
{
- struct ip_conntrack_tuple tuple[IP_CT_DIR_MAX];
+ struct ip_conntrack_tuple_generic tuple[IP_CT_DIR_MAX];
+ void *ct;
};
unsigned int ip_conntrack_hash_rnd;
-extern inline unsigned int ip_ct_tuple_equal(struct ip_conntrack_tuple *t1, struct ip_conntrack_tuple *t2)
+extern inline unsigned int ip_ct_tuple_equal(struct ip_conntrack_tuple_generic *t1,
+ struct ip_conntrack_tuple_generic *t2)
{
return t1->src.ip == t2->src.ip
&& t1->src.u.all == t2->src.u.all
@@ -94,9 +92,15 @@
&& t1->dst.protonum == t2->dst.protonum;
}
-extern inline uint32_t hash_tuple(struct ip_conntrack_tuple *tuple)
+#ifdef SFHASH
+#define HASH_3WORDS(a,b,c,i) sfhash_3words(a,b,c,i)
+#else
+#define HASH_3WORDS(a,b,c,i) jhash_3words(a,b,c,i)
+#endif
+
+extern inline u_int32_t hash_tuple(struct ip_conntrack_tuple_generic *tuple)
{
- return jhash_3words(tuple->src.ip,
+ return HASH_3WORDS(tuple->src.ip,
(tuple->dst.ip ^ tuple->dst.protonum),
(tuple->src.u.all | (tuple->dst.u.all << 16)),
ip_conntrack_hash_rnd);
Added: trunk/hashtrie/graphs
===================================================================
--- trunk/hashtrie/graphs 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/graphs 2006-03-28 12:14:46 UTC (rev 6560)
@@ -0,0 +1,108 @@
+#!/usr/bin/perl
+
+foreach $file (@ARGV) {
+ open(IN, "$file") || die "Cannot open $file: $!\n";
+ while (<IN>) {
+ if (/testnum (\d+)/) {
+ $testnum = $1;
+ } elsif (/(random|DoS) conntrack test/) {
+ $type = $1;
+ } elsif (/(.*): ((insert|lookup|delete).*)/) {
+ $table = $1;
+ ($mode = $2) =~ s/\)//;
+ $mode =~ s/\s*\(/-/;
+ } elsif (/memory: (\d+)/) {
+ $result->{$mode}->{$table}->{$type}->{$testnum}->{memory} = $1;
+ } elsif (/time: (\d+)/) {
+ $result->{$mode}->{$table}->{$type}->{$testnum}->{time} = $1;
+ }
+ }
+ close(IN);
+}
+
+foreach (qw(25600 51200 102400 204800)) {
+ $full->{$_} = 2*$_/102400;
+}
+
+open(GNUPLOT, "|gnuplot");
+foreach $mode (keys %$result) {
+ next unless $mode;
+ $title = $memory = $time = $dos = "";
+ foreach $table (qw(hashtable hashtable-sf hashtrie64 hashtrie32 hashtrie16 hashtrie8 hashtrie4 hashtrie-var0 hashtrie-var1 hashtrie-var2 hasharray8 hasharray4 shared_node)) {
+ # foreach $table (qw(hashtable hashtable2)) {
+ $title .= "'-' title \"$table\" with linespoints, ";
+ foreach $num (qw(25600 51200 102400 204800)) {
+ $memory .= $full->{$num} . ' ' .
+ $result->{$mode}->{$table}->{random}->{$num}->{memory} . "\n";
+ $time .= $full->{$num} . ' ' .
+ $result->{$mode}->{$table}->{random}->{$num}->{time} . "\n";
+ }
+ foreach $num (qw(25600 51200 102400 204800)) {
+ # $memory .= $num . ' ' .
+ # $result->{$mode}->{$table}->{DoS}->{$num}->{memory} . "\n";
+ $dos .= $full->{$num} . ' ' .
+ $result->{$mode}->{$table}->{DoS}->{$num}->{time} . "\n";
+ }
+ $memory .= "e\n";
+ $time .= "e\n";
+ $dos .= "e\n";
+ }
+ $title =~ s/, $//;
+ print GNUPLOT <<TXT;
+set terminal png small
+set title "$mode"
+set ylabel "Memory"
+set xlabel "Entries = hashsize * scale"
+set output "memory-$mode.png"
+plot $title
+$memory
+set ylabel "Time"
+set output "time-$mode.png"
+plot $title
+$time
+set output "time-dos-$mode.png"
+plot $title
+$dos
+TXT
+}
+foreach $mode (keys %$result) {
+ next unless $mode;
+ $title = $memory = $time = $dos = "";
+ # foreach $table (qw(hashtable hashtable-sf hashtrie64 hashtrie32 hashtrie16 hashtrie8 hashtrie4 hashtrie-var0 hashtrie-var1 hashtrie-var2 hasharray8 hasharray4 shared_node)) {
+ foreach $table (qw(hashtable hashtrie64 hashtrie16 hashtrie-var0 hashtrie-var1 hashtrie-var2 hasharray8 hasharray4)) {
+ # foreach $table (qw(hashtable hashtable2)) {
+ $title .= "'-' title \"$table\" with linespoints, ";
+ foreach $num (qw(25600 51200 102400 204800)) {
+ $memory .= $full->{$num} . ' ' .
+ $result->{$mode}->{$table}->{random}->{$num}->{memory} . "\n";
+ $time .= $full->{$num} . ' ' .
+ $result->{$mode}->{$table}->{random}->{$num}->{time} . "\n";
+ }
+ foreach $num (qw(25600 51200 102400 204800)) {
+ # $memory .= $num . ' ' .
+ # $result->{$mode}->{$table}->{DoS}->{$num}->{memory} . "\n";
+ $dos .= $full->{$num} . ' ' .
+ $result->{$mode}->{$table}->{DoS}->{$num}->{time} . "\n";
+ }
+ $memory .= "e\n";
+ $time .= "e\n";
+ $dos .= "e\n";
+ }
+ $title =~ s/, $//;
+ print GNUPLOT <<TXT;
+set terminal png small
+set title "$mode"
+set ylabel "Memory"
+set xlabel "Entries = hashsize * scale"
+set output "top-memory-$mode.png"
+plot $title
+$memory
+set ylabel "Time"
+set output "top-time-$mode.png"
+plot $title
+$time
+set output "top-time-dos-$mode.png"
+plot $title
+$dos
+TXT
+}
Property changes on: trunk/hashtrie/graphs
___________________________________________________________________
Name: svn:executable
+ *
Added: trunk/hashtrie/hasharray.c
===================================================================
--- trunk/hashtrie/hasharray.c 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/hasharray.c 2006-03-28 12:14:46 UTC (rev 6560)
@@ -0,0 +1,308 @@
+#include <stdio.h>
+#include <string.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include "misc.h"
+#include "list.h"
+#include "conntrack.h"
+#include "tables.h"
+#include "hasharray.h"
+
+#if 0
+#define printd(args...) printf(args)
+#else
+#define printd(args...)
+#endif
+
+spinlock_t lock;
+
+static inline int
+__lookup(struct hasharray_info *info,
+ struct ip_conntrack_tuple_generic *tuple,
+ hash_t hash)
+{
+ struct ip_conntrack_tuple *t;
+ unsigned int longsearch = 0;
+ struct ip_conntrack_array *array;
+ unsigned int i;
+
+ printd("Entering lookup\n");
+ printd("lookup: looking for tuple %p in bucket %u\n", tuple, bucketnr);
+
+ array = &info->hashtable[hash % info->hashsize];
+ while (array) {
+ for (i = 0; i < NUMENTRY; i++) {
+ if (info->longsearch < longsearch)
+ info->longsearch = longsearch;
+ longsearch++;
+ t = &array->members[i];
+ if (!t->dir)
+ return 0;
+ if (t->hash == hash
+ && ip_ct_tuple_equal(&t->tuple, tuple))
+ return 1;
+ }
+ array = array->next;
+ }
+ return 0;
+}
+
+static inline int
+lookup_do(struct hasharray_info *info,
+ struct ip_conntrack_generic *ct,
+ hash_t hash_orig, hash_t hash_reply)
+{
+ return (__lookup(info, &ct->tuple[IP_CT_DIR_ORIGINAL], hash_orig)
+ && __lookup(info, &ct->tuple[IP_CT_DIR_REPLY], hash_reply));
+}
+
+static int
+lookup(struct table_info *table, struct ip_conntrack_generic *ct)
+{
+ struct hasharray_info *info = (struct hasharray_info *) table->data;
+
+ return lookup_do(info, ct,
+ hash_tuple(&ct->tuple[IP_CT_DIR_ORIGINAL]),
+ hash_tuple(&ct->tuple[IP_CT_DIR_REPLY]));
+}
+
+static inline int
+__insert(struct hasharray_info *info,
+ struct ip_conntrack_tuple_generic *tuple,
+ hash_t hash,
+ struct ip_conntrack *ct,
+ int dir)
+{
+ struct ip_conntrack_tuple *t = NULL;
+ unsigned int longsearch = 0;
+ struct ip_conntrack_array *array;
+ unsigned int i;
+
+ printd("Entering insert\n");
+
+ array = &info->hashtable[hash % info->hashsize];
+ while (1) {
+ for (i = 0; i < NUMENTRY; i++) {
+ if (info->longsearch < longsearch)
+ info->longsearch = longsearch;
+ longsearch++;
+ t = &array->members[i];
+ if (!t->dir) {
+ t->hash = hash;
+ t->dir = dir + 1;
+ t->tuple = *tuple;
+ ct->tuple[dir] = t;
+ return 1;
+ }
+ if (t->hash == hash
+ && ip_ct_tuple_equal(&t->tuple, tuple))
+ return 0;
+ }
+ if (!array->next) {
+ array->next = malloc(sizeof(struct ip_conntrack_array));
+ if (!array->next)
+ return 0;
+ memset(array->next, 0, sizeof(struct ip_conntrack_array));
+ info->size += sizeof(struct ip_conntrack_array);
+ }
+ array = array->next;
+ }
+
+ return 0;
+}
+
+static int
+insert(struct table_info *table, struct ip_conntrack_generic *ct)
+{
+ struct hasharray_info *info = (struct hasharray_info *) table->data;
+ struct ip_conntrack *conntrack;
+ hash_t hash_orig, hash_reply;
+
+ printd("Entering insert\n");
+
+ conntrack = malloc(sizeof(struct ip_conntrack));
+ if (!conntrack) {
+ printf("Can't allocate conntrack\n");
+ return 0;
+ }
+ memset(conntrack, 0, sizeof(*conntrack));
+
+ hash_orig = hash_tuple(&ct->tuple[IP_CT_DIR_ORIGINAL]);
+ hash_reply = hash_tuple(&ct->tuple[IP_CT_DIR_REPLY]);
+
+ spin_lock(&lock);
+ if (!(__insert(info, &ct->tuple[IP_CT_DIR_ORIGINAL],
+ hash_orig, conntrack, IP_CT_DIR_ORIGINAL)
+ && __insert(info, &ct->tuple[IP_CT_DIR_REPLY],
+ hash_reply, conntrack, IP_CT_DIR_ORIGINAL))) {
+ spin_unlock(&lock);
+ return 0;
+ }
+
+ info->numentries += 2;
+ info->size += sizeof(struct ip_conntrack);
+
+ spin_unlock(&lock);
+ ct->ct = conntrack;
+
+ printd("Leaving insert\n");
+
+ return 1;
+}
+
+static inline int
+__delete(struct hasharray_info *info,
+ struct ip_conntrack_tuple_generic *tuple,
+ hash_t hash,
+ int dir)
+{
+ struct ip_conntrack_tuple *t = NULL;
+ unsigned int longsearch = 0;
+ struct ip_conntrack_array *array, *a, *b;
+ unsigned int i, j, k;
+
+ printd("Entering delete()\n");
+
+ array = a = b = &info->hashtable[hash % info->hashsize];
+ printd("Entering delete, %p\n", a);
+ j = k = NUMENTRY;
+ while (array) {
+ for (i = 0; i < NUMENTRY; i++) {
+ if (info->longsearch < longsearch)
+ info->longsearch = longsearch;
+ longsearch++;
+ t = &array->members[i];
+ if (j != NUMENTRY) {
+ if (!t->dir)
+ /* Use previous 'k' and 'b': */
+ goto found;
+ k = i;
+ b = array;
+ } else if (t->hash == hash
+ && ip_ct_tuple_equal(&t->tuple, tuple)) {
+ j = k = i;
+ a = b = array;
+ }
+ }
+ array = array->next;
+ }
+ if (j == NUMENTRY) {
+ printf("Entry to delete not found!\n");
+ return 0;
+ }
+ found:
+ if (j == k && a == b) {
+ /* j == last member */
+ a->members[j].dir = 0;
+ printd("Found as last member: %p (%u)\n", a, j);
+ } else if (k == 0) {
+ /* Last array can be freed */
+ memcpy(&a->members[j], &b->members[k], sizeof(*t));
+ free(b);
+ info->size -= sizeof(*b);
+ a->next = NULL;
+ printd("Last array can be freed: %p (%u), %p\n", b, k, a);
+ } else {
+ memcpy(&a->members[j], &b->members[k], sizeof(*t));
+ b->members[k].dir = 0;
+ printd("Found as mid member: %p (%u), %p (%u)\n", b, k, a, j);
+ }
+ return 1;
+}
+
+static int
+delete(struct table_info *table, struct ip_conntrack_generic *conntrack)
+{
+ struct hasharray_info *info = (struct hasharray_info *) table->data;
+ struct ip_conntrack *ct = (struct ip_conntrack *) conntrack->ct;
+
+ printd("Entering delete\n");
+ printd("delete: removing entry with ct %p\n", &ct);
+
+ spin_lock(&lock);
+ __delete(info, &conntrack->tuple[IP_CT_DIR_ORIGINAL],
+ hash_tuple(&conntrack->tuple[IP_CT_DIR_ORIGINAL]),
+ IP_CT_DIR_ORIGINAL);
+ __delete(info, &conntrack->tuple[IP_CT_DIR_REPLY],
+ hash_tuple(&conntrack->tuple[IP_CT_DIR_REPLY]),
+ IP_CT_DIR_REPLY);
+ spin_unlock(&lock);
+
+ info->numentries -= 2;
+ info->size -= sizeof(struct ip_conntrack);
+ free(ct);
+ printd("Leaving delete\n");
+
+ return 1;
+}
+
+static void report(struct table_info *table)
+{
+ struct hasharray_info *info = (struct hasharray_info *) table->data;
+
+ printf("Number of entries: %u\n", info->numentries);
+ printf("Longest search: %u\n", info->longsearch);
+ printf("Required memory: %u\n", info->size);
+
+ /* Reset for next test */
+ info->longsearch = 0;
+}
+
+static int init(struct table_info *table, unsigned int hashsize)
+{
+ struct hasharray_info *info;
+
+ table->data = malloc(sizeof(struct hasharray_info));
+ if (!table->data) {
+ printf("Error allocating hashtable info data\n");
+ return 0;
+ }
+ memset(table->data, 0, sizeof(struct hasharray_info));
+ info = (struct hasharray_info *) table->data;
+
+ info->hashtable = (void *)malloc(hashsize * sizeof(struct ip_conntrack_array));
+ if (!info->hashtable) {
+ printf("Error allocating hashtable\n");
+ return 0;
+ }
+ memset(info->hashtable, 0, hashsize * sizeof(struct ip_conntrack_array));
+ info->hashsize = hashsize;
+ info->size = hashsize * sizeof(struct ip_conntrack_array);
+
+ spin_lock_init(&lock);
+
+ printf("Table size: %u\n", info->size);
+ printf("Entry size: %u\n", sizeof(struct ip_conntrack));
+
+ return 1;
+}
+
+static int destroy(struct table_info *table)
+{
+ struct hasharray_info *info = (struct hasharray_info *) table->data;
+
+ if (info->numentries) {
+ printf("Error unregistering hashtable, not empty. entries: %u\n", info->numentries);
+ return 0;
+ }
+
+ free(info->hashtable);
+ free(info);
+
+ return 1;
+}
+
+#if NUMENTRY == 8
+struct table_info hasharray8_info = {
+ .name = "hasharray8",
+#else
+struct table_info hasharray4_info = {
+ .name = "hasharray4",
+#endif
+ .lookup = &lookup,
+ .insert = &insert,
+ .delete = &delete,
+ .report = &report,
+ .init = &init,
+ .destroy = &destroy,
+};
Added: trunk/hashtrie/hasharray.h
===================================================================
--- trunk/hashtrie/hasharray.h 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/hasharray.h 2006-03-28 12:14:46 UTC (rev 6560)
@@ -0,0 +1,36 @@
+#ifndef HASHARRAY_H
+#define HASHARRAY_H
+
+#ifndef NUMENTRY
+#define NUMENTRY 8
+#endif
+
+typedef uint32_t hash_t;
+
+struct ip_conntrack_tuple
+{
+ hash_t hash;
+ u_int8_t dir;
+ struct ip_conntrack_tuple_generic tuple;
+};
+
+struct ip_conntrack_array {
+ struct ip_conntrack_array *next;
+
+ struct ip_conntrack_tuple members[NUMENTRY];
+};
+
+struct ip_conntrack
+{
+ struct ip_conntrack_tuple *tuple[IP_CT_DIR_MAX];
+};
+
+struct hasharray_info {
+ struct ip_conntrack_array *hashtable;
+ unsigned int hashsize;
+ unsigned int numentries;
+ unsigned int longsearch;
+ unsigned int size;
+};
+
+#endif
Added: trunk/hashtrie/hashes.c
===================================================================
--- trunk/hashtrie/hashes.c 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/hashes.c 2006-03-28 12:14:46 UTC (rev 6560)
@@ -0,0 +1,158 @@
+/* Test different hashing methods */
+
+#include <unistd.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <time.h>
+#include "conntrack.h"
+#include "jhash.h"
+#include "sfhash.h"
+#include "rdtsc2.h"
+
+struct ip_conntrack_generic *conntrack_random;
+struct ip_conntrack_generic *conntrack_dos;
+
+#define DOS_SRC_BASE (10 << 24 | 0 << 16 | 0 << 8 | 1)
+#define DOS_DST (192 << 24 | 168 << 16 | 1 << 8 | 1)
+
+struct hash_info {
+ char name[16];
+ u32 (*fn)(struct ip_conntrack_tuple_generic *tuple);
+};
+
+u_int32_t jhash_tuple(struct ip_conntrack_tuple_generic *tuple)
+{
+ return jhash_3words(tuple->src.ip,
+ (tuple->dst.ip ^ tuple->dst.protonum),
+ (tuple->src.u.all | (tuple->dst.u.all << 16)),
+ ip_conntrack_hash_rnd);
+}
+
+u_int32_t sfhash_tuple(struct ip_conntrack_tuple_generic *tuple)
+{
+ return sfhash_3words(tuple->src.ip,
+ (tuple->dst.ip ^ tuple->dst.protonum),
+ (tuple->src.u.all | (tuple->dst.u.all << 16)),
+ ip_conntrack_hash_rnd);
+}
+
+#define TESTS_MAX 2
+struct hash_info hashes[2] = {
+ { .name = "jhash",
+ .fn = &jhash_tuple,
+ },
+ { .name = "sfhash",
+ .fn = &sfhash_tuple,
+ },
+};
+
+int init_conntrack(unsigned int testnum)
+{
+ unsigned int i;
+ unsigned int j,k;
+
+ conntrack_random = malloc(testnum * sizeof(struct ip_conntrack_generic));
+ if (!conntrack_random) {
+ printf("Couldn't allocate random conntracks\n");
+ return -1;
+ }
+ conntrack_dos = malloc(testnum * sizeof(struct ip_conntrack_generic));
+ if (!conntrack_dos) {
+ printf("Couldn't allocate DoS conntracks\n");
+ return -1;
+ }
+
+ srand((int)time(NULL));
+
+ ip_conntrack_hash_rnd = rand();
+
+ for (i = 0; i < testnum; i++) {
+ conntrack_random[i].tuple[IP_CT_DIR_ORIGINAL].src.ip = rand();
+ conntrack_random[i].tuple[IP_CT_DIR_ORIGINAL].src.u.tcp.port = (u16)rand();
+ conntrack_random[i].tuple[IP_CT_DIR_ORIGINAL].dst.ip = rand();
+ conntrack_random[i].tuple[IP_CT_DIR_ORIGINAL].dst.u.tcp.port = (u16)rand();
+ conntrack_random[i].tuple[IP_CT_DIR_ORIGINAL].dst.protonum = 6;
+ conntrack_random[i].tuple[IP_CT_DIR_ORIGINAL].dst.dir = IP_CT_DIR_ORIGINAL;
+
+ conntrack_random[i].tuple[IP_CT_DIR_REPLY].src.ip = conntrack_random[i].tuple[IP_CT_DIR_ORIGINAL].dst.ip;
+ conntrack_random[i].tuple[IP_CT_DIR_REPLY].src.u.tcp.port = conntrack_random[i].tuple[IP_CT_DIR_ORIGINAL].dst.u.tcp.port;
+ conntrack_random[i].tuple[IP_CT_DIR_REPLY].dst.ip = conntrack_random[i].tuple[IP_CT_DIR_ORIGINAL].src.ip;
+ conntrack_random[i].tuple[IP_CT_DIR_REPLY].dst.u.tcp.port = conntrack_random[i].tuple[IP_CT_DIR_ORIGINAL].src.u.tcp.port;
+ conntrack_random[i].tuple[IP_CT_DIR_REPLY].dst.protonum = 6;
+ conntrack_random[i].tuple[IP_CT_DIR_REPLY].dst.dir = IP_CT_DIR_REPLY;
+ }
+ i = j = 0;
+ while (i < testnum) {
+ for (k = 1024; k < 40000 && i < testnum; k++) {
+ conntrack_dos[i].tuple[IP_CT_DIR_ORIGINAL].src.ip = DOS_SRC_BASE + j;
+ conntrack_dos[i].tuple[IP_CT_DIR_ORIGINAL].src.u.tcp.port = k;
+ conntrack_dos[i].tuple[IP_CT_DIR_ORIGINAL].dst.ip = DOS_DST;
+ conntrack_dos[i].tuple[IP_CT_DIR_ORIGINAL].dst.u.tcp.port = 80;
+ conntrack_dos[i].tuple[IP_CT_DIR_ORIGINAL].dst.protonum = 6;
+ conntrack_dos[i].tuple[IP_CT_DIR_ORIGINAL].dst.dir = IP_CT_DIR_ORIGINAL;
+
+ conntrack_dos[i].tuple[IP_CT_DIR_REPLY].src.ip = conntrack_dos[i].tuple[IP_CT_DIR_ORIGINAL].dst.ip;
+ conntrack_dos[i].tuple[IP_CT_DIR_REPLY].src.u.tcp.port = conntrack_dos[i].tuple[IP_CT_DIR_ORIGINAL].dst.u.tcp.port;
+ conntrack_dos[i].tuple[IP_CT_DIR_REPLY].dst.ip = conntrack_dos[i].tuple[IP_CT_DIR_ORIGINAL].src.ip;
+ conntrack_dos[i].tuple[IP_CT_DIR_REPLY].dst.u.tcp.port = conntrack_dos[i].tuple[IP_CT_DIR_ORIGINAL].src.u.tcp.port;
+ conntrack_dos[i].tuple[IP_CT_DIR_REPLY].dst.protonum = 6;
+ conntrack_dos[i].tuple[IP_CT_DIR_REPLY].dst.dir = IP_CT_DIR_REPLY;
+ i++;
+ }
+ j++;
+ }
+ return 0;
+}
+
+void hash_tests(struct hash_info *hash, unsigned int testnum,
+ struct ip_conntrack_generic *conntrack,
+ struct ip_conntrack_generic *nomatch)
+{
+ int i;
+ u32 ret;
+
+ total_count = 0;
+ total_time = 0;
+ for (i = 0; i < testnum; i++) {
+ TIMER(ret = hash->fn(&conntrack[i].tuple[IP_CT_DIR_ORIGINAL]); );
+ TIMER(ret = hash->fn(&conntrack[i].tuple[IP_CT_DIR_REPLY]); );
+ TIMER(ret = hash->fn(&nomatch[i].tuple[IP_CT_DIR_ORIGINAL]); );
+ TIMER(ret = hash->fn(&nomatch[i].tuple[IP_CT_DIR_REPLY]); );
+ }
+ printf("%s:\n", hash->name);
+ print_timer();
+}
+
+void usage()
+{
+ printf("hashes [-t testnum]\n");
+ exit(1);
+}
+
+int main(int argc, char **argv)
+{
+ int c, i, j = 0;
+ unsigned int testnum = 100*1024;
+
+ while ((c = getopt(argc, argv, "t:")) != -1) {
+ switch (c) {
+ case 't': testnum = strtoul(optarg, 0, 10); j++; break;
+ default: usage();
+ }
+ }
+ rdtsc_cal(100000000);
+
+ if (init_conntrack(testnum))
+ exit(1);
+
+ for (i = 0; i < TESTS_MAX; i++) {
+ /* Run tests */
+ hash_tests(&hashes[i], testnum,
+ conntrack_random, conntrack_dos);
+ }
+ free(conntrack_random);
+ free(conntrack_dos);
+
+ return 0;
+}
Copied: trunk/hashtrie/hashtable.c (from rev 6559, trunk/hashtrie/oldtable.c)
===================================================================
--- trunk/hashtrie/oldtable.c 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/hashtable.c 2006-03-28 12:14:46 UTC (rev 6560)
@@ -0,0 +1,204 @@
+#include <stdio.h>
+#include <string.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include "misc.h"
+#include "list.h"
+#include "conntrack.h"
+#include "tables.h"
+#include "hashtable.h"
+
+#if 0
+#define printd(args...) printf(args)
+#else
+#define printd(args...)
+#endif
+
+spinlock_t lock;
+
+static inline int
+__lookup(struct hashtable_info *info,
+ struct ip_conntrack_tuple_generic *tuple,
+ hash_t bucketnr)
+{
+ struct ip_conntrack_tuple *t;
+ unsigned int longsearch = 0;
+
+ printd("Entering lookup\n");
+ printd("lookup: looking for tuple %p in bucket %u\n", tuple, bucketnr);
+
+ list_for_each_entry(t, &info->hashtable[bucketnr], list) {
+ if (ip_ct_tuple_equal(&t->tuple, tuple)) {
+ if (info->longsearch < longsearch)
+ info->longsearch = longsearch;
+ return 1;
+ }
+ longsearch++;
+ }
+ if (info->longsearch < longsearch)
+ info->longsearch = longsearch;
+ return 0;
+}
+
+static inline int
+lookup_do(struct hashtable_info *info,
+ struct ip_conntrack_generic *ct,
+ hash_t bucket_orig, hash_t bucket_reply)
+{
+ return (__lookup(info, &ct->tuple[IP_CT_DIR_ORIGINAL], bucket_orig)
+ && __lookup(info, &ct->tuple[IP_CT_DIR_REPLY], bucket_reply));
+}
+
+static int
+lookup(struct table_info *table, struct ip_conntrack_generic *ct)
+{
+ struct hashtable_info *info = (struct hashtable_info *) table->data;
+
+ return lookup_do(info, ct,
+ hash_tuple(&ct->tuple[IP_CT_DIR_ORIGINAL]) % info->hashsize,
+ hash_tuple(&ct->tuple[IP_CT_DIR_REPLY]) % info->hashsize);
+}
+
+static int
+insert(struct table_info *table, struct ip_conntrack_generic *ct)
+{
+ struct hashtable_info *info = (struct hashtable_info *) table->data;
+ struct ip_conntrack *conntrack;
+ hash_t bucket_orig, bucket_reply;
+
+ printd("Entering insert\n");
+
+ conntrack = malloc(sizeof(struct ip_conntrack));
+ if (!conntrack) {
+ printf("Can't allocate conntrack\n");
+ return 0;
+ }
+ memset(conntrack, 0, sizeof(*conntrack));
+ INIT_LIST_HEAD(&conntrack->tuple[IP_CT_DIR_ORIGINAL].list);
+ conntrack->tuple[IP_CT_DIR_ORIGINAL].tuple = ct->tuple[IP_CT_DIR_ORIGINAL];
+ INIT_LIST_HEAD(&conntrack->tuple[IP_CT_DIR_REPLY].list);
+ conntrack->tuple[IP_CT_DIR_REPLY].tuple = ct->tuple[IP_CT_DIR_REPLY];
+
+ bucket_orig = hash_tuple(&ct->tuple[IP_CT_DIR_ORIGINAL]) % info->hashsize;
+ bucket_reply = hash_tuple(&ct->tuple[IP_CT_DIR_REPLY]) % info->hashsize;
+
+ spin_lock(&lock);
+ if (lookup_do(info, ct, bucket_orig, bucket_reply)) {
+ spin_unlock(&lock);
+ return 0;
+ }
+
+ printd("insert: adding entry with ct %p into bucket %u:%u\n", ct, bucket_orig, bucket_reply);
+
+ list_add(&conntrack->tuple[IP_CT_DIR_ORIGINAL].list,
+ &(info->hashtable[bucket_orig]));
+ list_add(&conntrack->tuple[IP_CT_DIR_REPLY].list,
+ &(info->hashtable[bucket_reply]));
+
+ info->numentries += 2;
+ info->size += sizeof(struct ip_conntrack);
+
+ spin_unlock(&lock);
+ ct->ct = conntrack;
+
+ printd("Leaving insert\n");
+
+ return 1;
+}
+
+static int
+delete(struct table_info *table, struct ip_conntrack_generic *conntrack)
+{
+ struct hashtable_info *info = (struct hashtable_info *) table->data;
+ struct ip_conntrack *ct = (struct ip_conntrack *) conntrack->ct;
+
+ printd("Entering delete\n");
+ printd("delete: removing entry with ct %p\n", &ct);
+
+ spin_lock(&lock);
+ list_del(&ct->tuple[IP_CT_DIR_ORIGINAL].list);
+ list_del(&ct->tuple[IP_CT_DIR_REPLY].list);
+ spin_unlock(&lock);
+
+ info->numentries -= 2;
+ info->size -= sizeof(struct ip_conntrack);
+ free(ct);
+ printd("Leaving delete\n");
+
+ return 1;
+}
+
+static void report(struct table_info *table)
+{
+ struct hashtable_info *info = (struct hashtable_info *) table->data;
+
+ printf("Number of entries: %u\n", info->numentries);
+ printf("Longest search: %u\n", info->longsearch);
+ printf("Required memory: %u\n", info->size);
+
+ /* Reset for next test */
+ info->longsearch = 0;
+}
+
+static int init(struct table_info *table, unsigned int hashsize)
+{
+ struct hashtable_info *info;
+ unsigned int i;
+
+ table->data = malloc(sizeof(struct hashtable_info));
+ if (!table->data) {
+ printf("Error allocating hashtable info data\n");
+ return 0;
+ }
+ memset(table->data, 0, sizeof(struct hashtable_info));
+ info = (struct hashtable_info *) table->data;
+
+ info->hashtable = (void *)malloc(hashsize * sizeof(struct list_head));
+ if (!info->hashtable) {
+ printf("Error allocating hashtable\n");
+ return 0;
+ }
+ memset(info->hashtable, 0, hashsize * sizeof(struct list_head));
+ info->hashsize = hashsize;
+ info->size = hashsize * sizeof(struct list_head);
+
+ spin_lock_init(&lock);
+
+ for (i = 0; i < hashsize; i++)
+ INIT_LIST_HEAD(&info->hashtable[i]);
+
+ printf("Table size: %u\n", info->size);
+ printf("Entry size: %u\n", sizeof(struct ip_conntrack));
+
+ return 1;
+}
+
+static int destroy(struct table_info *table)
+{
+ struct hashtable_info *info = (struct hashtable_info *) table->data;
+
+ if (info->numentries) {
+ printf("Error unregistering hashtable, not empty. entries: %u\n", info->numentries);
+ return 0;
+ }
+
+ free(info->hashtable);
+ free(info);
+
+ return 1;
+}
+
+#ifdef SFHASH
+struct table_info hashtable_sf_info = {
+ .name = "hashtable-sf",
+#else
+struct table_info hashtable_info = {
+ .name = "hashtable",
+#endif
+ .lookup = &lookup,
+ .insert = &insert,
+ .delete = &delete,
+ .report = &report,
+ .init = &init,
+ .destroy = &destroy,
+};
Copied: trunk/hashtrie/hashtable.h (from rev 6559, trunk/hashtrie/oldtable.h)
===================================================================
--- trunk/hashtrie/oldtable.h 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/hashtable.h 2006-03-28 12:14:46 UTC (rev 6560)
@@ -0,0 +1,28 @@
+#ifndef HASHTABLE_H
+#define HASHTABLE_H
+
+typedef uint32_t hash_t;
+
+struct hashtable_info {
+ struct list_head *hashtable;
+ unsigned int hashsize;
+ unsigned int numentries;
+ unsigned int longsearch;
+ unsigned int size;
+};
+
+struct ip_conntrack_tuple
+{
+ struct list_head list;
+
+ struct ip_conntrack_tuple_generic tuple;
+};
+
+struct ip_conntrack
+{
+ struct ip_conntrack_tuple tuple[IP_CT_DIR_MAX];
+};
+
+
+
+#endif
Copied: trunk/hashtrie/hashtrie.c (from rev 6559, trunk/hashtrie/newtable.c)
===================================================================
--- trunk/hashtrie/newtable.c 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/hashtrie.c 2006-03-28 12:14:46 UTC (rev 6560)
@@ -0,0 +1,484 @@
+#define _XOPEN_SOURCE 600
+#include <stdio.h>
+#include <string.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include "conntrack.h"
+#include "tables.h"
+#include "hashtrie.h"
+
+#if 0
+#define printd(args...) printf(args)
+#else
+#define printd(args...)
+#endif
+
+/* Iterate over the buckets and their slots as we walk the tree
+ Provides bucketcode and slotcode with various variables:
+ curtable
+ bucket
+ bucketnr
+ slotnr
+ hashshift
+ hashbits
+ depth
+*/
+#define hashtrie_iterate_hash(info, table, hash, bucketcode_enter, slotcode) \
+ do { \
+ struct hashentry *curtable = table, *bucket; \
+ int hashshift = 0; \
+ hashbits_t hashbits; \
+ u8 depth = 0; \
+ unsigned int slotnr, bucketnr; \
+ \
+ while (curtable) { \
+ bucketnr = (hash >> hashshift) & (HASHNUM - 1); \
+ bucket = &curtable[bucketnr]; \
+ \
+ hashshift += HASHSHIFT; \
+ /* FIXME: This is wrong */ \
+ if (hashshift > (sizeof(hash_t) * 8 - HASHBITS)) \
+ hashshift -= sizeof(hash_t) * 8 - HASHBITS; \
+ \
+ if (bucket->child) \
+ prefetchtest(&bucket->child[(hash >> hashshift) \
+ & (HASHNUM - 1)]); \
+ \
+ hashbits = (hash >> hashshift) & HASHBITMASK; \
+ \
+ do { \
+ bucketcode_enter \
+ } while (0); \
+ \
+ /* We want to start at entry 1 for depth 0 \
+ and entry 0 for all other depths */ \
+ for (slotnr = !depth; slotnr < NUMENTRY; slotnr++) { \
+ do { \
+ slotcode \
+ } while (0); \
+ } \
+ \
+ depth++; \
+ curtable = bucket->child; \
+ if (info->longsearch < depth) \
+ info->longsearch = depth; \
+ } \
+ } while (0)
+
+#define hashtrie_iterate_all(info, table, bucketcode_leave, slotcode) \
+ do { \
+ struct hashentry *curtable = table, *bucket; \
+ struct hashentry_stack stack[MAXDEPTH]; \
+ u8 depth = 0; \
+ unsigned int slotnr, bucketnr = 0; \
+ \
+ for (;;) { \
+ stack[depth].bucket = curtable; \
+ stack[depth].bucketnr = bucketnr; \
+ printd("Current depth: %u table: %p bucketnr: %u\n", depth, curtable, bucketnr); \
+ \
+ bucket = &curtable[bucketnr]; \
+ \
+ if (bucket->child) { \
+ depth++; \
+ if (info->longsearch < depth) \
+ info->longsearch = depth; \
+ bucketnr = 0; \
+ curtable = bucket->child; \
+ printd("Following child to depth: %u table: %p bucketnr: %u\n", depth, curtable, bucketnr); \
+ continue; \
+ } \
+ \
+ for (slotnr = !depth; slotnr < NUMENTRY; slotnr++) { \
+ do { \
+ slotcode \
+ } while (0); \
+ } \
+ \
+ bucketnr++; \
+ if (bucketnr >= HASHNUM) { \
+ if (depth == 0) \
+ break; \
+ depth--; \
+ curtable = stack[depth].bucket; \
+ bucketnr = stack[depth].bucketnr; \
+ \
+ do { \
+ bucketcode_leave \
+ } while (0); \
+ } \
+ } \
+ } while (0)
+
+static inline int
+lookup_do(struct hashtrie_info *info,
+ struct ip_conntrack_tuple_generic *tuple,
+ hash_t hash)
+{
+ printd("\nEntering lookup()\n");
+ printd("Looking up entry with hash: %x\n", hash);
+
+ hashtrie_iterate_hash(info, info->hashtrie, hash, {}, {
+ if (!bucket->data.members[slotnr])
+ continue;
+
+ printd("checking hashbits of %u\n", slotnr);
+ printd("current hashbits: %x\n",
+ bucket->hashbits[slotnr] & HASHBITMASK);
+
+ if (hashbits == (bucket->hashbits[slotnr] & HASHBITMASK) &&
+ ip_ct_tuple_equal(tuple, &bucket->data.members[slotnr]->tuple)) {
+ printd("Confirmed match %p at %u\n",
+ bucket->data.members[slotnr], slotnr);
+ return 1;
+ } else {
+ printd("Miss at %u\n", slotnr);
+ }
+ });
+
+ printd("Leaving lookup()\n\n\n");
+
+ return 0;
+}
+
+static int
+lookup(struct table_info *table, struct ip_conntrack_generic *ct)
+{
+ struct hashtrie_info *info = (struct hashtrie_info *) table->data;
+
+ return (lookup_do(info, &ct->tuple[IP_CT_DIR_ORIGINAL],
+ hash_tuple(&ct->tuple[IP_CT_DIR_ORIGINAL]))
+ && lookup_do(info, &ct->tuple[IP_CT_DIR_REPLY],
+ hash_tuple(&ct->tuple[IP_CT_DIR_REPLY])));
+}
+
+#ifdef NOT_SIMPLIFIED
+int alter(struct hashtrie_info *info, struct ip_conntrack_tuple *tuple, unsigned long status, hash_t hash)
+{
+ hashtrie_iterate_hash(info, info->hashtrie, hash, {}, {
+ if (!bucket->data.members[slotnr])
+ continue;
+
+ printd("checking hashbits of %u\n", slotnr);
+ printd("current hashbits: %x\n",
+ bucket->hashbits[slotnr] & HASHBITMASK);
+
+ if (hashbits == (bucket->hashbits[slotnr] & HASHBITMASK) &&
+ ip_ct_tuple_equal(tuple->tuple, bucket->data.members[slotnr].tuple)) {
+ printd("Confirmed match %p at %u\n",
+ bucket->data.members[slotnr], slotnr);
+ bucket->hashbits[slotnr] = hashbits | ((status & 1) << HASHBITS);
+ return 1;
+ } else {
+ printd("Miss at %u\n", slotnr);
+ }
+ });
+
+ printd("Leaving alter()\n\n\n");
+
+ return 0;
+}
+
+
+int evict(struct hashtrie_info *info, struct hashentry *bucket, u8 depth)
+{
+ unsigned int slotnr, evicted = 0;
+
+ printd("\nEntering evict()\n");
+ printd("Evicting from bucket %p at depth %u\n", bucket, depth);
+
+ /* We want to start at entry 1 for depth 0 and entry 0 for all other depths */
+ for (slotnr = !depth; slotnr < NUMENTRY; slotnr++) {
+ if (!bucket->data.members[slotnr])
+ continue;
+
+ /* Try to find an entry to evict */
+ if (!(bucket->hashbits[slotnr] & STATUSBITMASK)) {
+ /* This is just to make newtest.c happy, should be ripped out */
+ bucket->data.members[slotnr]->src.ip = 0;
+ bucket->data.members[slotnr]->dst.ip = 0;
+
+ delete(info, bucket->data.members[slotnr]);
+
+ evicted++;
+ }
+ }
+
+ printd("Leaving evict()\n\n\n");
+
+ return evicted;
+}
+#endif
+
+static inline unsigned int
+expand(struct hashtrie_info *info, struct hashentry *bucket, uint8_t depth)
+{
+ struct hashentry *newtable;
+ unsigned int ret;
+
+ printd("\nEntering expand()\n");
+
+ if (bucket->child) {
+ printf("expand: Error, expanding a bucket with children?\n");
+ return 0;
+ }
+
+ printd("expand: expanding bucket %p\n", bucket);
+
+ ret = posix_memalign((void *)&newtable, CACHELINE_REAL, HASHNUM * sizeof(struct hashentry));
+ if (ret != 0)
+ return 0;
+
+ memset(newtable, 0, HASHNUM * sizeof(struct hashentry));
+
+ printd("expand: Newtable: %p\n", newtable);
+
+ bucket->child = newtable;
+
+ info->maxmem += HASHNUM * sizeof(struct hashentry);
+ info->numchildren++;
+ if (info->maxdepth < depth + 1)
+ info->maxdepth = depth + 1;
+
+ printd("Leaving expand()\n\n\n");
+
+ return 1;
+}
+
+static inline int
+insert_do(struct hashtrie_info *info,
+ struct ip_conntrack_tuple *tuple,
+ hash_t hash)
+{
+ struct hashentry *insertbucket = NULL, *lockedbucket = NULL;
+ struct hashentry_stack bucketstack[MAXDEPTH];
+ unsigned int insertpos = 0, status = 0;
+ u8 maxdepth = 0;
+ hashbits_t insertbits = 0;
+
+ printd("\nEntering insert()\n");
+
+ printd("Inserting entry %p with hash: %x\n", tuple, hash);
+
+start:
+ hashtrie_iterate_hash(info, info->hashtrie, hash, {
+ bucketstack[depth].bucket = bucket;
+ bucketstack[depth].bucketnr = bucketnr;
+
+ maxdepth = depth;
+
+ if (!lockedbucket) {
+ lockedbucket = bucket;
+ spin_lock(&(lockedbucket->data.lock));
+ }
+ }, {
+ if (!bucket->data.members[slotnr]) {
+ if (insertbucket == NULL) {
+ insertbucket = bucket;
+ insertpos = slotnr;
+ insertbits = hashbits;
+ }
+ continue;
+ }
+ if (hashbits == (bucket->hashbits[slotnr] & HASHBITMASK) &&
+ ip_ct_tuple_equal(&tuple->tuple, &bucket->data.members[slotnr]->tuple)) {
+ printd("Error inserting duplicate entry, "
+ "original found at %u\n", slotnr);
+ spin_unlock(&lockedbucket->data.lock);
+ return 0;
+ }
+ });
+
+#ifdef NOT_SIMPLIFIED
+ if (force_evict) {
+ /* Walk backwards and evict the bucket if we havn't been able to evict anything
+ or if the bucket has the magic position in its hashtable, stop when we have
+ been able to evict something and the next bucket position isn't magic.
+ Should give somewhat fair distribution of evictions at the diffrent depths */
+ for (i = maxdepth; i >= 0; i--) {
+ if (!evicted || bucketstack[i].bucketnr == info->evictbucketnr) {
+ evicted += evict(info, bucketstack[i].bucket, i);
+ continue;
+ }
+ break;
+ }
+
+ if (!evicted) {
+ /* We failed */
+ printd("Eviction failed!\n");
+ spin_unlock(&lockedbucket->data.lock);
+ return 0;
+ }
+ force_evict = 0;
+ insertbucket = NULL;
+ goto start;
+ }
+#endif
+ /* Have we found a place to put our new entry? */
+ if (insertbucket == NULL) {
+ printd("Too many entries in bucket, needs expanding "
+ "(hashshift %u)\n", hashshift);
+ if (!expand(info, bucketstack[maxdepth].bucket, maxdepth)) {
+ spin_unlock(&lockedbucket->data.lock);
+ return 0;
+ }
+
+ goto start;
+ }
+
+ insertbucket->hashbits[insertpos] = insertbits | ((status & 1) << HASHBITS);
+ insertbucket->data.members[insertpos] = tuple;
+ tuple->hashpointer = &insertbucket->data.members[insertpos];
+
+ info->numentries++;
+
+ printd("Inserting entry in bucket %p at %u with hashbits %x\n",
+ insertbucket, insertpos, insertbits);
+
+ spin_unlock(&lockedbucket->data.lock);
+
+ printd("Leaving insert()\n\n\n");
+ return 1;
+}
+
+static int
+insert(struct table_info *table, struct ip_conntrack_generic *ct)
+{
+ struct hashtrie_info *info = (struct hashtrie_info *) table->data;
+ struct ip_conntrack *conntrack;
+
+ conntrack = malloc(sizeof(struct ip_conntrack));
+ if (!conntrack) {
+ printf("Can't allocate conntrack\n");
+ return 0;
+ }
+ memset(conntrack, 0, sizeof(*conntrack));
+ conntrack->tuple[IP_CT_DIR_ORIGINAL].tuple = ct->tuple[IP_CT_DIR_ORIGINAL];
+ conntrack->tuple[IP_CT_DIR_REPLY].tuple = ct->tuple[IP_CT_DIR_REPLY];
+
+ if (!(insert_do(info, &conntrack->tuple[IP_CT_DIR_ORIGINAL],
+ hash_tuple(&ct->tuple[IP_CT_DIR_ORIGINAL]))
+ && insert_do(info, &conntrack->tuple[IP_CT_DIR_REPLY],
+ hash_tuple(&ct->tuple[IP_CT_DIR_REPLY])))) {
+ return 0;
+ }
+ info->maxmem += sizeof(struct ip_conntrack);
+ ct->ct = conntrack;
+ return 1;
+}
+
+static int
+delete(struct table_info *table, struct ip_conntrack_generic *conntrack)
+{
+ struct hashtrie_info *info = (struct hashtrie_info *) table->data;
+ struct ip_conntrack *ct = (struct ip_conntrack *) conntrack->ct;
+
+ /* What about locking?
+ bucket_orig = hash_tuple(&ct->tuple[IP_CT_DIR_ORIGINAL]) & (HASHNUM - 1);
+ bucket_reply = hash_tuple(&ct->tuple[IP_CT_DIR_REPLY]) & (HASHNUM - 1);
+ */
+
+ *(ct->tuple[IP_CT_DIR_ORIGINAL].hashpointer) = NULL;
+ ct->tuple[IP_CT_DIR_ORIGINAL].hashpointer = NULL;
+ info->numentries--;
+ *(ct->tuple[IP_CT_DIR_REPLY].hashpointer) = NULL;
+ ct->tuple[IP_CT_DIR_REPLY].hashpointer = NULL;
+ info->numentries--;
+ info->maxmem -= sizeof(struct ip_conntrack);
+ free(ct);
+
+ return 1;
+}
+
+static void report(struct table_info *table)
+{
+ struct hashtrie_info *info = (struct hashtrie_info *) table->data;
+
+ printf("Number of entries: %u\n", info->numentries);
+ printf("Longest search: %u\n", info->longsearch);
+ printf("Required memory: %u\n", info->maxmem);
+ printf("Number of children: %u\n", info->numchildren);
+ printf("Maximal depth: %u\n", info->maxdepth);
+
+ info->longsearch = 0;
+}
+
+static int init(struct table_info *table, unsigned int hashsize)
+{
+ struct hashtrie_info *info;
+ unsigned int i, ret;
+
+ table->data = malloc(sizeof(struct hashtrie_info));
+ if (!table->data) {
+ printf("Error allocating hashtrie info data\n");
+ return 0;
+ }
+ memset(table->data, 0, sizeof(struct hashtrie_info));
+ info = (struct hashtrie_info *) table->data;
+
+ ret = posix_memalign((void *)&info->hashtrie, CACHELINE_REAL, HASHNUM * sizeof(struct hashentry));
+ if (ret != 0) {
+ printf("Error allocating hashtrie\n");
+ return 0;
+ }
+
+ memset(info->hashtrie, 0, HASHNUM * sizeof(struct hashentry));
+
+ info->evictbucketnr = rand() % HASHNUM;
+ info->maxmem = HASHNUM * sizeof(struct hashentry);
+
+ for (i = 0; i < HASHNUM; i++)
+ spin_lock_init(&info->hashtrie[i].data.lock);
+
+ return 1;
+}
+
+static int destroy(struct table_info *table)
+{
+ struct hashtrie_info *info = (struct hashtrie_info *) table->data;
+
+ if (info->numentries) {
+ printf("Error unregistering hashtrie, not empty. entries: %u\n", info->numentries);
+ return 0;
+ }
+ hashtrie_iterate_all(info, info->hashtrie, {
+ /* Job for RCU */
+ free(curtable[bucketnr].child);
+ curtable[bucketnr].child = NULL;
+ info->numchildren--;
+ }, {});
+
+ if (info->numentries || info->numchildren) {
+ printf("Error unregistering hashtrie, not empty. entries: %u children %u\n", info->numentries, info->numchildren);
+ return 0;
+ }
+
+ free(info->hashtrie);
+ free(info);
+
+ return 1;
+}
+
+#if HASHSHIFT == 2
+struct table_info hashtrie4_info = {
+ .name = "hashtrie4",
+#elif HASHSHIFT == 3
+struct table_info hashtrie8_info = {
+ .name = "hashtrie8",
+#elif HASHSHIFT == 4
+struct table_info hashtrie16_info = {
+ .name = "hashtrie16",
+#elif HASHSHIFT == 5
+struct table_info hashtrie32_info = {
+ .name = "hashtrie32",
+#else
+struct table_info hashtrie64_info = {
+ .name = "hashtrie64",
+#endif
+ .lookup = &lookup,
+ .insert = &insert,
+ .delete = &delete,
+ .report = &report,
+ .init = &init,
+ .destroy = &destroy,
+};
Copied: trunk/hashtrie/hashtrie.h (from rev 6559, trunk/hashtrie/newtable.h)
===================================================================
--- trunk/hashtrie/newtable.h 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/hashtrie.h 2006-03-28 12:14:46 UTC (rev 6560)
@@ -0,0 +1,63 @@
+#ifndef HASHTRIE_H
+#define HASHTRIE_H
+
+/* HASHNUM _must_ be 2^n */
+#ifndef HASHSHIFT
+#define HASHSHIFT 6
+#endif
+#define HASHNUM (1<<HASHSHIFT)
+
+#define HASHBITMASK ((1 << HASHBITS) - 1)
+#define HASHBITS 7
+#define STATUSBITMASK (1 << HASHBITS)
+
+#define HASHALIGN 32
+
+#define MAXDEPTH 12
+
+#define NUMENTRY ((HASHALIGN - sizeof(struct hashentry *)) / (sizeof(hashbits_t) + sizeof(struct ip_conntrack_tuple *)))
+#define PADNUM (HASHALIGN - sizeof(struct hashentry *) - NUMENTRY * (sizeof(hashbits_t) + sizeof(struct ip_conntrack_tuple *)))
+
+typedef u32 hash_t;
+typedef u8 hashbits_t;
+
+struct hashtrie_info {
+ struct hashentry *hashtrie;
+ unsigned int evictbucketnr;
+
+ unsigned int numchildren;
+ unsigned int numentries;
+ unsigned int maxdepth;
+ unsigned int longsearch;
+ unsigned int maxmem;
+ unsigned int insfail;
+};
+
+struct hashentry_stack {
+ struct hashentry *bucket;
+ u8 bucketnr;
+};
+
+struct ip_conntrack_tuple {
+ struct ip_conntrack_tuple **hashpointer;
+
+ struct ip_conntrack_tuple_generic tuple;
+};
+
+struct ip_conntrack
+{
+ struct ip_conntrack_tuple tuple[IP_CT_DIR_MAX];
+};
+
+struct hashentry {
+ unsigned char filler[PADNUM];
+ struct hashentry *child;
+ hashbits_t hashbits[NUMENTRY];
+ /* Assuming that the spinlock gets placed at the start of the union */
+ union {
+ spinlock_t lock;
+ struct ip_conntrack_tuple *members[NUMENTRY];
+ } data;
+} __attribute__((packed));
+
+#endif
Added: trunk/hashtrie/hashtrie_var.c
===================================================================
--- trunk/hashtrie/hashtrie_var.c 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/hashtrie_var.c 2006-03-28 12:14:46 UTC (rev 6560)
@@ -0,0 +1,493 @@
+#define _XOPEN_SOURCE 600
+#include <stdio.h>
+#include <string.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include "conntrack.h"
+#include "tables.h"
+#include "hashtrie_var.h"
+
+#if 0
+#define printd(args...) printf(args)
+#else
+#define printd(args...)
+#endif
+
+static unsigned int HASHSHIFT[7] =
+ {HASHSHIFT0, HASHSHIFT1, HASHSHIFT2,
+ HASHSHIFT2, HASHSHIFT2, HASHSHIFT2,
+ HASHSHIFT2};
+static int HASHNUM[7] =
+ {1<<HASHSHIFT0, 1<<HASHSHIFT1, 1<<HASHSHIFT2,
+ 1<<HASHSHIFT2, 1<<HASHSHIFT2, 1<<HASHSHIFT2,
+ 1<<HASHSHIFT2};
+
+/* Iterate over the buckets and their slots as we walk the tree
+ Provides bucketcode and slotcode with various variables:
+ curtable
+ bucket
+ bucketnr
+ slotnr
+ hashshift
+ hashbits
+ depth
+*/
+#define hashtrie_iterate_hash(info, table, hash, bucketcode_enter, slotcode) \
+ do { \
+ struct hashentry *curtable = table, *bucket; \
+ int hashshift = 0; \
+ hashbits_t hashbits; \
+ u8 depth = 0; \
+ unsigned int slotnr, bucketnr; \
+ unsigned int hnum, hshift; \
+ \
+ while (curtable) { \
+ hnum = HASHNUM[depth]; \
+ hshift = HASHSHIFT[depth]; \
+ bucketnr = (hash >> hashshift) & (hnum - 1); \
+ bucket = &curtable[bucketnr]; \
+ \
+ hashshift += hshift; \
+ /* FIXME: This is wrong */ \
+ if (hashshift > (sizeof(hash_t) * 8 - HASHBITS)) \
+ hashshift -= sizeof(hash_t) * 8 - HASHBITS; \
+ \
+ if (bucket->child) \
+ prefetchtest(&bucket->child[(hash >> hashshift) \
+ & (hnum - 1)]); \
+ \
+ hashbits = (hash >> hashshift) & HASHBITMASK; \
+ \
+ do { \
+ bucketcode_enter \
+ } while (0); \
+ \
+ /* We want to start at entry 1 for depth 0 \
+ and entry 0 for all other depths */ \
+ for (slotnr = !depth; slotnr < NUMENTRY; slotnr++) { \
+ do { \
+ slotcode \
+ } while (0); \
+ } \
+ \
+ depth++; \
+ curtable = bucket->child; \
+ if (info->longsearch < depth) \
+ info->longsearch = depth; \
+ } \
+ } while (0)
+
+#define hashtrie_iterate_all(info, table, bucketcode_leave, slotcode) \
+ do { \
+ struct hashentry *curtable = table, *bucket; \
+ struct hashentry_stack stack[MAXDEPTH]; \
+ u8 depth = 0; \
+ unsigned int slotnr, bucketnr = 0; \
+ unsigned int hnum = HASHNUM[0]; \
+ \
+ for (;;) { \
+ stack[depth].bucket = curtable; \
+ stack[depth].bucketnr = bucketnr; \
+ printd("Current depth: %u table: %p bucketnr: %u\n", depth, curtable, bucketnr); \
+ \
+ bucket = &curtable[bucketnr]; \
+ \
+ if (bucket->child) { \
+ depth++; \
+ if (info->longsearch < depth) \
+ info->longsearch = depth; \
+ bucketnr = 0; \
+ curtable = bucket->child; \
+ printd("Following child to depth: %u table: %p bucketnr: %u\n", depth, curtable, bucketnr); \
+ continue; \
+ } \
+ \
+ for (slotnr = !depth; slotnr < NUMENTRY; slotnr++) { \
+ do { \
+ slotcode \
+ } while (0); \
+ } \
+ \
+ bucketnr++; \
+ hnum = HASHNUM[depth]; \
+ if (bucketnr >= hnum) { \
+ if (depth == 0) \
+ break; \
+ depth--; \
+ curtable = stack[depth].bucket; \
+ bucketnr = stack[depth].bucketnr; \
+ \
+ do { \
+ bucketcode_leave \
+ } while (0); \
+ } \
+ } \
+ } while (0)
+
+static inline int
+lookup_do(struct hashtrie_info *info,
+ struct ip_conntrack_tuple_generic *tuple,
+ hash_t hash)
+{
+ printd("\nEntering lookup()\n");
+ printd("Looking up entry with hash: %x\n", hash);
+
+ hashtrie_iterate_hash(info, info->hashtrie, hash, {}, {
+ if (!bucket->data.members[slotnr])
+ continue;
+
+ printd("checking hashbits of %u\n", slotnr);
+ printd("current hashbits: %x\n",
+ bucket->hashbits[slotnr] & HASHBITMASK);
+
+ if (hashbits == (bucket->hashbits[slotnr] & HASHBITMASK) &&
+ ip_ct_tuple_equal(tuple, &bucket->data.members[slotnr]->tuple)) {
+ printd("Confirmed match %p at %u\n",
+ bucket->data.members[slotnr], slotnr);
+ return 1;
+ } else {
+ printd("Miss at %u\n", slotnr);
+ }
+ });
+
+ printd("Leaving lookup()\n\n\n");
+
+ return 0;
+}
+
+static int
+lookup(struct table_info *table, struct ip_conntrack_generic *ct)
+{
+ struct hashtrie_info *info = (struct hashtrie_info *) table->data;
+
+ return (lookup_do(info, &ct->tuple[IP_CT_DIR_ORIGINAL],
+ hash_tuple(&ct->tuple[IP_CT_DIR_ORIGINAL]))
+ && lookup_do(info, &ct->tuple[IP_CT_DIR_REPLY],
+ hash_tuple(&ct->tuple[IP_CT_DIR_REPLY])));
+}
+
+#ifdef NOT_SIMPLIFIED
+int alter(struct hashtrie_info *info, struct ip_conntrack_tuple *tuple, unsigned long status, hash_t hash)
+{
+ hashtrie_iterate_hash(info, info->hashtrie, hash, {}, {
+ if (!bucket->data.members[slotnr])
+ continue;
+
+ printd("checking hashbits of %u\n", slotnr);
+ printd("current hashbits: %x\n",
+ bucket->hashbits[slotnr] & HASHBITMASK);
+
+ if (hashbits == (bucket->hashbits[slotnr] & HASHBITMASK) &&
+ ip_ct_tuple_equal(tuple->tuple, bucket->data.members[slotnr].tuple)) {
+ printd("Confirmed match %p at %u\n",
+ bucket->data.members[slotnr], slotnr);
+ bucket->hashbits[slotnr] = hashbits | ((status & 1) << HASHBITS);
+ return 1;
+ } else {
+ printd("Miss at %u\n", slotnr);
+ }
+ });
+
+ printd("Leaving alter()\n\n\n");
+
+ return 0;
+}
+
+
+int evict(struct hashtrie_info *info, struct hashentry *bucket, u8 depth)
+{
+ unsigned int slotnr, evicted = 0;
+
+ printd("\nEntering evict()\n");
+ printd("Evicting from bucket %p at depth %u\n", bucket, depth);
+
+ /* We want to start at entry 1 for depth 0 and entry 0 for all other depths */
+ for (slotnr = !depth; slotnr < NUMENTRY; slotnr++) {
+ if (!bucket->data.members[slotnr])
+ continue;
+
+ /* Try to find an entry to evict */
+ if (!(bucket->hashbits[slotnr] & STATUSBITMASK)) {
+ /* This is just to make newtest.c happy, should be ripped out */
+ bucket->data.members[slotnr]->src.ip = 0;
+ bucket->data.members[slotnr]->dst.ip = 0;
+
+ delete(info, bucket->data.members[slotnr]);
+
+ evicted++;
+ }
+ }
+
+ printd("Leaving evict()\n\n\n");
+
+ return evicted;
+}
+#endif
+
+static inline unsigned int
+expand(struct hashtrie_info *info, struct hashentry *bucket, uint8_t depth)
+{
+ struct hashentry *newtable;
+ unsigned int ret;
+ unsigned int hashnum = HASHNUM[depth + 1];
+
+ printd("\nEntering expand(), depth %u\n", depth);
+
+ if (bucket->child) {
+ printf("expand: Error, expanding a bucket with children?\n");
+ return 0;
+ }
+
+ printd("expand: expanding bucket %p\n", bucket);
+
+ ret = posix_memalign((void *)&newtable, CACHELINE_REAL, hashnum * sizeof(struct hashentry));
+ if (ret != 0)
+ return 0;
+
+ memset(newtable, 0, hashnum * sizeof(struct hashentry));
+
+ printd("expand: Newtable: %p\n", newtable);
+
+ bucket->child = newtable;
+
+ info->maxmem += hashnum * sizeof(struct hashentry);
+ info->numchildren++;
+ if (info->maxdepth < depth + 1)
+ info->maxdepth = depth + 1;
+
+ printd("Leaving expand()\n\n\n");
+
+ return 1;
+}
+
+static inline int
+insert_do(struct hashtrie_info *info,
+ struct ip_conntrack_tuple *tuple,
+ hash_t hash)
+{
+ struct hashentry *insertbucket = NULL, *lockedbucket = NULL;
+ struct hashentry_stack bucketstack[MAXDEPTH];
+ unsigned int insertpos = 0, status = 0;
+ u8 maxdepth = 0;
+ hashbits_t insertbits = 0;
+
+ printd("\nEntering insert()\n");
+
+ printd("Inserting entry %p with hash: %x\n", tuple, hash);
+
+start:
+ hashtrie_iterate_hash(info, info->hashtrie, hash, {
+ bucketstack[depth].bucket = bucket;
+ bucketstack[depth].bucketnr = bucketnr;
+
+ maxdepth = depth;
+
+ if (!lockedbucket) {
+ lockedbucket = bucket;
+ spin_lock(&(lockedbucket->data.lock));
+ }
+ }, {
+ if (!bucket->data.members[slotnr]) {
+ if (insertbucket == NULL) {
+ insertbucket = bucket;
+ insertpos = slotnr;
+ insertbits = hashbits;
+ }
+ continue;
+ }
+ if (hashbits == (bucket->hashbits[slotnr] & HASHBITMASK) &&
+ ip_ct_tuple_equal(&tuple->tuple, &bucket->data.members[slotnr]->tuple)) {
+ printd("Error inserting duplicate entry, "
+ "original found at %u\n", slotnr);
+ spin_unlock(&lockedbucket->data.lock);
+ return 0;
+ }
+ });
+
+#ifdef NOT_SIMPLIFIED
+ if (force_evict) {
+ /* Walk backwards and evict the bucket if we havn't been able to evict anything
+ or if the bucket has the magic position in its hashtable, stop when we have
+ been able to evict something and the next bucket position isn't magic.
+ Should give somewhat fair distribution of evictions at the diffrent depths */
+ for (i = maxdepth; i >= 0; i--) {
+ if (!evicted || bucketstack[i].bucketnr == info->evictbucketnr) {
+ evicted += evict(info, bucketstack[i].bucket, i);
+ continue;
+ }
+ break;
+ }
+
+ if (!evicted) {
+ /* We failed */
+ printd("Eviction failed!\n");
+ spin_unlock(&lockedbucket->data.lock);
+ return 0;
+ }
+ force_evict = 0;
+ insertbucket = NULL;
+ goto start;
+ }
+#endif
+ /* Have we found a place to put our new entry? */
+ if (insertbucket == NULL) {
+ printd("Too many entries in bucket, needs expanding "
+ "(hashshift %u)\n", hashshift);
+ if (!expand(info, bucketstack[maxdepth].bucket, maxdepth)) {
+ spin_unlock(&lockedbucket->data.lock);
+ return 0;
+ }
+
+ goto start;
+ }
+
+ insertbucket->hashbits[insertpos] = insertbits | ((status & 1) << HASHBITS);
+ insertbucket->data.members[insertpos] = tuple;
+ tuple->hashpointer = &insertbucket->data.members[insertpos];
+
+ info->numentries++;
+
+ printd("Inserting entry in bucket %p at %u with hashbits %x\n",
+ insertbucket, insertpos, insertbits);
+
+ spin_unlock(&lockedbucket->data.lock);
+
+ printd("Leaving insert()\n\n\n");
+ return 1;
+}
+
+static int
+insert(struct table_info *table, struct ip_conntrack_generic *ct)
+{
+ struct hashtrie_info *info = (struct hashtrie_info *) table->data;
+ struct ip_conntrack *conntrack;
+
+ conntrack = malloc(sizeof(struct ip_conntrack));
+ if (!conntrack) {
+ printf("Can't allocate conntrack\n");
+ return 0;
+ }
+ memset(conntrack, 0, sizeof(*conntrack));
+ conntrack->tuple[IP_CT_DIR_ORIGINAL].tuple = ct->tuple[IP_CT_DIR_ORIGINAL];
+ conntrack->tuple[IP_CT_DIR_REPLY].tuple = ct->tuple[IP_CT_DIR_REPLY];
+
+ if (!(insert_do(info, &conntrack->tuple[IP_CT_DIR_ORIGINAL],
+ hash_tuple(&ct->tuple[IP_CT_DIR_ORIGINAL]))
+ && insert_do(info, &conntrack->tuple[IP_CT_DIR_REPLY],
+ hash_tuple(&ct->tuple[IP_CT_DIR_REPLY])))) {
+ return 0;
+ }
+ info->maxmem += sizeof(struct ip_conntrack);
+ ct->ct = conntrack;
+ return 1;
+}
+
+static int
+delete(struct table_info *table, struct ip_conntrack_generic *conntrack)
+{
+ struct hashtrie_info *info = (struct hashtrie_info *) table->data;
+ struct ip_conntrack *ct = (struct ip_conntrack *) conntrack->ct;
+
+ /* What about locking?
+ bucket_orig = hash_tuple(&ct->tuple[IP_CT_DIR_ORIGINAL]) & (HASHNUM - 1);
+ bucket_reply = hash_tuple(&ct->tuple[IP_CT_DIR_REPLY]) & (HASHNUM - 1);
+ */
+
+ *(ct->tuple[IP_CT_DIR_ORIGINAL].hashpointer) = NULL;
+ ct->tuple[IP_CT_DIR_ORIGINAL].hashpointer = NULL;
+ info->numentries--;
+ *(ct->tuple[IP_CT_DIR_REPLY].hashpointer) = NULL;
+ ct->tuple[IP_CT_DIR_REPLY].hashpointer = NULL;
+ info->numentries--;
+ info->maxmem -= sizeof(struct ip_conntrack);
+ free(ct);
+
+ return 1;
+}
+
+static void report(struct table_info *table)
+{
+ struct hashtrie_info *info = (struct hashtrie_info *) table->data;
+
+ printf("Number of entries: %u\n", info->numentries);
+ printf("Longest search: %u\n", info->longsearch);
+ printf("Required memory: %u\n", info->maxmem);
+ printf("Number of children: %u\n", info->numchildren);
+ printf("Maximal depth: %u\n", info->maxdepth);
+
+ info->longsearch = 0;
+}
+
+static int init(struct table_info *table, unsigned int hashsize)
+{
+ struct hashtrie_info *info;
+ unsigned int i, ret;
+
+ table->data = malloc(sizeof(struct hashtrie_info));
+ if (!table->data) {
+ printf("Error allocating hashtrie info data\n");
+ return 0;
+ }
+ memset(table->data, 0, sizeof(struct hashtrie_info));
+ info = (struct hashtrie_info *) table->data;
+
+ ret = posix_memalign((void *)&info->hashtrie, CACHELINE_REAL, HASHNUM[0] * sizeof(struct hashentry));
+ if (ret != 0) {
+ printf("Error allocating hashtrie\n");
+ return 0;
+ }
+
+ memset(info->hashtrie, 0, HASHNUM[0] * sizeof(struct hashentry));
+
+ info->evictbucketnr = rand() % HASHNUM[0];
+ info->maxmem = HASHNUM[0] * sizeof(struct hashentry);
+
+ for (i = 0; i < HASHNUM[0]; i++)
+ spin_lock_init(&info->hashtrie[i].data.lock);
+
+ return 1;
+}
+
+static int destroy(struct table_info *table)
+{
+ struct hashtrie_info *info = (struct hashtrie_info *) table->data;
+
+ if (info->numentries) {
+ printf("Error unregistering hashtrie, not empty. entries: %u\n", info->numentries);
+ return 0;
+ }
+ hashtrie_iterate_all(info, info->hashtrie, {
+ /* Job for RCU */
+ free(curtable[bucketnr].child);
+ curtable[bucketnr].child = NULL;
+ info->numchildren--;
+ }, {});
+
+ if (info->numentries || info->numchildren) {
+ printf("Error unregistering hashtrie, not empty. entries: %u children %u\n", info->numentries, info->numchildren);
+ return 0;
+ }
+
+ free(info->hashtrie);
+ free(info);
+
+ return 1;
+}
+
+#if HASHSHIFT0 == 14
+struct table_info hashtrie_var0_info = {
+ .name = "hashtrie-var0",
+#elif HASHSHIFT0 == 8
+struct table_info hashtrie_var1_info = {
+ .name = "hashtrie-var1",
+#else
+struct table_info hashtrie_var2_info = {
+ .name = "hashtrie-var2",
+#endif
+ .lookup = &lookup,
+ .insert = &insert,
+ .delete = &delete,
+ .report = &report,
+ .init = &init,
+ .destroy = &destroy,
+};
Added: trunk/hashtrie/hashtrie_var.h
===================================================================
--- trunk/hashtrie/hashtrie_var.h 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/hashtrie_var.h 2006-03-28 12:14:46 UTC (rev 6560)
@@ -0,0 +1,63 @@
+#ifndef HASHTRIE_VAR_H
+#define HASHTRIE_VAR_H
+
+/* HASHNUM _must_ be 2^n */
+/*
+#define HASHSHIFT 6
+#define HASHNUM (1<<HASHSHIFT)
+*/
+
+#define HASHBITMASK ((1 << HASHBITS) - 1)
+#define HASHBITS 7
+#define STATUSBITMASK (1 << HASHBITS)
+
+#define HASHALIGN 32
+
+#define MAXDEPTH 7
+
+#define NUMENTRY ((HASHALIGN - sizeof(struct hashentry *)) / (sizeof(hashbits_t) + sizeof(struct ip_conntrack_tuple *)))
+#define PADNUM (HASHALIGN - sizeof(struct hashentry *) - NUMENTRY * (sizeof(hashbits_t) + sizeof(struct ip_conntrack_tuple *)))
+
+typedef u32 hash_t;
+typedef u8 hashbits_t;
+
+struct hashtrie_info {
+ struct hashentry *hashtrie;
+ unsigned int evictbucketnr;
+
+ unsigned int numchildren;
+ unsigned int numentries;
+ unsigned int maxdepth;
+ unsigned int longsearch;
+ unsigned int maxmem;
+ unsigned int insfail;
+};
+
+struct hashentry_stack {
+ struct hashentry *bucket;
+ unsigned int bucketnr;
+};
+
+struct ip_conntrack_tuple {
+ struct ip_conntrack_tuple **hashpointer;
+
+ struct ip_conntrack_tuple_generic tuple;
+};
+
+struct ip_conntrack
+{
+ struct ip_conntrack_tuple tuple[IP_CT_DIR_MAX];
+};
+
+struct hashentry {
+ unsigned char filler[PADNUM];
+ struct hashentry *child;
+ hashbits_t hashbits[NUMENTRY];
+ /* Assuming that the spinlock gets placed at the start of the union */
+ union {
+ spinlock_t lock;
+ struct ip_conntrack_tuple *members[NUMENTRY];
+ } data;
+} __attribute__((packed));
+
+#endif
Deleted: trunk/hashtrie/newtable.c
===================================================================
--- trunk/hashtrie/newtable.c 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/newtable.c 2006-03-28 12:14:46 UTC (rev 6560)
@@ -1,469 +0,0 @@
-#define _XOPEN_SOURCE 600
-#include <stdio.h>
-#include <string.h>
-#include <stdint.h>
-#include <stdlib.h>
-#include "conntrack.h"
-#include "newtable.h"
-
-#if 0
-#define printd(args...) printf(args)
-#else
-#define printd(args...)
-#endif
-
-/* Iterate over the buckets and their slots as we walk the tree
- Provides bucketcode and slotcode with various variables:
- curtable
- bucket
- bucketnr
- slotnr
- hashshift
- hashbits
- depth
-*/
-#define hashtrie_iterate_hash(table, hash, bucketcode_enter, slotcode) \
- do { \
- struct hashentry *curtable = table, *bucket; \
- int hashshift = 0; \
- hashbits_t hashbits; \
- u8 depth = 0; \
- unsigned int slotnr, bucketnr; \
- \
- while (curtable) { \
- bucketnr = (hash >> hashshift) & (HASHNUM - 1); \
- bucket = &curtable[bucketnr]; \
- \
- hashshift += HASHSHIFT; \
- /* FIXME: This is wrong */ \
- if (hashshift > (sizeof(hash_t) * 8 - HASHBITS)) \
- hashshift -= sizeof(hash_t) * 8 - HASHBITS; \
- \
- if (bucket->child) \
- prefetchtest(&bucket->child[(hash >> hashshift) \
- & (HASHNUM - 1)]); \
- \
- hashbits = (hash >> hashshift) & HASHBITMASK; \
- \
- do { \
- bucketcode_enter \
- } while (0); \
- \
- /* We want to start at entry 1 for depth 0 \
- and entry 0 for all other depths */ \
- for (slotnr = !depth; slotnr < NUMENTRY; slotnr++) { \
- do { \
- slotcode \
- } while (0); \
- } \
- \
- depth++; \
- curtable = bucket->child; \
- } \
- } while (0)
-
-#define hashtrie_iterate_all(table, bucketcode_leave, slotcode) \
- do { \
- struct hashentry *curtable = table, *bucket; \
- struct hashentry_stack stack[MAXDEPTH]; \
- u8 depth = 0; \
- unsigned int slotnr, bucketnr = 0; \
- \
- for (;;) { \
- stack[depth].bucket = curtable; \
- stack[depth].bucketnr = bucketnr; \
- printd("Current depth: %u table: %p bucketnr: %u\n", depth, curtable, bucketnr); \
- \
- bucket = &curtable[bucketnr]; \
- \
- if (bucket->child) { \
- depth++; \
- bucketnr = 0; \
- curtable = bucket->child; \
- printd("Following child to depth: %u table: %p bucketnr: %u\n", depth, curtable, bucketnr); \
- continue; \
- } \
- \
- for (slotnr = !depth; slotnr < NUMENTRY; slotnr++) { \
- do { \
- slotcode \
- } while (0); \
- } \
- \
- bucketnr++; \
- if (bucketnr >= HASHNUM) { \
- if (depth == 0) \
- break; \
- depth--; \
- curtable = stack[depth].bucket; \
- bucketnr = stack[depth].bucketnr; \
- \
- do { \
- bucketcode_leave \
- } while (0); \
- } \
- } \
- } while (0)
-
-struct ip_conntrack *lookup(struct hashtrie_info *info, struct ip_conntrack_tuple *tuple, hash_t hash)
-{
- printd("\nEntering lookup()\n");
- printd("Looking up entry with hash: %x\n", hash);
-
- hashtrie_iterate_hash(info->hashtrie, hash, {}, {
- if (!bucket->data.members[slotnr])
- continue;
-
- printd("checking hashbits of %u\n", slotnr);
- printd("current hashbits: %x\n",
- bucket->hashbits[slotnr] & HASHBITMASK);
-
- if (hashbits == (bucket->hashbits[slotnr] & HASHBITMASK) &&
- ip_ct_tuple_equal(tuple, bucket->data.members[slotnr])) {
- printd("Confirmed match %p at %u\n",
- bucket->data.members[slotnr], slotnr);
- return container_of(bucket->data.members[slotnr], struct ip_conntrack, tuple[bucket->data.members[slotnr]->dst.dir]);
- } else {
- printd("Miss at %u\n", slotnr);
- }
- });
-
- printd("Leaving lookup()\n\n\n");
-
- return NULL;
-}
-
-int alter(struct hashtrie_info *info, struct ip_conntrack_tuple *tuple, unsigned long status, hash_t hash)
-{
- hashtrie_iterate_hash(info->hashtrie, hash, {}, {
- if (!bucket->data.members[slotnr])
- continue;
-
- printd("checking hashbits of %u\n", slotnr);
- printd("current hashbits: %x\n",
- bucket->hashbits[slotnr] & HASHBITMASK);
-
- if (hashbits == (bucket->hashbits[slotnr] & HASHBITMASK) &&
- ip_ct_tuple_equal(tuple, bucket->data.members[slotnr])) {
- printd("Confirmed match %p at %u\n",
- bucket->data.members[slotnr], slotnr);
- bucket->hashbits[slotnr] = hashbits | ((status & 1) << HASHBITS);
- return 1;
- } else {
- printd("Miss at %u\n", slotnr);
- }
- });
-
- printd("Leaving alter()\n\n\n");
-
- return 0;
-}
-
-
-int evict(struct hashtrie_info *info, struct hashentry *bucket, u8 depth)
-{
- unsigned int slotnr, evicted = 0;
-
- printd("\nEntering evict()\n");
- printd("Evicting from bucket %p at depth %u\n", bucket, depth);
-
- /* We want to start at entry 1 for depth 0 and entry 0 for all other depths */
- for (slotnr = !depth; slotnr < NUMENTRY; slotnr++) {
- if (!bucket->data.members[slotnr])
- continue;
-
- /* Try to find an entry to evict */
- if (!(bucket->hashbits[slotnr] & STATUSBITMASK)) {
- /* This is just to make newtest.c happy, should be ripped out */
- bucket->data.members[slotnr]->src.ip = 0;
- bucket->data.members[slotnr]->dst.ip = 0;
-
- delete(info, bucket->data.members[slotnr]);
-
- evicted++;
- }
- }
-
- printd("Leaving evict()\n\n\n");
-
- return evicted;
-}
-
-inline unsigned int expand(struct hashtrie_info *info, struct hashentry *bucket, uint8_t depth)
-{
- struct hashentry *newtable;
- unsigned int ret;
-
- printd("\nEntering expand()\n");
-
- if (bucket->child) {
- printf("expand: Error, expanding a bucket with children?\n");
- return 0;
- }
-
- printd("expand: expanding bucket %p\n", bucket);
-
- ret = posix_memalign((void *)&newtable, CACHELINE_REAL, HASHNUM * sizeof(struct hashentry));
- if (ret != 0)
- return 0;
-
- memset(newtable, 0, HASHNUM * sizeof(struct hashentry));
-
- printd("expand: Newtable: %p\n", newtable);
-
- bucket->child = newtable;
-
- info->maxmem += HASHNUM * sizeof(struct hashentry);
- info->numchildren++;
- if (info->maxdepth < depth + 1)
- info->maxdepth = depth + 1;
-
- printd("Leaving expand()\n\n\n");
-
- return 1;
-}
-
-int insert(struct hashtrie_info *info, struct ip_conntrack_tuple *tuple, unsigned long status, hash_t hash, unsigned int force_evict)
-{
- struct hashentry *insertbucket = NULL, *lockedbucket = NULL;
- struct hashentry_stack bucketstack[MAXDEPTH];
- unsigned int insertpos = 0, evicted = 0;
- int i;
- u8 maxdepth = 0;
- hashbits_t insertbits = 0;
-
- printd("\nEntering insert()\n");
-
- printd("Inserting entry %p with hash: %x\n", tuple, hash);
-
-start:
- hashtrie_iterate_hash(info->hashtrie, hash, {
- bucketstack[depth].bucket = bucket;
- bucketstack[depth].bucketnr = bucketnr;
-
- maxdepth = depth;
-
- if (!lockedbucket) {
- lockedbucket = bucket;
- spin_lock(&(lockedbucket->data.lock));
- }
- }, {
- if (!bucket->data.members[slotnr]) {
- if (insertbucket == NULL) {
- insertbucket = bucket;
- insertpos = slotnr;
- insertbits = hashbits;
- }
- continue;
- }
- if (hashbits == (bucket->hashbits[slotnr] & HASHBITMASK) &&
- ip_ct_tuple_equal(tuple, bucket->data.members[slotnr])) {
- printd("Error inserting duplicate entry, "
- "original found at %u\n", slotnr);
- spin_unlock(&lockedbucket->data.lock);
- return 0;
- }
- });
-
- if (force_evict) {
- /* Walk backwards and evict the bucket if we havn't been able to evict anything
- or if the bucket has the magic position in its hashtable, stop when we have
- been able to evict something and the next bucket position isn't magic.
- Should give somewhat fair distribution of evictions at the diffrent depths */
- for (i = maxdepth; i >= 0; i--) {
- if (!evicted || bucketstack[i].bucketnr == info->evictbucketnr) {
- evicted += evict(info, bucketstack[i].bucket, i);
- continue;
- }
- break;
- }
-
- if (!evicted) {
- /* We failed */
- printd("Eviction failed!\n");
- spin_unlock(&lockedbucket->data.lock);
- return 0;
- }
- force_evict = 0;
- insertbucket = NULL;
- goto start;
- }
-
- /* Have we found a place to put our new entry? */
- if (insertbucket == NULL) {
- printd("Too many entries in bucket, needs expanding "
- "(hashshift %u)\n", hashshift);
- if (!expand(info, bucketstack[maxdepth].bucket, maxdepth)) {
- spin_unlock(&lockedbucket->data.lock);
- return 0;
- }
-
- goto start;
- }
-
- insertbucket->hashbits[insertpos] = insertbits | ((status & 1) << HASHBITS);
- insertbucket->data.members[insertpos] = tuple;
- tuple->hashpointer = &insertbucket->data.members[insertpos];
-
- info->numentries++;
-
- printd("Inserting entry in bucket %p at %u with hashbits %x\n",
- insertbucket, insertpos, insertbits);
-
- spin_unlock(&lockedbucket->data.lock);
-
- printd("Leaving insert()\n\n\n");
- return 1;
-}
-
-inline void delete(struct hashtrie_info *info, struct ip_conntrack_tuple *tuple)
-{
- *tuple->hashpointer = NULL;
- tuple->hashpointer = NULL;
- info->numentries--;
-}
-
-int allocate_hashtrie(struct hashtrie_info *info)
-{
- unsigned int i, ret;
-
- ret = posix_memalign((void *)&info->hashtrie, CACHELINE_REAL, HASHNUM * sizeof(struct hashentry));
- if (ret != 0) {
- printf("Error allocating hashtrie\n");
- return 0;
- }
-
- memset(info->hashtrie, 0, HASHNUM * sizeof(struct hashentry));
-
- info->evictbucketnr = rand() % HASHNUM;
-
- for (i = 0; i < HASHNUM; i++)
- spin_lock_init(&info->hashtrie[i].data.lock);
-
- return 1;
-}
-
-int free_hashtrie(struct hashtrie_info *info)
-{
- hashtrie_iterate_all(info->hashtrie, {
- /* Job for RCU */
- free(curtable[bucketnr].child);
- curtable[bucketnr].child = NULL;
- info->numchildren--;
- }, {
- if (!bucket->data.members[slotnr])
- continue;
-
- delete(info, bucket->data.members[slotnr]);
- });
-
- if (info->numentries || info->numchildren) {
- printf("Error unregistering hashtrie, not empty. entries: %u children %u\n", info->numentries, info->numchildren);
- return 0;
- }
-
- free(info->hashtrie);
-
- return 1;
-}
-
-void debug_hashtrie(struct hashtrie_info *info)
-{
- struct hashentry *curtable = info->hashtrie, *bucket;
- struct hashentry_stack stack[MAXDEPTH];
- struct hashtrie_debug debug[MAXDEPTH];
- u8 depth = 0;
- unsigned int slotnr, bucketnr = 0;
- unsigned int numentries;
- int i;
-
- for (i = 0; i < MAXDEPTH; i++) {
- debug[i].numchildren = 0;
- debug[i].numbuckets = 0;
- debug[i].numentries = 0;
- debug[i].nfbuckets = 0;
- }
-
- for (;;) {
- stack[depth].bucket = curtable;
- stack[depth].bucketnr = bucketnr;
- printd("Current depth: %u table: %p bucketnr: %u\n", depth, curtable, bucketnr);
-
- bucket = &curtable[bucketnr];
-
- if (bucket->child) {
- debug[depth].numchildren++;
- depth++;
- bucketnr = 0;
- curtable = bucket->child;
- printd("Following child to depth: %u table: %p bucketnr: %u\n", depth, curtable, bucketnr);
- continue;
- }
-
- debug[depth].numbuckets++;
-
- numentries = 0;
- for (slotnr = !depth; slotnr < NUMENTRY; slotnr++) {
- if (!bucket->data.members[slotnr])
- continue;
-
- numentries++;
- delete(info, bucket->data.members[slotnr]);
- }
- debug[depth].numentries += numentries;
-
- if (numentries != NUMENTRY - !depth) {
- debug[depth].nfbuckets++;
- }
-
- bucketnr++;
- if (bucketnr >= HASHNUM) {
- if (depth == 0)
- break;
- depth--;
- curtable = stack[depth].bucket;
- bucketnr = stack[depth].bucketnr;
-
-
- free(curtable[bucketnr].child);
- curtable[bucketnr].child = NULL;
- info->numchildren--;
- //bucketcode_leave
- }
- }
-
- printf("ip_conntrack_hash_rnd - %u\n", ip_conntrack_hash_rnd);
-
- printf("Statistics:\n");
- for (i = MAXDEPTH - 1; i >= 0; i--) {
- int subentries = 0, j, fullbuckets, nfratio = 0, ofratio = 0, ratio = 0;
-
- if (!debug[i].numbuckets)
- continue;
-
- if (i < MAXDEPTH - 1) {
- for (j = i + 1; j < MAXDEPTH; j++) {
- subentries += debug[j].numentries;
- }
- }
-
- fullbuckets = debug[i].numbuckets - debug[i].numchildren - debug[i].nfbuckets;
-
- if (debug[i].nfbuckets)
- nfratio = 100 * (debug[i].numentries - (fullbuckets + debug[i].numchildren) * ((NUMENTRY) - !i)) / (debug[i].nfbuckets * ((NUMENTRY) - !i));
-
- if (debug[i].numchildren)
- ofratio = 100 * (subentries + (debug[i].numchildren * ((NUMENTRY) - !i))) / (debug[i].numchildren * ((NUMENTRY) - !i));
-
- ratio = 100 * debug[i].numentries / (debug[i].numbuckets * ((NUMENTRY) - !i));
-
- printf("Depth %i:\n", i);
- printf("\tnumber of entries: %i\n", debug[i].numentries);
- printf("\tnumber of buckets: %i (%i%%)\n", debug[i].numbuckets, ratio);
- printf("\t\tsubentries: %i\n", subentries);
- printf("\t\tnot full buckets: %i (%i%%)\n", debug[i].nfbuckets, nfratio);
- printf("\t\tfull buckets: %i (100%%)\n", fullbuckets);
- printf("\t\toverfull buckets / children: %i (%i%%)\n", debug[i].numchildren, ofratio);
- printf("\n");
- }
-}
Deleted: trunk/hashtrie/newtable.h
===================================================================
--- trunk/hashtrie/newtable.h 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/newtable.h 2006-03-28 12:14:46 UTC (rev 6560)
@@ -1,66 +0,0 @@
-#ifndef NEWTABLE_H
-#define NEWTABLE_H
-
-/* HASHNUM _must_ be 2^n */
-#define HASHNUM (1<<HASHSHIFT)
-#define HASHSHIFT 6
-
-#define HASHBITMASK ((1 << HASHBITS) - 1)
-#define HASHBITS 7
-#define STATUSBITMASK (1 << HASHBITS)
-
-#define HASHALIGN 32
-
-#define MAXDEPTH 7
-
-#define NUMENTRY ((HASHALIGN - sizeof(struct hashentry *)) / (sizeof(hashbits_t) + sizeof(struct ip_conntrack_tuple *)))
-#define PADNUM (HASHALIGN - sizeof(struct hashentry *) - NUMENTRY * (sizeof(hashbits_t) + sizeof(struct ip_conntrack_tuple *)))
-
-typedef u32 hash_t;
-typedef u8 hashbits_t;
-
-struct hashtrie_info {
- struct hashentry *hashtrie;
- unsigned int evictbucketnr;
-
- unsigned int numchildren;
- unsigned int numentries;
- unsigned int maxdepth;
- unsigned int maxmem;
- unsigned int insfail;
-};
-
-struct hashentry_stack {
- struct hashentry *bucket;
- u8 bucketnr;
-};
-
-struct hashtrie_debug {
- unsigned int numbuckets;
- unsigned int numentries;
- unsigned int numchildren;
- unsigned int nfbuckets;
-};
-
-struct hashentry {
- unsigned char filler[PADNUM];
- struct hashentry *child;
- hashbits_t hashbits[NUMENTRY];
- /* Assuming that the spinlock gets placed at the start of the union */
- union {
- spinlock_t lock;
- struct ip_conntrack_tuple *members[NUMENTRY];
- } data;
-} __attribute__((packed));
-
-struct ip_conntrack *lookup(struct hashtrie_info *, struct ip_conntrack_tuple *tuple, hash_t hash);
-int alter(struct hashtrie_info *, struct ip_conntrack_tuple *tuple, unsigned long status, hash_t hash);
-int insert(struct hashtrie_info *, struct ip_conntrack_tuple *tuple, unsigned long status, hash_t hash, unsigned int evict);
-inline void delete(struct hashtrie_info *, struct ip_conntrack_tuple *tuple);
-
-int allocate_hashtrie(struct hashtrie_info *);
-int free_hashtrie(struct hashtrie_info *);
-
-void debug_hashtrie(struct hashtrie_info *info);
-
-#endif
Deleted: trunk/hashtrie/newtest.c
===================================================================
--- trunk/hashtrie/newtest.c 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/newtest.c 2006-03-28 12:14:46 UTC (rev 6560)
@@ -1,386 +0,0 @@
-#define _XOPEN_SOURCE 600
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-#include <stdint.h>
-#include <stdlib.h>
-#include "rdtsc2.c"
-#include "conntrack.h"
-#include "newtable.h"
-
-#define TESTNUM 100*1024
-#define EVICTNUM 300*1024
-
-#if 0
-#define REVINSFROM (TESTNUM/2)
-#define REVINSTO (TESTNUM)
-#else
-#define REVINSFROM 0
-#define REVINSTO (TESTNUM/2)
-#endif
-
-int main(void)
-{
- struct ip_conntrack **conntrack, **conntrack2, *retp;
- unsigned int ret, ret2, found = 0, notfound = 0;
- int i, dir, evicting;
- struct hashtrie_info info;
-
- rdtsc_cal(100000000);
-
- printf("sizeof struct hashentry: %u\n", sizeof(struct hashentry));
- printf("sizeof struct ip_conntrack: %u\n", sizeof(struct ip_conntrack));
- printf("number of conntrack entries: %u\n", TESTNUM);
- printf("number of slots per hashtrie bucket: %u\n", NUMENTRY);
- printf("number of pad bytes: %u\n", PADNUM);
- printf("number of bytes per child: %u\n", sizeof(struct hashentry) * HASHNUM);
-
- memset(&info, 0, sizeof(struct hashtrie_info));
-
- if (!allocate_hashtrie(&info)) {
- printf("Error registering hashtrie\n");
- return 1;
- }
-
- posix_memalign((void *)&conntrack, CACHELINE_REAL, sizeof(struct ip_conntrack *) * TESTNUM);
- //conntrack = (void *)malloc(sizeof(struct ip_conntrack *) * TESTNUM);
- if (!conntrack) {
- printf("Couldn't allocate conntracks\n");
- free_hashtrie(&info);
- return 1;
- }
-
- //memset(conntrack, 0, sizeof(struct ip_conntrack) * TESTNUM);
-
- posix_memalign((void *)&conntrack2, CACHELINE_REAL, sizeof(struct ip_conntrack *) * TESTNUM);
- //conntrack2 = (void *)malloc(sizeof(struct ip_conntrack *) * TESTNUM);
- if (!conntrack2) {
- printf("Couldn't allocate conntracks2\n");
- free_hashtrie(&info);
- return 1;
- }
- //memset(conntrack2, 0, sizeof(struct ip_conntrack) * TESTNUM);
-
- srand((int)time(NULL));
-
- ip_conntrack_hash_rnd = rand();
-
- for (i = 0; i < TESTNUM; i++) {
- //posix_memalign(&conntrack[i], CACHELINE_REAL, sizeof(struct ip_conntrack));
- conntrack[i] = malloc(sizeof(struct ip_conntrack));
- if (!conntrack[i]) {
- printf("Couldn't allocate conntrack\n");
- free_hashtrie(&info);
- return 1;
- }
- conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].src.ip = rand();
- conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].src.u.tcp.port = (u16)rand();
- conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.ip = rand();
- conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.u.tcp.port = (u16)rand();
- conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.protonum = 6;
- conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.dir = IP_CT_DIR_ORIGINAL;
-
- conntrack[i]->tuple[IP_CT_DIR_REPLY].src.ip = conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.ip;
- conntrack[i]->tuple[IP_CT_DIR_REPLY].src.u.tcp.port = conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.u.tcp.port;
- conntrack[i]->tuple[IP_CT_DIR_REPLY].dst.ip = conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].src.ip;
- conntrack[i]->tuple[IP_CT_DIR_REPLY].dst.u.tcp.port = conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].src.u.tcp.port;
- conntrack[i]->tuple[IP_CT_DIR_REPLY].dst.protonum = 6;
- conntrack[i]->tuple[IP_CT_DIR_REPLY].dst.dir = IP_CT_DIR_REPLY;
-
- //posix_memalign(&conntrack2[i], CACHELINE_REAL, sizeof(struct ip_conntrack));
- conntrack2[i] = malloc(sizeof(struct ip_conntrack));
- if (!conntrack2[i]) {
- printf("Couldn't allocate conntrack2\n");
- free_hashtrie(&info);
- return 1;
- }
- conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].src.ip = rand();
- conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].src.u.tcp.port = (u16)rand();
- conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].dst.ip = rand();
- conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].dst.u.tcp.port = (u16)rand();
- conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].dst.protonum = 6;
- conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].dst.dir = IP_CT_DIR_ORIGINAL;
-
- conntrack2[i]->tuple[IP_CT_DIR_REPLY].src.ip = conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].dst.ip;
- conntrack2[i]->tuple[IP_CT_DIR_REPLY].src.u.tcp.port = conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].dst.u.tcp.port;
- conntrack2[i]->tuple[IP_CT_DIR_REPLY].dst.ip = conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].src.ip;
- conntrack2[i]->tuple[IP_CT_DIR_REPLY].dst.u.tcp.port = conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].src.u.tcp.port;
- conntrack2[i]->tuple[IP_CT_DIR_REPLY].dst.protonum = 6;
- conntrack2[i]->tuple[IP_CT_DIR_REPLY].dst.dir = IP_CT_DIR_REPLY;
- }
-
- for (i = 0; i < TESTNUM; i++) {
- evicting = 0;
- if (info.numentries > EVICTNUM) /* two entries in hashtrie per conntrack */
- evicting = 1;
- TIMER(
- ret = insert(&info, &conntrack[i]->tuple[IP_CT_DIR_ORIGINAL], 0, hash_tuple(&conntrack[i]->tuple[IP_CT_DIR_ORIGINAL]), evicting);
- ret2 = insert(&info, &conntrack[i]->tuple[IP_CT_DIR_REPLY], 0, hash_tuple(&conntrack[i]->tuple[IP_CT_DIR_REPLY]), evicting);
- );
- if (!ret || !ret2) {
- //printf("Couldn't insert entry %p\n", &conntrack[i]);
- if (!ret) {
- conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].src.ip = conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.ip = 0;
- info.insfail++;
- }
- if (!ret2) {
- conntrack[i]->tuple[IP_CT_DIR_REPLY].src.ip = conntrack[i]->tuple[IP_CT_DIR_REPLY].dst.ip = 0;
- info.insfail++;
- }
- total_time -= code_timer;
- total_count--;
- }
- }
-
- printf("insert: ");
- print_timer();
-
- printf("Number of failed inserts: %u\n", info.insfail);
- printf("Number of entries in hashtrie: %u\n", info.numentries);
- printf("Number of children in hashtrie: %u\n", info.numchildren);
- printf("Maxdepth of hashtrie: %u (0 == root)\n", info.maxdepth);
- printf("Maximum memory usage: %u\n", info.maxmem);
- printf("Maximum memory usage per entry: %u\n", info.maxmem / info.numentries);
-
- total_count = 0;
- total_time = 0;
-
- for (dir = 0; dir < IP_CT_DIR_MAX; dir++) {
- for (i = 0; i < TESTNUM; i++) {
- if (conntrack[i]->tuple[dir].src.ip && conntrack[i]->tuple[dir].dst.ip) {
- TIMER(ret = alter(&info, &conntrack[i]->tuple[dir], i % 2, hash_tuple(&conntrack[i]->tuple[dir])););
- if (!ret) {
- printf("Couldn't alter entry %p, dir: %u, i: %u\n", conntrack[i], dir, i);
- return 1;
- }
- }
- }
- }
-
- printf("alter: ");
- print_timer();
-
- total_count = 0;
- total_time = 0;
-
- for (dir = 0; dir < IP_CT_DIR_MAX; dir++) {
- for (i = 0; i < TESTNUM; i++) {
- if (conntrack[i]->tuple[dir].src.ip && conntrack[i]->tuple[dir].dst.ip) {
- TIMER(retp = lookup(&info, &conntrack[i]->tuple[dir], hash_tuple(&conntrack[i]->tuple[dir])););
- if (retp != conntrack[i]) {
- printf("Couldn't find entry %p, dir: %u, i: %u\n", conntrack[i], dir, i);
- return 1;
- }
- }
- }
- }
-
- printf("lookup: ");
- print_timer();
-
- total_count = 0;
- total_time = 0;
-
- for (dir = IP_CT_DIR_MAX - 1; dir >= 0; dir--) {
- for (i = TESTNUM - 1; i >= 0; i--) {
- if (conntrack[i]->tuple[dir].src.ip && conntrack[i]->tuple[dir].dst.ip) {
- TIMER(retp = lookup(&info, &conntrack[i]->tuple[dir], hash_tuple(&conntrack[i]->tuple[dir])););
- if (retp != conntrack[i]) {
- printf("Couldn't find entry %p, dir: %u, i: %u\n", conntrack[i], dir, i);
- return 1;
- }
- }
- }
- }
-
- printf("lookup (reverse): ");
- print_timer();
-
- total_count = 0;
- total_time = 0;
-
- for (dir = 0; dir < IP_CT_DIR_MAX; dir++) {
- for (i = 0; i < TESTNUM; i++) {
- if (conntrack2[i]->tuple[dir].src.ip && conntrack2[i]->tuple[dir].dst.ip) {
- TIMER(retp = lookup(&info, &conntrack2[i]->tuple[dir], hash_tuple(&conntrack2[i]->tuple[dir])););
- if (retp == conntrack2[i])
- found++;
- else
- notfound++;
- }
- }
- }
-
- printf("lookup (nomatch): ");
- print_timer();
- printf("Found entries in hashtrie: %d\n", found);
- printf("Not found entries in hashtrie: %d\n", notfound);
-
- total_count = 0;
- total_time = 0;
-
- for (i = 0; i < TESTNUM; i++) {
- if (conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].src.ip && conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.ip &&
- conntrack[i]->tuple[IP_CT_DIR_REPLY].src.ip && conntrack[i]->tuple[IP_CT_DIR_REPLY].dst.ip) {
- TIMER(
- delete(&info, &conntrack[i]->tuple[IP_CT_DIR_ORIGINAL]);
- delete(&info, &conntrack[i]->tuple[IP_CT_DIR_REPLY]);
- );
- }
- }
-
- printf("delete: ");
- print_timer();
-
- total_count = 0;
- total_time = 0;
-
- info.insfail = 0;
-
- for (i = 0; i < TESTNUM; i++) {
- evicting = 0;
- if (info.numentries > EVICTNUM) /* two entries in hashtrie per conntrack */
- evicting = 1;
- TIMER(
- ret = insert(&info, &conntrack[i]->tuple[IP_CT_DIR_ORIGINAL], 1, hash_tuple(&conntrack[i]->tuple[IP_CT_DIR_ORIGINAL]), evicting);
- ret2 = insert(&info, &conntrack[i]->tuple[IP_CT_DIR_REPLY], 1, hash_tuple(&conntrack[i]->tuple[IP_CT_DIR_REPLY]), evicting);
- );
- if (!ret || !ret2) {
- //printf("Couldn't insert entry %p\n", &conntrack[i]);
- if (!ret) {
- conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].src.ip = conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.ip = 0;
- info.insfail++;
- }
- if (!ret2) {
- conntrack[i]->tuple[IP_CT_DIR_REPLY].src.ip = conntrack[i]->tuple[IP_CT_DIR_REPLY].dst.ip = 0;
- info.insfail++;
- }
- total_time -= code_timer;
- total_count--;
- info.insfail++;
- }
- }
-
- printf("insert2: ");
- print_timer();
-
- printf("Number of failed inserts: %u\n", info.insfail);
- printf("Number of entries in hashtrie: %u\n", info.numentries);
- printf("Number of children in hashtrie: %u\n", info.numchildren);
- printf("Maxdepth of hashtrie: %u (0 == root)\n", info.maxdepth);
- printf("Maximum memory usage: %u\n", info.maxmem);
- printf("Maximum memory usage per entry: %u\n", info.maxmem / info.numentries);
-
- printf("Removing entries between %u and %u.\n", REVINSFROM, REVINSTO - 1);
- for (i = REVINSFROM; i < REVINSTO; i++) {
- if (conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].src.ip && conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.ip &&
- conntrack[i]->tuple[IP_CT_DIR_REPLY].src.ip && conntrack[i]->tuple[IP_CT_DIR_REPLY].dst.ip) {
- delete(&info, &conntrack[i]->tuple[IP_CT_DIR_ORIGINAL]);
- delete(&info, &conntrack[i]->tuple[IP_CT_DIR_REPLY]);
- }
- }
-
- total_count = 0;
- total_time = 0;
-
- info.insfail = 0;
-
- printf("Adding entries between %u and %u.\n", REVINSTO - 1, REVINSFROM);
- for (i = REVINSTO - 1; i >= REVINSFROM; i--) {
- evicting = 0;
- if (info.numentries > EVICTNUM) /* two entries in hashtrie per conntrack */
- evicting = 1;
- TIMER(
- ret = insert(&info, &conntrack[i]->tuple[IP_CT_DIR_ORIGINAL], 1, hash_tuple(&conntrack[i]->tuple[IP_CT_DIR_ORIGINAL]), evicting);
- ret2 = insert(&info, &conntrack[i]->tuple[IP_CT_DIR_REPLY], 1, hash_tuple(&conntrack[i]->tuple[IP_CT_DIR_REPLY]), evicting);
- );
- if (!ret || !ret2) {
- //printf("Couldn't insert entry %p\n", &conntrack[i]);
- if (!ret) {
- conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].src.ip = conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.ip = 0;
- info.insfail++;
- }
- if (!ret2) {
- conntrack[i]->tuple[IP_CT_DIR_REPLY].src.ip = conntrack[i]->tuple[IP_CT_DIR_REPLY].dst.ip = 0;
- info.insfail++;
- }
- total_time -= code_timer;
- total_count--;
- info.insfail++;
- }
- }
-
- printf("insert (half reverse): ");
- print_timer();
-
- printf("Number of failed inserts: %u\n", info.insfail);
- printf("Number of entries in hashtrie: %u\n", info.numentries);
- printf("Number of children in hashtrie: %u\n", info.numchildren);
- printf("Maxdepth of hashtrie: %u (0 == root)\n", info.maxdepth);
- printf("Maximum memory usage: %u\n", info.maxmem);
- printf("Maximum memory usage per entry: %u\n", info.maxmem / info.numentries);
-
- printf("Removing every other entry from 0 to %u\n", TESTNUM - 1);
- for (i = 0; i < TESTNUM; i += 2) {
- if (conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].src.ip && conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.ip &&
- conntrack[i]->tuple[IP_CT_DIR_REPLY].src.ip && conntrack[i]->tuple[IP_CT_DIR_REPLY].dst.ip) {
- delete(&info, &conntrack[i]->tuple[IP_CT_DIR_ORIGINAL]);
- delete(&info, &conntrack[i]->tuple[IP_CT_DIR_REPLY]);
- }
- }
-
- total_count = 0;
- total_time = 0;
-
- info.insfail = 0;
-
- printf("Adding every other entry from %u to 0\n", TESTNUM - 1);
- for (i -= 2; i >= 0; i -= 2) {
- evicting = 0;
- if (info.numentries > EVICTNUM) /* two entries in hashtrie per conntrack */
- evicting = 1;
- TIMER(
- ret = insert(&info, &conntrack[i]->tuple[IP_CT_DIR_ORIGINAL], 1, hash_tuple(&conntrack[i]->tuple[IP_CT_DIR_ORIGINAL]), evicting);
- ret2 = insert(&info, &conntrack[i]->tuple[IP_CT_DIR_REPLY], 1, hash_tuple(&conntrack[i]->tuple[IP_CT_DIR_REPLY]), evicting);
- );
- if (!ret || !ret2) {
- //printf("Couldn't insert entry %p\n", &conntrack[i]);
- if (!ret) {
- conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].src.ip = conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.ip = 0;
- info.insfail++;
- }
- if (!ret2) {
- conntrack[i]->tuple[IP_CT_DIR_REPLY].src.ip = conntrack[i]->tuple[IP_CT_DIR_REPLY].dst.ip = 0;
- info.insfail++;
- }
- total_time -= code_timer;
- total_count--;
- info.insfail++;
- }
- }
-
- printf("insert (other reverse): ");
- print_timer();
-
- printf("Number of failed inserts: %u\n", info.insfail);
- printf("Number of entries in hashtrie: %u\n", info.numentries);
- printf("Number of children in hashtrie: %u\n", info.numchildren);
- printf("Maxdepth of hashtrie: %u (0 == root)\n", info.maxdepth);
- printf("Maximum memory usage: %u\n", info.maxmem);
- printf("Maximum memory usage per entry: %u\n", info.maxmem / info.numentries);
-
- debug_hashtrie(&info);
-
- if (!free_hashtrie(&info)) {
- return 1;
- }
-
- for (i = 0; i < TESTNUM; i++) {
- free(conntrack[i]);
- free(conntrack2[i]);
- }
- free(conntrack);
- free(conntrack2);
-
- return 0;
-}
Deleted: trunk/hashtrie/oldtable.c
===================================================================
--- trunk/hashtrie/oldtable.c 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/oldtable.c 2006-03-28 12:14:46 UTC (rev 6560)
@@ -1,126 +0,0 @@
-#include <stdio.h>
-#include <string.h>
-#include <stdint.h>
-#include <stdlib.h>
-#include "list.h"
-#include "conntrack.h"
-#include "oldtable.h"
-
-#if 0
-#define printd(args...) printf(args)
-#else
-#define printd(args...)
-#endif
-
-spinlock_t lock;
-
-inline struct ip_conntrack *__lookup(struct hashtable_info *info, struct ip_conntrack_tuple *tuple, unsigned int bucketnr)
-{
- struct ip_conntrack_tuple *c;
- unsigned int longsearch = 0;
-
- printd("Entering lookup\n");
- printd("lookup: looking for tuple %p in bucket %u\n", tuple, bucketnr);
-
- list_for_each_entry(c, &(info->hashtable[bucketnr]), list) {
- if (ip_ct_tuple_equal(c, tuple)) {
- if (info->longsearch < longsearch)
- info->longsearch = longsearch;
- return container_of(c, struct ip_conntrack, tuple[c->dst.dir]);
- }
- longsearch++;
- }
- if (info->longsearch < longsearch)
- info->longsearch = longsearch;
- return NULL;
-}
-
-struct ip_conntrack *lookup(struct hashtable_info *info, struct ip_conntrack_tuple *tuple, hash_t hash)
-{
- unsigned int bucketnr = hash % BUCKETS;
- struct ip_conntrack *ret;
-
- printd("Entering lookup\n");
- printd("lookup: looking for tuple %p in bucket %u\n", tuple, bucketnr);
-
- ret = __lookup(info, tuple, bucketnr);
-
- printd("Leaving lookup\n");
-
- return ret;
-}
-
-int insert(struct hashtable_info *info, struct ip_conntrack_tuple *tuple, hash_t hash)
-{
- unsigned int bucketnr = hash % BUCKETS;
-
- printd("Entering insert\n");
-
- spin_lock(&lock);
- if (__lookup(info, tuple, bucketnr)) {
- spin_unlock(&lock);
- return 0;
- }
-
- printd("insert: adding entry with tuple %p into bucket %u\n", tuple, bucketnr);
-
- list_add(&tuple->list, &(info->hashtable[bucketnr]));
-
- info->numentries++;
-
- spin_unlock(&lock);
-
- printd("Leaving insert\n");
-
- return 1;
-}
-
-int delete(struct hashtable_info *info, struct ip_conntrack_tuple *tuple)
-{
- printd("Entering delete\n");
- printd("delete: removing entry with tuple %p\n", &tuple);
-
- spin_lock(&lock);
-
- list_del(&tuple->list);
-
- info->numentries--;
-
- spin_unlock(&lock);
-
- printd("Leaving delete\n");
-
- return 1;
-}
-
-
-int register_hashtable(struct hashtable_info *info)
-{
- unsigned int i;
-
- info->hashtable = (void *)malloc(BUCKETS * sizeof(struct list_head));
- if (!info->hashtable) {
- printf("Error allocating hashtable\n");
- return 0;
- }
- memset(info->hashtable, 0, BUCKETS * sizeof(struct list_head));
-
- spin_lock_init(&lock);
-
- for (i = 0; i < BUCKETS; i++)
- INIT_LIST_HEAD(&info->hashtable[i]);
-
- return 1;
-}
-
-int unregister_hashtable(struct hashtable_info *info)
-{
- if (info->numentries) {
- printf("Error unregistering hashtable, not empty. entries: %u\n", info->numentries);
- return 0;
- }
-
- free(info->hashtable);
-
- return 1;
-}
Deleted: trunk/hashtrie/oldtable.h
===================================================================
--- trunk/hashtrie/oldtable.h 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/oldtable.h 2006-03-28 12:14:46 UTC (rev 6560)
@@ -1,21 +0,0 @@
-#ifndef OLDTABLE_H
-#define OLDTABLE_H
-
-#define BUCKETS (100*1024)
-
-typedef uint32_t hash_t;
-
-struct hashtable_info {
- struct list_head *hashtable;
- unsigned int numentries;
- unsigned int longsearch;
-};
-
-struct ip_conntrack *lookup(struct hashtable_info *info, struct ip_conntrack_tuple *tuple, hash_t hash);
-int insert(struct hashtable_info *info, struct ip_conntrack_tuple *tuple, hash_t hash);
-int delete(struct hashtable_info *info, struct ip_conntrack_tuple *tuple);
-
-int register_hashtable(struct hashtable_info *info);
-int unregister_hashtable(struct hashtable_info *info);
-
-#endif
Deleted: trunk/hashtrie/oldtest.c
===================================================================
--- trunk/hashtrie/oldtest.c 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/oldtest.c 2006-03-28 12:14:46 UTC (rev 6560)
@@ -1,217 +0,0 @@
-#define _XOPEN_SOURCE 600
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-#include <stdint.h>
-#include <stdlib.h>
-#include "rdtsc2.c"
-#include "conntrack.h"
-#include "oldtable.h"
-
-/* 16 times the number of buckets is the normal ratio for a fully loaded untuned system */
-#define TESTNUM BUCKETS
-
-int main(void)
-{
- struct ip_conntrack **conntrack, **conntrack2, *retp;
- unsigned int ret, ret2, found = 0, notfound = 0;
- int i, dir;
- struct hashtable_info info;
-
- rdtsc_cal(100000000);
-
- printf("sizeof struct ip_conntrack: %u\n", sizeof(struct ip_conntrack));
- printf("number of buckets in hashtable: %u\n", BUCKETS);
- printf("number of conntrack entries: %u\n", TESTNUM);
-
- memset(&info, 0, sizeof(struct hashtable_info));
-
- if (!register_hashtable(&info)) {
- printf("Error registering hashtable\n");
- return 1;
- }
-
- posix_memalign((void *)&conntrack, CACHELINE_REAL, sizeof(struct ip_conntrack *) * TESTNUM);
- //conntrack = (void *)malloc(sizeof(struct ip_conntrack) * TESTNUM);
- if (!conntrack) {
- printf("Couldn't allocate conntracks\n");
- unregister_hashtable(&info);
- return 1;
- }
-
- posix_memalign((void *)&conntrack2, CACHELINE_REAL, sizeof(struct ip_conntrack *) * TESTNUM);
- //conntrack2 = (void *)malloc(sizeof(struct ip_conntrack) * TESTNUM);
- if (!conntrack2) {
- printf("Couldn't allocate conntracks2\n");
- unregister_hashtable(&info);
- return 1;
- }
-
- srand((int)time(NULL));
-
- ip_conntrack_hash_rnd = rand();
-
- for (i = 0; i < TESTNUM; i++) {
- //posix_memalign((void *)&conntrack[i], CACHELINE_REAL, sizeof(struct ip_conntrack));
- conntrack[i] = malloc(sizeof(struct ip_conntrack));
- if (!conntrack[i]) {
- printf("Couldn't allocate conntrack\n");
- unregister_hashtable(&info);
- return 1;
- }
-
- conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].src.ip = rand();
- conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].src.u.tcp.port = (u16)rand();
- conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.ip = rand();
- conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.u.tcp.port = (u16)rand();
- conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.protonum = 6;
- conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.dir = IP_CT_DIR_ORIGINAL;
- INIT_LIST_HEAD(&conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].list);
-
- conntrack[i]->tuple[IP_CT_DIR_REPLY].src.ip = conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.ip;
- conntrack[i]->tuple[IP_CT_DIR_REPLY].src.u.tcp.port = conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.u.tcp.port;
- conntrack[i]->tuple[IP_CT_DIR_REPLY].dst.ip = conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].src.ip;
- conntrack[i]->tuple[IP_CT_DIR_REPLY].dst.u.tcp.port = conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].src.u.tcp.port;
- conntrack[i]->tuple[IP_CT_DIR_REPLY].dst.protonum = 6;
- conntrack[i]->tuple[IP_CT_DIR_REPLY].dst.dir = IP_CT_DIR_REPLY;
- INIT_LIST_HEAD(&conntrack[i]->tuple[IP_CT_DIR_REPLY].list);
-
- //posix_memalign((void *)&conntrack2[i], CACHELINE_REAL, sizeof(struct ip_conntrack));
- conntrack2[i] = malloc(sizeof(struct ip_conntrack));
- if (!conntrack2[i]) {
- printf("Couldn't allocate conntrack2\n");
- unregister_hashtable(&info);
- return 1;
- }
-
- conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].src.ip = rand();
- conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].src.u.tcp.port = (u16)rand();
- conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].dst.ip = rand();
- conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].dst.u.tcp.port = (u16)rand();
- conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].dst.protonum = 6;
- conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].dst.dir = IP_CT_DIR_ORIGINAL;
- INIT_LIST_HEAD(&conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].list);
-
- conntrack2[i]->tuple[IP_CT_DIR_REPLY].src.ip = conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].dst.ip;
- conntrack2[i]->tuple[IP_CT_DIR_REPLY].src.u.tcp.port = conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].dst.u.tcp.port;
- conntrack2[i]->tuple[IP_CT_DIR_REPLY].dst.ip = conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].src.ip;
- conntrack2[i]->tuple[IP_CT_DIR_REPLY].dst.u.tcp.port = conntrack2[i]->tuple[IP_CT_DIR_ORIGINAL].src.u.tcp.port;
- conntrack2[i]->tuple[IP_CT_DIR_REPLY].dst.protonum = 6;
- conntrack2[i]->tuple[IP_CT_DIR_REPLY].dst.dir = IP_CT_DIR_REPLY;
- INIT_LIST_HEAD(&conntrack2[i]->tuple[IP_CT_DIR_REPLY].list);
- }
-
- for (i = 0; i < TESTNUM; i++) {
- TIMER(
- ret = insert(&info, &conntrack[i]->tuple[IP_CT_DIR_ORIGINAL], hash_tuple(&conntrack[i]->tuple[IP_CT_DIR_ORIGINAL]));
- ret2 = insert(&info, &conntrack[i]->tuple[IP_CT_DIR_REPLY], hash_tuple(&conntrack[i]->tuple[IP_CT_DIR_REPLY]));
- );
- if (!ret || !ret2) {
- //printf("Couldn't insert entry %p\n", conntrack[i]);
- if (!ret)
- conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].src.ip = conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.ip = 0;
- if (!ret2)
- conntrack[i]->tuple[IP_CT_DIR_REPLY].src.ip = conntrack[i]->tuple[IP_CT_DIR_REPLY].dst.ip = 0;
- total_time -= code_timer;
- total_count--;
- }
- }
-
- printf("insert: ");
- print_timer();
-
- printf("Number of entries in hashtable: %u\n", info.numentries);
- printf("Longest search in hashtable: %u\n", info.longsearch);
- info.longsearch = 0;
-
- total_count = 0;
- total_time = 0;
-
- for (dir = 0; dir < IP_CT_DIR_MAX; dir++) {
- for (i = 0; i < TESTNUM; i++) {
- if (conntrack[i]->tuple[dir].src.ip && conntrack[i]->tuple[dir].dst.ip) {
- TIMER(retp = lookup(&info, &conntrack[i]->tuple[dir], hash_tuple(&conntrack[i]->tuple[dir])););
- if (retp != conntrack[i]) {
- printf("Couldn't find entry %p\n", conntrack[i]);
- return 1;
- }
- }
- }
- }
-
- printf("lookup: ");
- print_timer();
- printf("Longest search in hashtable: %u\n", info.longsearch);
- info.longsearch = 0;
-
- total_count = 0;
- total_time = 0;
-
- for (dir = IP_CT_DIR_MAX - 1; dir >= 0; dir--) {
- for (i = TESTNUM - 1; i >= 0; i--) {
- if (conntrack[i]->tuple[dir].src.ip && conntrack[i]->tuple[dir].dst.ip) {
- TIMER(retp = lookup(&info, &conntrack[i]->tuple[dir], hash_tuple(&conntrack[i]->tuple[dir])););
- if (retp != conntrack[i]) {
- printf("Couldn't find entry %p\n", conntrack[i]);
- return 1;
- }
- }
- }
- }
-
- printf("lookup (reverse): ");
- print_timer();
- printf("Longest search in hashtable: %u\n", info.longsearch);
- info.longsearch = 0;
-
- total_count = 0;
- total_time = 0;
-
- for (dir = 0; dir < IP_CT_DIR_MAX; dir++) {
- for (i = 0; i < TESTNUM; i++) {
- if (conntrack2[i]->tuple[dir].src.ip && conntrack2[i]->tuple[dir].dst.ip) {
- TIMER(retp = lookup(&info, &conntrack2[i]->tuple[dir], hash_tuple(&conntrack2[i]->tuple[dir])););
- if (retp == conntrack2[i])
- found++;
- else
- notfound++;
- }
- }
- }
-
- printf("lookup (nomatch): ");
- print_timer();
- printf("Found entries in hashtable: %d\n", found);
- printf("Not found entries in hashtable: %d\n", notfound);
-
- total_count = 0;
- total_time = 0;
-
- for (i = 0; i < TESTNUM; i++) {
- if (conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].src.ip && conntrack[i]->tuple[IP_CT_DIR_ORIGINAL].dst.ip &&
- conntrack[i]->tuple[IP_CT_DIR_REPLY].src.ip && conntrack[i]->tuple[IP_CT_DIR_REPLY].dst.ip) {
- TIMER(
- ret = delete(&info, &conntrack[i]->tuple[IP_CT_DIR_ORIGINAL]);
- ret2 = delete(&info, &conntrack[i]->tuple[IP_CT_DIR_REPLY]);
- );
- if (!ret || !ret2) {
- printf("Couldn't delete entry %p (entries: %u)\n", conntrack[i], info.numentries);
- return 1;
- }
- }
- }
-
- printf("delete: ");
- print_timer();
-
- printf("Number of entries in hashtable: %u\n", info.numentries);
-
- if (!unregister_hashtable(&info)) {
- printf("Error unregistering hashtable\n");
- return 1;
- }
- free(conntrack);
- free(conntrack2);
-
- return 0;
-}
Deleted: trunk/hashtrie/rdtsc2.c
===================================================================
--- trunk/hashtrie/rdtsc2.c 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/rdtsc2.c 2006-03-28 12:14:46 UTC (rev 6560)
@@ -1,123 +0,0 @@
-#include <math.h>
-#include <sys/time.h>
-#include <time.h>
-
-static unsigned long total_count;
-static unsigned long long total_time;
-static unsigned long long code_timer;
-
-#define TIMER(code) \
- do { \
- code_timer = rdtsc_read(); \
- do{code}while(0); \
- code_timer = rdtsc_read() - code_timer; \
- total_time += code_timer; \
- total_count++; \
- } while (0)
-
-
-static double ns_per_clock = 0.0;
-
-/*
- * Do not depend on kernel header. Taken from 2.4.19-pre7 include/asm/msr.h
- */
-#define rdtsc(low,high) \
- __asm__ __volatile__("rdtsc" : "=a" (low), "=d" (high))
-
-#define rdtscll(val) \
- __asm__ __volatile__("rdtsc" : "=A" (val))
-
-static inline unsigned long long rdtsc_read(void)
-{
- unsigned long high, low;
- rdtsc(low,high);
- return ((unsigned long long)high << 32) | low;
-}
-
-static inline unsigned long long rdtsc_read2(void)
-{
- unsigned long long val;
- rdtscll(val);
- return val;
-}
-
-static unsigned long long rdtsc__cal_empty(int cnt)
-{
- unsigned long long start = rdtsc_read();
- while (cnt-- > 0) ;
- return rdtsc_read() - start;
-}
-
-static int rdtsc__cal_run(int cnt)
-{
- struct timeval tv_start;
- struct timeval tv_delta;
- unsigned long long delta;
- unsigned long long delta_ns;
- double prev_ns_per_clock = ns_per_clock;
-
- gettimeofday(&tv_start, 0);
- delta = rdtsc__cal_empty(cnt);
- gettimeofday(&tv_delta, 0);
- tv_delta.tv_sec -= tv_start.tv_sec;
- if (tv_start.tv_usec <= tv_delta.tv_usec) {
- tv_delta.tv_usec -= tv_start.tv_usec;
- } else {
- tv_delta.tv_usec += (1000000 - tv_start.tv_usec);
- tv_delta.tv_sec--;
- }
- delta_ns = 1000000000ull * tv_delta.tv_sec;
- delta_ns += 1000ull * tv_delta.tv_usec;
- ns_per_clock = (1.0 * delta_ns) / delta;
-#ifdef RDTSC_VERBOSE
- printf("rdtsc_cal(%d), ns/clock old=%.2f new=%.2f, %.0fmhz, waste %.3fus\n",
- cnt,
- prev_ns_per_clock,
- ns_per_clock,
- 1000 / ns_per_clock,
- cnt * ns_per_clock / 1000.0);
-#endif
- return (fabs(ns_per_clock - prev_ns_per_clock) < (0.0005 * ns_per_clock));
-}
-
-void rdtsc_cal(int cntmax)
-{
- int cnt = 1 << 10;
- unsigned long long cyc;
- struct timeval tv_start;
- struct timeval tv_delta;
-
- gettimeofday(&tv_start, 0);
- cyc = rdtsc_read();
- while (cnt < cntmax) {
- if (rdtsc__cal_run(cnt))
- break;
- cnt <<= 1;
- }
- cyc = rdtsc_read() - cyc;
- gettimeofday(&tv_delta, 0);
- tv_delta.tv_sec -= tv_start.tv_sec;
- if (tv_start.tv_usec <= tv_delta.tv_usec) {
- tv_delta.tv_usec -= tv_start.tv_usec;
- } else {
- tv_delta.tv_usec += (1000000 - tv_start.tv_usec);
- tv_delta.tv_sec--;
- }
-#ifdef RDTSC_VERBOSE
- printf("rdtsc_cal: %.2f ns/cyc, took %Lu cyc / %.3f ms\n",
- ns_per_clock,
- cyc,
- cyc * ns_per_clock / 1000000.0);
- printf("rdtsc_cal gettimeofday interval: %.3f ms\n",
- (tv_delta.tv_sec * 1000000.0 + tv_delta.tv_usec) / 1000.0);
-#endif
-}
-
-void print_timer()
-{
- printf("time: %Lu cyc, %.0f ns (%.0f/s)\n",
- total_time / total_count,
- (ns_per_clock * total_time) / total_count,
- 1e9 / (ns_per_clock * total_time / total_count));
-};
-
Copied: trunk/hashtrie/rdtsc2.h (from rev 6559, trunk/hashtrie/rdtsc2.c)
===================================================================
--- trunk/hashtrie/rdtsc2.c 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/rdtsc2.h 2006-03-28 12:14:46 UTC (rev 6560)
@@ -0,0 +1,123 @@
+#include <math.h>
+#include <sys/time.h>
+#include <time.h>
+
+static unsigned long total_count;
+static unsigned long long total_time;
+static unsigned long long code_timer;
+
+#define TIMER(code) \
+ do { \
+ code_timer = rdtsc_read(); \
+ do{code}while(0); \
+ code_timer = rdtsc_read() - code_timer; \
+ total_time += code_timer; \
+ total_count++; \
+ } while (0)
+
+
+static double ns_per_clock = 0.0;
+
+/*
+ * Do not depend on kernel header. Taken from 2.4.19-pre7 include/asm/msr.h
+ */
+#define rdtsc(low,high) \
+ __asm__ __volatile__("rdtsc" : "=a" (low), "=d" (high))
+
+#define rdtscll(val) \
+ __asm__ __volatile__("rdtsc" : "=A" (val))
+
+static inline unsigned long long rdtsc_read(void)
+{
+ unsigned long high, low;
+ rdtsc(low,high);
+ return ((unsigned long long)high << 32) | low;
+}
+
+static inline unsigned long long rdtsc_read2(void)
+{
+ unsigned long long val;
+ rdtscll(val);
+ return val;
+}
+
+static unsigned long long rdtsc__cal_empty(int cnt)
+{
+ unsigned long long start = rdtsc_read();
+ while (cnt-- > 0) ;
+ return rdtsc_read() - start;
+}
+
+static int rdtsc__cal_run(int cnt)
+{
+ struct timeval tv_start;
+ struct timeval tv_delta;
+ unsigned long long delta;
+ unsigned long long delta_ns;
+ double prev_ns_per_clock = ns_per_clock;
+
+ gettimeofday(&tv_start, 0);
+ delta = rdtsc__cal_empty(cnt);
+ gettimeofday(&tv_delta, 0);
+ tv_delta.tv_sec -= tv_start.tv_sec;
+ if (tv_start.tv_usec <= tv_delta.tv_usec) {
+ tv_delta.tv_usec -= tv_start.tv_usec;
+ } else {
+ tv_delta.tv_usec += (1000000 - tv_start.tv_usec);
+ tv_delta.tv_sec--;
+ }
+ delta_ns = 1000000000ull * tv_delta.tv_sec;
+ delta_ns += 1000ull * tv_delta.tv_usec;
+ ns_per_clock = (1.0 * delta_ns) / delta;
+#ifdef RDTSC_VERBOSE
+ printf("rdtsc_cal(%d), ns/clock old=%.2f new=%.2f, %.0fmhz, waste %.3fus\n",
+ cnt,
+ prev_ns_per_clock,
+ ns_per_clock,
+ 1000 / ns_per_clock,
+ cnt * ns_per_clock / 1000.0);
+#endif
+ return (fabs(ns_per_clock - prev_ns_per_clock) < (0.0005 * ns_per_clock));
+}
+
+void rdtsc_cal(int cntmax)
+{
+ int cnt = 1 << 10;
+ unsigned long long cyc;
+ struct timeval tv_start;
+ struct timeval tv_delta;
+
+ gettimeofday(&tv_start, 0);
+ cyc = rdtsc_read();
+ while (cnt < cntmax) {
+ if (rdtsc__cal_run(cnt))
+ break;
+ cnt <<= 1;
+ }
+ cyc = rdtsc_read() - cyc;
+ gettimeofday(&tv_delta, 0);
+ tv_delta.tv_sec -= tv_start.tv_sec;
+ if (tv_start.tv_usec <= tv_delta.tv_usec) {
+ tv_delta.tv_usec -= tv_start.tv_usec;
+ } else {
+ tv_delta.tv_usec += (1000000 - tv_start.tv_usec);
+ tv_delta.tv_sec--;
+ }
+#ifdef RDTSC_VERBOSE
+ printf("rdtsc_cal: %.2f ns/cyc, took %Lu cyc / %.3f ms\n",
+ ns_per_clock,
+ cyc,
+ cyc * ns_per_clock / 1000000.0);
+ printf("rdtsc_cal gettimeofday interval: %.3f ms\n",
+ (tv_delta.tv_sec * 1000000.0 + tv_delta.tv_usec) / 1000.0);
+#endif
+}
+
+void print_timer()
+{
+ printf("time: %Lu cyc, %.0f ns (%.0f/s)\n\n",
+ total_time / total_count,
+ (ns_per_clock * total_time) / total_count,
+ 1e9 / (ns_per_clock * total_time / total_count));
+};
+
Added: trunk/hashtrie/runme
===================================================================
--- trunk/hashtrie/runme 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/runme 2006-03-28 12:14:46 UTC (rev 6560)
@@ -0,0 +1,11 @@
+#!/bin/sh
+
+HASHSIZE=$((100*1024))
+
+for x in 25 50 100 200; do
+ n=$((x*1024))
+ echo $n
+ ./tables -h $HASHSIZE -t $n all > tables.res.$n
+done
+
+./graphs tables.res.*
Property changes on: trunk/hashtrie/runme
___________________________________________________________________
Name: svn:executable
+ *
Added: trunk/hashtrie/sfhash.h
===================================================================
--- trunk/hashtrie/sfhash.h 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/sfhash.h 2006-03-28 12:14:46 UTC (rev 6560)
@@ -0,0 +1,74 @@
+#ifndef _LINUX_SFHASH_H
+#define _LINUX_SFHASH_H
+
+/* sfhash.h: SuperFastHash support.
+ *
+ * Copyright (C) 2004 by Paul Hsieh
+ *
+ * http://www.azillionmonkeys.com/qed/hash.html
+ *
+ */
+
+#define get16bits(d) (*((const u16 *) (d)))
+
+/* The most generic version, hashes an arbitrary sequence
+ * of bytes. No alignment or length assumptions are made about
+ * the input key.
+ */
+static inline u32 sfhash(const void * key, u32 len, u32 initval)
+{
+ const char * data = key;
+ u32 hash = len + initval, tmp;
+ int rem;
+
+ if (len <= 0 || data == NULL)
+ return 0;
+
+ rem = len & 3;
+ len >>= 2;
+
+ /* Main loop */
+ for (; len > 0; len--) {
+ /* Mix 32bit chunk of the data */
+ hash += get16bits(data);
+ tmp = (get16bits(data+2) << 11) ^ hash;
+ hash = (hash << 16) ^ tmp;
+ data += 2*sizeof(u16);
+ hash += hash >> 11;
+ }
+
+ /* Handle end cases */
+ switch (rem) {
+ case 3: hash += *((u16 *)data);
+ hash ^= hash << 16;
+ hash ^= data[sizeof(u16)] << 18;
+ hash += hash >> 11;
+ break;
+ case 2: hash += *((u16 *)data);
+ hash ^= hash << 11;
+ hash += hash >> 17;
+ break;
+ case 1: hash += *data;
+ hash ^= hash << 10;
+ hash += hash >> 1;
+ }
+
+ /* Force "avalanching" of final 127 bits */
+ hash ^= hash << 3;
+ hash += hash >> 5;
+ hash ^= hash << 2;
+ hash += hash >> 15;
+ hash ^= hash << 10;
+
+ return hash;
+}
+
+/* Special versions for hashing exactly 3 words.
+ */
+static inline u32 sfhash_3words(u32 a, u32 b, u32 c, u32 initval)
+{
+ u32 data[3] = {a,b,c};
+
+ return sfhash(data, 12, initval);
+}
+#endif
Added: trunk/hashtrie/shared_node.c
===================================================================
--- trunk/hashtrie/shared_node.c 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/shared_node.c 2006-03-28 12:14:46 UTC (rev 6560)
@@ -0,0 +1,310 @@
+#include <stdio.h>
+#include <string.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include "misc.h"
+#include "list.h"
+#include "conntrack.h"
+#include "tables.h"
+#include "shared_node.h"
+
+#if 0
+#define printd(args...) printf(args)
+#else
+#define printd(args...)
+#endif
+
+static inline void node_jhash_3words(u32 hash[3], u32 initval)
+{
+ hash[0] += JHASH_GOLDEN_RATIO;
+ hash[1] += JHASH_GOLDEN_RATIO;
+ hash[2] += initval;
+
+ __jhash_mix(hash[0], hash[1], hash[2]);
+}
+
+static inline void
+node_hash_tuple(u32 hash[3],
+ struct ip_conntrack_tuple_generic *tuple,
+ unsigned int hashsize)
+{
+ hash[0] = tuple->src.ip;
+ hash[1] = tuple->dst.ip ^ tuple->dst.protonum;
+ hash[2] = tuple->src.u.all | (tuple->dst.u.all << 16);
+
+ node_jhash_3words(hash, ip_conntrack_hash_rnd);
+
+ hash[0] %= hashsize;
+ hash[1] %= hashsize;
+ hash[2] %= hashsize;
+}
+
+spinlock_t lock;
+
+static inline int
+__lookup(struct shared_node_info *info,
+ struct ip_conntrack_tuple_generic *tuple,
+ u32 hash[3])
+{
+ struct shared_node *node;
+ unsigned int i,j, longsearch = 0;
+ u32 counter;
+
+ for (j = 0, counter = info->hashtable[hash[0]].counter, i = 1;
+ i < 3; i++){
+ if (info->hashtable[hash[i]].counter < counter)
+ j = i;
+ }
+
+ if (!info->hashtable[hash[j]].counter) {
+ return 0;
+ }
+
+ node = info->hashtable[hash[j]].next;
+ counter = info->hashtable[hash[j]].counter;
+ i = 1;
+ while (node != NULL && i++ <= counter) {
+ if (ip_ct_tuple_equal(&node->tuple->tuple, tuple)) {
+ if (info->longsearch < longsearch)
+ info->longsearch = longsearch;
+ return 1;
+ }
+ longsearch++;
+ node = node->next;
+ }
+ if (info->longsearch < longsearch)
+ info->longsearch = longsearch;
+ return 0;
+}
+
+static int
+lookup(struct table_info *table, struct ip_conntrack_generic *ct)
+{
+ struct shared_node_info *info = (struct shared_node_info *) table->data;
+ u32 bucket_orig[3], bucket_reply[3];
+
+ node_hash_tuple(bucket_orig, &ct->tuple[IP_CT_DIR_ORIGINAL], info->hashsize);
+ node_hash_tuple(bucket_reply, &ct->tuple[IP_CT_DIR_REPLY], info->hashsize);
+
+ return (__lookup(info, &ct->tuple[IP_CT_DIR_ORIGINAL], bucket_orig)
+ && __lookup(info, &ct->tuple[IP_CT_DIR_REPLY], bucket_reply));
+}
+
+static int
+__insert(struct shared_node_info *info, struct ip_conntrack_tuple *tuple, u32 hash[3])
+{
+ unsigned int i,j, k, used = 0;
+ struct shared_node *node, *new;
+
+ new = malloc(sizeof(struct shared_node));
+ if (!new) {
+ printf("Can't allocate shared_node\n");
+ return 0;
+ }
+ new->next = NULL;
+ new->tuple = tuple;
+ info->size += sizeof(struct shared_node);
+
+ for (i = 0; i < 3; i++) {
+ for (j = 0; j < i; j++)
+ if (hash[i] == hash[j])
+ goto skip;
+ if (info->hashtable[hash[i]].counter) {
+ k = 1;
+ node = info->hashtable[hash[i]].next;
+ while (k++ < info->hashtable[hash[i]].counter)
+ node = node->next;
+ if (node->next) {
+ struct shared_node *prep = malloc(sizeof(struct shared_node));
+ if (!prep) {
+ printf("Can't allocate shared_node\n");
+ return 0;
+ }
+ prep->tuple = tuple;
+ prep->next = info->hashtable[hash[i]].next;
+ info->hashtable[hash[i]].next = prep;
+
+ info->size += sizeof(struct shared_node);
+ } else {
+ node->next = new;
+ used = 1;
+ }
+ } else {
+ info->hashtable[hash[i]].next = new;
+ used = 1;
+ }
+ info->hashtable[hash[i]].counter++;
+ skip:
+ ; /* Keep compiler happy */
+ }
+ if (!used) {
+ free(new);
+ info->size -= sizeof(struct shared_node);
+ }
+ return 1;
+}
+
+static int
+insert(struct table_info *table, struct ip_conntrack_generic *ct)
+{
+ struct shared_node_info *info = (struct shared_node_info *) table->data;
+ struct ip_conntrack *conntrack;
+ u32 bucket_orig[3], bucket_reply[3];
+
+ printd("Entering insert\n");
+
+ conntrack = malloc(sizeof(struct ip_conntrack));
+ if (!conntrack) {
+ printf("Can't allocate conntrack\n");
+ return 0;
+ }
+ memset(conntrack, 0, sizeof(*conntrack));
+ conntrack->tuple[IP_CT_DIR_ORIGINAL].tuple = ct->tuple[IP_CT_DIR_ORIGINAL];
+ conntrack->tuple[IP_CT_DIR_REPLY].tuple = ct->tuple[IP_CT_DIR_REPLY];
+
+ node_hash_tuple(bucket_orig, &ct->tuple[IP_CT_DIR_ORIGINAL], info->hashsize);
+ node_hash_tuple(bucket_reply, &ct->tuple[IP_CT_DIR_REPLY], info->hashsize);
+
+ spin_lock(&lock);
+ if (!(__insert(info, &conntrack->tuple[IP_CT_DIR_ORIGINAL], bucket_orig)
+ && __insert(info, &conntrack->tuple[IP_CT_DIR_REPLY], bucket_reply))) {
+ spin_unlock(&lock);
+ return 0;
+ }
+ spin_unlock(&lock);
+
+ info->numentries += 2;
+ info->size += sizeof(struct ip_conntrack);
+ ct->ct = conntrack;
+
+ printd("Leaving insert\n");
+
+ return 1;
+}
+
+static int
+__delete(struct shared_node_info *info,
+ struct ip_conntrack_tuple_generic *tuple,
+ u32 hash[3])
+{
+ unsigned int i,j, k, longsearch = 0;
+ struct shared_node *node, *prev;
+
+ for (i = 0; i < 3; i++) {
+ for (j = 0; j < i; j++)
+ if (hash[i] == hash[j])
+ goto skip;
+ k = 1;
+ node = prev = info->hashtable[hash[i]].next;
+ while (k++ < info->hashtable[hash[i]].counter && node) {
+ if (ip_ct_tuple_equal(tuple, &node->tuple->tuple)) {
+ if (prev == node)
+ info->hashtable[hash[i]].next = node->next;
+ else
+ prev->next = node->next;
+ info->size -= sizeof(*node);
+ free(node);
+ if (info->longsearch < longsearch)
+ info->longsearch = longsearch;
+ break;
+ }
+ longsearch++;
+ prev = node;
+ node = node->next;
+ }
+ info->hashtable[hash[i]].counter--;
+ skip:
+ ; /* Keep compiler happy */
+ }
+ return 1;
+}
+
+static int
+delete(struct table_info *table, struct ip_conntrack_generic *conntrack)
+{
+ struct shared_node_info *info = (struct shared_node_info *) table->data;
+ struct ip_conntrack *ct = (struct ip_conntrack *) conntrack->ct;
+ u32 bucket_orig[3], bucket_reply[3];
+
+ node_hash_tuple(bucket_orig, &conntrack->tuple[IP_CT_DIR_ORIGINAL], info->hashsize);
+ node_hash_tuple(bucket_reply, &conntrack->tuple[IP_CT_DIR_REPLY], info->hashsize);
+
+ spin_lock(&lock);
+ __delete(info, &conntrack->tuple[IP_CT_DIR_ORIGINAL], bucket_orig);
+ __delete(info, &conntrack->tuple[IP_CT_DIR_REPLY], bucket_reply);
+ spin_unlock(&lock);
+
+ info->numentries -= 2;
+ info->size -= sizeof(struct ip_conntrack);
+ free(ct);
+ printd("Leaving delete\n");
+
+ return 1;
+}
+
+static void report(struct table_info *table)
+{
+ struct shared_node_info *info = (struct shared_node_info *) table->data;
+
+ printf("Number of entries: %u\n", info->numentries);
+ printf("Longest search: %u\n", info->longsearch);
+ printf("Required memory: %u\n", info->size);
+
+ /* Reset for next test */
+ info->longsearch = 0;
+}
+
+static int init(struct table_info *table, unsigned int hashsize)
+{
+ struct shared_node_info *info;
+
+ table->data = malloc(sizeof(struct shared_node_info));
+ if (!table->data) {
+ printf("Error allocating shared_node info data\n");
+ return 0;
+ }
+ memset(table->data, 0, sizeof(struct shared_node_info));
+ info = (struct shared_node_info *) table->data;
+
+ info->hashtable = (void *)malloc(hashsize * sizeof(struct shared_node_root));
+ if (!info->hashtable) {
+ printf("Error allocating hashtable\n");
+ return 0;
+ }
+ memset(info->hashtable, 0, hashsize * sizeof(struct shared_node_root));
+ info->hashsize = hashsize;
+ info->size = hashsize * sizeof(struct shared_node_root);
+
+ spin_lock_init(&lock);
+
+ printf("Table size: %u\n", info->size);
+ printf("Entry size: %u\n", sizeof(struct ip_conntrack));
+ printf("Node size: %u\n", sizeof(struct shared_node));
+
+ return 1;
+}
+
+static int destroy(struct table_info *table)
+{
+ struct shared_node_info *info = (struct shared_node_info *) table->data;
+
+ if (info->numentries) {
+ printf("Error unregistering shared_node, not empty. entries: %u\n", info->numentries);
+ return 0;
+ }
+
+ free(info->hashtable);
+ free(info);
+
+ return 1;
+}
+
+struct table_info shared_node_info = {
+ .name = "shared_node",
+ .lookup = &lookup,
+ .insert = &insert,
+ .delete = &delete,
+ .report = &report,
+ .init = &init,
+ .destroy = &destroy,
+};
Added: trunk/hashtrie/shared_node.h
===================================================================
--- trunk/hashtrie/shared_node.h 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/shared_node.h 2006-03-28 12:14:46 UTC (rev 6560)
@@ -0,0 +1,32 @@
+#ifndef SHARED_NODE_H
+#define SHARED_NODE_H
+
+struct ip_conntrack_tuple
+{
+ struct ip_conntrack_tuple_generic tuple;
+};
+
+struct ip_conntrack
+{
+ struct ip_conntrack_tuple tuple[IP_CT_DIR_MAX];
+};
+
+struct shared_node {
+ struct shared_node *next;
+ struct ip_conntrack_tuple *tuple;
+};
+
+struct shared_node_root {
+ uint16_t counter;
+ struct shared_node *next;
+};
+
+struct shared_node_info {
+ struct shared_node_root *hashtable;
+ unsigned int hashsize;
+ unsigned int numentries;
+ unsigned int longsearch;
+ unsigned int size;
+};
+
+#endif
Copied: trunk/hashtrie/tables.c (from rev 6559, trunk/hashtrie/newtest.c)
===================================================================
--- trunk/hashtrie/newtest.c 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/tables.c 2006-03-28 12:14:46 UTC (rev 6560)
@@ -0,0 +1,284 @@
+/* Test different conntrack storage methods */
+
+#include <unistd.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <time.h>
+#include "conntrack.h"
+#include "tables.h"
+#include "rdtsc2.h"
+
+struct ip_conntrack_generic ip_conntrack_nomatch = {};
+struct ip_conntrack_generic *conntrack_random;
+struct ip_conntrack_generic *conntrack_dos;
+
+enum table_tests {
+ HASHTABLE,
+ HASHTABLE_SF,
+ HASHTRIE64,
+ HASHTRIE32,
+ HASHTRIE16,
+ HASHTRIE8,
+ HASHTRIE4,
+ HASHTRIE_VAR0,
+ HASHTRIE_VAR1,
+ HASHTRIE_VAR2,
+ HASHARRAY8,
+ HASHARRAY4,
+ SHARED_NODE,
+ TESTS_MAX,
+};
+
+struct table_info *tables[TESTS_MAX];
+
+extern struct table_info hashtable_sf_info;
+extern struct table_info hashtable_info;
+extern struct table_info hashtrie64_info;
+extern struct table_info hashtrie32_info;
+extern struct table_info hashtrie16_info;
+extern struct table_info hashtrie8_info;
+extern struct table_info hashtrie4_info;
+extern struct table_info hashtrie_var0_info;
+extern struct table_info hashtrie_var1_info;
+extern struct table_info hashtrie_var2_info;
+extern struct table_info hasharray8_info;
+extern struct table_info hasharray4_info;
+extern struct table_info shared_node_info;
+
+static inline void init_tables(void) {
+ tables[HASHTABLE] = &hashtable_info;
+ tables[HASHTABLE_SF] = &hashtable_sf_info;
+ tables[HASHTRIE64] = &hashtrie64_info;
+ tables[HASHTRIE32] = &hashtrie32_info;
+ tables[HASHTRIE16] = &hashtrie16_info;
+ tables[HASHTRIE8] = &hashtrie8_info;
+ tables[HASHTRIE4] = &hashtrie4_info;
+ tables[HASHTRIE_VAR0] = &hashtrie_var0_info;
+ tables[HASHTRIE_VAR1] = &hashtrie_var1_info;
+ tables[HASHTRIE_VAR2] = &hashtrie_var2_info;
+ tables[HASHARRAY8] = &hasharray8_info;
+ tables[HASHARRAY4] = &hasharray4_info;
+ tables[SHARED_NODE] = &shared_node_info;
+}
+
+#define DOS_SRC_BASE (10 << 24 | 0 << 16 | 0 << 8 | 1)
+#define DOS_DST (192 << 24 | 168 << 16 | 1 << 8 | 1)
+
+int init_conntrack(unsigned int testnum)
+{
+ unsigned int i;
+ unsigned int j,k;
+
+ conntrack_random = malloc(testnum * sizeof(struct ip_conntrack_generic));
+ if (!conntrack_random) {
+ printf("Couldn't allocate random conntracks\n");
+ return -1;
+ }
+ conntrack_dos = malloc(testnum * sizeof(struct ip_conntrack_generic));
+ if (!conntrack_dos) {
+ printf("Couldn't allocate DoS conntracks\n");
+ return -1;
+ }
+
+ srand((int)time(NULL));
+
+ ip_conntrack_hash_rnd = rand();
+
+ for (i = 0; i < testnum; i++) {
+ conntrack_random[i].tuple[IP_CT_DIR_ORIGINAL].src.ip = rand();
+ conntrack_random[i].tuple[IP_CT_DIR_ORIGINAL].src.u.tcp.port = (u16)rand();
+ conntrack_random[i].tuple[IP_CT_DIR_ORIGINAL].dst.ip = rand();
+ conntrack_random[i].tuple[IP_CT_DIR_ORIGINAL].dst.u.tcp.port = (u16)rand();
+ conntrack_random[i].tuple[IP_CT_DIR_ORIGINAL].dst.protonum = 6;
+ conntrack_random[i].tuple[IP_CT_DIR_ORIGINAL].dst.dir = IP_CT_DIR_ORIGINAL;
+
+ conntrack_random[i].tuple[IP_CT_DIR_REPLY].src.ip = conntrack_random[i].tuple[IP_CT_DIR_ORIGINAL].dst.ip;
+ conntrack_random[i].tuple[IP_CT_DIR_REPLY].src.u.tcp.port = conntrack_random[i].tuple[IP_CT_DIR_ORIGINAL].dst.u.tcp.port;
+ conntrack_random[i].tuple[IP_CT_DIR_REPLY].dst.ip = conntrack_random[i].tuple[IP_CT_DIR_ORIGINAL].src.ip;
+ conntrack_random[i].tuple[IP_CT_DIR_REPLY].dst.u.tcp.port = conntrack_random[i].tuple[IP_CT_DIR_ORIGINAL].src.u.tcp.port;
+ conntrack_random[i].tuple[IP_CT_DIR_REPLY].dst.protonum = 6;
+ conntrack_random[i].tuple[IP_CT_DIR_REPLY].dst.dir = IP_CT_DIR_REPLY;
+ }
+ i = j = 0;
+ while (i < testnum) {
+ for (k = 1024; k < 40000 && i < testnum; k++) {
+ conntrack_dos[i].tuple[IP_CT_DIR_ORIGINAL].src.ip = DOS_SRC_BASE + j;
+ conntrack_dos[i].tuple[IP_CT_DIR_ORIGINAL].src.u.tcp.port = k;
+ conntrack_dos[i].tuple[IP_CT_DIR_ORIGINAL].dst.ip = DOS_DST;
+ conntrack_dos[i].tuple[IP_CT_DIR_ORIGINAL].dst.u.tcp.port = 80;
+ conntrack_dos[i].tuple[IP_CT_DIR_ORIGINAL].dst.protonum = 6;
+ conntrack_dos[i].tuple[IP_CT_DIR_ORIGINAL].dst.dir = IP_CT_DIR_ORIGINAL;
+
+ conntrack_dos[i].tuple[IP_CT_DIR_REPLY].src.ip = conntrack_dos[i].tuple[IP_CT_DIR_ORIGINAL].dst.ip;
+ conntrack_dos[i].tuple[IP_CT_DIR_REPLY].src.u.tcp.port = conntrack_dos[i].tuple[IP_CT_DIR_ORIGINAL].dst.u.tcp.port;
+ conntrack_dos[i].tuple[IP_CT_DIR_REPLY].dst.ip = conntrack_dos[i].tuple[IP_CT_DIR_ORIGINAL].src.ip;
+ conntrack_dos[i].tuple[IP_CT_DIR_REPLY].dst.u.tcp.port = conntrack_dos[i].tuple[IP_CT_DIR_ORIGINAL].src.u.tcp.port;
+ conntrack_dos[i].tuple[IP_CT_DIR_REPLY].dst.protonum = 6;
+ conntrack_dos[i].tuple[IP_CT_DIR_REPLY].dst.dir = IP_CT_DIR_REPLY;
+ i++;
+ }
+ j++;
+ }
+ return 0;
+}
+
+void table_tests(struct table_info *table, unsigned int testnum,
+ struct ip_conntrack_generic *conntrack,
+ struct ip_conntrack_generic *nomatch,
+ const char *type)
+{
+ int i;
+ int ret;
+
+ printf("\n%s conntrack tests\n\n", type);
+ /* Insert */
+ total_count = 0;
+ total_time = 0;
+ for (i = 0; i < testnum; i++) {
+ TIMER(ret = table->insert(table, &conntrack[i]); );
+ if (!ret) {
+ printf("Couldn't add entry %u, skipping\n", i);
+ conntrack[i].tuple[IP_CT_DIR_ORIGINAL].dst.protonum = 0;
+ total_time -= code_timer;
+ total_count--;
+ }
+ }
+ printf("%s: insert\n", table->name);
+ table->report(table);
+ print_timer();
+
+ /* Lookup */
+ total_count = 0;
+ total_time = 0;
+ for (i = 0; i < testnum; i++) {
+ if (!conntrack[i].tuple[IP_CT_DIR_ORIGINAL].dst.protonum)
+ continue;
+ TIMER(ret = table->lookup(table, &conntrack[i]); );
+ if (!ret) {
+ printf("Couldn't find entry %u!\n", i);
+ exit(1);
+ }
+ }
+ printf("%s: lookup\n", table->name);
+ table->report(table);
+ print_timer();
+
+ /* Lookup, reverse */
+ total_count = 0;
+ total_time = 0;
+ for (i = testnum - 1; i >= 0; i--) {
+ if (!conntrack[i].tuple[IP_CT_DIR_ORIGINAL].dst.protonum)
+ continue;
+ TIMER(ret = table->lookup(table, &conntrack[i]); );
+ if (!ret) {
+ printf("Couldn't find entry %u!\n", i);
+ exit(1);
+ }
+ }
+ printf("%s: lookup(reverse)\n", table->name);
+ table->report(table);
+ print_timer();
+
+ /* Lookup, nomatch */
+ total_count = 0;
+ total_time = 0;
+ for (i = 0; i < testnum; i++) {
+ if (!conntrack[i].tuple[IP_CT_DIR_ORIGINAL].dst.protonum)
+ continue;
+ TIMER(ret = table->lookup(table, &nomatch[i]); );
+ if (ret) {
+ printf("You win! Found nomatch entry at %i!\n", i);
+ exit(1);
+ }
+ }
+ printf("%s: lookup (nomatch)\n", table->name);
+ table->report(table);
+ print_timer();
+
+ /* delete */
+ total_count = 0;
+ total_time = 0;
+ for (i = 0; i < testnum; i++) {
+ if (!conntrack[i].tuple[IP_CT_DIR_ORIGINAL].dst.protonum)
+ continue;
+ TIMER(ret = table->delete(table, &conntrack[i]); );
+ if (!ret) {
+ printf("Can't delete entry %i!\n", i);
+ exit(1);
+ }
+ }
+ printf("%s: delete\n", table->name);
+ table->report(table);
+ print_timer();
+}
+
+void usage()
+{
+ unsigned int i;
+
+ printf("tables [-h hashsize] [-t testnum] [all]\n");
+ printf("Supported methods:\n");
+ for (i = 0; i < TESTS_MAX; i++)
+ printf("\t%s\n", tables[i]->name);
+ printf("\n");
+ exit(1);
+}
+
+int main(int argc, char **argv)
+{
+ int c, i, j = 0;
+ unsigned int hashsize = 100*1024;
+ unsigned int testnum = 100*1024;
+ int testit[TESTS_MAX] = {};
+
+ init_tables();
+ if (argc == 1)
+ usage();
+
+ while ((c = getopt(argc, argv, "h:t:")) != -1) {
+ switch (c) {
+ case 'h': hashsize = strtoul(optarg, 0, 10); j++; break;
+ case 't': testnum = strtoul(optarg, 0, 10); j++; break;
+ default: usage();
+ }
+ }
+ for (i = j; i < argc; i++) {
+ for (j = 0; j < TESTS_MAX; j++) {
+ if ((strcmp(argv[i], "all") == 0)
+ || (strcmp(argv[i], tables[j]->name) == 0))
+ testit[j] = 1;
+ }
+ }
+
+ rdtsc_cal(100000000);
+
+ if (init_conntrack(testnum))
+ exit(1);
+
+ printf("Hashsize %u, testnum %u\n", hashsize, testnum);
+ for (i = 0; i < TESTS_MAX; i++) {
+ if (!(testit[i] && tables[i]))
+ continue;
+ /* Create table */
+ total_count = 0;
+ total_time = 0;
+ printf("%s: initialize\n", tables[i]->name);
+ if (!tables[i]->init(tables[i], hashsize))
+ exit(1);
+ tables[i]->report(tables[i]);
+
+ /* Run tests */
+ table_tests(tables[i], testnum,
+ conntrack_random, conntrack_dos, "random");
+ table_tests(tables[i], testnum,
+ conntrack_dos, conntrack_random, "DoS");
+
+ if (!tables[i]->destroy(tables[i]))
+ exit(1);
+ }
+ free(conntrack_random);
+ free(conntrack_dos);
+
+ return 0;
+}
Added: trunk/hashtrie/tables.h
===================================================================
--- trunk/hashtrie/tables.h 2006-03-26 18:35:08 UTC (rev 6559)
+++ trunk/hashtrie/tables.h 2006-03-28 12:14:46 UTC (rev 6560)
@@ -0,0 +1,16 @@
+#ifndef TABLES_H
+#define TABLES_H
+
+struct table_info
+{
+ char name[16];
+ int (*insert)(struct table_info *table, struct ip_conntrack_generic *ct);
+ int (*lookup)(struct table_info *table, struct ip_conntrack_generic *ct);
+ int (*delete)(struct table_info *table, struct ip_conntrack_generic *ct);
+ void (*report)(struct table_info *table);
+ int (*init)(struct table_info *table, unsigned int hashsize);
+ int (*destroy)(struct table_info *table);
+ void *data;
+};
+
+#endif
More information about the netfilter-cvslog
mailing list