[PATCH] locking bug in fib_semantics.c

[PATCH] locking bug in fib_semantics.c

[Alexey Kuznetsov]

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 <yxpan@hotmail.com>. 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 <kuznet@ms2.inr.ac.ru>
---

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:

Re: [PATCH] locking bug in fib_semantics.c

[David Miller]

From: Alexey Kuznetsov <kuznet@ms2.inr.ac.ru>
Date: Thu, 17 Aug 2006 13:36:15 +0400

> Found in 2.4 by Yixin Pan <yxpan@hotmail.com>. 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.

> > 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 <kuznet@ms2.inr.ac.ru>

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

Thanks a lot.

Re: [PATCH] locking bug in fib_semantics.c

[Jarek Poplawski]

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 <yxpan@hotmail.com>. 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.

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.

Re: [PATCH] locking bug in fib_semantics.c

[David Miller]

From: Jarek Poplawski <jarkao2@o2.pl>
Date: Mon, 21 Aug 2006 10:16:43 +0200

> 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 <yxpan@hotmail.com>. 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.
> 
> 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.

Re: [PATCH] locking bug in fib_semantics.c

[Jarek Poplawski]

On 21-08-2006 10:17, David Miller wrote:
> From: Jarek Poplawski <jarkao2@o2.pl>
> Date: Mon, 21 Aug 2006 10:16:43 +0200
...
>> 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.

Re: [PATCH] locking bug in fib_semantics.c

[Jarek Poplawski]

On Mon, Aug 21, 2006 at 01:02:01PM +0200, Jarek Poplawski wrote:
> On 21-08-2006 10:17, David Miller wrote:
> > From: Jarek Poplawski <jarkao2@o2.pl>
> > Date: Mon, 21 Aug 2006 10:16:43 +0200
> ...
> > 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

Re: [PATCH] locking bug in fib_semantics.c

[Jarek Poplawski]

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

Re: [PATCH] locking bug in fib_semantics.c

[Stephen Hemminger]

On Tue, 22 Aug 2006 12:35:56 +0200
Jarek Poplawski <jarkao2@o2.pl> wrote:

> On Mon, Aug 21, 2006 at 01:02:01PM +0200, Jarek Poplawski wrote:
> > On 21-08-2006 10:17, David Miller wrote:
> > > From: Jarek Poplawski <jarkao2@o2.pl>
> > > Date: Mon, 21 Aug 2006 10:16:43 +0200
> > ...
> > > 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

Re: [PATCH] locking bug in fib_semantics.c

[Jarek Poplawski]

On 23-08-2006 20:31, Stephen Hemminger wrote:
> On Tue, 22 Aug 2006 12:35:56 +0200
> Jarek Poplawski <jarkao2@o2.pl> wrote:
...
>> 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.

>> 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.

Re: [PATCH] locking bug in fib_semantics.c

[Stephen Hemminger]

Jarek Poplawski wrote:
> On 23-08-2006 20:31, Stephen Hemminger wrote:
>> On Tue, 22 Aug 2006 12:35:56 +0200
>> Jarek Poplawski <jarkao2@o2.pl> wrote:
> ...
>>> 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.
>
>>> 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).