Fix race condition in early drop

PATCH In review Pablo Neira Ayuso 4 participants 8 messages Aug 21, 2006 – Aug 24, 2006 2 messages not in the archive

Subsystems (2)

Networking netfilter

lore

Share & tools

lore

Pablo Neira Ayuso

author maintainer

2006-08-21 08:47 UTC #0 lore raw

PATCH 3/3 Fix race condition in early drop

[CONNTRACK] Fix race condition in early drop

On SMP environments the maximum number of conntracks can be overpassed under heavy stress situations due to an existing race condition.

CPU A CPU B
atomic_read() ...
early_drop() ...
... atomic_read()
allocate conntrack allocate conntrack
atomic_inc() atomic_inc()

This patch uses an optimistic approach to solve the concurrency problem.

Signed-off-by Pablo Neira Ayuso <[email protected]>

Signature · 1 line

The dawn of the fourth age of Linux firewalling is coming; a time of great struggle and heroic deeds -- J.Kadlecsik got inspired by J.Morris

[CONNTRACK] Fix race condition in early drop

On SMP environments the maximum number of conntracks can be overpassed under heavy stress situations due to an existing race condition.

CPU A CPU B
atomic_read() ...
early_drop() ...
... atomic_read()
allocate conntrack allocate conntrack
atomic_inc() atomic_inc()

This patch uses an optimistic approach to solve the concurrency problem.

Signed-off-by Pablo Neira Ayuso <[email protected]>

net/ipv4/netfilter/ip_conntrack_core.c +19 ~~-10~~

Index: net-2.6/net/ipv4/netfilter/ip_conntrack_core.c
===================================================================
@@ -642,21 +642,32 @@ struct ip_conntrack *ip_conntrack_alloc(
 	}
 
 	if (ip_conntrack_max
-	    && atomic_read(&ip_conntrack_count) >= ip_conntrack_max) {
+	    && !atomic_add_unless(&ip_conntrack_count, 1, ip_conntrack_max)) {
 		unsigned int hash = hash_conntrack(orig);
 		/* Try dropping from this hash chain. */
-		if (!early_drop(&ip_conntrack_hash[hash])) {
-			if (net_ratelimit())
-				printk(KERN_WARNING
-				       "ip_conntrack: table full, dropping"
-				       " packet.\n");
-			return ERR_PTR(-ENOMEM);
-		}
+		do {
+			if (!early_drop(&ip_conntrack_hash[hash])) {
+				if (net_ratelimit())
+					printk(KERN_WARNING
+					       "ip_conntrack: table full, "
+					       "dropping packet.\n");
+				return ERR_PTR(-ENOMEM);
+			}
+			/*
+			 * On SMP environments, if the table is full and we
+			 * early drop a conntrack to make some place for this
+			 * new one then we have to ensure that no other
+			 * conntrack slips through.
+			 */
+		} while (!atomic_add_unless(&ip_conntrack_count, 
+					    1, 
+					    ip_conntrack_max));
 	}
 
 	conntrack = kmem_cache_alloc(ip_conntrack_cachep, GFP_ATOMIC);
 	if (!conntrack) {
 		DEBUGP("Can't allocate conntrack.\n");
+		atomic_dec(&ip_conntrack_count);
 		return ERR_PTR(-ENOMEM);
 	}

@@ -670,8 +681,6 @@ struct ip_conntrack *ip_conntrack_alloc(
 	conntrack->timeout.data = (unsigned long)conntrack;
 	conntrack->timeout.function = death_by_timeout;
 
-	atomic_inc(&ip_conntrack_count);
-
 	return conntrack;
 }

net/netfilter/nf_conntrack_core.c +22 -9

Index: net-2.6/net/netfilter/nf_conntrack_core.c
===================================================================
@@ -868,16 +868,26 @@ __nf_conntrack_alloc(const struct nf_con
 	}
 
 	if (nf_conntrack_max
-	    && atomic_read(&nf_conntrack_count) >= nf_conntrack_max) {
+	    && !atomic_add_unless(&nf_conntrack_count, 1, nf_conntrack_max)) {
 		unsigned int hash = hash_conntrack(orig);
 		/* Try dropping from this hash chain. */
-		if (!early_drop(&nf_conntrack_hash[hash])) {
-			if (net_ratelimit())
-				printk(KERN_WARNING
-				       "nf_conntrack: table full, dropping"
-				       " packet.\n");
-			return ERR_PTR(-ENOMEM);
-		}
+		do {
+			if (!early_drop(&nf_conntrack_hash[hash])) {
+				if (net_ratelimit())
+					printk(KERN_WARNING
+					       "ip_conntrack: table full, "
+					       "dropping packet.\n");
+				return ERR_PTR(-ENOMEM);
+			}
+			/*
+			 * On SMP environments, if the table is full and we
+			 * early drop a conntrack to make some place for this
+			 * new one then we have to ensure that no other
+			 * conntrack slips through.
+			 */
+		} while (!atomic_add_unless(&nf_conntrack_count, 
+					    1, 
+					    nf_conntrack_max));
 	}
 
 	/*  find features needed by this conntrack. */

@@ -923,9 +933,12 @@ __nf_conntrack_alloc(const struct nf_con
 	conntrack->timeout.data = (unsigned long)conntrack;
 	conntrack->timeout.function = death_by_timeout;
 
-	atomic_inc(&nf_conntrack_count);
+	read_unlock_bh(&nf_ct_cache_lock);
+	return conntrack;
+
 out:
 	read_unlock_bh(&nf_ct_cache_lock);
+	atomic_dec(&nf_conntrack_count);
 	return conntrack;
 }

Yasuyuki KOZAKAI

2006-08-22 04:35 UTC #1 lore raw

Hi, Pablo,

From: Pablo Neira Ayuso <[email protected]>
Date: Mon, 21 Aug 2006 10:47:49 +0200

Quoted 5 lines

[CONNTRACK] Fix race condition in early drop
On SMP environments the maximum number of conntracks can be overpassed under heavy stress situations due to an existing race condition.

Quoted 8 lines

CPU A CPU B
atomic_read() ...
early_drop() ...
... atomic_read()
allocate conntrack allocate conntrack
atomic_inc() atomic_inc()
This patch uses an optimistic approach to solve the concurrency problem.

Good catch!

Quoted 27 lines

Index: net-2.6/net/netfilter/nf_conntrack_core.c
===================================================================

net/netfilter/nf_conntrack_core.c +9 -8

@@ -868,16 +868,26 @@ __nf_conntrack_alloc(const struct nf_con
 	}
 
 	if (nf_conntrack_max
-	    && atomic_read(&nf_conntrack_count) >= nf_conntrack_max) {
+	    && !atomic_add_unless(&nf_conntrack_count, 1, nf_conntrack_max)) {
 		unsigned int hash = hash_conntrack(orig);
 		/* Try dropping from this hash chain. */
-		if (!early_drop(&nf_conntrack_hash[hash])) {
-			if (net_ratelimit())
-				printk(KERN_WARNING
-				       "nf_conntrack: table full, dropping"
-				       " packet.\n");
-			return ERR_PTR(-ENOMEM);
-		}
+		do {
+			if (!early_drop(&nf_conntrack_hash[hash])) {
+				if (net_ratelimit())
+					printk(KERN_WARNING
+					       "ip_conntrack: table full, "
+					       "dropping packet.\n");
+				return ERR_PTR(-ENOMEM);
+			}

net/netfilter/nf_conntrack_core.c __nf_conntrack_alloc(const struct nf_con · line 891

Quoted 10 lines

net/netfilter/nf_conntrack_core.c +9 -0

+			/*
+			 * On SMP environments, if the table is full and we
+			 * early drop a conntrack to make some place for this
+			 * new one then we have to ensure that no other
+			 * conntrack slips through.
+			 */
+		} while (!atomic_add_unless(&nf_conntrack_count, 
+					    1, 
+					    nf_conntrack_max));
 	}

I think there is unfair case like following.

       CPU A                   CPU B
    atomic_add_unless() == 0
    early_drop()                  ...
       ...                     atomic_add_unless() == 1
    atomic_add_unless() == 0
    early_drop()

The right to allocate conntrack is stolen by CPU B in this case. And there is no assurance that CPU A can exits this loop in short time.

How about incrementing {ip,nf}_conntrack_count at first ?

1. atomic_add()
2. if {ip,nf}_conntrack_count > {ip,nf}_conntrack_max (not '>=' ) then early_drop()
3. if early_drop() failed, atomic_dec()

-- Yasuyuki Kozakai

A message that is not in the archive (sent off-list or not yet received): [email protected]

Pablo Neira Ayuso

author maintainer

2006-08-22 13:46 UTC #3 lore raw

Hi Yasuyuki,

Quoted 15 lines · Yasuyuki KOZAKAI

From: Pablo Neira Ayuso <[email protected]>
Date: Mon, 21 Aug 2006 10:47:49 +0200
Quoted 12 lines
[CONNTRACK] Fix race condition in early drop
On SMP environments the maximum number of conntracks can be overpassed under heavy stress situations due to an existing race condition.
CPU A CPU B
atomic_read() ...
early_drop() ...
... atomic_read()
allocate conntrack allocate conntrack
atomic_inc() atomic_inc()

[snip]

Quoted 11 lines

I think there is unfair case like following.
       CPU A                   CPU B
    atomic_add_unless() == 0
    early_drop()                  ...
       ...                     atomic_add_unless() == 1
    atomic_add_unless() == 0
    early_drop()
The right to allocate conntrack is stolen by CPU B in this case.

Yes, but we're under stress so I'm not sure if fairness is important here.

Quoted 1 line

And there is no assurance that CPU A can exits this loop in short time.

You are right, this seems important. Instead of looping we can just give up if we lose race.

Quoted 6 lines

How about incrementing {ip,nf}_conntrack_count at first ?
1. atomic_add()
2. if {ip,nf}_conntrack_count > {ip,nf}_conntrack_max (not '>=' ) then early_drop()
3. if early_drop() failed, atomic_dec()

I thought about this possibility but then we can't guarantee the fixed maximum number of conntracks in the system.

Any comments?

Signature · 1 line

The dawn of the fourth age of Linux firewalling is coming; a time of great struggle and heroic deeds -- J.Kadlecsik got inspired by J.Morris

Pablo Neira Ayuso

author maintainer

2006-08-22 14:39 UTC #4 lore raw

Quoted 9 lines · Pablo Neira Ayuso

Quoted 6 lines
How about incrementing {ip,nf}_conntrack_count at first ?
1. atomic_add()
2. if {ip,nf}_conntrack_count > {ip,nf}_conntrack_max (not '>=' ) then early_drop()
3. if early_drop() failed, atomic_dec()
I thought about this possibility but then we can't guarantee the fixed maximum number of conntracks in the system.

Hm, actually this is wrong, we can guarantee the maximum number but aren't we somehow fooling the counter? I mean, the counter can reach values higher than conntrack_max during a short period.

Signature · 1 line

The dawn of the fourth age of Linux firewalling is coming; a time of great struggle and heroic deeds -- J.Kadlecsik got inspired by J.Morris

Yasuyuki KOZAKAI

2006-08-23 02:28 UTC #5 lore raw

Hi,

From: Pablo Neira Ayuso <[email protected]>
Date: Tue, 22 Aug 2006 16:39:23 +0200

Quoted 9 lines

Quoted 8 lines · Pablo Neira Ayuso
Quoted 6 lines
How about incrementing {ip,nf}_conntrack_count at first ?
1. atomic_add()
2. if {ip,nf}_conntrack_count > {ip,nf}_conntrack_max (not '>=' ) then early_drop()
3. if early_drop() failed, atomic_dec()

Quoted 6 lines

Quoted 2 lines
I thought about this possibility but then we can't guarantee the fixed maximum number of conntracks in the system.
Hm, actually this is wrong, we can guarantee the maximum number but aren't we somehow fooling the counter? I mean, the counter can reach values higher than conntrack_max during a short period.

good point. I don't mind fooling the counter in this short period, indeed someone might mind that. Then,

From: Pablo Neira Ayuso <[email protected]>
Date: Tue, 22 Aug 2006 15:46:50 +0200

Quoted 4 lines

Quoted 1 line
And there is no assurance that CPU A can exits this loop in short time.
You are right, this seems important. Instead of looping we can just give up if we lose race.

Now I think this is better.

-- Yasuyuki Kozakai

A message that is not in the archive (sent off-list or not yet received): [email protected]

Patrick McHardy

2006-08-23 04:38 UTC #7 lore raw

Quoted 13 lines · Yasuyuki KOZAKAI

Quoted 13 lines
Quoted 10 lines · Pablo Neira Ayuso
Quoted 6 lines
How about incrementing {ip,nf}_conntrack_count at first ?
1. atomic_add()
2. if {ip,nf}_conntrack_count > {ip,nf}_conntrack_max (not '>=' ) then early_drop()
3. if early_drop() failed, atomic_dec()
I thought about this possibility but then we can't guarantee the fixed maximum number of conntracks in the system.

Quoted 6 lines

Quoted 3 lines
Hm, actually this is wrong, we can guarantee the maximum number but aren't we somehow fooling the counter? I mean, the counter can reach values higher than conntrack_max during a short period.
good point. I don't mind fooling the counter in this short period,

Me neither. We can already be off by more than one since early_drop just removes a conntrack from the hash tables, but it is not necessarily destroyed immediately (at which point the counter is decremented). This is a reason why we can't loop while waiting for the counter to decrement.

Jarek Poplawski

2006-08-24 11:47 UTC #8 lore raw

In reply to Pablo Neira Ayuso

Quoted 39 lines · Pablo Neira Ayuso

Hi Yasuyuki,
Quoted 15 lines · Yasuyuki KOZAKAI
From: Pablo Neira Ayuso <[email protected]>
Date: Mon, 21 Aug 2006 10:47:49 +0200
Quoted 12 lines
[CONNTRACK] Fix race condition in early drop
On SMP environments the maximum number of conntracks can be overpassed under heavy stress situations due to an existing race condition.
CPU A CPU B
atomic_read() ...
early_drop() ...
... atomic_read()
allocate conntrack allocate conntrack
atomic_inc() atomic_inc()
[snip]
Quoted 11 lines
I think there is unfair case like following.
       CPU A                   CPU B
    atomic_add_unless() == 0
    early_drop()                  ...
       ...                     atomic_add_unless() == 1
    atomic_add_unless() == 0
    early_drop()
The right to allocate conntrack is stolen by CPU B in this case.
Yes, but we're under stress so I'm not sure if fairness is important here.
Quoted 1 line
And there is no assurance that CPU A can exits this loop in short time.
You are right, this seems important. Instead of looping we can just give up if we lose race.
Quoted 2 lines
How about incrementing {ip,nf}_conntrack_count at first ?

Quoted 8 lines

Quoted 4 lines
1. atomic_add()
2. if {ip,nf}_conntrack_count > {ip,nf}_conntrack_max (not '>=' ) then early_drop()
3. if early_drop() failed, atomic_dec()
I thought about this possibility but then we can't guarantee the fixed maximum number of conntracks in the system.
Any comments?

Sorry, maybe I'm to fresh, but if you say "any"... Maybe something simpler? I attach a proposal.

Jarek P.

net/netfilter//nf_conntrack_core.c renamed from net/netfilter/nf_conntrack_core.c- +7 -1

@@ -871,6 +871,7 @@
 		unsigned int hash = hash_conntrack(orig);
 		/* Try dropping from this hash chain. */
 		if (!early_drop(&nf_conntrack_hash[hash])) {
+			atomic_dec(&nf_conntrack_count);
 			if (net_ratelimit())
 				printk(KERN_WARNING
 				       "nf_conntrack: table full, dropping"

@@ -905,6 +906,12 @@
 		goto out;
 	}
 
+	if (!atomic_add_unless(&nf_conntrack_count, 1, nf_conntrack_max) {
+		kmem_cache_free(nf_ct_cache[features].cachep, conntrack);
+		conntrack = NULL;
+		goto out;
+	}
+
 	memset(conntrack, 0, nf_ct_cache[features].size);
 	conntrack->features = features;
 	if (helper) {

@@ -922,7 +929,6 @@
 	conntrack->timeout.data = (unsigned long)conntrack;
 	conntrack->timeout.function = death_by_timeout;
 
-	atomic_inc(&nf_conntrack_count);
 out:
 	read_unlock_bh(&nf_ct_cache_lock);
 	return conntrack;

Jarek Poplawski

2006-08-24 13:02 UTC #9 lore raw

On 24-08-2006 13:47, Jarek Poplawski wrote:
...

Sorry again, I'm definitely too fresh. It should be even shorter:

Jarek P.

net/netfilter//nf_conntrack_core.c renamed from net/netfilter/nf_conntrack_core.c- +6 -1

@@ -905,6 +906,12 @@
 		goto out;
 	}
 
+	if (!atomic_add_unless(&nf_conntrack_count, 1, nf_conntrack_max) {
+		kmem_cache_free(nf_ct_cache[features].cachep, conntrack);
+		conntrack = NULL;
+		goto out;
+	}
+
 	memset(conntrack, 0, nf_ct_cache[features].size);
 	conntrack->features = features;
 	if (helper) {

@@ -922,7 +929,6 @@
 	conntrack->timeout.data = (unsigned long)conntrack;
 	conntrack->timeout.function = death_by_timeout;
 
-	atomic_inc(&nf_conntrack_count);
 out:
 	read_unlock_bh(&nf_ct_cache_lock);
 	return conntrack;