[PATCH] break_lock forever broken

[PATCH] break_lock forever broken

[Hugh Dickins]

lock->break_lock is set when a lock is contended, but cleared only in
cond_resched_lock.  Users of need_lockbreak (journal_commit_transaction,
copy_pte_range, unmap_vmas) don't necessarily use cond_resched_lock on it.

So, if the lock has been contended at some time in the past, break_lock
remains set thereafter, and the fastpath keeps dropping lock unnecessarily.
Hanging the system if you make a change like I did, forever restarting a
loop before making any progress.

Should it be cleared when contending to lock, just the other side of the
cpu_relax loop?  No, that loop is preemptible, we don't want break_lock
set all the while the contender has been preempted.  It should be cleared
when we unlock - any remaining contenders will quickly set it again.

So cond_resched_lock's spin_unlock will clear it, no need for it to do
that; and use need_lockbreak there too, preferring optimizer to #ifdefs.

Or would you prefer the few need_lockbreak users to clear it in advance?
Less overhead, more errorprone.

Signed-off-by: Hugh Dickins <hugh@veritas.com>

--- 2.6.11-bk7/kernel/sched.c	2005-03-11 13:33:09.000000000 +0000
+++ linux/kernel/sched.c	2005-03-11 17:46:50.000000000 +0000
@@ -3753,14 +3753,11 @@ EXPORT_SYMBOL(cond_resched);
  */
 int cond_resched_lock(spinlock_t * lock)
 {
-#if defined(CONFIG_SMP) && defined(CONFIG_PREEMPT)
-	if (lock->break_lock) {
-		lock->break_lock = 0;
+	if (need_lockbreak(lock)) {
 		spin_unlock(lock);
 		cpu_relax();
 		spin_lock(lock);
 	}
-#endif
 	if (need_resched()) {
 		_raw_spin_unlock(lock);
 		preempt_enable_no_resched();
--- 2.6.11-bk7/kernel/spinlock.c	2005-03-02 07:38:52.000000000 +0000
+++ linux/kernel/spinlock.c	2005-03-11 17:46:50.000000000 +0000
@@ -163,6 +163,8 @@ void __lockfunc _write_lock(rwlock_t *lo
 
 EXPORT_SYMBOL(_write_lock);
 
+#define _stop_breaking(lock)
+
 #else /* CONFIG_PREEMPT: */
 
 /*
@@ -250,12 +252,19 @@ BUILD_LOCK_OPS(spin, spinlock);
 BUILD_LOCK_OPS(read, rwlock);
 BUILD_LOCK_OPS(write, rwlock);
 
+#define _stop_breaking(lock)						\
+	do {								\
+		if ((lock)->break_lock)					\
+			(lock)->break_lock = 0;				\
+	} while (0)
+
 #endif /* CONFIG_PREEMPT */
 
 void __lockfunc _spin_unlock(spinlock_t *lock)
 {
 	_raw_spin_unlock(lock);
 	preempt_enable();
+	_stop_breaking(lock);
 }
 EXPORT_SYMBOL(_spin_unlock);
 
@@ -263,6 +272,7 @@ void __lockfunc _write_unlock(rwlock_t *
 {
 	_raw_write_unlock(lock);
 	preempt_enable();
+	_stop_breaking(lock);
 }
 EXPORT_SYMBOL(_write_unlock);
 
@@ -270,6 +280,7 @@ void __lockfunc _read_unlock(rwlock_t *l
 {
 	_raw_read_unlock(lock);
 	preempt_enable();
+	_stop_breaking(lock);
 }
 EXPORT_SYMBOL(_read_unlock);
 
@@ -278,6 +289,7 @@ void __lockfunc _spin_unlock_irqrestore(
 	_raw_spin_unlock(lock);
 	local_irq_restore(flags);
 	preempt_enable();
+	_stop_breaking(lock);
 }
 EXPORT_SYMBOL(_spin_unlock_irqrestore);
 
@@ -286,6 +298,7 @@ void __lockfunc _spin_unlock_irq(spinloc
 	_raw_spin_unlock(lock);
 	local_irq_enable();
 	preempt_enable();
+	_stop_breaking(lock);
 }
 EXPORT_SYMBOL(_spin_unlock_irq);
 
@@ -294,6 +307,7 @@ void __lockfunc _spin_unlock_bh(spinlock
 	_raw_spin_unlock(lock);
 	preempt_enable();
 	local_bh_enable();
+	_stop_breaking(lock);
 }
 EXPORT_SYMBOL(_spin_unlock_bh);
 
@@ -302,6 +316,7 @@ void __lockfunc _read_unlock_irqrestore(
 	_raw_read_unlock(lock);
 	local_irq_restore(flags);
 	preempt_enable();
+	_stop_breaking(lock);
 }
 EXPORT_SYMBOL(_read_unlock_irqrestore);
 
@@ -310,6 +325,7 @@ void __lockfunc _read_unlock_irq(rwlock_
 	_raw_read_unlock(lock);
 	local_irq_enable();
 	preempt_enable();
+	_stop_breaking(lock);
 }
 EXPORT_SYMBOL(_read_unlock_irq);
 
@@ -318,6 +334,7 @@ void __lockfunc _read_unlock_bh(rwlock_t
 	_raw_read_unlock(lock);
 	preempt_enable();
 	local_bh_enable();
+	_stop_breaking(lock);
 }
 EXPORT_SYMBOL(_read_unlock_bh);
 
@@ -326,6 +343,7 @@ void __lockfunc _write_unlock_irqrestore
 	_raw_write_unlock(lock);
 	local_irq_restore(flags);
 	preempt_enable();
+	_stop_breaking(lock);
 }
 EXPORT_SYMBOL(_write_unlock_irqrestore);
 
@@ -334,6 +352,7 @@ void __lockfunc _write_unlock_irq(rwlock
 	_raw_write_unlock(lock);
 	local_irq_enable();
 	preempt_enable();
+	_stop_breaking(lock);
 }
 EXPORT_SYMBOL(_write_unlock_irq);
 
@@ -342,6 +361,7 @@ void __lockfunc _write_unlock_bh(rwlock_
 	_raw_write_unlock(lock);
 	preempt_enable();
 	local_bh_enable();
+	_stop_breaking(lock);
 }
 EXPORT_SYMBOL(_write_unlock_bh);
 

Re: [PATCH] break_lock forever broken

[Andrew Morton]

Hugh Dickins <hugh@veritas.com> wrote:
>
> lock->break_lock is set when a lock is contended, but cleared only in
>  cond_resched_lock.  Users of need_lockbreak (journal_commit_transaction,
>  copy_pte_range, unmap_vmas) don't necessarily use cond_resched_lock on it.
> 
>  So, if the lock has been contended at some time in the past, break_lock
>  remains set thereafter, and the fastpath keeps dropping lock unnecessarily.
>  Hanging the system if you make a change like I did, forever restarting a
>  loop before making any progress.
> 
>  Should it be cleared when contending to lock, just the other side of the
>  cpu_relax loop?  No, that loop is preemptible, we don't want break_lock
>  set all the while the contender has been preempted.  It should be cleared
>  when we unlock - any remaining contenders will quickly set it again.
> 
>  So cond_resched_lock's spin_unlock will clear it, no need for it to do
>  that; and use need_lockbreak there too, preferring optimizer to #ifdefs.
> 
>  Or would you prefer the few need_lockbreak users to clear it in advance?
>  Less overhead, more errorprone.

This patch causes a CONFIG_PREEMPT=y, CONFIG_PREEMPT_BKL=y,
CONFIG_DEBUG_PREEMPT=y kernel on a ppc64 G5 to hang immediately after
displaying the penguins, but apparently not before having set the hardware
clock backwards 101 years.

After having carefully reviewed the above description and having decided
that these effects were not a part of the patch's design intent I have
temporarily set it aside, thanks.

Re: [PATCH] break_lock forever broken

[Hugh Dickins]

On Fri, 11 Mar 2005, Andrew Morton wrote:
> 
> This patch causes a CONFIG_PREEMPT=y, CONFIG_PREEMPT_BKL=y,
> CONFIG_DEBUG_PREEMPT=y kernel on a ppc64 G5 to hang immediately after
> displaying the penguins, but apparently not before having set the hardware
> clock backwards 101 years.
> 
> After having carefully reviewed the above description and having decided
> that these effects were not a part of the patch's design intent I have
> temporarily set it aside, thanks.

That was a Klingon patch, sorry, it escaped.  Hence the time warp.  Did
terrible things on i386 too once I tested it differently.  When dealing
with something like a completion, disaster to touch a field of the lock
once it's been unlocked.  Here's a replacement...


lock->break_lock is set when a lock is contended, but cleared only in
cond_resched_lock.  Users of need_lockbreak (journal_commit_transaction,
copy_pte_range, unmap_vmas) don't necessarily use cond_resched_lock on it.

So, if the lock has been contended at some time in the past, break_lock
remains set thereafter, and the fastpath keeps dropping lock unnecessarily.
Hanging the system if you make a change like I did, forever restarting a
loop before making any progress.  And even users of cond_resched_lock may
well suffer an initial unnecessary lockbreak.

There seems to be no point at which break_lock can be cleared when
unlocking, any point being either too early or too late; but that's okay,
it's only of interest while the lock is held.  So clear it whenever the
lock is acquired - and any waiting contenders will quickly set it again.
Additional locking overhead? well, this is only when CONFIG_PREEMPT is on.

Since cond_resched_lock's spin_lock clears break_lock, no need to clear it
itself; and use need_lockbreak there too, preferring optimizer to #ifdefs.

Signed-off-by: Hugh Dickins <hugh@veritas.com>

--- 2.6.11-bk8/kernel/sched.c	2005-03-11 13:33:09.000000000 +0000
+++ linux/kernel/sched.c	2005-03-11 17:46:50.000000000 +0000
@@ -3753,14 +3753,11 @@ EXPORT_SYMBOL(cond_resched);
  */
 int cond_resched_lock(spinlock_t * lock)
 {
-#if defined(CONFIG_SMP) && defined(CONFIG_PREEMPT)
-	if (lock->break_lock) {
-		lock->break_lock = 0;
+	if (need_lockbreak(lock)) {
 		spin_unlock(lock);
 		cpu_relax();
 		spin_lock(lock);
 	}
-#endif
 	if (need_resched()) {
 		_raw_spin_unlock(lock);
 		preempt_enable_no_resched();
--- 2.6.11-bk8/kernel/spinlock.c	2005-03-02 07:38:52.000000000 +0000
+++ linux/kernel/spinlock.c	2005-03-12 22:52:41.000000000 +0000
@@ -187,6 +187,8 @@ void __lockfunc _##op##_lock(locktype##_
 			cpu_relax();					\
 		preempt_disable();					\
 	}								\
+	if ((lock)->break_lock)						\
+		(lock)->break_lock = 0;					\
 }									\
 									\
 EXPORT_SYMBOL(_##op##_lock);						\
@@ -209,6 +211,8 @@ unsigned long __lockfunc _##op##_lock_ir
 			cpu_relax();					\
 		preempt_disable();					\
 	}								\
+	if ((lock)->break_lock)						\
+		(lock)->break_lock = 0;					\
 	return flags;							\
 }									\
 									\

Re: [PATCH] break_lock forever broken

[Arjan van de Ven]

> 							\
> +	if ((lock)->break_lock)						\
> +		(lock)->break_lock = 0;					\
>  }									\
if it really worth an conditional there? the cacheline of the lock is
made dirty anyway on unlock, so writing an extra 0 is like almost free
(maybe half a cycle) while a conditional jump can be 100+....

Re: [PATCH] break_lock forever broken

[Hugh Dickins]

On Sun, 13 Mar 2005, Arjan van de Ven wrote:
> > 							\
> > +	if ((lock)->break_lock)						\
> > +		(lock)->break_lock = 0;					\
> >  }									\
> if it really worth an conditional there? the cacheline of the lock is
> made dirty anyway on unlock, so writing an extra 0 is like almost free
> (maybe half a cycle) while a conditional jump can be 100+....

I wondered the same, I don't know and would defer to those who do:
really I was just following the style of where break_lock is set above,
which follows soon (unless preempted) after a _raw_whatever_trylock.

Hugh

Re: [PATCH] break_lock forever broken

[Arjan van de Ven]

On Sun, 2005-03-13 at 09:35 +0000, Hugh Dickins wrote:
> On Sun, 13 Mar 2005, Arjan van de Ven wrote:
> > > 							\
> > > +	if ((lock)->break_lock)						\
> > > +		(lock)->break_lock = 0;					\
> > >  }									\
> > if it really worth an conditional there? the cacheline of the lock is
> > made dirty anyway on unlock, so writing an extra 0 is like almost free
> > (maybe half a cycle) while a conditional jump can be 100+....
> 
> I wondered the same, I don't know and would defer to those who do:
> really I was just following the style of where break_lock is set above,
> which follows soon (unless preempted) after a _raw_whatever_trylock.

if the cacheline is dirtied previously it's just free to do the write so
I suggest to remove the conditional...

Re: [PATCH] break_lock forever broken

[Nick Piggin]

On Sat, 2005-03-12 at 23:20 +0000, Hugh Dickins wrote:

> Since cond_resched_lock's spin_lock clears break_lock, no need to clear it
> itself; and use need_lockbreak there too, preferring optimizer to #ifdefs.
> 

FWIW, this patch solves the problems I had in mind (and so should
solve our copy_page_range livelock I hope). I was sort of inclined
to clear break_lock at lock time too.

As Arjan points out, an unconditional set is probably the way to go
if we've already dirtied the cacheline.

> Signed-off-by: Hugh Dickins <hugh@veritas.com>
> 

Thanks for doing the patch Hugh.

Re: [PATCH] break_lock forever broken

[Ingo Molnar]

* Hugh Dickins <hugh@veritas.com> wrote:

> @@ -187,6 +187,8 @@ void __lockfunc _##op##_lock(locktype##_
>  			cpu_relax();					\
>  		preempt_disable();					\
>  	}								\
> +	if ((lock)->break_lock)						\
> +		(lock)->break_lock = 0;					\

while writing the ->break_lock feature i intentionally avoided overhead
in the spinlock fastpath. A better solution for the bug you noticed is
to clear the break_lock flag in places that use need_lock_break()
explicitly.

One robust way for that seems to be to make the need_lock_break() macro
clear the flag if it sees it set, and to make all the other (internal)
users use __need_lock_break() that doesnt clear the flag. I'll cook up a
patch for this.

	Ingo

Re: [PATCH] break_lock forever broken

[Nick Piggin]

Ingo Molnar wrote:
> * Hugh Dickins <hugh@veritas.com> wrote:
> 
> 
>>@@ -187,6 +187,8 @@ void __lockfunc _##op##_lock(locktype##_
>> 			cpu_relax();					\
>> 		preempt_disable();					\
>> 	}								\
>>+	if ((lock)->break_lock)						\
>>+		(lock)->break_lock = 0;					\
> 
> 
> while writing the ->break_lock feature i intentionally avoided overhead
> in the spinlock fastpath. A better solution for the bug you noticed is
> to clear the break_lock flag in places that use need_lock_break()
> explicitly.
> 

What happens if break_lock gets set by random contention on the
lock somewhere (with no need_lock_break or cond_resched_lock)?
Next time it goes through a lockbreak will (may) be a false positive.

I think I'd prefer the additional lock overhead of Hugh's patch if
it gives better behaviour. I think. Any idea what the overhead actually
is?

> One robust way for that seems to be to make the need_lock_break() macro
> clear the flag if it sees it set, and to make all the other (internal)
> users use __need_lock_break() that doesnt clear the flag. I'll cook up a
> patch for this.
> 

If you do this exactly as you describe, then you'll break
cond_resched_lock (eg. for the copy_page_range path), won't you?

Re: [PATCH] break_lock forever broken

[Ingo Molnar]

* Nick Piggin <nickpiggin@yahoo.com.au> wrote:

> > while writing the ->break_lock feature i intentionally avoided
> > overhead in the spinlock fastpath. A better solution for the bug you
> > noticed is to clear the break_lock flag in places that use
> > need_lock_break() explicitly.
> 
> What happens if break_lock gets set by random contention on the lock
> somewhere (with no need_lock_break or cond_resched_lock)? Next time it
> goes through a lockbreak will (may) be a false positive.

yes, and that's harmless. Lock contention is supposed to be a relatively
rare thing (compared to the frequency of uncontended locking), so all
the overhead is concentrated towards the contention case, not towards
the uncontended case. If the flag lingers then it may be a false
positive and the lock will be dropped once, the flag will be cleared,
and the lock will be reacquired. So we've traded a constant amount of
overhead in the fastpath for a somewhat higher, but still constant
amount of overhead in the slowpath.

> >One robust way for that seems to be to make the need_lock_break() macro
> >clear the flag if it sees it set, and to make all the other (internal)
> >users use __need_lock_break() that doesnt clear the flag. I'll cook up a
> >patch for this.
> >
> 
> If you do this exactly as you describe, then you'll break
> cond_resched_lock (eg. for the copy_page_range path), won't you?

(cond_resched_lock() is an 'internal' user that will use
__need_lock_break().)

	Ingo

Re: [PATCH] break_lock forever broken

[Nick Piggin]

Ingo Molnar wrote:
> * Nick Piggin <nickpiggin@yahoo.com.au> wrote:
> 
> 
>>>while writing the ->break_lock feature i intentionally avoided
>>>overhead in the spinlock fastpath. A better solution for the bug you
>>>noticed is to clear the break_lock flag in places that use
>>>need_lock_break() explicitly.
>>
>>What happens if break_lock gets set by random contention on the lock
>>somewhere (with no need_lock_break or cond_resched_lock)? Next time it
>>goes through a lockbreak will (may) be a false positive.
> 
> 
> yes, and that's harmless. Lock contention is supposed to be a relatively
> rare thing (compared to the frequency of uncontended locking), so all
> the overhead is concentrated towards the contention case, not towards
> the uncontended case. If the flag lingers then it may be a false
> positive and the lock will be dropped once, the flag will be cleared,
> and the lock will be reacquired. So we've traded a constant amount of
> overhead in the fastpath for a somewhat higher, but still constant
> amount of overhead in the slowpath.
> 

Yes that's the tradeoff. I just feel that the former may be better,
especially because the latter can be timing dependant (so you may get
things randomly "happening"), and the former is apparently very low
overhead compared with the cost of taking the lock. Any numbers,
anyone?

> 
>>>One robust way for that seems to be to make the need_lock_break() macro
>>>clear the flag if it sees it set, and to make all the other (internal)
>>>users use __need_lock_break() that doesnt clear the flag. I'll cook up a
>>>patch for this.
>>>
>>
>>If you do this exactly as you describe, then you'll break
>>cond_resched_lock (eg. for the copy_page_range path), won't you?
> 
> 
> (cond_resched_lock() is an 'internal' user that will use
> __need_lock_break().)
> 

Off the top of my head, this is what it looks like:

spin_lock(&dst->lock);

spin_lock(&src->lock);
for (lots of stuff) {
	if (need_lock_break(src->lock) || need_lock_break(dst->lock))
		break;
}
spin_unlock(&src->lock);

cond_resched_lock(&dst->lock);

Right? Now currently the src->lock is broken, but your change would break
the cond_resched_lock here, it will not trigger because need_lock_break
clears dst->lock... oh I see, the spinning CPU will set it again. Yuck :(

Re: [PATCH] break_lock forever broken

[Arjan van de Ven]

> 
> Yes that's the tradeoff. I just feel that the former may be better,
> especially because the latter can be timing dependant (so you may get
> things randomly "happening"), and the former is apparently very low
> overhead compared with the cost of taking the lock. Any numbers,
> anyone?

as I said, since the cacheline just got dirtied, the write is just half
a cycle which is so much in the noise that it really doesn't matter.

Re: [PATCH] break_lock forever broken

[Nick Piggin]

Arjan van de Ven wrote:
>>Yes that's the tradeoff. I just feel that the former may be better,
>>especially because the latter can be timing dependant (so you may get
>>things randomly "happening"), and the former is apparently very low
>>overhead compared with the cost of taking the lock. Any numbers,
>>anyone?
> 
> 
> as I said, since the cacheline just got dirtied, the write is just half
> a cycle which is so much in the noise that it really doesn't matter.
> 

Yes, you were the "apparently" that I cited :)

I just wondered if Ingo has or has seen numbers that make
him dislike this way of doing it.

I would have thought that the spinlock structure and code bloat,
and the lock break checks in fast paths would be the far greater
cost of lockbreak than what Hugh's patch adds. But real numbers
are pretty important when it comes to this kind of thing.

Re: [PATCH] break_lock forever broken

[Ingo Molnar]

* Arjan van de Ven <arjan@infradead.org> wrote:

> as I said, since the cacheline just got dirtied, the write is just
> half a cycle which is so much in the noise that it really doesn't
> matter.

ok - the patch below is a small modification of Hugh's so that we clear
->break_lock unconditionally. Since this code is not inlined it ought to
have minimal icache impact too.

	Ingo

--
lock->break_lock is set when a lock is contended, but cleared only in
cond_resched_lock.  Users of need_lockbreak (journal_commit_transaction,
copy_pte_range, unmap_vmas) don't necessarily use cond_resched_lock on it.

So, if the lock has been contended at some time in the past, break_lock
remains set thereafter, and the fastpath keeps dropping lock unnecessarily.
Hanging the system if you make a change like I did, forever restarting a
loop before making any progress.  And even users of cond_resched_lock may
well suffer an initial unnecessary lockbreak.

There seems to be no point at which break_lock can be cleared when
unlocking, any point being either too early or too late; but that's okay,
it's only of interest while the lock is held.  So clear it whenever the
lock is acquired - and any waiting contenders will quickly set it again.
Additional locking overhead? well, this is only when CONFIG_PREEMPT is on.

Since cond_resched_lock's spin_lock clears break_lock, no need to clear it
itself; and use need_lockbreak there too, preferring optimizer to #ifdefs.

Signed-off-by: Hugh Dickins <hugh@veritas.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>

--- 2.6.11-bk8/kernel/sched.c	2005-03-11 13:33:09.000000000 +0000
+++ linux/kernel/sched.c	2005-03-11 17:46:50.000000000 +0000
@@ -3753,14 +3753,11 @@ EXPORT_SYMBOL(cond_resched);
  */
 int cond_resched_lock(spinlock_t * lock)
 {
-#if defined(CONFIG_SMP) && defined(CONFIG_PREEMPT)
-	if (lock->break_lock) {
-		lock->break_lock = 0;
+	if (need_lockbreak(lock)) {
 		spin_unlock(lock);
 		cpu_relax();
 		spin_lock(lock);
 	}
-#endif
 	if (need_resched()) {
 		_raw_spin_unlock(lock);
 		preempt_enable_no_resched();
--- 2.6.11-bk8/kernel/spinlock.c	2005-03-02 07:38:52.000000000 +0000
+++ linux/kernel/spinlock.c	2005-03-12 22:52:41.000000000 +0000
@@ -187,6 +187,7 @@ void __lockfunc _##op##_lock(locktype##_
 			cpu_relax();					\
 		preempt_disable();					\
 	}								\
+	(lock)->break_lock = 0;						\
 }									\
 									\
 EXPORT_SYMBOL(_##op##_lock);						\
@@ -209,6 +211,7 @@ unsigned long __lockfunc _##op##_lock_ir
 			cpu_relax();					\
 		preempt_disable();					\
 	}								\
+	(lock)->break_lock = 0;						\
 	return flags;							\
 }									\
 									\

Re: [PATCH] break_lock forever broken

[Nick Piggin]

Ingo Molnar wrote:
> * Arjan van de Ven <arjan@infradead.org> wrote:
> 
> 
>>as I said, since the cacheline just got dirtied, the write is just
>>half a cycle which is so much in the noise that it really doesn't
>>matter.
> 
> 
> ok - the patch below is a small modification of Hugh's so that we clear
> ->break_lock unconditionally. Since this code is not inlined it ought to
> have minimal icache impact too.
> 

Fine by me.