An Overview of Locking in the FreeBSD Kernel
CC Attribution - NonCommercial - ShareAlike 3.0 Unported:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this
McKusick, Kirk
The FreeBSD kernel uses seven different types of locks to ensure proper access to the resources that it manages. This talk describes the hierarchy of these locks from the low-level and simple to the high-level and full-featured. The functionality of each type of lock is described along with the problem domain for which it is intended. The talk concludes by describing the witness system within the FreeBSD kernel that tracks the usage of all the locks in the system and reports any possible deadlocks that might occur because of improper acquisition ordering of locks.
 If he does, I'm not aware of it. Yes. Well, historically, that's the way we did. Okay. Okay. So, with these short-lived laks, they're essentially mutacted. We have what's called a blacking mutex. And a blacking mutex is one that'll spin for a while, and then if it can't get the resource, it'll black on a turnstile. The key thing about all of these things that are using mutex is that they can always run. If there's either, I mean, there's no doubt that run is either that a CPU is not available while we're running for a mutex that some other process is holding, and that process will either give it up because they're running. Well, if they're not running, as soon as they get scheduled and they run, then they will release it, and so eventually we can get there. The difference between that sort of an activity and the ones down here with the sleep cues are sleep cues are something where you need to wait for something to happen. Like, you're waiting for the disk to deliver a block, and simply scheduling you to run is not going to make you give up the lock. With mutexes, scheduling you to run or the scheduling some other mutex holding threads to run will cause you to be able to make forward progress. Okay, so besides blacking mutexes, we have these things called plural mutexes, which are general use blacking mutexes. We have reader-writer locks, which are mutexes that have shared exclusive semantics. These are exclusive use only. And we have read-mercel locks, which give you fast access for things that are read-mercely. And as I said, I'm going to come back and look at each of these in detail. We have locks that use the sleep cue interface, and the sleep cue interface, again, is for longer-term sleeps, typically one for something that requires some outside stimulus. So you're waiting for a packet to arrive on the network, you're waiting for a block to arrive on it from a disk, you're waiting for the user to type something. So it can be potentially a fairly long time before these will come back. Okay, so we have shared exclusive locks. These are sort of the fastest and simplest of the sleep locks. We'll have conditioned variables, which is really just sort of a wrapper around the traditional sleep and wake-up that I described earlier. And then we'll have the all-singing, all-dancing lock manager, full functionality sleep locks with the commensurate high overhead of using them because they do a lot of stuff. And finally, we'll have the witness subsystem, and it is, as we'll see, the thing that sort of makes sure that you don't violate a lot of these rules that I'm going to talk about as we go through these different locks. Okay, so I'm going to put these slides up on the Wiki page, so if you want to get them later, you can do that. This is the place to refer to if you want to, you know, sort of get the executive summary. All right, so the first thing I want to do is to look at the data structures that we use for managing these locks. Turnstiles are the things that are used by the short-term mutexes, and as it says, the blacking mutexes, the reader-writers, and the read-mostly locks. And these are designed, these mutexes are designed for holding just for a short period of time, usually just tens of instructions. So you need to, you know, check a value and take some sort of action on it, or you need to insert something on a list, or you need to take something off a list, or you need to traverse a list and you don't want it to change, you know, you don't want to have someone pulling stuff out from underneath you while you're trying to traverse a list. So you do the operation, you give it up, and in the card you'll typically see that you acquire the mutex, you do a few lines of C code, and then you typically give it up. Okay, so it's used to protect both read and write access to data structures. A lot of people make the mistake of forgetting that they need to check, that they need to protect for read access. So if you're going to traverse a list, even though you're not going to change it, you still need to hold the mutex so that things don't get pulled out from underneath you. Okay, you are not allowed to own a term style lock when you request a long-term sleep type lock. That is just a no-no. One of the things that the witness code will check for, if you try and acquire a sleep lock and you're about to go to sleep while you hold a mutex, then it will panic and complain and whine and moan. Okay, one of the things that we do is that we track the current lock holder. So whenever a lock is held, we know who holds that lock. And the reason that we need to do that is so that we can do what's called priority propagation. The issue with priority propagation is that you may have some relatively low-priority thread that comes along and gets a mutex and then gets blocked because some higher-priority thread comes along that gets the CPU. And then some really high-priority, important thread comes along, and they need the mutex that's held by this low-priority thread. But the low-priority thread can't run because there's these higher-priority things that all have all the CPUs. And so the idea of priority propagation is that when this high-priority thread comes along and it sees that this lock that it needs, this mutex that it needs, is held by this low-priority thread, it temporarily gets its high-priority to that low-priority thread. So that low-priority thread goes right up on the queue, all of a sudden it's high-priority, it gets to run, it releases the mutex, and then we don't love it anymore. Down it goes, and then we get the CPU handed back to us, the mutex is available, and zoom off we go. So that's the notion of priority propagation. In order to be able to do that, we need to know who holds the mutex. Okay, so the turnstile implementation is the thing that does this. And so there's a bunch of different things that we need to be able to do. We need a hash header so that we can quickly find the turnstile that is the data structure that essentially keeps track of everything that's going on. So just to zip ahead of here a little bit, this is a picture of the turnstile data structure, and you can see here we have the hash header across the top, and so we're hashing based on a particular lock that we're interested in, and so let's say that we're interested here in lock 18, so we'd run down this hashing header, we would find this entry here, which yes, that's for lock 18, and now we can see we have the R of the lock at the moment, is thread number one here. Waiting for it, we have threads number two and three, and then also from this thread one, we have a list of all of the mutexes that it currently holds. So it's currently holding lock 18 here and lock 15. So let's just back up again here. So the hash header allows us to quickly find the lock turnstile, so we hash, we find that turnstile in turn points to the thread that holds the lock, and it gives us also the list of any threads that are waiting for that lock. Okay, now a turnstile, one of those entries, one of these entries here, is needed each time that a thread blocks. So any time that you block, we need to have that turnstile so we can have that data structure which says, oh, that's who owns it and you're waiting, and potentially others. Now, remember that these mutexes are things that only help for very short periods of time. The last thing in the log we want to do is to go up and malice one of those things. I mean, we're taking something that is going to be held for 10 instructions, we're going to go up and do several thousand instructions to malice something to keep track of that. I don't think so. So how are we going to deal with this? Well, a thread can only block on one thing at a time. You can hold a bunch of locks, but you can only block on one because when you're blocked, you're not going anywhere. So what happens is that when you create a thread, one of the things that we do is we also, at the same time, malice a turnstile for you. And that's your turnstile. And so when you show up, just to sashay up to the mutex and you try and get it, if it's already held, then we take the turnstile, your turnstile, and that's the one that we use here. Okay, so this thread came along, it got the mutex, nobody's waiting, so everything's fine, this doesn't yet exist. Now thread two comes along, thread two is blocked, and so we take this turnstile which was allocated by thread two here, and set this up and link it all in as you see here, and then along comes thread three that also wants this mutex, and that also has a turnstile that it turns over, and we don't need it because we've already got this here. And so I'm not showing this picture, but it ought to be here, so there's a little list off of the turnstile in yourself, all the other turnstiles that have been turned in in the meantime. And now let's suppose that thread two is the next one, thread one gives it out, thread two now is the next one we select to run, presumably because it's higher priority than thread three, and so when we wake up thread two, of course we'll have to give thread two back thread two's turnstile, but this turnstile is still in use because of thread three here, but luckily thread three had given us their turnstile, so let's give thread three's turnstile to thread two and off thread two goes, we'll turnstile, they're happy, and it's not the same one you gave us, but you know, who cares. And then thread three finally gets through, and now we don't need to turnstile here anymore, so we denote it from this structure, we'll hand it to thread three, and thread three goes running off with it, yes. Does that cause problems on human architecture? It's crossing zones? It would not work on loosely coupled, and it's not something we're in a tightly coupled multiprocessor here. Otherwise, no, that would potentially not work well. Okay, all right, so, that's essentially this point, you provide a turnstile when you show up, when you're awakened, you're getting a turnstile, not necessarily the one you gave us, but it's a turnstile. Okay, and that's here where the only turnstiles are saved in return as threads awaken. Okay, if the hoggobble whack has a lower priority than the thread that's about to be black, then we recursively propagate the higher priority to the hoggobble, but only until such time as it releases it. So again, if we look at this picture here, thread, let's say thread three comes along and is blocked by thread one, because thread one holds the mutex at this point, but if thread one has a lower priority than thread three, then we will gather thread three's priority to thread one until such time as thread one gives up the mutex that we want. And when it does this, then thread one's priority will be pushed back down, and in all likelihood thread three will then get to run and awake those. So that's how we implement the priority. Yes? So, we can get from the log to the current, on what ends the log to register itself. You want to do a pointer every log? Okay. That's more of a, that's a little bit, change the log. Okay. John's the one that implemented this stuff, so. Here's the point of the priority on these things. Can you make every log? Go on. All right. So, sleep cues. Sleep cues look a lot like turnstiles, except that there's certain properties that turnstiles have that these don't, and vice versa. So these are used by the shared exclusive lacks, the condition variables, and the lack manager lacks, that sort of second big block that I told you, these are the ones that are doing long-term sleeps. Typically waiting for I.O. events, user input, you know, how long is it going to take for user input to occur, you know, they might have had a heart attack, they never type again, who knows. There is no priority propagation, because only at turnstiles, these things can't run until whatever the event is happens. Just, you know, I can give you the highest priority in the entire system, if the disk block hasn't been delivered yet, you can't run, and you can't give up the lack until the data arrives, because that's the meaning of having that lack. So we don't need all the stuff having to do with priority propagation, because it's just not a sensible thing to do. You're not allowed to own a turnstile lack when you request a sleep queue lock, and that gets back to this whole business of, with the turnstile lacks, these are things where we can always get that lack, if we just get you or the recursively, the things that are black in you to run, and we can always get them to run, because the only reason that they haven't run is because they haven't had a high enough priority to be allowed to run. So if you were to hold a turnstile type of lack here, now, we're going to get that back, because just making you run isn't going to solve the problem. And so, it is not permitted to own any kind of a turnstile type of lack when you acquire one of these longer term locks. Okay. Now, remembering the previous data structure, we kept track of who held the lack, and we still have that available. So we can track who is the exclusive lock holder, but of course, it doesn't have the right of law to deal with the, if you have multiple shared lock holders, then that data structure as it's shown previously doesn't have the ability to deal with that. We do have the ability to track the shared lock holders, but I'll talk about that when we get to that point. Okay. These locks may be recursive, and the decision on whether it's recursive is decided by whoever sets up the lack in the first place. There is, when you create it, you can say this lock is allowed to be recursive. What do I mean by recursive? What I mean is that if you already hold the lack, you're allowed to get another, you can say I locked exclusively again, and you'll be able to get that. If it's not set up for recursion, then you'll get a panic saying, recursing on a lock that's not recursive, but if it is recursive, then it'll just dutifully give you another exclusive reference. What's the guideline for working this first-site lock? What? What's the guideline for applying one of these first-site locks? What's the guideline for the recursive lock? First-site lock. Can you hold them for longer duration or very short duration? You can hold them for longer duration, some of them are coming to you. Yeah. If you hold them- I guess the question I have is, if you're going to be holding for a very short duration, if you just unlock the option, then you won't have to deal with the priority combination problem. I'm going to speak to some of these things. So wait till I go through the locks, because I think I'll answer a lot of those questions for you. Which, by the way, is what we're about to do. Okay, so just on the left field, I'll just throw in critical sections, which I haven't said booed about yet. These are, in some sense, a locking mechanism. A critical section is bounded by a critical enter and critical exit. And while we're- it does grab one of these critical sections, the thread can't be preempted by another thread. So it cannot be thrown off the CPU, and it in fact can't even be migrated to another CPU. We can't say, well, you know, whenever I preempt the new one, just move from here to there. And no, can't do that. So critical sections are a lot like the old single-threaded kernel where you'd black out interrupts, essentially, to prevent yourself from being, well, descheduled. These are useful for per-CPU data structures. So for example, there's typically a run queue per CPU, and if you're going to manipulate that, really, you can just- you know, since that data structure is only going to ever be referenced from that CPU, putting a critical enter and exit around the part where you're going to manipulate the queue is sufficient to protect it. And that way, you don't have to have some kind of mutex, which is potentially going to conflict with other things. There's also some CPU-specific memory allocation structures. So if you have memory allocated per CPU, again, it allows you to manipulate that, but it does not, and I emphasize, does not protect system-wide data structures. So this is useful only in that very constrained context. Okay, so the hardware requirement is the test and set, as I've already described. Freedbeast actually uses compare and swap. The compare and swap, you basically say, compare this value with what's that value location, and then if they match, then you stick this in there. Okay, so what this actually boils down to is we have an owner field for the lock, and if nobody owns it, it has this stock value, a mutex unowned is stored in there. And if the lock is held, then we have a pointer to the thread structure of whoever holds that lock. So to essentially try and get the lock, what we do is we compare the lock owner field with mutex unowned, and if that's the value that's in there, then we store, atomically store in the pointer to the acquiring thread. And then what we do is the return value is what was there previously. So if you look at what came back, and if what came back was mutex unowned, then you know you got it, and if what came back is a pointer to a thread, that's not you, then you didn't get it. Okay, so at the bottom level, that's the mechanism that we're using. And then when you're done with it, you just store mutex unowned back in there, and now it's unlocked. Now you may not have checked and see if there were others that wanted it, etc., but we'll get to that. Okay, so starting at the right bottom, we've got the spin mutexes. These are exclusive access only. They're just super sparing running for the mutex to be available. Once it acquires the mutex, it's in a critical section, and so it can't be preempted until it gives that thing up. This is to avoid some possible deadlocks. It's actually more expensive to obtain than a blocking mutex. And so it's really only used for very low-level scheduling stuff and a little bit of the context-switching stuff. Unless you happen to be working in that one little area, you're not going to be using spin mutexes. You're going to be using the regular blocking mutexes, which are what I'm about to describe here. Yes? That's starting to get more expensive. How much proof would we put in that? I asked John, and he said they were more expensive. So, for example, in 186, you have to do a CNOI-STI and compare it up to the same amount of additional technical topical. I'm sort of curious why I'm living with spin mutexes. They also use RCU, right? They used the patented RCU algorithm. So why can't they answer? Let me do my talking, and we can have this debate later. God knows you could have the rest of the afternoon. So the blocking mutexes actually use what's called adaptive spinning. So in some sense, we get the benefits of the spinning without necessarily having some of the other drawbacks to it. So what do I mean by adaptive spinning? Well, we will spin running for it only if the owner of the lock is currently running. So if the owner of the lock is currently running, the expectation is, well, I haven't got much further to go, and then they're going to be done, and then we'll get it. So we'll just sit there waiting for it to happen. On the other hand, if they're not running, then it moves us to black because it potentially is going to be a while before we're going to be able to get it, and it also means that if we had a higher priority, it's going to propagate our priority to that particular thread, and hopefully that will boost it up and get it to run and get it to give it up so we can get it back. Okay. When someone is done with the lock or with the mutex, all the riders are awakened. And again, this might seem counterproductive because your first thought is, well, great, we wake up three things, they're all done, and one of them gets hit, and the others go back to sleep, and that doesn't seem like a particularly effective way to do things, but it is cheaper to release an uncontested lock since it's just a story. You just drop something in there. We don't have to find a turnstile and traverse it and do lots of other things. So we do that once when the first thread gives it up, and now all the best things get done and the turnstiles get turned back to the riders, etc. And we often end up just scheduling those things sequentially anyway because they only have the same priority and we just sort of drop them off. And even when they are scheduled concurrently, the lock actually has it, it's probably running, and so they're just going to use adaptive spinning anyway. They're not just going to immediately block, they're going to say, how about running, I'll just wait for it and then boom, you'll eventually get it. And so again, it's somewhat counterintuitive why you would wake them all up, but when you actually look at what happens, it's actually a more sensible way to do it. Okay. Now, mutexes, when you want to create them, you have to go off and allocate them and initialize them, and if the witness is running, they get registered with the witness code, and conversely, when you're done with them, you've got to essentially shut them back down, deallocate them, and deregister them from the witness code, etc. And this is not a lot of work, but it's not a trivial amount of work. And so if you have something where you need a mutex that's just for something that's a very short-lived data structure, the whole overhead of creating and tearing down the mutex can dominate the cost of using that data structure. And so for such things, there is a pool of pre-allocated mutexes. And so when you need a mutex, instead of going through the whole creation business, you just go out and say, I need a mutex, and you sort of check it out, like checking a book out at a library. You actually have that whole mutex in your data structure. It's just a pointer over to that one that's allocated over there in the pool. And so why do you use something like this? Well, the pool system call is one of the classic places where it gets used. It needs a structure to track a poll request from the time that you do the poll or the select system call until the unravel of data for one of the poll descriptors, and they're done with it. And if we've got high bandwidth networking coming in and you're just selecting on that, it could be a very short period of time between when you go in and the select returns. And all you want to make it for is to protect a couple little flag fields or something that's in that data structure. The data structure is maybe four or five pointers long. And so, you know, pulling a whole mutex in there would quadruple the size of it, and then the whole overhead of doing that for any descriptor that you're pulling would be prohibitive. So it's just very quicker to just say, grab a set of these four things, use them for one setting and clearing up a flag, give them back, and we're done. And if it keeps the structure small, it makes it all go quickly. All right. Next up, the ladder, come reader-reader locks. And mutexes, as I said earlier, are these exclusive access, but now we want to also be able to do shared semantics so that we can have multiple readers and single-threaded writers. We use, since we're using it, yeah, because these are, you know, turn-style type, mutex-type locks, again, you're not allowed to hold a reader-reader lock when you're going to go to sleep, when you're going to acquire a long-term lock. We provide priority propagation for the exclusive access, because that's just what turn-styles do. We do not provide priority propagation for the shared access, in this case. So if you are, there's a bunch of readers and a route comes along, and the writer has a higher priority, well, they still have to wait for all the readers to go to give up, but we don't have any way of knowing who they are, so we can propagate the priority to it. Consequently, if that's going to be an issue for you, you need to use some other mechanism. We also, in this case, allow you to specify that it's okay to recurse. And normally on mutex, if you recurse, that's a no-no. This recursion, of course, is referring to the exclusive access. Finally, in this class, we have the read-mostly locks, and this is, as pretty much the same property as the reader-reader locks, except that they add priority propagation for the shared access. So if you need to have the priority propagation, we can do that here. And the way we do that is that the shared owners provide a tracking data structure. So much like you provide a term style when you're blocking, if, in this case, you have to provide a little data structure that we can then link together in a big long list, so we now know who all the readers are. And so now we can do priority propagation because we can just run down that list. Now, when you call in to do a shared access lock, you also have to pass in a pointer to this tracking data structure. So if it's an issue where you need to have the priority propagation, then you're going to use these kind of locks. Now, the notion of this is that we're designed for fast access for readers. So shared access, assuming that there'll be relatively few writers. And again, the idea is, so if you have it mostly just reading, and you're not going to be writing it very often, then we'd like to have sort of a fast path for reading. So in essence, what we do is we read without a lock and then see if any bad stuff happened. And if it did, then we have to back up and do the whole thing the hard way. The writing table is a good example of a read mostly data structure. So for example, we don't actually add new routes very often, we mostly just look them up. And so the lookups of that go quickly. When you do an update to the routing table, of course, then you get a big burp. So if you use one of these in an instance where you have a lot of writing going on, it's not going to be inefficient. Now, the best way to implement this is actually patented by IBM. RCU is the magic word there. Now, IBM allows anyone with GPL code to use their patented implementation at no cost, i.e. Linux meets this criterion. But previous D is not GPLed, so we'd have to use a somewhat slower technique to avoid doing the patented way of things. And there was at least no approach to... What? No, no, not for a while. There wasn't actually an approach to IBM, but their attitude is, well, it would be pointless to have the patent if we let all of our for-profit competitors use it and we want it to be out there. And so I don't understand where they're coming from, but it's kind of a pain. Okay. So that's up to now. There are things that are the short-term type locks. Locks that you can only hold for a short-term basis. You can't hold them on a long-term basis. Now, starting to the locks that are the long-term locks, the fastest and simplest of these is the shared exclusive locks. And surprisingly, they provide shared and exclusive access. You can specify that you can recurse. You can also indicate that if a signal comes in while you're asleep, you would like to wake up and handle that signal. It has, I'll just say, limited upgrade and down-date grade capabilities. And like all sleep locks, it does not implement priority propagation because it's pointless, as for the reasons I described earlier. You'll still see a lot of people doing explicit sleep and wake-up in the system, but it's typically things like demons that are just sort of ping-ponging back and forth. Like the demon that does swapping or paging or whatever. And it will go to sleep and then when whatever someone decides they need it to run, they issue it to wake up and it does some stuff for a while and then it goes back to sleep. And so those sorts of sleep and wake-ups you will see just written as sleep and wake-up. But in the sort of traditional way, for example, the code that I showed you at the very beginning, we wrap all the business about want flags and lock flags and so on, and then we sleep and wake-up parts inside these condition variable functions. And so you'll see it being used in that way, the CV under type stuff. So it allows you to wait on an optionally timeout so you can say, well, I want to sleep, but not longer than five seconds. Or if a signal comes in, I want to be interrupted, or I don't want to be interrupted, whatever. You can say, when you do a wake-up, do you want to wake up just one of the ones that's waiting, when you're waiting the longest, or do you want to wake everybody up? That's what a historic behavior. And you have to hold a mutex before awakening or waiting. And if you're about to wait, the mutex is released as part of going to sleep. And I didn't really describe that aspect of it, but if you think about it, you need to get a mutex to check like the want and lock flags and so on. And that way, that's tight to be able to change before you get completely to sleep. Because if you release the mutex and then called sleep, between the time you release the mutex and the time you get to sleep, someone else might have run an issue to wake up. But since you haven't gotten to sleep yet, there's no one to wake up. Okay, no worries. But now you go to sleep, and there's no one that's ever going to issue you a wake-up. And remember that forever word, which we really don't like. So the issue with the mutex is you hold a mutex, it's actually passed as a parameter to sleep. And it says, when you have gotten to sleep, then release this mutex. And normally then it's reacquired when you wake up, although you can set a flag to sleep. It says, I don't really need it when I wake up. Yes, Julianne? I'm not so convinced that you need to do the lock-file. You're doing a waiting and a moment-file. You're doing a setting of what's consuming more cars. I know you do under some, some, some, some, I'm not sure if that allows to do a 64000 without having to hold the lock. Okay, well, I will check that, since I want to get the textbook right, of course. Okay. So we finally got to the most full-featured, awesome, all-dancing lock manager locks. These are, you can, you know, jump through hoops and do all kinds of exciting things. Show you an exclusive access. You can recourse. You can request a timeout or an interrupt by a signal. You can do upgrade, downgrade it, upgrade it, what's called an exclusive upgrade, which says, I have this shared lock. I want it to be turned into an exclusive lock and bound around it. I don't want anyone else to get an exclusive lock between when I ask for it and when I get it. And if someone else somehow manages to sneak in and get the exclusive lock before I get it, then you need to let me know that, so that I can potentially have to go back and check things again. Okay. Why is it the boundary to pass the ownership of the lock from the thread to the kernel? And this probably sounds a little bit weird. Why would you want to do that? The issue here is that normally, if you hold the lock, your thread needs to be the one that releases that lock. And if it's not, if I lock it and one of you unlocks, it's like, oh, now wait a minute, you're not supposed to do that. That's not you unlock. That's my lock. However, there are times when I may not even be around anymore by the time it needs to be unlocked. So for example, I'm running out of a bunch of blocks of a file, I sort of close the file and eventually its blocks need to be written out, and I initiate this, but I don't actually wait for that IOTA to complete. And in fact, by the time the IOTA is completed, I may be completely exited out of the system and not exist anymore at all. And so now who's going to be able to unlock it? So what ends up happening is if I'm sort of disowning it, I'm handing it off to the IOTA system, I turn it over and say, well, I disavow knowledge of this, I'm not in charge of this anymore, I'm just giving that to the kernel. And now something like the G up thread of GOM or the interrupt thread for the device or whatever can be the one that ultimately unlocks that at the end of the operation. And that thread is a kernel thread and it's owned by the kernel, so all is happy and we don't get any panics. We've been deprecating lock manager for a decade, but it just has enough uses that it doesn't ever seem to quite go away. And like all sleeplocks, it does not implement priority propagation. And also I think that lock manager cannot start, normal shared lock, so it can start right there. Yes, so the comment up here is that the reader rather lacks here, or the shared exclusive lacks here. What can happen is that if there's enough people coming through and using the shared ones, you can starve an exclusive access. So because of course you can't have exclusive access to all the shared ones go away. And if we just keep handing out shared ones all the time, you may never get to the point where the exclusive guy gets it. With the lock manager locks, once there's a repending request for an exclusive lock, we will not allow any more shared locks to come in. And so they will at some point drain away, so we do in fact ensure that the exclusive access can happen. It's not like one of those is correct and the other is not correct, they're just different algorithms and you need to know what they are when you're deciding which kind of lock to use. Okay, so how do we make all this stuff work and play well together? Well, in the old days we used to just sort of know that you had to have this kind of lock before you had that kind of lock and what all the correct orders were of everything. And it was a little documented in the comments for the most part when they were up to date and written. And it kind of sort of worked okay when we had single threaded kernels. But once we started getting all these mutexes and you have just an explosion of the number of locks that are in the system, it becomes virtually impossible to really know what the correct ordering is for the locking without getting yourself into deadlock. And deadlock is another one of the situations which is rather unpleasant. So there's essentially two ways to deal with deadlock. One is, and believe it or not it is the way it was historically done, not in Unix but in some other operating systems, is to essentially have a deal and it waches for deadlocks. And when it sees a deadlock it just goes, hmm, those two threads are deadlock. Well, I'll just shoot that one. Deadlock's out. Unfortunately the one that was shot was your Emacs editor that you hadn't saved the buffer for, well, never mind. So the approach that has been used in Unix since the beginning of time and still used today but is now being checked by the witness code is what's called partial ordering. And the idea of partial ordering is that we put the locks into classes. So we have class one here is all of the, all the one locks. So there's R1 and R1 prime and R1 double prime. And then in class two we've got R2 and R2 prime and R2 double prime. And then there's just two very simple rules. You can only have one lock at a time in a class and you can only acquire a lock in a higher numbered class than the one you already own. So we have two threads here A and B and A comes along and gets lock number one here and thread B comes along and gets lock R2 and so forth and that's fine. If you only own one lock there's no possibility for deadlock. But now thread A comes along and wants R2. Well that meets the criteria and it's in a different class and it's two is higher than one so that's all fine. But it gets locked because thread B is holding it. Well now thread B locks R1 over here. Well that's, if we just, if we just tried to get R1 we'd now be deadlocked because they each hold one and they each want the other one and we'd be stuck. But thread B realizes oh R1 is a locked class, numbered class than the one I already hold. So I can't do that, I have to temporarily give up my R2 then go back on R1 because thread A's already got it. But now thread A is going to be able to get R2, then it's done and release them and now thread B will be able to get R1 and then come back and reacquire R2 and everybody's happy and we have no deadlock. Now as I said, you know this was just sort of a non-thing and everyone sort of knew what they were as well as in the old days. But that, with the addition of SMP just became untenable and so the witness in code came into existence to actually help out with this. Now absent the algorithm I'm about to describe, someone has to go along and figure out what these classes are and what the ordering is. And while the programmers have some idea of that, it's a little bit tenuous to expect them to do that with every lock in the system. And so in fact what happens is, although you can sort of pre-define certain classes and what's in those, for the most part witness just figures it out on its own. It just sort of comes up and it watches the order in which things are used and it boils its own notion of what the hierarchy is supposed to be. And then when it sees a violation of that hierarchy, it complains and puts out the well-known LOR kind of thing. It's like you acquire this lock at this line of this function and this other lock at this other line of this other function and you can't have that one while you hold this one. You got to be the other order. Now you'd say, well how can it possibly figure all that out? Well the answer is that, and get it right. I mean what if it gets it in the wrong order? Well first of all you shouldn't be programming in the wrong order. So the right order should be sort of what's there. And it turns out by the time you've gone through the start-up code most of the interesting locks in New Texas have already been created and so been used in the right order. And so witness more or less gets it right and you only need to do a little bit of strategic identification, pre-identification and it all just kind of works. That being said, we still end up with a lot of lock order reversals which in fact may not ever really be a problem. But there's the LOR mailing list wherein people spend endless amounts of time debating how best to fix these things. Certainly it is a constant headache. But at least you know that if you're not getting LOR messages you're not going to be getting deadlocks in the system. And in fact, you know, previous to you sort of known as a system that's not prone to deadlocking unlike some other systems. And the witness is a large piece of why that is. The witness is also extremely valuable when you're jumping into a piece of code that you haven't worked on for a while or maybe never worked on. And so you don't really know what the order is but you very quickly, it gets pointed out to you. And specifically while you're doing things and where the order is running, figuring out how to fix that can often be a little more difficult. But as I say, once you get it fixed, it's fixed and you just know you're not going to get a deadlock, at least from that. Okay, so that is what I have to say. I meant to put these slides up and I went to do it last night and I couldn't quite get it to work so I need to talk to Dan. But I am going to put these slides up on the Wiki or the webpage or whatever it is and I will have about three minutes for questions. Yeah. You can certainly get witness to dump out the state of all the ordering rules that it has. John, do you know the answer to the first question there? I don't think, I'm going to be sharing my people at work. Sorry, everybody, this is the first thing. Yeah. So we have the locking man page, which basically covers all of this, which I wrote. I was trying to understand what the hell was going on. And I still do not quite sure it's all correct. So the next time anyone wants to write a chapter on this and needs to learn it all, they should go to the locking man page and they should. Update it? It's just everywhere it's wrong. I'll take that under, I have two more to do list here. I actually asked the, I asked John many, many times, many times to edit that page and just check it with the sender. Yeah, well that was one of the first places I looked when I went to write the chapter and I only went on two or three wild goose chases, so. Well, if I'm wrong, the I is your friend or he next maybe, because he was written by me that tells you how much to trust him. Yes. The conditional variables in the lock manager locks these signal or unified semantics when you're waiting on your cell. They are using the wake up primitive in the system, so they identify whatever is the thread that should be awakened and then they issue a wake up to take it off the sleep queue and put it on the run queue. Right, all the wake up does is put you on a run queue and then the scheduler will decide when you get to actually run. It might run straight away if it's quick security. Right. Okay, anything else? Ha, I've stunned them all into silence. Thank you very much.
 If he does, I'm not aware of it.  Yes.  Well, historically, that's the way we did.  Okay.  Okay.  So, with these short-lived laks, they're essentially mutacted.  We have what's called a blacking mutex.  And a blacking mutex is one that'll spin for a while,  and then if it can't get the resource, it'll black on a turnstile.  The key thing about all of these things that are using mutex is that they can always run.  If there's either, I mean, there's no doubt that run is either that a CPU is not available  while we're running for a mutex that some other process is holding,  and that process will either give it up because they're running.  Well, if they're not running, as soon as they get scheduled and they run,  then they will release it, and so eventually we can get there.  The difference between that sort of an activity and the ones down here with the sleep cues  are sleep cues are something where you need to wait for something to happen.  Like, you're waiting for the disk to deliver a block,  and simply scheduling you to run is not going to make you give up the lock.  With mutexes, scheduling you to run or the scheduling some other mutex holding threads to run  will cause you to be able to make forward progress.  Okay, so besides blacking mutexes, we have these things called plural mutexes,  which are general use blacking mutexes.  We have reader-writer locks, which are mutexes that have shared exclusive semantics.  These are exclusive use only.  And we have read-mercel locks, which give you fast access for things that are read-mercely.  And as I said, I'm going to come back and look at each of these in detail.  We have locks that use the sleep cue interface,  and the sleep cue interface, again, is for longer-term sleeps,  typically one for something that requires some outside stimulus.  So you're waiting for a packet to arrive on the network,  you're waiting for a block to arrive on it from a disk,  you're waiting for the user to type something.  So it can be potentially a fairly long time before these will come back.  Okay, so we have shared exclusive locks.  These are sort of the fastest and simplest of the sleep locks.  We'll have conditioned variables, which is really just sort of a wrapper around the traditional sleep and wake-up  that I described earlier.  And then we'll have the all-singing, all-dancing lock manager, full functionality sleep locks  with the commensurate high overhead of using them because they do a lot of stuff.  And finally, we'll have the witness subsystem,  and it is, as we'll see, the thing that sort of makes sure that you don't violate a lot of these rules  that I'm going to talk about as we go through these different locks.  Okay, so I'm going to put these slides up on the Wiki page,  so if you want to get them later, you can do that.  This is the place to refer to if you want to, you know, sort of get the executive summary.  All right, so the first thing I want to do is to look at the data structures that we use for managing these locks.  Turnstiles are the things that are used by the short-term mutexes, and as it says,  the blacking mutexes, the reader-writers, and the read-mostly locks.  And these are designed, these mutexes are designed for holding just for a short period of time,  usually just tens of instructions.  So you need to, you know, check a value and take some sort of action on it,  or you need to insert something on a list, or you need to take something off a list,  or you need to traverse a list and you don't want it to change, you know,  you don't want to have someone pulling stuff out from underneath you while you're trying to traverse a list.  So you do the operation, you give it up, and in the card you'll typically see that you acquire the mutex,  you do a few lines of C code, and then you typically give it up.  Okay, so it's used to protect both read and write access to data structures.  A lot of people make the mistake of forgetting that they need to check,  that they need to protect for read access.  So if you're going to traverse a list, even though you're not going to change it,  you still need to hold the mutex so that things don't get pulled out from underneath you.  Okay, you are not allowed to own a term style lock when you request a long-term sleep type lock.  That is just a no-no.  One of the things that the witness code will check for,  if you try and acquire a sleep lock and you're about to go to sleep while you hold a mutex,  then it will panic and complain and whine and moan.  Okay, one of the things that we do is that we track the current lock holder.  So whenever a lock is held, we know who holds that lock.  And the reason that we need to do that is so that we can do what's called priority propagation.  The issue with priority propagation is that you may have some relatively low-priority thread  that comes along and gets a mutex and then gets blocked because some higher-priority thread  comes along that gets the CPU.  And then some really high-priority, important thread comes along,  and they need the mutex that's held by this low-priority thread.  But the low-priority thread can't run because there's these higher-priority things  that all have all the CPUs.  And so the idea of priority propagation is that when this high-priority thread comes along  and it sees that this lock that it needs, this mutex that it needs,  is held by this low-priority thread, it temporarily gets its high-priority to that low-priority thread.  So that low-priority thread goes right up on the queue,  all of a sudden it's high-priority, it gets to run, it releases the mutex,  and then we don't love it anymore.  Down it goes, and then we get the CPU handed back to us,  the mutex is available, and zoom off we go.  So that's the notion of priority propagation.  In order to be able to do that, we need to know who holds the mutex.  Okay, so the turnstile implementation is the thing that does this.  And so there's a bunch of different things that we need to be able to do.  We need a hash header so that we can quickly find the turnstile  that is the data structure that essentially keeps track of everything that's going on.  So just to zip ahead of here a little bit,  this is a picture of the turnstile data structure,  and you can see here we have the hash header across the top,  and so we're hashing based on a particular lock that we're interested in,  and so let's say that we're interested here in lock 18,  so we'd run down this hashing header,  we would find this entry here, which yes, that's for lock 18,  and now we can see we have the R of the lock at the moment,  is thread number one here.  Waiting for it, we have threads number two and three,  and then also from this thread one,  we have a list of all of the mutexes that it currently holds.  So it's currently holding lock 18 here and lock 15.  So let's just back up again here.  So the hash header allows us to quickly find the lock turnstile,  so we hash, we find that turnstile in turn points to the thread that holds the lock,  and it gives us also the list of any threads that are waiting for that lock.  Okay, now a turnstile, one of those entries,  one of these entries here, is needed each time that a thread blocks.  So any time that you block, we need to have that turnstile  so we can have that data structure which says,  oh, that's who owns it and you're waiting, and potentially others.  Now, remember that these mutexes are things that only help for very short periods of time.  The last thing in the log we want to do is to go up and malice one of those things.  I mean, we're taking something that is going to be held for 10 instructions,  we're going to go up and do several thousand instructions to malice something to keep track of that.  I don't think so.  So how are we going to deal with this?  Well, a thread can only block on one thing at a time.  You can hold a bunch of locks, but you can only block on one  because when you're blocked, you're not going anywhere.  So what happens is that when you create a thread,  one of the things that we do is we also, at the same time,  malice a turnstile for you.  And that's your turnstile. And so when you show up,  just to sashay up to the mutex and you try and get it,  if it's already held, then we take the turnstile,  your turnstile, and that's the one that we use here.  Okay, so this thread came along, it got the mutex,  nobody's waiting, so everything's fine, this doesn't yet exist.  Now thread two comes along, thread two is blocked,  and so we take this turnstile which was allocated by thread two here,  and set this up and link it all in as you see here,  and then along comes thread three that also wants this mutex,  and that also has a turnstile that it turns over,  and we don't need it because we've already got this here.  And so I'm not showing this picture, but it ought to be here,  so there's a little list off of the turnstile in yourself,  all the other turnstiles that have been turned in in the meantime.  And now let's suppose that thread two is the next one,  thread one gives it out, thread two now is the next one we select to run,  presumably because it's higher priority than thread three,  and so when we wake up thread two, of course we'll have to give thread two  back thread two's turnstile, but this turnstile is still in use  because of thread three here, but luckily thread three had given us their turnstile,  so let's give thread three's turnstile to thread two and off thread two goes,  we'll turnstile, they're happy, and it's not the same one you gave us,  but you know, who cares.  And then thread three finally gets through,  and now we don't need to turnstile here anymore,  so we denote it from this structure,  we'll hand it to thread three, and thread three goes running off with it, yes.  Does that cause problems on human architecture?  It's crossing zones?  It would not work on loosely coupled,  and it's not something we're in a tightly coupled multiprocessor here.  Otherwise, no, that would potentially not work well.  Okay, all right, so, that's essentially this point,  you provide a turnstile when you show up,  when you're awakened, you're getting a turnstile,  not necessarily the one you gave us, but it's a turnstile.  Okay, and that's here where the only turnstiles are saved in return as threads awaken.  Okay, if the hoggobble whack has a lower priority than the thread that's about to be black,  then we recursively propagate the higher priority to the hoggobble,  but only until such time as it releases it.  So again, if we look at this picture here,  thread, let's say thread three comes along and is blocked by thread one,  because thread one holds the mutex at this point,  but if thread one has a lower priority than thread three,  then we will gather thread three's priority to thread one  until such time as thread one gives up the mutex that we want.  And when it does this, then thread one's priority will be pushed back down,  and in all likelihood thread three will then get to run and awake those.  So that's how we implement the priority.  Yes?  So, we can get from the log to the current,  on what ends the log to register itself.  You want to do a pointer every log?  Okay.  That's more of a, that's a little bit,  change the log.  Okay.  John's the one that implemented this stuff, so.  Here's the point of the priority on these things.  Can you make every log?  Go on.  All right.  So, sleep cues.  Sleep cues look a lot like turnstiles,  except that there's certain properties that turnstiles have that these don't,  and vice versa.  So these are used by the shared exclusive lacks,  the condition variables, and the lack manager lacks,  that sort of second big block that I told you,  these are the ones that are doing long-term sleeps.  Typically waiting for I.O. events, user input,  you know, how long is it going to take for user input to occur,  you know, they might have had a heart attack,  they never type again, who knows.  There is no priority propagation,  because only at turnstiles,  these things can't run until whatever the event is happens.  Just, you know, I can give you the highest priority in the entire system,  if the disk block hasn't been delivered yet,  you can't run, and you can't give up the lack until the data arrives,  because that's the meaning of having that lack.  So we don't need all the stuff having to do with priority propagation,  because it's just not a sensible thing to do.  You're not allowed to own a turnstile lack when you request a sleep queue lock,  and that gets back to this whole business of,  with the turnstile lacks,  these are things where we can always get that lack,  if we just get you or the recursively, the things that are black in you to run,  and we can always get them to run, because the only reason that they haven't run is  because they haven't had a high enough priority to be allowed to run.  So if you were to hold a turnstile type of lack here,  now, we're going to get that back,  because just making you run isn't going to solve the problem.  And so, it is not permitted to own any kind of a turnstile type of lack  when you acquire one of these longer term locks.  Okay. Now, remembering the previous data structure,  we kept track of who held the lack, and we still have that available.  So we can track who is the exclusive lock holder,  but of course, it doesn't have the right of law to deal with the,  if you have multiple shared lock holders,  then that data structure as it's shown previously doesn't have the ability to deal with that.  We do have the ability to track the shared lock holders,  but I'll talk about that when we get to that point.  Okay. These locks may be recursive,  and the decision on whether it's recursive is decided by whoever sets up the lack in the first place.  There is, when you create it, you can say this lock is allowed to be recursive.  What do I mean by recursive?  What I mean is that if you already hold the lack, you're allowed to get another,  you can say I locked exclusively again,  and you'll be able to get that.  If it's not set up for recursion, then you'll get a panic saying,  recursing on a lock that's not recursive,  but if it is recursive, then it'll just dutifully give you another exclusive reference.  What's the guideline for working this first-site lock?  What?  What's the guideline for applying one of these first-site locks?  What's the guideline for the recursive lock?  First-site lock.  Can you hold them for longer duration or very short duration?  You can hold them for longer duration, some of them are coming to you.  Yeah.  If you hold them-  I guess the question I have is,  if you're going to be holding for a very short duration,  if you just unlock the option,  then you won't have to deal with the priority combination problem.  I'm going to speak to some of these things.  So wait till I go through the locks,  because I think I'll answer a lot of those questions for you.  Which, by the way, is what we're about to do.  Okay, so just on the left field,  I'll just throw in critical sections,  which I haven't said booed about yet.  These are, in some sense, a locking mechanism.  A critical section is bounded by a critical enter and critical exit.  And while we're-  it does grab one of these critical sections,  the thread can't be preempted by another thread.  So it cannot be thrown off the CPU,  and it in fact can't even be migrated to another CPU.  We can't say,  well, you know, whenever I preempt the new one,  just move from here to there.  And no, can't do that.  So critical sections are a lot like the old single-threaded kernel  where you'd black out interrupts,  essentially, to prevent yourself from being, well, descheduled.  These are useful for per-CPU data structures.  So for example, there's typically a run queue per CPU,  and if you're going to manipulate that,  really, you can just-  you know, since that data structure is only going to ever be referenced from that CPU,  putting a critical enter and exit around the part where you're going to manipulate the queue  is sufficient to protect it.  And that way, you don't have to have some kind of mutex,  which is potentially going to conflict with other things.  There's also some CPU-specific memory allocation structures.  So if you have memory allocated per CPU,  again, it allows you to manipulate that,  but it does not, and I emphasize, does not protect system-wide data structures.  So this is useful only in that very constrained context.  Okay, so the hardware requirement is the test and set, as I've already described.  Freedbeast actually uses compare and swap.  The compare and swap, you basically say,  compare this value with what's that value location,  and then if they match, then you stick this in there.  Okay, so what this actually boils down to is we have an owner field for the lock,  and if nobody owns it, it has this stock value,  a mutex unowned is stored in there.  And if the lock is held, then we have a pointer to the thread structure  of whoever holds that lock.  So to essentially try and get the lock,  what we do is we compare the lock owner field with mutex unowned,  and if that's the value that's in there,  then we store, atomically store in the pointer to the acquiring thread.  And then what we do is the return value is what was there previously.  So if you look at what came back, and if what came back was mutex unowned,  then you know you got it, and if what came back is a pointer to a thread,  that's not you, then you didn't get it.  Okay, so at the bottom level, that's the mechanism that we're using.  And then when you're done with it, you just store mutex unowned back in there,  and now it's unlocked.  Now you may not have checked and see if there were others that wanted it, etc.,  but we'll get to that.  Okay, so starting at the right bottom, we've got the spin mutexes.  These are exclusive access only.  They're just super sparing running for the mutex to be available.  Once it acquires the mutex, it's in a critical section,  and so it can't be preempted until it gives that thing up.  This is to avoid some possible deadlocks.  It's actually more expensive to obtain than a blocking mutex.  And so it's really only used for very low-level scheduling stuff  and a little bit of the context-switching stuff.  Unless you happen to be working in that one little area,  you're not going to be using spin mutexes.  You're going to be using the regular blocking mutexes,  which are what I'm about to describe here.  Yes?  That's starting to get more expensive.  How much proof would we put in that?  I asked John, and he said they were more expensive.  So, for example, in 186, you have to do a CNOI-STI  and compare it up to the same amount of additional technical topical.  I'm sort of curious why I'm living with spin mutexes.  They also use RCU, right?  They used the patented RCU algorithm.  So why can't they answer?  Let me do my talking, and we can have this debate later.  God knows you could have the rest of the afternoon.  So the blocking mutexes actually use what's called adaptive spinning.  So in some sense, we get the benefits of the spinning  without necessarily having some of the other drawbacks to it.  So what do I mean by adaptive spinning?  Well, we will spin running for it only if the owner of the lock is currently running.  So if the owner of the lock is currently running,  the expectation is, well, I haven't got much further to go,  and then they're going to be done, and then we'll get it.  So we'll just sit there waiting for it to happen.  On the other hand, if they're not running, then it moves us to black  because it potentially is going to be a while before we're going to be able to get it,  and it also means that if we had a higher priority,  it's going to propagate our priority to that particular thread,  and hopefully that will boost it up and get it to run and get it to give it up  so we can get it back.  Okay.  When someone is done with the lock or with the mutex,  all the riders are awakened.  And again, this might seem counterproductive  because your first thought is, well, great, we wake up three things,  they're all done, and one of them gets hit, and the others go back to sleep,  and that doesn't seem like a particularly effective way to do things,  but it is cheaper to release an uncontested lock since it's just a story.  You just drop something in there.  We don't have to find a turnstile and traverse it and do lots of other things.  So we do that once when the first thread gives it up,  and now all the best things get done and the turnstiles get turned back to the riders, etc.  And we often end up just scheduling those things sequentially anyway  because they only have the same priority and we just sort of drop them off.  And even when they are scheduled concurrently,  the lock actually has it, it's probably running,  and so they're just going to use adaptive spinning anyway.  They're not just going to immediately block, they're going to say,  how about running, I'll just wait for it and then boom, you'll eventually get it.  And so again, it's somewhat counterintuitive why you would wake them all up,  but when you actually look at what happens, it's actually a more sensible way to do it.  Okay.  Now, mutexes, when you want to create them, you have to go off and allocate them  and initialize them, and if the witness is running, they get registered with the witness code,  and conversely, when you're done with them, you've got to essentially shut them back down,  deallocate them, and deregister them from the witness code, etc.  And this is not a lot of work, but it's not a trivial amount of work.  And so if you have something where you need a mutex that's just for something that's a very short-lived data structure,  the whole overhead of creating and tearing down the mutex can dominate the cost of using that data structure.  And so for such things, there is a pool of pre-allocated mutexes.  And so when you need a mutex, instead of going through the whole creation business,  you just go out and say, I need a mutex, and you sort of check it out, like checking a book out at a library.  You actually have that whole mutex in your data structure.  It's just a pointer over to that one that's allocated over there in the pool.  And so why do you use something like this?  Well, the pool system call is one of the classic places where it gets used.  It needs a structure to track a poll request from the time that you do the poll or the select system call  until the unravel of data for one of the poll descriptors, and they're done with it.  And if we've got high bandwidth networking coming in and you're just selecting on that,  it could be a very short period of time between when you go in and the select returns.  And all you want to make it for is to protect a couple little flag fields or something that's in that data structure.  The data structure is maybe four or five pointers long.  And so, you know, pulling a whole mutex in there would quadruple the size of it,  and then the whole overhead of doing that for any descriptor that you're pulling would be prohibitive.  So it's just very quicker to just say, grab a set of these four things,  use them for one setting and clearing up a flag, give them back, and we're done.  And if it keeps the structure small, it makes it all go quickly.  All right. Next up, the ladder, come reader-reader locks.  And mutexes, as I said earlier, are these exclusive access,  but now we want to also be able to do shared semantics so that we can have multiple readers and single-threaded writers.  We use, since we're using it, yeah, because these are, you know, turn-style type, mutex-type locks,  again, you're not allowed to hold a reader-reader lock when you're going to go to sleep,  when you're going to acquire a long-term lock.  We provide priority propagation for the exclusive access,  because that's just what turn-styles do.  We do not provide priority propagation for the shared access, in this case.  So if you are, there's a bunch of readers and a route comes along,  and the writer has a higher priority, well, they still have to wait for all the readers to go to give up,  but we don't have any way of knowing who they are, so we can propagate the priority to it.  Consequently, if that's going to be an issue for you, you need to use some other mechanism.  We also, in this case, allow you to specify that it's okay to recurse.  And normally on mutex, if you recurse, that's a no-no.  This recursion, of course, is referring to the exclusive access.  Finally, in this class, we have the read-mostly locks,  and this is, as pretty much the same property as the reader-reader locks,  except that they add priority propagation for the shared access.  So if you need to have the priority propagation, we can do that here.  And the way we do that is that the shared owners provide a tracking data structure.  So much like you provide a term style when you're blocking,  if, in this case, you have to provide a little data structure that we can then link together in a big long list,  so we now know who all the readers are.  And so now we can do priority propagation because we can just run down that list.  Now, when you call in to do a shared access lock,  you also have to pass in a pointer to this tracking data structure.  So if it's an issue where you need to have the priority propagation,  then you're going to use these kind of locks.  Now, the notion of this is that we're designed for fast access for readers.  So shared access, assuming that there'll be relatively few writers.  And again, the idea is, so if you have it mostly just reading,  and you're not going to be writing it very often, then we'd like to have sort of a fast path for reading.  So in essence, what we do is we read without a lock and then see if any bad stuff happened.  And if it did, then we have to back up and do the whole thing the hard way.  The writing table is a good example of a read mostly data structure.  So for example, we don't actually add new routes very often, we mostly just look them up.  And so the lookups of that go quickly.  When you do an update to the routing table, of course, then you get a big burp.  So if you use one of these in an instance where you have a lot of writing going on,  it's not going to be inefficient.  Now, the best way to implement this is actually patented by IBM.  RCU is the magic word there.  Now, IBM allows anyone with GPL code to use their patented implementation at no cost,  i.e. Linux meets this criterion.  But previous D is not GPLed, so we'd have to use a somewhat slower technique to avoid doing the patented way of things.  And there was at least no approach to...  What? No, no, not for a while.  There wasn't actually an approach to IBM, but their attitude is,  well, it would be pointless to have the patent if we let all of our for-profit competitors use it  and we want it to be out there.  And so I don't understand where they're coming from, but it's kind of a pain.  Okay.  So that's up to now.  There are things that are the short-term type locks.  Locks that you can only hold for a short-term basis.  You can't hold them on a long-term basis.  Now, starting to the locks that are the long-term locks,  the fastest and simplest of these is the shared exclusive locks.  And surprisingly, they provide shared and exclusive access.  You can specify that you can recurse.  You can also indicate that if a signal comes in while you're asleep,  you would like to wake up and handle that signal.  It has, I'll just say, limited upgrade and down-date grade capabilities.  And like all sleep locks, it does not implement priority propagation because it's pointless,  as for the reasons I described earlier.  You'll still see a lot of people doing explicit sleep and wake-up in the system,  but it's typically things like demons that are just sort of ping-ponging back and forth.  Like the demon that does swapping or paging or whatever.  And it will go to sleep and then when whatever someone decides they need it to run,  they issue it to wake up and it does some stuff for a while and then it goes back to sleep.  And so those sorts of sleep and wake-ups you will see just written as sleep and wake-up.  But in the sort of traditional way, for example, the code that I showed you at the very beginning,  we wrap all the business about want flags and lock flags and so on,  and then we sleep and wake-up parts inside these condition variable functions.  And so you'll see it being used in that way, the CV under type stuff.  So it allows you to wait on an optionally timeout so you can say,  well, I want to sleep, but not longer than five seconds.  Or if a signal comes in, I want to be interrupted, or I don't want to be interrupted, whatever.  You can say, when you do a wake-up, do you want to wake up just one of the ones that's waiting,  when you're waiting the longest, or do you want to wake everybody up?  That's what a historic behavior.  And you have to hold a mutex before awakening or waiting.  And if you're about to wait, the mutex is released as part of going to sleep.  And I didn't really describe that aspect of it, but if you think about it,  you need to get a mutex to check like the want and lock flags and so on.  And that way, that's tight to be able to change before you get completely to sleep.  Because if you release the mutex and then called sleep,  between the time you release the mutex and the time you get to sleep,  someone else might have run an issue to wake up.  But since you haven't gotten to sleep yet, there's no one to wake up.  Okay, no worries. But now you go to sleep, and there's no one that's ever going to issue you a wake-up.  And remember that forever word, which we really don't like.  So the issue with the mutex is you hold a mutex, it's actually passed as a parameter to sleep.  And it says, when you have gotten to sleep, then release this mutex.  And normally then it's reacquired when you wake up, although you can set a flag to sleep.  It says, I don't really need it when I wake up. Yes, Julianne?  I'm not so convinced that you need to do the lock-file. You're doing a waiting and a moment-file.  You're doing a setting of what's consuming more cars.  I know you do under some, some, some, some,  I'm not sure if that allows to do a 64000 without having to hold the lock.  Okay, well, I will check that, since I want to get the textbook right, of course.  Okay. So we finally got to the most full-featured, awesome, all-dancing lock manager locks.  These are, you can, you know, jump through hoops and do all kinds of exciting things.  Show you an exclusive access. You can recourse.  You can request a timeout or an interrupt by a signal.  You can do upgrade, downgrade it, upgrade it, what's called an exclusive upgrade,  which says, I have this shared lock. I want it to be turned into an exclusive lock  and bound around it. I don't want anyone else to get an exclusive lock between when I ask for it and when I get it.  And if someone else somehow manages to sneak in and get the exclusive lock  before I get it, then you need to let me know that,  so that I can potentially have to go back and check things again.  Okay. Why is it the boundary to pass the ownership of the lock from the thread to the kernel?  And this probably sounds a little bit weird. Why would you want to do that?  The issue here is that normally, if you hold the lock, your thread needs to be the one that releases that lock.  And if it's not, if I lock it and one of you unlocks, it's like, oh, now wait a minute, you're not supposed to do that.  That's not you unlock. That's my lock. However, there are times when I may not even be around anymore by the time it needs to be unlocked.  So for example, I'm running out of a bunch of blocks of a file,  I sort of close the file and eventually its blocks need to be written out,  and I initiate this, but I don't actually wait for that IOTA to complete.  And in fact, by the time the IOTA is completed, I may be completely exited out of the system and not exist anymore at all.  And so now who's going to be able to unlock it?  So what ends up happening is if I'm sort of disowning it, I'm handing it off to the IOTA system,  I turn it over and say, well, I disavow knowledge of this, I'm not in charge of this anymore,  I'm just giving that to the kernel. And now something like the G up thread of GOM or the interrupt thread for the device or whatever  can be the one that ultimately unlocks that at the end of the operation.  And that thread is a kernel thread and it's owned by the kernel, so all is happy and we don't get any panics.  We've been deprecating lock manager for a decade, but it just has enough uses that it doesn't ever seem to quite go away.  And like all sleeplocks, it does not implement priority propagation.  And also I think that lock manager cannot start, normal shared lock, so it can start right there.  Yes, so the comment up here is that the reader rather lacks here, or the shared exclusive lacks here.  What can happen is that if there's enough people coming through and using the shared ones, you can starve an exclusive access.  So because of course you can't have exclusive access to all the shared ones go away.  And if we just keep handing out shared ones all the time, you may never get to the point where the exclusive guy gets it.  With the lock manager locks, once there's a repending request for an exclusive lock, we will not allow any more shared locks to come in.  And so they will at some point drain away, so we do in fact ensure that the exclusive access can happen.  It's not like one of those is correct and the other is not correct, they're just different algorithms and you need to know what they are when you're deciding which kind of lock to use.  Okay, so how do we make all this stuff work and play well together?  Well, in the old days we used to just sort of know that you had to have this kind of lock before you had that kind of lock and what all the correct orders were of everything.  And it was a little documented in the comments for the most part when they were up to date and written.  And it kind of sort of worked okay when we had single threaded kernels.  But once we started getting all these mutexes and you have just an explosion of the number of locks that are in the system, it becomes virtually impossible to really know what the correct ordering is for the locking without getting yourself into deadlock.  And deadlock is another one of the situations which is rather unpleasant.  So there's essentially two ways to deal with deadlock. One is, and believe it or not it is the way it was historically done, not in Unix but in some other operating systems, is to essentially have a deal and it waches for deadlocks.  And when it sees a deadlock it just goes, hmm, those two threads are deadlock.  Well, I'll just shoot that one.  Deadlock's out.  Unfortunately the one that was shot was your Emacs editor that you hadn't saved the buffer for, well, never mind.  So the approach that has been used in Unix since the beginning of time and still used today but is now being checked by the witness code is what's called partial ordering.  And the idea of partial ordering is that we put the locks into classes. So we have class one here is all of the, all the one locks.  So there's R1 and R1 prime and R1 double prime.  And then in class two we've got R2 and R2 prime and R2 double prime.  And then there's just two very simple rules.  You can only have one lock at a time in a class and you can only acquire a lock in a higher numbered class than the one you already own.  So we have two threads here A and B and A comes along and gets lock number one here and thread B comes along and gets lock R2 and so forth and that's fine.  If you only own one lock there's no possibility for deadlock.  But now thread A comes along and wants R2.  Well that meets the criteria and it's in a different class and it's two is higher than one so that's all fine.  But it gets locked because thread B is holding it.  Well now thread B locks R1 over here.  Well that's, if we just, if we just tried to get R1 we'd now be deadlocked because they each hold one and they each want the other one and we'd be stuck.  But thread B realizes oh R1 is a locked class, numbered class than the one I already hold.  So I can't do that, I have to temporarily give up my R2 then go back on R1 because thread A's already got it.  But now thread A is going to be able to get R2, then it's done and release them and now thread B will be able to get R1 and then come back and reacquire R2 and everybody's happy and we have no deadlock.  Now as I said, you know this was just sort of a non-thing and everyone sort of knew what they were as well as in the old days.  But that, with the addition of SMP just became untenable and so the witness in code came into existence to actually help out with this.  Now absent the algorithm I'm about to describe, someone has to go along and figure out what these classes are and what the ordering is.  And while the programmers have some idea of that, it's a little bit tenuous to expect them to do that with every lock in the system.  And so in fact what happens is, although you can sort of pre-define certain classes and what's in those, for the most part witness just figures it out on its own.  It just sort of comes up and it watches the order in which things are used and it boils its own notion of what the hierarchy is supposed to be.  And then when it sees a violation of that hierarchy, it complains and puts out the well-known LOR kind of thing.  It's like you acquire this lock at this line of this function and this other lock at this other line of this other function and you can't have that one while you hold this one.  You got to be the other order.  Now you'd say, well how can it possibly figure all that out?  Well the answer is that, and get it right.  I mean what if it gets it in the wrong order?  Well first of all you shouldn't be programming in the wrong order.  So the right order should be sort of what's there.  And it turns out by the time you've gone through the start-up code most of the interesting locks in New Texas have already been created and so been used in the right order.  And so witness more or less gets it right and you only need to do a little bit of strategic identification, pre-identification and it all just kind of works.  That being said, we still end up with a lot of lock order reversals which in fact may not ever really be a problem.  But there's the LOR mailing list wherein people spend endless amounts of time debating how best to fix these things.  Certainly it is a constant headache.  But at least you know that if you're not getting LOR messages you're not going to be getting deadlocks in the system.  And in fact, you know, previous to you sort of known as a system that's not prone to deadlocking unlike some other systems.  And the witness is a large piece of why that is.  The witness is also extremely valuable when you're jumping into a piece of code that you haven't worked on for a while or maybe never worked on.  And so you don't really know what the order is but you very quickly, it gets pointed out to you.  And specifically while you're doing things and where the order is running, figuring out how to fix that can often be a little more difficult.  But as I say, once you get it fixed, it's fixed and you just know you're not going to get a deadlock, at least from that.  Okay, so that is what I have to say.  I meant to put these slides up and I went to do it last night and I couldn't quite get it to work so I need to talk to Dan.  But I am going to put these slides up on the Wiki or the webpage or whatever it is and I will have about three minutes for questions.  Yeah.  You can certainly get witness to dump out the state of all the ordering rules that it has.  John, do you know the answer to the first question there?  I don't think, I'm going to be sharing my people at work.  Sorry, everybody, this is the first thing.  Yeah.  So we have the locking man page, which basically covers all of this, which I wrote.  I was trying to understand what the hell was going on.  And I still do not quite sure it's all correct.  So the next time anyone wants to write a chapter on this and needs to learn it all, they should  go to the locking man page and they should.  Update it?  It's just everywhere it's wrong.  I'll take that under, I have two more to do list here.  I actually asked the, I asked John many, many times, many times to edit that page and just check it with the sender.  Yeah, well that was one of the first places I looked when I went to write the chapter and I only went on two or three wild goose chases, so.  Well, if I'm wrong, the I is your friend or he next maybe, because he was written by me that tells you how much to trust him.  Yes.  The conditional variables in the lock manager locks these signal or unified semantics when you're waiting on your cell.  They are using the wake up primitive in the system, so they identify whatever is the thread that should be awakened and then they issue a wake up to take it off the sleep queue and put it on the run queue.  Right, all the wake up does is put you on a run queue and then the scheduler will decide when you get to actually run.  It might run straight away if it's quick security.  Right.  Okay, anything else?  Ha, I've stunned them all into silence.  Thank you very much.
AnOverviewofLockingintheFreeBSDKernel_0_131.png AnOverviewofLockingintheFreeBSDKernel_132_6455.png AnOverviewofLockingintheFreeBSDKernel_6456_11171.png AnOverviewofLockingintheFreeBSDKernel_11172_11723.png AnOverviewofLockingintheFreeBSDKernel_11724_12923.png AnOverviewofLockingintheFreeBSDKernel_12924_13403.png AnOverviewofLockingintheFreeBSDKernel_13404_13487.png AnOverviewofLockingintheFreeBSDKernel_13488_15227.png AnOverviewofLockingintheFreeBSDKernel_15228_17867.png AnOverviewofLockingintheFreeBSDKernel_17868_18623.png AnOverviewofLockingintheFreeBSDKernel_18624_20315.png AnOverviewofLockingintheFreeBSDKernel_20316_25847.png AnOverviewofLockingintheFreeBSDKernel_25848_28403.png AnOverviewofLockingintheFreeBSDKernel_28404_28511.png AnOverviewofLockingintheFreeBSDKernel_28512_31091.png AnOverviewofLockingintheFreeBSDKernel_31092_32219.png AnOverviewofLockingintheFreeBSDKernel_32220_36923.png AnOverviewofLockingintheFreeBSDKernel_36924_40043.png AnOverviewofLockingintheFreeBSDKernel_40044_42191.png AnOverviewofLockingintheFreeBSDKernel_42192_46247.png AnOverviewofLockingintheFreeBSDKernel_46248_47507.png AnOverviewofLockingintheFreeBSDKernel_47508_49919.png AnOverviewofLockingintheFreeBSDKernel_49920_51623.png AnOverviewofLockingintheFreeBSDKernel_51624_56003.png AnOverviewofLockingintheFreeBSDKernel_56004_56063.png AnOverviewofLockingintheFreeBSDKernel_56064_56543.png AnOverviewofLockingintheFreeBSDKernel_56544_57155.png AnOverviewofLockingintheFreeBSDKernel_57156_64619.png AnOverviewofLockingintheFreeBSDKernel_64620_66335.png AnOverviewofLockingintheFreeBSDKernel_66336_71518.png