В продолжение "Ох уж эти ученые мужички"

Сама статья тут

Разберем сначала 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;
};

Ох уж эти ученые мужички

Прочитал статью про "Lock Free Data Structures" мистера Andrei Alexandrescu. Подумал, что раз автор решил официально опубликовать это, то он хотя бы проверил то о чем в статье написал. Взял пример из нее попробовал - не работает. Начал вникать - а ЭТО работать не может в принципе вообще никак.

Кстати огромный полновесный камень мистеру Krzysztof Machelski, который получил большие спасибки за то, что проверял этот код и нашел всего 2 ошибки в нём.

P.S. В тему: "я тебе отдалась при луне, а ты взял мои белые груди и связал их узлом на спине - вот и верь после этого людям..."

О пользе исходников

Давеча писал новую собиралку .NET метаданных для моего dotTrace'ика. Так вот после 2-х дневного ползанья по исходникам .NET и рытья в отладчике я с удивлением узнал, что:

1. IMetaDataTables/IMetaDataTables2 интерфейсы хотя и заявлены (отвечают на QueryInterface или отдаются ICorProfilerInfo::GetModuleMetaData), но по факту профайлирным API от Microsoft не поддерживаютя - попытка работы с ними вызывает "Assert Violation".
2. Для динамических сборок, в отличие от нормальных, используется unmapped PE. Сейчас я понимаю, что это логично. НО, блин, хоть бы где, хоть пол словечка

P.S. Естественно в документации от Microsoft'а ни слова обо всем этом... Так, что исходники - это наше всЁ!!!