Index: linux-2.6.10-bk12-Netfilter/include/linux/netfilter_ipv4/ip_conntrack_tuple.h
===================================================================
--- linux-2.6.10-bk12-Netfilter.orig/include/linux/netfilter_ipv4/ip_conntrack_tuple.h	2005-01-10 17:30:33.000000000 +1100
+++ linux-2.6.10-bk12-Netfilter/include/linux/netfilter_ipv4/ip_conntrack_tuple.h	2005-01-11 11:44:58.000000000 +1100
@@ -102,8 +102,6 @@
 /* Connections have two entries in the hash table: one for each way */
 struct ip_conntrack_tuple_hash
 {
-	struct list_head list;
-
 	struct ip_conntrack_tuple tuple;
 };
 
Index: linux-2.6.10-bk12-Netfilter/net/ipv4/netfilter/ip_conntrack_core.c
===================================================================
--- linux-2.6.10-bk12-Netfilter.orig/net/ipv4/netfilter/ip_conntrack_core.c	2005-01-11 11:42:12.000000000 +1100
+++ linux-2.6.10-bk12-Netfilter/net/ipv4/netfilter/ip_conntrack_core.c	2005-01-11 14:19:44.128755576 +1100
@@ -49,7 +49,7 @@
 #include <linux/netfilter_ipv4/ip_conntrack_core.h>
 #include <linux/netfilter_ipv4/listhelp.h>
 
-#define IP_CONNTRACK_VERSION	"2.1"
+#define IP_CONNTRACK_VERSION	"3.0"
 
 #if 0
 #define DEBUGP printk
@@ -66,9 +66,9 @@
 LIST_HEAD(ip_conntrack_expect_list);
 struct ip_conntrack_protocol *ip_ct_protos[MAX_IP_CT_PROTO];
 static LIST_HEAD(helpers);
-unsigned int ip_conntrack_htable_size = 0;
+unsigned int ip_conntrack_htable_bits;
 int ip_conntrack_max;
-struct list_head *ip_conntrack_hash;
+struct ct_hash_entry *ip_conntrack_hash;
 static kmem_cache_t *ip_conntrack_cachep;
 static kmem_cache_t *ip_conntrack_expect_cachep;
 struct ip_conntrack ip_conntrack_untracked;
@@ -88,16 +88,12 @@
 static int ip_conntrack_hash_rnd_initted;
 static unsigned int ip_conntrack_hash_rnd;
 
-static u_int32_t
-hash_conntrack(const struct ip_conntrack_tuple *tuple)
+static u32 hash_conntrack(const struct ip_conntrack_tuple *tuple)
 {
-#if 0
-	dump_tuple(tuple);
-#endif
-	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) % ip_conntrack_htable_size);
+	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);
 }
 
 int
Index: linux-2.6.10-bk12-Netfilter/include/linux/netfilter_ipv4/ip_conntrack_core.h
===================================================================
--- linux-2.6.10-bk12-Netfilter.orig/include/linux/netfilter_ipv4/ip_conntrack_core.h	2005-01-10 16:23:01.000000000 +1100
+++ linux-2.6.10-bk12-Netfilter/include/linux/netfilter_ipv4/ip_conntrack_core.h	2005-01-11 14:13:54.685878968 +1100
@@ -45,7 +45,32 @@
 	return NF_ACCEPT;
 }
 
-extern struct list_head *ip_conntrack_hash;
+/* One cacheline worth: at least 8 bits for hash acceleration. */
+#define CT_HASH_NUM							\
+	(((1<<L1_CACHE_SHIFT_MAX)					\
+		- sizeof(spinlock_t) - sizeof(struct ct_hash_entry*)) 	\
+	 / (sizeof(struct ip_conntrack *) + 1))
+
+#define CT_HASH_ENTRY_BYTES						      \
+((1<<L1_CACHE_SHIFT_MAX) - sizeof(spinlock_t) - sizeof(struct ct_hash_entry*) \
+ - sizeof(struct ip_conntrack *)*CT_HASH_NUM)
+
+#define CT_HASH_BITS ((CT_HASH_ENTRY_BYTES*8)/CT_HASH_NUM)
+
+struct ct_hash_entry
+{
+	/* Lock held by writer: readers use RCU. */
+	spinlock_t lock;
+
+	/* If we're not a terminal node, this points to page of hash entries */
+	struct ct_hash_entry *child;
+
+	/* Some number of bits per entry, to accelerate hash lookups. */
+	u8 bits[CT_HASH_ENTRY_BYTES];
+
+	struct ip_conntrack *entries[CT_HASH_NUM];
+};
+
 extern struct list_head ip_conntrack_expect_list;
 DECLARE_RWLOCK_EXTERN(ip_conntrack_lock);
 #endif /* _IP_CONNTRACK_CORE_H */
Index: linux-2.6.10-bk12-Netfilter/include/linux/netfilter_ipv4/ip_conntrack.h
===================================================================
--- linux-2.6.10-bk12-Netfilter.orig/include/linux/netfilter_ipv4/ip_conntrack.h	2005-01-11 11:42:12.000000000 +1100
+++ linux-2.6.10-bk12-Netfilter/include/linux/netfilter_ipv4/ip_conntrack.h	2005-01-11 11:44:45.000000000 +1100
@@ -193,7 +193,6 @@
 	unsigned long mark;
 #endif
 
-	/* Traversed often, so hopefully in different cacheline to top */
 	/* These are my tuples; original and reply */
 	struct ip_conntrack_tuple_hash tuplehash[IP_CT_DIR_MAX];
 };