Jörn Engel (joern.delete@this.purestorage.com) on January 4, 2020 11:34 am wrote:
>
> What are your thoughts about limiting unfairness.

Almost all serious locking libraries try to do something exactly like that.

A lot of locking libraries are not about a single locking model. You often have a opportunistic fast case that you know is unfair, but is very simple and works in 99% of the cases.

So your first-order locking might be literally (very bounded) loop doing a "cmpxchg" loop to try to get the lock. Say that "0" means "unlocked", and "1" means "I got the lock", so you might try to start out with a "trylock" that does just

old = cmpxchg_acquire(lock, 0, 1)

The above may look really stupid, but it actually might be optimal. Part of the "look stupid" is that it doesn't even read the old value before it tries to get the lock, which can actually be good in some situations. If the common case is that it's unlocked - and that often is the common case - you not only didn't do anything extraneous, but you also didn't cause a "read for shared ownership" cache cycle in an SMP environment. The cmpxchg() will have asked for the cacheline to be exclusively owned (unless the cache coherence protocol is garbage - we've seen a lot of bad cache coherence hardware).

Now, in the above trivial trylock case, if "old" was zero, you're done. You got the lock. Good. Go on with your life.

Now, if you didn't get the lock, you might decide that "hey, lots of locks are held only for very short times, and I'll try to wait for a very bounded time". You know that you really should sleep, but maybe the lock holder is running right now on another CPU, and sleeping would be more expensive than waiting a bit, so you do a very bounded loop and say

for (c=0; c < 10 && force_read(lock) == 1; c++) cpu_relax()

and now you're just doing regular reads, because you do not want to have a hundred CPUs all be in a loop at the same time trying to get the lock. The "cpu_relax" is some "let's delay a short while and hopefully put the CPU in a lower-power state too".

Note that "cpu_relax" is not a "sched_yield()". You haven't gotten to the point where you want to do a system call yet, you're way before that point. It's a "CPU core yield" - "rep nop" in x86.

And if you end up seeing that the lock got freed, maybe you try that trylock again. Once. Or maybe even twice. But you really really don't want to do a lot of write-for-ownership cycles, because that scales absolutely horribly in the case where you have a lot of CPUs.

You've now handled the fast-case, and it's not been fair, but it's been simple, and you hopefully haven't done too much damage on the CPU cache coherency, nor have you wasted a lot of time on busy-waiting for the lock to get free'd. And you haven't needed to do any expensive system calls or anything like that.

But now if the above hasn't worked and you didn't get the lock even after re-trying, you're in a quandary. Now you're going to wait for the lock and do system calls and shit, and while you were ok with unfairness for the simple and fast cases, by the time you say "I'm going to wait for it", you are no longer ok with unfairness - you're spending real time on this lock, and you don't want others to steal it from under you, the bastards.

And, btw, you also want to let the other side that currently holds the lock to know that it needs to do something special when it unlocks.

So maybe the next step is doing something like

atomic_add(lock,2)

and we've changed the rules for what the "lock values" mean.

"0" still means "unlocked", and "1" still means "locked", but the other bits now mean "contention count". Not only will that now mean that the next person who unlocks knows to do something about it, but it also means that other people trying the fast-case simple "cmpxchg" will no longer come in and steal the lock from under you.

IOW, you have now entered "I'm seeing contention, and I want fairness" mode.

Now, at this point, you'll need to do some system-specific stuff on how to wait and wake up things. On Linux, you'd be using futexes that basically combine a "do something atomic to this memory location, and wait on or wake up people who are waiting for it". You might have tickets for fairness, you might have additional things going on.

The above is all hand-wavy, but I hope you get the point.

Also, now that I've explained the expanded lock values, I can talk about unlocking. In particular, you also want unlock to be fast. But you need to make sure that unlocking will also wake up any waiters. But waking up waiters can be expensive (you don't want to do a futex call unless it's necessary), so the unlock sequence - like the lock sequence - might want to start off with

old = cmpxchg_release(lock, 1, 0)

that basically says "I know the lock value is supposed to be 1 for the fast case - because I hold the lock and nobody else is waiting - and if I can just turn it to zero, I'm all done".

And if the old value wasn't 1, you need to do the whole "wakey-wakey" dance using the system stuff for that (ie futex or whatever). And in particular, if it was "0", you need to do a big warning saying "somebody unlocked things from under me" so that you can debug the locking bugs you have. But you might want to have a whole lock debugging library that does a whole lot more than that.

And all of the above is basically simplified pseudo-code. There are a lot more complexities in reality, but the above hopefully kind of approaches something working while still having a reasonable fast case. And you can tune things for the load you want.

And if any of the details above are wrong, take it just as another proof of "locking is hard". The above is handwavy garbage, it's a high-level "maybe something kind of like this", and there might actually be a lot of extra steps with different levels of "what to do when the first lock failed", and flags in the lock saying whether you want fairness or not, and tuning on how long you are willing to wait etc etc.

In particular, the contention case really can be pretty interesting, in that that is when you know you have multiple people interested in the lock, and you really want to start thinking about ways to not have everybody suddenly start doing cacheline accesses when the lock eventually is released. You want to do clever queueing so that only one CPU sees the lock got released and do lock-handoff without that CPU having to go through extra cache events etc.

Maybe that's not a problem for you, simply because you know you'll never have seriously overcommitted resources, and you'll want to keep tings simple. Or maybe you have some other "I know my load" that means that you want very particular fast-case locking sequences, or maybe you have specific requirements for the data structures that means that you might use some other approach than the above kind of 0/1/many with a cmpxchg.

So there's a lot of glossing over going on above. And maybe you want a lock that does readers and writers and not just mutual exclusion, which adds yet another set of complexities. Or maybe you want to have recursive locks (so that a person who already owns a lock doesn't block on it if it does it recursively).

There's lots of complexities you can add, and that can make sense.

Linus