Introduction to spinlocks
Introduction
This part opens a new chapter in the linux-insides book. Timers and time management related stuff was described in the previous chapter. Now it's time to move on to the next topic. As you probably recognized from the title, this chapter will describe the synchronization primitives in the Linux kernel.
As always, we will try to know what a synchronization primitive
in general is before we deal with any synchronization-related issues. Actually, a synchronization primitive is a software mechanism, that ensures that two or more parallel processes or threads are not running simultaneously on the same code segment. For example, let's look at the following piece of code:
from the kernel/time/clocksource.c source code file. This code is from the __clocksource_register_scale
function which adds the given clocksource to the clock sources list. This function produces different operations on a list with registered clock sources. For example, the clocksource_enqueue
function adds the given clock source to the list with registered clocksources - clocksource_list
. Note that these lines of code wrapped to two functions: mutex_lock
and mutex_unlock
which takes one parameter - the clocksource_mutex
in our case.
These functions represent locking and unlocking based on mutex synchronization primitive. As mutex_lock
will be executed, it allows us to prevent the situation when two or more threads will execute this code while the mutex_unlock
will not be executed by process-owner of the mutex. In other words, we prevent parallel operations on a clocksource_list
. Why do we need mutex
here? What if two parallel processes will try to register a clock source. As we already know, the clocksource_enqueue
function adds the given clock source to the clocksource_list
list right after a clock source in the list which has the biggest rating (a registered clock source which has the highest frequency in the system):
If two parallel processes will try to do it simultaneously, both process may found the same entry
may occur race condition or in other words, the second process which will execute list_add
, will overwrite a clock source from the first thread.
Besides this simple example, synchronization primitives are ubiquitous in the Linux kernel. If we will go through the previous chapter or other chapters again or if we will look at the Linux kernel source code in general, we will meet many places like this. We will not consider how mutex
is implemented in the Linux kernel. Actually, the Linux kernel provides a set of different synchronization primitives like:
mutex
;semaphores
;seqlocks
;atomic operations
;etc.
We will start this chapter from the spinlock
.
Spinlocks in the Linux kernel.
The spinlock
is a low-level synchronization mechanism which in simple words, represents a variable which can be in two states:
acquired
;released
.
Each process which wants to acquire a spinlock
, must write a value which represents spinlock acquired
state to this variable and write spinlock released
state to the variable. If a process tries to execute code which is protected by a spinlock
, it will be locked while a process which holds this lock will release it. In this case all related operations must be atomic to prevent race conditions state. The spinlock
is represented by the spinlock_t
type in the Linux kernel. If we will look at the Linux kernel code, we will see that this type is widely used. The spinlock_t
is defined as:
and located in the include/linux/spinlock_types.h header file. We may see that its implementation depends on the state of the CONFIG_DEBUG_LOCK_ALLOC
kernel configuration option. We will skip this now, because all debugging related stuff will be in the end of this part. So, if the CONFIG_DEBUG_LOCK_ALLOC
kernel configuration option is disabled, the spinlock_t
contains union with one field which is - raw_spinlock
:
The raw_spinlock
structure defined in the same header file represents the implementation of normal
spinlock. Let's look how the raw_spinlock
structure is defined:
where the arch_spinlock_t
represents architecture-specific spinlock
implementation. As we mentioned above, we will skip debugging kernel configuration options. As we focus on x86_64 architecture in this book, the arch_spinlock_t
that we will consider is defined in the include/asm-generic/qspinlock_types.h header file and looks:
We will not stop on this structures for now. Let's look at the operations on a spinlock
. The Linux kernel provides following main operations on a spinlock
:
spin_lock_init
- produces initialization of the givenspinlock
;spin_lock
- acquires givenspinlock
;spin_lock_bh
- disables software interrupts and acquire givenspinlock
;spin_lock_irqsave
andspin_lock_irq
- disable interrupts on local processor, preserve/not preserve previous interrupt state in theflags
and acquire givenspinlock
;spin_unlock
- releases givenspinlock
;spin_unlock_bh
- releases givenspinlock
and enables software interrupts;spin_is_locked
- returns the state of the givenspinlock
;and etc.
Let's look on the implementation of the spin_lock_init
macro. As I already wrote, this and other macro are defined in the include/linux/spinlock.h header file and the spin_lock_init
macro looks:
As we may see, the spin_lock_init
macro takes a spinlock
and executes two operations: check the given spinlock
and execute the raw_spin_lock_init
. The implementation of the spinlock_check
is pretty easy, this function just returns the raw_spinlock_t
of the given spinlock
to be sure that we got exactly normal
raw spinlock:
The raw_spin_lock_init
macro:
assigns the value of the __RAW_SPIN_LOCK_UNLOCKED
with the given spinlock
to the given raw_spinlock_t
. As we may understand from the name of the __RAW_SPIN_LOCK_UNLOCKED
macro, this macro does initialization of the given spinlock
and set it to released
state. This macro is defined in the include/linux/spinlock_types.h header file and expands to the following macros:
As I already wrote above, we will not consider stuff which is related to debugging of synchronization primitives. In this case we will not consider the SPIN_DEBUG_INIT
and the SPIN_DEP_MAP_INIT
macros. So the __RAW_SPINLOCK_UNLOCKED
macro will be expanded to the:
where the __ARCH_SPIN_LOCK_UNLOCKED
is:
for the x86_64 architecture. So, after the expansion of the spin_lock_init
macro, a given spinlock
will be initialized and its state will be - unlocked
.
From this moment we know how to initialize a spinlock
, now let's consider API which Linux kernel provides for manipulations of spinlocks
. The first is:
function which allows us to acquire
a spinlock
. The raw_spin_lock
macro is defined in the same header file and expands to the call of _raw_spin_lock
:
Where _raw_spin_lock
is defined depends on whether CONFIG_SMP
option is set and CONFIG_INLINE_SPIN_LOCK
option is set. If the SMP is disabled, _raw_spin_lock
is defined in the include/linux/spinlock_api_up.h header file as a macro and looks like:
If the SMP is enabled and CONFIG_INLINE_SPIN_LOCK
is set, it is defined in include/linux/spinlock_api_smp.h header file as the following:
If the SMP is enabled and CONFIG_INLINE_SPIN_LOCK
is not set, it is defined in kernel/locking/spinlock.c source code file as the following:
Here we will consider the latter form of _raw_spin_lock
. The __raw_spin_lock
function looks:
As you may see, first of all we disable preemption by the call of the preempt_disable
macro from the include/linux/preempt.h (more about this you may read in the ninth part of the Linux kernel initialization process chapter). When we unlock the given spinlock
, preemption will be enabled again:
We need to do this to prevent the process from other processes to preempt it while it is spinning on a lock. The spin_acquire
macro which through a chain of other macros expands to the call of the:
The lock_acquire
function:
As I wrote above, we will not consider stuff here which is related to debugging or tracing. The main point of the lock_acquire
function is to disable hardware interrupts by the call of the raw_local_irq_save
macro, because the given spinlock might be acquired with enabled hardware interrupts. In this way the process will not be preempted. Note that in the end of the lock_acquire
function we will enable hardware interrupts again with the help of the raw_local_irq_restore
macro. As you already may guess, the main work will be in the __lock_acquire
function which is defined in the kernel/locking/lockdep.c source code file.
The __lock_acquire
function looks big. We will try to understand what this function does, but not in this part. Actually this function is mostly related to the Linux kernel lock validator and it is not topic of this part. If we will return to the definition of the __raw_spin_lock
function, we will see that it contains the following definition in the end:
The LOCK_CONTENDED
macro is defined in the include/linux/lockdep.h header file and just calls the given function with the given spinlock
:
In our case, the lock
is do_raw_spin_lock
function from the include/linux/spinlock.h header file and the _lock
is the given raw_spinlock_t
:
The __acquire
here is just Sparse related macro and we are not interested in it in this moment. The arch_spin_lock
macro is defined in the include/asm-generic/qspinlock.h header file as the following:
We stop here for this part. In the next part, we'll dive into how queued spinlocks works and related concepts.
Conclusion
This concludes the first part covering synchronization primitives in the Linux kernel. In this part, we met first synchronization primitive spinlock
provided by the Linux kernel. In the next part we will continue to dive into this interesting theme and will see other synchronization
related stuff.
If you have questions or suggestions, feel free to ping me in twitter 0xAX, drop me email or just create issue.
Please note that English is not my first language and I am really sorry for any inconvenience. If you found any mistakes please send me PR to linux-insides.
Links
Last updated