RE: [Linux-ia64] Linux kernel deadlock caused by spinlock bug

RE: [Linux-ia64] Linux kernel deadlock caused by spinlock bug

[Van Maren, Kevin]

> On Mon, Jul 29, 2002 at 03:37:17PM -0500, Van Maren, Kevin wrote:
> > I changed the code to allow the writer bit to remain set even if
> > there is a reader.  By only allowing a single processor to set
> > the writer bit, I don't have to worry about pending writers starving
> > out readers.  The potential writer that was able to set the 
> writer bit
> > gains ownership of the lock when the current readers finish.  Since
> > the retry for read_lock does not keep trying to increment the reader
> > count, there are no other required changes.
> 
> however, this is broken.  linux relies on being able to do
> 
> read_lock(x);
> func()
>   -> func()
>        -> func()
>             -> read_lock(x);
> 
> if a writer comes between those two read locks, you're toast.
> 
> i suspect the right answer for the contention you're seeing 
> is an improved
> get_timeofday which is lockless.

Recursive read locks certainly make it more difficult to fix the
problem.  Placing a band-aid on gettimeofday will fix the symptom
in one location, but will not fix the general problem, which is
writer starvation with heavy read lock load.  The only way to fix
that is to make writer locks fair or to eliminate them (make them
_all_ stateless).

Recursive read locks also imply that you can't replace them with
a "normal" spinlock, which would also solve the problem (although
they do _not_ scale under contention -- something like O(N^2)
cache-cache transfers for N processors to acquire once).

There are ways of fixing the writer starvation and allowing recursive
read locks, but that is more work (and heavier-weight than desirable).
How pervasive are recursive reader locks?  Should they be a special
type of reader lock?

Kevin

Re: [Linux-ia64] Linux kernel deadlock caused by spinlock bug

[Matthew Wilcox]

On Mon, Jul 29, 2002 at 04:05:35PM -0500, Van Maren, Kevin wrote:
> Recursive read locks certainly make it more difficult to fix the
> problem.  Placing a band-aid on gettimeofday will fix the symptom
> in one location, but will not fix the general problem, which is
> writer starvation with heavy read lock load.  The only way to fix
> that is to make writer locks fair or to eliminate them (make them
> _all_ stateless).

The basic principle is that if you see contention on a spinlock, you
should eliminate the spinlock somehow.  making spinlocks `fair' doesn't
help that you're spending lots of time spinning on a lock.

-- 
Revolutions do not require corporate support.

Re: [Linux-ia64] Linux kernel deadlock caused by spinlock bug

[Russell Lewis]

IDEA: Implement a read/write "bias" field that can show if a lock has 
been gained many  times in succession for either read or write.  When 
locks of the opposite type are attempting (and failing) to get the lock, 
back off the other users until starvation is relieved.

* You would add an unsigned integer field.  When you gain a read lock, 
you check the field.  If it had previously been positive, then just 
increment it.  If it had previously been negative, set it to 1 
(equivalent to setting to 0 and incrementing).  Likewise, if you gain a 
write lock and it had been negative, you DEcrement it, while if it had 
been positive, you set it to -1.  The general idea here is that the bias 
field gives a non-precise view of how many locks of a given type have 
been assigned in a row.
* When you attempt to grab a lock but fail, you set a bit to indicate 
that your are waiting; there is one bit for waiting reads and another 
for waiting writes.
* Before grabbing either a read or write lock, you check the bits and 
the bias field.  If you are grabbing a read AND the bias is positive AND 
the "write waiting" bit is set, then you do NOPs for min(bias,MAX_NOPS) 
cycles BEFORE you attempt to grab the lock.  Likewise, if you are 
grabbing a write AND the bias is negative AND the "read waiting" bit is 
set, then you do NOPs before attempting the grab the lock.
* When you gain either a read or write lock, you clear the "waiting" 
bit.  If there are other waiters that still remain, they will re-set 
that bit soon.

The general idea here is that if there is any lock that is granting an 
excessive amount of either reads or writes, you give preference to the 
other type of lock.  As soon as one of the "other" type of lock is 
granted, the bias field is reset and the whole process starts over. 
 Since the bias field doesn't have to be precise, you can increment it 
non-atomically.

Thoughts?

Re: [Linux-ia64] Linux kernel deadlock caused by spinlock bug

[Richard B. Johnson]

On Tue, 30 Jul 2002, Russell Lewis wrote:

> IDEA: Implement a read/write "bias" field that can show if a lock has 
> been gained many  times in succession for either read or write.  When 
> locks of the opposite type are attempting (and failing) to get the lock, 
> back off the other users until starvation is relieved.
> 

You need to gain a lock just to read the bias field. You can't read
something that somebody else will change while you are deciding
upon what you read. It just can't work.

If we presume that it did work. What problem are you attempting
to fix?  FYI, there are no known 'lock-hogs'. Unlike a wait on
a semaphore, where a task waiting will sleep (give up the CPU), a
deadlock on a spin-lock isn't possible. A task will eventually
get the resource. Because of the well-known phenomena of "locality",
every possible 'attack' on the spin-lock variable will become
ordered and the code waiting on the locked resource will get
it in a first-come-first-served basis. This, of course, assumes
that the code isn't broken by attempts to change the natural
order.

Cheers,
Dick Johnson
Penguin : Linux version 2.4.18 on an i686 machine (797.90 BogoMips).
The US military has given us many words, FUBAR, SNAFU, now ENRON.
Yes, top management were graduates of West Point and Annapolis.

Re: [Linux-ia64] Linux kernel deadlock caused by spinlock bug

[Russell Lewis]

Richard B. Johnson wrote:

>On Tue, 30 Jul 2002, Russell Lewis wrote:
>
>You need to gain a lock just to read the bias field. You can't read
>something that somebody else will change while you are deciding
>upon what you read. It just can't work.
>
I intentionally made bias a non-precise field.  It really doesn't matter 
if it gets corrupted; it is just a rough idea of what's going on.  So 
there's no problem reading it without a lock.  If the value you read is 
wrong (or partial), then the worst that happends is bunch of NOPs before 
you try for the lock (an undesirable, but not disastrous occurance).

>If we presume that it did work. What problem are you attempting
>to fix?  FYI, there are no known 'lock-hogs'. Unlike a wait on
>a semaphore, where a task waiting will sleep (give up the CPU), a
>deadlock on a spin-lock isn't possible. A task will eventually
>get the resource. Because of the well-known phenomena of "locality",
>every possible 'attack' on the spin-lock variable will become
>ordered and the code waiting on the locked resource will get
>it in a first-come-first-served basis. This, of course, assumes
>that the code isn't broken by attempts to change the natural
>order.
>
Check out the title of the thread...  Somebody has a real, reproducible 
deadlock on a rw_lock where many readers are starving out a writer, and 
the system hangs.

Re: [Linux-ia64] Linux kernel deadlock caused by spinlock bug

[Richard B. Johnson]

On Tue, 30 Jul 2002, Russell Lewis wrote:

> Richard B. Johnson wrote:
> 
> >On Tue, 30 Jul 2002, Russell Lewis wrote:
> >
> >You need to gain a lock just to read the bias field. You can't read
> >something that somebody else will change while you are deciding
> >upon what you read. It just can't work.
> >
> I intentionally made bias a non-precise field.  It really doesn't matter 
> if it gets corrupted; it is just a rough idea of what's going on.  So 
> there's no problem reading it without a lock.  If the value you read is 
> wrong (or partial), then the worst that happends is bunch of NOPs before 
> you try for the lock (an undesirable, but not disastrous occurance).
> 
> >If we presume that it did work. What problem are you attempting
> >to fix?  FYI, there are no known 'lock-hogs'. Unlike a wait on
> >a semaphore, where a task waiting will sleep (give up the CPU), a
> >deadlock on a spin-lock isn't possible. A task will eventually
> >get the resource. Because of the well-known phenomena of "locality",
> >every possible 'attack' on the spin-lock variable will become
> >ordered and the code waiting on the locked resource will get
> >it in a first-come-first-served basis. This, of course, assumes
> >that the code isn't broken by attempts to change the natural
> >order.
> >
> Check out the title of the thread...  Somebody has a real, reproducible 
> deadlock on a rw_lock where many readers are starving out a writer, and 
> the system hangs.
> 

They have, as you say, "real reproducible" deadlocks because they are
not using straight spin-locks. Sombody tried to use cute queued locks.
This invention is the cause of the problem. The solution is to not
try to play tricks on "Mother Nature".


Cheers,
Dick Johnson
Penguin : Linux version 2.4.18 on an i686 machine (797.90 BogoMips).
The US military has given us many words, FUBAR, SNAFU, now ENRON.
Yes, top management were graduates of West Point and Annapolis.

Re: [Linux-ia64] Linux kernel deadlock caused by spinlock bug

[Sean Griffin]

Mr. Lewis' solution fails to address the scenario of recursively
taken read locks.  Since in that case, the thread taking the lock
already holds the lock, running some nops doesn't really give
another thread the possibility of acquiring the write lock.  So
it works out to be the same situation only with a bunch of nops
executed in the critical path.


-Sean Griffin




> On Tue, 30 Jul 2002, Russell Lewis wrote:
> 
> > IDEA: Implement a read/write "bias" field that can show if a lock has 
> > been gained many  times in succession for either read or write.  When 
> > locks of the opposite type are attempting (and failing) to get the lock, 
> > back off the other users until starvation is relieved.
> > 
> 
> You need to gain a lock just to read the bias field. You can't read
> something that somebody else will change while you are deciding
> upon what you read. It just can't work.
> 
> If we presume that it did work. What problem are you attempting
> to fix?  FYI, there are no known 'lock-hogs'. Unlike a wait on
> a semaphore, where a task waiting will sleep (give up the CPU), a
> deadlock on a spin-lock isn't possible. A task will eventually
> get the resource. Because of the well-known phenomena of "locality",
> every possible 'attack' on the spin-lock variable will become
> ordered and the code waiting on the locked resource will get
> it in a first-come-first-served basis. This, of course, assumes
> that the code isn't broken by attempts to change the natural
> order.
> 
> Cheers,
> Dick Johnson
> Penguin : Linux version 2.4.18 on an i686 machine (797.90 BogoMips).
> The US military has given us many words, FUBAR, SNAFU, now ENRON.
> Yes, top management were graduates of West Point and Annapolis.
> 
> 
> _______________________________________________
> Linux-IA64 mailing list
> Linux-IA64@linuxia64.org
> http://lists.linuxia64.org/lists/listinfo/linux-ia64

Re: [Linux-ia64] Linux kernel deadlock caused by spinlock bug

[Russell Lewis]

Sean Griffin wrote:

>
>Mr. Lewis' solution fails to address the scenario of recursively
>taken read locks.  Since in that case, the thread taking the lock
>already holds the lock, running some nops doesn't really give
>another thread the possibility of acquiring the write lock.  So
>it works out to be the same situation only with a bunch of nops
>executed in the critical path.
>
>
>-Sean Griffin
>
Right.  It's not a very good solution, just one of many hacks that might 
work :(

What if we kept a value (in per-CPU or per-thread memory) that was a 
pointer to the last r/w lock we'd gained?  When we release ANY r/w lock, 
we could blindly initialize the "lastLock" pointer back to NULL.  Then 
we have a very quick (i.e. not very good) heuristic for detecting 
recursive locks; if the "lastLock" pointer equals the pointer to the 
thing you're about to try to lock, then you know that you already hold 
it and are about to grab it recursively...otherwise, you fall back to 
other routines.

If you really wanted, you could keep multiple pointers per CPU (exact 
number tunable by a kernel #define), and on release only clear the one 
you are actually releasing.  Most builds, I imagine, wouldn't need more 
than just a single pointer, though.

Re: [Linux-ia64] Linux kernel deadlock caused by spinlock bug

[Van Maren, Kevin]

> > Check out the title of the thread... Somebody has a real, reproducible 
> > deadlock on a rw_lock where many readers are starving out a writer, and 
> > the system hangs. 

> They have, as you say, "real reproducible" deadlocks because they are 
> not using straight spin-locks. Sombody tried to use cute queued locks. 
> This invention is the cause of the problem. The solution is to not 
> try to play tricks on "Mother Nature". 
> Cheers, 
> Dick Johnson 

Not quite.

The stock kernel hangs using regular reader/writer locks.  The problem
where a series of readers can continue passing a pending writer and
prevent the writer from _ever_ acquiring the lock affects at least i386
and ia64, and probably others, for both 2.4.x AND 2.5.x.

The problem would be fixed (but run very slow) by using normal spinlocks,
EXCEPT for the problem that reader locks are acquired recursivly, which
is the same reason my writer-preference patch could deadlock.

So we have the situation where the current code can deadlock, and the
only patch submitted can also lead to deadlock under a different situation.

It was suggested that a modified lock queue would be able to avoid
the eternal starvation problem, and it was also suggested that having
readers "spin" before acquiring the lock could reduce the problem.

Kevin

Re: [Linux-ia64] Linux kernel deadlock caused by spinlock bug

[William Lee Irwin III]

On Tue, Jul 30, 2002 at 12:06:54PM -0500, Van Maren, Kevin wrote:
> It isn't obvious to me how to extend those queued to reader/writer
> locks if you have to allow recursive readers without incurring the
> same overhead of tracking which processors already have a reader lock.
> If you do want to trigger recursive rw_locks, simply change the header
> file to make them normal spinlocks.  Then whenever the kernel hangs,
> see where it is. Of course, this approach only finds all of them if
> you execute every code path.
> Does anyone want to chip in on why we need recursive r/w locks?  Or why it
> is hard to remove them?  It doesn't sound like they are used much.

The tasklist_lock is taken in interrupt context by sigio generation,
and read_locks on it are permitted to be interrupted by other read_locks,
where write_locks of it must mask interrupts locally to prevent deadlock.
I think IA64 performance monitor code does it in interrupt context too.

Older (2.4.x and 2.5.x-early) took the tasklist_lock in interrupt
context to compute the load average by traversing the list of all tasks.
My concern when I changed that was largely timeslice overrun.


Cheers,
Bill

RE: [Linux-ia64] Linux kernel deadlock caused by spinlock bug

[Van Maren, Kevin]

> > There are ways of fixing the writer starvation and allowing recursive
> > read locks, but that is more work (and heavier-weight than desirable).
> 
> One such way would be a variant of queued locks, like John Stultz's
>
http://oss.software.ibm.com/developer/opensource/linux/patches/?patch_id=218
> These are usually needed for fairness even with plain spinlocks on NUMA 
> boxes in any case (so if your box is NUMA then you will need it anyways) 
> They only exist for plain  spinlocks yet, but I guess they could be
extended 
> to readlocks.

This ES7000 system is not NUMA.  All memory is equidistant from all
processors,
with a full non-blocking crossbar interconnect, and the hardware guarantees
fairness under cacheline contention.  So the processors aren't being starved
or treated unfairly by the hardware, just by the reader-preference locking
code.

It isn't obvious to me how to extend those queued to reader/writer locks if
you
have to allow recursive readers without incurring the same overhead of
tracking
which processors already have a reader lock.

If you do want to trigger recursive rw_locks, simply change the header file
to
make them normal spinlocks.  Then whenever the kernel hangs, see where it
is.
Of course, this approach only finds all of them if you execute every code
path.

Does anyone want to chip in on why we need recursive r/w locks?  Or why it
is hard to remove them?  It doesn't sound like they are used much.

Kevin

Re: [Linux-ia64] Linux kernel deadlock caused by spinlock bug

[William Lee Irwin III]

On Tue, Jul 30, 2002 at 03:32:08PM +0200, Andi Kleen wrote:
> One such way would be a variant of queued locks, like John Stultz's
> http://oss.software.ibm.com/developer/opensource/linux/patches/?patch_id=218
> These are usually needed for fairness even with plain spinlocks on NUMA 
> boxes in any case (so if your box is NUMA then you will need it anyways) 
> They only exist for plain  spinlocks yet, but I guess they could be extended 
> to readlocks. 

I should point out plenty of stock PC hardware gets NUMA effects.
For some reason there's not much documentation and/or publicity about
it, though. I wonder why... (don't answer, I know why and know I'm fscked)


Cheers,
Bill

Re: [Linux-ia64] Linux kernel deadlock caused by spinlock bug

[Andi Kleen]

"Van Maren, Kevin" <kevin.vanmaren@unisys.com> writes:

> There are ways of fixing the writer starvation and allowing recursive
> read locks, but that is more work (and heavier-weight than desirable).

One such way would be a variant of queued locks, like John Stultz's
http://oss.software.ibm.com/developer/opensource/linux/patches/?patch_id=218
These are usually needed for fairness even with plain spinlocks on NUMA 
boxes in any case (so if your box is NUMA then you will need it anyways) 
They only exist for plain  spinlocks yet, but I guess they could be extended 
to readlocks. 

IIRC the benchmarks correctly they were about 3 times slower for the
uncontended case, but somewhat faster for contended locks. Of course
this is the wrong priority for linux - contended locks should be eliminated,
not optimized, but if there is no other choice for correctness it has to do.

> How pervasive are recursive reader locks?  Should they be a special
> type of reader lock?

Not very common I hope, at least I cannot think of a case right now
(but then I don't claim to know all locks in linux) 
Verifying that this case does not occur by code audit (or that
you have catched all instances if you made it a special case) would 
be a lot of work:  the 2.5.29 kernel has about 800 calls to read/write_lock

-Andi

RE: [Linux-ia64] Linux kernel deadlock caused by spinlock bug

[David Mosberger]

>>>>> On Mon, 29 Jul 2002 16:29:09 -0500, "Van Maren, Kevin" <kevin.vanmaren@unisys.com> said:

  Van> Yes, but that isn't the point: unless you eliminate all rw
  Van> locks, it is conceptually possible to cause a kernel deadlock
  Van> by forcing contention on the locks you didn't remove, if the
  Van> user can force the kernel to acquire a reader lock and if
  Van> something else needs to acquire the writer lock.  Correctness
  Van> is the issue, not performance.

I agree with Kevin here.  There must be some argument as to why
readers cannot indefinitely lock out a writer.  A probabilistic
argument is fine, but just saying "contention doesn't happen"
certainly isn't good enough.

	--david

RE: [Linux-ia64] Linux kernel deadlock caused by spinlock bug

[Van Maren, Kevin]

> On Mon, Jul 29, 2002 at 04:05:35PM -0500, Van Maren, Kevin wrote:
> > Recursive read locks certainly make it more difficult to fix the
> > problem.  Placing a band-aid on gettimeofday will fix the symptom
> > in one location, but will not fix the general problem, which is
> > writer starvation with heavy read lock load.  The only way to fix
> > that is to make writer locks fair or to eliminate them (make them
> > _all_ stateless).
> 
> The basic principle is that if you see contention on a spinlock, you
> should eliminate the spinlock somehow.  making spinlocks 
> `fair' doesn't
> help that you're spending lots of time spinning on a lock.

Yes, but that isn't the point: unless you eliminate all rw locks,
it is conceptually possible to cause a kernel deadlock by forcing
contention on the locks you didn't remove, if the user can force
the kernel to acquire a reader lock and if something else needs to
acquire the writer lock.  Correctness is the issue, not performance.
You have locks because there _could_ be contention, and locks handle
that contention _correctly_.  If you can eliminate the contention,
you can eliminate the locks, but if there is a chance for contention,
the locks have to remain, _and_ they have to handle contention
_correctly_, which does not occur with the current reader/writer
lock code, which can hang the kernel just as dead as a writer
between recursive reader lock calls with my code.

Kevin

Re: [Linux-ia64] Linux kernel deadlock caused by spinlock bug

[Matthew Wilcox]

On Mon, Jul 29, 2002 at 03:37:17PM -0500, Van Maren, Kevin wrote:
> I changed the code to allow the writer bit to remain set even if
> there is a reader.  By only allowing a single processor to set
> the writer bit, I don't have to worry about pending writers starving
> out readers.  The potential writer that was able to set the writer bit
> gains ownership of the lock when the current readers finish.  Since
> the retry for read_lock does not keep trying to increment the reader
> count, there are no other required changes.

however, this is broken.  linux relies on being able to do

read_lock(x);
func()
  -> func()
       -> func()
            -> read_lock(x);

if a writer comes between those two read locks, you're toast.

i suspect the right answer for the contention you're seeing is an improved
get_timeofday which is lockless.

-- 
Revolutions do not require corporate support.