Эволюция ошибок

Сегодня было проведены полномаштабные dotTrace-маневры в обстановке приближенной к боевой. Незамедлительно я отметил для себя удивительную закономерность: предыдущая версия частенько кидала "Out of Memory" (эта стандартная болезнь почти всех профайлеров), а новая похоже будет частенько кидать "Low Disk Space"... Не смешно! Как вам размер снапшотика в 36 Гигабайт? А ведь это всего 20% теста... Другими словами, снапшотик в 180 Гигабайт - это наша объективная реальность. Не смешно, два раза! С другой стороны, один снапшот - это один винчестер. На лицо удобство транспортировки...

P.S. А теперь скажем об этом официально.

API из песка и тумана

Кривые ручка отдельного програмиста - это дело его босса, а вот кривые ручки одной из команд MS - это уже дело каждого. Особенно, если кривость увековечена в WinSDK. Итак, приступим. Постоянно ковыряясь в ассемблере x86 и x64 я заметил, что InterlockXXX функции в x86 - это вызовы API, а в x64 - просто команды ассемблера. Ошибкой было бы думать, что это трагическая случайность. И действительно для x64 и IPF в WinSDK по умочанию сделаны специальные intrinsic-мактосы, а про платформу x86 попросту забыли. Ну не совсем забыли конечно - все можно включить, но это требует некоторого умения и сноровки. Переопределение InterlockedExchangePointer и InterlockedCompareExchangePointer сделано не случайно - без оного мы опять получаем вызовы API вместо ассемблерной команды.

#if defined(_M_IX86)
  #include "intrin.h"
 
  #define InterlockedIncrement _InterlockedIncrement
  #define InterlockedDecrement _InterlockedDecrement
  #define InterlockedExchange _InterlockedExchange
  #define InterlockedCompareExchange _InterlockedCompareExchange
 
  #undef InterlockedExchangePointer
  #define InterlockedExchangePointer(T, V) ((PVOID) InterlockedExchange((PLONG) (T), (LONG) (V)))
 
  #undef InterlockedCompareExchangePointer
  #define InterlockedCompareExchangePointer(D, E, C) ((PVOID) InterlockedCompareExchange((PLONG) (D), (LONG) (E), (LONG) (C)))
#endif

Зачем же я все это говорю, если и так и так все работает. Да вы наверно уже обо всем догадались - ассемблерные команды сильно быстрее. На моем приложении прирост на пустом месте составил более 5%.

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

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

Разберем сначала 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'а ни слова обо всем этом... Так, что исходники - это наше всЁ!!!

Зависание при вызове Control.Invoke

Симптомы:
Приложение зависает при вызове Control.Invoke() для фреймворка 2.0, под 1.1 все работает изумительно.

Вскрытие показало:
Не приходит эвент об окончании выполнения функции которую хотели вызвать через Control.Invoke(), более того сама функция, которую нужно вызвать в другой нитке, не вызывается вобще, однако запрос поставлен в очередь контрола. Дальнейшее исследование вопроса выявило, что выполнение очереди происходит по получении контролом специального зарегистренного сообщения "WindowsForms12_ThreadCallbackMessage". Вот тут то и выяснилось, что это сообщение вобще не посылается. Ниже приведен дизасмблеж кода с ошибкой.

private object MarshaledInvoke(Control caller, Delegate method, object[] args, bool synchronous)
{
    int lpdwProcessId;
    if (!this.IsHandleCreated)
        throw new InvalidOperationException(SR.GetString("ErrorNoMarshalingThread"));
    if (((ActiveXImpl) this.Properties.GetObject(PropActiveXImpl)) != null)
        IntSecurity.UnmanagedCode.Demand();
    bool flag = false;
    if ((SafeNativeMethods.GetWindowThreadProcessId(new HandleRef(this, this.Handle), out lpdwProcessId) == SafeNativeMethods.GetCurrentThreadId()) && synchronous)
        flag = true;
    ExecutionContext executionContext = null;
    if (!flag)
        executionContext = ExecutionContext.Capture();
    ThreadMethodEntry entry = new ThreadMethodEntry(caller, method, args, synchronous, executionContext);
    lock (this)
    {
        if (this.threadCallbackList == null)
            this.threadCallbackList = new Queue();
    }
    lock (this.threadCallbackList)
    {
        if (threadCallbackMessage == 0x0)
            threadCallbackMessage = SafeNativeMethods.RegisterWindowMessage(Application.WindowMessagesVersion + "_ThreadCallbackMessage");
        this.threadCallbackList.Enqueue(entry); // Ставим запрос в очередь вызываемого контрола
    }
    if (flag)
        this.InvokeMarshaledCallbacks(); // Если можно вызвать функцию синфронно, то вызываем синхронно
    else
    {
        UnsafeNativeMethods.PostMessage(new HandleRef(this, this.Handle), threadCallbackMessage, IntPtr.Zero, IntPtr.Zero); // Вызываем функцию асинхронно
        // БАГА ТУТ: нет проверки на невозможность поставить сообщение в очередь
    }
    if (!synchronous)
        return entry;
    if (!entry.IsCompleted)
        this.WaitForWaitHandle(entry.AsyncWaitHandle); // Ждем окончания выполнения для асинхронного вызова
    if (entry.exception != null)
        throw entry.exception;
    return entry.retVal;
}

Причина смерти:
Горячо любимый Microsoft забыл выдать эксепшен в случае невозможности отсылки сообщения с помощью PostMessage. Оказалось, что на момент Control.Invoke() очередь сообщений заполнена на 100%!!!

Лечение:

по таймеру посылать "WindowsForms12_ThreadCallbackMessage" контолу (не кошерно, но когда нет другого выхода, то сойдет);

сделать Thread.Sleep() на пару секунд для очистки очереди в вызывающем треде (не наш метод, мы боремся за скорость);

устранить причину заполнености очереди сообщений.