Shulou(Shulou.com)06/01 Report--

This article is to share with you about how the spin lock Spinlock in Linux deadlocks Ubuntu. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Background

Because of the limitation of some resources in the multiprocessor environment, sometimes exclusive access (mutual exclusion) is needed, so it is necessary to introduce the concept of lock. Only the task that has acquired the lock can access the resource. Because the core of multithreading is the time slicing of CPU, only one task can acquire the lock at a time.

When there is a conflict between accessing resources in the kernel, there are usually two ways to handle it:

One is to wait in place.

One is to suspend the current process and schedule the execution of other processes (sleep)

Spin lock

Spinlock is a common locking mechanism provided in the kernel, and spin locking solves resource conflicts by "waiting in place". That is, after one thread acquires a spin lock, the other thread expects to acquire the spin lock, but can only "spin" in place (busy waiting).

Because of the busy waiting nature of the spin lock, it is destined to use the limitation in the scenario-the spin lock should not be held for a long time (consuming CPU resources).

Advantages of spin lock

Spin lock will not make the thread state switch, always in the user mode, that is, the thread has always been active; will not make the thread into the blocking state, reducing unnecessary context switching, and the execution speed is fast.

The non-spin lock will enter the blocking state when the lock is not acquired, thus entering the kernel state. when the lock is acquired, it needs to be restored from the kernel state and thread context switching is needed. After the thread is blocked, it enters the kernel (Linux) scheduling state, which causes the system to switch back and forth between the user state and the kernel state, seriously affecting the performance of the lock.

Use of spin lock

In the implementation of linux kernel, we often encounter such a scenario: shared data is accessed by interrupt context and process context, how to protect it?

If you only have access to the process context, you can consider using the locking mechanism of semaphore or mutex, but now that the interrupt context is also involved, the lock that can cause sleep can not be used, so you can consider using spin lock.

Sleep is not allowed in the interrupt context, so what is needed here is a lock that does not cause sleep-spinlock.

In other words, the interrupt context should be locked, and spinlock is preferred.

With a spin lock, there are two ways to define a lock:

Dynamic:

Spinlock_t lock; spin_lock_init & lock)

Static:

DEFINE_SPINLOCK (lock)

Use steps

The use of spinlock is simple:

To access critical resources, we need to first apply for a spin lock.

Spin if you can't get the lock, and enter the critical zone if you can get the lock.

When the spin lock is released, the spin lock can be obtained in the task of the lock and enter the critical area, and the task of exiting the critical area must release the spin lock.

Use an example

Static spinlock_t lock; static int flage = 1; spin_lock_init (& lock); static int hello_open (struct inode * inode, struct file * filep) {spin_lock (& lock); if (flage! = 1) {spin_unlock (& lock); return-EBUSY;} flage = 0; spin_unlock (& lock); return 0 } static int hello_release (struct inode * inode, struct file * filep) {flage = 1; return 0;}

Supplement

The reason why the interrupt context cannot sleep is:

1. Process switching should not occur during interrupt processing, because in the interrupt context, the only interrupt that can interrupt the current interrupt handler is the higher priority interrupt, which will not be interrupted by the process. If it sleeps in the interrupt context, there is no way to wake it up, because all wake_up_xxx is specific to a process, and in the interrupt context, there is no concept of a process. There is no task_struct (which is the same for softirq as for tasklet), so it really sleeps, such as calling routines that cause block, and the kernel will almost certainly die.

2.schedule () saves the current process context (the value of the CPU register, the state of the process, and the contents of the stack) when switching processes so that the process can be resumed later. After an interrupt occurs, the kernel first saves the context of the currently interrupted process (resumes after calling the interrupt handler)

But in the interrupt handler, the value of the CPU register must have changed (the most important program counter PC, stack SP, etc.). If schedule () is called because of sleep or blocking operation, the saved process context is not the current process context. Therefore, you cannot call schedule () in an interrupt handler.

3. The schedule () function itself in the kernel determines whether it is in the interrupt context when it comes in:

If (unlikely (in_interrupt ()) BUG ()

Therefore, the result of forcibly calling schedule () is kernel BUG.

4. Interrupting handler uses the interrupted process kernel stack, but does not affect it in any way, because handler completely clears the part of the stack it uses, restoring it to what it was before it was interrupted.

5. When interrupting context, the kernel is not preemptive. Therefore, if you hibernate, the kernel must hang.

Spin lock deadlock

The spin lock is not recursive, and waiting for the lock you have acquired will lead to a deadlock.

A spin lock can be used in an interrupt context, but imagine a scenario in which a thread acquires a lock but is interrupted by an interrupt handler, and the interrupt handler also acquires the lock (but it was previously locked and cannot be acquired. Can only spin), the interrupt cannot exit, resulting in a deadlock because the code that releases the lock later in the thread cannot be executed. It doesn't matter if you confirm that the interrupt will not access the same lock as the thread.

First, consider the following scenario (kernel preemption scenario):

(1) process An accesses the shared resource R during a system call

(2) process B also accesses the shared resource R during a system call.

Will it lead to conflict?

Suppose there is an interrupt in the process of An accessing the shared resource R, and the interrupt awakens the sleeping, higher priority B. When the interrupt returns to the scene, the process switch occurs, B starts execution, and accesses R through the system call. If there is no lock protection, two thread will enter the critical area, resulting in incorrect program execution. OK, let's add spin lock to see how: a gets the spin lock before entering the critical section, similarly, there is an interruption in the process of An accessing the shared resource R, and the interrupt awakens the sleeping, higher priority BMagie B will still try to obtain the spin lock before visiting the critical section. At this time, because A process holds spin lock, B process enters the permanent spin. How to break the kernel of linux is very simple. When process An acquires spin lock, preemption on this CPU is prohibited (the situation of permanent spin above only occurs when the process of this CPU preempts the current process of this CPU). If An and B are running on different CPU, the situation will be simpler: although process A holds spin lock and causes process B to enter the spin state, process A will continue to execute and release spin lock quickly, releasing the spin state of process B because it is running on a different CPU.

Second, consider the following scenario (interrupt context scenario):

Process A running on CPU0 accessed the shared resource R during a system call.

Process B running on CPU1 also accesses the shared resource R during a system call.

The shared resource R is also accessed in the interrupt handler of the peripheral P

In such a scenario, can the critical area of access to shared resource R be protected by using spin lock?

We assume that process An on CPU0 holds spin lock to enter the critical section, at this time, peripheral P has an interrupt event and dispatches it to CPU1 for execution, which seems to be no problem. Handler executing on CPU1 will wait for process An on CPU0 for a while, and then the critical area will release spin lock immediately, but What happens if the interrupt event of peripheral P is dispatched to CPU0 for execution? process An on CPU0 is preempted by the interrupt context while holding the spin lock, while handler on the preemptive CPU0 still tries to obtain spin lock before entering the critical section. tragedy occurs, and the interrupt handler of P peripheral on CPU0 enters the spin state forever. Process B on CPU1 also inevitably fails when trying to hold spin lock, resulting in a spin state. To solve this problem, linux kernel adopts this approach: if access to the interrupt context is involved, spin lock needs to be used in conjunction with disabling interrupts on this CPU.

Third, consider the following scenario (the bottom half of the scene)

Linux kernel provides a rich mechanism for bottom half, which is slightly different, although it belongs to the same interrupt context. We can simply modify the above scenario: peripheral P is not interrupting access to shared resources R in handler, but in bottom half. Using spin lock+ to prohibit local interrupts can of course achieve the effect of protecting shared resources, but using a cow knife to kill a chicken seems to be making a mountain out of a molehill, and disable bottom half is fine at this time.

Fourth, the competition between interrupt contexts

The same interrupt handler is not executed in parallel on both uni core and multi core, which is a feature of linux kernel. If different interrupt handler needs to use spin lock to protect shared resources, for the new kernel (there is no distinction between fast handler and slow handler), all handler turn off interrupts, so using spin lock does not need to turn off interrupt cooperation. Bottom half is divided into softirq and tasklet, and the same softirq is executed concurrently on different CPU, so if a global variable is accessed in the handler of the softirq in a driver, the global variable needs to be protected by spin lock, without disable CPU interrupt or bottom half. Tasklet is simpler because there is no concurrency on multiple CPU of the same tasklet.

The realization principle of spin Lock

Data structure

First define a data type of spinlock_t, which is essentially an integer value (the operation on this value requires atomicity), which indicates whether spinlock is available or not. It is set to 1 during initialization. Call the spin_lock function when thread wants to hold the lock, which subtracts the integer value of spin lock by 1, and then determines that if it is equal to 0, it means you can get spin lock. If it is negative, it means that other thread holds the lock, and this thread requires spin.

The data types of spinlock_t in the kernel are defined as follows:

Typedef struct spinlock {struct raw_spinlock rlock;} spinlock_t; typedef struct raw_spinlock {arch_spinlock_t raw_lock;} raw_spinlock_t

General-purpose (for all kinds of arch) spinlock uses type name like spinlock_t, and various arch define their own struct raw_spinlock. Sounds like a good idea and naming until linux realtime tree (PREEMPT_RT) challenges spinlock.

The naming convention for spin lock is defined as follows:

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

Spinlock, which may be preempted when rt linux (PREEMPT_RT is configured) (the actual underlying layer may be using mutext that supports PI (priority inversion)).

Raw_spinlock, the tenacious spin even if configured with PREEMPT_RT.

Arch_spinlock,spin lock is related to architecture.

Implementation of arch_spin_lock Interface in ARM Architecture

Add lock

Similarly, here is only a typical API to analyze, others can learn by themselves. We chose arch_spin_lock, whose ARM32 code is as follows:

Static inline void arch_spin_lock (arch_spinlock_t * lock) {unsigned long tmp; U32 newval; arch_spinlock_t lockval; prefetchw (& lock- > slock) -(0) _ asm__ _ volatile__ ("1: ldrex% 0, [% 3]\ n"-(1) "add% 1,% 0,% 4\ n"-(2) "strex% 2,% 1 [% 3]\ n "- (3)" teq% 2, # 0\ n "- (4)" bne 1b ":" = & r "(lockval)," = & r "(newval)," = & r "(tmp):" r "(& lock- > slock)," I "(1 tickets.owner) -(7)} smp_mb ();-(8)} (0) operations related to preloading cache, mainly for performance considerations (1) lockval = lock- > slock (if lock- > slock is not exclusive by other processors, mark the exclusive access of the current processor to the lock- > slock address Otherwise, it will not affect) (2) newval = lockval + (1 slock] (if the current execution processor does not have exclusive access to the lock- > slock address, do not store it, return 1 to temp If the current processor has exclusive lock- > slock memory access, write to the memory, return 0 to temp, clear the exclusive mark) lock- > tickets.next = lock- > tickets.next+ 1 (4) check whether lockval.tickets.next is written successfully (5) lock- > tickets.owner, lock- > tickets.next is 0 at initialization, assuming that the first execution arch_spin_lock,lockval = * lock,lock- > tickets.next++,lockval.tickets.next equals lockval.tickets.owner Get the spin lock The spin lock is not released. In the second execution, lock- > tickets.owner = 0, lock- > tickets.next = 1. After copying to lockval, lockval.tickets.next! = lockval.tickets.owner, wfe will be executed to wait for the spin lock release to be awakened, and lock- > tickets.owner++,lockval.tickets.owner re-assignment will be performed when the spin lock is released. (6) suspend execution temporarily. If the current state of spin lock is locked, then call wfe to enter the waiting state. For more details, please refer to the description in the ARM WFI and WFE instructions. (7) other CPU awakens the execution of this cpu, indicating that the owner has changed, the new own is assigned to the lockval, and then continues to determine the state of the spin lock, that is, back to step 5. (8) for more information on the operation of memory barrier, please see the description in memory barrier.

Release lock

Static inline void arch_spin_unlock (arch_spinlock_t * lock) {smp_mb (); lock- > tickets.owner++;-(0) dsb_sev ();-- (1)}

(0) lock- > tickets.owner increases by 1, and the next awakened processor will check whether the value is equal to its own lockval.tickets.next. Lock- > tickets.owner represents the processor of the spin lock that can be acquired, and lock- > tickets.next you can get the owner of the spin lock. When the processor acquires the spin lock, it will first read lock- > tickets.next to compare with lock- > tickets.owner and add 1 to lock- > tickets.next. The lock- > tickets.next obtained by the next processor is inconsistent with the current processor. When both processors are compared with lock- > tickets.owner, it is certain that only one processor will be equal. When the spin lock is released, add 1 to lock- > tickets.owner, so First apply for the spin lock multiprocessor lock- > tickets.Nextvalue update, and naturally get the spin lock first.

(1) execute sev instruction to wake up the processor that wfe is waiting for

Spin lock causes deadlock instance

Two cases of deadlock

1) process A with spin lock is blocked in kernel state, and the kernel dispatch process B, which coincidentally has to acquire spin lock, so B can only rotate itself. At this time, preemption has been turned off, A process will not be scheduled, B always spin, resulting in deadlock.

2) process A has a spin lock, and when the interrupt arrives, CPU executes the interrupt function, and the interrupt handler function needs to acquire the spin lock and access the shared resources. At this time, the process A can not get the lock, but can only spin, resulting in deadlock.

How to avoid deadlock

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

If you also want to obtain a spin lock in the interrupt handler, the driver needs to disable interrupts when you have a spin lock

The spin lock must be owned in the shortest possible time

Prevent a function that acquires a lock from calling another function that also tries to acquire the lock, otherwise the code will deadlock; neither semaphore nor spin lock will allow the lock owner to acquire the lock for the second time, and if you try to do so, the system will hang.

The order rules of locks acquire locks in the same order; if you must acquire a local lock and a lock that belongs to the more central position of the kernel, you should first acquire your own local lock; if we have a combination of semaphore and spin lock, you must obtain semaphore first; it is a serious error to call down (which can cause sleep) when you have a spin lock.

Examples of deadlocks

Because the spin lock is held for a very short time and there is no intuitive phenomenon, here is an example that can lead to a deadlock.

Operation condition

Virtual machine: vmware

OS: Ubuntu 14

Configuration: set the number of virtual machines to 1, otherwise there will be no deadlock

Principle

For a single CPU, a task with a spin lock should not schedule a function that causes sleep, otherwise it will lead to a deadlock.

Steps:

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

After process An is on the open () character device, the corresponding kernel function will apply for a spin lock. At this time, the spin lock is idle, the spin lock is applied, and process An immediately enters the execution of the sleep () function and goes to sleep.

While process An is in sleep, the spin lock is always owned by process A.

Run process B, process B executes the open function, and the corresponding kernel function also applies for spin lock. At this time, the spin lock belongs to process A, so process B enters the spin state.

Because preemption has been turned off, the system is deadlocked.

The driver code is as follows:

# include # include static int major = 250; static int minor = 0; static dev_t devno; static struct cdev cdev; static struct class * cls; static struct device * test_device; static spinlock_t lock; static int flage = 1; # define DEAD 1 static int hello_open (struct inode * inode, struct file * filep) {spin_lock (& lock); if (flage! = 1) {spin_unlock (& lock) Return-EBUSY;} flage = 0; # if DEAD # elif spin_unlock (& lock); # endif return 0;} static int hello_release (struct inode * inode, struct file * filep) {flage = 1; # if DEAD spin_unlock (& lock); # endif return 0 } static struct file_operations hello_ops = {.open = hello_open, .release = hello_release,}; static int hello_init (void) {int result; int error; printk ("hello_init\ n"); result = register_chrdev (major, "hello", & hello_ops); if (result < 0) {printk ("register_chrdev fail\ n"); return result } devno = MKDEV (major,minor); cls = class_create (THIS_MODULE, "helloclass"); if (IS_ERR (cls)) {unregister_chrdev (major, "hello"); return result;} test_device = device_create (cls,NULL,devno,NULL, "test"); if (IS_ERR (test_device)) {class_destroy (cls) Unregister_chrdev (major, "hello"); return result;} spin_lock_init (& lock); return 0;} static void hello_exit (void) {printk ("hello_exit\ n"); device_destroy (cls,devno); class_destroy (cls); unregister_chrdev (major, "hello"); return;} module_init (hello_init); module_exit (hello_exit) MODULE_LICENSE ("GPL")

The test procedure is as follows:

# include # include main () {int fd; fd = open ("/ dev/test", O_RDWR); if (fd

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.