Had a bit of a look though this, seems pretty OK to me. Obviously with

rwlocks it *is*  impossible to do non-atomic unlocks, so I can't see

a way to significantly improve your code there.
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.
Though that's a pretty tiny "optmisation", and not going to be an amazing

win, even when it does save a state transition on the cacheline...
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?

--

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 
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...
[ message continues ]

Yeah, it is a case of a large slowdown for write for a small speedup

for read (pity the API doesn't have explicit read and write unlocks

-- were they too lazy to type the last bit, or did they expect people

to lose track of whether they had a read or write lock? :P)
Anyway, it's obviously a tradeoff you'd just have to carefully
Well... a single lock is only going to be so scalable. I don't see how

it could be done really significantly better? Maybe a small factor of

improvement if you were to concentrate on the contended case (but you

wouldn't want to do that anyway)
--

My worry is that I did something wrong in the slowpath, and that there is

some thundering-herd-wakeup kind of thing that makes that much slower than

it should be.
The slow path doesn't much matter from the angle of counting individual

cycles, but it still matters very much from a bigger picture. Does it have

bad behavior where we wake up a thousand readers, but then a writer gets

to come in first and all the readers have to go to sleep again?
That's one thing I tried to avoid in the second version (the "Another

approch" commit) where a read-wakeup actually moves the readers from the

pending count to the final count - both to get more fairness (which can be

_bad_ for performance), but also because I think it can avoid pathological

cases (reader starvation and unnecessary futex wakeup).
		Linus

--

yeah, indeed. Compared to all the other costs that have to be dealt with

here, having a second atomic op isnt all that much of an issue either,

especially on latest hw. An atomic op will probably never be as cheap as

a non-atomic op, but ~20 cycles is still plenty fast for most practical

purposes.
	Ingo

--

I think optimised our unlock_page in a way that it can do a

non-atomic unlock in the fastpath (no waiters) using 2 bits. In

practice it was still atomic but only because other page flags

operations could operate on ->flags at the same time.
I still have to get around to submitting the damn thing upstream,

but maybe if I bring it up here, I get the idea more reviewed :)
Anyway, the algorithm goes like this:
lock_page()

{

  if (test_and_set_bit_lock(PG_locked))

    lock_page_slow();

}
lock_page_slow()

{

  /* slowpath */

again:

  prepare_to_wait();

  set_bit(PG_waiters);

  if (test_and_set_bit_lock(PG_locked)) {

    schedule();

    goto again;

  }

}
wake_page_waiters()

{

  /* slowpath */

  clear_bit(PG_waiters);

  smp_mb__after_clear_bit(); /* order clear_bit store with wake_up_page load */

  wake_up_page(PG_locked);

}
unlock_page()

{

  clear_bit_unlock(PG_locked);

  if (unlikely(test_bit(PG_waiters)))

    wake_page_waiters();

}
We don't require any load/store barrier in the unlock_page fastpath

because the bits are in the same word, so cache coherency gives us a

sequential ordering anyway.
Now you notice the lock page slowpath can set bits without holding the

lock, at first glance you'd think the clear_bit to unlock has to be

atomic too then. But actually if we're careful, we can put them in seperate

parts of the word and use the sub-word operations on x86 to avoid the atomic

requirement. I'm not aware of any architecture in which operations to the

same word could be out of order.
Not only does this avoid all barriers (except acquire/release) in the

fastpaths, but it also avoids the unconditional load of the random

hash page waitqueue cacheline on unlock.
Anything applicable to your problem at hand?
--

Yes and no.
Yes, the bits are int he same word, so cache coherency guarantees a lot.
HOWEVER. If you do the sub-word write using a regular store, you are now

invoking the _one_ non-coherent part of the x86 memory pipeline: the store

buffer. Normal stores can (and will) be forwarded to subsequent loads from

the store buffer, and they are not strongly ordered wrt cache coherency

while they are buffered.
IOW, on x86, loads are ordered wrt loads, and stores are ordered wrt other

stores, but loads are *not* ordered wrt other stores in the absense of a

serializing instruction, and it's exactly because of the write buffer.
See above. The above is unsafe, because if you do a regular store to a

partial word, with no serializing instructions between that and a

subsequent load of the whole word, the value of the store can be bypassed

from the store buffer, and the load from the other part of the word can be

carried out _before_ the store has actually gotten that cacheline

exclusively!
So when you do
	movb reg,(byteptr)

	movl (byteptr),reg
you may actually get old data in the upper 24 bits, along with new data in

the lower 8.
I think.
Anyway, be careful. The cacheline itself will always be coherent, but the

store buffer is not going to be part of the coherency rules, and without

serialization (or locked ops), you _are_ going to invoke the store buffer!
		Linus

--

I'd be very surprised if that was the case. But the unlock code needn't

do that anyway. It could do
movb reg,(byteptr)   # clear PG_locked

movb (byteptr+1),reg # load PG_waiters
--

Put another way: the CPU may internally effectively rewrite the two

instructions as
	movb reg,tmpreg		(tmp = writebuffer)

	movl (byteptr),reg	(do the 32-bit read of the old cached contents)

	movb tmpreg,reg		(writebuffer snoop by reads)

	movb tmpreg,(byteptr)	(writebuffer actually drains into cacheline)
and *if* your algorithm is robust wrt these kinds of rewrites, you're ok.

But notice how there are two accesses to the cacheline, and how they are

actually in the "wrong" order, and how the cacheline could have been

updated by another CPU in between.
Does this actually happen? Yeah, I do believe it does. Is it a deathknell

for anybody trying to be clever with overlapping reads/writes? No, you can

still have things like causality rules that guarantee that your algorithm

is perfectly stable in the face of these kinds of reordering. But it *is*

one of the few re-orderings that I think is theoretically archtiecturally

visible.
For example, let's start out with a 32-bit word that contains zero, and

three CPU's. One CPU does
	cmpxchgl 0->0x01010101,mem
another one does
	cmpxchlg 0x01010101->0x02020202,mem
and the third one does that
	movb $0x03,mem

	movl mem,reg
and after it all completed, you may have 0x02020203 in memory, but "reg"

on the third CPU contains 0x01010103.
Note how NO OTHER CPU could _possibly_ have seen that value! That value

never ever existed in any caches. If the final value was 0x02020203, then

both the cmpxchgl's must have worked, so the cache coherency contents

*must* have gone from 0 -> 0x01010101 -> 0x02020202 -> 0x02020203 (with

the movb actually getting the exclusive cache access last).
So the third CPU saw a value for that load that actually *never* existed

in any cache-line: 0x01010103.  Exactly because the x86 memory ordering

allows the store buffer contents to be forwarded within a CPU core.
And this is why atomic locked instructions are special. They bypass the

store buffer (or at least they...
[ message continues ]

I see what you're saying, but I hadn't really considered it before.

Not that I've attempted to do much of these sub-word operations

without consulting you first (which brings us here) ;).
I'd have thought that for a case like this, you'd simply hit the store

alias logic and store forwarding would stall because it doesn't have

the full data.
I'd like to know for sure.
The other thing that could be possible, and I'd imagine maybe more likely

to be implemented in a real CPU because it should give more imrpovement

(and which does break my algorithm) is just that the load to the cacheline

may get to execute first, then if the cacheline gets evicted and

modified by another CPU before our store completes, we effectively see

store/load reordering again.
--

That's _one_ possible implementation. 
Quite frankly, I think it's the less likely one. It's much more likely

that the cache read access and the store buffer probe happen in parallel

(this is a really important hotpath for any CPU, but even more so x86

where there are more of loads and stores that are spills). And then the

store buffer logic would return the data and a bytemask mask (where the

mask would be all zeroes for a miss), and the returned value is just the 
You'd have to ask somebody very knowledgeable inside Intel and AMD, and it

is quite likely that different microarchitectures have different 
Oh, absolutely, the perfect algorithm would actually get the right answer

and notice that the cacheline got evicted, and retried the whole sequence

such that it is coherent. 
But we do know that Intel expressly documents loads and stores to pass

each other and documents the fact that the store buffer is there. So I bet

that this is visible in some micro-architecture, even if it's not

necessarily visible in _all_ of them.
The recent Intel memory ordering whitepaper makes it very clear that loads

can pass earlier stores and in particular that the store buffer allows

intra-processor forwarding to subsequent loads (2.4 in their whitepaper).

It _could_ be just a "for future CPU's", but quite frankly, I'm 100% sure

it isn't. The store->load forwarding is such a critical performance issue

that I can pretty much guarantee that it doesn't always hit the cacheline.
Of course, the partial store forwarding case is not nearly as important,

and stalling is quite a reasonable implementation approach. I just

personally suspect that doing the unconditional byte-masking is actually

_simpler_ to implement than the stall, so..
			Linus

--

Well, it would just be nice to hear a "no we'll never do that", "we
Well I have a simple test case to show loads pass earlier non conflicting

stores in the case that loads do not come from the store buffer (ie.

*inter* processor forwarding).
And store forwarding, by definition means that the load can complete before

the store can possibly be visible to another CPU I'd say. So yes, I'm

sure this does happen too.
--

Well, I should qualify that: it doesn't actually break my algorithm

because you can still implement the unlock without atomic RMWs.

This may require you to have an mfence there, but we can still get

away without atomics (whether that's much cheaper or not, I haven't

measured recently!)

--

Btw, that comment is bogus, ignore it. It comes from an earlier algorithm

I tried that also explained the contention case, but got unnecessarily

complex. Separating out the queuing behaviour from the actual

non-contended behaviour made things much simpler to explain, so I stopped

even bothering with a "both" case.
Too much cut-and-paste, IOW.
		Linus

--

Uli, you're NOT EVEN READING!
Go back and read it, dammit! How many times have I said that you can even

have more than 32 bits of data? 
There's nothing wrong with using 64-bit atomics to update the words. All

I've *ever* questioned is whether you need more than 32 bits for the

FUTEX part.
For example, let's say that you need 4 bits of "state" information (ie

"next woken-up one is a reader"). And yes, you need counts for readers and

writers. Maybe we can make those counts be 30 bits each. 64 bits total

space. But does the FUTEX_OP things actually need to access all 64 bits?
So imagine that you bave a 64-bit atomic op, and bits 0-1 are the reader

state bits, with bits 2-31 being the reader count. Bits 32-33 are the

writer state bits, and bits 34-63 are the writer count.
Now you can use 64-bit atomic ops to update them, but perhaps just use a

32-bit FUTEX op to actually wait as a reader on the low 32 bits that are

the reader state bits. See?
THIS is what I've been trying to tell you. It's quite possible that the

algorithm you already have could work with just moving the bits around so

that each FUTEX op can be done on just one of the words.
And notice my use of the word "possible". 
The kernel uses a 32-bit count word, but has various other state too that

it maintains under a separate locking setup. Same basic idea: the 32-bit

word is "special" (because it's the one that has to have the right format

for the 'xadd' op that we use for the fast path), but it's not the _only_

data in the thing. The other data is also accessed, it's just accessed

according to different principles.
			Linus

--