Shulou(Shulou.com)05/31 Report--

This article focuses on "what are the Linux concurrency control technologies". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "what are the Linux concurrency control technologies?"

Interrupt mask

As the name implies, it shields all interrupts. In embedded systems, interrupt masking can have three levels

1. Shielding of hardware interface

two。 Shielding of hardware GIC

3. Shielding of CPU (kernel).

If it is shielded at the interface, then the interrupt will be lost and cannot be found at all. If it is blocked at GIC, if there is an irq_1,irq_2,irq_3 interrupt during the blocking period, because there is only one pending flag bit, the pending will be set when * irq_3 comes, and then the mask will be unblocked. CPU will still deal with it when it finds that pending has been set, but 1Min 2 will definitely be lost. The mask at ARM, that is, the mask in the kernel, depends on how it is set. If it is local_irq_disable, then it is lost, just like shielding at the interface. If local_irq_save is the same as the second one, the kernel also has a corresponding mechanism to count interrupts, knowing how many interrupts have come during this period, but in actual operation. For the most part, we don't chase after a missed interrupt unless it's very important.

What we are talking about here is interrupt masking in the kernel. Because many important operations in the kernel depend on interrupts, it is very dangerous to shield all interrupts, and the code executed in it should be as fast as possible. Moreover, because the process scheduling of the kernel is also driven by interrupts, it is not possible to cause dormant code in the interrupt mask, otherwise it cannot be awakened. Note that interrupt masking only shields the interrupts of this CPU, so it does not solve the competitive Thai problem caused by SMP. In general, interrupt masking is used in conjunction with spin locks to prevent access to the critical area of spin lock protection from being interrupted.

Ordinary interrupt masking

Local_irq_disable (); / / mask interrupts / / or local_irq_save (flags); / / mask interrupts and save interrupt bit information in the current CPU / * critical section * / local_irq_enable (); / / unmask / / or local_irq_restore (flags); / / unmask and restore interrupt bit information

Interrupt shielding of the bottom half

Local_bh_disable (); / / mask interrupts / * critical section * / local_bh_enable ()

Atomic operation

Atomic operations are operations that cannot be interrupted, and like the concept of the application layer, the atomic operation templates in the kernel are as follows:

Integer atomic variable

/ / asm/atomic.h / / create and initialize atomic variable atomic_t tv = ATOMIC_INIT (initial value); / / read atomic variable int atomic_read (atomic_t * v); / / write atomic variable void atomic_set (atomic_t * v, int I) / * atomic_dec_and_test-try to change the atomic variable-1 * v: if the atomic variable changes to 0 after-1, return non-0, otherwise return 0 * / int atomic_dec_and_test (volatile atomic_t * v); int atomic_inc_and_test (volatile atomic_t * v); int atomic_sub_and_test (int I, volatile atomic_t * v) / / operate and return int atomic_add_return (int I, atomic * v); int atomic_sub_return (int I, atomic * v); int atomic_inc_return (atomic * v); int atomic_dev_return (atomic * v)

Template

Static atomic_t tv; static int demo_open (struct inode * inode, struct file * filp) {if (! atomic_dec_and_test (& tv)) {atomic_inc (& tv); return-EBUSY;} / * Operation Code * / return 0;} static int demo_release (struct inode * inode, struct file * filp) {atomic_inc (& tv); return 0 } static int _ init demo_init (void) {/ / init atomic_t atomic_set (& tv, 1);}

Bit atom operation

Bit atomic operations are atomic bit operations. "bits" are widely used in the kernel to record information, such as bitmaps. These operations must be atomic. The kernel API is as follows:

/ / set bit void set_bit (nr,void * addr); / / clear bit void clear_bit (nr,void * addr); / / change bit void change_bit (nr,void * addr); / / Test bit test_bit (nr,void * addr); / / Test and operate bit int test_and_set_bit (nr,void * addr); int test_and_clear_bit (nr,void * addr); int test_and_change_bit (nr,void * addr)

Spin lock

It means "spin in place". When the lock is not successful, spin, spin lock will continue to occupy CPU for variable testing, because it is an atomic operation, so the occupation of the CPU will rise to 100%. Therefore, when using spin lock, the code in the critical area needs to be very short, otherwise it will affect the system performance. in addition, as a kind of locking mechanism, the use of spin lock also needs to pay attention to the occurrence of deadlock. Functions that may cause process scheduling cannot be called during spin locking. If the process acquires the spin lock and then blocks, eg,copy_from_user (), copy_to_user (), kmalloc (), msleep (), etc., once blocking occurs, it may cause the kernel to crash.

Spin lock can be used to solve the SMP race problem. Different types of spin locks have their own processing mechanisms, which are suitable for different situations. It includes traditional spin lock, read-write spin lock, RCU mechanism, sequence lock and so on. Spin lock is the underlying implementation tool of semaphore and mutex.

Compare\ type traditional spin lock read write spin lock sequence lock RCU mechanism applications need lock exclusive resources need writer exclusive resources read more read write less resources read more read and write less resources + read and write parallel × √√√ read and write concurrent × × √√ write + write concurrent × × √

As with other locking mechanisms, using spin locks to protect data is divided into preemptive locking-operation-unlocking. The following is a typical process of using locks, through which a file is opened by only one process.

Int cnt=0; lock_t lock;static int my_open () {lock (& lock); if (cnt) {unlock (& lock)} cnt++; unlock (& lock);} static int release () {lock (& lock); cnt--; unlock (& lock);}

Traditional spin lock

Is a relatively rough spin lock, when using this lock, the locked critical area does not allow other CPU access. It should be noted that although the critical section operation performed after obtaining the lock will not be disturbed by other CPU and other preemptive processes in this CPU, it will still be interrupted and affected by the bottom half, so we usually use the derivative version of the following API For example, spin lock + interrupt mask is mentioned above to prevent interruption when using spin lock to access critical resources, and the corresponding macro functions are spin_lock_irq and spin_lock_irqsave.

/ / define and initialize spin lock spinlock_t spinlock void spin_lock_init (spinlock_t *); / / lock / / spin_lock-lock function (busy, etc.) void spin_lock (spinlock_t * lock); int spin_trylock (spinlock_t * lock); spin_lock_irq (); / / = spin_lock () + local_irq_disable () spin_lock_irqsave (); / / = spin_lock () + lock_irq_save (); spin_lock_bh () / / = spin_lock () + local_bh_disable (); / / unlock void spin_unlock (spinlock_t * lock); spin_unlock_irq (); / / = spin_unlock () + local_irq_enable () spin_unlock_irqrestore (); / / = spin_unlock () + lock_irq_restore (); spin_unlock_bh (); / / = spin_unlock () + local_bh_enable ()

Read-write spin lock

Traditional spin locks roughly assign critical resources to a CPU, but many resources will not be destroyed by reading, so we can allow multiple CPU to read critical resources at the same time, but not to write resources at the same time, similar to file locks in the application layer. The kernel read-write locking mechanism also has the following mutual exclusion principle:

Readers + readers do not repel each other

Reader + writer mutually exclusive

Writer + writer mutually exclusive

/ / include/linux/rwlock.h / / define and initialize spin lock rwlock_t rwlock; void rwlock_init (rwlock_t * lock); / / add read lock void read_lock (rwlock_t * lock); int read_trylock (rwlock_t * lock); void read_lock_irqsave (rwlock_t * lock,unsigned long flags); void read_lock_irq (rwlock_t * lock,unsigned long flags); void read_lock_bh (rwlock_t * lock) / / decipher lock void read_unlock (rwlock_t * lock) Void read_unlock_irqrestrore (rwlock_t * lock,unsigned long flags); void read_unlock_irq (rwlock_t * lock,unsigned long flags); void read_unlock_bh (rwlock_t * lock); / / write lock void write_lock (rwlock_t * lock); int write_trylock (rwlock_t * lock) Void write_lock_irqsave (rwlock_t * lock,unsigned long flags); void write_lock_irq (rwlock_t * lock,unsigned long flags); void write_lock_bh (rwlock_t * lock); / / unwrite lock void write_unlock (rwlock_t * lock); void write_unlock_irqrestrore (rwlock_t * lock,unsigned long flags); void write_unlock_irq (rwlock_t * lock,unsigned long flags); void write_unlock_bh (rwlock_t * lock)

Sequence lock

The sequential lock can be regarded as an upgraded version of the read-write lock, which does not allow both the reader and the writer to exist at the same time. The sequential lock improves this situation by allowing both the writer and the reader to access the critical area at the same time. The reader no longer has to wait for the writer to finish reading like the read-write lock, and the writer has to wait for the reader to finish reading. However, when using a sequential lock, the critical section cannot have a pointer, because the writer may change the pointer's direction, and if the reader reads it, it will Oops. In addition, if the data that the reader has read is changed by the writer, the reader needs to reread it to maintain that the data is *. Although there are these two constraints, sequential locks provide more flexibility than read-write locks. In the case of writer + writer, the mechanism of sequential lock is the same as read-write lock, which must wait!

Readers + readers do not repel each other

Readers + writers do not repel each other, there is no pointer in the critical area and readers need to pay attention to their own updates.

Writer + writer mutually exclusive

/ / include/linux/seqlock.h / / define sequential locks struct seqlock_t sl;// get sequential locks void write_seqlock (seqlock_t * sl); void write_tryseqlock (seqlock_t * sl); void write_seqlock_irqsave (lock,flags); / / = local_irq_save () + write_seqlock () void write_seqlock_irq (seqlock_t * sl); / / = local_irq_disable () + write_seqlock () void write_seqlock_bh (seqlock_t * sl) / / local_bh_disable () + write_seqlock () / / release sequence lock void write_sequnlock (seqlock_t * sl); void write_sequnlock_irqsave (lock,flags); / / = local_irq_restore () + write_sequnlock () void write_sequnlock_irq (seqlock_t * sl); / / = local_irq_enable () + write_sequnlock () void write_sequnlock_bh (seqlock_t * sl) / / local_bh_enable () + write_sequnlock () / / start reading unsigned read_seqbegin (const seqlock_t * sl); read_seqbegin_irqsave (lock,flags); / / = local_irq_save () + read_seqbegin (); / / reread int read_seqretry (const seqlock_t * sl,unsigned iv); read_seqretry_irqrestore (lock,iv,flags); / / = local_irq_restore () + read_seqretry ()

RCU

RCU is Read-Copy Update, that is, the reader reads directly, and the writer copies first and then updates at the right time. It is another upgraded version of the read-write lock. This mechanism is widely used in the VFS layer. As the name suggests, the reader does not need a lock to access the critical resource. As can be seen from the definition of rcu_read_lock below, the writer backs up the critical resource before writing and modifies the copy. After all CPU exits the reference to this critical section, the original pointer referencing the resource will be directed to the modified backup through the callback mechanism. It can be seen that under the RCU mechanism, the overhead of the reader is greatly reduced, and there is no pointer problem of sequential locks, but the overhead of the writer is very high, so RCU is suitable for critical resources that read more and write less. If there are a lot of write operations, it is possible to offset the performance savings of read operations, and the loss outweighs the gain.

Readers + readers do not repel each other

Readers + writers do not repel each other, and readers pay attention to updates.

Writers + writers do not repel each other, and writers synchronize with each other

The kernel maintains two data structures for each CPU-rcu_data and rcu_bh_data, which are used to hold the callback function, call_rcu () registers the callback function with rcu_data, and call_rcu_bh () registers the callback function with rcu_bh_data. On each data structure, the callback functions form a queue.

When using RCU, the read execution unit must provide a signal to the write execution unit so that the write execution unit can determine when the data can be safely released or modified. There is a special garbage collector in the kernel to detect the signal of the read execution unit. Once all the read execution units have sent a signal to tell the collector that they do not use the RCU data structure, the collector will call the callback function to complete the data release or modification operation.

Read

Read is the R in RCU. As you can see from the macro definition below, the read operation actually prohibits preemptive scheduling of the kernel and does not use a lock object.

/ / read lock / / include/linux/rcupdate.h rcu_read_lock (); / / preempt_disbale () rcu_read_lock_bh (); / / local_bh_disable () / / read unlock rcu_read_unlock () / / preempt_enable () rcu_read_unlock_bh (); / / local_bh_enable ()

Synchronization

Synchronization is a step of RCU write operation-Update. The following API will color the write execution unit. Until all read execution units have completed the critical section of the read execution unit, the write execution unit can proceed to the next step. If multiple RCU write execution units call this function, they will all be awakened after a grace period (that is, all read execution units have finished accessing the critical section).

Synchrosize_rcu ()

Suspend callback

The following interface, also called by the RCU write execution unit, does not block the write execution unit, so it can be used in an interrupt context or soft interrupt, which hangs the func on the RCU callback function chain and returns immediately. The function sychrosize_rcu () actually calls call_rcu () as well.

Void call_rcu (struct rcu_head * head,void (* func) (struct rcu_head * rcu))

The following interface treats the completion of the soft interrupt as experiencing a quiecent state (silent state), so if the write execution unit calls this function, the read execution unit in the process context must use rcu_read_lock_bh ()

Void call_rcu_bh (struct rcu_head * head,void (* func) (struct rcu_head * rcu))

The RCU mechanism is widely used in reading and writing kernel linked lists. The following are the data structures protected by the RCU mechanism in the kernel. The function of the function is the same as the non-RCU version. You can refer to the kernel file "include/linux/list.h" for details, but all operations here are protected by RCU.

Void list_add_rcu (struct list_head * new,struct list_head * head); void list_add_tail_rcu (struct list_head * new,struct list_head * head); void list_del_rcu (struct list_head * entry); void list_replace_rcu (struct list_head * old,struct list_head * new); list_for_each_rcu (pos,head); list_for_each_safe_rcu (pos,n,head); list_for_each_entry_rcu (pos,head,member) Void hlist_del_rcu (struct hlist_node * n); void hlist_add_head_rcu (struct hlist_node * n, struct hlist_head * h); list_for_each_rcu (pos,head); hlist_for_each_entry_rcu (tpos,pos,head,member)

Semaphore

As mentioned in the spin lock section, if a CPU does not have access to critical resources, it will cause "spin in place", so the implementation time of the critical region of spin lock protection should not be too long, but what if we do need to protect a critical region that takes a long time to execute? The answer is semaphores.

The underlying layer of the semaphore relies on the spin lock to achieve its atomicity, and further enhances it to the dimension of the "process", which is called a "lock" that can be run in the process context. it is this ability to run in the process context that gives semaphores and spin locks many differences.

With semaphores, if the process trying to get the semaphore fails to get it, the kernel will schedule it to sleep and execute other processes, avoiding CPU busyness, and so on. However, process context switching also comes at a cost, so semaphores are usually used only to protect large critical areas in the kernel.

In addition, a process will go to sleep once it is unable to get the expected semaphore, so the critical area protected by the semaphore can have a sleep code. In this respect, the area protected by the spin lock cannot sleep or perform schedule (), because once a CPU that grabs the lock switches or sleeps the process context, the other CPU waiting for the spin lock will be busy waiting there and will never be able to wait for the lock to form a deadlock unless some other process wakes it up (usually not).

It is also because semaphore operations can cause blocking, semaphores cannot be used to interrupt the context. To sum up the wordy paragraph just now:

Project semaphore spin lock critical zone time process switching time shorter critical zone execution time shorter process context critical area can sleep or schedule critical area can not sleep or schedule interrupt context only down_trylock () can

Traditional semaphore

Kernel semaphores are used in a similar way to application layer semaphores, but there is no step of getting semaphores, because semaphores in the kernel can be mapped to the kernel space of all user processes that call this module. These user processes directly share a semaphore, so they do not get a semaphore, which I discuss in the article "Linux IPC System V semaphore".

Like application layer semaphores, kernel semaphores are also used for mutex / sequential access to critical resources. Similarly, although we can initialize to any value when using semaphores, in practice we usually only initialize them to 1 or 0. The following is the semaphore API provided by the Linux kernel.

/ / include/linux/semaphore.h / / define and initialize the semaphore object struct semphore sem;// initialization semaphore void sem_init (struct semaphore * sem,int val); init_MUTEX (sem); init_MUTEX_LOCKED (sem); DECLARE_MUTEX (sem); DECLARE_MUTEX_LOCKED (sem); / / P operation / / down () causes sleep and cannot be used to interrupt context void down (struct semaphore * sem) / / down_interruptible will also go into hibernation, but can be interrupted by int down_interruptible (struct semaphore * sem); / / down_trylock will return immediately when the lock cannot be obtained, will not sleep, and can be used in the interrupt context int down_trylock (struct semaphore * sem); / / V operation void up (struct semaphore * sem)

Read-write semaphore

The relationship between read-write semaphores and semaphores is similar to that between read-write spin locks and spin locks. Their mutually exclusive logic is the same. I will not repeat them here.

/ define and initialize read / write semaphores struct rw_semaphore my_rwsem; void init_rwsem (struct rw_semaphore * sem); / / P read semaphores void down_read (struct rw_semaphore * sem); int down_read_trylock (struct rw_semaphore * sem); / / V read semaphores void up_read (struct rw_semaphore * sem); / / P write semaphores void down_write (struct rw_semaphore * sem); int down_write_trylock (struct rw_semaphore * semaphores) / / V write semaphore void up_write (struct rw_semaphore * sem)

Template

Struct rw_semaphore my_rwsem; void init_rwsem (& my_rwsem); / / get read semaphore down_read (& my_rwsem) before reading; / / for non-blocking: down_read_trylock (& my_rwsem); / * read critical area * / / release read semaphore up_read (& my_rwsem) after reading; / / get letter number down_write (& my_rwsem) before writing / / for non-blocking: down_write_trylock (& my_rwsem); / * write critical section * / release write semaphore up_write (& my_rwsem)

Completion quantity

The completion amount is used for one execution unit to wait for another execution unit to finish something, which, like the traditional semaphore, is mainly used to achieve sequential / mutually exclusive access to the critical area of the team. But completion also provides an interface to wake up one or all waiting processes, somewhat similar to the conditional variables in the application layer.

/ define and initialize completion struct completion my_completion; init_completion (& my_completion); / or DECLARE_COMPLETION (my_completion) / / wait completionvoid wait_for_completion (struct completion * c); / / Wake up completionvoid complete (struct completion * c); / / Wake up only one waiting execution unit void complete_all (struct completion * c); / / release all execution units waiting for this completion amount

Repulsive body

In addition to semaphores, the Linux kernel also provides a special mechanism for implementing mutexes-mutexes. The related kernel API is as follows:

/ / include/linux/mutex.h / / define and initialize mutex object struct mutex my_mutex; mutex_init (& my_mutex); / / get mutexvoid mutex_lock (struct mutex * lock); int mutex_trylock (struct mutex * lock); int mutex_lock_interruptible (struct mutex * lock); / / release mutexvoid mutex_unlock (struct mutex * lock). At this point, I believe you have a better understanding of "Linux concurrency control technology". Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.