Re: [PATCH 0/3] 64-bit futexes: Intro

[Linus Torvalds <torvalds@linux-foundation.org>]

On Fri, 6 Jun 2008, Nick Piggin wrote:
> 
> What you *could* maybe do, to slightly speed up the reader fastpath, at
> the expense of the writer fastpath, is to also have the active writer add
> 4 to the count too, so your unlock can start with a lock xadd -4, count
> in order to get the write-intent on the cacheline straight up.

Yes, nice idea. It avoids the possible unnecessary S->M transition, but 
the downside is that it effectively slows down the write unlock by making 
it do two atomic ops even for the fastpath. So if I were to _only_ care 
about the reader path, I think it would be a great idea, but as it is, the 
current non-contended write case is actually pretty close to optimal, and 
doing the unconditional xaddl on the unlock path would slow that one down.

> I'd be more interested to know why this code can't be evolved into a full
> rwlock implementation? This is a rather standard (though neat) looking rwlock
> -- so my question is what can the patented 64-bit futex locks do that this
> can't, or what can they do faster?

Quite frankly - and this was my argument the whole time - I do not believe 
that a "full" 64-bit implementation can do _anything_ more than this 
32-bit one can do.  That's the reason I wrote the code. I'm pretty sure 
that you can do perfectly well with just 32 bit atomic futex ops (my 
rwlocks obviously do use 64-bit cmpxchg's in user space, but not in the 
fast-path, and it should work fine on x86-32 too using cmpxchg8b).

In fact, in the second version of my locks, I didn't do futex operations 
on the actual lock itself at *all*, and just do futex ops on separate 
"event" fields. That actually should have avoided a bug I think I had (but 
couldn't really trigger in practice) in the first version, and made 
everything look pretty straightforward.

I haven't really worked on them since I write the thing, but I did 
consider things like timeouts etc. Timeouts are "hard" to handle because 
they mean that you cannot use any kind of trivially incrementing "ticket 
locks" with sequence numbers (because we may have to just avoid a sequence 
if it times out), so the sequence number approach that we now use for 
kernel spinlocks was not an option. I didn't actually *write* the timeout 
versions, of course, but given the structure of the locks they really 
should be very straightforward.

[ Half-way subtle thing: a writer that times out needs to be very careful 
  that it doesn't lose a wakeup event, but futexes actually make that part 
  pretty easy - since FUTEX_WAIT returns whether you got woken up or not, 
  you can just decide to wake up the next write-waiter if you cannot get 
  the lock immediately and have to exit due to a timeout. ]

But I really haven't tested my rwlocks very exhaustively, and I did not 
verify that they actualyl scale with lots of CPU's, for example.  I 
literally only have dual-core CPU's in use at home, right now, nothing 
fancier. Somebody with dual-socket quads would be a lot better off, and 
the more the merrier, of course.

But correctness is even more important, and that can at least be somewhat 
"thought" about.

		Linus