One for engineering students , Keen on the underlying technology development , Have a strong curiosity , I'm interested in MCU , The embedded Linux,Uboot etc. , Welcome to study and exchange !
I like running , To play basketball , sleep .
Welcome to join me QQ1500836631( remarks CSDN), Learn and communicate with each other , Sharing various learning materials , electronic text , Learning videos, etc .


List of articles


Introduction to concurrency and contention in kernel

Early Linux The kernel , There are relatively few sources of concurrency . Early kernels did not support symmetric multiprocessing ( symmetric multi processing,SMP), therefore , The only reason for concurrent execution is the interruption of service to the hardware . This situation is relatively simple to deal with , But not for systems that use more processors for better performance and emphasize fast response to events .

In response to the needs of modern hardware and Applications , Linux The kernel has evolved to deal with more things at the same time .Linux The system is a multitasking operating system , There will be multiple tasks accessing the same memory area at the same time , These tasks may overlap each other with the data in memory , Cause memory data confusion . We must deal with this problem , If it's serious, it may cause the system to crash . current Linux The cause of system concurrency is very complicated , To sum up, there are several main reasons :

  1. Multithreaded concurrent access , Linux It's multitasking ( Threads ) The system of , So multithreading is the basic reason .
  2. Preemptive concurrent access , Kernel code is preemptive , therefore , Our driver code may lose exclusive access to the processor at any time
  3. Interrupt program concurrent access , Device interrupts are asynchronous events , It can also lead to concurrent code execution .
  4. SMP( Multicore ) Concurrent access between cores , Now? ARM Multi core architecture SOC Very common , Multicore CPU There is concurrent access between cores . Multiple running user space processes can access our code in an amazing combination ,SMP The system can even execute our code on different processors at the same time .

As long as our program is running , Concurrency and competition are possible . such as , When two threads of execution need to access The same data structure ( Or hardware resources ) when , The possibility of mixing exists forever . So when designing your own driver , We should avoid sharing resources . If there is no concurrent access , There will be no competition . therefore , Carefully written kernel code should have Least sharing . The most obvious application of this idea is Avoid using global variables . If we put resources where multiple threads of execution will find them ( A critical region ), There must be a good reason .

How to prevent our data from being accessed concurrently ? This is the time to establish a protection mechanism , The following describes several concurrent and competitive processing methods provided by several kernels .

Atomic manipulation

Introduction to atomic operation

atom , Early exposure is in the chemical concept . Atoms are basic particles that cannot be further separated by chemical reactions . alike , The atomic operation in the kernel means that this access is a step , It has to be done all at once , Can't be interrupted , No more splits .
for example , In multithreaded access , We have a couple of threads a Perform assignment operation ,a=1, Thread two is also right a Perform assignment operation a=2, Our ideal execution order is that threads execute first , Thread two executes again . But it's very likely to be interrupted by other operations when the thread is executing , Make the last execution result of thread one become a=2. To solve this problem , We must ensure that our thread one cannot be interrupted by other operations in the process of data access , One time execution complete .

Integer atom operation function

function describe
ATOMIC_INIT(int i) Initialize atomic variables when they are defined .
int atomic_read(atomic_t*v) Read v Value , And back to
void atomic_set(atomic_t *v, int i) towards v write in i value .
void atomic_add(int i, atomic_t *v) to v add i value .
void atomic_sub(int i, atomic_t *v) from v subtract i value .
void atomic_inc(atomic_t *v) to v Add 1, That is, self increasing .
void atomic_dec(atomic_t *v) from v reduce 1, That is, self subtraction .
int atomic_dec_return(atomic_t *v) from v reduce 1, And back to v Value .
int atomic_inc_return(atomic_t *v) to v Add 1, And back to v Value .
int atomic_sub_and_test(int i, atomic_t *v) from v reduce i, If the result is 0 Just go back to real , Otherwise return to false
int atomic_dec_and_test(atomic_t *v) from v reduce 1, If the result is 0 Just go back to real , Otherwise return to false
int atomic_inc_and_test(atomic_t *v) to v Add 1, If the result is 0 Just go back to real , Otherwise return to false
int atomic_add_negative(int i, atomic_t *v) to v Add i, If the result is negative, return true , Otherwise return false

notes :64 The integer atom operation of bit just puts “atomic_” Change the prefix to “atomic64_”, take int Switch to long long.

Bit atom operation function

function describe
void set_bit(int nr, void *p) take p Address of the nr Location 1
void clear_bit(int nr,void *p) take p Address of the nr A reset
void change_bit(int nr, void *p) take p Address of the nr Bit reversal
int test_bit(int nr, void *p) obtain p Address of the nr The value of a
int test_and_set_bit(int nr, void *p) take p Address of the nr Location 1, And back to nr Bit original value
int test_and_clear_bit(int nr, void *p) take p Address of the nr Positional clarity 0, And back to nr Bit original value
int test_and_change_bit(int nr, void *p) take p Address of the nr Bit flip , And back to nr Bit original value

Atomic operation routines

/*  Defining atomic variables , The initial value is 1*/static atomic_t xxx_available = ATOMIC_INIT(1); static int xxx_open(struct inode *inode, struct file *filp){
 ...
 /*  Check by judging the value of the atomic variable LED Is it used by other applications  */
 if (!atomic_dec_and_test(&xxx_available)) {
 /* Less than 0 If so, add 1, Make its atomic variable equal to 0*/
 atomic_inc(&xxx_available);
 /* LED By using , Back to busy */
 return - EBUSY; 
 }.../*  success  */
 return 0;static int xxx_release(struct inode *inode, struct file *filp){
 /*  Release atomic variables when closing the driver file  */
 atomic_inc(&xxx_available); 
 return 0;}

spinlocks

So we talked about atomic variables , You can see from its operation function that , Atomic operations can only be directed at Integer variables or bits . Suppose we have a struct variable that needs to be threaded A Visited , In a thread A Cannot be accessed by other threads during access , So what do we do ? Spin lock can complete the protection of structural variables .

Introduction to spin lock

spinlocks , seeing the name of a thing one thinks of its function , We can think of him as a lock on the toilet door . This toilet door has only one key , When we go in , Take the key off , Go in and lock it . So when the second person wants to come in , We have to wait until we get out . When the second person is waiting outside , May have been waiting around the door .

So is our spin lock , Spin lock has only two states: lock and unlock . When we get in, get the key, get in the toilet , This is equivalent to the state of spin lock , No one can come in during this period . When the second person wants to come in , This is equivalent to a thread B Want to access this shared resource , But it's not accessible right now , So threads B Just waiting in place , Always check if you can access this shared resource . When we get out of the toilet , At this time “ Unlock ” 了 , Only at this time can threads B Ability to visit .

If , What if people in the toilet stay too long ? People outside are waiting all the time ? If it's us , Definitely not , It's a waste of time , Maybe we'll find other ways to solve the problem . It's the same with spin locks , If the thread A hold Spin lock time too long , It's obviously a waste of processor time , Reduced system performance . We know CPU The greatest invention is multithreading , This time let the thread B I don't know how long to wait here , It's obviously unreasonable . therefore , If Spin lock is only suitable for short-term holding , If you need to hold it for a long time , We're going to do it in a different way ( Mutex below ).

Spin lock operation function

function describe
DEFINE_SPINLOCK(spinlock_t lock) Defines and initializes a spin variable
int spin_lock_init(spinlock_t *lock) Initialize spin lock
void spin_lock(spinlock_t *lock) Gets the specified spin lock , It's also called locking
void spin_unlock(spinlock_t *lock) Release the specified spin lock .
int spin_trylock(spinlock_t *lock) Try to get the specified lock , If not , return 0
int spin_is_locked(spinlock_t *lock) Check whether the specified spin lock is acquired , If it is not obtained, return not 0, Otherwise return to 0.

Spin lock is mainly for Multiprocessor systems The design of the . about Single processor and kernel does not support preemption , Once you're in the spin state , It will spin forever . because , No thread can get CPU To release the lock . therefore , In a single processor system where the kernel does not support preemption , Spin lock will be set to null operation .

The functions in the list above Apply to SMP Or support preemptive orders CPU Concurrent access between threads , That is, between threads , Spin locked critical protection zone Must not call anything that can cause sleep and block ( In fact, the essence is still sleep ) Of API function , Otherwise, it may lead to deadlock . Spin lock will Automatic no preemption , In other words, when a thread A When I get the lock, I'll Temporarily prohibit kernel preemption . If the thread A Entered while holding the lock Sleep state , So thread A Meeting Give up automatically CPU Right to use . Threads B Began to run , Threads B Also want to get locks , But at this point the lock is A Thread hold , and Kernel preemption is also banned ! Threads B Can't be dispatched , So thread A Can't run , The lock cannot be released Deadlock It happened. !

When concurrent access occurs between threads , If you interrupt at this time, you have to plug in , Interrupt also wants to access shared resources , So what should we do ? The first thing is for sure , Interrupt inside using spin lock , But when using spin lock in interrupt , Before getting the lock, be sure to No local interruptions first ( That is to say Ben CPU interrupt , For multi-core SOC There will be many CPU nucleus ), Otherwise, it may lead to lock phenomenon . Here's an example :

// Threads Aspin_lock(&lock);.......functionA();.......spin_unlock(&lock);// Interruption occurs , Running threads Bspin_lock(&lock);.......functionA();.......spin_unlock(&lock);

Threads A First run , And got it lock This lock , When a thread A function functionA Function when the interrupt occurs , The interruption robbed CPU Right to use . The next interrupt service function also needs to get lock This lock , But this lock is locked by the thread A Possess , The interruption will spin all the time , Wait for the lock to work . But before the interrupt service function is finished , Threads A It's impossible to carry out , Threads A say “ You let go first ”, He said “ You let go first ”, The scene is so deadlocked !

After using spin lock, we can ensure that the critical region is not affected by other factors CPU And Ben CPU Preemption within the process of disturbing , But when the code that gets the lock executes the critical section , It can also be affected by interruptions and the bottom half , To prevent this effect , It is recommended to use the functions in the following list :

function describe
void spin_lock_irq(spinlock_t *lock) Local interruptions are prohibited , And get the spin lock
void spin_unlock_irq(spinlock_t *lock) Activate local interrupt , And release the spin lock
void spin_lock_irqsave(spinlock_t *lock, unsigned long flags) Save interrupt state , Local interruptions are prohibited , And get the spin lock
void spin_unlock_irqrestore(spinlock_t *lock, unsigned long flags) Restore the interrupt state to the previous state , And activate the local interrupt , Release the spin lock

In multicore programming , If the process and interrupt may access the same critical resource , We generally need to call in the context of the process spin_ lock irqsave() spin_unlock_irqrestore(), Called in the interrupt context spin_lock() spin _unlock(). such , stay CPU On , Whether it's process context , Or does the interrupt context get the spin lock , thereafter , If CPU1 Whether it's process context , Or interrupt context , To get the same spin lock , We have to wait , This avoids all the possibility of concurrency between cores . meanwhile , Because the process context of each core holds the lock with spin_lock_irgsave(), So the interrupt on the core is impossible to enter , This avoids the possibility of intra core concurrency .

DEFINE_SPINLOCK(lock) /*  Define and initialize a lock  */ /*  Threads A */void functionA (){ unsigned long flags; /*  Interrupt state  */
 spin_lock_irqsave(&lock, flags) /*  Get the lock  */ 
  /*  A critical region  */ spin_unlock_irqrestore(&lock, flags) /*  Release the lock  */ } 
 /*  Interrupt service function  */
 void irq() { 
 spin_lock(&lock) /*  Get the lock  */ 
   /*  A critical region  */ 
 spin_unlock(&lock) /*  Release the lock  */ }

Spin lock routines

static int xxx_open(struct inode *inode, struct file *filp){...spinlock(&xxx_lock);if (xxx_count) {/*  Already open */spin_unlock(&xxx_lock);return -EBUSY;
 }
 xxx_count++;/*  Increase usage count */
  spin_unlock(&xxx_lock);
 ...
 return 0;/*  success  */}static int xxx_release(struct inode *inode, struct file *filp){
 ...
 spinlock(&xxx_lock);
 xxx_count--;/*  Reduce use count */
 spin_unlock(&xxx_lock);
  return 0;}

Read write spin lock

When a file in the critical area can be Read at the same time , But also Can't be read and written at the same time . If a thread is reading , Another thread is writing , Well, it's very likely to read the wrong Incomplete data . Read write spin lock can be Allows concurrent read operations on shared resources in critical areas . But multiple threads are not allowed to read and write concurrently . If you want to read and write concurrently , We're going to use sequence lock .
The read operation function of the read-write spin lock is as follows :

function describe
DEFINE_RWLOCK(rwlock_t lock) Define and initialize read-write locks
void rwlock_init(rwlock_t *lock) Initialize read / write lock
void read_lock(rwlock_t *lock) Get read lock
void read_unlock(rwlock_t *lock Release read lock
void read_unlock_irq(rwlock_t *lock) Turn on local interrupt , And release the read lock
void read_lock_irqsave(rwlock_t *lock,unsigned long flags) Save interrupt state , Local interruptions are prohibited , And get the read lock
void read_unlock_irqrestore(rwlock_t *lock,unsigned long flags) Restore the interrupt state to the previous state , And activate the local interrupt , Release read lock
void read_lock_bh(rwlock_t *lock) Close the bottom half , And get the read lock
void read_unlock_bh(rwlock_t *lock) Open the bottom half , And release the read lock

The write operation function of the read-write spin lock is as follows :

function describe
void write_lock(rwlock_t *lock) Get write lock
void write_unlock(rwlock_t *lock) Release the write lock
void write_lock_irq(rwlock_t *lock) Local interruptions are prohibited , And get the write lock .
void write_unlock_irq(rwlock_t *lock) Turn on local interrupt , And release the write lock
void write_lock_irqsave(rwlock_t *lock,unsigned long flags) Save interrupt state , Local interruptions are prohibited , And get the write lock
void write_unlock_irqrestore(rwlock_t *lock,unsigned long flags) Restore the interrupt state to the previous state , And activate the local interrupt , Release the write lock
void write_lock_bh(rwlock_t *lock) Close the bottom half , And get the write lock
void write_unlock_bh(rwlock_t *lock) Open the bottom half , And release the write lock

Read write lock routine

rwlock_t lock; /*  Definition rwlock */rwlock_init(&lock); /*  initialization rwlock *//*  Get lock on read */read_lock(&lock);... /*  Critical resources  */read_unlock(&lock);/*  Get lock on write */write_lock_irqsave(&lock, flags);... /*  Critical resources  */write_unlock_irqrestore(&lock, flags);

Sequential lock

Sequential lock is an optimized version of read-write lock , Read write lock does not allow simultaneous reading and writing , While using Sequence lock can complete the operation of reading and writing at the same time , But it's not allowed to write at the same time . Although sequential locks can read and write at the same time , But it's not recommended , The process of reading does not guarantee the integrity of the data .

Sequential lock operation function

The sequence of read lock operations is shown below :

function describe
DEFINE_SEQLOCK(seqlock_t sl) Define and initialize the sequence lock
void seqlock_ini seqlock_t *sl) Initialize sequence lock
void write_seqlock(seqlock_t *sl) Sequential lock write operations
void write_sequnlock(seqlock_t *sl) Get the write order lock
void write_seqlock_irq(seqlock_t *sl) Local interruptions are prohibited , And get the write order lock
void write_sequnlock_irq(seqlock_t *sl) Turn on local interrupt , And release the write order lock
void write_seqlock_irqsave(seqlock_t *sl,unsigned long flags) Save interrupt state , Local interruptions are prohibited , And get the write order
void write_sequnlock_irqrestore(seqlock_t *sl,unsigned long flags) Restore the interrupt state to the previous state , And activate the local interrupt , Release the write order lock
void write_seqlock_bh(seqlock_t *sl) Close the bottom half , And get the write read lock
void write_sequnlock_bh(seqlock_t *sl) Open the bottom half , And release the write read lock

The write function of a sequential lock is as follows :

function describe
DEFINE_RWLOCK(rwlock_t lock) Call this function when the read unit accesses the shared resource , This function returns the sequence number of the sequence lock
unsigned read_seqretry(const seqlock_t *sl,unsigned start) After reading, the function is called to check whether or not the resources are written in the process of reading , If there is one, reread it

Precautions for using spin lock

  1. Because while waiting for the spin lock, it's in “ The spin ” state , So you can't hold the lock for too long , It must be short , Otherwise, the system performance will be reduced . If the critical area is large , If the running time is relatively long, you should choose other concurrent processing methods , For example, we will talk about semaphores and mutexes later .
  2. In the critical area of spin lock protection, you can't call any API function , such as copy_from_user()、copy_to_user()、kmalloc() and msleep() Such as function , Otherwise, it may lead to deadlock .
  3. Cannot recursively apply for spin lock , Because once you apply recursively for a lock you are holding , Then you have to “ The spin ”, Waiting for the lock to be released , But you're in “ The spin ” state , There's no way to release the lock . As a result, I locked myself up
  4. When writing drivers, we must consider the portability of drivers , So whether you're single core or multi-core SOC, Think of it as multi-core SOC To write the driver .

copy_from_user The use of is combined with the process context , Because they're going to visit “user” Of memory space , This “user” It has to be a specific process . If you use these two functions in the driver , It must be used in functions that implement system calls , Cannot be used in functions that implement interrupt handling . If... Is used in interrupt context , Then the code is likely to operate on irrelevant process address space . Secondly, because the operation page may be swapped out , These two functions may sleep , So it can't be used in interrupt context as well .

Semaphore

Introduction to semaphores

Semaphores are similar to spin locks , The difference is that the semaphore sends out a signal telling you how long you need to wait . therefore , There will be no waiting . such as , Yes 100 A parking lot with two parking spaces , The number of parking lots updated in real time on the electronic display screen at the door is a semaphore . This number of stops is a semaphore , He told us if we could park in . When a car comes in , Signal plus one , When a car comes out , One less signal .
such as , Only one person can enter the toilet at a time , When A When you're inside ,B I want to go in , If it's a spin lock , that B Will be waiting at the door . If it's a semaphore ,A Will give you B A signal , You go back first , I came out to call you . This is an example of a semaphore ,B hear A After sending the signal , You can go back to bed first , wait for A come out .
therefore , Semaphores can obviously improve the execution efficiency of the system , A lot of useless work is avoided . Semaphores have the following characteristics :

  1. Because semaphores can make the thread waiting for resources go to sleep , So it applies to those It takes a long time The occasion of .
  2. So semaphores cannot be used in interrupts , Because semaphores cause sleep , Interrupt cannot sleep .
  3. If the holding time of shared resources is short , Then it's not appropriate to use semaphores , Because of frequent dormancy 、 The cost of switching threads is much greater than the advantage of semaphores .

Semaphore operation function

function describe
DEFINE_SEAMPHORE(name) Define a semaphore , And set the semaphore value to 1
void sema_init(struct semaphore *sem, int val) Initialize semaphores sem, Set the semaphore value to val
void down(struct semaphore *sem) Acquisition semaphore , Because it causes dormancy , So it can't be used in interrupts
int down_trylock(struct semaphore *sem); Try to get the semaphore , If you can get the semaphore, you can get , And back to 0. If you can't, return to the non 0, And it doesn't go into hibernation
int down_interruptible(struct semaphore Acquisition semaphore , and down similar , Just use dow A thread that goes to sleep cannot be interrupted by a signal . When you use this function to enter sleep, you can be interrupted by the signal
void up(struct semaphore *sem) Release semaphore

Semaphore routines

struct semaphore sem; /*  Defining semaphores  */ sema_init(&sem, 1); /*  Initialize semaphores   It means that only one thread can access this resource at the same time  */
 down(&sem); /*  Application semaphore  */
  /*  A critical region  */ 
 up(&sem); /*  Release semaphore  */

mutex

Introduction to mutex

A shared resource is accessed only once by a shared thread , You can't recursively apply for mutexes .
Semaphores can also be used for mutexes , When semaphores are used for mutual exclusion ( That is to avoid multiple processes running in a critical area at the same time ), The value of the semaphore should be initialized to 1. This semaphore can only be owned by a single process or thread at any given time . In this mode of use , Sometimes called a semaphore “ mutex ( mutex)”, It's mutually exclusive ( mutual exclusion) For short .Linux The kernel All the semaphores of Jiping are used for mutual exclusion .

Mutually exclusive functions

function describe
DEFINE_MUTEX(name) Define and initialize a mutex Variable
void mutex_init(mutex *lock) initialization mutex
void mutex_lock(struct mutex *lock) obtain mutex, That is to give mutex locked . If you can't get it, go to sleep
void mutex_unlock(struct mutex *lock) Release mutex, Just give it to mutex Unlock
int mutex_trylock(struct mutex *lock) Judge mutex Whether it is acquired or not , If so, return , Otherwise return to 0
int mutex_lock_interruptible(struct mutex *lock) Use this function to get semaphore failure, after entering sleep can be interrupted by signal

Mutex routines

struct mutex lock; /*  Define a mutex  */ mutex_init(&lock); /*  Initialize mutex  */ mutex_lock(&lock); /*  locked  */ /*  A critical region  */mutex_unlock(&lock); /*  Unlock */

Mutex and spin lock

Both mutex and spin lock are means to solve the problem of mutex . Mutexes are process level , Mutex can switch between processes when it is used , therefore , Using mutex resources costs a lot . Spin lock can save context switching time , If you don't hold the lock for a long time , Spin lock is a good choice , If you hold the lock for a long time , Mutex is obviously a better choice .

Precautions for using mutex

  1. When the lock cannot be acquired , The overhead of using mutexes is Process context switch time , The overhead of using spin locks is waiting Get the spin lock ( It is decided by the execution time of the critical area ). If the critical area is small , Spin lock should be used , If the critical area is large , Mutex should be used .
  2. The critical area protected by mutex can contain code that may cause blocking , The spin lock is absolutely necessary to avoid protecting the critical area containing such code . because Blocking means switching processes , If the process is switched out , Another process attempts to acquire this spin lock , Deadlocks happen .
  3. Mutexes exist in the process context . therefore , If the protected shared resource needs to be used in case of interruption or soft interruption , Only spin lock can be selected between mutex and spin lock . Of course , If you have to use mutexes , Only through mutex trylock() In a way that , In order to avoid blocking immediately .

Everyone's encouragement is the driving force for me to continue to create , If you think it's good , Welcome to your attention , give the thumbs-up , Collection , forward , thank you !