mafulechka06 листопада 2019 р. 05:36

Швидкий та потокобезпечний аллокатор пулів для Qt - Частина 2

Зміст

1. Тестування з політикою

У першій частині цієї серії статей розглядався аллокатор пула, оптимізований для невеликих виділень. Розробники розповіли, що багато роблять у 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) всі потоки використовують ту саму арену.

Тестування з політикою

Розробники хочуть зробити аллокатор тестованим, не уповільнюючи його. Аллокатор, який повинен перевіряти змінні середовища або інші конфігурації середовища виконання, як частина своїх шляхів коду для отримання даних, що спостерігається, повинен буде виконати деяку додаткову роботу, навіть якщо він просто перевіряє, чи є покажчик функції 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++ вимагає, щоб кожен член структури мав унікальну адресу. Навіть масив нульового розміру споживає байт пам'яті, а розмірповертає 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))
Час: 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 додана як окремий коміт.