Lock-Free Queue Correctness: Generation Counters & Memory Ordering

[00:00:00]ah at one point in time this talk which is now part two of n or part 2.4 or so because I've given various versions of this but it started out as part one was an overly complicated lock freak you got simpler along the way which was good started getting more complicated I don't know we're somewhere in the middle Oh before I even start anything I always let people know that this is the stuff I really work on take a bunch of projectors and you turn them into one projector do it on flight simulators do it on great cars that's a great car car looks like that so he projected on it gives it color and this was WOW this is the short version of my have more examples now than last time and that's basically what we're doing is doing magic that's like a giant building that's been projection mapped cool stuff like that anyhow I'm not talking about any of that so someday someday maybe I'll give a talk on that a guide to threaded coding stop sharing this is forget you know kindergarten you learn to share no don't do that if you have to share okay we'll use locks and one I added recently because people keep I forget that people forget don't call unknown unknown code while holding a lock that includes a virtual function or any you know callback which is any time you write a kind of a signal slot observer thing you will like have a list of observers and you'll lock that list and then you'll iterate over the list and then one of those guys will grab another lock and you'll deadlock so don't do that and then you should measure your code and measure code again because the first time you measured it was wrong it's guaranteed when you may try to measure your performance of anything then you change your algorithm then you go back to one and most likely changing your algorithm involves share less share less data you'll notice that that algorithm loops forever and you never get to lock free lock free is the last thing you want to do if you do somehow decide that you can't get any more performance or I should mention lock-free is also really good for you know you don't get deadlocks it's more robust if a thread dies that's okay even if someone does stupid things like killing a thread which you should never do a lock free algorithm can deal with that but if you do get down to the lock free don't forget to measure again because there's no guarantee that the lock free algorithm is any faster than just grabbing a lock so basically don't share and use locks almost you he'd take my joke away actually rules of lock free coding was the first rule of lock free coding don't talk about Locker coding now we're done good break that break that rule I also have a guide to coding well I'm well I have a room full of people who you know are stuck listening to me so I'll take this opportunity macros are evil has nothing do with my talk either but I just thought I would put that in and any chance I get John Lycos is allowed to leave use macros it's he's the exception he gets mad if I say don't use them in my slides I'm not gonna write out compare exchange week or compare exchange strong cuz that is way too many letters I'm gonna write Kaz cuz before we had standard compare exchange that's what that's the way I used to spell it and also my slides are gonna have code just crammed right in and that's not using my coding style but it's got to fit on slides so anyhow we're gonna talk about this MP mcq which means multi producer multi consumer cue so you have multiple threads putting data into the cue John you just miss the common man I you're talking about you it's good it's okay man and we have multiple threads pulling items out of the queue and what would probably be a much better idea is to have separate queues and have mostly single thread per queue instead of and maybe a little bit of sharing when necessary but this kind of queue where everything's going through one queue what's that cute look like that cue looks like a bottleneck so you probably don't want to put everything through a single cue but also a cue with some sharing and whatnot is kind of a multi threaded multi producer multi consumer cue so maybe you we make this cue and then we use it with other cues and kind of spread out the sharing and try not to share in all three one cue avoid the bottleneck anyhow this just burned this diagram in your head because every slide is gonna have a version of this diagram on it I gave this talk a couple years ago here and I did the first version of this and we only got so far so I'm just gonna do like five slides of where we work because I don't remember and you don't remember where we were but basically we have a cue that has a head and a tail it's like every cue does but what how is this cue implemented so you can implement a queue a million different ways you could use a linked list inside of there or something like that but who would ever do that this cue is going to be a contiguous cute right so there's there's this is kind of theory cue this is you know real real memory address cue and it's gonna have a buffer of things on a head and a tail something like that and it's going to be a circular queue such that the head is now over there and the tail is on the other side okay and our first compromise is it's not a queue of T's it's a queue of integers because that's a lot easier to deal with and this will be a lot like one of many compromises which I like to call a compromise ation because it's a compromise for the sake of optimization which is obviously a real word word if you look it up in Google you'll see the indistinct you theny hand a tea without comped amazing the historic pitar file of the existing tetanus tetanus yeah I just like to make fun of Google whenever I get a chance their first result was did you mean compromise ation and there is one actual use of comptes ation in low frequency radiation something something something so so this this worst part was this is the same joke from two years ago and you can still find not exactly the same things are found but you get the same answers as like second third answer so someone needs to work on their OCR anyhow just to avoid people bringing it up there's this idea of false sharing where if I have head and tail and I want to eventually make those atomic and do atomic operations on them an atomic operation on head might interfere with an operation on tail because they're side by side in memory so what we probably do is put some space between them so they're not on the same cache line and now just forget I said that so just pretend that I did that and if necessary pretend that I did that inside the queue and you can think about later whether it's necessary to do it in the queue and how could we avoid doing it in the queue so the first weird thing about this queue I had you know that we started last year was that the head and tail don't point to the actual head in actual tail they points they tend to point somewhere behind the head and tail and they're just kind of head and tail ish they're nearby and the idea is that you get the tail and then you go looking for the head knowing that it's near where you are and you just find you know you see some X's for you.when tail is trying to look ahead it sees an X other's data there others data there oh here's the first one without data that must be the real tail and head does the same thing it's sitting somewhere on non data it has to find the real the real data so of course what do I mean by non data I've got X's in there I have to have something in those blanks right well let's put zeros in those blanks that's another compromise ation you can have any numbers in this queue except zeros right everyone's okay with that who zeros I mean who wants a zero as you could imagine if you wanted to start putting pointers in here someday no pointers you know special special case so that's another compromise ation and we have this other problem though look at tail there's trying to find the first non data and if tail is so far behind that the queue has you know there was some queue here some other threads went along kale didn't get updated because for some reason tail was allowed to not update the whole queue can fly by and tail is now so far behind that it looks down and says oh there's the first nonzero whoops that's the wrong nonzero cuz tails supposed to be on the other side alright what are we gonna do about that we need to tell the difference between that zero over there and this zero over here negative zero let me get one how would we just use one so we'll just take another compromised ation and we zero in one who you know who uses one that's it's not a worthwhile it doesn't do anything you multiply by one that did nothing right don't need a one and and then of course we're fine now right until the queue starts going around and now we get ones and ones and we have the same problem as having zeros and zeros so yeah let's start using twos all right so on one hand you can say I'm going to you know keep going up the thing I'm going to take away half your numbers that sounds like a lot but look at it the other way I'm just taking a single bit what's one bit right you didn't need that good so yeah how big is that optimization that Compton ization it's a it's a compromise but well at this point optimization means works are not so you know any customization goes from non working to working is a good optimization so there we have the black is real real numbers and the red is not real numbers so yeah imagine that the red numbers are negative and the the real numbers are positive or if you don't want to be a scientist you can have all negative numbers in your queue and I will put all positive numbers in my encoding of the key or something like that take your pick so yeah it's only one bit and last time I'm sure we all remember last time I showed this queue I had this other comforta mise ation where I put the the kind of like this generation count inside the tail fair so I kind of just stuff it in there maybe make tail there bill a little extra big or whatever is stuff that that data in there and oh yeah right this so this is this is kind of where we left off and last time and and last time I gave this talk it was all about walking through the forest because I used to do this I used to work a blackberry and behind the behind the building was a forest that would take walks and all my work on lock-free programming is done in my head while walking because if you have a lock-free problem that has more than a couple of variables that you can't keep in your head you're not gonna get it right so you might as well just do it in your head I hardly ever put it on whiteboards or anything it's just you need to be able to think of all the states you need to keep it all in your head anyhow so and it's also like you know you're dropping off the kids somewhere you're like okay I've got five minutes what are you doing dad oh I'm working except for don't do luck for you at work so it's it's it's a it's I guess it's a hobby it's kind of a weird hobby so any I used to take these walks oh and I I did these walks through the woods so many times and then one time I turned around and noticed that there's a poison ivy sign it's like after like at the end of my walk I turn back it's like Oh poison ivy which is kind of a good you know analogy to lock-free programming so you just stay on the path and you avoid poison ivy and then and then you know that's that was the rim buildings actually the BlackBerry buildings here we got we MIT this is where we left the the story last last time and so that's kind of the end of the review and that's kind of where we left off and now we're going to take a deeper a darker path through the forest I guess so that's kind of the end of the review so we've got head looking for the real head we've got tail looking for the real tail see what my notes actually say and and this one's because it's wrapped around you could like head is actually going to the far side and tail is going has to go all the way around to find the real tail here's an unfortunate same problem first data found his real head like nope same sort of problem we had with with tail thing his last time I showed this whew we never got to dealing doing anything with head it was all about tail so it seems like we have somewhat the same problem so we're gonna have the same kind of we need we need to tell the difference between the X's over there and the X's over here all right so we need to find not just the first data we need to find the first data of the correct generation so now our Q is actually going to have a generation thing that we keep track of and we're gonna have to do this again we're gonna have 5s and fours and now I've compromised the not just I'm not taking away half your numbers now like I'm not just saying when there's no data I have a number and now saying when there is data I have numbers I'm not taking one bit anymore and taking half your bits so is this a kind of a big not worthwhile Compton ization well I'm gonna say that usually I can take two intz so now my buffer is full of 2-inch and you know make this little entry structure it has data and it has a generation and I'm just gonna say you can lock free that right 64 bits probably you can still do lock free operations you've got a system where you need you know bigger system well maybe you have bigger lock free things you could maybe a lot of systems you can do at least maybe not 128 but you do 96 so you could have 64 bits of data and and 32 bits of count or something like that it's like if you have a tiny system where you've only got like 16 bit pointers or something like that well I bet you probably don't have big queues then either right so is this the customisation oh wait no we still have we still this other compromise ation we still have zero I still I still need to know not only what generation of data is it but is the data zero or non data which I could just as easily hide inside the number or the data but conceptually it's just easier for me to think generation is generation data is there or not so so now we have tails looking for the first zero data of the correct generation and head is looking for the first nonzero data of the correct generation so tail instead of if generation you know we're kind of thinking we're on generation four here so tail starts here and won't stop on this zero it'll go around increment itself like you have to assume that when we when we rap we up the generation and it gets over here and I'll find zero five and they'll be the first zero five and tail will be happy and head will do something similar and find the it'll skip past it'll be looking for x4 you know skip past x5 and then it should find each should find the right place so I should probably do all my slides in the weird cases where like we're wrapping around everything just to keep your brain working but I tend to make my slides look like this where it's all nice and contiguous and it's kind of a simpler case so this is you know tail is looking for that tail which is just beyond it and head is looking for the head which is just beyond it and this is a problem we ran into last time where you're pulling data out of the queue which is pac-man eating the he's eating the things out of the queue and you get to this point where you're going to eat the last item in the queue right and then after that you're going to move head forward and head and tail will be in the same spot and then you start worrying about shouldn't I keep head less than tail and that was actually a huge problem last time I gave this talk and there's like all these ugly ways of making head less than tail but now that I have you know I've put this extra generation count in in the inside the queue head is now looking for eating exactly not just a piece of data in the last piece data was looking for X for head can come along find X for update like take that X out leave it leave a 0 5 and now it gets to 0 4 and head can actually see whoa wait a second there is no data it doesn't have to look at where tail is to figure out that the queue is empty you can see by the queue that it's looking for data of X and 4 and there's just there is none because you already ran into a 0 4 and can you know yeah you have to trust me that if you see a 0 for the rest of 0 4 is and No x4 so now the good part about this is that head can see what's going on without comparing itself to tail and the queue is empty and head and tail we don't worry about because it's not a problem anymore and we have this case in the general case before I put the extra number and we had this problem with same problem when it got full you can see where tail is you can see where head is right there's one spot where the next item is going to go that's what tail is pointing to and head is pointing to the first entry soon as you put that one last place in and now you look at a queue that just has X's in it you once again no longer know where's the beginning where's the end so now that I put this numbering system inside I can see that it went from five down to four I know where the where the queue is full and where the start and end of the queue is right so head is looking for X for it can find it tail is pinky y'all know you have to know the names of the ghost right it's important for the talk pinky is looking for a 0 4 to find the find the tail he finds he can look around he'll find nothing even if he looks through the whole thing he realizes wait there's there's there's no room for 0 4 so they can both independently tell that the queue is full oh yeah tail will probably go off come back around 2:05 still looking for a 0 4 somewhere because tail is looking if tail sees a 0 for it thinks that's are an X for it it thinks that somewhere along the way there still be 0 fours so it looks forward and it looks for wraps around it updates itself to the saying I'm looking for 0 5 now and it will get back to a 4 and go whoa wait a second I'm on a generation B I've gone around I'm on a generation behind so yes there are so many slides ahead the question is why do you need a head and tail pointer so this is this let me go a couple slides and I will answer that even better q is full so this is yeah one slight your at least one slide ahead of me so is this the comptes a ssin and my answer is no this is an awesome ization that we put the numbering in here because exactly what he's saying is all the information is in the Q head and tail can be anything you can just look at the Q walk through the Q and find the right answer head and tail are just more they're not comp timaeus they're just optimizations it's like you probably want to start looking from where you left off and also particularly the generation because you could actually do this starting at generation zero at the beginning of the Q and just start looking and wrap the Q until you get to the right generation but that seems kind of you can also that there's we can get into a big discussion of like how can I look at the front of the queue or the back of the queue and know what the generation is do I have to look at both the front and back of the queue to know what the generation is like oh I see a five I see a four but when I see the five and I go look at the four it's no longer a five you can't see both ends at the same time there's lots of things you can do and I constantly play around with which ones I like the best but that is the crux of this whole queue is that everything you need to know is in the queue not in the data structure that's maintaining it so we should do some Thomas ization because right now I have integers so because the data the important information is in the queue the queue itself has to be atomic and and not just atomic it's gonna be atomic with with some sequentially consistent or acquire a release or something it's gonna have some important memory ordering on those because that's where the real information is and I like I said I'm gonna assume that that is small enough to make it atomic and and still be locked free and then the head and tail ish I'm going to use a lack stomach which is some word I made up what is it what is a lack stomach it is well if it who's seen herbes that atomic weapons of mass destruction it's actually just called atomic weapons but yes so he says you should never ever use relaxed Atomics and I completely agree so that lacks atomic up there is a class where you derive from atomic and change all the functions to be relaxed yeah cuz why not right this the purpose of this talk is to convince you not to do atomic operations so is that okay I am tempted to say you know just argue right here hand waving that's okay because like I said head and tail are hints they're not the real data so using relaxed Atomics and getting you know this answer that has no dependencies on other information it's like it's not there's no there's no real information head and tail it's just like look at that look at the cue to get the real information so I'm going to claim roughly that it's okay to make those all relaxed and and kind of explain that a little further in normal if there's anything like normal lock free you you know you have some data it's got an axe you said it's got a why you set it and then you set a flag saying hey this data is ready right and on the flag you set you use a memory order probably you should just use sequential consistent but maybe you use memory order release because you because that's typically what you use when you're publishing some data I've wrote some data I tell people that I wrote the data so I publish it on the other side you look hey is there some data ready you do an acquire because you're going to acquire some data and then you can read X&Y and the whole thing is that the release on this side means what's the meaning of release and you can read likely this huge thing in the standard release means before means before so if I have two lines of code before the release those two lines of code are before the release of course you're probably thinking isn't that always true right but isn't that how code works it's like no code does not work like that at all in normal code that X setting X could have drifted down below the setting of the ready person you know there's no there's no real ordering on a single thread and the standard and your processor both assumed that there's only one thread in the world it's kind of funny that the processor assumes that since it knows that there's another processor sitting beside it and has multiple threads inside the processor but nonetheless they go well 99% of the time you want me to assume that there's only one thread and most of this stuff isn't really ordered because from your one thread you can't tell and if it didn't do that processes would be like literally a hundred times slower so it's a great thing that a processor goes I'm just gonna write these in whatever order I want it's a great thing 99% of the time and there's one percent of the time you say wait a second I really mean these must happen before that you use a release on the other side you say I can't read this data X before I check that it's ready there's also an if statement in there that has some logic but you know think of like speculative execution and other were strange things you want to say look this has to happen after that you use an acquire so if you put relaxed in there this would all break because of that this the ready flag isn't a thing of its own it's a thing that has a relationship with other data that's the important part the ready flag will be completely consistent on its own it'll always have the right value but it won't guarantee the other values unless you use the right memory orders so the question is what other data does what not what data does head and tail rely on what data relies on head and tail and it turns out there's none because all the data really relies on the queue that's why I can make these relax there's just hints so we make those two our etat are these relaxed Atomics and i'm gonna stop calling them head ish and tail ish which right i now think that was a mistake i should all my slide should say head ish and tail ish because otherwise you forget and i'm a big guy on on proper naming the proper naming for these variables its head ish and tail ish to remind you every time you see them that they're the they're the they're not really head and tail but i wasn't gonna go through 100 200 slides and fix that sometimes someday will so then the next question is I have this generation count should it be atomic relaxed atomic you know what is it and I'm gonna say same thing the generation count that's inside the cue that's in every entry that's got to be a strong atomic in the entry but the generation of what generation that are head and tail in that can be relaxed it's the same thing it's a hint now we might have a situation where head and tail are communicating through generation maybe there's a dependency between the those three variables so that's something we have to watch out for but right now I'm gonna say they could be relaxed so that's our class so what does push look like and and it's often in these talks I'd go like one line at a time and I build up the function now here's the function but but it's very small function so why not you load up some your your variables into temporaries you got a temporary generation count and temporary tail and then all you're doing is walking like I said you're just going to walk through the queue with that is 0 to find the find a 0 and it's not just is it 0 but is it 0 of the correct generation right and because that's a relaxed atomic on most platforms that is free that's just like not even doing an atomic you just you're searching for through a queue for an integer it's like whoa that's that's pretty fast right it's very close to the same okay and then if we don't find it we increment like in that what the first while loop there and our increment just has to make sure if it goes off the end it comes back to the beginning updates the generation and then if we do finally get there let's see I actually had slides for this blah blah blah like I was just saying we walk through we increment that one's not zero yet so we increment again this one is zero or like great we come down here and now even though we just saw that this was a zero on this next line of code what is the number in there well we have no idea because it's a it's multiple multiple multiple threads so someone else could have changes value so when we get to this point we have to do another atomic operation we have to reread that value and say hey this was zero just a second ago a zero four is it still a zero four and now we're going to do it with a Kaz because it's like if it's still a zero four then I want to put X there right so we do a Kaz on and we leave entry is our is our new what we want to put in there whatever value came into the function we're pretending it's a I guess we don't know what it is some value generation is gonna be four and this is not relaxed so we put our P in there for pinkie and we're all happy right or what Michael warned me about this thinking or we came here we went to put a value there and we found a C in there for Clyde told you you had to know your your characters and if that happens the while loop will will you know the the calves will fail that's why it's in red we jump back up to the loop and then we just go over again we just like okay go back to finding a zero and this is the fundamental nature of lock-free programming and the actual the term lock-free is that you only fail when someone else came around and did something that succeeded in this case Clyde aah aah sloop is what I tend to call these things ACK as loop who will relook on progress right someone made progress so you fail and you loop around again a spin lock loops on progress if another thread is making progress it also loops if that other thread is doing nothing because it's just waiting for a flag to tell me that other thread is done but that other thread got got shut off by that by the scheduler or something that spin a spin loop a spin lock will still just wait no one's making progress a kaz loop will only loop back if someone else did something that's that's lock-free right that if you look at Hurley he's definition it'll say a thread made progress guaranteed either you made progress or someone else made progress someone got in your way because they were making progress not because they just stole a variable and told you to wait so we will again see see that there's a value there now we will increment look at the value but got a zero and then we have to do this one more time and then maybe this time they succeed and now we're happy are we happy when do we increase the generation of in the the variable that's like not in the not in the queue not inside the cube of the generation variable in the also when do we increment tail because I mean it's so far I've been incrementing temp so exactly it will increment the temporary generation of the thing walking around but the the real thing that tracks the generation at the end of the day isn't being in committed yet so that's one question is we have an incremented tail or generation turns out this would still work because we had always started at zero and we would go through five times to you know or whatever we had to do or a hundred times the best the best part about that yeah now the scary part about that is if you wrote tests for this and you forgot to ice those tests would probably all pass and those tests would probably be small enough that you would never notice that every time you add more the cue just gets a little slower every generation the cues a little slower and you're like I don't know what's going on just a little just a little bit slower so so here's the thing you know there's that question of we didn't update some stuff but there's also other questions like what about this case right we just did one case it was a simple case of being you know inside the X's when we started here's the case where we're inside the zeros already but it's a zero five we're looking for a zero four well I'm jumping back and forth sorry maybe I don't even know what I was trying to say there cuz I think I say that okay I'm just gonna go on I will get back to that I know I know there's more slides for them that question should we update Generation tail so let's say yes let's just say we magically update those variables for now and now I wanted to mention what about this case what about when it's wrapped around and we got to get to the other end and I'm gonna go fast because I was told I'm already a half-hour in it's going to correctly see the is 0 is fail Italy hopefully do the wraparound in the increment it comes around it lands in the right spot yeah it still works here's another example what about four right on the edge it's always a good question to check that there's no X before the first entry but it's way on the other end and I'm going to claim yes it will find the the right spot as well because temp starts at zero again it gets to the right spot but then what about this case you've got nothing in the queue there's no X's and I'm going to claim that whoa what happened here oh the empty case sorry empty case works right away just like BAM you can find that really quickly how about this case where tail is past the real tail right the real spot we're looking for is that zero first zero for but we're already past zero for and now we come into the code and go let's look for a zero for what happens I think you already saw me put an X on the screen it doesn't work hmm anyone it appears not to work because we come into this while loop and we'll search for zero will find that zero four and it's the wrong zero for the question is how did we get to this state where tail is ahead of the real tail this is this is when the one guy Sebastian one second and he's like that can't happen just instantaneously he's like that's wrong it can't happen can't have tail past the real tail and I own a claim that is an invariant tail with the right generation will never be ahead of the real tail with the with the right generation you can you can always see have them pointing past each other but not with the with the right generation so oh my claim why this works is because the temp always increments past the tail variable is here temp goes forward and then you set the real tail based on temp so real tail is always lagging behind there's no decrements in the code anywhere it's kind of part of it you have to think about multiple threads what each thread is doing but you kind of get this feeling of it's always going forward and they go forward even when they wrap around they still go forward man I got to remember why I highlight things that's that's where it gets written into I just get skipped that that's where generation gets written so it's it's also ahead of tail being written because update isn't being called yet then update happens before the rest now because once again tail and generation are just hints so I'm going to click question actually I'm gonna solve that later anyhow so I'm gonna feel I have to go quickly here how far behind can tail actually be like can tail be at 0 3 and we don't have any threes at all gonna claim yes it can happen it happens if that whole do-while loop happens a lot by a lot of threads so the queue gets full of things and we never know thread gets to update so the queue can get really full and tail is miles behind it can be like 10 generations behind probably not but it could and that will be a case where it's gonna be like over over looping which you could optimize by by looking at how far behind you are so you know is there an invariant that generations at least for it that there isn't and there doesn't have to be it doesn't matter so I'm going to claim this case is fine because it never happens that tail is on the wrong side oh this is another edge case that you know tails on the wrong side it's all empty and I'm gonna say oh that's the actually the same thing where that can't happen because in the invariant so we're good this case and I think I know when I'm high changed just going over the edge cases again ah right this is the last edge case of course I leave that last edge cases for a good edge case for last the queue is full tail is looking for zero for we're at X 5 will go will go along looking that's not I have more slides for that we go along looking for X 0 for and we don't find it so we'll go around now we'll start looking for 0 5 we won't find it then we'll look for 0 6 and we'll look for 0 7 and we'll just go on forever looking for that value eventually we'll wrap the integer overflow the integer and then we'll start you know maybe it's some event you know you is another one where this code could just keep running because sometimes there will be a zero in the buffer and at some time you will wrap your integer enough that you'll find that zero probably not what you want so I'm gonna stick a little bit of code in there that says if the entry that I'm looking at is a lower generation that I'm looking for then I know that I'm done like so I will start looking for zero four and I'll start looking for zero five and I get to hear back to four again I go whoa I'm going backwards in time now so I must be done and I know that the queue is full so I returned queues full or I do it depends what you how you want to do it but let's just say I returned queues full you can try to do a wait until it's not full and things like that and the best part about that is you returned the queue is full you don't return the queue is is full you return the queue was full and that might not even have been true either but it's like it looked full to you and it was full for like just a split moment it's it's from the outside you can't tell the difference of whether it was ever really full or not I can tell you it was full and you will believe me that is that's often the case right it may not yeah but it looked fold to me so I'm gonna return that it was full and you can't tell that I'm lying so it's yeah I mean even if it was truly full as soon as I start to do the return it might not be full anymore so what's the difference right it's happens all the time in lock free programming it's like so I changed the code now so in theory I have to recheck all those cases all those edge cases all right because you made a change of code and this is me rechecking all those edge cases and then we get this point of if you recall this slide of updating generation and tail it's actually going to look like this I have to pass some the old tale and the old generation in and then update is going to look like this it's going to because we were because we were right there and we wrote the P once we get into update we have to increment one more time because we want to put the new tail there and we're going to Kaz because at some point old tail was their tail started there we've moved temped along and now we want to know has old has tail changed since we last saw it so that we can update it or did someone else already update it for us because at this point the queue looks like this right the whole queue might have changed tail tail could be somewhere else now it could look like this now we don't know we don't know what it looks like ah that's a great way to do it we all know what slide number is on right okay we're here we're trying to update we don't know what the queue looks like could it look like this where the real tail is right there so if it looks like this and the real tail is right there and we go to update tail to over there then we've broken that invariant I just talked about will have tail passed the dotted line where the real tail should be so we really don't want to do that right we'll break our invariant I didn't say that can't happen because we had fours there and now I'm saying oh what happens if it looks like this now with those zero fours once you've got fours with data you'll never get zero fours again in those spots they will at least be fives or something bigger so I'll never get this case where I put that [Music] that they'll never get the case where tail is behind where I last thought it was so you won't you will never see it looking with these fives and fours like that however you'll see this six and fives because you know it's gone around so now I look at tail in the caz loop there I look at old tail and I say yeah it's pointing at the exact same location it used to point at so I will now update it to the other location where temp is that's what the Cavs Luke has instruction will do and I have now broken my invariant just like a whole loop later and you probably will rarely find that because because it's another case that you'd have to do a lot of testing before you ran into it this is an ABA problem let me explain that so here is a we've got old tail and tail and we're looking at the value of tail compared to the value of old tail and we go okay they're both on at and you know entry seven or eight or whatever number that right there right there pointing at that that cell and then we go along and we do some work and that's B there's some state of the of the Machine and we don't know what it is and then we decide okay we're here now we want to update tail to temp and tail you go tail hasn't moved it's at the exact same spot old tail was so I can do that update problem is that the old a in the new a aren't the same color one is purple one is blue obviously so we need to take the purple and blue and encode it into tail and old tail because we've lost that bit of information things look the same but they're not really the same so we just stuff it in there you can either imagine stuffing it in there like put the number B saw it like cram two integers together or you can also just think of tail and old tail don't have like they just always increment forever and eventually you need to worry about wrapping around but we're not gonna worry about that right now which are essentially equivalent things either either old tail never gets past you know 16 or whatever the size of your cue is and it just goes back to 0 or it just goes goes on forever and if it goes on forever then you'll have to do the mod whenever you access the buffer right so equivalent ways of thinking about it so now when we try to see if tail has changed and checked like has the world changed on us we can we can see whether it has changed or not what in this case it is the same and in this case we'll look at tail and and we actually see that they're different because we've added that extra bit of bit of data to them so the cast will fail and we won't update tale and we won't have broken our invariants and then generation has a similar thing it's like what generation are we on now I don't know we were on generation for a second ago but the whole world changes between every line of code and I'm gonna say that generation count the temporary generation count just has this tendency to always increment so what we can do is say as long as we're the generation we want to set it to as long as it's greater than whatever generation it currently is updated even if it's changed someone in key might have come here and changed generation from two to three but I think it should be five I don't looked oh if it's to make it five I look if it's anything less than five make it five because why not let's get up to the most most recent and I'm gonna claim this all keeps our invariants in check and that is all that code for push now I'm gonna have to figure out how much to do in the next 15 minutes there's some interesting things about that even oh is that one question is how many relaxed versus non relaxed operations are there ends up being like three or four relaxed operations and one non relaxed which is pretty good there is a problem of course that there's really no such thing as relaxed caz on most unlike x86 or anything because it has to do it's it's an if statement it's it's not just oh I just setting this vary or something it's going to it's going to be as slow as a as a non relaxed caz so that's that's not as optimal as you would like so the next question is that same thing do I don't even have to for some of that like the generation try to even check if the generation has changed or should I just set it just like it might I might be behind but the chance of maybe it doesn't matter if I set it behind I'm probably ahead so just said it don't even check if you're a head or not just assume you're the last guy there's a lot of little optimizations you can do because we assume that these are just hints ah okay at least we can get to pop same sort of thing head is looking for the first non-zero data instead of the first zero data of the correct generation and if the push code looks like this the pop code looks like that and hopefully that looks very similar and then basically put in read every line that's different right you're looking for data instead of zeros instead of checking for this less than thing we're going to check for equals zero and we can find out that it's empty or equal if the generations are equal we know it's empty and we're going to be updating head returning some data and we have a very important we have an acquire operation instead of a release operation and I have this one problem that I keep talking about this generation thing and I have head needs a generation and tail needs a generation and in this example those are different generations so now I've got two generation counts and once you've got that it's like why not I just put head and head generation into a struct and tail tail generation into a struck so I made this struct called Gen I for something that would fit on slides its generation plus integer and it is now the same struct as the entry itself they're all three generation an integer plus a generation count and you know you can assume that operate or less than equals default is a C++ feature it's not so this turns out to be all the code and it all fits on one slide surprisingly so that's why this is a simple lock freak you and all you need to do is look at all these different states and check that every single line of code is valid for any one state and when you go to a second line of code check every state to see if it's valid and of course the first question is is this all the states or are there more states that I'm not putting up here or are there actually less states this state right how is this any different than these two because the algorithm only sees one entry at a time so that state in green is really a combination of those other two states in yellow the algorithm can't see the whole queue it sees one entry in the queue so in a sense there's actually not this many states and what you really want to do is look at the entry you're looking at because this is every diagram I have looks like this every diagram should really look like that that's all you can see when you're your code right you just I can only see what's here now you make the whole thing is that you build up a few assumptions or some invariants so that it's like if I see this I know something else but all I can see is one thing at a time so for that x4 it can be any one of those kind of configurations except for maybe fives or whatever said that same same idea and you know when you're you know the next from from this step to the next step you could be in a different state and the next step you give me in a different state and every step of the way you have to check what state you're in and you can do it this way and just look at those values and say well if I'm looking for a zero for if I find a zero for stop if I find an X for there's a little fork in the road and if I find a 5 or an x5 I just keep going so that narrows down all the states that we have to deal with and to have to remember what this case is about yeah this this is that that when you find out that the queue is full you would actually I don't update head and tail there I don't update tail when I should I can I can search through the whole thing and find out it full and I just leave instead of like at least telling people what the last thing I saw was but small problems so this is what lock free programming looks like all right have all the code in your head have all the states in your head and do the code I'm really close to being out of time so that's the part about updating tail this is this is like the real half of the talk that I can never get to next time I claim these are some of the invariants that we're trying to maintain in this queue that tail is always less than real tail head is always us in the real head that it's actually is circularly contiguous like that I didn't end up putting a hole in there somewhere because then everything would break that the entry generation is always like five four there's only over two generations in there it's always higher than lower tail only creases and it adds data and then head only increases when there is data so that should be able to for me to prove that head is less entail but I don't really care if head is less entail because it no longer becomes a problem and ordering guarantees something that is hiding in here is what guarantees do you have on I have a thread that put in one two three into this queue in order what order do they get pulled out of they might get pulled out in any order in a normal yeah you have to assume that if I have a multi multi threaded in and multi threaded out you didn't care what order I put those in because they're coming out in whatever order and they're getting processed in whatever order on the other hand maybe I write this Q that is multi threaded multi producer multi consumer but you happen to use it in a single threaded case then you're like hey I put I know I put one two three in an order why didn't they come out in order like that would be if you only have one thread or you could see this now so my queue actually tries to guarantee that for a single thread that put in a 1 a 1 a 2 a 3 you could see that that thread comes out in order even if you had multiple thread ins and one thread you would see a won some other stuff a to some other stuff a three that comes down to also what are the cement you know I didn't explain what the semantics I'm I'm going for and that that they're kind of ties in what invariants are you trying to maintain and in theory I would try to prove something like range is circularly contiguous which in ten seconds I will do which means did I write it in the right spot so 0 we start 0 we walk through this and I will write it in the right spot Oh awesome 0 case works it's always good to know that the first case works then we assume that we've gotten so far because is proof by induction it's like okay now we have some some things in the queue we know we just have to prove that the rest of it works this relies on some of these other things that I've yet to prove right so this proof can go on for about an hour of how do you prove lock-free code and it's very much one step at a time and things like how do I know that real tail like we've kind of talked about but it's like you have to look at well it gets set by temp get set there it came from here and it came from up there you have to trace backwards where did this data come from is it always increasing does it decrease and when I was walking through all this I ran into this case of like I said before it's like tail will never get set until after everything else cuz it's it's the update happens last right but this code is actually relying on quite at the right spot yes could this ever happen can line one happen before line two and you're like that can't happen because like line two is basically an if statement and how do you go into the if statement like you know it's if this you'll fall out how do you go into an if statement and do something before the if statement right but at the same time you're I'm like well I don't have an acquire I don't have a for I mean I don't have an after means after here I've only got a release everything before happens before but I don't other than the logic of an if-statement which used to have to start to think about when you're doing Locke reprogramming I don't have anything that says well it's you know we also don't do speculative writes so the chances of something being written going upwards but you do have this or I have this ordering between these two variables and the code is this is where some information passes between threads some other thread is setting might be setting the buffer with this release and I have an ordering relationship where tail is saying well I know the buffer is set so I will know that I will never see 0 4 and problems like that so at least technically I feel there's a relationship between these lines of code right like I'm worried that all those X's will happen later than then the setting the tail and it'll get out of order at least there's a logical relationship even if it doesn't happen in a current processor or there's no see there's no compilers that optimize it or whatever but technically I think I need an acquire release there and we could spend a whole bunch of time to decide do you need to require acquire release there or do you just go I'm gonna put a choir release there because because it's safer leave that as a question further we could you know go read the standard word for word and try to decide how that works this is what makes me worry about it that simple is you know simple line of code there read the value at some address that's two separate loads right you have to load what's the value of the pointer then what is the value at the pointer can those two lines at the bottom be reordered by the CPU and of course you're like how could it be reordered by the CPU the second line has to know what the first line came as a result course on an alpha processor those two lines can be reordered in the memory and I could spend some time if I had more time trying to explain how in the world can something like that happen but you have to imagine that it one way of imagining is it's already red pointer before and it's just gonna use that same light it's like oh I've already got that in the cache I've already got that and I just read it two seconds ago why would I reread it when I'm the only thread around so it it can it can in effect reorder those instructions and that's my question would be does anyone here understand memory order consumed and I guarantee no because the committee doesn't understand memory order consumed and we've like put a comment in the standard saying don't use this right now we're still figuring it out so that's what that's what this is all about so that's what makes me wonder about you know I don't think those lines can be changed but then I'm starting to like I start questioning myself and that is I mean it managed to get to the end looking back we did push awesome and pop that's like how far can you get that's that's that's a lot for a lock free and we started talking about invariants I'd like to talk more about the invariance later and I'd like to point out this thing someone did this project called the Potala me project where they wrote a kernel an OS and all stuff at berkeley and they said let's make this the you know the best best practices possible we will do design reviews code reviews nightly builds regression tests code coverage 100% code coverage reviews of the concurrency they brought in concurrency experts to review this code and in the kernel and it ran for four years and then a deadlock right so the whole idea of like do I test lock free code yes you need to test it do I guarantee that those tests tell me that it's right no I don't Karen T those tests at all well it guarantees that it won't you know what you won't have a problem as often as if you didn't run the tests it really comes because you know to for a lot of Industry you look at this you say bug once every four years I can live with that like maybe that's you know if it's a if it's like a medical device maybe you make a different choice but if it's my phone my phone is not gonna run for four years straight so you know who cares but it does this is this is also here to scare you that's the point of this slide um and looking ahead I have a cue that looks like that when it gets really full my goal is to put a marker in there and allocate another cue that's twice the size that's is why this the goal of this cue is to be a growing and shrinking mostly contiguous multi producer multi consumer lock-free cue I think that's a lock free cue that grows forever is a cue of any kind that grows forever is a bad idea it means you have a problem in your system but it's the most complicated cue I could think of so I thought I'd write it and the plan is to have this other side buffer here that only has to be like 32 numbers to track is anybody using are those new cues that you've constructed are they are they still in use or if they become empty so the idea would be of course this is still circular you go here then you go up there and then you go up there then you come back to here and then you loop around and then at some point if one of those gets empty you remove it again but someone might be in there looking around for something and so you have to have reference counts and all these other things so this is why this is called part 2 of n this is Q this this is my next 5 years of talks and I want to get not just in switch structures that's someday we will have structures in this Q ha and then we're getting out of the woods we're at the end of the thing that is the the code I think I am done I went fast because it's sorry and is if there's questions we know how much time but I will stay around and talk about this stuff as long as you want but I'm gonna say that is my last slide thank you [Applause]