Cloud Native Computing Foundation KubeCon + CloudNativeCon China 2019 (Shanghai), 5 Jul 2019

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Recursive Read Deadlocks and Where to Find Them - Boqun Feng, Huawei

Description

Join us for Kubernetes Forums Seoul, Sydney, Bengaluru and Delhi - learn more at kubecon.io

Don't miss KubeCon + CloudNativeCon 2020 events in Amsterdam March 30 - April 2, Shanghai July 28-30 and Boston November 17-20! Learn more at kubecon.io. The conference features presentations from developers and end users of Kubernetes, Prometheus, Envoy, and all of the other CNCF-hosted projects

Recursive Read Deadlocks and Where to Find Them - Boqun Feng, Huawei

Lockdep (the deadlock detector in the Linux kernel) is a powerful tool to detect deadlocks, and has been used for a long time by kernel developers. However, when comes to read/write lock deadlock detections, lockdep only has limited support. Another thing makes this limited support worse is some major architectures (x86 and arm64) has switched or is trying to switch its rwlock implementation to queued rwlock. One example is we found some deadlock cases that happened in kernel but we could not detect it with lockdep. To improve this situation, a patchset to support read/write deadlock detection in lockdep has been post to lkml and got to its v6. This topic will give a brief introduction on rwlock related deadlocks (recursive read deadlocks) and how we can tweak lockdep to detect them. It will focus on the detection algorithm and its correctness, but also some implementation details.

https://sched.co/NruT

A

Okay, gotten him from watching from highway today like to talk about and recursive readout logs and where to find them.

A

This topic is I've been informative and Tans limited, so first go through their background and some of the information I would like to assume that you are all aware of it and if you have questions, then you're welcome to approach me privately after this session, and then today, I would like to talk about several topics: the logged app and where to find that log and how to assess it and what I do based on locked up. And how can we detect lock death? How can we detect that lock? First, pretty simple dialogue.

A

Let's give this part since, basically, if it's involved in the it's it's relevant with deadlock and self deadlock and abpa deadlock.

B

A

The lower right corner, what we see here- I'm gonna- assume that you understand it.

A

Personally, a and B are in the locker status unable to proceed. Nbpa can be expanded into three that lock sequence and also.

A

There are some dead logs relevant with interrupts, so basically we can assume that's an expansion or scaling off Appa and stop that lock and for trying to solve it. That log.

B

A

Matter the code, if there is that lock, then.

A

We will find a specific combination of codes and interrupt. We increase the possibility of deadlock code occurrence well,.

A

If you have I hope you enabled context, and you drop the ABP a deadlock, then there is a deadlock. P0 r AQ is enabled and there's a spin lock a and there's a lock handler. Then they will handle lock, B but lock.

A

B is locked and in turn that will spin lock a and then there is a deadlock and it will be expanded to a 3 that lock chain lock that what is it locked up is a that lock assessing tools and it's a self equipped tools in the kernel and still up around 2000, and it tried to minimize the occurrence of code in deadlock and they will check clarify. They were classified different categories of that logs and there is a concept, a lock dependency to the right.

A

You can see p0 if there is a spin lock, a and spin lock B, then we'll assume that a TP there is a lot of dependence based on the dependence. Then we will have a dependency graph. It's pretty simple, it's pretty straightforward.

A

We see the rock dependency graph. It's there. Any ring lay out if there is a ring in the lock dependency graph, and that will be a BPA. That lock then.

B

A

B

A

It's likely to appear the lock dependency graph.

A

It's gonna have this code.

B

A

This case is a typical debt law case.

B

A

Here, I won't go into great details if you're interested then you're more than welcome to do more research. The condition of that lock.

B

A

Other cases it's all spin lock and in curl there there are some other cases, the lock that are dealing with it like the following. Well, first, let's focus in locked up so to River lock what is recursive we're a lock, unfavorable right, lock and the yellow the yellow arrow is.

B

A

B

The time progresses.

A

W1 writer, one in red, that means they won't get the lock.

A

Next, we have our two reader too, and they get the lock. And if it's like this, then it's a non common, rare lock. We have writers keep coming that the other one would not get the lock. It sounds fair and the writer will be very hungry and it's not very good, and so all the real log is fair. We rewrite lock. So these are two cases, so the yellow arrow is that, where the time progress forward and.

A

Or two won't get the lock.

B

A

W1 will have high priority on getting the lock if it's like. What's to the right, if we didn't have the writer, then our two can get the lock. So it's a river lock different from the previous deadlock, the reader catalog, and if there is any writer there's, no other writer than the rest of the reader can also get the lock. So there's the difference. So we can summarized in this graph saying that the recursive a lock or that lock they will have multiple readers and they were allowed recursive reader.

B

A

Have a critical zone: one reader will not block the other readers and for a non recursive, his Rivera lock, and also they were allowed multiple readers, but they were not allowed. Recursive CS it's code, non recursive, obviously, and the non recursive reader will blocks other reader and they will have a signal.

A

This one here you can see the r-1, sometimes not an out locking r2, but sometimes our one when they get the lock, will block r2 with our one now getting lock or two will not get the lock as well.

B

A

R1 will flock r2 with non-relevant writers, so that's what we caught. One writer can plug other writers. One reader can plot our readers, so this is the condition of blocking a differentiating, different cases.

B

Different scenarios so.

A

Spin lock can be consider as the scenarios the only writers exist. So if we view this graphic horizontally, the recursive reader, they will now block any other readers, whether it's recursive or not, and.

B

A

Recursive reader, we now block other readers, guess it's recursive and it will block writers and the non recursive not number, no matters, reader or writer. Oh well. First from recursive aspects, they were not allowed CSI and the writer is non recursive, lock the non recursive novelist reader writer. They would block other reader and also other writer.

A

This is the block condition.

A

And starting from here.

A

This is what we call it.

B

A

We say this river lock is a non recursive ray log. Then.

B

A

We're not focusing on p2 but also p0 p1, then it's like the previous example. But if we want to trigger this that lock, then we need p2. If there's no p2 p1, wouldn't they get the B, then they can proceed to a if you're, assessing, detecting any that lock it would have to go through all you have to rule out all the possibilities of that lock.

A

If we got if the codes have p0 and p1, then there's still the possibility of not being a deadlock and.

B

A

It's a recursive lock, then. Obviously, this is not a deadlock. A recursive lock will not be blocked by another reader and.

A

If they have a p2, then p1 will still have to be I spin. This can still get the lock. This is none deadlock and the lock gap graph can be changed to this and a tip Ian BJ there's a ring, and it's not that lock.

B

A

This one, this is that lock itself and the writer will be blocked by reader. The read lock will be blocked by p0 and because it's a ring layout, then we can see that here B to a is the ww.

A

This is not the initial lock visa right, lock and a is also a write. Log and p1 that's the case, so they have the same struct. But categories is different. One is that lock, if the other is not so.

B

A

Same struct, they might have different categories of lock.

A

Sometimes it is determined as the dialogue, sometimes it it is that and.

B

A

A

Non-Recursive root lock.

B

A

If it's in the RQ context, it's a recursive deadlock, they guarantee that had to guarantee that the handler can get luck and exceed ASAP, and it's a famous that mark example. It's pretty special, and this is that log example. This is read lock.

B

A

Is a bit different to the upper-right corner? It's a recursive that lock the green pit and the other way lock is non recursive.

A

This is a that log and that lock a if p0 get to be and p1 will not get the B.

A

Because if we have a not relevant readers, then the blocking condition is that the p1 is when the it's getting the P, it's a functional reader lock. If they have writers there, then the writers will first get the lock and then the readers will get the lock, so the p1 read log will they won't be able to get the lock and it's a ring struct.

A

So later we're gonna touch upon that.

B

A

This is a not that lock this. We just reverse the sequence, so we can see p0 cadei p1 get b p0 now once get the B, it is possible, it is accessible. The lock is a recursive.

A

A

They have a p2 right service to de can get the lock. So this is not that lock itself.

B

B

A

A

If you're just assessing the ring that will be missing some of the conditions of the deadlock.

B

A

Need to make several changes first, we have to make sure the existing that lock is working lock. Tab is working and also we had to handle the queue, add a block, and we have to consider the false positive situation, and if we have a false positive detection, then people are not trusting the tool you can miss.

A

Some of the dialogue is ok, but if you report a false positive result, you might lose the trust from the clients you have to guarantee that 2 is trustworthy, the lock that we must rule out the possibility of false positive. So this is very simply about how can we detect recursively rate lock and we classify as follows? First, we consider that we have three categories of lock: first, our reader recursive reader and non-recursive reader and writer.

A

In one dependency, we're gonna have nine combinations three times three, so this is a direct sorting up according to the locked up conditions for a categories, one shared locks read their locks, recursive or not, and exclusive locks, writer, lock or playing Spurlock's and recursive readers and non recursive readers and writers.

A

It's from presented by letters as e and s, erm and recursive reader will be blocked by writers and non recursive. The managed research or writer blocks will be possibly blocked by other readers and other writers. So if we summarized it got the following: graphics, our would be blocked by s and the others. On the other occasion, that will be blocked aspect, as means sheer e means exclusive R means recursive and non recursive and means non recursive.

B

B

A

The dependency where for categories in this regard, so why.

B

A

As our an en er, based on previous conditions and definitions, we can easily understand that and I am saying that for the headed dependency, we only need to determine whether it's sure all exclusive for the tail. We have to determine whether it's Rita, recursive and not recursive,.

B

A

Determine the block on this, we consider LOC dependency. We are actually focusing on first, if we're considering the dependency from A to B, then a will be a lock.

A

What are the conditions it will block and water or other conditions? They will be blocked.

A

B, if we say B can be blocked by the B in PC and then we can scale up.

A

For the codes in the lower right corner, we can come over this graphic from p0. We have a lock dependency. Sw, sorry, my mistake: it should be as an ITP dependency and B to a en dependency.

A

We have to define.

A

A

A

Discover the ring.

A

It's in the following conditions: that means.

C

If this kind of situation happens, the ping is a recursive reader, yes from A to B. The peak occurs in return from.

B

A

B

A generator and.

C

Let's look back on.

B

C

Request cannot be blocked by the non recursive reader, so there's not a strong dependency here.

B

C

You can translate it into codes. It means that.

A

C

Won't press choices a and participate.

B

C

He can still choose to be from A to B.

B

C

Can think about it.

B

C

Other situations there were these occurrence of blocking, so this.

A

C

Strong dependency.

A

C

Have we think it is, can transfer the relationship of the locks.

A

C

Lock condition: it means that the strong dependency chain forms a circle and the metal example. It shows the coda for the right one yeah it has the deadlock because it doesn't have container are at all.

B

C

The we can prove that it is also a deadlock.

C

Yep, you won't get a and P one get the enemy to get C and the system cannot continue.

B

C

Suppose this that lobbies are now recursive, the reader is a non recursive. One.

B

C

B

Also proved it.

C

As I want to prove that there's a kind of a circle- a loop, not a piece on this definition- we establish a dependency graph. If there's a kind of a loop occur happening, so it you acquiesce to the possibility, but it doesn't mean that the deadlock is definitely going to happen, because we only need a very special condition to make it happen to make the dialogue get triggered better faster. We don't allow this possibility.

A

Of dialogue or.

C

Have occur because if it happens, then the system will get start any.

B

Time, yes,.

C

We don't want the deadlock possible.

B

C

That equated to the deadlock possibility so suppose we have a strong dependency within the construct construct example in which the death occurs.

A

C

For the reverse, we can see that the technical.

B

Possibility means that we.

C

Will have this a condition from Circular wait for the circular wait. We can build a little gradually, so there's must be a strong dependency circle.

C

This is for the algorithm, and this is for implementation. We change the look that codes and also PMS it's their codes, so as to make it to implement the strong dependency, and we have done some tests on it. The code is shown in the below yeah. You can check it.

B

C

Is a one good point is that when the locked-up just appears it has its own deadlock test, it's called a QR reader precursor, one yeah.

B

C

I, have it added an algorithm. It is drawn very well.

B

C

Proves that, yes, my implementation algorithm is consistent with the.

A

Previous sauce.

C

Yes, today, my father is a very complex and abstract, but the hope that there's a two points I want to make first.

C

How can we expand that the log dependence a relationship we use the block, condition the wait condition so suppose I have a to lock dependencies yeah, it's easy to find them. If you can have this in the code, then you can find it. How can we expand it? Look it's a issue and.

B

C

C

The dependency wall condition.

C

Yes, one reader can be blocked by another reader. Yes, other things, they are very enough. Not complicated I mean the algorithm. You can just go, go tipped off yourself. So that's my presentation today. Thank you.

C

C

B

C

A question because they haven't used it. You don't look.

B

Is it a static or dynamic? It's a good question. Is that dynamic otras? Yes,.

C

It was the Builder dynamically.

C

So that it won't affect the operation mystery.

B

C

Its algorithm analysis.

B

Is static so you think it's locked so.

C

We still need a story to.

B

While we are writing it, so you.

C

Go to the previous one about the.

B

Calculation of waste dependency.

C

I, don't remember which page.

B

Of three or four.

C

If you want to calculate a lot of dependency.

B

C

The decipher machine.

C

B

Be performed to find a machine.

C

But wise realized in the next kernel is a dynamic.

A

C

B

Record or the catalog it gets and.

C

This kind of method is not at.

B

Time is dating, go.

C

Back to the dependency graph, so is it a dynamically generated? Yes, look it.

B

Is dynamically.

C

B

C

Locked out, where classify days, locks.

B

C

Won't focus on the instances of this locks is dead.

C

It focus on the doctors locks, its were categorized into it until one type, but there's another s. If you use log it's another time yeah it has classified it. You got a boss and we have this kind of a classification.

B

C

After they have a written, the code that they have already found out about application- and you just need to wrong it- yes,.

B

C

That's basically the point so I want to mention that the look Deb is the more to do with the integration. Yes, different systems use the different box. The way you want integrated and then.

B

There is a locker unpredictable happening so.

B

A

C

Up with the information, you actually avoided that lock, actually the tap lock happens more during the integration process. So it's more like a form of the.

B

Distributor right because.

C

As the distributor dispatcher at.

B

The scheduler can just allocated resources and.

C

Yes, we can avoid this. You should happening through the code. Thank you.

B

C

B

C

B

C

B

C

About that you can't detect it yes for me. Yes,.

A

C

We have this dialog. We cannot not.

B

Detect the block- and we.

C

B

To our think that it doesn't have a deadlock, yes,.

C

You have a realized on the branch.

A

B

You sure about it.

C

Yes, we want to avoid the fog too.

C

B

They were classified as locsin.

C

And, depending on the ways to classify this, if you get into the very few categories, then for.

B

Example, there's a deadlock.

A

The filesystem.

C

Regard the firing process and.

B

As a disc, and in this way, if.

C

The file system would.

B

C

Were just the one to get a lock all the time because you think is a deadlock, so we that's why we want to classify it.

B

C

Avoid being recorded, I sat there longer.

B

C

The sound because it's there something long and we want to skip it, but I can't think of a variety tell the case. A specific case.

B

C

Yes, I have a question, so we.

B

Have to doubt it I just write back.

C

Well, we are just there just want to get the back of it. You know our says: wait, it's bound other words wait, but their lock condition.

B

C

Can't capture it, you mean the completion, would is the structure bridge, they were right, fake.

C

B

C

Way to be right back and to make it to turn still off.

B

C

Mean the we're taking Linux.

B

C

Be knock and you'll have to wait a fighter for the weight to be clear to zero.

B

C

Not sure what you are mentioned. Yes, we have this kind of this progress last year. There's.

B

A

B

C

B

There's a dialog with the condition of wait. Nothing.

C

Is where you wait? Actually, waiter waiter luck but time it doesn't take into consideration of this case. Sophie attack actually wait with a lock, so this weight has a dependency.

B

C

Has done of detection manager great, but.

B

The text number.

C

Trying to detect.

B

C

Actually doubt there's kind of problem. You.

B

Have just to print a patch again, yes,.

C

Then you can find the issue.

B

They remember the name of the.

C

Same song, Thackeray new student I, don't mr. name is Parker PRK.

B

C

Can search for locked up? You can find him he's very active in this area.

C

As I'm running out of time, so thank you very much.