Сама статья тут
Разберем сначала CAS (compare-and-swap). Как вы знаете для того чтобы атомарно менять память (в том числе и на много- процессорных/ядерных машинах) в x86 и x64 пердусмотрены специальные ассемблерные команды, для совместимости в виндах они спрятаны в системные API вызовы InterlockedXXX. Так вот, если исключить экзотические или не поддерживаемые всеми платформами (в том числе Windows Mobile) наборы InterlockedXXX инструкций (например InterlockedCompare64ExchangeAcquire128 или InterlockedAdd64), то у нас практически остается только работа с указателем через InterlockedCompareExchangePointer и InterlockedIncrement/InterlockedDecrement. В статье же автор умудряется атомарно сравнивать структуры. Конечно теоритически все это возможно, но практического смысла не имеет никакого.
Теперь собственно по алгоритму. Первое что бросается в глаза - это реализация метора Lookup. Мне показалось странным, что инкрементируется счетчик в одной структуре, а декрементируется потенциально в другой. Это немедленно приведет к разъезжанию счетчиков и невозможности правильно удалить старые данные. Единственным рабочим вариантом мне кажется является запоминание того указателя для которого производился инкремент, чтобы потом для него же сделать декремент.
Дальше больше. Метод Update до момента CAS обязан точтно таким же образом инкрементировать счетчик того указателя для которого производится модификация данных. Зачем? Да затем, что неизвестно еще будут ли эти данные отброшены (полный зквивалент Lookup) или нет.
А вот собственно отлаженный и реально работающий код:
template
struct LockFreeValue
{
private:
struct Data
{
Value m_Value;
LONG volatile m_Ref;
__forceinline Data() : m_Ref(0) {}
};
public:
__forceinline LockFreeValue() : m_pData(NULL) { m_pData = new Data();}
__forceinline ~LockFreeValue() { delete m_pData; }
struct ReadContext
{
private:
LONG volatile * m_pRef;
friend struct LockFreeValue;
};
__forceinline Value const * EnterRead(ReadContext & context) const // Thread safe
{
while (true)
{
Data * const pData = m_pData;
InterlockedIncrement(CAST_INTERLOCKED_PLONG(&pData->m_Ref));
if (m_pData == pData)
{
context.m_pRef = &pData->m_Ref;
return &pData->m_Value;
}
InterlockedDecrement(CAST_INTERLOCKED_PLONG(&pData->m_Ref));
}
}
__forceinline void LeaveRead(ReadContext const & context) const // Thread safe
{
InterlockedDecrement(CAST_INTERLOCKED_PLONG(context.m_pRef));
}
struct WriteContext
{
private:
Data * m_pOld;
std::auto_ptr m_New;
friend struct LockFreeValue;
};
__forceinline Value * EnterWrite(WriteContext & context) const // Thread safe
{
while (true)
{
Data * const pData = m_pData;
InterlockedIncrement(CAST_INTERLOCKED_PLONG(&pData->m_Ref));
if (m_pData == pData)
{
std::auto_ptr newData(new Data());
newData->m_Value = pData->m_Value;
context.m_pOld = pData;
context.m_New = newData;
return &context.m_New->m_Value;
}
InterlockedDecrement(CAST_INTERLOCKED_PLONG(&pData->m_Ref));
}
}
__forceinline bool LeaveWrite(WriteContext & context) // Thread safe
{
bool const done = InterlockedCompareExchangePointer(
CAST_INTERLOCKED_PPVOID(reinterpret_cast(&m_pData)),
context.m_New.get(),
context.m_pOld) == context.m_pOld;
InterlockedDecrement(CAST_INTERLOCKED_PLONG(&context.m_pOld->m_Ref));
if (done)
{
context.m_New.release();
std::auto_ptr oldData(context.m_pOld);
while (oldData->m_Ref)
SafeSleep(10);
}
return done;
}
__forceinline Value * operator->() { return &m_pData->m_Value; }
__forceinline Value const * operator->() const { return &m_pData->m_Value; }
private:
Data * volatile m_pData;
};
