Hello everyone, welcome back to another one of these long impulse streams. I still need to find a good name for them. I don't really have a collective name for these implementation streams the same way I do for Crest of Rust. Someone suggested Imple Rust, which could be fun given that they're all implementation streams, but I'm still debating it in my head. Today, we're going to continue on the journey of implementing hazard pointers in Rust and specifically what we're doing is porting a library from Facebook called Folly. So Folly is like a concurrency and synchronization library that has all sorts of bits and pieces in it. But we're only specifically porting the hazard pointer scheme from it, which is also described in a sort of proposal, technical proposal to the C++ standard, which I don't think has been officially accepted yet, but it is like a real thing that's being proposed and people are being serious about it. So I figured having an implementation of this in Rust would be helpful. I'm not going to go over all of how the implementation works and stuff again, because there's already Part 1 and Part 2, which cover that in pretty extensive detail. But because it's been a while since Part 1 and 2, I will spend the beginning of the stream recapping a little bit of where we're at, where we left off, and where we're going to go today. The high level summary is that today is going to be primarily about testing, at least that's my intention. Of course, if we run a test and then the implementation breaks, we have to fix the implementation. But my hope is that we start with coming with some decent testing strategy for this because testing concurrent programs is notoriously complicated. And hopefully we'll get to something where we're pretty sure that this works the way we want it to. I'll also take a quick second at the beginning to say I wrote a book. If you haven't heard about this book, then you've been hiding in a dark corner of the internet where my voice hasn't reached you all the time I've tweeted about this. So it's called Rust for Rustations and it's basically a book where I try to capture all of the little bits and pieces that I've learned about Rust and about using Rust and about being better at writing Rust and writing idiomatic Rust over the years. It's sort of intended to be a continuation of the of the Rust language like the original Rust book. It's not a replacement. It's more like, once you feel that you're fairly comfortable with the language, but you want to sort of expand your reach if you will. This is the book to go to at least that's my hope. And you can order it on no starch. And then you get both like the print any book if you buy the print book and it will also be on retailers like Amazon and stuff pretty soon. I also have a Twitter and on Twitter is where you will generally hear announcements about my streams. So go follow me there or subscribe on YouTube or whatever, however, whatever floats your boat, wherever you can get notifications about when I go live. So just a couple of things that I wanted to touch on as sort of a stepping stone from where we ended last time just sort of because a bunch of time has passed, even if you're watching these back to back in sort of after the fact. In reality, it's been about three or four months since the previous part of this video. And since then it turns out things change when time passes. The first of this and this happened fairly quickly after the previous stream is that someone sent me a PR for getting rid of this macro we had to do in the original implementation. You may not remember this but basically we ran into a limitation of the borrower checker that basically meant that we couldn't write a method quite the way we wanted it to because the borrower checker would complain. And we ended up like extracting a macro that did the same thing and that way we worked around the borrower checker, someone submitted a PR that simplified this a little bit. I'm not going to talk too much about this in detail, you can look at the PR if you want to end the linked issues. But just wanted to let you know that I've merged that. So there's a slight diff to what I have locally compared to what we ended the previous stream. Someone also filed an issue about a panic is in has pointer domain drop when using local domains. And about like the counts that we use for retired versus reclaimed items. I'm not going to go into specifically trying to debug this right now. I'm more interested in writing a test that reproduces this problem and then see if we can narrow it down from there. There's also been a bunch of changes to folly itself since the previous stream. So this is the commit that I last linked to for folly itself. And this is the latest head at the time of recording. And there are a lot of commits. We can narrow this down a little bit like folly has a bunch of things in it. So if we specifically want to look at the synchronization primitives, which includes hazard pointers, then I've narrowed that down here. It's just like two pages or so of commits. So this is the commit that we were on at the end of last stream. Since then one of the commits that's landed is this commit which just aligns the Facebook implementation more with the standards proposal for the C++ working group. The biggest change here is that in folly, the protection mechanism, so if you just sort of recap a little bit, right? In fact, let's do this the other way around. Let's open up the test that we wrote, and then just sort of walk through just so we get remind ourselves of the interface. So feels good as a test that's supposed to pass is supposed to make us feel good. So if you recall, the types we export from our library is the atomic pointer type. And sorry, not the atomic pointer type, the atomic pointer type is one from the standard library, the hazard pointer object wrapper type, which is just a thin new type, essentially, around an actual value of whatever whatever kind the user wants to represent. And we expect the user to store that using some kind of pointer interaction scheme. So in this case, we're using box. The reason we need the pointer interaction is because hazard pointers, guard pointer values, right? So the idea is that a hazard pointer is saying this pointer, like this address is guarded, someone is using it. So you are not allowed to drop it yet. And so that's why we're required that there is some stable address that people can protect, which comes in the form of a box in this case. So as a reader, you have a holder. So the holder here is a it's a local value to you that has a single sort of slot for a for a pointer value. And everyone in the domain is aware of every such slot. So in this case, we're using the global domain. They're also local domains, we're not going to talk about those right now. So there's a global domain that keeps track of all of the slots that have been given out all of the hazard pointer holders that have been given out. And when you have one of these holders, you can protect a given pointer value. So what you do when you protect a pointer value is that you atomically load. So this is it assumes you give it an atomic pointer, it atomically loads the pointer value that stored inside of there. And then it stores it in that slot. And then it gives you access to the value. The idea being that because you stored it in your slot, anyone who might want to modify that value is going to see that that pointer value is guarded by your slot, and therefore refuse to make any changes to that value or at least refuse to deallocate the old value so that you can continue accessing for as long as you have it guarded in your slot. As you see the API here is I create a holder, I use the holder to protect the value behind x. So the protect is sort of protect and load, right? So you're going to load the value in the atomic pointer and protect the loaded value. And that gives you back a reference like a real rust reference, not an unsafe one that you can then use to access the underlying values. In this case, we're accessing the the first element of the tuple. And then you can call reset on the holder to sort of end the your protection of that pointer value. And at that point, if a writer, for example, had replaced your value, the old value that you're still accessing here would actually be possible to be dropped. Otherwise, it would just never be dropped, right? If you if you held on to this guard or rather for as long as you hold on to this guard, that value cannot be dropped by anyone. And then this is required by rust safety rules, right? Like the reference you get back here must remain valid at all times for as long as the reference lives. And similarly, like if you drop the holder that implicitly releases your your guarding of the value and at that point, you can no longer use the reference that you got back from protect because the protection no longer applies. And then on the writer's side, what you do is you allocate some new replacement value. And then you call swap. So again, X here is an atomic pointer from the standard library, right? So it's just a a pointer value stored somewhere that we can do atomic operations on. So in this case, we're swapping the value that's stored in there with a different box that holds a different value. And then what you get back, of course, is the old pointer value that was stored in there. And at this point, if a reader comes along and tries to protect and load the value, they get back the the updated values. If you read from my X to you're going to get the updated value from after the swap. But notice the my X, which is the read that we did up here, that one is still using the old value, even though it's been swapped away. And that is because we loaded at the time of the protect and the protect ensures that even though the pointer value has been swapped, the value that was pointed to by the old pointer has not actually been dropped and freed. And we can still access it because it knows that there is one of these hazard pointers guarding that value. And then at some point as the writer, you can say, I want to retire this pointer value now. And when you retire a pointer value, what you're really doing is you're saying to the hazard pointer library, whenever it's safe to do so, you can now free this object. So swapping away the value is not enough to say that it should be dropped. The reason for this is you can imagine having, say, a data structure that has multiple pointers to a given pointer value. So this could be something like a cyclic data structure, for example, where you might have to do multiple atomic pointer operations before it's actually safe to say, this value is no longer reachable, and you can drop it whenever you want.  And at some point you tell the hazard pointer library, this value should now be retired, which means it is no longer reachable. So that's one of the safety guarantees that you have to sort of sign off on in order to call retire. And you also say how to drop that pointer value. So in this case, we know that it was constructed from a box. So we're going to say this has to be deallocated by using a box when you do get to deallocation. So this does not immediately drop the value. So we have this like drop counter associated with this first value we made. And that drop counter is still zero even after we called retire. We can still keep using my x, which is the value we read before the swap and before the retire. And if we try to run a reclamation in the writer, it doesn't actually reclaim any objects, right? It continues to become available. But the moment we drop the h here, we really should have named these better arguably, the h here is the holder that has the protection slot for my x. The moment we drop that, then now it's not like it gets dropped immediately. But the next time the hazard pointer sort of mechanism gets to retire objects, which tends to be whenever you sort of invoke something inside of there. Like for example, the next time you call retire on some value, or in this case here, if you call eager reclaim, then at that point, it realizes that okay, this old pointer value, which is the one that pointed to 42, is no longer reachable. So it's been retired. And there are no hazard pointers guarding this pointer value anymore. Therefore, I'm okay to actually reclaim the value. So the nomenclature here is you have a value that's live. So that's one that's actually reachable. It has not been retired. And therefore, it cannot be reclaimed, it cannot be dropped. At some point, a value becomes retired, which means that it's no longer reachable by new readers, but old readers may still have access to it. A retired object cannot be reclaimed yet. It cannot be dropped because there may still be active references to it. But it also is not reachable by new ones. So eventually, like over time, fewer and fewer readers will be guarding that pointer value. At some point, that value becomes reclaimable. So that is, it can be dropped. And that is the point at which there are no hazard pointers guarding that pointer value anymore. So if we look at the state of the old pointer, the 42 pointer, up here, it's live before we do the swap. After the swap, it's like, it is retired, but we haven't let the library know that it's retired yet. Here, we notify it that is retired, but it can still not be reclaimed because there's a hazard pointer. The moment we drop h here, it becomes reclaimable. And then the moment we call eager reclaim, we are actually reclaiming it, which then means dropping the value and invoking the the deleter that we associated with the retire. And at this point, you see that the 42 drop count becomes one. The new value, of course, is still not reclaimed because it's still active. It's not retired. And even if we drop the handle that was used to store the the 9001 value and then try to reclaim, it's still not reclaimed because it was never retired. Therefore, it's still active in the data structure. So new reads might still access it. And therefore, it can't be reclaimed. Okay, so this is just like the recap of the interface that we have. And it's not super pretty, right? It's very low level. You might imagine, for example, that we could construct a sort of we could construct our own atomic pointer type, for example, that deals with many of the nuances here itself, like the fact that you have to pass in like deleter's drop box, right? Instead, we could say we have we provide an atomic pointer type that internally always uses a box. And so you never need to do this. One and three here are always true. The retire probably still has to be unsafe because we don't know how the outer data structure is constructed. So we don't know when an element is no longer reachable, but at least it simplifies the safety invariance. The same thing with protect here, right? Protect requires that the pointer value you give it is actually valid. And we would know that that is always true if we provide the pointer value. And same thing, we could guarantee that retire is being used. Because we could, for example, refuse to do swaps unless they're unsafe or something. Like we could probably tidy up this interface. And that might be something we do eventually, but you could imagine that actually being a different crate that wraps what we provide in this library, rather than us baking it into the library itself. It's nice to provide this very low level interface. You can build nicer abstractions on top of because the the lowest level primitive here is quite powerful. And it's nice to have that flexibility to use it in in different ways. So that brings us them back to the change that was made. So the first that they made is for in folly the protect method that we talked about. This is the one that you have a hazard pointer holder and you protect a given pointer to a pointer, right?  And then you get a reference to it. It used to be called get protected. They've now renamed it to protect, which is the same value we always used and is what is in the spec. And the other thing is that they renamed reset, which is the sort of thing for giving up the protection that you have to reset protection. This is a change we can make pretty easily. So this is over in a holder, right? So we have a reset and we want to call that reset protection. That is sort of the the nomenclature they want you to use here. And at that point, this would be reset protection, right? And I sort of understand why they made this change because it's not clear what resetting a hazard pointer holder means, right? Are you resetting the pointer that you're currently storing or are you resetting the protection of it, right? Whereas reset protection is very clear, you are resetting the protection just to see that this still works. Great. So that's a minor change, but let's check that in just to keep the similarity with folly adopt name for reset. That's annoying. And then if we look back, that's the only one on this page. That's why I wanted to get it out of the way. So really it's just this page of diffs. If we look through, so this seems to be a round hazard pointer, you'll see that this is the whole synchronization directory, right? So there's a bunch of stuff here that that doesn't really affect us. There's this one, there's this one, there's this one, this one, this one, this one, this one, and here there are a decent number of them. This one, this seems to be about locking. Yep, and this is more hazard pointers.  Just looking through the diffs. There's like a bunch of stuff in here and this is why I wanted to keep the names similar. Remember when we did this original implementation stream, I was like we could tidy up the interface here to sort of give these things different names. Like if you look at domain, for example, we have like hazard pointer domain is not a very Rustian name for a type. We have all these helper methods like check cleanup and reclaim that in turn is called try timed cleanup and all of these just match exactly what was in the folly code base and I think that's something that's going to turn out to be really beneficial now because it means that trying to follow these diffs is going to be a lot simpler because we use all the same name so we can almost just like port the PRs, right? The question now is whether we want to do the work to actually let me make this dark because I know people are sitting in dark rooms. The question now is whether we want to go through these and apply all of these changes to our port or whether we want to get started with testing first. I'm a little torn because on the one hand it's tempting to just do the testing first because we have something that we sort of think works and it means that we don't have to sort of spend all this time looking at diffs and trying to piece them together into what we have but the downside of doing it is that these might these changes might be fixing actual bugs so when we write a test suite we might just end up reproducing bugs that have already been fixed and it's kind of nice to not do that right to just have the fixes already and then test something that's closer to being correct. All right let's see roughly how bad we think these are so let's read through the descriptions of them. Change the constructors for hazard pointer holder and add the function make hazard pointer to be consistent with the working group. Arrays we never implemented that's fine. Now the default constructors construct empty holders and arrays the free function make make hazard pointer are used to construct non-empty holders and arrays. Okay so this is about the constructor for hazard pointer holders where oh I see a bunch of these diffs actually aren't relevant to us because they're in consumers of the hazard pointer library. That does make this a lot nicer so let's just collapse these. I think it's worth going through these diffs. It'll also be a good way to sort of page everything back in for us. So let's start with the sort of top level hazard pointer dot h file. Right so this is I think they called this out initially yeah that I see. I think it used to be that for them in fact I think you'll see this pretty clearly here.  Let's see yeah so here they used to have a constructor where you could immediately guard a value. But it seems like they still do is what surprises me. This change might actually not matter for us. They say you have to explicitly call make hazard pointers. Resid protection that's fine. So they provide a free function for constructing a non-empty holder. Right so make hazard pointer takes a oh right. Okay so I remember what this is. This is I think this is actually very very useful for paging things back in. So the holders remember have are actually a little weird because the holders are they don't themselves have a slot the holders hold a hazard pointer and the hazard pointer has the slot. So the idea here is that you construct a holder then you acquire a hazard pointer which is one of these protection slots from the domain you put it in the holder and at that point you can keep using that without doing synchronization with the domain every time. And then you can release that hazard pointer back into the domain at some point. Yeah right and what we've currently done and I think this is what the Facebook one was doing too is that the constructor for a hazard pointer holder for us will always acquire a hazard pointer from the domain. And what that diff is doing is it's saying the default constructor should not acquire for you. The default constructor should just give you a hazard pointer holder that doesn't have an associated hazard pointer yet. So if you look here the private constructor that's fine where's the public constructor? Yeah so the default empty constructor constructs a hazard pointer holder which internally contains a hazard pointer holder but no hazard pointer. And then if you want to actually fill it with a hazard pointer inside then you have to call a make hazard pointer which is the thing that takes a domain and that acquires and then constructs. What's weird here is why. Why did they change this? Oh that's a very good question. Right because it makes it a lot more annoying to construct one. What are they changing domain? These friend classes are weird stuff. Hazard pointer forward. Yeah it's got to be so construction is cheap. I think you're right. I mean it's a simple enough change I suppose. I'm just like when would you ever just have a hazard pointer holder that you never use. Also make hazard pointer I assume you can pass no domain to right like these calls where you don't actually provide a domain where's the this one. Presumably defaults to using the global domain although it's not entirely clear how because the free function here always takes a domain. The other thing that's a little weird is remember how our hazard pointer holder is tied to the lifetime of the domain that you constructed with and it's not entirely clear if you don't specify a domain what this would be. One option here right is to say okay we're gonna implement default for a hazard pointer holder specifically for static what's f here. f is the like family stuff I think we set up. Yeah so the idea here was that to make it harder for you to accidentally use a hazard pointer holder hazard pointer from one domain with values from a different domain and to check that sort of at compile time so it's a little unclear what we would even default this to. I think what we would do actually is just implement it for like unit right and then what this would actually produce is a hazard pointer holder I think this would have to become an enum that's either empty or acquired so this is going to become an empty I really want these variants to be private so we it's really annoying to me that you can't mark variants as private I think we'll get it one day but in the meantime what we'll do is something like this or a hazard pointer holder really has a hazard pointer holder inner domain f it's real annoying so this becomes a non-public enum and so this is going to be a hazard pointer holder hazard pointer holder inner static of this and in fact this is going to be an empty so the idea would be that rather than we could still have global be like a handy shortcut right so this is what they call the the make hazard pointer so if we do this oops and then the other thing we would do is this is where it gets a little bit weird right so here what we really want to do is say that this takes a domain and returns a hazard pointer holder for that domain and for the given f so this is going to be generic over f2 I guess um actually it doesn't even need to it can just be f and this would be a self of hazard pointer holder inner acquired um and now the problem we run into is exactly this which is what I observed about the c plus plus code right which is how is it possible to call it um without an argument which is you might be able to get this with sort of overloading in in c plus plus land but in rust we don't have specializations you can't really do this um this name is also weird for me I guess it is it is indicative of what actually goes on right which is hazard pointer holder doesn't make a hazard pointer by default um so what you do is you say by calling this method your explicitly sort of saying I want you to create a hazard pointer for me for this holder as well um I guess we could say make global right and then this would not be global um and this would be domain and then this can return self that's fine uh make hazard pointer um and then I'm guessing that they have some right they have a constructor see what I think what's weird to me is okay let's say that you use this constructor so now you have an empty one how do you fill it right um in fact let's go back to um where is that file even going to be it's going to be over here um so this is the state of the project at the time where we ended the last stream so if we go to holder what do we have here um right so this implicitly created one in the global domain in the past yeah right so so they used to have this constructor which was domain which is equal to the default hazard pointer domain and they had a destructor but did they have something for specifically setting the domain if you constructed as empty right if you use this empty constructor then how do you later set the domain and I don't see a way to do that yeah I don't think there's a constructor for that at all no the example of top here just shows it like like it seems like you just always construct the global one no set HP rec is a little bit different because uh where do we have it um oh did you mean in the in the final source like over here um so the example here does not show how to do it uh this is constructing from a given domain this is constructing from a different holder is the move but I don't see a way to retroactively set it for a given domain yeah it's it's really not clear to me why that API is sort of superior because I'm a little tempted to just not support it I guess like we could do this actually I wonder what does protect do maybe that's the thing to look at what does protect do if there is none if you call try protect and you don't have an HP rec what happens uh try protect source dot load it doesn't oh I think they need the empty one for moves they need something to leave behind when you move yeah but why I guess it's like okay let's let's think in sort of rust terms right when would you want to be able to just construct a default value to put in there and you might actually want to do this if you want to do something like uh mem swap or mem replace or mem take for that matter um right like if you only had a an exclusive reference to a hazard pointer holder and you wanted to sort of steal it away from where it currently was then mem take would let you do that only if there was a default implementation and you would want the default implementation to be cheap but this is pretty rare in rustland um yeah and like you as a user you can always just wrap it in option um well I like we could totally do this right of sort of any any you can always construct an an empty thing of any type um but like here I just feel like I would tell the caller to use an option like why should we basically implement option internally in the library that doesn't seem worth it I think we're gonna ignore this change and keep what we had I think it's was I think it was a useful exercise to realize why but I don't think this is the right pattern for us recent production I think we should keep all right so that means this first diff is one we can ignore all right next diff remove unused hazard pointer domain data members unprotected and children and the function reclaim unprotected safe that's fine we don't have any of those because rust would tell us about these unused things so that goes away no need to do anything improve readability specialize friends and use specialize aliases reduce use of the atom template parameter okay this I don't think is going to affect us this seems like C++ faffery yeah this is irrelevant to us great we're speeding through these support class and function names consistent with WG2 so they've renamed hazard pointer to has pointer holder isn't that the name we already use yeah has pointer object base has pointer domain I think these are all values oh I see is are the left ones maybe the left ones are actually what are in the proposal sorry this is this one's bright that's fine yeah so here you see the the sort of example they give right of hazard pointer holders are called hazard pointer I still don't understand why yeah all right so this makes me think that we want to conform with the with the names that are used in the spec right so we would rename hazard pointer holder to hazard pointer because in practice that's just that is how the user will actually interact with these in fact the way the code is structured right that the hazard pointer type I don't think they even deal with like all the methods are pubcrate so I think what we'll do is I think that change is a good one so let's go ahead oh do I not have a code action set for this I thought I did that's fine so let's go ahead and say that has pointer holder is going to become hazard pointer right and our has pointer it's not entirely clear that that's even a type that exists in the c++ world in fact I wonder what that code actually refers to like if we go in and look at the code in here what does has pointer holder holds a has pointer rec and we don't have a separate rec so I think really what that means is has pointer is going to be has pointer rec as in has pointer record so in that case let's go ahead and move pointer to record go to lib hazard pointer I don't think this needs to be pub at all so I think that can go away we do need this to be record and then we want record to be has pointer record that's fine and arguably we could give this a nicer name too but I think I think it doesn't really matter because it's entirely an internal type so domain is going to probably come has pointer this is going to be has pointer record that's pub crate so that's fine that's fine that's fine that's fine and luckily now we should find out pretty soon whether rust agrees that this type can be private but I'm pretty sure it can this one this one complains about and holder this is going to be I guess yeah fine we can retain this as pub crate use record has pointer record the reason I like having these pub crate uses is because it means that I can move this around and not have to change everywhere test lib is obviously going to be sad but I think this is actually for the better because now this is going to be hazard pointer and in fact I think what I want to do is I think they're onto something with the make keyword I think I want this kind of nomenclature to indicate that the hazard pointer make is not a free operation right it's not just like an empty constructor it actually has to do work and at that point like this will be make global um this will be hazard pointer make global same thing here as pointer holder is hazard pointer see if that compiles it does not because this is make global great I like that much better and I think this is almost certainly going to also complain about some of our doc tests apparently not which seems dubious remember we have these compile fail tests and these will almost certainly now fail for the wrong reason this has to be hazard pointer make in domain so I mentioned this when we made them that the problem with writing compile fail tests these wet this way rather than using something like try build is that you don't get to check why it didn't compile you just get to check that it didn't compile and in this case it's going to start not complaining for the wrong reasons making domain this is also going to have to be make in domain hazard pointer and this is going to be make in domain they're still going to pass because they don't compile but now they don't compile for the right reason we can check this right so we can run without this and you'll see it'll fail ooh no method load that's interesting that is not the error I was expecting that's because there's another bug in this which is this should say protect and now it'll say yeah here so now we get the correct thing that the the trade families don't match which is what we wanted to get all right compile fail back on here if we do the same thing up here and I do this I get family error and if I get here protect I remove the compile fail then another family error okay great so now they don't compile for the right reasons what other renames did they do in this they renamed has pointer domain to hazard pointer domain I mean that's true we could have this be hazard pointer domain really I want to just name this domain and hazard pointer just pointer in fact I will rename this to domain because it really just shouldn't be hazard pointer domain isn't necessary when you have modules that the qualification isn't necessary so I'm going to go ahead and do that and that's probably going to make a bunch of things not compile ooh same thing here object same ooh holder uh f is never used oh that's because it can no longer find domain which is now here and testlib is going to make the same change and now that looks a lot nicer right because the reason why there's no reason to have that prefix is because it already comes from a crate by this name right so if you think about it if you really wanted the qualification then you would just instead of saying domain you would say haphazard domain right and just don't import it without the the rename and hazard pointer I'm more conflicted about I'm sort of inclined to keep the hazard in the name there because it isn't a pointer it is a hazard pointer that's like its type and it could be a haphazard pointer but it's in that sense it's more like a guard but it's not really a guard it's like a maybe guard or a thing that can guard so hazard pointer seems like the way to go why hazard pointer is not epic based reclamation this whole table in the in the C++ proposal that talks about the differences I'll send that thing here why did you rename it with language server that's what I said I thought I had the alias set up but apparently I don't and I don't want to go look it up now hazard pointer default domain that's fine we just use global so that's different I don't think the rest of these really matter for us that's fine we can close those fixed typo and hazard pointer that's fine I don't think we ported that error so this is going to be the only reason I have to go through these is because there's one note in here that's like a note to myself that I left in a comment which I really should have just stashed before I started this where is it this comment and this comment yes, yes, yes, yes okay so this is going to be better match names from spec I really need to set a longer expiry time out for my key because that's annoying fix a bug in hazard pointer object cohort handling of children of reclaimed nodes so that's not a problem because we don't support children or cohorts so this one we can ignore fix flaky test that one we don't have to port because we don't have the test yet extend cleanup to cover cohort objects well this is certainly interesting because this seems like it's doing something else than it purports to like it might well be doing that too but this is changing code that doesn't have anything to do with cohorts this change includes incrementing num bulk reclames before invoking due reclamations either directly or in an executor the corresponding decrement is done at the completion of due reclamations which may happen on a different thread if reclamation is done in an executor all right I mean this seems like a thing that we just need to this seems like it's a bug fix that doesn't just matter for cohorts so they have relaxed cleanup why don't we have a cleanup method it feels like we should have a cleanup method there's load num bulk ink num bulk deck num bulk that's fine check why don't we have a check threshold and reclaim either do we have a wait for zero that's interesting why don't we have those methods let's look for check threshold and reclaim it didn't exist in our version oh I'm in the wrong file so that's not very weird here in the version we had push list do we have a push list oh push list is the one that's used when you want to reclaim multiple items sort of as a group rather than individually currently we only support retiring individually and I'm guessing the push list yeah I think we just don't do push list we have push retire which is for retiring a single one but I don't think we have push list and push list is the only thing that calls check threshold and reclaim which is why we don't have that it might be something that's like worth adding but it seems this seems more like modification to a new feature uh although it's doing this even for things that aren't tagged it's a good question actually like if we look at here is there a call to push list check threshold push check threshold push comes from push obj there's so much indirection here which is pretty frustrating so retire just calls retire on the domain for us yeah I don't think we have the same I don't think we have the same logic as they do here so I think that's okay I think we can ignore this this would only oh is this in a method that we have do we have a do reclamation method we don't all right I think that's fine I don't think then that this actually makes a difference for us that's fine eliminate thread local list of retired objects non-core retired objects are pushed in directly into the domain oh nice this is already a change that we have we don't do this anyway that's fine in fact like we didn't implement the thread local has pointer optimized in any way so anything that relates to that we can just ignore so this changes entirely irrelevant to us consolidate non-cohort and untied cohort retired objects so this actually is going to be a little bit of a pain for us because here they're making it so that there's not special handling for things that aren't using cohorts we implemented only the things that are not using cohorts and now they're saying you got to use our logic for cohorts which would mean we have to port that which is a little annoying yeah so right now we're going through the the commit list of relevant files since last time and then making those modifications to our code and then we'll add the tests on top of that yeah so they got rid of push retired which is a little awkward for us actually because it means that we sort of have to implement their cohort stuff which makes me a little bit sad right so we have oops right so we implement the retired list but with this change they're getting rid of retired and not special handling those things so it's going to be a little bit of a pain right because they're they're storing those in this retired list instead which means we're going to need to implement retired list I don't really want to make that change but to follow along with this we might have to let's see if we can rebase these that gets even worse because now they're sharding that list so we're gonna have to do that too huh so so the advantage of the previous change of this change is almost certainly simplification right because previously they had implementation for cohorts without tags cohorts with tags and non-cohort retire and we only implemented non-cohort retire but they had two and a half code code paths for this right because cohorts tagged and untagged are share a bunch of the code paths and then diverge further down whereas the the non-cohort code path was just different and we were only implementing the non-cohort part but for them because they want to support cohorts which we really want to do eventually too right having the non-cohort path as just a separate code path means that there are more opportunities for things to go wrong so if you can get rid of them like they did in this commit then now you have more shared code right so if if you have a bug in one you have a bug in the other but if you fix it in one you fix it in the other so that's why they make this change and I think that's pretty reasonable all right let's go through and make that change then this is going to be a good way to sort of dig into some of the some of the deeper stuff I just want to see how much it changes later right so this is a change to shard the untagged list which is probably to avoid contention on it so that makes some amount of sense this is right so they have this like ability to have executors that do reclamation like in the background for example like you could imagine you have a a background thread that does reclamation every so often rather than forcing the threads that are retiring to do that reclamation and that's something we didn't really implement so I don't think this one's going to make too much of a difference to us this is a change to the tests which doesn't matter because we haven't implemented them yet this is adding a benchmark nice that's something we can eventually port that's fine ooh that seems like a good change and this is something something improving reclamation all right I think we should do these one at a time I think that's valuable because they seem like they're fairly disparate changes so the reason I don't want to write the test yet is because my my inkling here is that there are bugs like the part of the reason they did this I assume is because there are bugs in the implementation and by unifying them you're getting rid of some of the those bugs and I don't really want to test known broken code it might not be broken but I worry that it might be and we were like we have a very basic top-level test right so so we know that the basic scheme works so I think I want to port these first because I don't think that the old code matters in a sense once we do this port all right the one challenge here is going to be that as part of moving from push retired to push list which is really the core of this change we will have to implement all of push list which includes a bunch of other machinery that we're going to have to grab from that file the nice thing here is I think we'll just have to do this and view the file at that commit and what am I going to do about these notes I'm going to what do I have in my stash oh and then I'm going to stash that all right so they're getting rid of retired and then instead they're going to use this untagged so we're going to move this from retired to untagged their type is called retired list which is a little interesting right we didn't use this type we use this retired list type but I don't know if our retired list is the same as their retired list this is something that I guess we will find out and then when we call push retired oh this is in where in retire oh why do we do that in bulk look up and retain what do they do to the bulk look up and retain then oh they give the entirety of tri bulk reclaim and bulk reclaim see this is why they made the change right because all of this can go away because they can just use the cohort stuff it's just that that's all the stuff we had well even better of a way to make sure we understand what the code is doing okay so they really get rid of this whole thing huh all right that's fine I guess all right retire so what do they do in retire now um so in order to retire you have to construct a retire note that you stick on the retired list right so the idea here being that you're basically keeping a a queue of objects that have been marked as retired and then at some point in the future something whether that's a future thread that calls retire or some background executor is going to walk the list of retired objects check which ones are actually reclaimable and then reclaim them so you construct one of these retired nodes that is basically the the type of the things that you're going to stick on that on that linked list and then you push it so here this is where we stick it at the head of the linked list right where they basically we I think we basically inlined push retire here so push retired is basically from here and onwards this is where we construct the node and then this is where they have a barrier and then move to to stick it on the end and then if check clean check up and that's the same thing we do here we stick it at the head and then we do check clean up and reclaim um which means that now this is going to change to uh self dot push list of retired and then if we find so they don't have a push retired they just have a push list and we're going to have to implement the same thing so push list in fact we can just stick push list right here for now so push list is going to take a self and a does it need to take it might need to take domain that's fine and a star mute in fact it doesn't need to take a star mute it can take it can take a retired what we have over here retired just takes this one that's fine so we don't need this uh so this I think we're gonna have to require that it takes a box retired we could box internally in this function the reason why it's nice to let the caller do it is if the caller for some reason already have a has a box then you they can still call this method they take a list not an item well so only kind of they take a linked list node that may or may not be the head of an existing list and that's the same thing we do too right uh if you look at retired it has a next pointer so it could itself be a list so think of this as it's a node in a retired list um which may or may not be a list like it could be an item or a list but that's sort of the nature of linked lists is that any node is a list um so what do they do in pushed list if the list is empty all right so if how could the list even be empty I don't think the list can be empty in our case and I think what we're also going to do is work under the simplification that we're only going to retire one thing at a time for now so what we can do here actually is like assert a retire dot next uh is that an atomic pointer it almost certainly is yeah and but we can do get mute only single item retiring is supported at the moment is null um all right so what are they doing here they read out a cohort tag we don't do cohorts we don't do tags so that's fine then they do a light barrier um they do a list from head to tail that's fine if not tagged then untagged dot push so this is going to be um untagged is a retired list and I think here we should really just help ourselves a little which is just add a retired list push items or I guess this is like a sublist retired right because this code is entirely generic uh and the sublist is going to be box into raw of sublist right because we're going to be sticking on we're going to be sticking raw pointers on there um they read the head up here which we're going to have to do up here and self dot count fetch add so here there's like arguably this should this is one of the places where um this one technically needs to count how many items are actually in that list right in order to find the right count here we can do that right there's we can say let n is uh n is zero um and then we do something like actually we can do let n is and we're going to do this introduce a scope so that in here we can borrow into sublist um next is sublist and then we're going to do while next while cur dot next dot get mute and here this can be an unsafe fact this can be a get all they all explain this code in a second just um so we're going to do this no we're going to do while cur dot next dot get dot is no we're basically just counting the number of items in the list um and we're going to set cur is equal to that uh is there not a I thought atomic pointer why am I not getting autocomplete not entirely sure atomic pointer oh this might be bright no it's not okay um so when you have a when you have a mutable reference to an atomic pointer then you can just call get mute to get its actual value um but I think that's fine we can just do load uh of ordering relaxed relaxed and because the idea here is that because we own the head of the list we know that no one else is modifying the rest of the list either um so safety um we own the head of the list and thus also all of its elements and uh a retired can only be constructed from valid elements um yeah maybe maybe right maybe this should be a like fn len of self um that returns a u size the only challenge we're doing it here is that here um you no longer have the guarantee that you own it I guess what we could do is this actually but uh that down here we can safely dereference because we know that we own the list we own the head of the list there are no other owners and therefore that list is not going to change under us we could have it be a length that takes a an exclusive reference to self and that is probably good enough like if you have exclusive access to the head of the list the question is does having exclusive access to the head of the list mean that you have a guaranteed that you can dereference the next pointers and I don't think that's true so I don't think I want to add it as a len there I think I want to have it be um explicitly just in push where we own the source um so this is now going to be n plus equals one and this has to start at one because sublist it it starts at an element of one and then it returns n um I don't understand why I'm not getting not entirely clear let me try this why I'm not getting any um auto completion anymore oh well uh so n I mean it could be you're right it could be an unsafe helper function I don't think we'll need lend anywhere else though um so n is going to be there and then we're going to fetch add n here so if we now go back to this change um we're basically implementing on tag.push may not be locked yeah so I think this like retired list that they have is probably something we need to look at more carefully so where did they get their retired list from the hash pointer detail shared head only list so has pointer cpp oh is there a hash pointer detail detail hash pointer utils thread save linked lockable list that maintains only a head pointer supports push and pop all it's lockable that sounds pretty painful I wonder if we can get away with not allowing just not supporting the locking part of this actually because my guess is that the locking is needed because of the the sort of cohort bits or maybe because like tagged is also a retired list but I don't think we need that functionality and untagged so for now I'm just going to say this is just going to stick it on to the head of the list uh and the other thing that's awkward here is so there's one more change that has to be made so that this actually can support a list which is that this has to change the next of the tail of the sub list not the next of the first element otherwise it only supports one element so this is going to be last I guess last next so we're going to set this is going to be oops it's going to return n and cur dot next and this has to be right so we're turning a raw pointer to the next pointer of the tail of the list because that is the thing that we need to modify so that it points at the head that we're replacing right so you have a current link list right which has a head here and we're inserting a list here which is as a head and a tail and we need the next pointer of the tail to point to the head of the old list right and in order to do that we need to know what this next pointer is so that we can change it and so that's where we're computing up here now this then is going to be instead of unsafe like this we're going to say last next oops dot store head ordering doesn't even need to be that it can just be the release as atomic pointer right and it does need an unsafe this safety we haven't moved anything in retire and we own the head so last next is still valid right so we're storing the the head that we got from the list into the next pointer of the tail of the sub list we're inserting and we're doing that in a loop right because the head might be changing under us great so now and this has to be just self actually i'm lying this has to be now if we go back to push list we're not tagged so we're gonna do self dot untagged dot push retired and then what does it do it does add count and then check threshold and reclaim l dot count so we could probably have our push return the number of things it added that seems pretty reasonable so that's going to be n so it has a an add count i'm gonna keep this one for later and just in case we need it so that's going to be here add count is count dot fetch add that's very unhelpful i see count is really so remember how we have our count i think our count is just going to become i think that's just the count of the number of things in untagged in our case which we store as an item of retired lists so we don't actually need to do anything special here because this add count is a part of the push into untagged like this count is already kept inside of untagged so we don't have to do anything about that in fact that also means we don't care about why is this an i size should be a u size oh as i size that's why so push list up here that does that and then it calls check threshold and reclaim so this is no longer going to be check cleanup it's going to be check threshold and reclaim uh which is this method right here which calls count threshold this is the same thing that we went through last stream right of we need to fall follow back like all of the methods that they have and then eventually we can probably tidy this up a little bit but but for now we'll just do it the way it's given so check count threshold is i'm guessing load count is actually just going to read from count which is the replacement for our count which is the count value inside the retired list of untagged so check count threshold returns a u size possibly an i size so so our count is going to be self untagged count that's easy enough dot load and how do they load in load count acquire that's fine and then while our count is greater than threshold all right while our count is greater than threshold and threshold came from over here and i think threshold we already have case ah i thought we already had this one like h count multiplier we definitely use somewhere we have reached threshold i see but we don't actually have threshold so we're gonna have up here const of n threshold um takes no arguments returns a let's say u size and it returns the max of the k threshold which is a value that i don't think we ended up using or rather i don't think we made configurable um which is a little awkward actually because we're gonna need it now is the r count threshold right and the r count threshold is a thousand which i think we have up here in a value yeah okay so our count threshold is really what threshold is so this is just going to be our count threshold uh well i guess we can just do max that's fine of that and the k multiplier times h count oh so this is not a const because it takes self um and it's the k multiplier which i think is the same as the h multiplier why they have multiple names for this is not entirely clear k multiplier is two which is our eight count multiplier okay so h count multiplier times self dot an h count is is h count dot load uh so what is our h count i think the h count is the number of hazard pointer records um so this is going to be has pointer why do i not have autocomplete it's very unfortunate dot load uh and that's loaded as a choir yeah so this is going to end up being an i size um so now that we have threshold uh check count threshold so um i'll think if i remember from last time um this is really just trying to it's sort of a heuristic that they've implemented for figuring out whether or not you should run reclamation because you don't really want to run reclamation every single time someone retires an object for example you want to do it only when the rec reclamation list or the retirement list is getting particularly long and so that's why they have these like multipliers and stuff it's not really a part of the data structure is more a part of the heuristic um so it's while our count is greater than self dot threshold uh then if cast count oh that's weird so here what they do is they're trying to do self untagged count compare exchange week of our count to zero right so they're trying to set it to zero and if they succeed then they do whatever this is which we don't know yet um so they're matching on this or actually they're just saying if uh this dot is okay then return i count our count otherwise return zero and then they do set due time uh i don't forget if we did this time optimization we do have sink time but we don't have due time so let's add due time in here oops that's not what i meant to do um yeah i'm guessing what this is really gonna be is um all of i think sink time is related just to retired so i'm guessing these methods are all going to be deleted and it's not going to be the untied somewhere i mean i don't think i have a syntax error that's severe but yeah i don't know what uh it doesn't seem like it's particularly confused although it seems to think that maybe i have two of them open not entirely clear um i'm gonna add a little helper function here and do it's equal to now it doesn't even take self yeah i mean it could be because there are a bunch of things we haven't changed yet uh so set due time is that called anywhere else it's only called there they have a lot of these helper methods that at least personally i would just not do um so they have a due time so self due time dot store uh self now plus the sink time period yeah see i think this is the same as sink time and it's just been renamed um but that's fine we'll just this and ordering probably release uh what do they do for that it's acquire release and relaxed it's this is very very annoying but fine ordering relaxed i am glad that there is no um there doesn't seem to be a microphone trouble this time though so that's good uh great so now we have check count threshold so this next method this one check threshold and reclaim is going to be uh let our count is self dot check oops uh check count threshold and then if our count is zero then check due time and what does check due time do check due time returns a u64 maybe no it returns a u size so it does time is self now and then it low see they have like even though load due time is only called in this one place they have a helper for it which seems excessive uh let due is self due time load um so here i think this is just try to try to have basically they're trying to make it so that you reclaim objects either if a certain amount of time has passed or if a certain number of objects have been um have been acquired i've been retired uh doesn't calling system time so often put a big limit on maximum performance it shouldn't i mean it is true that a system call is expensive but in general it shouldn't be because it's using um oh i forget what it's called now it's not a traditional system call it gets the load from like basically shared memory with the kernel uh in general you get to do this when you're um just reading time uh so it should be fairly fast especially there was a recent pr that landed in rust that that um changed how we extract these these time stamps uh which should help with this as well uh so it's going to check the due time and if time is less than due or cast due time all right uh self due time compare exchange not the weak one it's going to be a choir release of due with time plus sync period from ordering a choir release to ordering relaxed oh or this is oh i see um so the the idea here is that if it's not yet time or if someone else has updated the due time is what this is saying sync time period right so uh if this compare exchange fails then that's because someone else has updated the due time which means someone else realized that they needed to do the swap so that's what this or is for um because we don't want like imagine two threads are both calling retire at the same time they both check due they both realize that you're due and then they both run reclamation and we don't want that to happen so that's why this this extra sort of second uh clauses here uh so in that case return zero not yet due or someone else uh noticed we were due already otherwise return exchange count which is just self dot uh untagged dot count dot swap zero with a choir release so this is now an eye size all right so back to check threshold and reclaim um we do if our count is still zero uh then there's nothing for us to do okay so i think the idea here let's try to reason about what it's doing so far check count threshold is looking at okay so check count threshold here is basically you can think of this sort of as a not quite a lock or semaphore but it's basically like it's trying to change the number of items really this shouldn't be under untagged because it's no longer really the the length of the list because we're we're sort of mutating it all over the place um but what we're doing here is checking whether we are able to set it to zero if we're able to set it to zero then we return the number it was before it became zero if we were able to set it to zero we are responsible for reclaiming the items um so if that's the case then our count is not equal to zero and we're going to go on and do reclamation if we weren't able to set it to zero because for example it changed under us um then we go and check whether reclamation is due anyway if reclamation is not due either then we just return there's nothing for us to actually do otherwise either it's due to do either it's time to do reclamation and we sort of won the race there or the we managed to set the the number of items to zero in either case it's our job to do reclamation so that's down here it's like we discovered that we should do reclamation there might still be other people doing reclamation but we should be one of them um um so num bulk where's the counter for this this one so we're going to start a bulk reclamation um yeah you could totally have two reclamations running at the same time although so you could do that even if you just had a reclamation running for a long time if it runs for more than sink time period um so so you it doesn't actually you don't get this guarantee even if it's monotonic um if it is monotonic you might have fewer sort of false races but i think that's it this one is if adam int is the same as standard atomic int and we're in the default hazard pointer domain and we've been told to use an executor then invoke reclamation executor okay we don't support executors so we're just going to ignore that for now and we're going to call due reclamation self dot due reclamation of our account great so now we need now we need due reclamation all right so due reclamation self our count i size hello cat um while true great luckily we only have to deal with untagged for now um so let's see what we got here uh this is going to be a pain all right so we're doing let untagged equals i guess null um bool done is true extract retired objects okay so this is actually going to be pretty simple because we don't have support for for tagged and this shards loop is only for tagged so really all we're doing here is uh we're just we're just taking retired that's actually all this is doing so in here um the place where we used to call self retired uh where's the place where we steal it it's down not here where do we take this oh it's probably gotten swap maybe yeah here so in bulk reclaim right which remember is going to go away we have this code for stealing the entire list and i think this code is going to turn out to be basically exactly the same as what this unwraps into um so let's go ahead and we know this goes away so i'm just going to delete this here and i'm going to grab well i'll leave it in place for now but we can at least do this so due reclamation is going to steal the head of retired that's all this really did um and if steel is null then it's not quite true we're going to do nothing because we have to do this bit so this is going to be uh if not steel dot is null then we're going to have to do this business and this is going to be the same logic that we used to have right which is find all the guarded addresses so that's this load has paint pointer vowels right so that is walk all the hazard pointer records and then store them in a set which is the same thing do we do here we create a hash set we walk all the records and we insert them into the set it's not clear why folly doesn't skip the active ones but that's fine so i think this logic is still sound so we're going to go with this here uh so back to this we don't have tagged we have match reclaim untagged and so this is where it's going to be interesting so uh untagged here gets populated by extract retired objects so where does done come from that's the other good question let's see what match reclaim untagged does it's going to walk uh and this has support for this like children stuff which we don't actually care about list match condition untagged match no match right so stick anything that matches into this stick anything that didn't match into this uh and we're looking for the ones where the hash set indicates that the pointer isn't guarded okay that's fine so this is just basically a partition over the list so this is uh walk the list which is uh probably what we did inside bulk lookup and reclaim right which is this walk the list business and we can actually so this is a little interesting because do reclamation where does the actual reclamation gets done i think it gets done here yeah reclaim unprotected claim unprotected why does reclaim go for the ones that are not a match oh right because match is that they are protected okay i think this actually translates pretty well to what we had before so uh if i now go here and take this code um and just i'm just going to inline it up here for now we can tidy that up a little bit later yeah match doing a reclaim is weird um but what we'll do here is we're really just walking the nodes and and what we're doing is or what this is doing rather is constructing taking the existing link list that we stole right so as we own that whole link list and splitting it into one linked list for the ones that are now reclaimable and one link list for the ones that are no longer or the ones that are not yet reclaimable so the ones that sort of need to be put back which is sort of the same as what we used to do as well right we we know it is the stolen retired head which is a great name for a variable um although here what we're doing is we're actually deallocating sort of on the fly right like they collect them first and then call reclaim unprotected which maybe is nicer it does mean that this doesn't have to this doesn't get indented quite as deep um so maybe we should do that and say um like reclaimable and unreclaimable and then for each one we say um so this is no longer guarded uh guarded um safe to reclaim and so for this one what we'll do is stick it onto uh not remaining but onto to reclaimable and why do they keep the count as they go I wonder I guess they return the number of things that were reclaimed that's fine so we can do reclaimed plus equals one um and then this business the the bit that actually reclaims the nodes this we can then do later on so this is a little bit nice in that we can sort of separate finding them and actually reclaiming them so then here we're going to store remaining we also store the unreclaimed tail unreclaimed and I think I'm going to do just to keep them a little bit consistent uh unreclaimable unreclaimable that's it's a terrible variable name I apologize um sword nodes into those that can be reclaimed and those that are still guarded guarded um right so that's now that loop which is basically this loop and then it calls reclaim unprotected here reclaim unprotected on uh reclaimable and that's going to probably be self dot reclaim unprotected um and then it says done it sets done to so done actually is set up here right so at the at the top of the loop it says uh let done is true and then down here it says done is set equal to untagged dot is empty but this see this is where you get into real funkiness right where I hate implicit this because that's what's happening here untagged underscore is the variable in the class here in the C++ stuff it's not this untagged it is uh it is this untagged and calling the empty method on it which is just awful so done here is actually set to um self dot uh retire which is untagged dot like is empty uh which I guess that is a helper method we can add that seems pretty reasonable which is pubfn is empty or fn is fine turns a bool and it is uh self dot head and I guess we can go over to this one empty head returns head which is a relaxed load uh head dot load ordering relaxed is null so done is true is set to true but if it's it defaults to true when would it ever be set to fall oh I see if it's not empty then done will be set to false that's really what's happening uh counter moves children dot count we're not dealing with children uh match let's splice children that sound that reads real awkward uh match are all the ones that weren't retired so it pushes those back right so this is the um unreclaimable ones need to be stuck back onto untagged right which I think we already had code for doing uh down somewhere just gonna go ahead and delete some of this bulk look up and reclaim yeah is down here right so here is where they push back onto we push it back onto the head so this is where it gets a little awkward which is um self dot untagged dot push and we really here want to be able to pass it um unreclaimed so like if unreclaimed actually we can just do this right so this is actually where fn push this really does need to take a I guess mute of retired and did we care about this returning the n I don't think it we do which means that it doesn't need to count uh so I think actually this has to be sub it has to take the sublist tail which is like it's unfortunate right because here yeah it's sort of the same thing they're doing right which is if you want to push onto a linked list you need the head and tail of the sublist you're inserting because the tail needs to point to the old head but the head needs to point to the new the old head needs to point to the new head um and so that's really what we're saying here is that it's sort of a in order to push this you need both ends of the list um which means that this now no longer needs to do that or this um it is going to be unsafe though because we're going to be trying to dereference this which is up to the caller to sort of assure us is is safe um so this is going to be sub tail no sub list tail dot next dot store so arguably I really feel like this count is starting to feel like it needs to move out of retired list um so I think we're going to move that up to here and then anywhere that says self.retired self.retired.count is going to have to change to not be that and instead just read directly from count I think that's just more it's a more accurate representation of what's really going on which means that this count needs to not happen here and then in the place where we call push list um it needs to change the count which is I think the same same thing this is like we're going gone full circle right the c++ code is also doing the count outside of the the actual push um and this is now going to be a little weird because retired is going to be box into raw retired and then we're going to pass retired retired unsafely uh yep and so it's certainly true now that this has to be these have to both both be const I think yeah and now here this now becomes unreclaimed and unreclaimable and unreclaimable tail and I think we can do this and have it be right because we're we're pushing onto the head which means the first thing we push is the tail so that's why this is if it's null then set it otherwise don't set it um so this means we now unreclaimed and unreclaimed tail we could tighten this up a little bit the same way the c++ code had done of having like a new type wrapper around a linked list that that holds the head in the tail um so this is going to be pushing those um and then I'm guessing we're also going to have to update I'm a little surprised that this doesn't have to update the count un yes see reclaimed I don't understand why my rust analyzer is being ooh maybe this is throwing it off almost certainly that's because okay let's get rid of the things that are no longer real things uh like all the all the things that we saw them delete in the uh in the commit before and where is my bad closing brace I think it's up here somewhere it's not there it's here I still have doing I'm doing something bad somewhere this one that's fine um so it calls reclaim unprotected on those decrements again by children which we don't care about it pushes back on um those which we're doing here yeah there is ah this is on should be on retired list unreclaim I really want this to be unreclaimable to be unreclaimed because that's what I keep typing everywhere um and then this is going to be reclaim unprotected and then it returns count so up in the parent which is what we're still inside of here um our count our count minus equals uh the count that remains so this returns count which is the one the number of things that were reclaimed all right so this is minus equal the number of things that were reclaimed reclaimed unreclaimed but actually unreclaimable uh that's actually let's just make this a an i size as well that's fine okay so to explain my reasoning for the names um reclaimable is a linked list of retired objects that can be reclaimed but they haven't been reclaimed yet unreclaimed are retired retired objects that were not reclaimed and cannot be so they are unreclaimed um unreclaimed tail is the tail of the linked list of unreclaimed things unreclaimable is the number of things unreclaimable and ununreclaimed is the number of things unreclaimed so the names are very intentional uh and hopefully it's sensical but they're complicated words uh which is unfortunate uh okay so let's leave reclaim unprotected for a little bit because I want to finish the structure of this one um which is we're still inside of so at the end of this if it's if our count not equal to zero then add count our count I see so this is where it ends up getting added back uh and then our count equals self dot check count threshold so this is like it's a loop where when do you ever break if our if our count equals zero and done then you get to break all right okay so that I think the idea here is you only enter due reclamation if there's an indication that you should be reclaiming there could be multiple threads that enter due reclamation that it's not exclusive lock it's just you should only enter there if it's somewhat reasonable that you will have to reclaim things once you enter you're gonna loop until it doesn't look like there's anything more to reclaim so that means um that means there's nothing that can be reclaimed and there's no indication that you should try again like you should retry so that's why we recheck this count threshold and we only exit if there's no indication that we should reclaim again and there is nothing that can be reclaimed uh great and then down here it does a decrement of and bulk reclaims so a little weird to me that the increment happens outside the function but the decrement happens inside the function but very well that it it is what it is an add count is doing release which is interesting okay so now we're gonna need this uh reclaim unprotected which in this case takes just the head and the children it takes the children uh and it takes just the head which is a star mute retired yeah yeah yeah retired i get it um and it says while retired so that's while retired is not null um next is retired dot next and i i believe that next here is um i'm gonna have to open that up in another file because there are too many files so that's going to be has pointer object which is a next method which is a relaxed load and then it calls reclaim so the actual reclamation i deleted that code didn't i come back to me code that is this code right here so this is going to be unsafe the reference of that and this is definitely unsafe uh safety um all retired nodes in retired retired uh are unaliased throughout yeah are unaliased and owned you take an ownership of yeah i didn't want to go through get check out dash p because you have to it it's more annoying to skip uh and also i have the file open so here uh this is really a safety comment for the call to reclaim unprotected so safety um every item in reclaimable or rather no item in reclaimable has a hazard pointer guarding it so we have the only remaining pointer to each item so therefore you can call this unsafe um are valid unaliased and can be taken ownership of so safety here is really like one this is sort of the important one but two every retired was originally constructed from a box and is thus valid and i i guess there's also like three um none of these retired have been uh dropped previously and dropped previously uh because we um um atomically stole the entire sublist from um self dot untied and what else do they do yeah they just call reclaim um yep great i do like this restructuring i think it i think it makes the code nicer to read um and i think i think that's the whole loop right check threshold and reclaim they made this change but this we've already picked up on um so look up and reclaim goes away so if i run cargo check what do we have left a decent amount okay so four three four um this should be sublist head okay fine it doesn't return anything anymore reached threshold so i think this is going to become due time i think this is going to become untagged um i think count is going to go away from there and just become a basic item i think sync time is going to go away probably um this is now just count this is now just count this is now just count due reclamation this should be untagged oh thank you type annotation needed why i don't want to give it a type annotation it should be needed so i think check i think this method is no longer called so that can go away i think this method it is no longer called so that can go away i think this method is no longer called so it can go away i think this is no longer called so it can go away eager reclaim uh so this is the method we had mostly just sort of for helpers which is if you want to do a reclamation now you don't want to put it off until the next time is due or something. And that one's pretty easy for us now, because that one can just be this now, I think. The question is, what is reclamations here? I think actually what this will be is this. Let R count is self dot count dot swap with 0. Self do reclamations. And now the question is, can we find a way for this to tell us how many items were actually reclaimed? And I think we can. I think the way we'll do this is total reclaimed is zero. This is going to return like a view size or something, right? And here, we're going to do total reclaimed plus equals n reclameable. And then here, this is going to return total reclaimed as view size. Actually, we're just going to have here as view size. So now eager reclaim is just going to whatever the count is, it's going to just try to take all of them. Then it's going to start to bulk reclaim starting from that number. And then it's going to call due reclamations. So look up and reclaim went away. What else do we have now? What's it going to complain about? That's not too bad. 232 is still one's type annotations here. That's fine. We can deal with that in a second. 331. So on drop, this is the destructor for domain. And those we got rid of, that's fine. Those we got rid of, that's fine. Sink time went away. That's fine. Push retired is now just push list. That's fine. Highest pointer object. That's also fine, I think drop though, we do need to deal with. So that calls reclaim all objects. Seems great. Let's let's structure this the same way they structure their destructor, which is there's a shutdown field now, apparently. Shutdown, which is an atomic bool. Do I already have atomic bool in here? I do nice. So shutdown is going to be atomic bool new false. And then what we're going to do is in drop, we're going to self shutdown store true relaxed. And then we're going to call self dot reclaim all objects. And I think this is what eager reclaim is going to end up being as well. And self dot free has pointer rex. And I think this is going to mostly end up being what we already have. And then this debug will deal with in a second. So we're going to have a fn reclaim all objects and reclaim all objects who that's interesting. Because this almost certainly assumes that you have exclusive access to self. So we're going to steal the head of untagged. And I guess here, like pop all is really what this is called, right? So where's our stolen head? So we could just have this be a another helper here, which is pop all. And I guess really this could be like an option box, right? But I don't think we want that because that would make it unsafe. So it's just going to be this.  Pop all. And this can be the same now. And then it calls reclaim list transitive of head, which who knows what that does. Reclaim list transitive. I'm just making these mute self for now. They might not need to be. But for now, we'll keep them that way. And this is really the same as that loop we had above like this business grabs the children. It grabs the children reclaim unconditional. Oh, I see because this is going to recurse into the children that's a neat loop actually. Like reclaim unconditional head, I'm going to assume walks all the things from head to tail, pushing any children it finds into children. And then the head gets set to head of children, which means that you're going to do like scans by depth. That's a really neat loop. I like that loop. In our case, we're actually just going to do self reclaim unconditional head. I think that's going to be like to do handle children. And then reclaim unconditional is going to be here. And again, mute self, mute head. And that one is just going to. Yeah, exactly. So reclaim unconditional is the one that is basically the same as reclaim unprotected. In fact, how do they differ? Aren't these the same? I think these are the same. Reclaim unconditional and reclaim unprotected are the same. So self reclaim unprotected head. So unsafe self. So unsafe unsafe. What's the difference here? Also, why is this okay? Because reclaim notice that reclaim unprotected. Oh, I see what's going on here. So this is tricky. Yeah. I think here's what's going on. The observation is the same as what we used to have in drop, which is there should be no hazard pointers active anymore. So all retired objects can be reclaimed. Because that's true, you don't actually need to check the like active guards and stuff. But in the Facebook implementation, they just sort of assume that that's true, right? So notice that this just calls it takes the entire retired list and it doesn't check guarded pointers at all. Because there should be no hazard pointers left. So the question is, what in what actually makes it so that that is the case? I think in C++ land, it's just the programmer knows not to keep a hazard that you a hazard pointer doesn't matter once the domain is dropped. In rust land, the question is, can we do better? And I think the answer to that is yes, because the holders are tied to the lifetime of the domain. So the moment the domain is dropped, there can't be hazard pointers to it. But for global, this gets weird. Because they're static. So the question is, how do you guarantee that the domain is dropped first? Sorry, that the domain is dropped last. You guarantee that because they're dropped in reverse order. So you create the domain first and then you create handles to it. So the handles will end up getting dropped first, the domain will get dropped last. So it is indeed the case here that once you have exclusive reference to the domain, there cannot be any hazard pointers, because the hazard pointers have shared references to the domain, which would preclude the existence of an exclusive reference. So I think therefore, so that's why Reclaim Unconditional is sort of the appropriate name, right? Because you call this, to sort of say, you call this only in the event where you don't care about the protection status. So maybe we should document why that's the case. So here certainly, safety is at mute self implies that there are no hazard pointers active, no active hazard pointers. So all objects are safe to reclaim. So claim. This is just this word, man. And this can remain unsafe. This one, I want to say equivalent to Reclaim Unprotected, but differs in name to clarify that it will remove indiscriminately. So I think the reason why this alias is here is because it would look weird for Reclaim, let's ignore Reclaim ListTransitive here and sort of inline it in our heads into ReclaimAllObjects. If ReclaimAllObjects called ReclaimUnprotected, that sort of gives the wrong implication here, right? Which is that, oh, we're only reclaiming the ones that aren't protected. But in fact, we're reclaiming unconditionally, and that just so happens to be the implementation of Unprotected. Now, arguably, this means that Unprotected is the wrong name for that function because that one is really just reclaim these, and it's up to the caller to indicate to check whether they're protected or not. So I think this is really a naming error in the name of ReclaimUnprotected, but I want to keep that name again so that refactoring is later with respect to the upstream code base are easier.  I have a feeling it's not even necessary, but you know. And then the other thing they call is Free Hazard Pointer Rex. So FN Free Hazard Pointer Rex itself. Oh yeah, all right. Where's my other typo? Indiscriminately. Yeah, so I think this is the same, this one we can ignore. And this code is probably already right. Because it's really just walking the list of Hazard Pointers. But they have this special like if self is global, if self is shared domain, am I missing something here? I feel like I'm probably not allowed to reference. Maybe it's never dropped. This is weird, right? Because we have a mutable reference to the domain because it's being dropped. But what if that mutable domain is in a static? Then we can still refer to the static in the drop, which would be unsafe. So how is this legal? This suggests to me that it just would never be dropped or this would just be on sound. But there's no unsafe here. If this was unsafe, then like imagine that I wrote the following program. Static foo is equal to what's a const, I mean, simple const defend new returns to self just returns x. This is an x foo of type x. And I import drop for x, drop new self, right? Like there's no unsafe code here. Yeah, fine. This is irrelevant to the explanation, but fine. This compiles and there's no unsafe code there. But the existence of this exclusive reference implies that this shared reference shouldn't exist. There's no unsafe. This seems like a cargo new test drops source main. There we go it. The I guess new doesn't really matter. So statics are never dropped is the reason why that's not unsound, which means that we don't actually need to deal with the the global domain being dropped because it never gets dropped. And that's why there's no one safety there. Okay, well, in that case, the drop here is kind of stupid, right? Like this can just never happen. So I don't know how to I think statics are just never dropped. That's certainly what this implies. Right, like the the drop for x here is never printed. So the question here is sort of skip for global domain, but global domain is never dropped as it's a static. Like I don't I don't think we need this check. I guess we could assert it, right? Like, we could assert that there's like no way to assert it because if it if we could assert it, then that implies the global could be dropped, which is false. And if you're relying on assuming false, then anything can be true. So it's like not I don't think it's useful to even think about this. Folly skips this for the global domain. But the global domain is never dropped as it's a static. Yeah. Oh, yeah, someone linked to the documentation. And saying, actually, let me copy that real quick. And go over here. Static items do not call drop at the end of the program. skips this step for the global domain, but the global domain is never dropped in the first place as it is static. See this link. We have new self. So no one holds any of our hazard pointers anymore as all holders are tied to domain which must have expired to create at me. And so here, I mean, we could look at what their implementation does. But yeah, it just walks it asserts that they're not active. This is a debug check for them. So it's a debug assert. That's fine. And then they drop the end. That's fine. That seems totally reasonable. And like it's about the same. And then the other thing they do is they check not tagged empty. That's fine. We don't support tags. So that's easy enough. What else we got here? Actually, I think we're trying to get this to compile. Now it's only the type annotation that's needed here. Why does it need the type annotation? I guess I can just say unreclaimed. And then it realizes that they're the same. The number unreclaimed is not relevant. That's fine. This should definitely not require new self. 132. Why is this unsafe? I don't think this needs to be unsafe. Although I do think that maybe, no, that's fine. What else we got? 339. That's fine. This is unsafe because that's unsafe. That's fine. Does this even need to be pubcrate? I don't think it does. 289. Unused variable. Oh, that's... Thank you, Rust. That would have come back to bite us. Is cargo test work? No, it's segfaults. Great. All right, what else we got here? Any other changes that we're missing? No, I don't think so. All right, but something somewhere is causing us to poo poo and be sad. So the question is what? I want just... I want only to run FeelsGood. That's great. All right, let's see what we got here. We're going to go ahead and GDB this. GDB. Run with... I don't even care about no capture, I think, but I do care about FeelsGood. Oh, I forget what the GDB add to path. Source path. There is a search path somewhere. Oh, the question about unreclaimed, it's still set to null, right? It's just that by doing this, I'm indicating to the compiler that they're the same type. So whatever the compiler and first this type to be, this should be the same type, but it's still initialized to null. What is the... Oh my god, yes, that's fine. Yeah, that's fine. Where is the... No, no. I had this in my history at some point, and now I've forgotten what the... All right, let's see if Google does better at searching. There we go. This thing is what I want, except it has to be not this, but this, which is like the particular commit of the release. And this is going to be this, which is home, john, that if I now do backtrace, I'll get backtraces into the standard library as well. Nice. All right, give me that backtrace again. We're failing in retired. When we're pushing to the retired list. Oh, yeah. Okay, I know what this is. Here, if sublist head is null, turn, pushing an empty list is easy. Hey, fantastic. All right, so this is then full restructuring associated with that command. Follow upstream in switching all to untagged. This again. And I think now we're most... I think that was like the biggest one of them, right? So if we go back here, one thing I do want to do is this. And say this is the relevant commit. Sweet. All right, so we have this commit. Well, let's move on to the next one. This one is minor, I think, which is it shards the untagged list, which I think we can do pretty easily. So it keeps num shards, which I think is just a constant. So as a num shards of type, probably use size is this value, which is eight. And then untagged is now actually multiple untagged. I'm using the wrong syntax because that's what I like to do. Great. And then we're going to need calc shard somewhere down here. Probably down here. I feel like realistically, we should probably reorder these functions as well. Calc shard of self. And I might not even need self actually, it just takes a tag. Oh, it uses the head pointer as the tag. I see. So the input here is like a star mute to nothing. Or if you will, the input as a use size. And it returns a use size. So really, this is just okay. So it's a standard hash, you say. What exactly is a standard hash according to C++? Implementation dependent. That's good. Well, we can always use just this the hash map harsher. Honestly, sip harsher is probably the reason I don't want to use default harsher is because it's cryptographically secure, which makes it slower. And also you need to basically it's seeded with a random number every time you create a new one. Although I guess that means the hashing function would be different for each domain, which maybe is nice. So let's do this. Let's really this should be a hash. No, what am I doing? So I think what we're going to do here is go to cargo Tom all dependencies. It's a little bit sad to have to include a hash as a dependency here. It's nice for it to take no dependencies. I kind of don't want to do it. FNB is no better, right? In the sense of it's still it's still a dependency. I'd rather not take a dependency is sort of what I mean. All right, fine. We'll do it. And we can always factor it out later. I don't want to. The reason why it's tempting is because this hashing is like, every time you retire an object, you're going to have to compute this hash. I thought there was a speed comparison where like it doesn't really matter if the keys are small. Where is the standard library hash? I think the standard library hash is Oh, here. This is great. Like it's a fair bit faster. Okay. So the thing is we could the point is I whether we use a hash or FNB isn't that important. It's whether we take a dependency or not that I care about. Like I like a hash as a crate. We could take a user supplied hasher. It sort of feels it's sort of an implementation detail of the library that we're doing hashing in the first place, right? Like it would be a generic parameter that I don't think any user will ever set or to phrase it slightly differently. I would like this change that we're about to make to not be a breaking change. Right. You need a hasher for the global domain as well. I don't think that's a problem. Oh, it's constructor needs to be const, which I'm assuming a hash new is not not a hash map a hasher. Yeah, it's default is not const. I mean, it does have const with seeds. So we could create a random state and then just set the seeds because we don't actually care about sort of cryptographic randomness here. Right. Like what we're hashing is pointer values. I guess eventually we're hashing tags. It's definitely tempting to just construct a hasher with like static key material here because all that matters is that the values end up neatly distributed, which shouldn't depend on the seed of the hash is I think a hash has fallbacks. No. Yeah, it uses as on x86, but it doesn't require x86. All right. So in that case, I think what I want is this. And I think what I want here, well, at that point, actually, we don't even need to store the hasher. We can just construct one in here because it's const. So this can be a const fn. And then this can be a hash random state from seeds. And let's make this 123 and four because those are those are random numbers.  That'll be fine. And then it's that. And then we're going to. So this is the hasher. And then we're going to hasher dot hash input or its input dot hash mute hasher. And then hasher dot finish. And then it ignored low bits. It's fine. So we're going to have a const ignored low bits usize or you ate for that matter. It doesn't really matter. Ignored low bits with a case shard mask on shard mask is num shards minus one. Also use size. This is going to be this ended with shard mask. Is it not from seed? Did I misread that with seeds? A hash random state implements hasher. It's a build hasher. It implements build hasher but not hasher. So I'm going to have to construct one of these. But that one does it really feels like there isn't a const way to do this. Which makes me real sad. The part of the problem we're running into is that for the global domain, we need a hasher for the global domain. The global domain is static, which means that we need a const hasher. We could make one with lacy static, right? Like there is a way around that. The other way to do this is just this, which is maybe nicer, right? I think that's fine, honestly. I'm going to go with that for now. It just means that we're going to, it means we don't take into account really the full information from the higher bits. The low bits we do have to ignore because the, otherwise the shard mask is going to take out the lower numbers and the lower numbers are generally going to just be the same because they're, they depend on the alignment of the allocated objects. So this is going to take sort of the high bits and then it's going to take just out the shard mask of the high bits. And it's not going to take very many bits from there because we're not sharding that many ways. Honestly, I think this is fine. I think this is fine for now. I think we're going to stick with this. And then because we don't support tags yet anyway, I think what we'll do is say that we're only going to support the, the star mute tire. And then we're going to do this as U size. I think that's what I want to do. That's what I want to do. It's definitely a little like awkward, but it's fine. And then this is going to be up in a push list. So push list is going to do here self calc shard of retired. And like in theory here, we can use like get unchecked or something because we know that this already takes a modulo of the number of shards. But I think the optimizer might be able to realize that that is the case here. And then extract retired objects. Right. So that one now has to change. So this is the bit where we here do the pop all, where remember how there was this like match or extract retired where which splits it into the ones that can be retired and the ones that can't. And the ones that can be retired is just everything and untagged. Well, that's now not quite as simple because we need to steal from all of them, not just from one. So I think what we'll do is this is going to be no mute num shards. And then a four I in num shards, we're going to set stolen head of I is self untagged I pop all. And then we're going to set let me empty is false. Or empty is true. If stolen head I, if not that, then empty is false. No, empty is yes, then empty is false. If not empty, then we do that. What else do they change here? Right, this now just walks. It has to walk the shards for the inner loop. It's interesting because you could probably do better here by having by sticking them all into one list and then walking that one list. This is sort of a naive reinterpretation here, right? Like you could imagine that you instead just merge the match and no match lists. First in the for loop. And then you call reclaim unprotected on the merge no match, which I think would be an optimization here. But let's I guess not do that. That's fine. So this is then just do we want to split this out into a function maybe let's do that. So they call this match reclaim untagged.   What am I doing? That doesn't work. And is that how I want to do it? Yeah, it's like real. So it is true. The fact that we're not hashing in quite nicely means that some shards make it larger than others. It's still better than everything being in one chart, which is how it was previously. And I'm guessing that just using pointer values, you're probably going to get pretty far. You're going to get a decently even distribution unless all of your objects are very large. So the alignment ends up going over.  So I think what's going to happen here is I guess this whole thing goes in there. This does for I in zero to num shards does this right? This is basically the same refactor they did here. They return a bool for whether they're done, which they set to true. Yes, that's fine. Done, I guess. And they take in the guarded pointers, which is the hash set of retired. So it takes stolen heads and guarded pointers. Is that not what I know? This should be stolen heads. And this should be guarded pointers. I guess, realistically, it could just be passing ownership of the set, but it doesn't really matter. Storm, you ate. That's fine. And what else? Actually, I guess most of this is going to end up inside of there, right? So they pushing back onto untagged and reclaiming unprotected, both happen inside of there. And so does setting done. So these all happen inside of here, except they do all as one untagged, which makes a lot of sense. So they're setting these outside of the loop. And see, this is the optimization I'm talking about, but let's not do that one quite yet. So stolen heads, I'll explain in a second. Pointers. So that sticks onto there. And then they reclaim unprotected inside of the loop. And they set done. Right, so this has to change to if untagged empty. This ends up being a nested loop, which I don't think they need. I think this goes outside the loop. And I think they do if if self dot untagged dot error dot any, then done as false, which I think just means that done is this. So this is we have to check. Okay, so this is where we're not done. If there are untagged items, after we've reclaimed everything we can, and before we've pushed back the ones we couldn't reclaim. And it's important they happen in this order, because otherwise, the fact that we push the ones that can't be reclaimed yet would mean that this might be set to false, even though you can't actually do any work. So this order is important. They push, they push all the items that can't be reclaimed onto shard zero, because let's not re shard them or anything. That's fine, I guess. That's wild. We're not re shard. We're not respecting sharding here, presumably, to avoid multiple push casses, which would decrease performance. That's wild. What I was going to suggest was that we do reclaimable up here too, and we call reclaim unprotected on all of them at the end too, because why not? I'm going to leave that as an this can probably also be hoisted out of the loop, and we can do do a single reclaim unprotected call as well. Facebook code doesn't do that, right? They call reclaim unprotected inside of the loop. I don't know why. This also just seems wrong to me, because why do you have to check as you go rather than once at the end? I think that's wrong, or I don't think it's wrong. I think it's less efficient than it could be. This one I'm less sure about, because there might be some subtlety I'm not picking up on, but I doubt it. Okay, and do reclamation also needs to change. So this needs to be this four num shards shards. It's fine. And this right match reclaim untagged also returns the count. So it returns use size and whether it's done. And the use size is number of reclaimable or unreclaimed, if you will. And then this will be here, reclaimed, and reclaimed, and reclaimed final be an ice ice. Can it be use size instead? Nice. And then this is going to be now count. So what it gets assigned to up here, where we call match, where's the place we call match? I think it ends up being our count. So this is n reclaimed and done. And then our count is minus equals and reclaimed total reclaimed is plus equals that. And this has to be is done and then done equals is done. Because otherwise we'd be declaring a declaring a new variable whose name is done the shadows the previous one. And we wouldn't be overriding the done from up here. There's a like a cool thing that's landing soon, I think where you can do this. But for now, we're going to have to do that. Okay, where else is complaining? Do reclamation? I don't think we need to change anything. All right, that's the same thing we already changed. That's fine. This just needs to loop over all the shards. So that's fine. 394 pointers cannot be cast to integers during const eval. That's fine. It doesn't need to be constant anymore. Retired list copy is not satisfied. That's fine, because there's a new cool thing where if you have a constant constructor, then you can do it. Forget exactly how this works. Let's see. Like I think if I do this, and then do retired list new, I think it lets me do it. I thought that was what it did. I thought this landed in like 154 or something where maybe it's just you can't use this syntax. I'm pretty sure that you are allowed to do this now. I just can't remember the syntax, which is pretty annoying. Hmm. I don't really want to make retired list copy because it shouldn't be. Time to go to the Rust blog and look back at 153, 152. Sorry that these are bright. No. 151. It was like an accidental stabilization previously. Const value repetition for a race. I knew it was there somewhere. Petition has only been allowed for extra copy, sought to allow any const expression there. However, while the feature was enabled for constant values, so the way you have to do it is const retired list is retired list new and then here retired list. Yeah. And this is going to be retired list. And then it works, but you have to, it's wild, but that works. You shouldn't need try into here. I don't want try into because I don't want to have to write on wrap because I know that this is the right size, but you can do it this way by telling the compiler that this retired list is a constant value. It's evaluatable at compile time and then using the constant value here and then the compiler is happy. One day we'll be able to move that into there, but what I'll do is put a link to this. I mean, I'll put it in chat, but I'll also put it here. Great. What else is it complaining about? Well, something's about to crash, but that's fine. 261 done is unused. That sounds like a problem. That's because now it's computed at the end. So that part's fine. But it spins forever. I mean, it could be that my optimization was premature. Like, alright, let's stick it where they want it. They want it right after the call to reclaim unprotected. So here it's if any is not empty, then done equals false. What? I do not believe that that's necessary. I cannot done is all is empty. There's a negation missing. Okay, good. Great. Great. Okay. So this is shard the retired, untagged retired. Man. And there we're going to link to this one, because that's the commit we just did. That one's done. We only have two more commits. And then maybe we'll actually be able to test this thing, which would be nice. Rearrange invoking asynchronous reclamation and executor. That's fine. We don't support executors. Hey, that was one cheap commit. We got here. Optimize the management of available hazard pointers in the domain that are not in thread caches by adding a linked list of available hazard pointers with a lock bit packed with the pointer to the head of the list. What is the actual modification here? Trying to lock down the list. Why is this better? I'm still trying to figure out what it does. Oh, I see. I think what it's doing is currently we keep a list of all the hazard pointers, but there's just one list that is all of them. So the problem, if you want an available one, like one that's not being used, let's see if I can find where this code is. Where is the old acquire? Not acquire new. Yeah, so this method try acquire existing HP rec. So it used to be if we were just looking at the red lines, it used to be that it got the head. It kept walking the next until it find one that it was able to acquire by virtue of its acquired bit being set to false, and then it returned that rec. Although I thought try acquire removed it from the list, but is that wrong? Existing. Try acquire existing. Try acquire. Yeah, so try acquire just sets active to true with a compare and swap. So what this is doing is it's keeping a it's specifically keeping a separate list of active ones. So there's the hazard pointers list, but there's also the like available hazard pointers list, which I think is just pointers into this list. So it almost becomes like a skip list. But where you can skip to the next one that's available, right? So it's not it like, let's use move. Let's you seek directly to one that is active. Yeah, so it starts out being null. And to acquire one pry pop available HP Rex, right? So let's assume this is one. Oh, it probably allocates them in batches too. Yes, you create one. And then, yeah, and then you stick them all onto the available list, which basically becomes a linked list of it becomes you're basically keeping two linked list over the same set of objects. Yeah. And now this freeing, why does it not? I wonder why they removed the debug check here. It seems odd. Yeah, so trying to pop an available one is you load the head of the available list. If the head of the available list is null, then you go, I failed, I couldn't pop one that was available. Otherwise, you try to lock the available list.  If you succeeded locking the list, then you remove the first however many you need. Let's say you only need one, right? Then you would just remove the head of the list. You would set the head to be the head of the tail. And then you release the lock. Yeah, so that's this bit. So you take, yeah, so you need to, if you're moving past n items, then you just walk, you need to find the head after n items. That's what this loop does. And then it stores that as the new head of available. It sets the next of the tail to be null so that you don't unlink the chain that you're removing. And then you return the, you return the number of items you successfully stole. Right? So it might be, you might tell it, I want, I want eight hazard pointers and there are only five in the available list. So it goes here or five. So you might still need to push more. And this is just the push for another linked list, which has to take the lock into account. That makes sense. In fact, pushing, right for pushing, you just do a comparison swap on the head and they store the lock bit in the pointer itself to the head. So the cast would fail if someone took the lock. And the cast would also fail if someone took the head, like took the lock, took the head, release the lock in either case the cast would fail. Decheck connected. And this seems to just be a debug check that I think this debug check is just to see that the, oh, it just checks that the head is connected to the tail through the next available pointers. That's fine. We don't really care about that. And then the hazard pointer holder, this seems like an entirely unnecessary change. This calls acquire HPRX1, that makes sense. Why did they even make this so that it could acquire multiple, they did that for array. So this is imagine that you're writing a data structure where you know that you have to guard multiple pointers in order to make progress. So really you need to allocate multiple hazard pointers. Well, if you want to allocate multiple hazard pointers, allocating them one by one is a little sad, because each one has to be added to this like linked list and now to multiple linked list. So if you can just grab multiple at once, then yeah, you've amortized the cost of those pushes and potentially pops and allocations. And that's what the hazard pointer array bit is doing, which we never implemented. But that's what it's for. I think it's probably fine for us to implement the available stuff for supporting multiple allocations. And then we just only use the single one for now. So that if someone does want to like submit a PR that adds support for a race later, that would be pretty easy. And they've augmented the hazard pointer records so that they now both have a next pointer, which is sort of the next pointer in the main linked list of hazard pointers. And that will never change, because that's just a list that you only ever keep appending to the head of. And the only time it changes is when you deallocate all of them at the end of the domain. But next available is sort of this skip list that we're drawing over the linked list itself. That's cool. I like that. And now, oh, and now active, they removed the active flag. Because you no longer need it. You no longer need it because all of the ones that aren't active are in the available list. That's cool. Thread locals, we don't support so we don't really care about those. They change the test a little, but that's fine. All right, this looks like a fairly straightforward and fun optimization to implement. And it certainly seems like it matters a lot. Okay, yeah, let's do it. I'm going to take a quick break to get more tea and a little bit of a bio break. But let's say we continue in like five ish minutes, maybe a little less. So I'll be back in a second to talk amongst yourselves. I'll link this commit so you can all look at it in case you want to. So all right, see you on the other side. All right, I'm back. Today I want to do mainly test but let's port these commits first. Yeah, you're right. Although, like, I think this was still worthwhile. Because I noted that there's a Folly has a test suite. It's not very large, but specifically for hazard pointers. And I have it open in a tab here somewhere. It's over here. I have the file. And this test suite, I'd like us to port. I would also like us to write tests with loom. And but that's neither here nor there. But for this test file, this one is written with the latest code in mind. And I would worry not just about bugs that we haven't caught. But also that the tests might be relying on behavior that was only implemented since last time, which would make me a little sad. And also it just seems like the right thing to do. And also it lets me page everything back in. But you are right. We didn't, we haven't done tests yet. I'm still hoping that we'll be able to do tests. I have faith. But you are right that I kind of lied. I mean, we could just not do this thing, right?  We should just, we should kind of just do it. It was, it was committed four days ago. So really, if I'd streamed like a week ago, we wouldn't have this commit to catch up on. All right. But the improvement seems pretty, pretty significant. But yeah, you're right. It is quite the rabbit hole. All right. All right. So we're going to go with const lock bit use size. It's going to be one solid lock bit right there. And now we're going to have has pointers. I'm going to model this a little bit different than they do, which is I'm going to have head. And I'm going to have available head. And this is going to be available next. Yeah, I think that's the way I want to structure it. You're right. We might end up just rebasing every time when you do stream like, we have to catch up first. We never get to actually write the tests. You're right. Although in my own defense or since last time, I've been working on finishing the book, which is now finished. So in theory, there should be less time until the next stream. At least that's that's my hope. Right. So that's fine. Head available. That's fine. So the first thing we're going to have to do is the constructor constructor, which is going to have to be head available. It's easy enough. System allocator. Yeah, I mean, one day will be generic over allocators to but that's we're not going to deal with that right now. This is just helpers for load and store require HP wrecks. Right. So we're going to this is the one that used to be HP REC acquire, which is this one. So that one has now been replaced. It's instead going to be a choir end. What do you think of that? Is that bad? Is that good? It's kind of cool. Right. It gets it's going to get specialized. It gets specialized to the one case and no bounce checks. Yeah, I like that. And I guess there's going to be a debug assert that n is greater than zero because, you know, so we're going to end up with let n and head is going to be try acquire available. This doesn't need to be called a choir end. It can just be a choir try acquire available. So this one's going to be a little weirder do this. I think what I want to do here is why does that have to be head? Do I care about that being head? Well, what I'm thinking here is what is the return type of try acquire available? And I think it's going to be I think it's going to end up being something like of this, right? Really, it can return any m that's smaller than n. So it could return like a slice of them, right? It could return this, which is maybe nicer in the C++ one. It actually returns a linked list. And I don't think it needs to. But they keep the they keep them as a linked list so that they can all just be like stuck back on to the available list easy later. But that's fine. So in the thing that consumes this acquire, like let's look at array, which I guess is down here somewhere that acquires m. It uses the available pointers and then sets them to null, which I don't think it needs to. I think we can relink them when we push them back in which case. So we, I think I want this, it would be nice if I could express that this one is like at most n long. But I think that's fine. I think what we're going to do here is Yeah, I think we can make this work. So here, we're going to do assert that available dot Len is less than or equal to n. And then we're going to do for is going to be the problem here is constructing this thing actually because it is, I can use standard mem, maybe on in it new pass point or record of N. Oh, maybe on in it mem uninitialized is fine. So what I'm going to do here is for wreck in available dot into iter dot, I can't return that, can it? I think it has to be option, which is so dumb. I just really don't want this return a vector is the thing like it shouldn't need to. All right, fine, fine. It'll return the head of one. I hate that. So we'll return a pointer to the first one of a linked list. That's fine. That's fine. So head and then n. And then we're going to do for I in zero to n out of n is maybe a minute new of so the reason we need to maybe on in it here is we need something to start the arrays. And then here, I guess we're gonna set, we're going to walk the linked list to throw them all in. This is where like, you could sort of do this, right to construct the linked list. But I think instead what I want here is, can you collect into an array, like is basically is from iterator implemented for array. Think so sadly. And there isn't a try collect. So then that sort of means we were basically we were basically implementing try collect for or try from iterator or something for arrays here, but sort of manually. So we're going to do let next is in fact, I think this is going to be a star mute to that. We're going to say next is unsafe. Next. And this is going to be on that head is unsafe. So the safety here is pass pointer records are never deallocated. So I guess this is going to be rec. And then this is going to be head. So this has to be mutable. So head is rec dot next download. Relax this fine here. This is going to be rec. And then this is going to be for I in N to N. Right. So this is the the second loop there, which is anything beyond what we get back from available, we have to allocate ourselves. So that's going to be out. This should be I out of I is self dot acquire new. And at this point, we can do standard mem maybe I should really just use standard maybe on in it here. Because here what we can do now is maybe on in it. And then there's like an assume this landed, I think in 156 even actually, maybe 155. There is assume in it const array array assume in it. Array assume in it of out safety, we have initialized all N. Oh, it's a nightly API, isn't it? All right. So this is really going to be safety. This is maybe on in it array assume in it. And we have initialized we have initialized all N. And then we can just copy paste this. Ooh, that's not what I wanted. Oh, where the T here is as pointer record. And same thing here. And I can't access the intrinsics. So I guess I will just not have that assertion. That's fine. I should say acquire new thoughts on using unit plus array map. You know, that's a good question. Can I use map for this? The problem with using map for this is that we're not mapping all of them the same, right? The map function is different for the first lower case N and for the latter for the remaining N. So array map would be a little weird, I think. All right. So back to this. So what we've implemented now is basically this. And there's a release they've added, which is pub create. Oh, I suppose you're right, actually. So once you're right, we could do, let me try and see if I can write that out. This and then we could do out dot map. If we did this dot map, and then we could do if not head dot is null, else self acquire new and get rid of maybe a minute. You're right. That is nicer. I take it all back. I regret everything. Release AP rec. So this is going to be pub create fn release. Self and as pointer record. So this is then going to be be assert that rec dot next dot is null next available. And then self dot push available. I'm just going to call that push available. All right. And this is going to be head and tail again. I guess we already have a release, which tells the record to release. I see which is going to stop being a thing. Okay. Okay. That's fine. And then there's also going to be a release. Oops. Release HP wrecks. I see which is if you want to release, like release many, which is if you have. See, this is where I think what I actually want here is for this to also be constant. Because I think this is specifically this use case. Right. Which is you have the thing in an array and you want to give them back because no one will be able to construct a linked list of has pointer records outside of this library. So the only thing that we'll ever have is what we give them. And what we give them is either singles or arrays of some length n. So there's no reason for us to really have the case where we have given them some number of things and they've like rearranged them and constructed a longer list. The example I'm thinking of here is imagine someone calls acquire twice. They would call it, I guess this should be acquire many and we should have here. They call it, they call acquire many twice. Once with both times with the value two as the number or something. There's no way that they can provide us with a linked list of four items. All they can do is return them as they came because they don't have a way to merge these. Right. We know as in the library authors, we know that you can string has pointer records together and construct a longer chain, but there's no way for the caller to do that on our behalf. So we don't actually need to support the use case where like, you give me an arbitrary head and tail and I deallocated for you. Instead, we only really need to deal with the case where they do what we, they give us back what we gave them. So this is just going to be acquire many one, zero, which and the reason why I want to do this is because it lets us, the tail is just the last element of the array, which we can compute trivially. Right. So we can do rex, rex dot Len minus one, which realistically, we can use rex dot last sort of the same thing. We only give out with and greater than zero. Right. So that's the equivalent to their that's their, the equivalent to their check of the tail is our check of last here, because we're assuming that we're giving them out in, in sort of order. Do they chain them together when they give them out? They do. So we probably need to do the same, which is let rex is this rex next available.store. It's awkward. I think what we'll do here is keep sort of a separate tail is standard pointer null mute. And then we're going to say here, tail is equal to head. And here we're going to say tail is equal to wreck. That doesn't look great. That definitely doesn't compile. This can go away. And now I should get an error up here. This should be available next dot store ordering relaxed because we haven't given this out anywhere. There we go. There we go. This is that that's ugly and I apologize. So this way we're guaranteeing that what we give out is also a valid linked list through the available next so that they can all be pushed back together at the end. And the last one in what we give out will have its next pointer be null. And is that in fact what this does next avail? Next avail? Where is the what does next avail actually do it is almost certainly just a relaxed load. Yeah, it's a relaxed load. Okay, so we string these together so that what we return is both an array and a valid linked list. And the array is basically our way of communicating the end along with the value rather than like a linked list plus a length. Be nice to do the same thing here, but we would have to return a slice and the slice doesn't have a meaningful lifetime. So that's fine. It also means that technically we should have this be like an option or something but I'm going to not deal with that. So here, in the release multiple, this is now going to be Rex zero. And this is going to be, I guess, let head is Rex zero, let tail is Rex dot last dot expect. And then we can assert here instead that the tail is that and then this can be the tail.  We no longer need to check the dot active flag. There is now this has disappeared. This is next or available next. So that's fine. This is where we can get rid of the old. That's fine, I guess, I guess it was up here anyway. So this is assert that and is greater than one. And then this is just going to walk the link list. I'm a little surprised actually that it can't. Oh, it can steal multiple at a time. Okay, so we're going to loop. We're going to get the head of the list, which like load avail is almost certain