I'm implementing a 'sequence lock' class to allow locked write and lock-free reads of a data structure.
The struct that will contain the data contains the sequence value, which will be incremented twice while the write takes place. Once before the writing starts, and once after the writing is completed. The writer is on other threads than the reader(s).
This is what the struct that holds a copy of the data, and the sequence value looks like:
template<typename T>
struct seq_data_t
{
seq_data_t() : seq(0) {};
int seq; <- should this be 'volatile int seq;'?
T data;
};
The whole sequence lock class holds N copies of this structure in a circular buffer. Writer threads always write over the oldest copy of the data in the circular buffer, then mark it as the current copy. The writing is mutex locked.
The read function does not lock. It attempts to read the 'current' copy of the data. It stores the 'seq' value before reading. Then it reads data. Then it reads the seq value again, and compares it to the value it read the first time. If the seq value has not changed, the read is deemed to be good.
Since the writer thread could change the value of 'seq' while a read is occurring, I'm thinking that the seq variable should be marked volatile, so that the read function will explicitly read the value after it reads the data.
The read function looks like this: It will be on threads other than the writer, and perhaps several threads.
void read(std::function<void(T*)>read_function)
{
for (;;)
{
seq_data_type<T>* d = _data.current; // get current copy
int seq1 = d->seq; // store starting seq no
if (seq1 % 2) // if odd, being modified...
continue; // loop back
read_function(&d->data); // call the passed in read function
// passing it our data.
//??????? could this read be optimized out if seq is not volatile?
int seq2 = d->seq; // <-- does this require that seq be volatile?
//???????
if (seq1 == seq2) // if still the same, good.
return; // if not the same, we will stay in this
// loop until this condition is met.
}
}
Questions:
1) must seq be volatile in this context?
2) in the context of a struct with multiple members, are only the volatile qualified variable volatile, and not the other members? i.e. is only 'seq' volatile if I only mark it volatile within the struct?
1) must seq be volatile in this context?
Sure, most probably the read from seq will be optimized out with -O3. So yes, you should hint the compiler that seq might be changed elsewhere (i.e. in other thread) with volatile keyword.
For x86 architecture it would be enough, because x86 memory model is (almost) sequential as described on Wikipedia.
For portability, you better use atomic primitives.
2) in the context of a struct with multiple members, are only the volatile qualified variable volatile, and not the other members? i.e. is only 'seq' volatile if I only mark it volatile within the struct?
No, the data should be marked as volatile as well (or you should use atomic primitives as well). Basically, the loop:
for (;;) {
seq1 = d->seq;
read_data(d->data);
seq2 = d->seq;
if (seq1 == seq2)
return;
}
is equivalent to:
read_data(d->data);
return;
Because the only observable effect in the code is the read_data() call.
Please note, that most likely with -O3 compiler will reorder your code quite extensively. So even for x86 architecture you will need a compiler barriers between first seq read, data read and second seq read, i.e.:
for (;;)
{
seq_data_type<T>* d = _data.current;
int seq1 = d->seq;
COMPILER_BARRIER();
if (seq1 % 2)
continue;
read_function(&d->data);
COMPILER_BARRIER();
int seq2 = d->seq;
if (seq1 == seq2)
return;
}
}
The most lightweight compiler barrier is:
#define COMPILER_BARRIER asm volatile("" ::: "memory")
For C++11 you can use atomic_signal_fence() instead.
Overall, it is safer to use std::atomic<>: it is more portable and not that tricky as juggling with volatiles and compiler barriers...
Please also have a look at Herb Sutter's presentation called "atomic<> Weapons", which explains compiler and other memory barriers as well as atomics: https://channel9.msdn.com/Shows/Going+Deep/Cpp-and-Beyond-2012-Herb-Sutter-atomic-Weapons-1-of-2