SMR design flaw and improvements

So, the freelist rapid push/pop test, using SMR, revealed an SMR bug, which in turn revealed the changes I made to the SMR function for advancing the generation counter, such that that function became multi-threaded (rather than being a critical section bounded by CAS flag) were broken.

What I’ve come up with now instead is the idea that there is a “setting” phase, where threads set their SMR state flags, and then when a thread sees that the generation counter can be advanced, we then have a “clearing” phase, where threads calling the generation-advance function act not to check to see if the generation counter can be advanced, but rather they check to see if all the per-thread flags have been cleared, so that we’re then in the correct state for threads to start the work again of indicating the SMR state so we can again see if the generation counter can be advanced.

The whole point of all this is to ensure any single thread entering the check function can make forward progress – before, this was not the case. I think the design is sound, although I’ve not yet implemented, because…

…I’ve realised in the course of this there is a design flaw, and I’ve not yet resolved it. The handle idle threads, I have it so that when a thread enters a lock-free section, it sets a flag – “LOCK_FREE_IN_PROGRESS” – and lowers that flag on exit. Design flaw is that the code only uses a store barrier, so there’s no guaranteee that flag is visible to other threads (who have issued a load barrier) until an atomic operation is performed – which typically occurs in the act of *performing* the lock-free work being done, i.e. *after* we’ve read in and are using sensitive memory addresses.

Any real SMR has to support idle threads, so I have to think of a solution.

Two steps forward, one step backwards, the mantra of all lock-free design work 🙂