Найти и уничтожить: как Clickhouse удаляет собственный код из памяти и переключается на использование Huge Pages

В Clickhouse есть интересный код: при вызове одной функции происходит перевод области памяти исполняемого кода программы на использование Huge Pages. В процессе весь код программы копируется на новое место, память, использовавшаяся изначально для кода программы возвращается ОС, а потом запрашивается снова. Эта статья основана на соответствующей части доклада с Я.Субботника.

Сначала мы посмотрим, что такое виртуальная память и TLB, потом перейдём собственно к Clickhouse, посмотрим, почему там пришла идея делать такие махинации с бинарником в памяти, а в конце посмотрим, как это всё реализовано.

Виртуальная память

Как известно, программы на современных процессорах x86 не работают с физической памятью напрямую - вместо этого используется механизм виртуальной памяти. При этом, все адреса памяти, которые доступны программе - виртуальные. При каждом обращении к памяти процессор преобразует виртуальный адрес в физический. Для того, чтобы это работало, ОС настраивает систему таблиц страниц. Посмотрим, как это происходит на 32-битной системе. Вся память делится на страницы. Как правило, страница имеет размер 4Кб. На x86 адрес в памяти имеет 32 бита. Чтобы преобразовать виртуальный адрес в физический, процессор берёт верхние 10 бит адреса и читает элемент с таким номером из таблицы страниц. Там будет лежать адрес второй таблицы, в которой ищется запись под номером, соответствующим вторым 10 битам изначального адреса. Теперь уже процессор получает адрес начала искомой страницы памяти, прибавляет к нему нижние 12 бит адреса и получает физический адрес, по которому уже можно прочитать или записать данные.

Конечно, так, как описано, всё работало бы очень долго: мы хотели пройти по одному адресу из памяти, а чтобы сделать это, пришлось ещё два раза читать из памяти таблицы страниц.. Поэтому используется TLB (Translation lookaside buffer) - это этакий кеш.

На X86/64 (amd64) схема работы с памятью похожая, но, поскольку адрес уже 64-ёх битный, а не 32-ух, то уровней таблиц становится 4 или 5, вместо двух.

Большие страницы

Поскольку TLB имеет ограниченный и не очень большой размер, промахи по нему случаются, и это отнимает много времени. Разработчики ядра Linux предложили решение этой проблемы - Huge pages. Это страницы размера 2Мб или 1Гб. Логика такая: страницы больше - всего страниц меньше - меньше места в TLB нужно и реже случаются промахи. Всё должно работать быстрее.

Тесты производительности Clickhouse

Для того, чтобы можно было делать хорошие оптимизации для Clickhouse, там есть тесты производительности - при каждом коммите запускается множество performance тестов. Поскольку Clickhouse - это СУБД, то тесты представляют из себя различные запросы. В итоге по каждому запросу может быть 4 вердикта:

1. Разница несущественная - нет статистически значимой разницы

2. Запрос ускорился

3. Запрос замедлился

4. Запрос нестабилен - разброс времени выполнения запроса настолько велик, что вывод сделать невозможно.

Последний вариант - это не очень хорошо, потому что не даёт полезной информации о влиянии коммита на производительность. Кроме того, некоторые нестабильные запросы могут не определяться как нестабильные, а случайный результат из первых трёх.

Почему же запросы могут быть нестабильными? Для того, чтобы понять, можно пытаться смотреть метрики:

• userspace метрики - те, которые Clickhouse сам собирает. Сколько времени запрос выполнялся, сколько строк обработано и так далее

• метрики ОС: сколько времени программа ожидала очереди на запуск и тд

• метрики процессора: сколько обработано инструкций, количество промахов L1 кеша и TLB

Странный Pull Request

В какой-то момент появился pull request, в котором добавили поддержку типов Int256, Uint256, Decimal256 для подсчёта денег в криптовалютах. В результате вырос размер бинарника (от 324 Мб до 429 Мб). Замедлений тестов производительности обнаружено не было, но выросло количество нестабильных тестов.

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

Решение - засунуть сегмент памяти с кодом программы в память, использующую Huge Pages!

Реализация

Код, который делает всю магию, находится здесь.

Итак, нам надо как-то заставить ОС использовать большие страницы для памяти с инструкциями программы.
Казалось бы, можно сделать системный вызов madvise и сказать операционной системе использовать большие страницы для нужного участка памяти.

Но не тут-то было. Linux позволит использовать большие страницы только для анонимных отображений в память - то есть, для тех, которые не связаны ни с каким файлом. Поскольку память с инструкциями - это отображение файла бинарника в память, то это, конечно, не анонимное отображение.

Что же тогда делать? Есть безумное решение - надо переаллоцировать код на лету:

1. Выделить новый кусок памяти и попросить ОС использовать для него большие страницы

2. Скопировать туда весь код программы

3. Сделать этот код исполняемым

4. Передать туда исполнение

5. Удалить отображение старого участка памяти с кодом, сделав munmap.

Будет ли это работать? Конечно, нет. Все вызовы функций, условные и безусловные переходы будут пытаться перейти на исполнение инструкций из старого куска памяти, для которого большие страницы не включены, так как при сборке Clickhouse не включено Position Independent Code из соображений производительности. При таком переходе произойдёт Segmentation Fault, потому что старой памяти уже нет или там лежит что-то другое.

Но можно сделать немного по-другому.

1. Выделить новый кусок памяти

2. Скопировать туда весь код программы

3. Сделать этот код исполняемым

4. Перейти туда

5. Удалить отображение старого участка с кодом, вызвав munmap

6. Выделить участок памяти по старому адресу, такого же размера, как и был

7. С помощью madvise попросить ОС использовать для него большие страницы

8. Переписать код на этот участок памяти, пометить его как исполняемый и перейти на него

9. Победа!

Будем смотреть, как это сделать.

Функция getMappedArea просматривает список отображений в память данного процесса и находит то, в котором находится переданный ей указатель - если передать туда адрес какой-нибудь функции, она вернёт то отображение, где находится код программы.

std::pair<void *, size_t> getMappedArea(void * ptr)
{
    using namespace DB;

    uintptr_t uintptr = reinterpret_cast<uintptr_t>(ptr);
    ReadBufferFromFile in("/proc/self/maps");

    while (!in.eof())
    {
        uintptr_t begin = readAddressHex(in);
        assertChar('-', in);
        uintptr_t end = readAddressHex(in);
        skipToNextLineOrEOF(in);

        if (begin <= uintptr && uintptr < end)
            return {reinterpret_cast<void *>(begin), end - begin};
    }

    throw Exception("Cannot find mapped area for pointer", ErrorCodes::LOGICAL_ERROR);
}

Функция remapExecutable вызывает функцию getMappedArea, после чего переходит на первый шаг нашего процесса в функции remapToHugeStep1.

size_t remapExecutable()
{
    auto [begin, size] = getMappedArea(reinterpret_cast<void *>(remapExecutable));
    remapToHugeStep1(begin, size);
    return size;
}

Функция remapToHugeStep1 выделяет новый кусок памяти с помощью mmap, копирует туда весь код программы функцией memcpy, после чего переходит к функции remapToHugeStep2, но не просто так, а переходя на код на новом участке памяти.

__attribute__((__noinline__)) void remapToHugeStep1(void * begin, size_t size)
{
    /// Allocate scratch area and copy the code there.

    void * scratch = mmap(nullptr, size, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (MAP_FAILED == scratch)
        throwFromErrno(fmt::format("Cannot mmap {} bytes", size), ErrorCodes::CANNOT_ALLOCATE_MEMORY);

    memcpy(scratch, begin, size);

    /// Offset to the scratch area from previous location.

    int64_t offset = reinterpret_cast<intptr_t>(scratch) - reinterpret_cast<intptr_t>(begin);

    /// Jump to the next function inside the scratch area.

    reinterpret_cast<void(*)(void*, size_t, void*)>(reinterpret_cast<intptr_t>(remapToHugeStep2) + offset)(begin, size, scratch);
}

На момент входа в функцию remapToHugeStep2 регистр instruction pointer (eip) находится на новом участке памяти, поэтому старый можно удалять. К сожалению, нельзя использовать библиотечные функции, поэтому используются их замены.

remapToHugeStep2 удаляет отображение бинарника в старый участок памяти с кодом с помощью munmap, затем там же делает анонимное отображение того же размера и просит ОС использовать для него большие страницы. Затем код программы копируется в это новое отображение и оно помечается как разрешённое только для чтения и исполнение (чтобы больше нельзя было туда писать). В конце концов мы переходим в функцию remapToHugeStep3, но уже в новом участке памяти.

__attribute__((__noinline__)) void remapToHugeStep2(void * begin, size_t size, void * scratch)
{
    /** Unmap old memory region with the code of our program.
      * Our instruction pointer is located inside scratch area and this function can execute after old code is unmapped.
      * But it cannot call any other functions because they are not available at usual addresses
      * - that's why we have to use "our_syscall" function and a substitution for memcpy.
      * (Relative addressing may continue to work but we should not assume that).
      */

    int64_t offset = reinterpret_cast<intptr_t>(scratch) - reinterpret_cast<intptr_t>(begin);
    int64_t (*syscall_func)(...) = reinterpret_cast<int64_t (*)(...)>(reinterpret_cast<intptr_t>(our_syscall) + offset);

    int64_t munmap_res = syscall_func(SYS_munmap, begin, size);
    if (munmap_res != 0)
        return;

    /// Map new anonymous memory region in place of old region with code.

    int64_t mmap_res = syscall_func(SYS_mmap, begin, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED, -1, 0);
    if (-1 == mmap_res)
        syscall_func(SYS_exit, 1);

    /// As the memory region is anonymous, we can do madvise with MADV_HUGEPAGE.

    syscall_func(SYS_madvise, begin, size, MADV_HUGEPAGE);

    /// Copy the code from scratch area to the old memory location.

    {
        __m128i * __restrict dst = reinterpret_cast<__m128i *>(begin);
        const __m128i * __restrict src = reinterpret_cast<const __m128i *>(scratch);
        const __m128i * __restrict src_end = reinterpret_cast<const __m128i *>(reinterpret_cast<const char *>(scratch) + size);
        while (src < src_end)
        {
            _mm_storeu_si128(dst, _mm_loadu_si128(src));

            ++dst;
            ++src;
        }
    }

    /// Make the memory area with the code executable and non-writable.

    syscall_func(SYS_mprotect, begin, size, PROT_READ | PROT_EXEC);

    /** Step 3 function should unmap the scratch area.
      * The currently executed code is located in the scratch area and cannot be removed here.
      * We have to call another function and use its address from the original location (not in scratch area).
      * To do it, we obtain its pointer and call by pointer.
      */

    void(* volatile step3)(void*, size_t, size_t) = remapToHugeStep3;
    step3(scratch, size, offset);
}

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

__attribute__((__noinline__)) void remapToHugeStep3(void * scratch, size_t size, size_t offset)
{
    /// The function should not use the stack, otherwise various optimizations, including "omit-frame-pointer" may break the code.

    /// Unmap the scratch area.
    our_syscall(SYS_munmap, scratch, size);

    /** The return address of this function is pointing to scratch area (because it was called from there).
      * But the scratch area no longer exists. We should correct the return address by subtracting the offset.
      */
    __asm__ __volatile__("subq %0, 8(%%rsp)" : : "r"(offset) : "memory");
}

Вот и всё, в общем-то.

Выводы

1. Всё работает, Huge Pages используются

2. Количество iTLB промахов уменьшилось почти до нуля

3. Скорость работы никак не изменилась

4. Как это повлияло на число нестабильных тестов - в докладе не сказано. Если найдёте эту информацию - подскажите.