From mboxrd@z Thu Jan 1 00:00:00 1970 From: Patrick McHardy Subject: [NETFILTER 42/50]: nf_conntrack: early_drop improvement Date: Sat, 7 Jul 2007 14:23:59 +0200 (MEST) Message-ID: <20070707122315.1589.61669.sendpatchset@localhost.localdomain> References: <20070707122215.1589.12100.sendpatchset@localhost.localdomain> Cc: netfilter-devel@lists.netfilter.org, Patrick McHardy To: davem@davemloft.net Return-path: In-Reply-To: <20070707122215.1589.12100.sendpatchset@localhost.localdomain> List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: netfilter-devel-bounces@lists.netfilter.org Errors-To: netfilter-devel-bounces@lists.netfilter.org List-Id: netfilter-devel.vger.kernel.org [NETFILTER]: nf_conntrack: early_drop improvement When the maximum number of conntrack entries is reached and a new one needs to be allocated, conntrack tries to drop an unassured connection from the same hash bucket the new conntrack would hash to. Since with a properly sized hash the average number of entries per bucket is 1, the chances of actually finding one are not very good. This patch makes it walk the hash until a minimum number of 8 entries are checked. Based on patch by Vasily Averin . Signed-off-by: Patrick McHardy --- commit a145c8a34ab8aee235642d69b4fbc56846e92e63 tree 1f8409b20bcad056f6590fa32dc4ae4e0924f798 parent 0609c74ca5cb508da390c17a2ad706a8583f2b7e author Patrick McHardy Sat, 07 Jul 2007 12:16:01 +0200 committer Patrick McHardy Sat, 07 Jul 2007 12:16:01 +0200 net/netfilter/nf_conntrack_core.c | 22 +++++++++++++++------- 1 files changed, 15 insertions(+), 7 deletions(-) diff --git a/net/netfilter/nf_conntrack_core.c b/net/netfilter/nf_conntrack_core.c index d1fc019..472396d 100644 --- a/net/netfilter/nf_conntrack_core.c +++ b/net/netfilter/nf_conntrack_core.c @@ -377,21 +377,30 @@ nf_conntrack_tuple_taken(const struct nf_conntrack_tuple *tuple, } EXPORT_SYMBOL_GPL(nf_conntrack_tuple_taken); +#define NF_CT_EVICTION_RANGE 8 + /* There's a small race here where we may free a just-assured connection. Too bad: we're in trouble anyway. */ -static int early_drop(struct hlist_head *chain) +static int early_drop(unsigned int hash) { /* Use oldest entry, which is roughly LRU */ struct nf_conntrack_tuple_hash *h; struct nf_conn *ct = NULL, *tmp; struct hlist_node *n; + unsigned int i, cnt = 0; int dropped = 0; read_lock_bh(&nf_conntrack_lock); - hlist_for_each_entry(h, n, chain, hnode) { - tmp = nf_ct_tuplehash_to_ctrack(h); - if (!test_bit(IPS_ASSURED_BIT, &tmp->status)) - ct = tmp; + for (i = 0; i < nf_conntrack_htable_size; i++) { + hlist_for_each_entry(h, n, &nf_conntrack_hash[hash], hnode) { + tmp = nf_ct_tuplehash_to_ctrack(h); + if (!test_bit(IPS_ASSURED_BIT, &tmp->status)) + ct = tmp; + cnt++; + } + if (ct || cnt >= NF_CT_EVICTION_RANGE) + break; + hash = (hash + 1) % nf_conntrack_htable_size; } if (ct) atomic_inc(&ct->ct_general.use); @@ -425,8 +434,7 @@ struct nf_conn *nf_conntrack_alloc(const struct nf_conntrack_tuple *orig, if (nf_conntrack_max && atomic_read(&nf_conntrack_count) > nf_conntrack_max) { unsigned int hash = hash_conntrack(orig); - /* Try dropping from this hash chain. */ - if (!early_drop(&nf_conntrack_hash[hash])) { + if (!early_drop(hash)) { atomic_dec(&nf_conntrack_count); if (net_ratelimit()) printk(KERN_WARNING