Using lock-free data structures in a “single-threaded mode”

I have recently implemented hazard pointers.

As with epoch-based safe memory reclamation, each thread maintains a list of allocations which are pending reclamation.

This list must support delete, and where it’s per-thread, it can be single-threaded, so no problems there.

One solution then is to provide in the library a single-threaded list.

However, there is another possible solution, which also provides useful functionality and allows the absence of this singleton single-threaded data structure; to allow the lock-free list to be operated in a single-threaded mode.

The user would need to know, a priori, that at some point the list would only be operated on by a single thread. That thread would enter single-threaded memory with a load barrier, then Do Stuff, and then finish with a store barrier and forced write to memory. Other threads wishing to use the list again in normal multi-threaded mode I think (not yet checked the code) can do so without a special effort, since they get load barriers anyway – but if not, then any thread wishing to again use that list must issue a macro (which turns into a load barrier).

Similar functionality would be useful for all of the data structures, I think; I can imagine times when they are operated on in a single-threaded mode, and then you simply do not want the overhead and costs of the atomic operations – but you DO still want to operate on the SAME data structure you will then use multi-threaded.

There are two efficiency concerns.

The first is that the data structure C-language structures often have alignment constraints on some of their members. This is fine for CAS platforms, but not necessarily for ERG platforms – the worst case on ARM is 2048 bytes, so you end up with fat structures. You would avoid this is you had a single-thread *only* data structure, because then you don’t care about alignment. Still – if we are arguing the use case where we want single-threaded operations on a data structure which we either before or after want to use multi-threaded, then there’s no avoiding it.

The second is to do with the type qualifier volatile. Volatile is necessary to prevent compiler optimization. The compiler can in theory put a value into a register and keep it there forever – load barriers, which could cause the cache line holding that value to change, do not cause the register to be updated, and so the compiler would continue forever to use an old value. This will break most data structures, or at least prevent forward progress 🙂

One common solution is to take use a non-volatile object, take a pointer to it, cast that pointer to be volatile, and access through it.

The Standard does not support this behaviour; by the language of the Standard, the compiler decides what to do with regard to volatile based on the type qualifier of the *object*, not the pointer.

However, GCC has supported this behaviour for a long time. I’m not sure what MSVC does, or other compilers.

What this means is that in single-threaded mode, the lock-free data structures must retain their volatile qualifier, which make them less efficient. We can avoid atomic operations, which is great, and we can perform operations which otherwise we could not (deletes for example) – but we can’t safely avoid volatile.

The problem is that if we did remove volatile, and use casts when we wanted volatile access, *but the compiler does not support it*, it would lead to a fault which would be intermittant and hard to diagnose.

The issue itself is difficult to explain to users – if it were for example exposed via the abstraction layer, by making volatile a define – and it is equally difficult for users to actually find out how their version of their compiler deals with volatile.

Correctness is the first attribute of software. You cannot ever put it at risk; software which does not do as it was intended has failed.

Given that it is problematic to determine whether a compiler will honour the type qualifier of the pointer, it has to be assumed it will not.