background

Due to the limitation of some resources in multiprocessor environment , Sometimes you need exclusive access (mutual exclusion), At this time, we need to introduce the concept of lock , Only tasks that acquire locks can access resources , Because the core of multithreading is CPU Time slice of , So only one task can acquire the lock at the same time .

When there is a resource access conflict in the kernel , There are usually two ways of handling :

  1. One is waiting in place
  2. One is to suspend the current process , Schedule other processes to execute ( sleep )

spinlocks

Spinlock It's a common locking mechanism provided by the kernel , Spin lock is “ Wait in place ” How to solve resource conflicts .
namely , After a thread acquires a spin lock , Another thread expects to acquire the spin lock , Can't get , We can only stay where we are “ Spin ”( Busy waiting ).

Because of the busy waiting property of spin lock , It's doomed to the limitations of its use scenarios —— Spin locks should not be held for a long time ( Consume CPU resources ).

Advantages of spin lock

Spinlocks do not switch thread state , Always in user state , That is, threads are always active Of ; Does not put the thread in a blocking state , Reduce unnecessary context switching , Fast execution .

The non spin lock will enter the blocking state when the lock cannot be acquired , So it goes into kernel state , Recover from kernel state when obtaining lock , Need thread context switch .( After the thread is blocked, it enters the kernel (Linux) Scheduling status , This will cause the system to switch back and forth between user state and kernel state , Seriously affect the lock performance ).

The use of spinlocks

stay linux kernel In the implementation of , We often encounter such a scene : Shared data is accessed by interrupt context and process context , How to protect ?

If only the process context is accessed , Then consider using semaphore perhaps mutex Lock mechanism , But now interrupt context is also involved , Those that can lead to sleep lock You can't use it , Now , Consider using spin lock.

In interrupt context , Sleep is not allowed , therefore , What's needed here is a lock that doesn't cause sleep ——spinlock.

In other words , Interrupt context should use lock , The preferred spinlock.

Use spin lock , There are two ways to define a lock :

Dynamic :

spinlock_t lock;spin_lock_init (&lock);

Static :

DEFINE_SPINLOCK(lock);

step

spinlock It's easy to use ,

  1. To access critical resources, we need to apply for spin lock first
  2. Spin without lock , If you can get the lock, you go into the critical zone
  3. When the spin lock is released , Spin in this lock task can acquire the lock and enter the critical region , Spin lock must be released from the critical mission area

Using examples

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;}

Add

The reason interrupt context can't sleep is :

  1. When interrupt handling , There should be no process switching , Because it's interrupting context in , The only way to interrupt the current interrupt handler Only higher priority interrupts , It won't be interrupted by the process , If in interrupt context Sleep in the middle , There's no way to wake it up , Because of all the wake_up_xxx It's all about a process , But in the interruption context in , There is no concept of process , no There is one task_struct( This is for softirq and tasklet equally ), So it's really dormant , For example, calling will cause block Routine for , The kernel is almost certain to die .

  2. schedule() When switching processes , Save the current process context (CPU Register value 、 The state of the process and the contents of the stack ), So that this process can be resumed later . After the interruption , The kernel will first save the context of the currently interrupted process ( Resume after calling interrupt handler );

But in interrupt handler ,CPU The value of the register must have changed ( The most important program counter PC、 Stack SP etc. ), If at this time due to sleep or blocking operation called schedule(), The saved process context is not the current process context 了 . Therefore, it is not allowed to call in interrupt handlers schedule().

  1. The kernel schedule() The function itself determines whether it is in the interrupt context when it comes in :
if(unlikely(in_interrupt()))BUG();

therefore , Force call schedule() The result is the kernel BUG.

  1. interrupt handler Will use the interrupted process kernel stack , But it won't have any impact on it , because handler After use, it will completely clear the part of the stack it uses , Restore the original appearance before being interrupted .

  2. In a state of interruption context When , The kernel is not preemptive . therefore , If you sleep , The kernel must hang .


Spin lock deadlocks

Spin lock is not recursive , I wait for the lock I've got , Can cause deadlock .

Spin locks can be used in interrupt context , But imagine a scene : A thread acquires a lock , But interrupted by the interrupt handler , The interrupt handler also gets the lock ( But it was locked before , Can't get , Only spin ), Interrupt cannot exit , The code that releases the lock later in the thread cannot be executed , Lead to a deadlock .( If you confirm that the interrupt will not access the same lock as the thread , It doesn't matter ).

One 、 Consider the following scenario ( Kernel preemption scenario ):

(1) process A A shared resource was accessed during a system call R

(2) process B Shared resources are also accessed during a system call R

Will there be conflict ?

Suppose that A Access shared resources R There was an interruption in the process of , The interruption awakens the sleeping , Higher priority B, When the interruption returns to the scene , A process switch occurs ,B Start execution , And through the system call access to R, If there is no lock protection , There will be two thread Enter the critical area , Causes the program to execute incorrectly .OK, We add spin lock See how :A Before entering the critical zone, we got spin lock, alike , stay A Access shared resources R There was an interruption in the process of , The interruption awakens the sleeping , Higher priority B,B You still try to get... Before you visit the critical area spin lock, At this time, due to A Processes hold spin lock And lead to B The process has entered a permanent spin…… How to deal with it ?linux Of kernel It's simple , stay A Process get spin lock When , Ban this CPU Preemption on the Internet ( The permanence above spin It's only in this CPU The process of seizing this CPU In a scenario like the current process of ). If A and B Run in different CPU On , Then the situation will be simpler :A Although the process holds spin lock And lead to B The process enters spin state , But because it's running on different CPU On ,A The process will continue to execute and will be released soon spin lock, relieve B Process spin state .

Two 、 Consider the following scenario ( Interrupt context scenarios ):

  1. Running on the CPU0 Progress on A A shared resource was accessed during a system call R
  2. Running on the CPU1 Progress on B Shared resources are also accessed during a system call R
  3. peripherals P The interrupt handler Shared resources are also accessed in R

In such a scenario , Use spin lock Can protect access to shared resources R The critical region of the earth ?

We assume that CPU0 Progress on A hold spin lock Enter the critical area , Now , peripherals P There was an interruption , And it's scheduled to CPU1 On the implementation , It doesn't seem to be a problem , Execute on CPU1 Upper handler I'll wait a little bit CPU0 Progress on A, As soon as it does, the critical zone will be released spin lock Of , however , If the peripherals P The interrupt event for is scheduled to CPU0 What's going to happen with the execution on the Internet ?CPU0 Progress on A In the hold spin lock Is preempted by the interrupt context , And grab it CPU0 Upper handler You're still trying to get... Before you go into the critical zone spin lock, Tragedy struck ,CPU0 Upper P Interruption of peripherals handler Enter forever spin state , Now ,CPU1 Progress on B And inevitably trying to hold spin lock When you fail, you get into spin state . To solve such problems ,linux kernel Such an approach was adopted : If it's about interrupt context access ,spin lock Need and ban this CPU Interrupt Union on .

3、 ... and 、 Consider the following scenario ( The bottom half of the scene )

linux kernel Provides a wealth of bottom half The mechanism of , Although they belong to the same interrupt context , But it's a little different . We can simply modify the above scene : peripherals P It's not a break handler Access shared resources in R, It's about bottom half Medium visit . Use spin lock+ Forbidding local interruption can achieve the effect of protecting shared resources , But it's a bit of a fuss to use a bull's knife to kill chickens , Now disable bottom half That's all right. .

Four 、 Interrupt context competition

The same interrupt handler Between uni core and multi core It's not going to run in parallel , This is a linux kernel Characteristics of .
If different interrupt handler Need to use spin lock Protect shared resources , For the new kernel ( Indistinguishes fast handler and slow handler), all handler It's all off and off , Therefore use spin lock No need to turn off interrupt coordination .
bottom half And is divided into softirq and tasklet, The same softirq Will be in a different CPU Concurrent execution on , So if one of the drivers softirq Of handler A global variable is accessed in , For this global variable, you need to use spin lock The protection of , No need to cooperate disable CPU Interrupt or bottom half.
tasklet It's simpler , Because the same tasklet Not many CPU Concurrent on .

The realization of spin lock

data structure

So let's define a spinlock_t Data type of , It's essentially an integer value ( The operation of this number needs to be atomic ), This value represents spin lock Is it available . Initialization is set to 1. When thread Call when you want to hold the lock spin_lock function , This function will spin lock That integer minus 1, Then judge , If it is equal to 0, Means that you can get spin lock, If it's a negative number , Other thread Hold the lock , Ben thread need spin.

Kernel spinlock_t The data types of 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;

Universal ( Applicable to all kinds of arch) Of spin lock Use spinlock_t In this way type name, Various arch Define your own struct raw_spinlock. Sounds like a good idea and naming , until linux realtime tree(PREEMPT_RT) Put forward to spinlock The challenge of .

spin lock The nomenclature of is defined as follows :

  1. spinlock, stay rt linux( Configured with PREEMPT_RT) It's going to be preempted when it's time ( The actual bottom layer might be using support PI( Priority flipping ) Of mutext).
  2. raw_spinlock, Even if it's configured PREEMPT_RT We should also be tenacious spin
  3. arch_spinlock,spin lock Is and architecture dependent ,

ARM Structure system arch_spin_lock Interface implementation

Lock

alike , Here is just a typical example API To analyze , Others can learn by themselves . What we chose is arch_spin_lock, Its ARM32 The code for 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 << TICKET_SHIFT)
   : "cc");
   while (lockval.tickets.next != lockval.tickets.owner) {----(5)       wfe();------------(6)
 lockval.tickets.owner = ACCESS_ONCE(lock->tickets.owner);----(7)   }   smp_mb();-----------(8)}

(0) and preloading cache Related operations , Mainly for the sake of performance
(1)lockval = lock->slock ( If lock->slock Not exclusive to other processors , Then mark the current execution processor pair lock->slock Exclusive access to address ; Otherwise, it will not affect )(2)newval = lockval + (1 << TICKET_SHIFT)(3)strex tmp, newval, [&lock->slock] ( If the current execution processor is not exclusive lock->slock Address access , No storage , return 1 to temp; If the current processor is already exclusive lock->slock Memory access , Write to the memory , return 0 to temp, Clear exclusive flag ) lock->tickets.next = lock->tickets.next + 1
(4) Check whether the write is successful  lockval.tickets.next
(5) On initialization lock->tickets.owner、lock->tickets.next All for 0, Suppose for the first time arch_spin_lock,lockval = *lock,lock->tickets.next++,lockval.tickets.next  be equal to  lockval.tickets.owner, Get the spin lock ; Spin lock not released , The second time it was executed ,lock->tickets.owner = 0, lock->tickets.next = 1, copy to lockval after ,lockval.tickets.next != lockval.tickets.owner, Will execute wfe Waiting to be released by spin lock and awakened , When the spin lock is released  lock->tickets.owner++,lockval.tickets.owner Reassign
(6) Suspend execution temporarily . If at present spin lock The state of is locked, So called wfe Enter the waiting state . For more details, please refer to ARM WFI and WFE The description in the instruction .
(7) Other CPU Wake up Ben cpu Implementation , explain owner There is a change , The new own Assign to lockval, Then continue to judge spin lock The state of , That is to go back to step 5.
(8)memory barrier The operation of , For details, please refer to memory barrier Description in .

Release the lock

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

  • (0)lock->tickets.owner increase 1, The next awakened processor checks to see if the value matches its own lockval.tickets.next equal ,lock->tickets.owner The processor that represents the spin lock that can be acquired ,lock->tickets.next You can get a spin lock owner; When the processor acquires the spin lock , Read first lock->tickets.next Used with lock->tickets.owner Compare and compare with lock->tickets.next Add 1, The next processor gets lock->tickets.next It's inconsistent with the current processor , Both processors are connected to lock->tickets.owner Compare , There must be only one processor equal , When the spin lock is released lock->tickets.owner Add 1 Calculation , therefore , First apply for spinlock multiprocessor lock->tickets.next Value update , Nature gets the spin lock first
  • (1) perform sev Instructions , Wake up the wfe Waiting processors

Spin lock causes deadlock instance

Deadlocked 2 In this case

1) Spin locked processes A It's blocked in kernel state , Kernel scheduling B process , Happen B Processes also need to acquire spin locks , here B It can only rotate itself . And by this time preemption is closed , No scheduling A Process ,B Always spin , Generate deadlock .
2) process A Having a spin lock , The interruption came ,CPU Execute interrupt function , Interrupt handling function , The interrupt handler needs to get the spin lock , Access shared resources , The lock cannot be obtained at this time , Only spin , Generate deadlock .

How to avoid deadlock

  1. If you also want to get spin lock in interrupt handling function , Then the driver needs to disable interrupt when it has spin lock ;
  2. Spin lock must be owned in the shortest possible time
  3. Avoid a function that gets the lock from calling another function that also tries to get the lock , Otherwise, the code will deadlock ;
    Whether it's semaphores or spinlocks , The lock owner is not allowed to acquire the lock a second time , If you try to do that , The system will hang ;
  4. The order of locks
    Get locks in the same order ;
    If you have to get a local lock and a lock that belongs to a more central location of the kernel , You should get your own local lock first ;
    If we have a combination of semaphores and spinlocks , You have to get the semaphore first ; Call when you have a spin lock down( Can cause dormancy ) It's a serious mistake .

Examples of deadlocks

Because the spin lock hold time is very short , There is no intuitive phenomenon , Here is an example of deadlock .

Operating conditions

  • virtual machine :vmware

  • OS :Ubuntu 14

  • To configure : Set the number of virtual machines to 1, Otherwise, there will be no deadlock
     Insert picture description here

principle

For single CPU, Tasks with spin locks should not schedule functions that cause sleep , Otherwise, it will lead to deadlock .

step :

 Insert picture description here

  1. process A stay open() After the character device , The corresponding kernel function will apply for spin lock , Now the spin lock is idle , Apply to spin lock , process A Then go to execution sleep() Function goes to sleep ;
  2. In the process A be in sleep period , Spin lock always belongs to the process A all ;
  3. Run the process B, process B perform open function , The corresponding kernel function will also apply for spin lock , At this point, the spin lock process A all , So the process B Go into spin ;
  4. Because the preemption is now closed , System deadlock .

The driver code is as follows :

#include <linux/init.h>#include <linux/module.h>#include <linux/kdev_t.h>#include <linux/fs.h>#include <linux/cdev.h>#include <linux/device.h>#include <linux/spinlock.h>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 1static int hello_open (struct inode *inode, struct file *filep){spin_lock(&lock);if(flage !=1){ spin_unlock(&lock); return -EBUSY;}flage =0;#if DEAD#elifspin_unlock(&lock);#endifreturn 0;}static int hello_release (struct inode *inode, struct file *filep){flage = 1;#if DEADspin_unlock(&lock);#endifreturn 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 <stdio.h>#include <sys/types.h>#include <sys/stat.h>#include <fcntl.h>main(){int fd;fd = open("/dev/test",O_RDWR);if(fd<0){perror("open fail \n");return;}sleep(20);close(fd);   printf("open ok \n ");}

testing procedure :

  1. Compile and load the kernel
makeinsmod hello.ko

  1. Run the process A
gcc test.c -o a
./a

  1. Open a new terminal , Run the process B
gcc test.c -o b
./b

Be careful , It has to be in the process A Run the process without exiting B.