Synchronization primitives in Linux Kernel

Kernel level Concurrency

Modern operating system kernels are inherently concurrent, thus every kernel engineer should be very familiar with kernel level concurrency and the mechanisms to enforce mutual exclusion in OS kernels. Kernel level concurrency comes from:

1. SMP: the same piece of kernel code is running in parallel on multiple processors while sharing all kernel data.
2. Kernel Preemption: even for a uniprocessor system, the Kernel is still concurrent if we allow kernel preemption. Specifically, a process running in kernel space during a system call is allowed to be preempted by another high priority process, which could also call into the kernel and access the same data. Thus, kernel data need to be protected from preemption.
3. Interrupt Handlers: even with non preemptive Kernel in uniprocessor system the interrupt handlers are the source of concurrency. Whenever an interrupt is triggered by hardware, the current kernel control path is preempted by the interrupt handler, unless interrupts delivery are disabled. If the interrupt handler accesses shared data, mutual exclusion has to be enforced.

How to pick the correct synchronization primitive

Linux Kernel implements many different synchronization primitives (spinlock, mutex, semaphore, RCU, ...) and we need to be able to select the most appropriate one to ensure code correctness and effectiveness. I would suggest to use the following guidelines:

1. The shared data (that we want to protect) is accessed from different contexts. The following table https://www.kernel.org/doc/html/latest/kernel-hacking/locking.html#locking-in-the-linux-kernel may help to pick the correct synchronization primitive depending on the contexts.
2. If there are no restrictions (either spinlock or mutex can be used). we need to know how fast the critical session, can it switch the current task and how many simultaneously contending threads could be. If the critical section is fast enough (that is, it's better for waiting thread to be in busy wait loop than execute voluntary context switch) and it can't switch off the current task (put it to sleep) and the number of simultaneously contending threads is small enough, then use spinlock, otherwise use mutex.
3. If the number of "readers" is significantly higher than number of "writers", consider using read/write primitives (more details is here https://www.kernel.org/doc/html/latest/kernel-hacking/locking.html#locking-speed)

Examples:

1. Adding or deleting the element of the shared linked list, from user context (IOCTL implementation) only, may be protected by spinlock.
2. Updating (by calling snprintf function) some global variable, from user context (IOCTL implementation), should be protected by mutex.
3. Updating the shared data structure, from IRQ handler and user context, should be protected by spinlock (with disabled local IRQs)