Re: [PATCH] Upgradeable read locks for USB (was: Re: Kernel locks)

Linus Torvalds (torvalds@transmeta.com)
Sun, 11 Jan 1998 10:32:58 -0800 (PST)


On Sun, 11 Jan 1998, Iñaky Pérez González wrote:
>
> I've found a simpler sollution which does what I need to
> do. It doesn't need to use any special kind of lock, just the normal
> ones. The code goes in, read locks, and then decides it has to
> write. It upgrades the read lock to write lock, writes, releases the
> write lock, and later (when due), releases the read lock.
>
> What it is done is, when requesting the upgrade, wait until
> there's only ONE reader holding the lock; this is our read lock, and
> we can easily set the write bit. Then we can unlock with
> write_unlock(), what will keep the read lock still held.

Right. This is indeed the simple solution, but it's also the incorrect
solution. This solution also clearly demonstrates _why_ you need an
update-lock.

Imagine two separate processes trying to do an update: they both get a
read lock, and you now have two readers. Fine, that's the whole point of
read locks - you can have multiple readers active. The problem happens
when one of them wants to upgrade to a write lock.

Oops. Now one of the processes is waiting for all other readers to go away
before it can get the write lock. But the readers _won't_ go away, because
the other reader _also_ wants to upgrade the read lock to a write lock,
and you now have two processes waiting for each other to go away.
Deadlock.

> I have tested this in software (with a mixture of gdb and
> paper), and it worked fine, BUT NOT ON REAL KERNEL OPERATION. I don't
> own a SMP machine, so it'be nice if people could test it out; I know I
> should provide a sample for an stress test, but know I have to leave
> my house and won't be here for a loong while (quite a month). Perhaps
> tomorrow I'll be able of scratching some.

Note that the thing that makes this extra dangerous is that it _seems_ to
work fine - your kernel will probably run flawlessly for a longish time.

But when you happen to catch the right wave, your machine is dead.

The reason for upgrade locks is exactly so that there can be one _one_
process that can upgrade at any particular time. There may be other
readers at the same time, but none of the other readers may upgrade their
locks, so there is no potential for deadlocks.

Linus