So we’re back with the basic problem of how do we know when we can finally delete a data structure state instance.
A basic problem is that deallocation could be infinitely deferred.
Say a given thread had elements for a given data structure in its delete candidate list.
That thread then goes into a wait, on say a socket.
Well, the generation counter in the main SMR state is whizzing along – but that thread will never see it; and so never come to notice that it can now release the candidates in its list.
Other threads cannot touch that list (even though they have access to it – all thread SMR states are stored in the main SMR state) because it’s single threaded; which is to say, only one thread can access that list at a time, and it must always be available to the owning thread, because if the owning thread comes to want to put an element into the release candidate list it must be able to do so, or what else can it do with that element?
So here we actually see a really fundamental problem. What happens when release candidates linger on indefintely in a threads release candidate list? if we’re only going to call free() on them, well, that’s okay. And I guess it’s also true that we’re only going to call free() on the data structure state, too, so it’s just another element…
But what it does mean is that we have to be able to know, somehow, upon the release of an element, that we can now deallocate the data structure state. For that right now I have a counter of the number of elements in the state, and that counter has to be atomic – so that means an additional atomic increment/decrement for every push/pop type operation upon a data structure.