[PATCH] jump label: close race in jump_label_inc() vs. jump_label_dec()

[PATCH] jump label: close race in jump_label_inc() vs. jump_label_dec()

[Jason Baron]

The previous fix to ensure that jump_label_inc() does not return until the jump
is completely patched, opened up a race in the inc/dec path. The scenario is:

key->enabled = 0;

	CPU 0					CPU 1
        ----- 					-----

jump_label_inc():			jump_label_dec():

1) if (atomic_read(&key->enabled) == 0)
	jump_label_update(key, JUMP_LABEL_ENABLE);

					 2) if (!atomic_dec_and_mutex_lock(&key->enabled, &jump_label_mutex))
					 	return;

3) atomic_inc(&key->enabled);

So now, key->enabled = 0, but the jump has been enabled, which is an invalid
state.

Fix this, by returning to the old, atomic inc/dec logic, but adding a check
to see if we are in the middle of an enabling operation, so that we
don't return early.

Signed-off-by: Jason Baron <jbaron@redhat.com>
---
 kernel/jump_label.c |   15 ++++++++++++---
 1 files changed, 12 insertions(+), 3 deletions(-)

diff --git a/kernel/jump_label.c b/kernel/jump_label.c
index 30c3c77..4ae9fa2 100644
--- a/kernel/jump_label.c
+++ b/kernel/jump_label.c
@@ -62,13 +62,22 @@ static void jump_label_update(struct jump_label_key *key, int enable);
 
 void jump_label_inc(struct jump_label_key *key)
 {
-	if (atomic_inc_not_zero(&key->enabled))
+	int not_zero;
+
+	not_zero = atomic_inc_not_zero(&key->enabled);
+	if (not_zero && !mutex_is_locked(&jump_label_mutex))
+		return;
+
+	if (not_zero) {
+		/* prevent from returning before we've switched the branch */
+		jump_label_lock();
+		jump_label_unlock();
 		return;
+	}
 
 	jump_label_lock();
-	if (atomic_read(&key->enabled) == 0)
+	if (atomic_add_return(1, &key->enabled) == 1)
 		jump_label_update(key, JUMP_LABEL_ENABLE);
-	atomic_inc(&key->enabled);
 	jump_label_unlock();
 }
 
-- 
1.7.7.3

Re: [PATCH] jump label: close race in jump_label_inc() vs. jump_label_dec()

[Gleb Natapov]

On Wed, Jan 04, 2012 at 10:32:37AM -0500, Jason Baron wrote:
> The previous fix to ensure that jump_label_inc() does not return until the jump
> is completely patched, opened up a race in the inc/dec path. The scenario is:
> 
> key->enabled = 0;
> 
> 	CPU 0					CPU 1
>         ----- 					-----
> 
> jump_label_inc():			jump_label_dec():
> 
> 1) if (atomic_read(&key->enabled) == 0)
> 	jump_label_update(key, JUMP_LABEL_ENABLE);
> 
> 					 2) if (!atomic_dec_and_mutex_lock(&key->enabled, &jump_label_mutex))
> 					 	return;
> 
> 3) atomic_inc(&key->enabled);
> 
> So now, key->enabled = 0, but the jump has been enabled, which is an invalid
> state.
> 
Isn't it an indication of a higher level bug if jump_label_dec() is
called on a disabled jump label? In other words isn't key->enabled == -1
invalid sate by itself? I do not see how the call sequence above can
happen with perf events for instance. jump_label_dec() is called on
event destruction and if key->enabled = 0 then there is no events to
destroy.

--
			Gleb.

Re: [PATCH] jump label: close race in jump_label_inc() vs. jump_label_dec()

[Steven Rostedt]

On Wed, 2012-01-04 at 10:32 -0500, Jason Baron wrote:
> The previous fix to ensure that jump_label_inc() does not return until the jump
> is completely patched, opened up a race in the inc/dec path. The scenario is:

You forgot something:


> 
> key->enabled = 0;
> 
> 	CPU 0					CPU 1
>         ----- 					-----

  jump_label_lock();

> 
> jump_label_inc():			jump_label_dec():
> 
> 1) if (atomic_read(&key->enabled) == 0)
> 	jump_label_update(key, JUMP_LABEL_ENABLE);
> 
> 					 2) if (!atomic_dec_and_mutex_lock(&key->enabled, &jump_label_mutex))
> 					 	return;
> 
> 3) atomic_inc(&key->enabled);

  jump_label_unlock();



> 
> So now, key->enabled = 0, but the jump has been enabled, which is an invalid
> state.

How does key->enabled end up == 0?

As Gleb said, it's a higher level bug if we do a jump_label_dec() when
key->enabled already is zero.

Thus, in this scenario, we enter jump_label_inc() with key->enabled=1,
and 1) will not be true. When we hit 2), it will have to grab the
jump_label_mutex, which will be held, thus it will block until CPU 0 is
finished, in which case, key->enabled=1 and the
atomic_dec_and_mutex_lock() will fail and return.

The end result is key->enabled=1 and we have jump labels enabled.

What's the invalid state?

-- Steve

Re: [PATCH] jump label: close race in jump_label_inc() vs. jump_label_dec()

[Jason Baron]

On Thu, Jan 05, 2012 at 09:39:56AM -0500, Steven Rostedt wrote:
> On Wed, 2012-01-04 at 10:32 -0500, Jason Baron wrote:
> > The previous fix to ensure that jump_label_inc() does not return until the jump
> > is completely patched, opened up a race in the inc/dec path. The scenario is:
> 
> You forgot something:
> 
> 
> > 
> > key->enabled = 0;
> > 
> > 	CPU 0					CPU 1
> >         ----- 					-----
> 
>   jump_label_lock();
> 
> > 
> > jump_label_inc():			jump_label_dec():
> > 
> > 1) if (atomic_read(&key->enabled) == 0)
> > 	jump_label_update(key, JUMP_LABEL_ENABLE);
> > 
> > 					 2) if (!atomic_dec_and_mutex_lock(&key->enabled, &jump_label_mutex))
> > 					 	return;
> > 
> > 3) atomic_inc(&key->enabled);
> 
>   jump_label_unlock();
> 
> 
> 
> > 
> > So now, key->enabled = 0, but the jump has been enabled, which is an invalid
> > state.
> 
> How does key->enabled end up == 0?
> 
> As Gleb said, it's a higher level bug if we do a jump_label_dec() when
> key->enabled already is zero.
> 

I was worried about exactly that case. Part of my thinking is based on
'static_branch_def_true()' that I am looking to introduce, see:
https://lkml.org/lkml/2011/12/21/359. In that case, key->enabled starts
at 1, and we need to do a jump_label_dec(key), in order to make the
branch false and change the branch from its initial state. So, if we don't allow
negative 'enabled' values, the api doesn't feel symmetrical.

That said, until we have a use-case that would excercise this race,
I'm ok with having it be a higher level bug as Gleb pointed out. So how about a
WARN() for this case. I'll send as a separate patch, if people are ok
with it.

Thanks,

-Jason

--- a/kernel/jump_label.c
+++ b/kernel/jump_label.c
@@ -75,8 +75,11 @@ void jump_label_inc(struct jump_label_key *key)
 static void __jump_label_dec(struct jump_label_key *key,
 		unsigned long rate_limit, struct delayed_work *work)
 {
-	if (!atomic_dec_and_mutex_lock(&key->enabled, &jump_label_mutex))
+	if (!atomic_dec_and_mutex_lock(&key->enabled, &jump_label_mutex)) {
+		WARN(atomic_read(&key->enabled) < 0,
+		     "jump label: negative count!\n");
 		return;
+	}
 
 	if (rate_limit) {
 		atomic_inc(&key->enabled);




> Thus, in this scenario, we enter jump_label_inc() with key->enabled=1,
> and 1) will not be true. When we hit 2), it will have to grab the
> jump_label_mutex, which will be held, thus it will block until CPU 0 is
> finished, in which case, key->enabled=1 and the
> atomic_dec_and_mutex_lock() will fail and return.
> 
> The end result is key->enabled=1 and we have jump labels enabled.
> 
> What's the invalid state?
> 
> -- Steve
> 
> 

Re: [PATCH] jump label: close race in jump_label_inc() vs. jump_label_dec()

[Steven Rostedt]

On Thu, 2012-01-05 at 10:30 -0500, Jason Baron wrote:

> That said, until we have a use-case that would excercise this race,
> I'm ok with having it be a higher level bug as Gleb pointed out. So how about a
> WARN() for this case. I'll send as a separate patch, if people are ok
> with it.

You mean a WARN_ON(key->enabled < 0) ?

for that, yeah I'm fine with it.

-- Steve

Re: [PATCH] jump label: close race in jump_label_inc() vs. jump_label_dec()

[Jason Baron]

On Thu, Jan 05, 2012 at 10:34:24AM -0500, Steven Rostedt wrote:
> On Thu, 2012-01-05 at 10:30 -0500, Jason Baron wrote:
> 
> > That said, until we have a use-case that would excercise this race,
> > I'm ok with having it be a higher level bug as Gleb pointed out. So how about a
> > WARN() for this case. I'll send as a separate patch, if people are ok
> > with it.
> 
> You mean a WARN_ON(key->enabled < 0) ?
> 

yes.

> for that, yeah I'm fine with it.
> 
> -- Steve

Ok, I'll post a patch for that.

Thanks,

-Jason