mafulechka6 ноября 2019 г. 5:36

Быстрый и потокобезопасный аллокатор пулов для Qt - Часть 2

Содержание

1. Что разработчики хотят проверить?
2. Тестирование с политикой

В первой части этой серии статей рассматривался аллокатор пула, оптимизированный для небольших выделений. Разработчики рассказали, что многое делают в Qt, выделяя экземпляры QEvent или QObject, и специализированный аллокатор может быть полезен и для их приложений. Пока что решения разработчиков Qt будут распределять целые страницы памяти по мере необходимости и раздавать фрагменты данных фиксированного размера, который указывается во время компиляции через параметр шаблона. Он поддерживает различные модели потоков, с различными компромиссами в отношении производительности, эффективности памяти и параллелизма. Разработчики получили очень многообещающие результаты, превзойдя аллокаторы общего назначения в 3-10 раз в многопоточных тестах.

Однако, с помощью аллокатора, который может обрабатывать только один размер блока и никогда не возвращает память обратно операционной системе, у разработчиков все еще есть путь, прежде чем они смогут реально поддерживать сценарии использования QEvent и QObject в Qt. Невозможно просто израсходовать библиотеку впустую и забрать память, или попросить разработчиков приложений реализовать оператор new/delete, чтобы иметь возможность выделять экземпляры своих больших подклассов.

Но прежде, чем задуматься о том, чтобы добавить больше сложности, разработчикам нужно подумать о тестировании. Об этом и будет эта статья.

Что разработчики хотят проверить?

Тестирование аллокатора только с использованием стратегий «черного ящика» очень ограничено. Разработчики не могут быть уверены, что аллокатор обеспечивает правильное выполнение, если смотреть только на указатели, которые от него получают. Они хотят быть уверены, что аллокатор находится в том состоянии, в котором ожидают. В идеале, можно сделать это без необходимости написания тестового кода, который более или менее дублирует то, что уже делает аллокатор. В основном это будет просто проверка того, что есть способность копировать/вставлять код (copy/pasting code). Кроме того, если бы имелся доступ к внутренним структурам данных, пришлось бы блокировать их во время многопоточного тестирования, что делать определенно не хочется.

Но даже при безупречной реализации аллокатора
пользовательский код (user-code) также будет содержать ошибки. Разработчики должны получать предсказуемые ошибки, если их код выполняет запрещенные операции чтения или записи, осуществляет доступ к удаленным объектам, имеет ошибки двойного освобождения или утечки памяти. Такой доступ к памяти обычно вызывает ошибки нарушения сегментации с полезной трассировкой стека. Но разработчики работают только с памятью, которая принадлежит процессу (если только не попадаем на край страницы памяти), и операционная система не следит за тем, что делают с этой памятью. Кроме того, использование пользовательских аллокаторов приводит к появлению совершенно нового типа ошибок - несоответствие аллокатора. Все аллокаторы используют структуры данных и макеты памяти, которые оптимизированы для их эффективной работы, поэтому выбрасывание произвольного адреса в аллокатор приведет к неопределенному поведению, если этот адрес не был получен из того же аллокатора в первую очередь.

И, наконец, аллокатор Qt в некоторой степени настраивается и предназначен для довольно специфических ситуаций. Разработчики хотят собрать данные о том, как аллокатор используется в реальных условиях, чтобы можно было настроить конфигурации и убедиться, что это правильный тип аллокатора.

Пока разработчики не узнают, что аллокатор работает правильно, можно оставить в стороне обнаружение ошибок в пользовательском коде. Вот некоторые вещи, которые нужно проверить, чтобы быть уверенными в реализации:

• когда выделяют столько фрагментов, сколько умещается на странице, а затем освобождают первый выделенный фрагмент, то при следующем выделении не должна выделяться дополнительная страница;
• когда выделяют больше фрагментов данных, чем помещается на странице, тогда аллокатор должен выделять новую страницу;
• в многопоточном аллокаторе (multi-threaded allocator) используемые arena не удаляются, если соответствующий поток завершается, а помечаются, как устаревшие;
• в многопоточном аллокаторе новый поток будет повторно использовать arena, ранее помеченную, как устаревшую;
• в аллокаторе общего пула (multi-threaded allocator) все потоки используют одну и ту же arena.

Тестирование с политикой

Разработчики хотят сделать аллокатор тестируемым, не замедляя его. Аллокатор, который должен проверять переменные среды или другие конфигурации среды выполнения, как часть своих путей кода для получения наблюдаемых данных, должен будет выполнить некоторую дополнительную работу, даже если он просто проверяет, является ли указатель функции nullptr перед вызовом. Разработчики хотят избежать такой дополнительной работы. Он не только замедляет работу, но также может скрывать неочевидные состояния гонки, которые можно было бы иметь в своем многопоточном коде.

К счастью, разработчики используют C++ и реализуют аллокатор, как шаблонный класс. Это позволяет использовать policy-based design, где объявляют интерфейс, через который аллокатор может сообщать о важных событиях, которые происходят в его реализации:

enum class AnalyzerEvent {
    Allocate,
    Free,
    ArenaCreate,
    ArenaDestroy,
    PageAllocate,
    PageFree,
    MemoryLeaked
};

// the no-op policy
struct NoAnalyzer
{
    reportEvent(AnalyzerEvent, void *) {};
};

template<size_t ChunkSize, ThreadModel Threading = MultiThreaded,
         typename Analyzer = NoAnalyzer>
class PoolAllocator : public Analyzer
{
    // ...
    struct Arena
    {
        Arena(PoolAllocator *allocator)
            : m_allocator(allocator)
        {
            m_allocator->reportEvent(AnalyzerEvent::ArenaCreate, this);
        }
        // ...
        bool grow()
        {
            void *ptr = ::mmap(NULL, sizeof(Page), PROT_READ | PROT_WRITE,
                               MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
            m_allocator->reportEvent(AnalyzerEvent::PageAllocate, ptr);
            // ...
        }
        PoolAllocator *m_allocator;
    };
public:
    // ...
    void *allocate(size_t size)
    {
        reportEvent(AnalyzerEvent::Allocate, &size);
        // ...
    }
    void free(void *ptr)
    {
        reportEvent(AnalyzerEvent::Free, ptr);
        // ...
    }
};

С этим шаблоном компилятор по умолчанию оптимизирует вызов пустой функции. А поскольку применяется оптимизация пустой базы, не увеличивается размер экземпляра PoolAllocator. Даже не требуется таблица виртуальных функций! Нужно передать указатель на аллокатор в экземпляры Arena, где будет сообщаться о некоторых событиях, но также дальше будет видно, что этот указатель имеет другие практические применения, поэтому стоить платить эти 8 байтов за поток.

Если предоставляется класс анализатора, код пользователя может обращаться к своим членам данных напрямую через экземпляр PoolAllocator. Нужно быть осторожными, чтобы не объявлять какие-либо элементы, конфликтующие с существующими членами PoolAllocator, также нужно сделать анализатор безопасным для потоков, как настроено для экземпляра PoolAllocator. Обычно это приводит к мьютексу, поэтому использование анализатора окажет некоторое влияние на поведение и производительность аллокатора, особенно в условиях высокой степени одновременности.

struct UsageAnalyzer
{
    QBasicMutex m_mutex;
    int pageCount = 0;

    void recordEvent(AnalyzerEvent t, void *p)
    {
        std::lock_guard lock(m_mutex);
        switch (t) {
        case AnalyzerEvent::PageAllocate:
            ++pageCount;
            break;
        default:
            break;
        }
    }
};

С помощью такого анализатора можно написать тестовые случаи, которые подтверждают правильное поведение аллокатора, например, чтобы проверить два первых элемента из списка выше:

void tst_PoolAllocator::test()
{
    PoolAllocator<16, SingleThreaded, UsageAnalyzer> allocator;
    const size_t numChunks = allocator.chunksPerPage();

    void *objects[numChunks];
    QCOMPARE(allocator.pageCount, 0);
    for (int i = 0; i < numChunks; ++i)
        objects[i] = allocator.allocate(16);
    QCOMPARE(allocator.pageCount, 1);
    allocator.free(objects[0]);
    objects[0] = allocator.allocate(16);
    QCOMPARE(allocator.pageCount, 1);

    void *object = allocator.allocate(16);
    QCOMPARE(allocator.pageCount, 2);

    allocator.free(object);
    for (int i = 0; i < numChunks; ++i)
        allocator.free(objects[i]);
}

Можно расширить класс анализатора, чтобы отслеживать общее использование аллокатора в приложении, а также может сообщать об утечках памяти, когда аллокатор выходит из области видимости. Чего пока невозможно сделать эффективно, так это связать наблюдаемые метаданные с индивидуальными аллокаторами.

Метаданные с использованием заголовка

Аллокатор Qt не требует никакого заголовка с информацией о распределении, если игнорируем несколько указателей, которые несет сам аллокатор - 99,8% использования памяти. Каждая страница 4K содержит один указатель на arena, к которой он принадлежит, поэтому имеется 4088 байтов фрагментов данных. Это здорово, но иногда полезно иметь возможность связывать некоторые метаданные с каждым аллокатором. Например, захотим подтвердить, что распределения с использованием аллокатора пулов действительно недолговечны. Вариант использования, в котором такие метаданные могут быть даже частью производственной системы, - это прозрачно реализованный счетчик ссылок или сборщик мусора.

Структура данных для используемого типа Node до сих пор была объединением: для свободных узлов - указатель на предыдущий узел в свободном стеке; для выделенных узлов - массив байтов:

union Node
{
    Node *previous;
    char chunk[ChunkSize];
};

Для случаев по умолчанию, когда не нужен заголовок, будем придерживаться этого макета. Если нужен заголовок, тогда нужно добавить еще один элемент данных с необходимым пространством. Поскольку аллокатор пулов является шаблоном, можно использовать методы метапрограммирования:

struct NoHeader {};

template<size_t ChunkSize, ThreadModel Threading = MultiThreaded,
         typename Header = NoHeader, typename Analyzer = NoAnalyzer>
class PoolAllocator : public Analyzer
{
    static constexpr size_t HeaderSize = std::is_empty<Header>::value
                                       ? 0 : sizeof(Header);
    struct NodeDataWithHeader
    {
        char header[HeaderSize];
        char chunk[ChunkSize];
    };
    struct NodeDataWithoutHeader
    {
        char chunk[ChunkSize];
    };
    using NodeData = typename std::conditional<HeaderSize == 0,
                     NodeDataWithoutHeader, NodeDataWithHeader>::type;
    union Node
    {
        Node *previous;
        NodeData data;
        void initHeader()
        {
            if constexpr (HeaderSize > 0
                      && std::is_default_constructible<Header>::value
                      && !std::is_trivially_default_constructible<Header>::value) {
                (void)new (node->header) Header();
            }
        }
        void destructHeader()
        {
            if constexpr (HeaderSize > 0
                      && std::is_destructible<Header>::value
                      && !std::is_trivially_destructible<Header>::value) {
                reinterpret_cast<Header*>(node->header)->~Header();
            }
        }
        static Node *fromMemory(void *ptr)
        {
            return reinterpret_cast<Node*>(static_cast<char*>(ptr) - HeaderSize);
        }
    };
    // ...

C++ не допускает массив нулевого размера и даже если это так, стандарт C++ требует, чтобы каждый член структуры имел уникальный адрес. Даже массив нулевого размера потребляет байт памяти, а sizeof возвращает 1 для пустой структуры. Чтобы не тратить этот байт, выбираем соответствующую структуру во время компиляции, в зависимости от того, является ли тип пустым или нет. Использование C++17, если оператор constexpr предотвращает ошибки времени компиляции, когда нет заголовка или, если заголовок не требует построения, или уничтожения. Вспомогательные функции скрывают детали, поэтому allocate() и free() не становятся намного сложнее:

void *allocate(size_t size)
    {
        Q_ASSERT(size <= ChunkSize);
        Node *node = arena()->pop();
        if (!node)
            return nullptr;
        node->initHeader();
        return node->data.chunk;
    }

    void free(void *ptr)
    {
        Node *node = Node::fromMemory(ptr);
        node->destructHeader();
        Arena *arena = Page::fromNode(node)->arena;
        arena->push(node);
    }

Так как пользовательский код захочет что-то сделать с заголовком, класс аллокатора может дать доступ к заголовку для указателя:

 static Header *header(void *ptr)
    {
        if constexpr (HeaderSize == 0)
            return nullptr;
        return reinterpret_cast<Header*>(Node::fromMemory(ptr)->header);
    }
};

Анализ

Теперь есть возможность делать некоторые интересные вещи с заголовками и анализаторами. Поскольку разработчики создают аллокатор, оптимизированный для небольших и недолговечных объектов, подтвердим действительно ли код распределяет объекты:

struct TimingHeader
{
    QElapsedTimer timer;
    TimingHeader()
    {
        timer.start();
    }
};

struct UsageAnalyzer
{
    UsageAnalyzer(...)
    {}

    QBasicMutex m_mutex;
    QMap<size_t, int> m_sizehistogram;
    QMap<h;int, int> m_timeHistogram;
    int m_pageCount = 0;

    void recordEvent(QAllocator::AnalyzerEvent t, void *p);
};

// the biggest event we have seen in our last test was 112 bytes
using EventAllocator = PoolAllocator<112, MultiThreaded, TimingHeader, UsageAnalyzer>;
Q_GLOBAL_STATIC(EventAllocator, eventAllocator);

void UsageAnalyzer::recordEvent(AnalyzerEvent t, void *p)
{
    std::lock_guard lock(m_mutex);
    switch (t) {
    case AnalyzerEvent::Allocate:
        ++m_sizeHistogram[*static_cast<size_t*>(p)];
        break;
    case AnalyzerEvent::Free:
        ++m_timeHistogram[QEventAllocator::header(p)->timer.elapsed()];
        break;
    case AnalyzerEvent::PageAllocate:
        ++m_pageCount;
        break;
    default:
        break;
    }
}

void *QEvent::operator new(std::size_t size) noexcept
{
    qDebug() << "Usage:" << eventAllocator()->m_sizeHistogram;
    return eventAllocator()->allocate(size);
}

void QEvent::operator delete(void *ptr) noexcept
{
    qDebug() << "Timing:" << eventAllocator()->m_timeHistogram;
    qDebug() << "Pages:" << eventAllocator()->m_pageCount;
    eventAllocator()->free(ptr);
}

Использование этого в qcoreevent.cpp в Qt и запуск любого теста Qt действительно подтвердит, что распределения QEvent и малы, и очень недолговечны, за очень немногими исключениями.

Usage (Использование): QMap((24, 2367)(32, 26)(112, 557))
Timing: QMap((0, 44)(1, 10)(2, 91)(3, 116)(4, 330)(5, 524)(6, 546)(7, 397)(8, 338)(9, 219)(10, 135)(11, 41)(12, 21)(13, 14)(14, 7)(15, 6)(30, 12)(31, 5)(32, 17)(33, 3)(35, 7)(36, 10)(37, 3)(41, 11)(44, 5)(45, 7)(46, 2)(47, 4)(49, 1)(63, 2)(90, 9)(95, 5)(96, 3)(215, 1)(19800, 2)(19802, 3))
Pages (Страницы): 4

Также видно, что достигнут пик на 4 страницах, выделенных для экземпляров QEvent. 16K определенно больше, чем хотелось бы, поэтому определенно нужно оптимизировать это.

Отладка кода пользователя

Теперь, когда можно убедиться, что аллокатор реализован правильно и что, в первую очередь, используется правильный аллокатор, можно сосредоточиться на том, чтобы облегчить пользователям обнаружение ошибок в их коде.

Для начала, можно добавить несколько отключений в сборках отладки. Аллокатор, являющийся шаблоном, снова помогает, поскольку только код, использующий его, должен быть собран в режиме отладки. Например, можно добавить простое обнаружение двойного освобождения, пройдя по стеку и проверив, находится ли входящий узел в нем:

void push(Node *node)
{
#ifdef QT_DEBUG
    Node *doubleFreeTest = stack;
    while (doubleFreeTest) {
        if (doubleFreeTest == node)
            qFatal("Double free detected for %p", node->chunk);
        doubleFreeTest = doubleFreeTest->previous;
    }
#endif
    node->previous = stack;
    stack = node;
}

Также можно заполнить освобожденную память фрагмента данных мусором, используя memset, чтобы повысить вероятность того, что использование такой памяти вызовет ошибки и неопределенное поведение, которое легко заметить и идентифицировать при отладке. Выполнение этого только для отладочных сборок не добавляет никаких накладных расходов для кода, работающего в рабочей среде.

Архитектура аллокатора Qt также позволяет эффективно защищать от несоответствий аллокатора. Поскольку можно легко отобразить адрес пользователя на страницу, оттуда к arena, и оттуда, благодаря указателю аллокатора, который нужно было добавить, чтобы иметь возможность вызывать интерфейс политики, аллокатору, можно реализовать проверку:

bool owns(void *memory) const
    {
        Page *page = Page::fromNode(Node::fromMemory(memory));
        return page->arena->m_allocator == this;
    }
    void free(void *ptr)
    {
        if (!owns(ptr))
            qFatal("Allocator mismatch for %p", ptr);

        Node *node = Node::fromMemory(ptr);
        node->destructHeader();
        Arena *arena = Page::fromNode(node)->arena;
        arena->push(node);
    }

Это помогло бы, если бы имелось несколько аллокаторов пулов для разных размеров или типов. Конечно, более вероятно, что получим аварийное завершение, если free() или owns() вызываются совершенно неизвестным указателем, и в этом случае не возникает никаких проблем.

Поддержка Address Sanitizer

Очень хорошим и популярным средством отладки памяти является средство Address Sanitizer. Компиляторы, которые его поддерживают, предоставляют API, позволяющие пользовательскому коду отравлять и распаковывать адреса и области памяти. Существуют также API-интерфейсы для проверки того, являются ли адреса и области памяти отравленными, и затем можно использовать их для проверки правильности отравления и удаления областей. Использование API-интерфейсов ASan, неявно, также улучшает тестирование самого кода аллокатора, так как будем касаться отравленных адресов, если, например, арифметика указателей верна.

В разделе обзора кода поддержка ASan добавлена, как отдельный коммит.