История про realloc (и лень)

Простой макрос

Все началось с простого макроса: (приблизительный код)

#define ADD_BYTE(C) do {            
  if (offset == capa) {             
    if (capa < 16) {                
      capa = 16;                    
    } else {                        
      capa <<= 1;                   
    }                               
    buffer = realloc(buffer, capa); 
    assert(buffer != NULL);         
  }                                 
  buffer[offset++] = (C);           
} while(0)

Для тех, кто не знаком с языком программирования C, поясню: этот простой макрос™ добавляет байт «C» в динамически выделяемый буфер (buffer), размер которого (в байтах) равен capa. Следующая позиция для записи определяется при помощи параметра offset. При каждом заполнении буфера происходит двукратное увеличение его объема (начиная с минимального размера в 16 байт).

Мы добавляем байты в динамический буфер — это одна из наиболее распространенных операций практически в любой программе (для работы со строками, массивами и т. п.).

Но как понять, насколько эффективна стратегия перераспределения? Если вы посмотрите на эту проблему с точки зрения сложности, принимая сложность realloc() равной O(N), то сразу поймете, что добавление одного байта имеет сложность в среднем O(1), что вполне неплохо.

Но какова сложность в наихудшем случае — если требуется перераспределение памяти под буфер?

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

Я: Хм… Честно говоря, никогда не задумывался над этим… Но уверен, все не так страшно. Система должна успешно справиться с этой задачей.

Анонимус: А мне кажется, что связанная структура — более удачный вариант, пусть даже с той же экспоненциальной стратегией.

Я: Да нет, это пустая трата времени.

Анонимус: Пруф?

Ах вот так, значит?!

Ладно, придется обосновать свою позицию. Как и все программисты, я весьма ленив. Точнее: «Как подобает программисту, я весьма ленив». Лень — отличный стимул стать умнее и эффективнее. Вы слишком ленивы для того, чтобы решать повторяющиеся или рутинные задачи; вам нужно что-то более интеллектуальное, что-то максимально быстрое. Да, именно это иногда называют ленью. Но, по-моему, это не что иное, как эффективность.

Связанный список блоков для хранения буфера — несколько громоздкое решение. Я не говорю, что это невозможно. «Невозможно — не французское слово», — говаривал Наполеон (правда, кончил он плохо). Решение возможно, но оно громоздкое. Копирование подмассива или сохранение его на диск потребует некоторых усилий. Нам, вероятно, пришлось бы поддерживать индекс указателей на начало каждого массива, брать логарифм по основанию два, чтобы получить адрес начала блока и еще много всякой нудятины… Ух, я уже устал…

Что-то подсказывает мне, что моя лень будет здесь как нельзя кстати. Ведь о маленьких блоках вовсе не стоит беспокоиться, а о больших позаботится виртуальная память системы.

Давайте разберемся.

Кстати, что такое realloc()?

Это обычная функция, соответствующая стандарту POSIX, которая реализована в библиотеке C. В случае с Linux это библиотека libc.so, в ней же находятся и родственные realloc функции malloc и free:

nm -D /lib/x86_64-linux-gnu/libc.so.6 | grep -E "T (malloc|realloc|free)$"
000000000007e450 T free
000000000007e030 T malloc
000000000007e4e0 T realloc

Для тех, кому это действительно интересно: «T» означает «text symbol» (текстовый символ), заглавная буква используется, чтобы показать, что символ этот общедоступный и видимый; текстовый сегмент программы — это код, сегмент данных — инициализированные данные (переменные), а сегмент bss — неинициализированные данные (переменные), а точнее данные (переменные), получившие в качестве начального значения ноль).

Для выделения, перераспределения и освобождения памяти используется распределитель памяти (спасибо, Капитан Очевидность!). Таких распределителей много (самый известный — buddy allocator).

Мы можем реализовать собственный простейший распределитель с помощью великого и ужасного вызова sbrk, который просто добавляет пустое пространство в конец сегмента данных:

#include <sys/types.h>
#include <unistd.h>
#include <string.h>

void *malloc(size_t size) {
  return sbrk(size);
}

void free(void *ptr) {
  /* Кого это волнует? */
}

/* Примечание: только для увеличения (да, я ленив) */
void *realloc(void *ptr, size_t size) {
  void *nptr = malloc(size);
  if (nptr == NULL) {
    return NULL;
  }
  // «old_size» должен быть известен :)
  // (например, запишите его в начало выделенного блока)
  memcpy(nptr, ptr, old_size);
  free(ptr);
  return nptr;
}

[Примечание. Как справедливо заметил один из читателей Hacker News, здесь нужно значение old_size, которое, например, можно было записать в начало блока после того, как блок был выделен. Но нет, мы не должны были освободить исходный блок в случае ошибок в работе realloc :)]

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

Чтобы понять, что происходит с большими блоками, нам придется поближе познакомиться с Glibc на Linux.

Знакомство с Glibc

Просто скачайте последнюю версию glibc и изучите дерево исходного кода.
Там есть один интересный каталог malloc. Найдите в нем файл malloc.c и откройте его в редакторе.

/*
  Основные свойства алгоритмов:
   * Это наиболее подходящий распределитель для больших запросов (>= 512 байт), связи обычно создаются с использованием FIFO (т. е. вытеснение по давности использования).
   * Для небольших запросов (<= 64 байт по умолчанию) это кэширующий распределитель, который управляет пулами интенсивно используемых блоков.
   * Что касается средних блоков, а также комбинаций из больших и маленьких блоков, делается все возможное для максимально эффективной работы и с теми, и с другими.
   * Для очень больших запросов (>= 128 Кб по умолчанию) используются системные средства сопоставления памяти, если они поддерживаются.

    Более подробная, хотя и слегка устаревшая, информация по этому поводу: http://gee.cs.oswego.edu/dl/html/malloc.html 
*/

Нас больше всего интересует вот эта часть: «Для очень больших запросов (>= 128 Кб по умолчанию) используются системные средства сопоставления памяти, если они поддерживаются».

Порог в 128 Кб настраивается функцией mallopt():

M_MMAP_THRESHOLD
          Если свободной памяти недостаточно, то для блоков, превышающих или равных лимиту (в байтах), установленному для M_MMAP_THRESHOLD, функции выделения памяти используют mmap(2), вместо того чтобы увеличивать размер сегмента данных с помощью sbrk(2).

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

В сущности, это означает, что:

• malloc будет реализована с использованием mmap;
• free будет реализована с использованием munmap;
• realloc будет реализована с использованием mremap (Что?! Такого в POSIX еще нет? Серьезно?)

Ладно, давайте чуть-чуть расширим свои познания о mremap.

Итак, что мы знаем о man mremap:

mremap() использует схему таблиц страничной адресации Linux. mremap() изменяет отображение виртуальных адресов на страницы памяти. Таким образом, можно реализовать очень эффективный realloc(3).

Ага, очень эффективный realloc. Насколько эффективный?

Во-первых, mmap, munmap и mremap описаны в библиотеке glibc. На самом деле, только точки входа:

nm -D /lib/x86_64-linux-gnu/libc.so.6 | grep -E "(mmap|munmap|mremap)$"
00000000000e4350 W mmap
00000000000e9080 W mremap
00000000000e4380 W munmap

Обратите внимание на то, что точки входа по умолчанию — это в данном случае «слабые» символы. То есть они могут быть переопределены кем-то другим во время динамической компоновки. Например:

ldd /tmp/sample
        linux-vdso.so.1 (0x00007584a8aaa000)
        libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007584a86e6000)
        /lib64/ld-linux-x86-64.so.2 (0x00007584a8aac000

… символы могут быть переопределены библиотекой linux-vdso.so.1 — это волшебная библиотека, которая отображается во всех программах под Linux и позволяет ускорить некоторые вызовы, включая системные вызовы.
В любом случае наши символы в библиотеке glibc — это только каналы к вызовам ядра системы (syscall), будь то glibc или vdso (см. реализации по умолчанию: sysdeps/unix/sysv/linux/mmap64.c). Например:

void *
__mmap64 (void *addr, size_t len, int prot, int flags, int fd, off64_t offset)
{
  // проверка аргументов удалена
  void *result;
  result = (void *)
    INLINE_SYSCALL (mmap2, 6, addr,
                    len, prot, flags, fd,
                    (off_t) (offset >> page_shift));
  return result;
}

Итак, наш первоначальный вопрос уже связан не с glibc, а с ядром Linux.

Знакомство с ядром

Скачайте последнюю версию ядра, и давайте кратко рассмотрим принципы работы mremap.

Заглянув в руководство (The Linux Kernel Howto), вы найдете очень интересный каталог:

Каталог mm содержит весь необходимый код для работы с памятью. Код управления памятью, специфичный для конкретной архитектуры, размещается в каталогах вида arch/*/mm/, например arch/i386/mm/fault.c.

Отлично. Они-то нам и нужны!
Вот интересный файл: mm/mremap.c. В нем вы найдете точку входа для системного вызова функции mremap. Вот здесь:

/*  
* Увеличить (или уменьшить) существующее отображение, возможно, одновременно переместив его 
* (с учетом значения флага MREMAP_MAYMOVE и доступного пространства VM) 
*
* Опция MREMAP_FIXED добавлена 5 декабря 1999 г. Бенджамином Лахейзом (Benjamin LaHaise) 
* Эта опция подразумевает использование MREMAP_MAYMOVE.  
*/ 
SYSCALL_DEFINE5(mremap, unsigned long, addr, unsigned long, old_len,
                unsigned long, new_len, unsigned long, flags,
                unsigned long, new_addr)
{

Именно здесь мы входим в ядро при выполнении соответствующего системного вызова в пользовательском коде (через glibc или соответствующий канал vdso).

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

Затем ядро попытается расширить отображенную область путем ее увеличения (то же самое делал бы распределитель в библиотеке C при помощи sbrk). В случае успешного расширения функция возвращает результат.

Все эти тривиальные случаи реализованы со сложностью O(1) (даже если учитывать затраты на вход в ядро — они будут меньше, поскольку прерывания больше не используются, но все равно будут).

А что в наихудшем случае?

        /*
         * Мы не могли просто расширить или уменьшить область
         * нам пришлось создать новую и затем переместить.         
         */
        ret = -ENOMEM;
        if (flags & MREMAP_MAYMOVE) {
                unsigned long map_flags = 0;
                if (vma->vm_flags & VM_MAYSHARE)
                        map_flags |= MAP_SHARED;

                new_addr = get_unmapped_area(vma->vm_file, 0, new_len,
                                        vma->vm_pgoff +
                                        ((addr - vma->vm_start) >> PAGE_SHIFT),
                                        map_flags);
                if (new_addr & ~PAGE_MASK) {
                        ret = new_addr;
                        goto out;
                }

                map_flags = vma->vm_flags;
                ret = move_vma(vma, addr, old_len, new_len, new_addr);
                if (!(ret & ~PAGE_MASK)) {
                        track_exec_limit(current->mm, addr, addr + old_len, 0UL);
                        track_exec_limit(current->mm, new_addr, new_addr + new_len, map_flags);
                }
        }

На первый взгляд, ядро делает то же самое, что делаем мы в своем простом распределителе:

• выделяет новую область;
• копирует исходную область в новую, а затем освобождает ее (т. е. выполняется операция перемещения).

Но давайте посмотрим повнимательнее.

Вот вызов move_vma:

static unsigned long move_vma(struct vm_area_struct *vma,
                unsigned long old_addr, unsigned long old_len,
                unsigned long new_len, unsigned long new_addr)
{
...
        new_pgoff = vma->vm_pgoff + ((old_addr - vma->vm_start) >> PAGE_SHIFT);
        new_vma = copy_vma(&vma, new_addr, new_len, new_pgoff,
                           &need_rmap_locks);
        if (!new_vma)
                return -ENOMEM;

        moved_len = move_page_tables(vma, old_addr, new_vma, new_addr, old_len,
                                     need_rmap_locks);

Здесь есть два интересных вызова:

• copy_vma;
• move_page_tables.

Функция copy_vma описана в файле mm/mmap.c; она перемещает структуру типа vm_area_struct — это внутренняя структура ядра, описывающая блок памяти.

Определение можно найти здесь: include/linux/mm_types.h. Эта небольшая структура содержит всю информацию об области: начальный и конечный адрес, файл на диске (если область памяти используется для отображения файла) и т. д.

Итак, эта операция перемещения достаточно проста — O(1).

А что делает функция move_page_tables?

Самое интересное, похоже, вот в этом цикле:

...
        for (; old_addr < old_end; old_addr += extent, new_addr += extent) {
...
                move_ptes(vma, old_pmd, old_addr, old_addr + extent,
                          new_vma, new_pmd, new_addr, need_rmap_locks);
...

Этот код несколько сложноват (кроме того, нет комментариев), но в основном это базовые арифметические операции и расчеты.

Функция move_ptes содержит внутренний цикл самого нижнего уровня:

...
        for (; old_addr < old_end; old_pte++, old_addr += PAGE_SIZE,
                                   new_pte++, new_addr += PAGE_SIZE) {
                if (pte_none(*old_pte))
                        continue;
                pte = ptep_get_and_clear(mm, old_addr, old_pte);
                pte = move_pte(pte, new_vma->vm_page_prot, old_addr, new_addr);

...
                set_pte_at(mm, new_addr, new_pte, pte);
        }
...

Так что же в этом цикле происходит?! Мы просто перемещаем строки таблицы страниц (PTE, Page Table Entries), соответствующие области памяти, в другое место. По сути, это целые числа, назначенные каждой странице.

Итак, что мы имеем: фактически ядро не притрагивалось к данным из нашего сопоставленного блока; для перемещения всей области достаточно было поменять местами несколько битов.
Формально сложность по-прежнему O(N), но

• вместо копирования целых страниц по 4 Кб (или 2 Мб для очень больших страниц), мы меняем местами целые числа внутри структуры ядра;
• мы работаем с «горячей» памятью ядра, не притрагиваясь к «холодной» и тем более к данным, вытолкнутым в файл подкачки.

Поэтому мы используем O(N), но с огромным отличием.

Да, кстати, вы знаете, что O(N) во многих случаях сбивает с толку?

В нашем случае максимальным значением N является 2⁴⁸ (максимальный размер виртуального пространства). Большинство компьютеров работают лишь с несколькими гигабайтами памяти — не более 64 Гб для большинства архитектур (то есть 2³⁶ байт). Большая станица — это 2²¹ байт, максимальное число операций составляет 2¹⁵ для move_ptes (да, это всего лишь 32 768 операций).

Итак, в наихудшем случае затраты всегда крайне низкие, и я почему-то не сомневался в этом с самого начала.

Также рекомендую к прочтению: книгу Understanding the Linux Virtual Memory Manager Мела Гормана (Mel Gorman).

«Ниасилил многабукаф»? Не парьтесь. Лень и realloc — наше все.

Автор: ABBYYTeam

Источник