Skip to contentSkip to conversation

bad BUG_ON in rtmutex.c

RT Applied Steven Rostedt 3 participants 15 messages Apr 18, 2006

lore
Share & tools
lore
#0 lore raw

I believe the following BUG_ON can produce false positives. Not sure if this would be a problem though if the case was true.

Here in rt_adjust_prio_chain line 236 (2.6.16-rt16):

	/*
	 * When deadlock detection is off then we check, if further
	 * priority adjustment is necessary.
	 */
	if (!detect_deadlock && waiter->list_entry.prio == task->prio) {
		BUG_ON(waiter->pi_list_entry.prio != waiter->list_entry.prio);
		goto out_unlock_pi;
	}

This is only protected by the waiter->task->pi_lock.

Here's the race:

We have Process A blocked on some lock L1 (this owner doesn't matter). A owns L2 and L3.

Say process B is blocked on lock L2 and process C is blocked on L3. We can also say that B and C are of lower priority than A.

Process B owns lock L4 and process C owns lock L5.

We have Process D that comes and blocks on lock L4 of higher priority than A.

At the same time we have process E blocking on L5 on another CPU that just happens to be the same priority as D.

Here's a view of this scenario.

L1 <=blocks= A

                 <=owns= L2
                           <=blocks= B <=owns= L4
                                                  <=blocks= D
                 <=owns= L3
                           <=blocks= C <=owns= L5
                                                  <=blocks= E

Remember both D and E are running on two different CPUs with the same priority, but both are higher than A and the priority boosting is in effect.

As D climbs the chain and finally gets to task == A and lock == L1

Then we get to this part of the code:

	/* Requeue the waiter */
	plist_del(&waiter->list_entry, &lock->wait_list);
	waiter->list_entry.prio = task->prio;
	plist_add(&waiter->list_entry, &lock->wait_list);

	/* Release the task */
	spin_unlock_irqrestore(&task->pi_lock, flags);
	put_task_struct(task);

	/* Grab the next task */
	task = rt_mutex_owner(lock);
	spin_lock_irqsave(&task->pi_lock, flags);

Now after we unlock the task->pi_lock, the waiter->list_entry.prio is now equal to the task->prio but waiter->pi_list_entry.prio does not yet equal waiter->pi_list_entry.prio. And at this moment, we only have the L1->wait_lock. And to make matters worst, interrupts can now be on.

Lets say before the above happened, process E was going up its chain, and the above happened just as it reached:

retry:

	/*
	 * Task can not go away as we did a get_task() before !
	 */
	spin_lock_irqsave(&task->pi_lock, flags);

And E blocked on the task->pi_lock (since task == A, and D had the lock).

Now when D releases the pi_lock, E can continue, but it gets to the problem compare:

	if (!detect_deadlock && waiter->list_entry.prio == task->prio) {
		BUG_ON(waiter->pi_list_entry.prio != waiter->list_entry.prio);
		goto out_unlock_pi;
	}

Remember that D had the same prio as E, so when E hits this point, waiter->list_entry will equal task->prio (boosted by D), but when it enters the condition, pi_list_entry.prio hasn't been updated yet by D, so we have a legitimate condition that the BUG_ON test will produce a true result.

So the question now is: is this a real bug?

-- Steve

#1 lore raw

On Mon, 2006-04-17 at 21:48 -0400, Steven Rostedt wrote:
...

Quoted 2 lines

So the question now is: is this a real bug?

It seems like a possible scenario . So if the false BUG_ON() needlessly kills a perfectly running system, then it must be a bug. It's the case of the buggy BUG_ON ;) !

Daniel

#2 lore raw
Quoted 9 lines · Daniel Walker

On Mon, 2006-04-17 at 21:48 -0400, Steven Rostedt wrote:
...

Quoted 2 lines

So the question now is: is this a real bug?

It seems like a possible scenario . So if the false BUG_ON() needlessly kills a perfectly running system, then it must be a bug. It's the case of the buggy BUG_ON ;) !

It was late when I was writing that. I reread my email today, and realize that there's a few confusing statements there. That last one being one :)

I meant to say:

So the question is now: Is that case in BUG_ON a real bug?

The BUG_ON bugging a normal system _is_ a bug.

-- Steve

#3 lore raw
Quoted 7 lines · Steven Rostedt
Quoted 5 lines · Daniel Walker

On Mon, 2006-04-17 at 21:48 -0400, Steven Rostedt wrote:
...

Quoted 2 lines

So the question now is: is this a real bug?

Quoted 7 lines
Quoted 4 lines

It seems like a possible scenario . So if the false BUG_ON() needlessly kills a perfectly running system, then it must be a bug. It's the case of the buggy BUG_ON ;) !

It was late when I was writing that. I reread my email today, and realize that there's a few confusing statements there. That last one being one :)

Yeah , it was a bit confusing .

Quoted 5 lines

I meant to say:

So the question is now: Is that case in BUG_ON a real bug?

The BUG_ON bugging a normal system _is_ a bug.

Something in the code bothered me right around the block you referenced.

Specifically when it drops the pi_lock , then takes it again, then does plist_add to the pi_waiters ( during the "Boost the owner" section in rt_mutex_adjust_prio_chain() ). Since the pi_lock was dropped you could get an priority change which would lead to a bogus value in waiter->pi_list_entry.prio .

I was looking over the code, and it seems like once all the chain adjusting bottoms out you would end up with the correct priorities in the waiter structures .. Cause whatever task made the priority adjustment would just end up resetting the pi_waiters during it's adjustment process. (Seems like there's room for optimization though ..)

Daniel

#4 lore raw
Quoted 9 lines · Daniel Walker

Something in the code bothered me right around the block you referenced.

Specifically when it drops the pi_lock , then takes it again, then does plist_add to the pi_waiters ( during the "Boost the owner" section in rt_mutex_adjust_prio_chain() ). Since the pi_lock was dropped you could get an priority change which would lead to a bogus value in waiter->pi_list_entry.prio .

It's not really bogus. It just wont match the task->prio. The waiter->pi_list_entry.prio is set to waiter->list_entry.prio and that's what you really need to match. But you are right that the prio could have changed. But whoever changed the prio should also be updating the chain, so whoever finishes, should have the chain setup properly.

Quoted 7 lines

I was looking over the code, and it seems like once all the chain adjusting bottoms out you would end up with the correct priorities in the waiter structures .. Cause whatever task made the priority adjustment would just end up resetting the pi_waiters during it's adjustment process. (Seems like there's room for optimization though ..)

I guess I just reiterated above what you are saying here. Not sure if this can be optimized. You're talking about optimizing a case that would seldom happen, but in doing so you stand a great chance of slowing down the normal case.

To keep latencies down, we are letting the PI chain walk be preempted, by releasing locks. It's understood that the chain can then change while walking (big debate about this between Ingo, tglx and Esben). But at the end, we decided on it being better to have latencies down, and just make adjustments when they arise. This also keeps the latencies bounded, since the old way was harder to know the worst case (PI chain creep).

BUT! I need to take another good look at the code, and maybe my previous example of the failed BUG_ON is really a clue that there exists a deeper bug. If the processes D and E from my last example were of different priorities, but still higher than A, could the end result be setting A to the lower of the two? This would be a bug, because then A would not inherit the correct priority!

-- Steve

#5 lore raw
Quoted 6 lines · Steven Rostedt

BUT! I need to take another good look at the code, and maybe my previous example of the failed BUG_ON is really a clue that there exists a deeper bug. If the processes D and E from my last example were of different priorities, but still higher than A, could the end result be setting A to the lower of the two? This would be a bug, because then A would not inherit the correct priority!

OK, this shouldn't be a problem (answering my own question ;).

The setting of the task's prio is done by __rt_mutex_adjust_prio(task) and this sets the task's prio to the highest prio task that is blocked on a lock own by "task", or to "task"s original prio if that is higher.

So nevermind.

-- Steve

#6 lore raw
In reply to Steven Rostedt
Quoted 12 lines · Steven Rostedt
Quoted 7 lines · Daniel Walker

I was looking over the code, and it seems like once all the chain adjusting bottoms out you would end up with the correct priorities in the waiter structures .. Cause whatever task made the priority adjustment would just end up resetting the pi_waiters during it's adjustment process. (Seems like there's room for optimization though ..)

Quoted 4 lines

I guess I just reiterated above what you are saying here. Not sure if this can be optimized. You're talking about optimizing a case that would seldom happen, but in doing so you stand a great chance of slowing down the normal case.

I'm not really working on it, but on a bigger SMP machine it might not be that uncommon .. PI is running on all tasks now isn't it? It seems like a simple check could be at the same point as the BUG_ON() we're talking about .. <speculation> If that BUG_ON() triggers , it means the task is walking the lock chain at the same time as another task on the same chain, so you could make the lower prio chain stop at that point .. no?

Quoted 7 lines

To keep latencies down, we are letting the PI chain walk be preempted, by releasing locks. It's understood that the chain can then change while walking (big debate about this between Ingo, tglx and Esben). But at the end, we decided on it being better to have latencies down, and just make adjustments when they arise. This also keeps the latencies bounded, since the old way was harder to know the worst case (PI chain creep).

I can imagine. Seems like PI is always a point of controversy .

Quoted 6 lines

BUT! I need to take another good look at the code, and maybe my previous example of the failed BUG_ON is really a clue that there exists a deeper bug. If the processes D and E from my last example were of different priorities, but still higher than A, could the end result be setting A to the lower of the two? This would be a bug, because then A would not inherit the correct priority!

Did that BUG_ON ever trigger for you? I don't know how you would end up in that state without at least two chain walkers on different cpu's ..

Daniel

#7 lore raw
Quoted 18 lines · Daniel Walker
Quoted 12 lines · Steven Rostedt
Quoted 7 lines · Daniel Walker

I was looking over the code, and it seems like once all the chain adjusting bottoms out you would end up with the correct priorities in the waiter structures .. Cause whatever task made the priority adjustment would just end up resetting the pi_waiters during it's adjustment process. (Seems like there's room for optimization though ..)

Quoted 4 lines

I guess I just reiterated above what you are saying here. Not sure if this can be optimized. You're talking about optimizing a case that would seldom happen, but in doing so you stand a great chance of slowing down the normal case.

Quoted 7 lines

I'm not really working on it, but on a bigger SMP machine it might not be that uncommon .. PI is running on all tasks now isn't it? It seems like a simple check could be at the same point as the BUG_ON() we're talking about .. <speculation> If that BUG_ON() triggers , it means the task is walking the lock chain at the same time as another task on the same chain, so you could make the lower prio chain stop at that point .. no?

Actually, where that BUG_ON was is the exiting of the chain walk. So it does stop. It's the higher priority task that needs to be continuing the chain walk for that problem to occur. So really, it already does what you suggest :)

Quoted 10 lines
Quoted 8 lines

To keep latencies down, we are letting the PI chain walk be preempted, by releasing locks. It's understood that the chain can then change while walking (big debate about this between Ingo, tglx and Esben). But at the end, we decided on it being better to have latencies down, and just make adjustments when they arise. This also keeps the latencies bounded, since the old way was harder to know the worst case (PI chain creep).

I can imagine. Seems like PI is always a point of controversy .

But, as PI matures, it seems to be more and more acceptable.

Quoted 10 lines
Quoted 7 lines

BUT! I need to take another good look at the code, and maybe my previous example of the failed BUG_ON is really a clue that there exists a deeper bug. If the processes D and E from my last example were of different priorities, but still higher than A, could the end result be setting A to the lower of the two? This would be a bug, because then A would not inherit the correct priority!

Did that BUG_ON ever trigger for you? I don't know how you would end up in that state without at least two chain walkers on different cpu's ..

Yes it did, but I need to clearify. I have a custom kernel that is based on Ingo's -rt patch, and I hit this bug on touching other parts of the PI list. When looking at fixing it, I realized that the BUG_ON condition, was legitimate.

Also, I always test on SMP (then I test on UP) and the chain walkers were on two CPUs.

-- Steve

#8 lore raw
Quoted 5 lines · Steven Rostedt

Actually, where that BUG_ON was is the exiting of the chain walk. So it does stop. It's the higher priority task that needs to be continuing the chain walk for that problem to occur. So really, it already does what you suggest :)

I bet you could test for that condition in some other spots too . Like when it adds to the pi_waiters , you could test if the priorities are out of sync ..

Quoted 9 lines
Quoted 9 lines
Quoted 8 lines

To keep latencies down, we are letting the PI chain walk be preempted, by releasing locks. It's understood that the chain can then change while walking (big debate about this between Ingo, tglx and Esben). But at the end, we decided on it being better to have latencies down, and just make adjustments when they arise. This also keeps the latencies bounded, since the old way was harder to know the worst case (PI chain creep).

Quoted 3 lines
Quoted 1 line

I can imagine. Seems like PI is always a point of controversy .

But, as PI matures, it seems to be more and more acceptable.

I read an article on priority ceiling as another method of doing this.
Priority ceiling doesn't seem better, but at the same time I can't imagine how you'd implement it in Linux, or not in a straight forward way .

Quoted 2 lines

Also, I always test on SMP (then I test on UP) and the chain walkers were on two CPUs.

Yeah, best policy, I've learned ..

Daniel

#9 lore raw
Quoted 6 lines · Daniel Walker
Quoted 1 line

But, as PI matures, it seems to be more and more acceptable.

I read an article on priority ceiling as another method of doing
this. Priority ceiling doesn't seem better, but at the same time I can't imagine how you'd implement it in Linux, or not in a straight forward way .

it's already implemented and can be done in userspace: userspace can do it by doing a sys_setscheduler() call when entering the critical section, and another one when exiting it. (PI is obviously faster because there the futex fastpath can be pure-userspace.)

Ingo

#10 lore raw
In reply to Daniel Walker
Quoted 11 lines · Daniel Walker
Quoted 5 lines · Steven Rostedt

Actually, where that BUG_ON was is the exiting of the chain walk. So it does stop. It's the higher priority task that needs to be continuing the chain walk for that problem to occur. So really, it already does what you suggest :)

I bet you could test for that condition in some other spots too . Like when it adds to the pi_waiters , you could test if the priorities are out of sync ..

You mean the other places in rt_mutex_adjust_prio_chain? It already checks once an iteration, anything more is just over kill.

Quoted 10 lines
Quoted 10 lines
Quoted 10 lines
Quoted 9 lines

To keep latencies down, we are letting the PI chain walk be preempted, by releasing locks. It's understood that the chain can then change while walking (big debate about this between Ingo, tglx and Esben). But at the end, we decided on it being better to have latencies down, and just make adjustments when they arise. This also keeps the latencies bounded, since the old way was harder to know the worst case (PI chain creep).

Quoted 8 lines
Quoted 3 lines
Quoted 1 line

I can imagine. Seems like PI is always a point of controversy .

But, as PI matures, it seems to be more and more acceptable.

I read an article on priority ceiling as another method of doing this.
Priority ceiling doesn't seem better, but at the same time I can't imagine how you'd implement it in Linux, or not in a straight forward way .

Actually, I always thought that running PREEMPT_DESKTOP with soft and hard IRQS as threads was priority ceiling. It's just that all locks have the priority of MAX_RT_PRIO (no preemption allowed). OK, this doesn't apply to mutexes, but it does apply for spin_locks. :)

-- Steve

#11 lore raw
Quoted 10 lines · Steven Rostedt
Quoted 8 lines · Daniel Walker
Quoted 5 lines · Steven Rostedt

Actually, where that BUG_ON was is the exiting of the chain walk. So it does stop. It's the higher priority task that needs to be continuing the chain walk for that problem to occur. So really, it already does what you suggest :)

Quoted 6 lines
Quoted 3 lines

I bet you could test for that condition in some other spots too . Like when it adds to the pi_waiters , you could test if the priorities are out of sync ..

You mean the other places in rt_mutex_adjust_prio_chain? It already checks once an iteration, anything more is just over kill.

Yeah, sounds good .

Quoted 4 lines

Actually, I always thought that running PREEMPT_DESKTOP with soft and hard IRQS as threads was priority ceiling. It's just that all locks have the priority of MAX_RT_PRIO (no preemption allowed). OK, this doesn't apply to mutexes, but it does apply for spin_locks. :)

Interesting way to look at it .

Reminds me of the RT read/write locks, only one read or one writer at a time, so it's really just a mutex ..

Daniel

#12 lore raw
Quoted 11 lines · Daniel Walker
Quoted 5 lines

Actually, I always thought that running PREEMPT_DESKTOP with soft and hard IRQS as threads was priority ceiling. It's just that all locks have the priority of MAX_RT_PRIO (no preemption allowed). OK, this doesn't apply to mutexes, but it does apply for spin_locks. :)

Interesting way to look at it .

Reminds me of the RT read/write locks, only one read or one writer at a time, so it's really just a mutex ..

We'll read/write doesn't work well with PI (or latencies for that matter). But rw_locks have one advantage over normal rt_mutex, and that is they are self recursive. i.e. one rw_lock can be taken over and over again (as read) by the same process, as long as it releases it the same amount of times.

-- Steve

#13 lore raw

PATCH 1/1 Remove false BUG_ON from rtmutex.c

In reply to Steven Rostedt

Ingo,

Here's a patch to remove the BUG_ON in rtmutex.c. I previously showed that the condition in that particular BUG_ON can legitimately be the case.

Once again, if you have processes A, B, C, D, and E holding the following locks in this scenario:

L1 <=blocks= A

               <=owns= L2 <=blocks= B <=owns= L4 <=blocks= D
               <=owns= L3 <=blocks= C <=owns= L5 <=blocks= E

Where the priorities of these tasks are

    B,C < A < D = E

B and C are less than A and A is less than D and E where D and E are equal (actually it probably works when D and E are not equal too).

As D and E climb the chain, there's a very slight race condition that could allow for the condition in the offending BUG_ON to be true.

This patch removes that BUG_ON.

kernel/rtmutex.c +1 -3
Index: linux-2.6.16-rt16/kernel/rtmutex.c
===================================================================
@@ -232,10 +232,8 @@ static int rt_mutex_adjust_prio_chain(ta
 	 * When deadlock detection is off then we check, if further
 	 * priority adjustment is necessary.
 	 */
-	if (!detect_deadlock && waiter->list_entry.prio == task->prio) {
-		BUG_ON(waiter->pi_list_entry.prio != waiter->list_entry.prio);
+	if (!detect_deadlock && waiter->list_entry.prio == task->prio)
 		goto out_unlock_pi;
-	}
 
 	lock = waiter->lock;
 	if (!spin_trylock(&lock->wait_lock)) {
Applied
#14 lore raw

Re: [PATCH -rt] Remove false BUG_ON from rtmutex.c

Quoted 3 lines · Steven Rostedt

Here's a patch to remove the BUG_ON in rtmutex.c. I previously showed that the condition in that particular BUG_ON can legitimately be the case.

thanks, applied.

Ingo