[PATCH] locking bug in fib_semantics.c

Hello!

[IPV4]: severe locking bug in fib_semantics.c

The patch is for net-2.6.19, but the bug is present in all the kernels
since yore.

Found in 2.4 by Yixin Pan [off-list ref]. Why do we need lockdep,
when sharp-sighted eyes are available? :-)

When I read fib_semantics.c of Linux-2.4.32, write_lock(&fib_info_lock) =
is used in fib_release_info() instead of write_lock_bh(&fib_info_lock).  =
Is the following case possible: a BH interrupts fib_release_info() while =
holding the write lock, and calls ip_check_fib_default() which calls =
read_lock(&fib_info_lock), and spin forever.

Signed-off-by: Alexey Kuznetsov <redacted>
---

diff --git a/net/ipv4/fib_semantics.c b/net/ipv4/fib_semantics.c
index 4ea6c68..5dfdad5 100644
--- a/net/ipv4/fib_semantics.c
+++ b/net/ipv4/fib_semantics.c

@@ -159,7 +159,7 @@ void free_fib_info(struct fib_info *fi)
 
 void fib_release_info(struct fib_info *fi)
 {
-	spin_lock(&fib_info_lock);
+	spin_lock_bh(&fib_info_lock);
 	if (fi && --fi->fib_treeref == 0) {
 		hlist_del(&fi->fib_hash);
 		if (fi->fib_prefsrc)

@@ -172,7 +172,7 @@ void fib_release_info(struct fib_info *f
 		fi->fib_dead = 1;
 		fib_info_put(fi);
 	}
-	spin_unlock(&fib_info_lock);
+	spin_unlock_bh(&fib_info_lock);
 }
 
 static __inline__ int nh_comp(const struct fib_info *fi, const struct fib_info *ofi)

@@ -598,7 +598,7 @@ static void fib_hash_move(struct hlist_h
 	unsigned int old_size = fib_hash_size;
 	unsigned int i, bytes;
 
-	spin_lock(&fib_info_lock);
+	spin_lock_bh(&fib_info_lock);
 	old_info_hash = fib_info_hash;
 	old_laddrhash = fib_info_laddrhash;
 	fib_hash_size = new_size;

@@ -639,7 +639,7 @@ static void fib_hash_move(struct hlist_h
 	}
 	fib_info_laddrhash = new_laddrhash;
 
-	spin_unlock(&fib_info_lock);
+	spin_unlock_bh(&fib_info_lock);
 
 	bytes = old_size * sizeof(struct hlist_head *);
 	fib_hash_free(old_info_hash, bytes);

@@ -820,7 +820,7 @@ link_it:
 
 	fi->fib_treeref++;
 	atomic_inc(&fi->fib_clntref);
-	spin_lock(&fib_info_lock);
+	spin_lock_bh(&fib_info_lock);
 	hlist_add_head(&fi->fib_hash,
 		       &fib_info_hash[fib_info_hashfn(fi)]);
 	if (fi->fib_prefsrc) {

@@ -839,7 +839,7 @@ link_it:
 		head = &fib_info_devhash[hash];
 		hlist_add_head(&nh->nh_hash, head);
 	} endfor_nexthops(fi)
-	spin_unlock(&fib_info_lock);
+	spin_unlock_bh(&fib_info_lock);
 	return fi;
 
 err_inval:

From: Alexey Kuznetsov <redacted>
Date: Thu, 17 Aug 2006 13:36:15 +0400

Found in 2.4 by Yixin Pan [off-list ref]. Why do we need lockdep,
when sharp-sighted eyes are available? :-)

Lockdep can only tell us about code paths which actually have been
run, so it shows that nobody running lockdep has had a redirect arrive
on a non-shared-media device marked for secure redirects :)

But such a code path would only need to run once for lockdep to catch
it.

quoted

When I read fib_semantics.c of Linux-2.4.32, write_lock(&fib_info_lock) =
is used in fib_release_info() instead of write_lock_bh(&fib_info_lock).  =
Is the following case possible: a BH interrupts fib_release_info() while =
holding the write lock, and calls ip_check_fib_default() which calls =
read_lock(&fib_info_lock), and spin forever.

Signed-off-by: Alexey Kuznetsov <redacted>

Good spotting.  Patch applied, and I'll push this to -stable too.

Thanks a lot.

On 17-08-2006 11:36, Alexey Kuznetsov wrote:

Hello!

[IPV4]: severe locking bug in fib_semantics.c

The patch is for net-2.6.19, but the bug is present in all the kernels
since yore.

Found in 2.4 by Yixin Pan [off-list ref]. Why do we need lockdep,
when sharp-sighted eyes are available? :-)

quoted

When I read fib_semantics.c of Linux-2.4.32, write_lock(&fib_info_lock) =
is used in fib_release_info() instead of write_lock_bh(&fib_info_lock).  =
Is the following case possible: a BH interrupts fib_release_info() while =
holding the write lock, and calls ip_check_fib_default() which calls =
read_lock(&fib_info_lock), and spin forever.

But I hope the real reason for this patch isn't exactly like that.
Could fib_release_info() be interrupted by BH really?

Jarek P.

From: Jarek Poplawski <redacted>
Date: Mon, 21 Aug 2006 10:16:43 +0200

On 17-08-2006 11:36, Alexey Kuznetsov wrote:

quoted

Hello!

[IPV4]: severe locking bug in fib_semantics.c

The patch is for net-2.6.19, but the bug is present in all the kernels
since yore.

Found in 2.4 by Yixin Pan [off-list ref]. Why do we need lockdep,
when sharp-sighted eyes are available? :-)

quoted

When I read fib_semantics.c of Linux-2.4.32, write_lock(&fib_info_lock) =
is used in fib_release_info() instead of write_lock_bh(&fib_info_lock).  =
Is the following case possible: a BH interrupts fib_release_info() while =
holding the write lock, and calls ip_check_fib_default() which calls =
read_lock(&fib_info_lock), and spin forever.

But I hope the real reason for this patch isn't exactly like that.
Could fib_release_info() be interrupted by BH really?

Absolutely, yes it can.  What makes you think it can't?

All of the call sites I have checked cause it to run with
BH's enabled, and that allows ip_fib_check_default() to
potentially run.  All we need is one such case to cause
the deadlock.

I was skeptical of this case too, until I checked how
fib_release_info() was called.

On 21-08-2006 10:17, David Miller wrote:

From: Jarek Poplawski <redacted>
Date: Mon, 21 Aug 2006 10:16:43 +0200

...

quoted

But I hope the real reason for this patch isn't exactly like that.
Could fib_release_info() be interrupted by BH really?

Absolutely, yes it can.  What makes you think it can't?

All of the call sites I have checked cause it to run with
BH's enabled, and that allows ip_fib_check_default() to
potentially run.  All we need is one such case to cause
the deadlock.

I was skeptical of this case too, until I checked how
fib_release_info() was called.

I overlooked this - so I've to sharpen my sight and look at it 
again - now knowing it's there.
Thanks for your response. I didn't expect it so fast and right 
from the top!

Jarek P.

On Mon, Aug 21, 2006 at 01:02:01PM +0200, Jarek Poplawski wrote:

On 21-08-2006 10:17, David Miller wrote:

quoted

From: Jarek Poplawski <redacted>
Date: Mon, 21 Aug 2006 10:16:43 +0200

...

quoted

I was skeptical of this case too, until I checked how
fib_release_info() was called.

I overlooked this - so I've to sharpen my sight and look at it 
again - now knowing it's there.

...

Hello,
I've found it at last but on that occasion I've got some
doubt according to rcu_read_lock and rcu_call treatment:
isn't it "illegal to block while in an RCU read-side
section"? And I think it takes place in:

fib_lookup(): from tb_insert (fn_hash_insert() or
  fn_trie_insert()), fib_create_info(), fib_check_nh() 

fn_trie_lookup(): like above, inet_addr_type(),
  tb_lookup()

fib_rule_put(): like #1 above or #2 after tb_lookup(),
  fib_res_put()

Shouldn't there be _bh also?

Jarek P.

PS: linux-2.6.18-rc4

On Tue, Aug 22, 2006 at 12:35:56PM +0200, Jarek Poplawski wrote:
... 

Hello,
I've found it at last but on that occasion I've got some
doubt according to rcu_read_lock and rcu_call treatment:

...

Actually there is one more doubt (bug really, but
not very probable): proc file reading is without any
locking in fib_hash.c, so if somebody uses programs
which do that often, he could have problems while
adding or deleting a route in a wrong time. If it
will be ever changed, fz_nent should also be ++/--
under lock, I think. 

Jarek P.
 
PS: linux-2.6.18-rc4

On Tue, 22 Aug 2006 12:35:56 +0200
Jarek Poplawski [off-list ref] wrote:

On Mon, Aug 21, 2006 at 01:02:01PM +0200, Jarek Poplawski wrote:

quoted

On 21-08-2006 10:17, David Miller wrote:

quoted

From: Jarek Poplawski <redacted>
Date: Mon, 21 Aug 2006 10:16:43 +0200

...

quoted

I was skeptical of this case too, until I checked how
fib_release_info() was called.

I overlooked this - so I've to sharpen my sight and look at it 
again - now knowing it's there.

...

Hello,
I've found it at last but on that occasion I've got some
doubt according to rcu_read_lock and rcu_call treatment:
isn't it "illegal to block while in an RCU read-side
section"? And I think it takes place in:

No, it is perfectly okay for a cpu to acquire a lock
while in an RCU section, it just can't acquire a mutex/semaphore that
will put it to sleep. That is caught by the might_sleep() check.

fib_lookup(): from tb_insert (fn_hash_insert() or
  fn_trie_insert()), fib_create_info(), fib_check_nh() 

fn_trie_lookup(): like above, inet_addr_type(),
  tb_lookup()

fib_rule_put(): like #1 above or #2 after tb_lookup(),
  fib_res_put()

Shouldn't there be _bh also?

fib_rule_put only does something if refcount == 1 in which
case it is safe.

Jarek P.

PS: linux-2.6.18-rc4
-
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

On 23-08-2006 20:31, Stephen Hemminger wrote:

On Tue, 22 Aug 2006 12:35:56 +0200
Jarek Poplawski [off-list ref] wrote:

...

quoted

I've found it at last but on that occasion I've got some
doubt according to rcu_read_lock and rcu_call treatment:
isn't it "illegal to block while in an RCU read-side
section"? And I think it takes place in:

No, it is perfectly okay for a cpu to acquire a lock
while in an RCU section, it just can't acquire a mutex/semaphore that
will put it to sleep. That is caught by the might_sleep() check.

Then I've wrongly understood it can't sleep while in RCU
and that enabled bh can make it sleep.

quoted

fib_lookup(): from tb_insert (fn_hash_insert() or
  fn_trie_insert()), fib_create_info(), fib_check_nh() 

fn_trie_lookup(): like above, inet_addr_type(),
  tb_lookup()

fib_rule_put(): like #1 above or #2 after tb_lookup(),
  fib_res_put()

Shouldn't there be _bh also?

fib_rule_put only does something if refcount == 1 in which
case it is safe.

It's like above. I've thought (wrongly): fib_rule_put() calls 
call_rcu() and is made to sleep.

Thanks for explaining: now I can peacefully go... to sleep!

Jarek P.

Jarek Poplawski wrote:

On 23-08-2006 20:31, Stephen Hemminger wrote:

quoted

On Tue, 22 Aug 2006 12:35:56 +0200
Jarek Poplawski [off-list ref] wrote:

...

quoted

quoted

I've found it at last but on that occasion I've got some
doubt according to rcu_read_lock and rcu_call treatment:
isn't it "illegal to block while in an RCU read-side
section"? And I think it takes place in:

No, it is perfectly okay for a cpu to acquire a lock
while in an RCU section, it just can't acquire a mutex/semaphore that
will put it to sleep. That is caught by the might_sleep() check.

Then I've wrongly understood it can't sleep while in RCU
and that enabled bh can make it sleep.

quoted

quoted

fib_lookup(): from tb_insert (fn_hash_insert() or
  fn_trie_insert()), fib_create_info(), fib_check_nh()
fn_trie_lookup(): like above, inet_addr_type(),
  tb_lookup()

fib_rule_put(): like #1 above or #2 after tb_lookup(),
  fib_res_put()

Shouldn't there be _bh also?

fib_rule_put only does something if refcount == 1 in which
case it is safe.

It's like above. I've thought (wrongly): fib_rule_put() calls 
call_rcu() and is made to sleep.

call_rcu() doesn't sleep, it schedules work in a later context.  In that 
way call_rcu()
is like other deferred work mechanism (tasklets, timers, workqueues).