Re: [RFC PATCH] Writer-biased low-latency rwlock v8

Linus Torvalds
2008-08-21T21:17:05Z

On Thu, 21 Aug 2008, Linus Torvalds wrote:
>
> That leaves 30 bits for readers. If you still think you need to "limit the
> number of readers", then you aren't getting it.

Side note: the actual main rwlock thing is designed for a 64-bit word and
the waiters separately as two 32-bit words, so it doesn't really do what I
describe, but that's actually because the whole sleeping thing is _harder_
than a spinning thing, and has races with wakeups etc.

A spinning thing, in contrast, is pretty trivial.

So here's what I think your code should be like:

rdlock:
movl $4,%eax
lock ; xaddl %eax,(%rdi)
testl $3,%eax
jne __rdlock_slowpath
ret

rwlock:
xorl %eax,%eax
movl $1,%edx
lock ; cmpxchgl %edx,(%rdi)
jne __rwlock_slowpath
ret

rdunlock:
lock ; subl $4,(%rdi)
ret

rwunlock:
lock ; andl $~1,(%rdi)
ret

and I'm pretty damn sure that that should be totally sufficient for a
spinning rwlock. The non-spinning one is more complex just because the
unlock paths need to guarantee that something gets woken up, that just
isn't an issue when you do spinlocks.

Now, in the slow-path:
- on the rwlock slowpath side, set bit#1 to make sure that readers get
caught in the slowpath
- then do a *separate* count of how many pending readers and writers
(ie the ones that got caught into the slowpath) you have (one word
each is probably fine), and then the slowpaths can just do the right
thing depending on whether there are pending readers/writers.

See? The main lock needs not worry about number of writers AT ALL, because
it's totally irrelevant. So don't worry about running out of bits. You
won't. Just put those counts somewhere else! The only thing that matters
for the main lock word is whether there are active readers (30 bits), and
whether there is an active writer (there can only ever be one: 1 bit), and
whether new readers should be trapped (1 bit).

If you worry about overflows, you're doing something wrong.

Linus