MCS locks in Linux kernel

This lock added in kernel from kernel version 3.15 and 3.18. It is fair version of spinlock where each CPU tries to acquire the lock spinning on local variable.

MCS lock is defined as

struct mcs_spinlock {

         struct mcs_spinlock *next;

         int locked; /* 1 if lock acquired */

    };

To acquire lock:-

void mcs_spin_lock(struct mcs_spinlock **global_queue, struct mcs_spinlock *node);

Arg1: global queue one for each type of spinlock.

Arg2: This is defined per CPU of same type as Arg1 , will be added in queue.

This function tries to acquire spinlock by performing "unconditional" atomic exchange operation to store its own spinlock struct address in next field of global spinlock struct (main lock).

global spinlock struct's next points tail of queue of the waiting CPUs.

global spinlock struct's next points to null if no one is holder, its previous

value (null) in this case.

If global spinlock struct's next is not null it means it is already acquired.

it points to last member in queue, so CPU will save its own struct address in that member's next as well. Now it will spin on local variable (locked) till its not zero.

To release lock:

void mcs_spin_unlock(struct mcs_spinlock **global, struct mcs_spinlock *node)

When thread (CPU) finishes with the lock, it will do a compare-and-swap operation on the main lock (global), trying to set the next pointer to NULL on the assumption that this pointer still points to its own structure.

If that operation succeeds, the lock was never contended and the job is done.

If some other CPU has changed by some other thread (CPU), the compare-and-swap will fail. In that case, thread will not change the main lock at all;

instead, it will change the locked value to "0" in lock structure pointed by its next filed.

MCS lock v/s Spinlock

• MCS lock maintains FIFO order while acquiring lock, spinlock does not maintain FIFO order of acquiring lock. So whoever comes first to acquire the lock will get first.
• In spinlock every process waits on single variable, MCS lock reduces waiting order from n to 1 by maintaining per CPU local variable and spin on it.
• Every attempt to acquire a spinlock requires moving the cache line containing that lock to the local CPU, hence lot of cache bouncing happens, this issue is avoided in MCS lock.

References:

http://lwn.net/Articles/590243/

Defined in linux/3.18.1/kernel/locking/mcs_spinlock.h