mafulechkaNov. 6, 2019, 5:36 a.m.

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

Content

В первой части этой серии статей рассматривался аллокатор пула, оптимизированный для небольших выделений. Разработчики рассказали, что многое делают в 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 добавлена, как отдельный коммит.

We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.
Support the author Donate

Comments

Only authorized users can post comments.
Please, Log in or Sign up
How to become an author?

Contribute to the evolution of the EVILEG community.

Learn how to become a site author.

Learn it
Donate

Good day, Dear Users!!!

I am Evgenii Legotckoi, developer of EVILEG. And it is my hobby project, which helps to learn programming another programmers and developers

If the site helped you, and you want also support the development of the site, than you can donate by following ways

PayPalYandex.Money
Timeweb

Let me recommend you the excellent hosting on which EVILEG is located.

For many years, Timeweb has been proving his stability.

For projects on Django I recommend VDS hosting

View Hosting
KA

C++ - Тест 003. Условия и циклы

  • Result:78points,
  • Rating points2
R

C++ - Test 002. Constants

  • Result:75points,
  • Rating points2
R

C++ - Test 001. The first program and data types

  • Result:73points,
  • Rating points1
Last comments
V

Django - Tutorial 027. Implementation Google reCAPTCHA

Спасибо. Только использую декоратор не в urls.py а перед views
R

Qt WinAPI - Lesson 001. How to collect all DLL, which used in Qt project?

Вы меня не совсем правильно поняли, но все равно спасибо, принял все к сведению. Все сделал как вы сказали, все отлично работает, еще раз огромнейшее спасибо) Разве что только что были опять про…

Qt WinAPI - Lesson 001. How to collect all DLL, which used in Qt project?

Стоило перед использованием что ли инструкцию прочитать https://www.cyberforum.ru/blogs/131347/blog2457.html "После сборки при запуске требовались dll," Ясное дело стоило задепло…
R
R

Qt WinAPI - Lesson 001. How to collect all DLL, which used in Qt project?

Да, собралось. После сборки при запуске требовались dll, перекинул всю папки bin, plugins(не знаю как можно было сделать более умно). Как я понял в первой строке путь к екзешнику вставляю, втор…
Now discuss on the forum

QML+QtGraphicalEffects

да, сборку делал без параметра поиска qml, хотя dll QtGraphicalEffects он подтягивает, когда я добавил всю папку QtGraphicalEffects в проект - то заработало, похоже что именно qml-файлов ему не …

Не работают слоты/сигналы

и посмотрите работу с потоками в Qt, там подробно описано как передавать данные с одного в потока в другой при помощи сигналов и слотов

Как в Qt в qmenu добавить scrollarea

Вот это наследованный класс меню. Но посути это обычное меню. #pragma once#include <QtWidgets>class TransMenu : public QMenu { Q_OBJECTpublic: TransMenu(QWidget* parent = …

Qt C++ и Python

Красиво/некрасиво - это скорее моё личное отношение. Если есть возможность ограничить количество интсрументов, то лучше ограничить. Но не зацикливайтесь на этом. Если у вас есть скрипты Py…

Qt + OpenGL glDeleteVertexArrays

Я не уверен, поскольку с OpenGL очень мало работал. Но может быть OpenGL контекст виджета нужно переинициализовывать. И ещё виджет стоит удалять через метод deleteLater() а не п…
About
Services
© EVILEG 2015-2020
Recommend hosting TIMEWEB