Detailed explanation of the RCU mechanism in the Linux kernel

The Linux kernel is a complex system that needs to deal with a variety of concurrency issues, such as process scheduling, memory management, device drivers, network protocols, etc. In order to ensure the consistency and correctness of data, the Linux kernel provides a variety of synchronization mechanisms, such as spin locks, semaphores, read-write locks, etc. However, these synchronization mechanisms have some shortcomings, such as:

• Spin locks will cause the CPU to waste time in busy waiting, and cannot be used in preemptive kernels;
• Semaphore will cause the process to sleep and wake up, increasing the overhead of context switching;
• Read-write locks will cause writer starvation or reader starvation, and when there are more readers than writers, the writer will also have to pay the overhead of acquiring the lock.

So, is there a better synchronization mechanism? The answer is yes, that is RCU (Read Copy Update). RCU is a synchronization mechanism based on the publish-subscribe model, which can achieve efficient read operations and low-latency update operations. The basic idea of ​​RCU is this:

• The read operation does not need to acquire any locks, and only needs to use rcu_read_lock() and rcu_read_unlock() to mark the critical area;
• The update operation requires first creating a copy of the data, making modifications on the copy, then using rcu_assign_pointer() to publish the new data, and using call_rcu() or synchronize_rcu() to wait for all read operations to be completed before recycling the old data.

What are the advantages of RCU? It has the following characteristics:

• RCU can reduce lock competition and context switching, and improve the concurrency performance and responsiveness of the system;
• RCU can avoid problems such as deadlock and priority inversion, simplifying the programming model;
• RCU can adapt to different scenarios, such as real-time systems, NUMA systems, SMP systems, etc.;
• RCU can be used in conjunction with other synchronization mechanisms, such as spin locks, atomic operations, etc.

So, how does RCU work? What application scenarios does it have? This article will introduce the efficient synchronization mechanism of RCU from two aspects: principle and application. The design idea of ​​RCU is relatively clear, and lock-free sharing protection is achieved by replacing old and new pointers. But when it comes to the code level, it is still somewhat difficult to understand. In Chapter 4 of "In-depth Linux Device Driver Kernel Mechanism", the rules followed behind RCU have been very clearly described. These rules are viewed from a relatively high perspective, because I think too much code analysis is easy. Let the reader get lost in the details. After I got the book recently, I carefully read the text in the RCU part again, and felt that I should add a little more content, because some things may not be suitable to be written in the book.

The sign that the RCU reading side enters the critical section is to call rcu_read_lock. The code of this function is:

1. 
2. static inline void rcu_read_lock(void)
3. {
4. ​    __rcu_read_lock();
5. ​    __acquire(RCU);
6. ​    rcu_read_acquire();
7. }

There seem to be three function calls in this implementation, but the actual work is done by the first function __rcu_read_lock(). __rcu_read_lock() turns off kernel preemptibility by calling preempt_disable(). But interrupts are allowed. Assume that the reader is in the rcu critical section and has just read a pointer p in the shared data area (but has not yet accessed the data members in p). An interrupt occurs, and the interrupt handling example The ISR happens to need to modify the data area pointed to by p. According to the design principles of RCU, the ISR will newly allocate a data area new_p of the same size, and then copy the data in the old data area p to the new data area, and then in new_p Basically do the data modification work (because it is modified in the new_p space, there is no concurrent access to p, so RCU is a lock-free mechanism, and this is the reason), after the ISR completes the data update work , assign new_p to p (p=new_p), and finally it will register a callback function to release the old pointer p at the appropriate time. Therefore, as long as all references to the old pointer p are over, there is no problem in releasing p. When the interrupt handling routine returns from completing these tasks, the interrupted process will still access the data in the p space, that is, the old data. This result is allowed by the RCU mechanism. RCU rules allow temporary resource view inconsistencies caused by pointer switching between readers and writers.

The next interesting question about RCU is: when can the old pointer be released. The answer to this I've seen in many books is: when a process switch occurs on all processors in the system. This stylized answer often confuses readers who are new to the RCU mechanism. Why do we have to wait for a process switch to occur on all processors before calling the callback function to release the old pointer? This is actually determined by the design rules of RCU: All references to old pointers can only occur in the critical section included by rcu_read_lock and rcu_read_unlock, and process switching is not possible in this critical section, Once the critical section is out of the critical section, there should no longer be any form of reference to the old pointer p. Obviously, this rule requires that the reader cannot switch processes in the critical section, because once there is a process switch, the callback function that releases the old pointer may be called, causing the old pointer to be released. When the switched process When it is rescheduled, it may reference a freed memory space.

Now we see why rcu_read_lock only needs to turn off kernel preemptibility, because it makes it impossible for the current process to be switched and removed even if an interrupt occurs in the critical section. Kernel developers, or rather, RCU designers, can only do so much. The next step is the responsibility of the user. If a function is called in the critical section of RCU, the function may sleep, then the design rules of RCU will be violated and the system will enter an unstable state.

This once again shows that if you want to use something, you must understand its inner mechanism. Like the example just mentioned above, even if there are no problems with the program now, the hidden dangers left in the system are like a time bomb. It can be detonated at any time, especially if the problem suddenly breaks out after a long time. In most cases, the time it takes to find the problem may be much longer than it takes to calm down and carefully understand the principles of RCU.

Readers in RCU have a higher degree of freedom than readers in rwlock. Because the RCU reader does not need to consider the writer's feelings when accessing a shared resource, this is different from the rwlock writer. The rwlock reader needs to ensure that no writer is operating the resource when reading the shared resource. The difference between the two comes from RCU's separation of shared resources between readers and writers, while rwlock's readers and writers only use shared resources from beginning to end. One copy. This also means that writers in RCU have to bear more responsibilities, and some kind of mutual exclusion mechanism must be introduced between multiple writers who update the same shared resource, so RCU is a "lock-free mechanism" The statement is limited to readers and writers. So we see that the RCU mechanism should be used in situations where there are a large number of read operations and relatively few update operations. At this time, RCU can greatly improve the system performance, because RCU's read operation has almost no lock overhead compared to some other locking mechanisms.

In actual use, shared resources often exist in the form of linked lists. The kernel implements several interface functions for linked list operations in RCU mode. Readers and users should use these kernel functions, such as list_add_tail_rcu, list_add_rcu, hlist_replace_rcu Etc. For specific usage, please refer to some kernel programming or device driver information.

In terms of releasing old pointers, the Linux kernel provides two methods for users to use, one is to call call_rcu, and the other is to call synchronize_rcu. The former is an asynchronous method. call_rcu will put the callback function that releases the old pointer into a node, and then add the node to the local linked list of the processor currently running call_rcu. In the softirq part of the clock interrupt (RCU_SOFTIRQ ), the rcu soft interrupt processing function rcu_process_callbacks will check whether the current processor has experienced a sleep period (quiescent, which involves kernel process scheduling and other aspects). The kernel code implementation of rcu determines that all processors in the system have experienced After a sleep period (meaning that a process switch has occurred on all processors, so the old pointer can be safely released at this time), the callback function provided by call_rcu will be called.
The implementation of synchronize_rcu makes use of the waiting queue. During its implementation, it also adds a node to the local linked list of the current processor like call_rcu. The difference from call_rcu is that the callback function in this node is wakeme_after_rcu, and then synchronize_rcu will sleep in a waiting queue until a process switch occurs on all processors in the system, so wakeme_after_rcu is called by rcu_process_callbacks to wake up the sleeping synchronize_rcu. After being awakened, synchronize_rcu knows that it can now release the old pointer.

So we see that the registered callback function may not have been called after call_rcu returns, which means that the old pointer has not been released, and the old pointer must have been released after synchronize_rcu returns. Therefore, whether to call call_rcu or synchronize_rcu depends on the specific needs and the current context. For example, the synchronize_rcu function cannot be used in the context of interrupt processing.

This article introduces RCU, an efficient synchronization mechanism in the Linux kernel. It is a synchronization mechanism based on the publish-subscribe model. We analyzed the basic ideas, key interfaces and implementation details of RCU from the principle aspect, and gave corresponding code examples. We also introduced the use of RCU in linked list operations, timer management, soft interrupt processing and other scenarios from the application perspective, and gave corresponding code examples. By studying this article, we can master the basic usage of RCU, and be able to flexibly use RCU in actual development to achieve efficient synchronization requirements. Hope this article is helpful to you!

The above is the detailed content of Detailed explanation of the RCU mechanism in the Linux kernel. For more information, please follow other related articles on the PHP Chinese website!