I have been following Herb Sutter on his Sutter’s Mill[1] website and while reading the solution and comments to the posted solution to GotW #6b Solution: Const-Correctness, Part 2[2] some thoughts popped into my head.
First to catch my eye were some comments on the overhead that may be incurred by std::atomic being only to do with what liberties the compiler can take with respect to optimising writes. This raised an eyebrow as I was under the impression that the need to force atomic operation effects to be globally and consistently visible has more of an effect on performance than reordering write restrictions. Even where a processor has atomic memory update support there is still a cost[3,4] – although that cost is significantly lower in modern processors.
The main topic though has to do with various comments noting that modifying the set of points added to objects of the example polygon class is not synchronised and performing such changes concurrently with other operations without external synchronisation will end in tears and confusion! One suggestion was to do all the updates on a single thread then allow shared concurrent read access to the finalised polygon. This got me speculating as to how to enforce such a usage pattern.
The pattern is:
-
Create an object – e.g. a polygon as per GotW 6b; this occurs on a single thread.
-
On this thread perform updates to this object (e.g. add points to the polygon).
-
Having performed all updates share the polygon for read-only access from potentially many threads concurrently.
The above omits what to do when we wish to delete the object - which of course should be considered a mutating operation! The simplest option might be:
-
When all threads using the object have died the object may be deleted.
Although this seems somewhat restrictive.
During the initial updating phase read-access will, in general, also need to be restricted to access by a single thread. Step 2 could be relaxed to allow access on different threads so long as access only occurred on one thread at a time. It would be nice to relax step 4 to allow the object to be safely deleted without all the reader threads having to terminate first.
Thus mutating and non-mutating (or const in C++ terms) operations have different usage restrictions:
-
Mutating operations are allowed to be used initially from a single thread then disallowed.
-
Non-mutating operations are allowed to be used initially from a single thread then from multiple threads.
Let’s consider restricting multithread access first. An obvious lock-based approach would be to create an object in a locked, mutable, state and then change the state to being immutable and release the lock. This does not help with the deletion problem though. Using a readers–writer or readers-upgrade-writer lock could potentially solve this issue: create in mutable, write-locked state, when done setting up the object’s state move to the immutable readers-locking state, when wanting to destroy the object obtain a writer lock, possibly via an upgrade lock.
Such locking strategies allow for more flexible usage patterns than we require here. Because multithread access is forbidden when in the initial mutable state we can just treat such accesses as errors when in this state. It would be nice to be able to prevent such usage by failing compilation – possibly restricting usage patterns such as use as stack objects only – but (I am fairly certain) this is not attainable. Hence we should look to detecting and raising such misuse as errors at runtime.
One obvious approach would be to use a std::atomic<bool> flag instance member that is tested, set and reset around each mutating operation. An exception is thrown if testing the flag indicates the method is currently being used by some other thread:
void the_type::mutating_operation()
{
bool expect_false{false};
if (!in_use.compare_exchange_strong(expect_false, true))
{
throw std::runtime_error
{"!!Concurrent access: illegal usage!!"};
}
// Do state changing stuff…
in_use = false;
}This will be monotonous to do repeatedly but the logic could be centralised – for example bundled up into a functor using execute-around to plumb in the boilerplate code around the actual work passed as a lambda function. A rough bare bones implementation might look like:
class enforced_exclusive_executor
{
std::atomic<bool> in_use;
public:
enforced_exclusive_executor() : in_use{false} {}
template <class WkFnT>
void operator()(WkFnT do_work)
{
bool expect_false{false};
if (!in_use.compare_exchange_strong(expect_false, true))
{
throw std::runtime_error
{"!!Concurrent access: illegal usage!!"};
}
do_work();
in_use = false;
}
};Which reduces the mutating operation implementation to:
void the_type::mutating_operation()
{
exclusive_exec([&](){/*Do state changing stuff…*/;});
}In which exclusive_exec is an instance member of the_type of type enforced_exclusive_executor.
Other than the various overheads incurred this technique’s main problem is not necessarily detecting access by multiple threads immediately, if at all. This means that pattern-misuse exceptions are raised indeterminably. Then of course there is the question of what to do about non-mutating operations that do not alter the object’s state.
A better approach may be to work with a token: if the token matches the current valid token then updates are OK otherwise it is erroneous usage. A convenient token would seem to be a thread id, represented in C++11 by the std::thread::id type:
void the_type::mutating_operation()
{
if (std::this_thread::get_id()!=update_id)
{
throw std::runtime_error
{"!!Concurrent access: illegal usage!!"};
}
// Do state changing stuff…
}update_id is an instance member of the_type of type std::thread::id which is initialised to the thread id of the thread creating the object. Of course the check logic can be pulled out - for example into a private instance method maybe called something like validate_call_context():
void the_type::validate_call_context()
{
if (std::this_thread::get_id()!=update_id)
{
throw std::runtime_error
{"!!Concurrent access: illegal usage!!"};
}
}
void the_type::mutating_operation()
{
validate_call_context();
// Do state changing stuff…
}This scheme will throw an exception any time any thread other than that the object expected to be called on calls any instance member function that validates its call context – which should be most if not all operations. The scheme has potential to be extended. Transferring the call context to another thread is simply a matter of updating the value of the object’s update_id to the id of the new calling thread. As such a transfer only makes sense during the initial updating stage of the object, like all such operations during this stage, it would be restricted to being performed only by the current calling context. As a bonus when moving to the shared, immutable state the calling context can be ‘transferred’ to the single distinct std::thread::id value that does not represent a thread – as produced by default constructing a std::thread::id object - which would ensure that all operations that validate their call context will fail.
I shall pause here and defer developing my musings further for a later post.