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

How to predict the deadlock problem of read-write locks, many novices are not very clear about this. In order to help you solve this problem, the following editor will explain it in detail. People with this need can come and learn. I hope you can get something.

1. Deadlock (Deadlock)

Deadlocks are not uncommon in daily life. People living in big cities have more or less experienced the scene shown in the following picture. What happens at a roundabout or at an intersection is a deadlock. Maybe some of the cars broke down, but most of the cars are runnable. But because every car has to wait for the car in front to move before it can move, none of the cars can move, or, more generally, they can't Make Forward Progress. The reason for this is that the waiting of the vehicle forms a cycle in which each car is waiting for the car ahead, so none of the cars can wait for what they have to wait for. This kind of vehicle deadlock will continue to worsen and have serious consequences: first, it will cause traffic jams at intersections, and if the congestion is further expanded, it will lead to a large area of traffic paralysis. Vehicle deadlock is very difficult to heal itself, and it is very difficult or takes a long time to get out of the deadlock by itself, which can only be solved by manual intervention (such as traffic police).

Figure 1: traffic jam on the road around the island (picture from the network)

Deadlocks can also occur in multithreaded or distributed system programs. Its essence is the same as the traffic jam at the above intersection, because the participants constitute a cycle of waiting, so that all participants can not wait for the desired results, so that they can never make progress there. Of course, deadlocks can occur in the Linux kernel, and if the Core, such as the scheduler and memory management, or subsystems, such as the file system, deadlocks occur, the entire system will become unavailable.

The deadlock is random. Just like the situation around the island in the picture above, the ring is there and deadlocks don't happen all the time. But around the island itself is a deadlock hidden danger, especially in the traffic pressure is relatively high, the island will be more likely to produce deadlock. It would be much better if this kind of intersection was designed as traffic lights, and it would be much better if it was designed and set up. In the program, we call the scenarios where deadlocks may occur as potential deadlocks (Potential Deadlock Scenario), and the deadlocks that are about to occur or are occurring are called deadlock instances (Concrete Deadlock).

How to deal with deadlock has always been an active research and solution problem in academic and application fields. The solution to deadlock can be roughly divided into: deadlock discovery (Detection), deadlock avoidance (Prevention) and deadlock prediction (Prediction). Deadlock discovery refers to the discovery of deadlock instances in the running of the program, deadlock avoidance is to further prevent the instance when it is about to be generated, and deadlock prediction is to find out the potential deadlocks in the program through static or dynamic methods. so as to fundamentally eliminate the hidden danger of deadlock.

two。 Deadlock and Lockdep of lock

In deadlocks, deadlocks caused by improper use of locks (Lock) are an important source of deadlocks. Lock is one of the main means of synchronization, and it is inevitable to use lock. For complex synchronization relationships, the use of locks can be more complex. It is easy to cause a deadlock if it is not used properly. From a waiting point of view, the deadlock of a lock is due to the participating thread waiting for the lock to be released, which constitutes a waiting loop, such as an ABBA deadlock:

Figure 2: two-thread ABBA deadlock

Where the black arrow in the thread represents the current execution statement of the thread, and the red arrow indicates the wait relationship between the thread statements. As you can see, the red arrows form a circle (or loop). Once again, looking back at the potential deadlock and deadlock instances, it is very likely that if the execution time of these two threads changes slightly, the deadlock instance will not occur, for example, if you let Thread1 finish executing this piece of code before Thread2 starts execution. But such a locking behavior (Locking Behavior) is undoubtedly a potential deadlock.

It can be further seen that if we can track and analyze the locking behavior of the program, it is possible to predict deadlocks or identify potential deadlocks, rather than waiting for deadlocks to occur before deadlock instances can be detected. The Lockdep tool of the Linux kernel is to depict the lock behavior of the kernel to predict potential deadlocks and report them.

Lockdep can describe the behavior of a class of locks (Lock Class), mainly by recording the locking order (Locking Order) of all lock instances in a class of locks, that is, if a thread holds lock An and takes lock B before it is released, then lock An and lock B have a locking order of A-> B. in Lockdep, this locking order is called Lock Dependency. Similarly, for ABBA-type deadlocks, we do not need Thread1 and Thread2 to generate just a deadlock instance. As long as a thread produces a locking order behavior of A-> B, and another thread produces a locking sequence behavior of B-> A, then this constitutes a potential deadlock, as shown in the following figure:

Figure 3: thread ABBA locking sequence

As a result, we can record and save all locking sequences (that is, lock dependencies) to form a locking sequence diagram (Graph). If there is a lock dependency A-> B and a lock dependency B-> C, then because the lock dependency (Relation) is Transitive, we can also get the lock dependency A-> C. A-> B and B-> C are called Direct Dependency, while A-> C is called Indirect Dependency. For each new direct lock dependency, we check to see if the dependency forms a loop with the lock dependency that already exists in the diagram, and if so, we can predict a potential deadlock.

3. Read-write lock (Read-write Lock)

The locks we referred to just now are all Exclusive Lock. A read-write lock is a more complex lock, or a universal lock (General Lock), and we can think of a mutex as a read-write lock that only uses write locks. As long as there is no write lock or write lock scramble, the read lock allows the Reader to hold it at the same time. There are many kinds of read-write locks in the Linux kernel, including rwsem, rwlock, qrwlock and so on. The problem is that read-write locks make deadlock prediction extremely complex, and Lockdep cannot support these read-write locks, so Lockdep will produce some related false false positive (False Positive) deadlock prediction and false false negative (False Negative) deadlock prediction during use. This problem has existed for more than 10 years. We propose a general deadlock prediction algorithm for locks and prove that this algorithm can solve the deadlock prediction problem of read-write locks.

4. Deadlock Prediction algorithm for Universal Lock (General Deadlock Prediction For Locks)

In the process of describing this algorithm, we propose several Lemma to explain or prove the effectiveness of our proposed deadlock prediction.

▍ Lemma 1: after the introduction of read-write locks, the locking sequence cycle of locks is a necessary condition, but not a sufficient condition, for potential deadlocks. Moreover, a potential deadlock can and can only be predicted at the earliest when the last locking order (or lock dependency) is about to generate a deadlock loop.

Based on Lemma 1, to solve the deadlock prediction problem is to calculate whether the waiting ring constitutes a potential deadlock by some method when the last lock sequence (that is, lock dependency) forms a waiting ring (loop). And our task is to find this method (algorithm).

▍ Lemma 2: two virtual threads T1 and T2 can be used to represent all deadlock scenarios.

For any deadlock instance, suppose there are n threads participating in the deadlock instance, and the n threads are represented as:

T1, T2, … , Tn

Consider the case of n:

If Recursion Deadlock 1: this kind of deadlock means that the thread waits for itself, which is called a recursive deadlock in Lockdep. Because it is easy to check for this deadlock, this special case is ignored in the algorithm below. If n > 1: this kind of deadlock is called Inversion Deadlock in Lockdep. For this case, we divide the n threads into two groups, that is, T1, T2, T2, … , Tn-1 and Tn, and then merge all the lock dependencies in the previous group and assume that all of these dependencies exist in a virtual thread, resulting in two virtual threads T1 and T2.

These are the two virtual threads described in Lemma 2. Based on Lemma 2, we propose a deadlock checking two-thread model (Two-Thread Model) to represent the locking behavior of the kernel:

T1: currently checks all lock dependencies before lock dependencies, which form a lock dependency graph. T2: the current direct lock dependency to be checked.

Based on Lemma 2 and the two-thread model of deadlock checking, we can get the following Lemma:

▍ Lemma 3: any deadlock can be converted to an ABBA type.

Based on the above three lemmas, we can further describe the deadlock prediction problem as: when we get a new direct lock dependency B-> A, we assume that the new dependency is T2. All the previous lock dependencies exist in a lock dependency graph generated by an imagined T1, so deadlock prediction is to check whether there is a lock dependency of A-> B in T1, and if so, there is a deadlock. Otherwise, there is no deadlock and T2 is merged into T1. As shown in the following figure:

Lock dependency of graph 4:T1 and direct lock dependency of T2

After the introduction of read-write locks, lock dependencies also depend on the type of lock in it, that is, the read or write type. According to the design characteristics of mutex lock and read-write lock in Linux kernel, we introduce a lock mutex table to represent the mutex relationship between locks:

Table 1: read-write lock mutex table

Among them, the recursive read lock (Recursive-read Lock) is a special read lock, which can be held recursively by the same thread. Let's first propose a simple algorithm (Simple Algorithm). Based on the dual-threaded model, given T1 and T2, and ABBA locks:

Figure 5: simple algorithm based on dual-threaded model

The steps of the simple algorithm are as follows:

If X1.An and X1.B are mutually exclusive and X2.An and X2.B are mutually exclusive, then T1 and T2 constitute a potential deadlock.

Otherwise, T1 and T2 do not constitute a potential deadlock.

From the simple algorithm, we can see that the lock type determines the mutex relationship between locks, and the mutex relationship is the key information to check deadlocks. For read-write locks, lock types may change during program execution, so how do you record all lock types? We are based on the mutual exclusion of lock types, that is, the mutual exclusion of lock types from low to high: recursive read locks

< 读锁 < 写锁（互斥锁），提出了锁类型的升级（Lock Type Promotion）。在程序执行过程中，如果碰到了高互斥性的锁类型，那么我们将锁依赖中的锁类型升级到高互斥性的锁依赖。锁类型升级如图所示： 图6：锁类型的升级 其中 RRn 表示递归读锁n（Recursive-read Lock n） ，Rn表示读锁n（Read Lock n），Wn代表写锁或者互斥锁n（Write Lock n）。下面 Xn 则表示任意锁n （即递归读、读或者写锁）。 但是，如上简单算法并不能处理所有的死锁预测情况，比如下面这个案例就会躲过简单算法，但事实上它是一个潜在死锁： 图7：简单算法失败案例 在这个案例中， X1 和 X3 是互斥的从而这个案例构成了潜在死锁。但是简单算法在检查 RR2->

In the case of X1 (that is, T2 is RR2- > X1), X1-> RR2 can be found in T1 according to a simple algorithm, but because RR and RR are not mutually exclusive, it is mistakenly determined that this case is not a deadlock. The reason for the wrong conclusion in this case is that X3-> X1 in the real deadlock X1X3X3X1 is an indirect lock dependency, which is omitted by a simple algorithm.

The deeper reason for this problem is that there is only mutex between mutexes, so as long as there is an ABBA, it is a potential deadlock, and there is no need to check T2 indirect lock dependencies. In the case of read lock, this condition no longer exists, so it is necessary to consider the indirect lock dependency in T2.

▍ Lemma 4: for indirect lock dependencies introduced by direct lock dependencies, if indirect lock dependencies constitute deadlocks, then direct lock dependencies are still critical.

Lemma 4 is an extension of Lemma 1. According to Lemma 1, this direct lock dependency must be the last lock dependency that forms the lock loop, and Lemma 4 shows that through this lock dependency, we can determine whether the lock loop is a potential deadlock in some way. In other words, by modifying and strengthening the simple algorithm proposed earlier, the new algorithm will certainly be able to solve this problem. But the question is, the direct lock dependency in T2 may have further generated a lot of indirect lock dependency. how can we find the indirect lock dependency that eventually produces a potential deadlock? Further, we first need to redefine T2, and then find out all the indirect lock dependencies in this T2, so what is the boundary of T2? If T2 is extended to the entire lock dependency graph, the complexity of the algorithm will be greatly increased and may even exceed the processing power of Lockdep, making Lockdep virtually unavailable.

The ▍ Lemma 5:T2 only needs to be extended to the Lock Stack of the current thread.

According to Lemma 5, we first modify the previously proposed two-threaded model as follows:

T1: currently checks all lock dependencies before direct lock dependencies, which form a graph. T2: the lock stack of the current thread to be checked.

According to Lemma 5 and the new dual-threading model, we propose the following final algorithm (Final Algorithm) on the basis of a simple algorithm:

Continue to search the lock dependency graph, T1, for a new lock dependency loop. In this new loop, if there are other locks in T2, then this lock and the direct lock dependency in T2 constitute an indirect lock dependency and check whether the indirect lock dependency constitutes a potential deadlock. If a potential deadlock is found, the algorithm ends, if it does not go to 1 until the entire lock dependency graph is searched.

Can this final algorithm solve previous cases of vulnerabilities? The answer is yes, the specific inspection process is shown in the figure:

Figure 8: failure case resolution process of a simple algorithm

However, for all other cases, is Lemma 5 correct? Why does the final algorithm work? We prove that the indirect lock dependency in the final algorithm is necessary and sufficient through the following two lemmas.

▍ Lemma 6: it is necessary to check for indirect lock dependencies in T2, otherwise the simple algorithm has solved all the problems.

Lemma 6 states that because of the existence of read-write locks, you can't just check for direct lock dependencies.

It is sufficient that the boundary of the ▍ Lemma 7:T2 is the lock stack of the current thread.

According to Lemma 2 and Lemma 3, any deadlock can be converted into a dual-threaded ABBA deadlock, and T1 can only contribute AB,T2 must contribute BA. Here, T2 is not only a virtual thread, but also an actual physical thread, so T2 needs and only needs to check the current thread.

At this point, the description of a general read-write lock deadlock prediction algorithm is not formally proved.

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

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.