lkml.org 
[lkml]   [2008]   [Jun]   [5]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH 0/3] 64-bit futexes: Intro


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


\
 
 \ /
  Last update: 2008-06-06 05:41    [W:0.146 / U:0.528 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site