Spinlocks are one of the simplest and lightweight mutual exclusion mechanisms widely implemented by most concurrent programming environments. A spinlock implementation defines a lock structure and operations that manipulate the lock structure. The lock structure primarily hosts an atomic lock counter among other elements, and operations interfaces include:
- An initializer routine, that initializes a spinlock instance to the default (unlock) state
- A lock routine, that attempts to acquire spinlock by altering the state of the lock counter atomically
- An unlock routine, that releases the spinlock by altering counter into unlock state
When a caller context attempts to acquire spinlock while it is locked (or held by another context), the lock function iteratively polls or spins for the lock until available, causing the caller context to hog the CPU until lock is acquired. It is due to this fact that this exclusion mechanism is aptly named spinlock. It is therefore advised to ensure that code within critical sections is atomic or non-blocking, so that lock can be held for a short, deterministic duration, as it is apparent that holding a spinlock for a long duration could prove disastrous.
As discussed, spinlocks are built around processor-specific atomic operations; the architecture branch of the kernel implements core spinlock operations (assembly programmed). The kernel wraps the architecture-specific implementation through a generic platform-neutral interface that is directly usable by kernel service; this enables portability of the service code which engages spinlocks for protection of shared resources.
Generic spinlock interfaces can be found in the kernel header <linux/spinlock.h> while architecture-specific definitions are part of <asm/spinlock.h>. The generic interface provides a bunch of lock() and unlock() operations, each implemented for a specific use case. We will discuss each of these interfaces in the sections to follow; for now, let's begin our discussion with the standard and most basic variants of lock() and unlock() operations offered by the interface. The following code sample shows the usage of a basic spinlock interface:
DEFINE_SPINLOCK(s_lock);
spin_lock(&s_lock);
/* critical region ... */
spin_unlock(&s_lock);
Let's examine the implementation of these functions under the hood:
static __always_inline void spin_lock(spinlock_t *lock)
{
raw_spin_lock(&lock->rlock);
}
...
...
static __always_inline void spin_unlock(spinlock_t *lock)
{
raw_spin_unlock(&lock->rlock);
}
Kernel code implements two variants of spinlock operations; one suitable for SMP platforms and the other for uniprocessor platforms. Spinlock data structure and operations related to the architecture and type of build (SMP and UP) are defined in various headers of the kernel source tree. Let's familiarize ourselves with the role and importance of these headers:
<include/linux/spinlock.h> contains generic spinlock/rwlock declarations.
The following headers are related to SMP platform builds:
- <asm/spinlock_types.h> contains arch_spinlock_t/arch_rwlock_t and initializers
- <linux/spinlock_types.h> defines the generic type and initializers
- <asm/spinlock.h> contains the arch_spin_*() and similar low-level operation implementations
- <linux/spinlock_api_smp.h> contains the prototypes for the _spin_*() APIs
- <linux/spinlock.h> builds the final spin_*() APIs
The following headers are related to uniprocessor (UP) platform builds:
- <linux/spinlock_type_up.h> contains the generic, simplified UP spinlock type
- <linux/spinlock_types.h> defines the generic type and initializers
- <linux/spinlock_up.h> contains the arch_spin_*() and similar version of UP builds (which are NOPs on non-debug, non-preempt builds)
- <linux/spinlock_api_up.h> builds the _spin_*() APIs
- <linux/spinlock.h> builds the final spin_*() APIs
The generic kernel header <linux/spinlock.h> contains a conditional directive to decide on the appropriate (SMP or UP) API to pull.
/*
* Pull the _spin_*()/_read_*()/_write_*() functions/declarations:
*/
#if defined(CONFIG_SMP) || defined(CONFIG_DEBUG_SPINLOCK)
# include <linux/spinlock_api_smp.h>
#else
# include <linux/spinlock_api_up.h>
#endif
The raw_spin_lock() and raw_spin_unlock() macros dynamically expand to the appropriate version of spinlock operations based on the type of platform (SMP or UP) chosen in the build configuration. For SMP platforms, raw_spin_lock() expands to the __raw_spin_lock() operation implemented in the kernel source file kernel/locking/spinlock.c. Following is the locking operation code defined with a macro:
/*
* We build the __lock_function inlines here. They are too large for
* inlining all over the place, but here is only one user per function
* which embeds them into the calling _lock_function below.
*
* This could be a long-held lock. We both prepare to spin for a long
* time (making _this_ CPU preemptable if possible), and we also signal
* towards that other CPU that it should break the lock ASAP.
*/
#define BUILD_LOCK_OPS(op, locktype)
void __lockfunc __raw_##op##_lock(locktype##_t *lock)
{
for (;;) {
preempt_disable();
if (likely(do_raw_##op##_trylock(lock)))
break;
preempt_enable();
if (!(lock)->break_lock)
(lock)->break_lock = 1;
while (!raw_##op##_can_lock(lock) && (lock)->break_lock)
arch_##op##_relax(&lock->raw_lock);
}
(lock)->break_lock = 0;
}
This routine is composed of nested loop constructs, an outer for loop construct, and an inner while loop that spins until the specified condition is satisfied. The first block of code in the outer loop attempts to acquire lock atomically by invoking the architecture-specific ##_trylock() routine. Notice that this function is invoked with kernel preemption disabled on the local processor. If lock is acquired successfully, it breaks out of the loop construct and the call returns with preemption turned off. This ensures that the caller context holding the lock is not preemptable during execution of a critical section. This approach also ensures that no other context can contend for the same lock on the local CPU until the current owner releases it.
However, if it fails to acquire lock, preemption is enabled through the preempt_enable() call, and the caller context enters the inner loop. This loop is implemented through a conditional while that spins until lock is found to be available. Each iteration of the loop checks for lock, and when it detects that the lock is not available yet, it invokes an architecture-specific relax routine (which executes a CPU-specific nop instruction) before spinning again to check for lock. Recall that during this time preemption is enabled; this ensures that the caller context is preemptable and does not hog CPU for long duration, which can happen especially when lock is highly contended. It also allows the possibility of two or more threads scheduled on the same CPU to contend for the same lock, possibly by preempting each other.
When a spinning context detects that lock is available through raw_spin_can_lock(), it breaks out of the while loop, causing the caller to iterate back to the beginning of the outer loop (for loop) where it again attempts to grab lock through ##_trylock() by disabling preemption:
/*
* In the UP-nondebug case there's no real locking going on, so the
* only thing we have to do is to keep the preempt counts and irq
* flags straight, to suppress compiler warnings of unused lock
* variables, and to add the proper checker annotations:
*/
#define ___LOCK(lock)
do { __acquire(lock); (void)(lock); } while (0)
#define __LOCK(lock)
do { preempt_disable(); ___LOCK(lock); } while (0)
#define _raw_spin_lock(lock) __LOCK(lock)
Unlike the SMP variant, spinlock implementation for UP platforms is quite simple; in fact, the lock routine just disables kernel preemption and puts the caller into a critical section. This works since there is no possibility of another context to contend for the lock with preemption suspended.