Re: [RFC PATCH] Fair rwlock

Linus Torvalds
2008-08-16T21:34:17Z

On Sat, 16 Aug 2008, Mathieu Desnoyers wrote:
>
> Tweakable contention behavior seems interesting, but I don't think it
> deals with the fact that on a mainline kernel, when an interrupt handler
> comes in and asks for a read lock, it has to get it on the spot.

Right. Which is exactly why I'd suggest using the extra space for saying
"this CPU is busy-looping waiting for a write lock", and then the
read-lock contention case can say

- ok, there's a pending write lock holder on _my_ CPU, so I need to just
succeed right away despite the fact that there is contention.

In other words, there are a few cases:

- you actually *got* the write lock

interrupts obviously have to be disabled here, because any reader can
simply not get the lock.

- you are waiting to get the write lock.

Mark this CPU as "pending" in the rwlock (by making the extended thing
be a queue, or by simply only ever allowing a single pendign CPU), and
re-enable interrupts while you wait for it. An interrupt that comes in
and wants a read-lock sees that it's pending, so it should then ignore
the contention bit, and only wait for the write bit to go away.

See? This way you only need to actually disable interrupts while holding
literally the lock, not while waiting for it. While still giving priority
to writers (except for the _one_ CPU, where new readers will have to get
through).

So this way you can be fair, and not allow readers to starve a writer. The
only reader that is allowed past a waiting writer is the reader on that
same CPU.

And notice how the fast-path needs no spinlock or anything else - it's
still just a single locked instruction. In comparison, if I read your
example code right, it is absolutely horrid and has an extra spinlock
access for the fair_write_lock case.

Linus