Hello, folks welcome to yet another one of the the long coding streams This is part two of the the video series where we implement Hazard pointers. I almost called them haphazard pointers, which is not right hazard pointers in rust I'll give a little bit of a recap from last time and sort of where we ended and where we go next But a little bit of housekeeping just first I decided to sort of start a subreddit I don't know whether I'm gonna use it yet. There's just it's just r slash John who I always I figured this might be an easier way to sort of Post updates for people who aren't Twitter people or where you want more structured discussion or something Maybe I'll do some Q&A here. I haven't quite decided But this is now a thing that exists and you can go look at it if you want to there's not too much of interest there right now Also for the stream so neofm 0.5 was released, which is really cool I'm excited for it because it includes native support for the language server protocol And so I have Upgraded to neofm 0.5. I have changed my configuration to use this to integrate with rust analyzer I Haven't tested it very much So we'll see on stream to what extent this will work whether it'll be better than the old setup I have I haven't checked in the configuration yet because I'm not sure I'm Done with it yet, but this will be a nice Beta test of of that functionality. I'm using it with like nm Lsp config and stuff There's a decent amount of configuration to change actually It's especially if you're coming from something like a coc neofm like I was it's a little bit different All right, but how about we start where we left off so Last time we started Writing this this library that implements hazard pointers and and I won't go over what hazard pointers are that sort of covered in part one but basically this is paper from 2004 on How to use hazard pointers to do safe concurrent memory reclamation the idea is that if you have a highly concurrent Data structure in particular where you need to deallocate memory Deallocating memory is non-trivial in a concurrent setting and so you need something like hazard pointers that there are other schemes too But this is the one we decided to implement To safely do that memory reclamation So we wanted to write a library that the implements that algorithm for you And we ended up calling it haphazard because that's a fun name and it has hazard in it We got pretty far last time So we managed to sort of run a test that doesn't crash and and it checks that things actually get dropped It it's not super rigorous yet. Like we know that there are some Atomic barriers for example that are missing. We know there's some functionality missing around having like custom domains domains if you remember is Each hazard pointer and allocation is associated with the domain And there's sort of a global domain that everyone can use But you might want a local domain for something like a data structure where you want the collection of garbage to not have to Sort of contend with collection from all of all concurrent the allocations in your program in General and and this is what the documentation from the library We're basing this on says to in general you won't really need this like Most people should just use the global domain, but we'd like to implement support for it. Anyway The library we're basing this on is out of Facebook's folly library Which is an open-source sort of data structure and algorithm library It's great. There's all sorts of stuff in there But in particular they have a pretty solid implementation of hazard pointers It's well documented and it also forms the basis for a proposed standard that I think they wanted to get included in the C++ standard and So we'll sort of switch back and forth between using the the proposed standardization Document for reference and using the actual code that they sort of serve different purposes We end up using both for this So that's sort of where we ended off I think that the places we want to go next are we want To get all the sort of atomics right so this includes both getting the barriers in place and you choosing Like memory orderings that aren't necessarily just sequentially consistent And then we also want to get multiple domains to work Ideally we also want to Figure out a way to provide just better Ergonomics for this in Rust like currently our interface pretty closely maps on to the C++ one And I think we can do a little bit better in particular. I want to Make sure that we take advantage of the type system to do things like make sure that you can't For example Accidentally use a hazard pointer from one domain with a With an allocation From a different domain. These are things that that like we can have runtime checks for them But it would be nice to have some static checks, too And even just like making the type signatures nicer and giving them better names are things we're going to be looking at As well as some questions in chat, let me see those real quick Great nothing too relevant. So After last stream it seems a decent number of people were just interested in the code basis wanted wanted to dig into it and One great thing about having people look at your code is that they found problems So in particular there have been Three well a little bit more than three technically but three relevant PRs posted to the haphazard repository already that identify Actual problems with the implementation that we had so I figured I would go through those quickly because we should just merge them and get those Get those into the Into the code base before we keep going The first one here is if you'll remember from last time We we added this this Feature if you will of reclamation where it can sort of recurse And we wanted to make this potentially tail recursive So we pass in the start the thing the number of reclaimed items to start counting from This this is what allows tail recursion because if you add to the count after your return you can't tell her curse Unfortunately when we did that the we we sort of computed the total number of reclaimed items as Like we just added to that counter But we still subtracted the total number from the the count we keep of number of retired items Which of course becomes a problem because This reclaimed number includes the ones that we subtracted last time around so we end up double subtracting them So this just fixes that up so that we only Subtract by the number of items that we reclaimed this time around So I'm gonna go ahead and merge that Like so That's great the other one is The entirely correct observation that we remember we have this deleter trait And on deleter we have a delete function that just takes a Sort of a v-table trait object through a raw pointer and its job is to drop it and the idea would be that if all of your Allocations that are guarded are created with with box for example, then you need to like Box from raw to reconstruct the box and then drop the box so that it gets to run its own deallocator Which is gonna free the underlying memory of course this itself is an unsafe operation And the trait method should be marked as unsafe because otherwise remember we expose this this drop in place function closure, but we expose this as Not an unsafe even though internally It uses unsafe and relies on the safety guarantees of retire But that is an unsafe property, right? Like that that is a requirement of the caller that the caller is retire Which doesn't necessarily hold and so we need to propagate the unsafety up here and so this just marks the trait function as being unsafe and That's great So I'm just gonna go ahead and merge this too because this is a correct and good change And then Finally then remember how The actual hazard pointers are sort of cached over time So even when a thread stops using a hazard pointer, it is actually deallocated It just marks it as inactive but leaves it in this linked list of Hazard pointers so that other threads that come along Don't actually need to sort of modify this linked list of due allocations in order to get a new hazard pointer They can just take one that's currently inactive. Well, when we walk through to look at which pointers are guarded. We should skip Hazard pointers that aren't active because they're not actually guarding anything Otherwise, we're gonna be checking them when they're not they shouldn't be checked because they're not used by anyone anymore And so this just Changes that loop that walks through and and sort of collects all the guarded pointers so that it only guards active pointers So we're gonna merge that one great if you remember from last time to I should have prepared these but I did not Let's see author John who maybe We filed two issues last time to which were This one So actually let me go pull this code here I just left some diffs here for myself to remember to merge these PRs because things are clearly not okay Let me go ahead and get rid of those ones And this I think is something we need to fix manually and this one to fix in PRs Yeah, I thought of some problems too And we're gonna move that one down there and then do that Great Yeah, so if you remember This is maybe a little too large. There we go Yeah, like the text is going off-screen, so I'm sorry. I'm gonna have to make it a little bit smaller We have we have this annoying problem where for the deleter trait We implement deleter for just freestanding functions but unfortunately If you have Dig this up down here. It's easier to show if I show the actual code that calls this Dot deleter dot delete Man, where is my Call to this Ah, so retire if you recall takes a din deleter Sticks that into the the retired objects, right and the retired objects down here Take sort of call the delete method on the deleter that's passed in and the Deleter trait is implemented for freestanding functions But what we want to do is provide a Function like drop box unfortunately function definitions like drop box here are not equal to Function pointers, which is this type and the the type that we implement the deleter trait for We implemented for function pointers not for function definitions and that's what requires is like Not very nice static in the middle here to sort of do that cast for the user so that they don't have to think about it We filed an issue about this seems sad And there was actually a really interesting discussion the followed about whether this is the right thing to do Ultimately, it's not entirely clear whether Whether the compiler could just like do this cast for you whether this should be an implicit cast I highly recommend going through and reading this discussion. I thought it was interesting. I learned some from it, too I think for now, we're probably gonna keep this interface in place because it does mean that The drop in Drop box The fact that we declare the static that does the cast for you Means that Users can just pass in a sort of deletors colon colon drop box rather than having to do the cast in their call to retire So that's really nice The other thing that we followed an issue on was this This drop bounce lint So if you recall for has pointer object We say that anything that implements this trait needs to implement drop and the reason we say that it has to implement drop is because we need to be able to turn it into a Trait object that has the drop method because ultimately when we retire any allocation so anything that is a Has pointer object so something that can have a hazard point or point to it We need to be able to drop it later on and we want to treat it as a trait object So that we can keep a sort of heterogeneous Collection of all of the objects that need to be dropped regardless of what their original type was And it's a little bit silly because you can really take any type and turn it into Into a trait object and it will always have the drop function on it like every v-table for any trait always contains the drop method But normally if you do this if you don't have this this allow if I remove that in fact, let's see whether nice Okay, so I do get a warning that says the bound self drop is useless even though if we remove it The compiler complaints you can't turn this into a trait object because it's not guaranteed the self implements drop And so we added this this bound and then we added this allow drop bounds and like the warning is clearly wrong Like the trade is trade bind was not useless and That's some of what this discussion Sort of came down to but one interesting observation that came up here and in the the sort of linked Pull request that tries to improve the warning was it like in some sense the link is It is getting at something which is and this is something we notice ourselves This drop bound shouldn't really be necessary It's not really the right thing because even though it's true that you can drop any object The drop trait is only implemented for a certain subset of types and really here. We want to accept any type But then we need some way to turn it into a trait object that we can call drop on And this is why we had to add this like unnecessary implementation of drop for our object wrapper type We had to implement that drop because otherwise this wrapper doesn't implement drop and can't be used as a has pointer object Even though it doesn't do anything because it just calls the inner drop method And well what came up in that discussion, which I think is a pretty decent Suggestion was basically to add a new trait with a blanket implementation. So what we do here is We find the I also really need to split up this file because it's getting a little bit unmanageable So has pointer object what we're gonna do is we're gonna add a new trait called retire or Maybe even reclaim That trait has no methods we're gonna implement Reclaim for any T And then we're gonna say is that this is gonna require that the type implements group reclaim Which we know is true for any type right because we have a blanket implementation for all types Then we can turn this into a din reclaim and because claim has no methods This doesn't meaningfully create a larger v-table, but it will include drop because remember every trait object v-table In fact every v-table includes drop Close enough and so now if we go to retire we say that this has to include a din reclaim Which then in turn means that Where's it complaining over here? So I want to go to definition that worked nice So this is gonna take a din reclaim Deleter is now gonna be given a din reclaim And this is gonna be a dinner claim. This is gonna be a dinner claim. This is gonna be a dinner claim This is a dinner claim this is a dinner claim and in some sense we're claim here This is like an alias for drop, right? It has no methods. It doesn't provide any methods. That's just what it does Cannot find right so this needs to use super reclaim Din drop Okay, and now this impel drop for For the wrapper is gone and we no longer need this Drop bound lint that can now go away because it will no longer trigger so that's kind of nice and I thought I left a to-do for myself here So let me go ahead and just commit this So we're gonna say here is avoid din drop Like so And then I'm gonna stash pop because I had some notes for myself in here So this is another sort of error that I realized After the stream ended which is in retire This is the rumor this is if you're trying to deallocate an object like you've removed it You've unlinked it from the data structure, but there might still be readers have handles to it So you're gonna sort of retire it by sticking it into the collection. That's later gonna be reclaimed We added this optimization where if the type doesn't need drop That then we might then we just return now. This isn't quite accurate Because like Technically it might be that the pointer type needs a drop, right? So the example would be a box u8 I'd imagine that the the actual object type here is a box u8 so this this star mute is a Box turned into a raw pointer and self as a u8. Well, then u8 doesn't need drop so we would return But then we wouldn't call retire which means the raw pointer would never be turned back into the box So the box would never be dropped. So the memory would never be freed. So we end up with a memory leak There are two ways we can deal with this one is we just remove this optimization and have it go through the the normal procedure the other thing we could do is we could say and Like deleter dot needs drop Right and to sort of add a method to the leader that says does this pointer type Require dropping. I think in practice. We should just let it go through the machinery like it avoids the extra complication on the leader It avoids the extra complication of this method. It sort of means more things use the same logic which tends to be better I think in reality, it's like unclear that you would ever really get here in General the pointer type is just going to require a drop like Because you have to turn it into a raw pointer The only cases wouldn't be is like if it's already like you're sticking Stack pointers into atomic pointers, which is already pretty weird. And in that case, I think it's fine to just go through the retire So I'm just gonna get rid of that logic That's nice And then I think I left one more to do or xxx or something Right so this is I Think I definitely need to zoom out more Because I can't even whoa Okay, that's fine. I guess this is actually a good size because this is a hundred characters Which is what rust the rust format spec dictates is the right like Wrapping size for text Yeah, so I wrote a note to myself, this is clearly not okay readers may still be accessing the nodes We can't take ownership until we verify it's not guarded. What about panics? So to recap what this code is doing this is We're trying so we have a collection of objects that have been retired So they were moved from the data structure and we're trying to figure out whether or not we can reclaim Think we actually drop them which is only the case if the if no readers like basically if no one Has a pointer to the element anymore. Is it no longer guarded by any hazard pointers? And so what we're gonna do here is when I walk through all of the nodes And then we sort of grab the node into into a box Then we check whether Whether any of the guarded pointers Had that pointer in it and if that's the case then it's not safe to reclaim the node and we We do this we turn it back into a raw pointer and stick it on to the remaining tail and otherwise We it's no longer guarded and it's safe to just drop the the box the problem here as I tried to sort of articulate in the comment is What happens if there's a panic here? So imagine that what's a good example of this Maybe we're guaranteed no panics here, but I just don't trust that that's the case like imagine that guarded pointers dot contains panics for some reason like I don't know there's a Weird DRF implementation in there or just like we did there's like a bug in the hash map Whatever it ends up being if the code panics anywhere between here and here We have a problem because we've turned the node into a box Which means that we're claiming that we own it and a panic At least if it unwinds is going to drop all local variables and that includes is going to drop this box even though It could be that we're in this case where there are pointers There are hazard pointers guarding that box and so we're not allowed to deallocate it We don't actually own it. In fact, this claim is just false, right? It's not true that we know that we own this here And if you remember the I have a video. I think it's called like the unsafe chronicles on on box Basically, you're not allowed to construct an aliased box So you're not allowed to construct a box unless you actually actually have Exclusive ownership to the underlying value never mind using it. You're not even allowed to construct one Which is what we're doing here. We're constructing one even though someone else might already have a shared reference to node Think of this is this is because box internally connects a unique pointer and unique pointer has optimizations Assuming that no one else has that same pointer, but that's not true if this is shared so in reality what we need to do here is We have to do this Right, so it's totally safe for us to take a shared reference into the node That's totally fine because we know that it hasn't been deallocated because we're the ones considering deallocating it So that can go away and What else here? I think actually what we're gonna do is say unsafe node call that and and Then we're gonna do is only in the case where we know that it's okay. Are we gonna take back the end? so here And a pointer that's fine not safe to reclaim still guarded So here I think what we need to do is actually say n dot next Dot store Remaining And Same here and then remaining is gonna be equal to node. Oh, I see so this is gonna be Hmm so here what I'm gonna do is say current is equal to node and Then this is gonna set remaining to current Right, so the idea here is We're walking the list of nodes We're looking at the current node We're we're setting node to be the next node because we're iterating right so we need to move on to the next node at some point and In the case where we can't reclaim this node What we need to do is make sure that the node goes back on the list of nodes that are still remaining still retired but not reclaimed So we store we set the next pointer of the node that we just sort of unlinked To be I guess we didn't Yeah, we unlinked it because if you remember here Further up what we do is we sort of we swap out the head of a retired list We sort of steal that whole list for ourselves And so now that the steel list is at the sorry the retired list is empty And we need to anything that we don't end up reclaiming we have to stick back on the retired list So that's what this remaining list is for as what we do here is We walk all the things that we stole right so this is we take the current node We find the next node because that's what we're gonna iterate over next But in this case we need to stick the current node Back on to remaining so it eventually goes back on to the Onto the retired list so that we can try to reclaim it the next time around And then only in this case Is it okay for us to deallocate the thing? so I think here I think here what we're gonna do is Let n Is on say from current So No longer guarded So here the the safety for this is Current Has no hazard pointers guarding it So we have the only remaining pointer And the safety for calling delete So so this box from raw is for the remember that there's sort of two parts here Right, there's the data that was actually stored in the atomic data structure That's end on pointer and then the box for current is sort of the the node on the linked list of elements that were Tired and that one we have to deallocate as well. So that's this part up here So the safety here is that end on pointer has not yet been dropped Has not yet been dropped because it's still on the Retired list It will not be dropped again Because we have removed I guess let's actually make this a list that's a good point It will not be dropped again because we removed it from remaining not from remaining from retired It was still on retired It will not be dropped again because we removed it from retired and end on pointer was allocated by the corresponding allocation method as Per the safety guarantees Safety Guarantees of calling retire great So that's why it's okay for us to call call delete and then reclaim plus equals one and Just to check that that's not entirely insane the test we still passes So let's see here Also deallocate Pointer pointer type So maybe this should say deallocate pointer type even if self doesn't need to drop Let me see if I can Deallocate pointer type even if self Draw pointer type even if self type doesn't draw pointer type Even if self doesn't need drop there we go what I was trying to do is in general the The first line of a get commit should be 72 characters So you see if I make it longer you see how the characters on the right turn red The later lines can be I think 80 characters But the first one should be shorter so that it like fits an email subject and whatnot There are sorts of conventions for what these rules should be and I try to stick to them when I can and Then the other one here is Don't construct a box until it's safe Great, so let me go ahead and push that just so I have Less of a dirty local change All right So now I think we're sort of at the point where we have all the things we did in the last stream Plus fixes for things that were buggy in the last stream So this was sort of a we went through a bunch of things we sort of we didn't really do a ramp up Which is sort of jumped into problems from the end of the last stream Let's stop for a second and take like questions on how do we get here what just happened? Remind me what these things are I'm sure that if any of you are like I don't remember this thing There are probably many others so let's do like Recaps of things that are unclear that people don't remember Why not a const rather than a static For the deleter I'm guessing for this alias This Can this be a const This can probably be a const you're right It might not it might not actually because it needs To be oh, maybe it can be I was thinking it had to be a static because we actually need the address of this like it's stupid but up here we implement deleter for a function pointer but delete takes a Reference to self which is a reference to a function pointer So we need an address of a function pointer, which const doesn't give you right consts don't have addresses At least not in the general sense Whereas a static does so that's why I was thinking it might have to be static But maybe not maybe it'll just let me have this be a const if so, I don't I don't quite understand Why this actually came up in the discussion on the issue to like why does the compiler allow this cast if you make it explicit? Like where does the address live? Where is this reference Right the function pointer is the function pointer But what is this a reference to if this is a constant or in the case of an explicit cast? It's not clear like does the compiler just generate a reference for you something weird is going on But nice if it can be a const yeah Why when I'm returning a string literal it doesn't recognize it as a tick static automatically a In rust you have to be explicit about lifetimes Otherwise they're inferred so the function signatures that's given is like fn str like for this Inference is usually what you want for lifetimes like in general You're not gonna have a function like this in general the the rule is that output lifetimes are tied to input lifetimes That's what the inference is. It's not gonna look at the function body In order to determine whether this should be static or not because that would mean that if you change the function body But not the signature the signature might change and you don't want that property You can make your own drop trait that's always implemented yep, that's basically what we did for I I really need to just put this file up. I should just do that now for reclaim when would drop not be implemented for a Trait object and so drop is not implemented for a bunch for types that Rather drop is only implemented for types that have an explicit drop implementation So if you have a if you have something like a struct foo tea Right this type does not implement drop Even if it contains a type that itself implements drop like Struct bar Imple drop for bar And drop self Right, so if I now do buzz is foo bar So bar implements drop even though it doesn't have to do anything foo does not implement drop and even foo bar does not implement drop even though foo bar Does have to be dropped it doesn't implement drop because it doesn't have an explicit implementation for drop but if you construct a trait object over a foo bar or Indeed over a foo that the table will always contain a drop method Regardless of whether foo implements drop and this is why this trick with the the trait which I believe oh You're right. This might not even be necessary I might even be able to get away with not declaring that bound because it's implemented for any type That's nice Although it does need to be pub for these drop-in-place things to be pub So I'm just gonna leave it a pub. The other reason to leave it as pub is because it is easier to document Why not use din any we could use din any but din any has a slightly larger v table because it needs to include the Type ID in there and there's no reason for us to really use any here I also think and maybe I'm misremembering, but I believe the any trait Yeah any is only implemented for T's that are static And I don't want that requirement for this type. There's no need to have that requirement in this case I can close this and I can close this and I guess I should make this Be appearance dark so that people don't yell at me I'm still a bit confused why you needed to define reclaim I suppose using din any again because of the static bound that's required by any There's rusts cons we have more like C plus pluses constant evil or cost expert not sure In general, I as in I don't I'm not sure what the difference between the C plus plus ones are so I can't really speak to that A constant rust is generally a compile time Value like it's it's computed at combine time and and it's effectively Replaced in every place that you use that constant at compile time. It doesn't have a location in memory So is there a linked list of guarding pointers for each element of the data structure that as be that is being protected? No, there's a linked list of of hazard pointers globally or associated with each domain, but but think globally and Those hazard pointers can point to any pointer to guard that pointer from de-allocation And so if you have a data structure like a I don't know a be tree or something what you do is the readers would Take a hazard pointer sort of pointed at the node in the be tree They're currently looking at and that way they prevent that node in the be tree from being de-allocated But they could also point it at a Location and complete a different data structure and guard that from being de-allocated So what's nice about the hazard pointers is they're not tied to any particular data structure Or in need any particular instance of a data structure. They're just sort of I'm guarding this pointer And then it's up to the the thing that drops to make sure to have a check with the list Whenever they're about to drop something All right great So I think then we're in a pretty good position here. What I'm gonna do is I'm gonna go ahead and go ahead and go ahead and go ahead and go ahead and go ahead and go ahead and go ahead And I'm gonna go here and first get rid of these So we're gonna say Drop helpers can be const And I'm gonna add this because I'm not entirely sure where the address comes for for the self Reclaim has blanket impulse so not needed in where That's great. Push those two just so we have them out there And then what I want to do is before we start doing anything more serious about this implementation I want to split it into files because there are too many things So what we're gonna do is Go ahead and take Am I gonna do this I'm gonna say that we want to split this into Oh No, I've remapped my one of my key bindings that I use for other things. That's fine So I want to edit a Source I Guess well, I guess we'll use the standard names for now. I still think that what we're gonna do is Replace most of the names Mod holder and We're gonna go ahead and move all of that into here and Then we're going to take I guess pointer the RS mod pointer and we're gonna take This bit and put it into here. I'm gonna take mod deleter or deleters Maybe The leader haven't decided yet That's gonna be source the leader Deleter because the RS is implied Great And then I guess pub use the leader the leaders And we want to pub use Holder has point holder and we want to pub use pointer has pointer And What else do we want here? Oh, right? We also need pub use the leader What else we got here has pointer domain so we're gonna have domain dot RS and stick Let's go with 60 a hundred maybe 2050 So that's gonna go in here Mod domain And here we're gonna pub use domain has pointer domain Bring that into here. I didn't save that file What else do we have in here? These are Private things that go into domain.  This needs create has pointer and I guess shared domain for now, although realistically, this is probably gonna take from the actual This is gonna to construct a hazard pointer holder You're probably gonna have to do that from a domain anyway, but for now, we're just gonna have it use that And then we can trim these down to only the ones we need Beautiful Same thing here This is not needed. These aren't needed That I'm gonna find out soon enough what it's complaining about this needs reclaim I guess reclaim can go in to leaders too.  That's nice Hazard pointer object. So I guess is gonna be mod object and Again, it's gonna take all of these so that we have them and we're gonna pub use Object has pointer object And in fact, we're gonna stick the wrapper in there too because we might as well remember the the wrapper here is Anything that's guarded by a hazard pointer needs to be sort of dropped in a special way and so Basically, there needs to be a sort of back reference to the domain so that you know When you're gonna drop the thing that's behind the atomic pointer You need a pointer back to the domain so that you know where to Where to do the dropping because you need to like retire it and then reclaim it you don't get to just drop it in place And so this is why we have this has pointer object that has the retire method Which is when you call when you removed something from the data structure and We want people to be able to implement this trait themselves so that they don't necessarily have to use our wrapper type But we provide this wrapper type for for those who want it So we can take This and stick that in here too, and then this can be This and has pointer object wrapper Nice And these tests could probably just be standalone tests Actually The shared domain is a good question. I think I want the shared domain to be in lib Problem. No, let's move that into Domain as well. So that can go away And Then I guess what we'll do here is This probably has to be pub crate is my guess Because we're gonna have to use that from Some of these other ones all of the tests we're gonna move into their own files because Let's see Because that way changing a test won't have to recompile the whole program Have Zurt have hazard right And Just for good measure. I'm gonna stick these uses in here too, even though they may not be needed And These aren't necessary in this file now because it's just forwarding stuff and what happens if I cargo T It yells at me because in object. We need Shared domain So I guess I'm actually gonna re-export it pub crate re-export domain shared domain Because it's gonna be used in so many places So this is gonna be create to share domain This is also gonna have to use create task pointer domain like so and also Create the leader possibly some others to reclaim Claim And I guess I'll stick that one on there too Great don't need that don't need that don't need that Now back to lib great. What else we got in Domain we also need to use create Probably a bunch of things we need to use has pointer We need to use This is like the pain of restructuring We need to use Reclaim We need to use the leader And I think that might be it so I don't think we need the holders or anything in here Great Yeah, some of these are gonna have to be Pub crate such as active and probably next to end pointer and Protect which is on holder I 29 is a Has pointer so has pointer this So protect has to be pub crate This is Yeah, this is not a method that we expect users to call in fact has pointers are Arguably entirely private like I almost wonder if this can be pub crate But let's leave it pub for now It might be that it doesn't even appear anywhere Object can't call retire On domain Because retire is almost certainly yep Retire on domain should also only be pub crate because we expect you to call that on You should call that on the object that you have take out of an atomic pointer or something rather than directly on the domain What else we got? Acquire is the same probably so this is pub crate Nice although Right I made a silly in that this needs to be called tests And now Great this can go away. This can go away. This can go away And who and now it complains about shared domain I Guess shared domain can be pub. That's a good question. So should the shared domain be public? I Think so I like domains are public. So you should be able to get a reference to the shared domain I think that makes sense. So this is gonna be a pub That's gonna be a pub which arguably means it should just be here Fantastic and that test now passes. So if I do get add dot Split into files Fantastic. Oh, yeah, I monitor all the chats. It's just I don't look at the chat while typing code But I get all of the different platforms in here You can't see it but my screen actually has like Below where my video is or there like to the side on my screen. I have chat So I see all of it Great. So now we have this restructured. It's a little bit cleaner now I think the question is where do we start? Do we want to start by fixing up all the atomics or do we want to start by adding support for domains? I Think I want to do domain support first So this is like custom domain support because it might require that we sort of re architect some things at least a little bit and That might it might both align our code more with what the Facebook library is doing but also Also, it might expose more places where we need the barriers later So if we add the the barriers are now, we might just have to move them later anyway Yeah, so I think we're gonna do that first. So let's head on over to domain So the structure here is that We want users to be able to create their own domains, that's easy enough Right so we can pubf and new and in fact, it doesn't even need Any arguments it just does this So this we've already done And in fact, this can be Const Yeah, because there's nothing here that even does allocation. It's just Which means that because it can be const we can do this Which is very nice We can even like implement default for has pointer domain I think there's an argument for not implementing default. I haven't quite decided yet, which is I can just call new If it implements default It's a little bit harder to document that you probably don't want to do this, right? So I don't know if you remember this from the Facebook documentation But it says here most users do not need to specify custom domains and custom to leaders and by deep and by Default use the default domain and the default to leaders too many uses of the word default there But the idea is that in general you should just have like Everything use the same domain because that way you get to reuse the hazard pointer holders the retire list the hazard pointers You get to amortize the cost of Deallocation across all different uses of this And remember we we end up doing like deferred to deallocation with hazard pointers, right? So when you remove an object from a data structure, you retire it, but you don't necessarily get to reclaim it straight away and it's that means it just sort of sits in this retire list and We don't check the retire list again until someone tries to retire something else So imagine that someone does like a bunch of removes from your data structure But none of them can be reclaimed yet, and then they don't do any more removes That memory will just never be reclaimed If they have one domain for that data structure if they use the shared domain then any Retire in any data structure will reclaim stuff for the other data structures as well So it's like in general what you want is to use the shared domain So I kind of almost want to call this like New not recommended But but even if I if the name doesn't imply it like at least with new we can document why with default That's a little bit harder I don't know if you knew this but you can actually write documentation here And it does get rendered in Rust doc, but it gets rendered like you need to click plus next to default which I Certainly don't in fact there was a case where I was specifically looking for what the default value for a given type was and I Just didn't think to look there because normally what you would get is the documentation from the standard libraries Default trait definition for the default method, right? Which is like not helpful. It just says like the default value for the type But if someone wrote a custom one here, it would show up in Rust doc, but no one would think to look for it And I feel like if it implements default you're also just like more likely to create your own So I think I'm gonna not do that What I do want to do though is this Which is gonna give in fact This is a good argument for this not being pub and in fact Not even being pub crate and then saying We're not gonna expose the fact that this is through a static Instead what we're gonna do is Here we're gonna say has pointer domain shared That feels much nicer and If we really wanted to we could have this be a an associated const I Think so we could say that this is equal to this This obviously has to be shared I think this is legal now and then Then we can do this Nice so it's an associated constant of the type so that's kind of nice Yeah, I think I like that Rather than like having to expose an actual static And that we can like write documentation for when you like Documentation for new is gonna point you a shared and the like Or maybe this should be called global actually I Think global is a better name. It could be called static actually Like the static has pointer domain not entirely bad, but global has a better feel to it. I think Okay, so if you construct your own hazard pointer domain It's gonna have its own list of hazard pointers and its own list of retired That part is fine And then what we're gonna need is on Hazard pointer object Yeah, this one is gonna be a little interesting so here I'm pretty sure there's a static bound missing here sort of separately from all this but This is gonna have to be tied to the Lifetime of the domain Lifetime as from first oh I Guess I could actually call this domain Actually, no, this is so if you use the default domain, you're gonna get back an object wrapper. That's static And this I guess is gonna be Domain is has pointer domain global And What else do we want to say here? So this is gonna be self dot domain and for any domain We're gonna return here is a reference to the domain That's all good Same thing here, although for the D ref the domain doesn't matter for D ref mute to the domain doesn't matter This is complaining but the complaint is off my screen, which is a little unfortunate Lifetime parameter instantiated with left a domain the lifetime parameter must outlive the static lifetime I think the requirement here is that t outlive domain not t outlive static But has pointer object requires that self is static and The reason for that is The reason for that is because when you call retire you have no guarantee about when the object will actually be deallocated and That's why we require that the the type that you want to retire is static It needs to live for however long it might be until the object is actually reclaimed Which could be forever like it could be the end of the program. That's why it has to be static, but I guess now this is actually going to be parameterized by the domain and Self has to outlive that domain They have to be able to provide a domain that lives for that long And We do and the the idea here is that we do guarantee that when the domain is deallocated Every t will be deallocated too So if your t think of this as like you have a domain that lives for this long And you have a type t that lives for this long, right? This won't work because imagine that like okay, so this I Actually, what am I doing? Why am I using your hands? I have a drawing tool. I'm silly so let's say here we have a Domain domain lives until here and then down here the domain is deallocated And this is the lifetime of your program. So like in some sense tick static is like down here And now imagine that you have a t that can only live for this long Like imagine it's a value on the stack or something and like this is where that function that holds that t returns So after that function returns the t is gone. It can't live anymore any references to it can't live anymore This is not okay, right because you can imagine that someone calls like retire here But there are references to it. So it doesn't actually get reclaimed until here So this is when we call drop But it's not okay to drop the t down here because the t doesn't live anymore So references to it are invalid So we're gonna have to require that any t lives for at least as long as the domain lives When the domain goes out of scope like when the domain is dropped Then we do call reclaim on everything because if you think about it the hazard pointers are tied to the lifetime of the domain So when the domain is dropped that means there are no hazard pointers to the domain anymore Therefore all of the pointers must be reclaimable Therefore we get to reclaim them and drop all of them And therefore we don't require that the t lives any longer because this destructor will be called when the domain goes out of scope Does that does that make sense why we need this this parameter? I was following the hands. Yeah, I mean, right like the domain lifetime the t lifetime What if something gets deallocated or reclaimed down here? That's what I was trying to get at but I didn't my fingers didn't have enough dexterity to actually show it And so what this implies is that as long as the Object that you want to retire lives for at least as long as the domain and you can prove that you have a domain That lives that long you're fine Great so if that's the case Then now we can say this implements this it's a lot of a lot of tick domain here Great and we can prove that we have this because we have that Self may not live long enough. That's probably because we have a Constraint somewhere here, too So if you have a has pointer domain where you're gonna get back is actually a reference to a hazard pointer that lives for As long as the domain does it's not gonna be tick static when You retire it Take any pointer that should be fine So why is it complaining about this self? Why is holder complaining now shared domain is no longer a thing this is gonna be has pointer Domain global So I guess we need Has pointer domain global It's still complaining here though that The tram parameters self might not live long enough That's because din. I think by default is Requires tick static and here we want to say this And that means that retire now needs to take din reclaim plus domain Which is undeclared here because So this is gonna be Domain and you have to demonstrate that the pointer outlives the domain great and retired Is also gonna be generic over domain. This might get hairy Because we might not be able to name this type here And you'll see why in a second I believe if I go up here now Yeah, so the problem here as the the retired list is sort of self, right? It's however long The domain is around for So here we're gonna pull a little trick which is Not super nice But what we're gonna have to do which is that the retired is gonna be a Just a din and Then like we're gonna have to use on safety here because you can't that basically what what let me put this back and explain Why this is a problem? What it's gonna complain about here, right is that The things in the retired list need to live for at least as long as self We guarantee that because we never put anything in there that doesn't already outlive a reference to the domain So we know that this will always hold for anything that we put in there But we can't name this lifetime at this point like in the definition of has pointer domain This is It's not even self-referential really It's just we can't name this lifetime, but we know that it always holds by the bounds on The bounds that we Enforce on putting anything into here in the first place So what we're gonna do instead is down here get rid of this Get rid of this get rid of this get rid of this and sort of say here this is plus tick domain Which is enforced on push Which is enforced for anything that constructs a retired And in fact in the place where we do construct a retired Where do we do that that's down here Here What I think we're gonna do is impel retired We're gonna say FN New And that's gonna take a it's gonna take all these same arguments except I guess not a next But it's gonna take this extra parameter so what we're gonna do is we're gonna take a Domain that we don't use but the existence of it proves that you have something that has that lifetime This is gonna be didn't reclaim plus domain And a deleter and it's gonna return a self And at this point and this is where the sort of funkiness Gets in we're going to have an unsafe Pointer as star mute didn't claim and Now if I why do I keep going back to that file? That's not what I want to do And now in the place where we actually construct the retired we're instead going to do new self pointer deleter and So here notice that this isn't unsafe because we prove that the pointer lives for as long as the domain I need to stop doing that and inside of new is where we have this unsafe transmute And where we sort of erase the domain lifetime and so here what we'll say is safety It's sort of misleading, but I think what we're gonna say here is The safety requirement here is that we know that the pointer will not be used after the domain goes away So like Arguably it should be unsafe here, maybe And this has a requirement along the lines of Yeah, this is basically a transmute to static right we're transmuting away the lifetime which is the same as transmuting to static and What we're really saying is Pointer Pointer will not be accessed after Tick domain ends Right, so as long as this is true, it's fine for us to Erase the domain because the caller has already guaranteed that they won't They won't take advantage of the fact that we're storing this is something longer the domain And the only reason we have to do this is because Otherwise we would have to name tick domain all the way through which would get all the way back to the sort of top level domain So Now where is the call to? Retired new so this is now going to be unsafe And here the safety is Pointer will not be accessed After domain is dropped Which is when? tick domain ends So the question is is that actually true? I have to think about this because Actually, I don't think this is safe the challenge The challenge you run into here is that imagine that someone has a Yeah, I don't think this works Imagine someone has a hazard pointer domain that lives for some long period of time The fingers again lives for some long period of time and then they take a reference to it And that reference only lives for a short amount of time and then they give a T in that outlives this short lifetime, but doesn't outlive the The existence of the hazard pointer domain So it meets the bounds here But it but it still isn't safe to reclaim here after its lifetime ends just because it outlives the the reference and Actually, that's sort of what Russ was trying to tell us right is that the Yeah, it's real awkward Right by sort of requiring that we declare self here It's saying not only do you have to tell me that this outlives any given reference to hazard pointer domain You have to tell me that it outlives has pointer domain itself Regardless of how short or long any references you can construct to it are Which is awkward And in fact, this is a there's a larger problem here, right, which is This isn't the life the right lifetime Because the lifetime here is the the lifetime of it's the lifetime of The thing that is being referenced and so remember that immutable references or shared references rather are Covariant which means that they can be shortened as much as you want So you can always construct an immutable reference with a shorter lifetime than an immutable reference you already have And so that's why this won't work Sorry to try to demonstrate this problem just to make it a little bit more concrete Imagine that I write code like this Let domain is Has pointer domain new And then I'm gonna do this and I'm gonna say D is domain And then I do T is String new why not and then I do D dot retire T. Well, I'm I'm Abstracting over a lot of details that aren't really important for this particular example But down here the domain actually gets dropped So this the the syntax here isn't quite right, but but imagine that this Imagine that we call this take a And we say that this is a Has pointer domain Reference that lives for take a it's not quite true, but we could totally shorten it to that Then this retire is gonna sort of accept what we're saying, right, which is that We're giving in a T that Out lives or lives as long as take a right because T goes away at the end of take a but it's valid for take a So this is allowed, but imagine that this retired doesn't get to reclaim T So it takes T and it sticks it on the retired list, but it doesn't reclaim it straight away Then this ends so now The T goes out of scope So now it's no longer legal to access T I guess this would have to be like a And so when the domain has actually dropped it's gonna reclaim from the retired list and reclaim T now in practice doesn't quite work that way because T won't be dropped anyway maybe a better example here is that we try to retire a Z is box new of reference to T That's a better example But that's not gonna read T so this needs to be a Read on or let's see print on drop now. We're talking okay So print on drop imagine I have a strict print on drop that implements drop when it gets dropped is gonna print whatever its references It's gonna print print the empty string in this case So what's gonna happen now is this type right is a box print on drop Tick a string Right, that's the type of Z here And when we call retire on Z It's gonna allow given what we just wrote it's gonna allow that retire because Z Lives for at least as long as the domain. They both live for take a therefore the retire is accepted now Z goes on dot retired, but is not dropped Right then we get down here. So now T so down here there's sort of an implicit Implicit drop T So Z is no longer valid at this point So down here Let's say that now for some reason we sort of walk dot retired We find that a Z can be reclaimed and so we call drop Z But when we call drop Z we're gonna Run the drop the destructor of print on drop which is gonna try to print what it has a reference to But that reference was tied to the lifetime of T and T has been dropped. So it's a dangling reference So this is the problem, right? This is why it's not sufficient to have retire Have retire require that its argument outlives its reference And why we really need this to be a reference to the The domain itself I Wonder whether we can do this by Intentionally constructing an invariant type So the problem here, right is that you can construct a reference that has a shorter lifetime then You can construct a reference that has a shorter lifetime Then the actual lifetime of the domain is sort of the problem I don't think we can easily restrict that though because We don't have a way to sort of Get the the real lifetime of this Maybe with pin It might be the retire just has to be unsafe The other way around this right is to Still just require the T is static it's like unfortunate, but But that's certainly a way around it like if T is static this problem can't occur in the first place because you wouldn't be able to Stick this type give this type to retire because it's not static You can also think of it as static outlives any domain and therefore is always valid to drop That's kind of sad, but I think that's what we're gonna end up doing here That's Unfortunate that's real unfortunate There might be a way around this but not one that's immediately obvious So I think we're just gonna not dive too deep into this right now And instead just require for retire That This is just static and in fact we could even say plastic static here. It's implied. We don't actually need it Right it doesn't take a self anymore. It's no longer unsafe to call Right it's no longer unsafe to call And now here we're gonna have to require That this is still static. I kind of still want the object to be Generic over the lifetime of the domain maybe Yeah, I think we still want that even though we require the type to be static Just because in the future we might find a way to actually do this and then we don't want that the trait to change and Relaxing this to a shorter lifetime. I don't think it's a break in change That's that's too bad So now this has to require that T is static Has pointer object It's Complaining somewhere Lifetime parameters essentially with tick domain, but lifetime parameter must outlive the static lifetime. Why oh Balls Well, so this is kind of weird actually Well, it's awkward here, right is that Haster pointer object itself now needs to implement static Which isn't true if it contains a reference that only lives for domain And so if it has that reference to any domain that reference has to be static I think this is just gonna have to be this That's Unfortunate but the the problem that it's rightly complaining about is that You've said that has pointer object has to be tick static But has pointer object is not tick static because it holds a reference that is tick domain And you haven't said that tick domain is static and So I think that the way to get around this for now is to just not Make has pointer object be generic over the lifetime of the domain because I don't think we need to Because we're now requiring the type to be static the domain can live for a shorter as long as it wants to the T will always live long enough to be retired and This means now that But that means that the domain now has to be oh That would mean that the reference to the domain that we keep here has to be static We could have every object wrapper hold like an arc to a domain the reason I didn't really want to do that is because The user might have an arc to the domain already and I want them to not have to do like I don't want us to Enforce that for them Hmm. I mean Okay, so the reason why this doesn't come up in the C++ code is because in the C++ code all of this is like unsafe, right like these are all just Requirements that the caller must uphold that the type lives long enough and what we're trying to do here is enforce it on the type system The challenge we're running into is basically that We can't really enforce this like basically We can't statically Check that the domain lives long enough Because imagine that the domain is like In an arc, right? You can't check at compile time when the last arc will be dropped And So there is no lifetime we can assign to the domain the domain doesn't have a lifetime because or it doesn't have a Lifetime that's expressible at compile time There's an alternative here Which is to Do what we just proposed of having like this domain lifetime everywhere. So sort of basically go back to Go back to Go back to this and then just make this a requirement of retire instead Domain doesn't look like a word anymore So if you go back here and we still do this just as a Sort of basic requirement Just like a basic safety check, but still says that this is unsafe And then now we might mark this is unsafe So the safety here is oops the safety here is That Pointer Remains valid Until the Until Self is dropped Which really feels like the pin guarantee Pin is a little too strict here because we don't actually require the pin doesn't that the domain doesn't move We just require that it's not dropped So this is then gonna go back to the holder no to To object And then I think we're gonna have to add a fourth safety requirement here to retire Which is a caller must Guarantee that So now this can be tick domain Caller must require that Self outlives The Hass pointer domain and Not just any reference to it or or we could phrase this differently self lives Until has point until the hash pointer domain is dropped Is a better way to phrase it because outlives makes it sound like reference lifetime outlive Would really we mean not just a reference to it, but the actual Ownership of it and this is more equivalent to what the C++ code does Which is that retire had to have to promise this into the C++ code to it just basically the type system is forcing us into Giving this on safety as it correctly should and Then I guess This I'm gonna go ahead and say pointer is this and pointer is this and Now this whole call is actually unsafe So this is gonna be something like This whole call is unsafe The reason I move that cast out is because this cast I want to be safe I don't want this to be an unsafe transmute and and having to be hidden by the fact that I put unsafe here this Just a double check Should complain. Oh, it probably doesn't cuz lints aren't happening yet oh I didn't remove the Self I added for explanation up here. So this has to go away See we get now 252 Is Captured and required to live. No, this has to be plus static What is it saying lifetime parameter Instantiated with a lifetime domain, but lifetime parameter must outlive the static lifetime lifetime bound not satisfied Yeah, that's oh, it's probably It might actually require this to be a Mem transmute Domain is complaining about shared domain constants cannot refer to statics Consider extracting the value of the static to a const and referring to that Consider extracting the value of the static to a const No, I don't want to do that I wonder why that is I Guess it's cuz it's not a const This is so the static is a Location in memory, but that location in memory isn't known until link time So the compiler doesn't know the value here So in that case this isn't a const, but it's sort of a public field Like if I do this is that accepted I think maybe it's telling me that it is pub const defend global like is that allowed no method acquire found. Oh, that's just because this has to be global and No, same thing constant functions cannot refer to statics Well, I guess global isn't a const Yeah, I think it's because you can't Well, you sort of can at at compile time you do know Where the static will end up, but maybe it happens too early in the compilation process Like this might be something that just isn't supported yet Because this feels like it should be allowed to be constified The reason I don't want to make this a const even though sort of in theory you could is because then it then You wouldn't necessarily have just one instance of it I want this to be a single shared domain if I made this a const what this would mean is that you have one You have a different domain anytime you use this const because it sort of gets in line into the compiled code Or at least you might end up with several whereas. I really wanted to be a single global shared domain Test lib, okay, so this has to be has pointered Domain global Same thing here Same thing here And it currently probably tries to import it to you know, okay great sweet So at least that's now Now we have a way to construct these holders Yeah, great great great great great great Okay, so now Remember there's sort of two parts to this puzzle, right if you have a If you have a data structure that's using this you have the the hazard pointer object Which is the thing that's like stored in your data structure that you have atomic pointers that are pointing to And then you also have the hazard pointers themselves Which are which may or may not point to a hazard pointer object in order to guard that object from being Deallocated and both of these need to be associated with a single domain the same domain in order to actually guard because when you retire an object You need to check all of the hazard pointers But you check all the hazard pointers from the domain of the object So if the hazard pointer is in a different domain, it won't be checked so we need to make sure that the the hazard pointer domain that the readers the clients the The things accessing the objects use is the same one as the one that's used for the call to retire Currently that's not the case. So if I go to pointer If I go to holder The hazard pointer holder remember is the thing that has a hazard pointer That it's going to use the guard and it might not have one because it might not have taken one from the linked list from the domain yet There's a lot of indirection here Indirections may be the wrong word but there's a lot of sort of layers of abstraction here and then and one of the things that's certainly not helping are the names here and When you actually went so you create a hazard pointer holder Then you say now I want to guard this pointer and the hazard pointer holder goes and like gets an actual hazard pointer from the domain And and that's this hazard pointer Function here, and you'll see that if it already has a hazard pointer It reuses it if it doesn't it currently just gets one from the global, but this is a problem, right? Imagine a data structure is using its own hazard pointer domain That's not the global one and then some reader goes. Oh, I'm gonna construct a hazard pointer holder I'm gonna grab use that to guard my load of that atomic pointer to the object Everything is fine, but the reader is gonna be using the global domain and the the retireer or the data structure is gonna use Its own custom domain. And so when it retires, it's not even gonna see the hazard pointer that the client is using And so this really needs to be the same domain as what's used by the object and We have some ways to deal with this Specifically so first and foremost for load We're gonna require that T implements Has pointer object of any lifetime Has pointer object So if you try to load a hazard pointer to guard it with a hazard pointer it better implement hazard pointer object Because if it doesn't it's it's not something that even can be guarded So we want to say that you can only load things that know about hazard pointers I guess in theory there's no danger in having a hazard pointer to something that doesn't support hazard pointers But we might as well add this as a bound here because otherwise You're probably doing something wrong. The other reason why we want this bound is because this gives us a way to Get at the domain that that object is using So let's see here Take underscore cannot be used here The objects Domain needs to live for at least as long as L That's fine. I think that's fine And I think what we're gonna have to do here is do This is even stupider So Okay, so here's here's the challenge we run into how do you know that the holders for the right domain?  Because okay, you can start the hazard pointer you load the pointer You're not allowed to dereference it until you know that it's protected But you don't know that it's protected until you know that the has pointer is for the correct domain So I think this is just like inherently unsafe Like I guess we could we could have a debug assertion here, right of like debug assert Self dot domain which we don't have yet is equal to Actually up here It's equal to Are is this so that's the target is gonna turn our but we're gonna assert equals R dot domain is equal to self dot domain. Is there there's a pointer equals I think Which is really just this as Star cons test domain It should be equal to this as star cons task pointer domain right, so this is all we can do here as a debug assert because like this is If the domains are different, right, then you haven't actually protected here and so This D ref is just not safe if the domain is if it's not the right domain because even though you call protect Your protection is guarded by the wrong domain. So it won't be checked by the writer So the writer might have deallocated. So this D ref is incorrect and so This is already undefined behavior. So so this like this is sort of a last-ditch effort of okay Maybe it was deallocated with the memory hasn't been overwritten yet. So maybe we can like detect it at least in a testing context But if you ever hit this assertion like things have already gone wrong. It's just we happen to be able to detect it But but this is definitely another Another instance of this on safety that we can't trivially check although I have a I have a trick up my sleeve That we'll see soon it's not gonna fully solve the problem, but it's gonna help a little bit So the column was guaranteed the address in the topic pointer is valid as a reference or null The columns also guarantee that the value behind the atomic pointer. Let's first and foremost make these nice Will be called will only be deallocated through calls to hazard pointer object retire on the same Has pointer domain as This holder is Associated with right so that this is like the key addition here that it has to be the same hazard pointer domain As a what we're gonna do now is Instead of deriving default we're gonna have The holder Is gonna hold a I guess this is the hazard and This is the domain and we're gonna have a a Global perhaps unsurprisingly which gives you a has pointer holder static. Well, there's a lot of annotations on my screen right now So global is just gonna give you a hazard pointer holder where the hazard is none and Actually, this can just be self of For domain of has pointer domain global So we're gonna have another constructor for domain which takes a This is now gonna be generic over domain which is fine But we're also gonna have a constructor for glow for static Which does this Which in fact does this And this is gonna then have to be hazard pointer holder For domain so that's gonna take a domain reference and give you back thing with the appropriate lifetime and that's gonna be a Self Where the hazard is none right because we don't have a hazard for the domain yet and the domain is domain We're just can no longer implement defaults and Now this is gonna give you back a hazard pointer with the lifetime Self domain And this is gonna be hazard and this is gonna be hazard And now this is not gonna use the global domain, but it's gonna use our own domain And now this load Still does the same thing this is gonna use the hazard We're gonna implement drop for hazard pointer for any domain. That's fine This is just gonna set it to inactive and that's fine So now you can construct a hazard pointer holder either for the global domain Which is what you normally want and in fact we could implement default here again, the downside with default is People will just like use it and not think carefully about it And so I want them to explicitly make a choice as to whether this is for the global domain or for a particular domain and Or they can choose to use it for for the particular domain and Then we have this debug assertion which like arguably happens too late, but it's sort of the best we can do Let's see if this Compiles it does not because the tests have changed now This is now going to be a global hazard pointer holder Global has a pointer holder global has a pointer holder a global has a pointer holder I Wonder why this is complaining borough of H occurs here Cannot borrow H as mutable More than once at a time That's because Whoa first borrow occurs here Okay, but why doesn't it end there? Oh, it's because of this so This needs to be like a Tick oh This is tick oh where tick oh outlifts tick. Oh, I think that will do it. Yeah, okay So the the challenge here was I was saying so so remember how the The reference we return from load is tied to a mutable borrow of the holder So the idea here is that for as long as this holder still exists and you haven't used it to load anything else since the the exclusive part This reference is still valid because the hazard pointer is guarding that reference What I was doing when I when I set L here is that I also need that lifetime That's what I'm saying here that lifetime needs to be the same as the lifetime for the object behind the atomic pointer But that's just like not true right like remember this is basically static for most things and That sort of goes back in requiring that this is saying that this is going to be static and this has to be static Which is like not true What I really wanted to say is that whatever the guarded object is That guarded object has to live for at least as long as we want this reference to live for but it doesn't have to be the actually the same And so that way this can be a long lifetime without requiring this to be a long lifetime This is an example of where multiple lifetimes are just needed in order to accurately express the constraints we want and you know It's like it's you can do this It's just that it becomes a pain to use because now any load is going to borrow the The holder for eternity, which is not what we want and not what we need in fact Oh So there's some discussion about constants referring to statics. It's true that in general like because statics are mutable you can't Well, so it's not quite true statics are not mutable mutable statics are mutable You could have interior mutability in a static, but that does mean that the the Address of the static is still constant, right? So that's why I agree that you shouldn't be able to have constants to refer to that the De-reference into a static because that value is not constant But the address of the static should be constant, which is all we were using here So this is why I'm saying I'm guessing this is a limitation of the constant valuation that it doesn't Realize that if you take if you only use the address of a static, then it's still constant. That would be my guess All right So now we have this now we have multiple domains and and just to sort of Sanity check that our test actually does something useful So it feels good let's do feels bad Because why not so what I'm gonna do here is I guess go ahead and do this and Construct one of these and I'm gonna have like D1 is hazard pointer domain new And D2 is has a point domain and then oh I guess did I not Declare a constructor for this so let's do with default with let's maybe say instead of default call it global and then something along the lines of with domain Which is gonna take a domain Which is a tick domain of Has pointer domain Which is then gonna take that domain and stick it in the domain too many domains This is gonna be object wrapper with domain This and It also needs to pass in the T So now I should be able here to say with domain and Give in say D1 Or I guess actually a reference to D1 Did I put in multiple feels bad that won't work can only have one feels bad Okay, so the writer is gonna be using Domain D1, I guess maybe let's call them D DW and DR So the writer is gonna use DW the reader is gonna use DR actually, I wonder whether we want this to not be a For domain, maybe we don't want to require that it's a reference But maybe we want to require that it's any type that implements like as ref or D ref or something because If someone stores like a it keeps like an arc of a domain They can't actually give you a reference with the appropriate lifetime With arc, maybe it's good enough For readers but for writers is a little bit of a pain because the object wrapper Gets a little awkward Yeah, I think it's okay So as a reader, we're gonna create a holder for that And then we're gonna H dot load X and this should panic should panic Reader uses a Different domain than the writer Let's hope this catches the error at least in debug mode Right, it's no longer called default. It's called global No line 53 same thing Global domain and unused variable. That's true Thread panicked while panicking that's certainly interesting it probably panicked when dropping the holder or Something That's interesting. Let's go with no capture here and let's do Test lib Feels bad Whoo Yeah, that's fine. That's so that's the assertion failure we expected That's because the domains are different and we could we can sort of double-check this by saying in holder Object Guarded by different domain than holder used to access it Right, and if we test now that should be the error we get Yeah object guarded by different domain than holder used to access it But it panicked at not yet implemented at domain. Oh, right So it panicked when it drops the domain because Implement drop for hazard pointer domain. So we haven't done this implementation yet. And in fact If I just comment this out just to see that this indeed works. Yeah, so that does panic Which is what we expected so the test passes So that's great. The reason this panicked was We want when the domain is dropped it should clean up all of its retired things, right? It should be at that point safe for it to reclaim basically all of its objects So here I should be able to do self dot Just block do again here I think I don't even want to Block at this point. It should be fine for me to say Self-dot retired dot count dot load in fact dot dot get Because I Should have a mutable reference to it like the when the has pointer domain is being dropped. There are no references to it So I own all the values So all So n retired I guess and then I want to call bulk reclaim of zero and false and Reclaimed And these should be equal, right? I should be able to retire Reclaim all the retired objects when the hazard pointer domain is gone because there should be no hazard pointers outstanding Now technically maybe this should be a debug assert because you could imagine that someone like Panics while holding a holder or something and in that case maybe this isn't too bad But in general this should be true And then there's still a little bit more of to do here for us, but at least that's a start Okay, so that works and then the little bit of work that's still needed is if you recall Inside of a hazard pointer domain. We have the linked list of hazard pointers and the linked list of retired lists and Both of those are sort of contain or the retire list should be empty. I guess but the hazard pointer list remember We never deallocate from because the idea is that you can always reuse these hazard pointers But when the domain goes away, we can deallocate them because no one should be using them anymore So self dot retired dot Head Get mute. So we're gonna Assert that this is null right, there should be nothing in the retired list anymore and So we could say here There should be no hazard Pointers active so all retired objects can be reclaimed Also Drop all hazard pointers as No one should be holding them anymore So this one is a little more annoying In that we have to walk a linked list So in fact what we could do here is We could just implement drop for hazard pointers instead, but I think what we're gonna do is just Oh We're gonna do head is self dot hazard pointers Get mute and then we're just gonna walk the linked list So while I guess this can be no it can be mute While And in fact, I think I want it to be as cons You'll see why in a second. So while the node is not null We're going to say We're basically gonna reclaim the hazard pointer So we can hear just assume ownership of this one actually we can say N is box from raw of Node and That's unsafe That's why this can't be this This is safe because We're in drop so no So no one holds any of our hazard pointers anymore As all holders are tied to tick domain Which expired on drop which must have expired on drop? And then node is n dot Next Don't get me Really we have pointer we have next and we have active That's fine So why can't I use next here then this should be a box has pointer And I can also hear assert that N is not active that should certainly not be the case I guess this is dot get mute. Why not? right, this is a Mutable reference to the pointer, which is silly. This should be a star mute has pointer Just to make it clear what this is actually is And This is gonna be that so we're gonna move to the next node and this is gonna implicitly, but we can do it explicitly drop in As we're just gonna walk the whole list linked list and drop all of them Get mute not found for this is because that has to be dot head Cannot borrow and active as mutable is there a get as well Apparently not. All right, fine. I wonder does it just implement like D ref? and I think so I'll be Too good to be true. That's fine So the observation here is that if you have a an exclusive reference to any of the atomic types You can just get their value with get mute, which is not unsafe because no one else has a reference to it So there's no contention possible Great stuff All right, let's see how that does Great. So now I think we have all the bits that we need for multi-domain support So let's do Commit that as support non-global domains And it's like it's unfortunate that we still have the static bound. I wish that wasn't the case. That's something we can look at separately We do have this like pending foot gun though, right of This debug assert is really unfortunate. It's really easy to accidentally use the wrong domain So how do we fix this? Well, it's not trivial to fix because Ultimately you you just like need to compare the domains by pointers and you can't get the domain until you do Until you have protected the target. So there's like a catch 22 here. It fundamentally needs to be unsafe But we can do a little bit better and this is This is a little bit of a weird trick But I think it might be valuable Which is also an idea that chat came up with on their own, which is nice So the trick here is going to be to have a sort of associated or not associated type but a type parameter on domain Which is we can call it like Differentiator or mark like it's a type that doesn't matter. It's only there to sort of denote that a domain That the note the two domains are different But but at it like statically So what we're going to do is let's call it M for mark and What we're going to store here is use standard marker phantom data And this is going to store a mark. So maybe Actually the name of this is actually fairly important Because it's not it's not a uniqueness guarantee You could totally make multiple domains that have the same mark type and so we want to use a sort of a Name for this that that indicates what's going on class might to be a good name here It's like a category almost I Wonder if this class reserved keyword It's not family is not awful Right so a domain belongs to a domain family And so the only thing this is going to guarantee and you'll see the implementation in a second is that you can't accidentally use a domain from one family with a domain from a Like you can't use a reader using a domain from one family with a writer using a domain from a different family And the idea here is that we're going to make the global one The the global domain sort of have a distinct family that no other domain is going to have And so that means that you can't accidentally use a global client with a non-global writer You could still have like imagine someone has their own data structure and that data structure is let's say Like they use their own family for the data structure But multiple instances of that data structure use different domains, but you can't create a type at runtime So each instance of that data structure is going to have a domain a distinct domain, but of the same family And therefore we can't statically detect that those don't that you don't use the wrong domain like use a Client from one instance of that data structure, but a writer from another instance of that data structure that wouldn't work Yeah, so let's call this family it just gives us a little bit more of that of that protection And then the shared domain I guess can have a really what we want here is for this to be a private struct I Don't know that we can do that. I think that's going to trigger the Private type in public interface Error We're warning. It's a warning. It's fine. Let's let's see. Um, so let's call this Global so we we have a unit struct global And this you can only get a global using the global one and otherwise You can construct a new And I think what we want to do here is like you can use any family you want in new Phantom data of F we use a phantom data because we don't actually want to store an F We want this to be sort of erased at runtime Comparison operators cannot be chained Right, right, this is an instance of phantom data not the type Yeah, and so the reason why I want global to be a private type is so that no one can construct a hazard pointer domain global themselves Now one way to Let's first see whether it actually complains So this is gonna complain about F. That's fine This is gonna write so now the the family is gonna just actually it's not gonna go in here The family is sort of gonna infect everything That's fine holder probably needs now a family And This is gonna be global and in fact This is gonna be pub crate So this is gonna be pub crate use domain global I Have another trick up my sleeve if this ends up being not quite right So this is gonna be a crate global This is gonna be for any family. Oh, that's not what I meant to do Object also holds a domain So this is now gonna be for family This is gonna be for a family This is now gonna be generic over the family and in fact this one is gonna be for global But this is gonna be for any Family This is also gonna be for any family F So so notice that this this is not actually a cost of runtime at all like there's no dynamic check here It's just everything is getting this type parameter Which is gonna make it impossible to do what we did in the test the test is just not gonna compile Which is really cool Just finish up oops. No, that's not what I meant What else do I have holder has some more This needs the family now What's we got this needs the family now? This needs the family now Parameter F may not live long enough, but F F is not Fine F is always gonna be static F doesn't need to be static here. That's right What it's complaining about here is that Hazard pointer object needs to be static remember requires self a static and It's generic over F which might not be static and then it's like oh, but then the trait isn't static But like realistically of course it is because there's no I guess we could say F Domain, but like it doesn't matter. It's not used for anything So I think we're gonna claim that F is just static Now I'm gonna have to add it everywhere Static, thank you Ah all right, oh and it did not complain about my type being private. That's good to know It might maybe later on but here Okay, so let's say that we make the writer use a global one Type global is private because it really doesn't like that That's fine That's fine Okay, it's a little awkward, but it's fine. So so let's let's take the the simpler case here of I'm gonna make this domain be Let's just see Let's just make this be any like weird type Okay, so notice now that these domains have different families, right? They have different family types and now this load just doesn't compile because it says Has pointer object u8 is not implemented for has pointer object integer. What? Sorry, it's this this is last the the error is not very nice But at least it wouldn't let you compile right so see how this underscore is this underscore and it says has pointer Object of this is not implemented for has pointer object of this family Right, so it's now catching at compile time that we're trying to use different ones and like in reality How often are people gonna remember to give a particular value for here? But the thing is they have to right if if you don't give a value here the compiler goes I don't know how to find this value if I if you if you don't give one for one It'll just go. Oh, they're probably the same and inference gets you but if we don't give it for either of them It goes. I don't know what family to use here. You need to tell me which family to use and So this still doesn't catch the instance problem, right of if these have the same family then this will be allowed We'll be caught at runtime Global as private we'll get to that in a second, right? So so these are different domains, but they have the same family And so it will compile crash at runtime because of the debug check we added So it doesn't catch all the problems But it does catch the fact and this is the sort of big one where if I use global for one and non-global for a different one Where it'll say like this is not the same as global not okay And it should catch the other way around too So if if I made the the reader be globe the reader be global and the writer be non-global it would also catch that So that's kind of nice I guess I'll make them New for now and now it'll fail up here because it complains that global is private Yeah, why? Okay, so it Complains that the global type is private which it is entirely correct about the global type is private And we need it to be private because if it's not private someone can Can basically someone can accidentally do this and now if someone if the reader now was global Then now this wouldn't be caught at compile time, and I think this is the clearest case of an error someone would make and Realistically like no one should be doing this in fact, maybe we could just have a static check that this isn't the case But static checks for that are a little bit difficult Because it's sort of a like a negative impulse block like you'll have new for any type of but global So instead what we're going to do and this has some other nice benefits, too It's we're actually going to make this pub and bear with me for a second We're going to mark it as non-exhaustive We're going to give it a Private constructor like so And then we're going to require that new is Given an instance of the F It's it doesn't it doesn't use the F like it doesn't use the F you pass in this is not used But it requires that you pass in an F But and the global type is public, but you cannot construct one yourself So in new we can use and this I guess is a const, right? This can use global new Because why shouldn't it? But anyone else has to pass in the F The structures cannot be evaluated at compile and now this can't be const That's fine, and you just oh, no, but then it can't be oh No, it totally can't be we just need to inline this which is real dumb Fine Makes me so sad great. It can't be const, but It is actually really unfortunate that it can't be const Because I want people to be able to create a Shared domain for their data structure. That's like shared across all instances. So I do really want it to be const Can I make this argument Be Can I say that ooh? Can I say where F is copy? That's fine. This can be copy and clone and debug and Partial eek and eek and will the hash Whatever type you want. That's fine Trait bounce other than sized on const of M parameters are unstable But I want my To work Can this be a reference to an F can It can it can great Okay, so you can still to start a global just the way you normally did but you can't make a global the type Yourself so you can't make one of these yourself unless you call global Which means you're getting the shared domain and you can construct your own and one thing that's nice about this part Is that now you can use types that you can't even name such as closures, which always have unique types So now you can just like use a closure to Pass to new and that type is now going to be the type of the domain The problem of course is you still need to be able to name this type in order to use it for your readers Oh, no, you don't because you can just get them from this If you ever have to name your reader, you're in trouble if you use a closure here But that's fine. So now if I go to test lib Okay, this should be called called at runtime But here's a How am I gonna do this I'm gonna make a compile fail test over here just gonna be Actually, I'm gonna make it not a compile fail first and then and then check so now So if you try to make a global and This can be any types now. This doesn't have to be a fancy type compile because families differ this I guess will be a structure Cannot confuse Global writer And same we want cannot confuse global reader where This is the reader and this is the writer and I did something silly here, which is in tests This now it needs to take an instance of the type Which now arguably makes it easier because I don't need the the weird turbo fish and Something complains in probably my doc test my doc test needs to do this here same thing here and Probably needs to use like I Guess it probably just needs atomic pointer. Maybe oh Our load almost certainly needs to take an ordering. I just realized that's something we need to fix but to do ordering and Oh and adult my my test also obviously needs to use all of the things from the crate. So hap hazard Star and the same thing for this one See what it says Indeed this one fails to compile And the tricky thing about compile fail tests At least when you make them in this particular particularly like simple stupid way You should use something like compile test or try build. I guess it's called To check for the exact error message when you use a compile fail doc test You need to manually check that it actually fails to compile for the right reason, right? Because otherwise this could fail to compile because I was missing a semicolon and the test would pass if our market is compile fail but here it does indeed fail with the correct error message which is that like The parentheses are not the same as global. I Wish I could make that error a little nicer, but it's good enough for now It at least means that that code does not compile Beautiful Why doesn't it run this This that should be compile fail. That's why notice that if you misspell this The it's no longer considered rust code and therefore not run as a doc test It's like there are two lines missing great Add domain families to statically catch misuse Okay Let's talk to this particular solution because it's there's all sorts of subtleties here and that That might be helpful for us to talk through and let me also scroll back and see if I missed any particularly good questions Couldn't use pubcrate for global yes, so that doesn't work You get a family you get a family everyone gets a family Let's see Would it be worth making creating domains unsafe where the caller has to guarantee that there's no dupes I Don't want to do that because There are valid reasons for creating duplicate domains, right like Just because you create a domain for a given family Doesn't mean that creating another Domain for the same family is the wrong thing to do right that might actually be what you want if you want a Domain for each instance of a data structure, for example, like imagine Imagine a concurrent hash map that use this right You would declare a family for the hash map generally and then you would declare a You would create a an instance of a domain of that family for each Individual hash map so that if you de-allocate anything from from one hash map It only considers the hazard pointers for that hash map and not for any other ones Even though the family is the same so it's still correct use right there There isn't an error there the error that could still occur when using families is someone takes a Hazard pointer holder from a domain that was generated for a particular instance of that hash map like map one and tries to use it with a value that is that was retired from Another instance of the data structure which uses another instance of the same domain but by the same family And now you have a problem because they're not really the same domain even though they share family But but we do want to allow the use where the family is the same, but there are multiple domains So that's why I don't think it's the right thing to do to make the Domain creation unsafe Because there are valid reasons to sort of alias them if you will I kind of want new to take an instance of tea it does that now and to have a macro that calls Domain new with a closure Yeah, so that's an interesting idea So you could have something like macro rules, and I guess this would be something like macro export Domain And this would take no arguments and what it would do is has pointer domain new this Uh Macro Export And so the idea now would be that now you can use this to create a distinct domain every time so in our tests This could be domain and this could be domain and they will now be notice that this error is now caught because and This is going to be an even more painful error to debug, right? But the closure types are different and therefore the types are different So that that is pretty nice in this case. I did want to catch it at runtime. So I specifically want them to be the same But you're right that this does mean that if I go back to Our compile test failure Is cannot confuse a Unique domain you cannot confuse across families Right, so this is going to be Domain it's going to be domain and Just double check remove the compile fail cargo T this now Correctly fails to compile with the right error So that's a nice addition that the challenge of course with With this particular macro we just added is that you can no longer name this domain anywhere So you get a unique domain with a unique family And you can't create multiple instances of it. That's not possible. So in some sense It's like immune to abuse But the downside is that it's also much harder to share between your readers and your writers I Can't domain say something like f is not global. No Unfortunately not right. So you're you can imagine something like f not global This is work for a couple of reasons one is that negative trait implementations aren't the thing the other is a global isn't a trait we could here say that The way you would actually get at this is like f is not global And then you would have a trait not global that's like Imple not global for For any T and then implement not not global for global But this needs negative trait implementations which don't exist at the moment Besides I like this being able to pass in by value because for example you can use closure types as this Demonstrates, so I may guess maybe this should be called like unique domain probably Anyone can construct or struct with no fields. So that's not true because it's marked as non exhaustive I should have called this out explicitly. So non exhaustive is an attribute that you can put on a on any type and it makes it so that adding fields to the type is Backwards compatible so I can add Bull here which normally would be a backwards incompatible change because in the past Some other crate could have written like let X is global Right and have that compile and if I add a bool here That's a private field then now their code will no longer long no longer compile And so this would be a backwards incompatible change normally, but with non exhaustive basically it takes away the Sort of built-in constructors is one way to think about it. So The other example would be let's say Pub X is bool Right, then in the past someone could write X true and now adding say Y Bool would be a backwards incompatible change with non exhaustive. This constructor is also removed and disabled Same thing goes for matching over the struct all matches need to be Need to be non exhaustive. So this is no longer permit permitted on a non exhaustive struct It has to be marked as this But but crucially the property we're relying on here is that this means that global does not have a constructor that anyone can call Do you actually need to derive all that stuff on global no we don't need it anymore It was just in case the F copy trick worked But it did not so I agree we should just not have those have those derives Can you use associated types to tackle types is global not global oh Maybe Okay, yeah, so this is a real ugly trick, but you could say like maybe global and It has an associated type is global and We do impulse T may be global for T and say type is global is unit and then we also Implement may be global for global Where type is global is bool And then we say here where F implements may be global is Global equals this I Think that works No, it's still conflicting implementation the the blanket implementation still conflicts, but we won't wait to do this If if you were basically this required specialization, which doesn't currently exist The doc test drugs could be marked config doc test. Yeah, that's certainly true There's no like huge reason to do this The biggest reason is that you don't accidentally start using this type in actual coding It seems pretty unlikely that you're gonna start doing that But at least this way there's just no way that you can One downside of doing this is that now the compiler is telling you oh this code is inactive, which like is fine I don't think it adds too much Could be an associated const. Yeah, it could be an associated const instead of an associated type would have the same property. I think Could probably be done with auto traits What we could do is we could make sure the global isn't send and then require that F is send But it just doesn't seem worth it and the upsides of having this be able to take a closure argument I think it's worth it But you're right. It could probably done with Basically getting out of the auto-imple of send and then requiring F to be send But I don't want to do that Alright, so Let's go ahead and Amend that actually and let me push that out for you all to You Fantastic All right, that's pretty good. So now we have these domains. I think the next step now that's sort of Necessary is Are you believe this should be? Doc hidden but I'm gonna not do that. Oh, right. Let's fix the ordering here, too This is gonna take an ordering Which is gonna be an ordering and then Actually, I don't know if it can because We have to make sure that the protect here doesn't get reordered so before we add the ordering I want to check what the actual Implementation does so I think this is gonna be the next step now is to sort of align all of our Memory ordering and barriers and stuff with what's in the actual implementation in folly So let's do that next I'm gonna take a quick break though We're we can all make tea and pee and be happy and then in like a couple of minutes. Well, we'll keep going All right. See you in a second Think in theory. I'm back Let's see whether in practice. I'm back Like can you all see and hear me again? Maybe yes. No Can you hear my crunching? I'm back great Chat has confirmed that I'm back glad to hear it So Could the unsafe on load be moved to the method for creating a domain?  All right, let's start exploring the Facebook code base and see what they got here Um, so synchronization Okay, so house pointer domain Threshold for the number of retired objects to trigger asynchronous reclamation hmm Right, so they have a bunch of optimizations on like They have these like tags and Groups and stuff that we don't implement currently Hmm I currently Anytime you retire it tries to reclaim a bunch of objects and I think I hear Those are trying to be smarter about that You see the they have these like all these additional stats that are kept for a domain They're an executor the executor is presumably like the Thing that a way that you can say what should be deleting in the background like if you want to do reclamation in the background Then You like you could spin up a thread every time you want to do it but in reality You probably already have a thread running somewhere that could do that work Tire New house pointer retire node That's fine Push retired Yeah, so a bunch of this is just for sort of keeping track of these stats You see like do time accounts for The the retire list to figure out when you should reclaim Push retired is a full fence Interesting Yeah, as you see rather than have a count that they decrement for the number of Items that have been retired they add to the number of ones that have been reclaimed. Oh No, they add to the number of ones that have been retired. I see Auto r is retired so I'm guessing retired here is Retired is a Choir load of the retired list. Okay, so let's go back to I guess domain because that's the one we're looking at So They're looking at retire So we allocate and you know that's sort of the same thing they do Okay, so retired Get me back to where I was please As he pushed retired let's you retire multiple objects at once Which is not something that we currently implement but but Relatively easily could Which makes a lot of sense right because it what you can do and this is the nice property of a linked list is that you can You can Just construct the sort of subset of the linked list and then atomically insert it into the existing one Which is nice Which is basically what they're doing here So there's a full fence before the push I think with the count before we give anyone a chance to reclaim it. Okay, so there's a Standard sync atomic fence What does full fence here mean Like is that a sequentially consistent fence see what I want the definition Of this one, huh? If is Linux Then ASM volatile memory Otherwise a fence why Why is this considered good enough? so I'd what I'd okay, what I don't understand is why is a compiler barrier sufficient But only on Linux That just seems odd like if we're on Linux and Not on mobile so I guess not on Android Then case Linux is true and we can use a different kind of barrier Why? All right. Well, I'm I'm I'm okay with using their definition here. So I guess we'll say FN We'll even call it the same as they do asymmetric light barrier And we're gonna do If config Linux Else Standard sync Sync atomic Fence Standard sync Atomic ordering then What's our equivalent here? Where is the definition they use of that here we go? So it's not even if Linux It's different on MSc, what? Okay, but what is read write barrier in in MSVC specifically it's awful. That's awful So Okay, here's the thing though, I know that the Rust standard library has Compiler fence Because I added it a while back Which is a single threaded fence and the single threaded fence I think differs by platform this that's the Crane lift implementation Where's the actual implementation? This has to be in mirror like it gets lowered to like a don't reorder, but But why does it not appear anywhere in the compiler source? single thread fence ah mirror intrinsics Becomes an atomic fence Okay, I just want to see whether we can use the simpler one and get the semantics of the more complicated one um Rust code gen LVM. What do we get for atomic fence? We get Build atomic fence. All right LVM show me your build atomic fence, please That's unhelpful. Is that just what the okay? LVM rust build atomic fence great Uh So that's gonna be over here and that is a LVM create fence we're really a diggin deep here That's unhelpful Like I don't even even if we find that this is the right thing, I don't know if I believe it All right create fence Wow That's super helpful LVM. Thanks All right Where have I seen memory before? Oh? This is what Standard hint black box uses So in theory we could abuse that here, too, but that doesn't seem quite right. All right Let's not do that But let's do look at intrinsics And see what we find here. These are all atomic fences That's probably not very helpful Equivalent to LVM M set that the reason I'm looking through this is because I want to find if for this And for that matter for this Oh This is even worse Okay Imagine the your own Linux, but you're not using new C or clang you see the problem Here, let me let me demonstrate. I want to program this way asymmetric link light barrier If K is Linux call this function. What does this function do? This function if you're in new C or clang does this if you're an MSc does this otherwise does nothing So if you're on Linux and in not a one of these three cases your Your asymmetric light barrier does nothing which seems like entirely the wrong thing to do We could make it always been be this What is atomic thread fence? Is it a single thread of fence? No good. Okay Yeah, it's not a signal fence that makes sense Why did what I don't understand also is why do they fall back to this? Here's what I'm gonna do To do we did it team good job Back to domain this is going to be a crate asymmetric light barrier Great close that close this and Then it grabs the head of retire so first of all the count can definitely be a choir release Probably even relaxed But I think we want it to be a choir release because we do need it to happen before we add to the list and a choir release will make sure that a choir release is Stores can't be delayed and loads can't be hoisted so A choir release is actually not sufficient here kind of technically because We need this to take effect before this store Because otherwise someone could in theory Otherwise this could be hoisted to happen before this In which case someone could see the new head but not see the updated count and end up doing a subtraction that ends up below zero Arguably the right thing to do here is to never try to subtract from this but Or do this that's fine Okay, so the head here. They're saying we can load with a choir All right, so that's what we saw retire did it loaded the head with with a choir and then it is a compare exchange week with Release and a choir Now the other question here is is the ordering the same for the C++ one and for rust Probably success and failure. That's the same order as the rust one. So here. This is release and this is a choir And this one we want to be a choir release as well So here actually I guess Yeah, they do the ad down here Right, so they do the ad after which you know as May be reasonable. I guess like there's a question here of We probably want to implement sort of their smarts rather than our smarts All right, so let's do that fine. Fine. Fine. Fine. Fine. So we're gonna do this We're gonna have this be a fetch ad with release And then they have a if check So they have a check Which is a bull Which for them defaults to true And it's like if check I'm gonna remove the check from now and just say let Isn't the load like always not equal to zero here basically I Think we're just gonna Do this that seems fine Because we just added a thing so there's something to reclaim in all likelihood So we should just try to run it and of course here we should figure out whatever their check is What's what is their push list to do This is for their like cohorts and tags which we don't use so that's fine This is check cleanup and reclaim What does check clean up and reclaim do I guess we could just mirror this straight away really But Yeah, fine. Let's do self Check check clean up and reclaim and we're gonna have a fn check clean up and reclaim which takes self and it does if If self try timed clean up and if Self that reached threshold our account and each count which I think is just their Our account I think is a load Yeah, it's just a load of R which is the number of retired elements And h which I don't know what is yet. This is gonna be self retire count load And that's gonna be an ordering Acquire So if that try bulk reclaim And it's gonna be an fn try bulk Reclaim Eventually I'm sure it will actually call reclaim So I guess we need a try timed clean up we might just leave some of these empty for now Just we don't have to implement all of the sort of complexity of their cleanup in one go So I want to do this line to stick around Try timed cleanup is if not That check sync time of Sync time which I guess we'll have to figure out what that parameter is for If not that then return false Okay Otherwise self dot relaxed clean up and true So we need a relaxed cleanup Which takes a self How deep does it go you think oh check sync time is right here Sync time is probably just a field on self is my guess here, so Check sync time probably doesn't need to actually take that It's just gonna be a check sync time which takes a self and Returns a bull we know that much Chrono duration cast nanosecond steady clock now time since epic count, so this is figuring out This is just finding the current time in nanoseconds and the previous time It's loading from sync time, so I'm guessing sync time here is a field on this So this is gonna be an atomic. I guess you size you 64 That makes sense because it's nanoseconds and I guess we might as well just have sync time here be atomic you 64 Probably zero is fine I'm let's import that too And now this is gonna be a time is standard time Instant Instant now duration since standard time epic I'm pretty sure there's a way to get time since epic Unix epic. Oh, it's a system time damn it System time now duration since great That's that is what I want It's a duration since and then I want that as So in duration there is from memory a as nanoseconds you 64 as As nanos, which gives a you 128 as Nanos and I guess we're gonna do a you 64 from this is definitely fine to unwrap Current time is after the epic actually I guess System time is set to Before the epic which we're just gonna not say is okay And we're gonna say you 64 from which isn't gonna work. Can we try from? Can we use standard convert try from and then try from and Then can we expect? System time is too far into the future Fantastic Great so now we have the nanoseconds all right now what do we want to do with them? So now we want to all have Rev time, which is self sink time load and this one was a relaxed and if Time is less than prep time or Not or Self dot sync time dot compare exchange strong Prev time with time plus case in time period With ordering relaxed Then return false Otherwise true and this can be simplified a little bit But we need this We need this case in time period Wow great love that all right so const K sync time period is a u64 is equal to I'm gonna make this from nanose this dot as nanose Dot at u64 Standard time this Let's hope this is const. I think it is sync time period plus sync time period beautiful Or this dot is error That's what they're after and this expected four arguments. All right That's fine. They're both relaxed so this is like If It's not time to clean yet or someone else is Just started cleaning Don't clean So I'm gonna call this maybe I feel like many of the names here are not great Like it's true that it checks the sync time, but really this should be something like Like is next cleaning period or something So really I would probably rewrite this to if the time is Greater than prep time if time is less than prep some things off here I Think something's a little odd because this means that You're just like if if time is later than a past time which like seems obvious to be true Like why would this not be true? Also system time is sort of wrong here realistically this should be Like a monotonic time which is what instant gives you but instant doesn't tell you about the eunuch the eunuch's epic So you can't take duration since It's all a little stupid Arguably we could just like get the time at startup, but but what we can do here is if time is Greater than so time is greater than the prep time and We succeed at this Then true right so if the New time is greater greater than the last time we did a sync Which feels like should most of the time be true and if we like Successfully say oh I see prev time isn't actually set to the current time It's set to the current time plus this period I see so that's why great So really this isn't like I guess this is a sync time So this isn't prev time. This is prev sync time Or something more like it this should really be sync time So this reads much better, I know I specifically did not mean to use the available field I Wanted to do this, but thanks for catching it Hmm oh, yeah, the Intel compiler is a case where you could be on Linux and have atomic barriers to nothing That's good There's a return zero at the top of bulk reclaim you are completely right Good catch Prev reclaimed Okay, so we have check sync time now now we need relaxed cleanup we don't have thread locals so relaxed cleanup Um just does this bit down here, which is self dot retired dot count dot Store zero how does that make any sense? Relaxed cleanup is just Store zero and then bulk reclaim What does their argument for bulk reclaim actually let's make sure it means the same thing it might actually not at all Transitive all right bulk reclaim Should be transitive Num bulk reclaims all right fine we can keep track of that. That's fine and Bulk reclaims is an atomic use size. Why not? Um So self dot and bulk reclaims dot fetch add one and that one is acquire while true Yeah, so this is the example of Where we use tail recursion instead I think I think that's the equivalent here But that's fine we can do the same kind of separation they did So that probably means we can get rid of Prev reclaimed So while true is a loop So we're stealing the retired And that should be with a choir Then an asymmetric heavy barrier expedited Wow, that's that's quite the barrier. Mm-hmm Asymmetric heavy barrier, I'm sure that one is has no bugs either Okay, so that's declared elsewhere. I guess we'll We'll add it there and then figure out what it's supposed to do Thanks a flag Which is a I guess a barrier heavy Heavy barrier kind Which is going to be normal or expedited And I guess we don't actually know what this function does yet. Let's try to figure that out Thought cpp. Oh, no, there's another is Linux M protect mem barrier, which creates a dummy page All right, so this one also, we're gonna go ahead and To do if config linux Add a link to well First of all, let's stick this in here. It's so it's so silly All right, then this business Great that seems like great chances for optimization later 64 bits is not enough time Mmm-hmm. Oh Did they have retired count as a As an ice ice that seems pretty reasonable that way we don't have to worry about this underflow Mmm Think time is e64 Our count is an int now All right, that's fine. Well, we can make it an int retired list What? Where's my retired list? This count by size fine Let's see what we got here While true So we're in a loop and I guess we can I guess we we do have a lot of code just inlined here that That they've just split up into multiple sort of functions. So here they Do a Asymmetric heavy barrier with a heavy barrier kind expedited Apparently They just write full fence anytime they call it but sometimes they use light barrier and sometimes heavy barrier. It's not entirely clear why Rec is has pointers dot load. I'm surprised that they don't do That they don't Like do a shortcut for if the retired list is empty right like okay bulk bulk lookup and reclaim has a while object and Just it's just gonna end up returning. So I'm pretty sure we can just I guess I'll leave it after the barrier But this is definitely fine to just do that But then they have I Find all guarded axes ease so that's gonna be They call it wreck I'm gonna call it First has pointer or has pointers head I guess that one they load with a choir And then But this so really this could just stay the way it was Let's do that And then they loop through all of them, which is the same thing we do here Although interestingly enough They don't skip ones that aren't active Maybe that's because when they drop has pointer They know the pointer as well Which isn't currently something we do Oh This can't say never deallocated anymore either But while the domain lives Unless they have an implementation of Next that skips over active that could also be so that would be in Has pointer wreck probably So what's their implementation of next here? No, that just returns next That's interesting Yeah, so they really don't skip over Over ones that aren't active Does the the destructor? Because of this reset we have a reset to Release that's active to false Yes, it's not entirely clear. This feels like it would it's not quite right I think this does need to skip over the ones that aren't active Folly doesn't skip active here, but that seems wrong Hmm. Oh, well Yeah, so we just record the pointer and here they just use has pointer Which is probably even just a relaxed load to be honest Has pointer. Oh, it's an acquire load. Okay, so we need to do an acquire load here That's fine and for next I Guess next actually never changes Once the thing has been allocated. That's why this is just This is why next isn't even considered atomic in fact, that's kind of interesting Maybe or shouldn't be either Maybe next really just should be a star mute this That it could be I have too many ones now, but I think I think it actually should be I think that's correct Because well when we allocate one. Oh, I need to import Tomic ice ice Once we allocate one it's next never changes again, so why have it be an atomic pointer it doesn't it doesn't need to be That's a fair point Then for each retired object reclaim of no match and that they have in their own little if Self-dot bulk look up and reclaim wreck which is the loaded head No, obj, which is Steel so steel and the set that we made or Not transitive Transitive Then break and then they end there and then I guess I Guess what we'll do is I'm at least my Assumption here is that bulk? look up and reclaim also takes elf takes a Stolen has pointers head Which is a star mute has pointer Sorry stolen Retired head Which is a retired? Yep and a guarded Pointers which is a hash set of star mute What do we even store in there we store Pointer load which is a star mute you ate And then I guess at the bottom of the loop they do Self-dot and bulk reclaims fetch sub one with release And bulk look up and reclaim almost certainly is just the same thing We just did like the same thing. We already had So they call it children and matched But I'm guessing realistically this is just like the same code just phrased a little bit differently So there's a while not node is null So that's the equivalent just are to our like obj. So node for us is stolen retired head Next is object dot next Which is Equivalent to this part right so we set node to be the next one I guess we could say let next is equal to this and then at the bottom say Node equals next. It's like the the equivalent to what they're doing there And that way we don't have to override node quite yet And then Decheck any so this is a debug check not equal object to next So they have a debug assert not equal That node is Not equal to next That's fine. I wonder why they have that but okay I guess it's good to have checks for these things so that when you run something like loom or thread sanitizer Whatever or not really thread sanitizer, but I guess loom is the best one best example here or a fuss tester You want to make sure you have panics if something goes wrong because otherwise your program will just like silently crash If the hash set Contains the raw pointer. What's a raw pointer for them as opposed to just the pointer in object raw pointer is probably just the name they use for for The like pointer to the data Oops Raw pointer returns this. Okay, great So that's not super complicated So that's the same thing is here if it contains the pointer Then No, if they have if it doesn't contain the pointer, that's fine Well, I feel like it's like valuable here to match their ordering unless we have a reason not to Okay, so if it doesn't contain that then object reclaim Object and children Not entirely clear what Children what white children is useful here. I guess we'll have to figure out what what children eventually does but So here we can reclaim it using the deleter. Oh I'm guessing there's like the Reclaimer can choose not to reclaim it or something. Oh, it's probably for They mentioned in the docs we read last time that they have support for like linked nodes so like The deleter can know about the fact that nodes are like Nodes may have in turn have other nodes that need to be reclaimed So this is probably the way that you can say also reclaimed these other child nodes of this node when it gets reclaimed So that's something we don't actually need to worry about right now. This is where the child optimization sort of would be implemented So I guess here we could leave a sort of to-do for ourselves, which is support support linked nodes for more efficient Deallocation Or something Children so that's somewhat unhelpful comment. I guess Otherwise Not safe to reclaim right so here they push it onto matched which is a linked list And this is where we instead do We stick it onto this remaining which is the equivalent to pushing it onto a linked list This now is Oh, this is why it's an atomic pointer for us because We Yeah Okay, let's keep it an atomic pointer then that's fine So I'm pretty sure this can be relaxed Because for them it's as if this was a normal memory operation In our case, we do change it We do change it but only so that we can Rejigger the linked list while we're walking it rather than doing it in a separate pass So they have to do this like oh, I see this is to splice in the children And then they push retired Right. So this is where I See what they're doing. So remember how push retired for them Or sort of our our retire right only takes a single pointer theirs takes a Linked list of pointers Where you want to retire all of them at once and I see so that's why they have that check which is a bull Which all that really does is just stick them back Onto the list And then call like check clean up and reclaim which we can just do in line here really Okay, I think we're gonna change the structure a little bit from what they're doing here Because I don't think we want to recurse up to push retired, but they do And I don't think that's valuable here Because I don't want to have to construct a new linked list to past past to push retired That seems unfortunate Although I guess we can reuse the next pointers probably But realistically what they're doing is just keeping a list of the ones that weren't reclaimed Which is the same thing we're doing here, right with remaining. It's that they called it matched. We call it remaining and We keep a track of the tail because we use that for the atomic apparent swap. That's fine And then they do object will next we do node equals next. So that's fine. Then they have some stuff for has pointer And they do if children on count is zero and Why does it even return a bool? Well, it does return a bool apparently So we don't have children so the children count is zero so the question is whether retired as a null pointer and retired If I go back here Retired is a I think it's just a an acquire load great So if Self-dot retired dot head dot load is Is null But done This is the equivalent of what they're doing Right because we don't have we don't deal with children Then they splice children into matched wh