[Перевод] Трюки с виртуальной памятью
Я уже довольно давно хотел написать пост о работе с виртуальной памятью. И когда @jimsagevid в ответ на мой твит написал о ней, я понял, что время пришло.
Виртуальная память — очень интересная штука. Как программисты, мы прекрасно знаем, что она есть (по крайней мере, во всех современных процессорах и операционных системах), но часто забываем о ней. Возможно, из-за того, что в популярных языках программирования она не присутствует в явном виде. Хотя иногда и вспоминаем, когда наш софт начинает тормозить (а не падать) из-за нехватки физической оперативной памяти.
Но, оказывается, с помощью виртуальной памяти можно делать довольно интересные вещи.
Неприлично большой массив
Напомню, что у меня был пост, где я описывал проблему с большой таблицей, отображающей идентификаторы объектов в указатели. Также я хотел зафиксировать эту таблицу в памяти, чтобы писатели могли атомарно изменять указатели в ней, не мешая читателям. Это означает, что использование чего-то вроде std: vector было невозможным, так как его внутренние структуры изменяются при увеличении размера вектора.
Создать массив фиксированного размера очень просто:
objecto *objects[MAXOBJECTS]
Но какой размер массива следует использовать? Если выбрать большое значение, то зря потратим память. Сделать массив небольшим — нам его может не хватить. В упомянутом выше посте я использовал иерархический подход, но, как подсказал @jimsagevid, вместо этого можно использовать виртуальную память и избежать сложностей с иерархией таблиц.
При использовании механизмов виртуальной памяти мы сразу резервируем адресное пространство и никакой другой код не может выделить память в этом же диапазоне адресов. Фактическая физическая память не выделяется, пока мы не не обратимся к страницам.
Итак, в данной ситуации мы можем просто выбрать достаточно большое число для размера массива и виртуально выделить под него память. Например, 1 миллиард объектов:
#define MAXOBJECTS 1000000000ULL
objecto **objects = virtualalloc(MAXOBJECTS * sizeof(objecto ));Мы используем 8 ГБ адресного пространства и виртуальной памяти, но физической только столько, сколько нам действительно нужно для наших объектов. Очень простое решение, для которого потребовалась всего одна строчка кода.
Примечание — Я использую здесь условный virtualalloc() в качестве системного вызова для выделения виртуальной памяти, не зависящего от ОС. На самом деле в Windows вы бы вызвали VirtualAlloc (), а в Linux mmap ().
Еще одно примечание — Windows разделяет выделение виртуальной памяти на отдельные вызовы MEMRESERVE и MEMCOMMIT. MEMRESERVE резервирует адресное пространство, а MEMCOMMIT выделяет его в физической памяти. Но это не значит, что физическая память реально выделяется при вызове MEMCOMMIT, физическая память не выделяется, пока вы не обратитесь к страницам. MEMCOMMIT резервирует память в файле подкачки, а если вы попытаетесь выделить больше памяти, чем доступно в файле подкачки, то MEMCOMMIT завершится ошибкой. Поэтому в Windows вы, скорее всего, не будете использовать MEMCOMMIT для всей таблицы из моего примера (потому что у файла подкачки размер ограничен). Вместо этого лучше сначала использовать MEMRESERVE для всей таблицы, а затем MEMCOMMIT только для фактически используемого диапазона.
В отличие от этого, Linux допускает overcommit (чрезмерное выделение памяти). То есть вы можете выделить больше памяти, чем доступно в файле подкачки. По этой причине Linux не нуждается в отдельных операциях резервирования (reserve) и подтверждения (commit), что упрощает использование виртуальной памяти.
Есть ли проблема в резервировании виртуальной памяти для массива в 8 ГБ? Здесь два ограничения. Первое — это адресное пространство. В 64-битном приложении адресное пространство составляет 264. Это очень большое число, в котором можно разместить миллиарды массивов гигабайтного размера. Второе ограничение касается виртуальной памяти. Операционная система обычно не позволяет выделять все возможное адресное пространство. Например, в 64-битной Windows мы можем выделить только 256 ТБ виртуальной памяти. Тем не менее в этом объеме можно разместить 32 000 массивов по 8 ГБ каждый, так что пока мы не совсем сходим с ума, все будет в порядке.
Эту технику, вероятно, можно использовать без каких-либо проблем для любых глобальных или полуглобальных массивов в вашем приложении.
Вспомните об олдскульном способе писать игры на Си с использованием статических массивов:
uint32t numtanks;
tankt tanks[MAXTANKS];
uint32¨C11Cbullets;
bullet¨C12CBULLETS];
…Если вы пишете подобный код, то будьте уверены, что найдутся те, кто его будет критиковать, так как здесь есть ограничения на количество объектов. Выглядит забавно, но можно вместо использования std::vector просто избавиться от MAX¨C13C и выделить 1 ГБ виртуальной памяти для каждого из массивов:
#define GB 1000000000
uint32_t num_tanks;
tank_t *tanks = virtual_alloc(GB);
uint32_t num_bullets;
bullet_t *bullets = virtual_alloc(GB);Уникальные ID в рамках всего приложения
Многим игровым движкам требуются уникальные идентификаторы (ID) для идентификации объектов. Часто код выглядит примерно так:
uint64_t allocate_id(system_t *sys)
{
return sys->next_free_id++;
} Но с использованием виртуальной памяти можно сделать по другому. Вместо использования в качестве идентификаторов целых чисел будем использовать адреса, зарезервированные в виртуальной памяти. Это позволит нам создавать уникальные идентификаторы не только в текущей системе, но и глобально во всем приложении. А поскольку мы никогда не используем память, на которую указывают эти адреса, то физическая память не будет потребляться.
Это может выглядеть примерно так:
system_id_t *allocate_id(system_t *sys)
{
if (!sys->id_block || sys->id_block_used == PAGE_SIZE) {
sys->id_block = virtual_alloc(PAGE_SIZE);
sys->id_block_used = 0;
}
return (system_id_t *)(sys->id_block + sys->id_block_used++);
}
Обратите внимание, что, используя для идентификатора указатель на непрозрачную структуру (opaque struct), мы также получаем некоторую безопасность типа, которой у нас не было с uint64_t.
Обнаружение перезаписи памяти
Один из самых сложных багов для исправления — это случайная перезапись памяти, когда какой-то код пишет в участок памяти, в который он не должен писать. Когда позже какой-нибудь другой код попытается использовать эту память, то он прочитает там мусор и, скорее всего, упадет. Проблема здесь заключается в том, что хотя само по себе падение найти легко, но сложно определить, где изначально произошла неправильная запись, повредившая данные. К счастью, виртуальная память может помочь нам и здесь.
Чтобы понять как, давайте сначала обратим внимание на то, что термин «случайная перезапись памяти» на самом деле неправильный. Адресное пространство в основном пустое. При 64-битном адресном пространстве и размере приложения, скажем, 2 ГБ, адресное пространство пусто на 99,999999988%. Это означает, что если перезапись памяти действительно случайная, то, скорее всего, она попала бы в это пустое пространство, что привело бы к ошибке/нарушению доступа к странице. А это бы привело к падению приложения в момент некорректной записи, а не при невинном чтении, что бы значительно упростило поиск и исправление ошибки.
Но, конечно, обычно запись не бывает абсолютно случайной. Вместо этого она часто попадает в одну из двух категорий:
Запись в память, которая была освобождена.
Запись за пределами выделенной памяти для объекта.
В обоих случаях весьма вероятно, что запись действительно попадет в какой-то другой объект, а не в пустое место. В первом случае память, скорее всего, предназначалась для чего-то другого. А во втором запись, вероятно, попадет в соседний объект или заголовок блока распределения (allocation block header).
Мы можем сделать это более случайным, заменив стандартный системный аллокатор на end-of-page — аллокатор (аллокатор в конце страницы). Такой аллокатор размещает каждый объект в виртуальной памяти в собственном множестве страниц и выравнивает объект так, чтобы он располагался в конце блока памяти.
Это позволяет добиться двух вещей. Во-первых, когда мы освобождаем страницы, мы освобождаем их в виртуальной памяти. Это означает, что попытка записи на страницы после их освобождения приведет к нарушению прав доступа. Обратите внимание, что с обычным аллокатором памяти обычно этого не происходит — он сохраняет освобожденную память в своих списках свободных страниц, используя их для других распределений, а не возвращает ее в ОС.
Во-вторых, так как конец блока совпадает с концом страницы, запись за пределы конца блока также приведет к нарушению доступа. Другими словами, при таком подходе наши попытки «ошибочной» записи в память будут завершаться ошибкой в момент записи, что позволит нам легко обнаружить проблему.
Так как такой аллокатор округляет выделение памяти по размеру страницы, то для небольших данных будет тратиться лишняя память. Поэтому обычно я работаю со стандартным аллокатором, но если подозреваю, что происходит перезапись памяти, то переключаюсь на end-of-page — аллокатор. После устранения проблемы я переключаюсь обратно на стандартный аллокатор. Конечно, возможность переключения аллокатора должна быть заложена в архитектуру вашего проекта.
Написание end-of-page аллокатора совсем несложно. Вот как может выглядеть malloc:
void *eop_malloc(uint64_t size)
{
uint64_t pages = (size + PAGE_SIZE - 1) / PAGE_SIZE;
char *base = virtual_alloc(pages * PAGE_SIZE);
uint64_t offset = pages * PAGE_SIZE - size;
return base + offset;
}
Примечание — Здесь все еще остается вероятность порчи данных при записи. Например, после очистки страниц выделение памяти для новой страницы может произойти в том же диапазоне. Кроме того, есть вероятность, что другой набор страниц может быть расположен в памяти непосредственно после нашего, и в этом случае мы не обнаружим перезапись за пределами последней страницы.
Обе эти проблемы можно исправить. Для решения первой проблемы мы можем оставить страницы зарезервированными (reserved), но не подтвержденными (commited). Таким образом, физическая память освобождается и мы получим ошибки страниц, но адреса остаются зарезервированными и не смогут использоваться другими объектами. Для второй проблемы можно зарезервировать дополнительную страницу после наших страниц, но не подтверждать ее. Тогда никакой другой объект не сможет претендовать на эти адреса и запись в них все равно приведет к ошибке доступа (access violation). (Примечание: это работает только в Windows, где reserve и commit являются отдельными операциями.)
Однако на практике мне никогда не приходилось принимать эти дополнительные меры предосторожности. Для меня всегда было достаточно обычного end-of-page — аллокатора.
Непрерывное выделение памяти
В былые времена фрагментация памяти могла стать ночным кошмаром для программистов. Но и на современных машинах фрагментация памяти может стать большой проблемой при попытке реализации эффективных аллокаторов памяти.
Аллокатор памяти запрашивает у системы большие куски памяти и по запросу пользователя разбивает их на более мелкие фрагменты. Фрагментация памяти происходит, когда освобождается только часть из них, оставляя дыры в используемом блоке памяти.
Проблема здесь в том, что когда пользователь запрашивает большой объем памяти, то может оказаться, что ни в одной из «дыр» не будет достаточно места. Это означает, что мы должны выделить память из свободного блока в конце, увеличивая использование памяти. Другими словами, появляется много впустую потраченной памяти, которую мы не можем реально использовать. Раньше память была очень дорогим ресурсом. Сегодня это уже не совсем так, но мы по-прежнему не хотим тратить ее впустую.
Фрагментация памяти — это очень большая тема и мы посмотрим на нее только с точки зрения виртуальной памяти. Когда вы выделяете память из виртуальной памяти, проблемы с фрагментацией не будет.
Причина здесь в том, что при использовании виртуальной памяти каждая страница в адресном пространстве индивидуально отображается на страницу в физической памяти. Поэтому появление «дыр» в физической памяти при выделении и освобождении страниц не имеет значения, потому что эти «дыры» впоследствии можно использовать для выделения того, что нам кажется непрерывной памятью.
Здесь мы сначала выделяем красные страницы и освобождаем некоторые из них, оставляя дыры в адресном пространстве и физической памяти. Однако это не мешает нам выделить адресное пространство под фиолетовые страницы. Каждая фиолетовая страница может быть отображена на одну из страниц-дырок, которые образовались ранее, без необходимости выделения дополнительной физической памяти.
Обратите внимание, что в адресном пространстве у нас все еще остается фрагментация. Т.е. мы не можем выделить большой непрерывный блок памяти в адресном пространстве, где находятся красные страницы. Фрагментация адресного пространства, на самом деле, нас особо не беспокоит, потому что, как было сказано выше, обычно адресное пространство на 99.999999988% пустое. Так что у нас нет проблем с поиском смежных страниц в адресном пространстве. (Но в 32-битных системах это совсем другая история.)
Недостаток такого подхода по сравнению с обычным аллокатором заключается в том, что нам приходится округлять выделяемую память по размеру страницы, которая в современных системах обычно составляет 4 КБ. Это означает, что мы не используем всю доступную память — проблема, которая называется внутренней фрагментацией.
Есть несколько способов решения этой проблемы. Для объектов с неизменяемым размером можно использовать пул объектов — выделить страницу памяти и разместить там столько объектов, сколько поместится.
Размер динамически увеличивающегося буфера можно сделать соответствующим размеру страницы. Это простой, но интересный метод, о котором я очень редко слышу. Допустим, у вас есть массив объектов размером 300 байт. Обычно при необходимости размещения большего количества записей вы увеличиваете размер массива геометрически, например, удваивая. Таким образом, получается увеличение количества элементов с 16 до 32 до 64 и до 128 элементов. Геометрический рост важен, чтобы было меньше затрат на частое увеличение массива.
Однако 16×300 = 4800. При выделении виртуальной памяти вам придется округлить это до 8 КБ, тратя впустую почти целую страницу. Но это можно легко исправить. Вместо того чтобы концентрироваться на количестве элементов, мы просто увеличиваем размер буфера кратно размеру страницы: 4 КБ, 8 КБ, 16 КБ, 32 КБ, …, а затем помещаем туда столько элементов, сколько поместится в него (13, 27, 54, 109, …). Это по-прежнему геометрический рост, но теперь внутренняя фрагментация составляет в среднем всего 150 байт вместо 2 КБ.
Мне кажется странным то, что стандартные аллокаторы не используют преимуществ виртуальной памяти для борьбы с фрагментацией. Большинство аллокаторов, которые я видел, получают большие участки памяти из ОС, вместо того, чтобы работать со страницами виртуальной памяти.
Может получать от ОС большие участки памяти эффективнее? Здесь мои знания довольно поверхностны. Но я не думаю, что это так. Возможно, использование больших страниц будет более производительным, потому что будет меньше таблица страниц и эффективнее будет использоваться кэш TLB. Но, учитывая фиксированный размер страницы, я не думаю, что это имеет значение — один большой кусок виртуальной памяти у вас или много маленьких, — потому что разрешение адресов в любом случае выполняется страница-к-странице. И даже если вы выделяете большие непрерывные фрагменты памяти, в физической памяти они все-равно часто не будут непрерывными.
Возможно, появятся некоторые дополнительные затраты памяти ОС для отслеживания большого количества отдельных выделений памяти. Также время тратится на системные вызовы выделения и освобождения страниц. Может быть, в этом и есть причина. Или просто дело в том, что аллокаторы написаны для работы в различных средах — и в 32-битных системах и в системах с большими страницами — поэтому они не могут использовать преимуществ 64-битных систем и 4KБ страниц.
Кольцевой буфер
Об этом трюке я узнал из блога Фабиана Гизена (Fabian Giesen). Но, кажется, что это довольно давняя идея.
Кольцевой буфер — это очень полезная структура данных для ситуаций, когда данные передаются и принимаются с разной скоростью. Например, при чтении из сокета вы можете получать данные фрагментами, поэтому вам нужно их буферизовать до тех пор, пока вы не получите полный пакет.
Кольцевой буфер хранит данные в массиве фиксированного размера. Когда массив заполняется, запись в него начинается с начала массива.
Кроме массива нам нужны еще указатели на «читателя» и «писателя» , чтобы знать, в какое место в буфере данные пишутся, а где читаются. Для этого мне нравится использовать uint64t, указывая общее количество записанных и прочитанных данных, что-то вроде этого:
enum {BUFFER_SIZE = 8*1024};
struct ring_buffer_t {
uint8_t data[BUFFER_SIZE];
uint64_t read;
uint64_t written;
};Обратите внимание, что поскольку буфер начинает записываться сначала, мы не можем позволить указателю записи находиться слишком далеко от указателя чтения, иначе он начнет удалять данные, которые еще не прочитаны. По сути, BUFFER_SIZEуправляет тем, как далеко вперед может уйти указатель на запись. Если буфер заполнен, то указатель на запись должен остановиться и дождаться чтения. Если буфер пустой, то указатель на чтение должен остановиться и ждать записи данных.
Что неудобно в кольцевом буфере, так это то, что вам нужно специально обрабатывать переход в начало буфера. Если бы не это, то для записи в буфер можно использовать простой memcpy, но приходится обрабатывать достижение конца массива.
void write(ring_buffer_t *rb, uint8_t *p, uint64_t n)
{
uint64_t offset = rb->written % BUFFER_SIZE;
uint64_t space = BUFFER_SIZE - offset;
uint64_t first_write = n < space ? n : space;
memcpy(rb->data + offset, p, first_write);
memcpy(rb->data, p + first_write, n - first_write);
rb->written += n;
}Как бы это ни раздражало, но с чтением все еще хуже. Если бы не перезапись с начала, то для чтения вообще бы не потребовалось никакого копирования — мы могли просто использовать данные непосредственно из буфера. Но с перезаписью нам понадобятся два вызова memcpy() для перемещения данных в непрерывный блок памяти для дальнейшей обработки.
Как здесь может помочь виртуальная память? Мы можем использовать технику «огромного массива» и просто зарезервировать большой массив вместо кольцевого буфера и фиксировать (commit) страницы по мере продвижения указателя на запись, а по мере продвижения читателя отменять фиксацию (decommit). При этом нам даже не нужно будет задавать фиксированный размер массива — он просто может использовать столько памяти, сколько потребуется. Довольно красивое решение. Но учтите, что вам может понадобиться очень большой массив. Для буферизации сетевого потока 1 Гбит/с с аптаймом в течение года вам потребуется зарезервировать 4 ПБ (петабайта) памяти. К сожалению, как мы видели выше, 64-разрядная Windows ограничивает объем виртуальной памяти 256 ТБ. Кроме того, вызовы commit и decommit не бесплатны.
Но мы можем поступить и другим способом, воспользовавшись тем, что в одну физическую страницу может отображаться несколько виртуальных. Обычно это используется для совместного использования памяти разными процессами. Но можно использовать и в рамках одного процесса. Чтобы использовать этот подход для кольцевого буфера, создадим несколько страниц сразу после кольцевого буфера (ring buffer), указывающих на одну и ту же физическую память.
Как видите, при таком подходе о «перезаписи с начала» за нас заботится система виртуальной памяти. В адресном пространстве мы всегда можем найти непрерывную копию памяти для кольцевого буфера, даже в физической памяти не будет непрерывных участков. Функции чтения и записи становятся простыми:
void write(ring_buffer_t *rb, uint8_t *p, uint64_t n)
{
memcpy(rb->data + (rb->written % BUFFER_SIZE), p, n);
rb->written += n;
}
uint8_t *read(ring_buffer_t *rb, uint64_t n)
{
uint8_t *p = rb->data + (rb->read % BUFFER_SIZE);
rb->read += n;
return p;
}
Это намного лучше, но мы по-прежнему используем тот же объем физической памяти.
Обратите внимание, что настройка такой схемы размещения в памяти может быть немного запутанной. В Windows нужно создать отображение файлов в виртуальную память с помощью CreateFileMapping(). Да, даже если никакие файлы на диске не задействованы, все равно нужно использовать «отображение файла», потому что совместно виртуальная память используется именно так. Но поскольку файл на диске нам не нужен, то для дескриптора файла используется INVALID_HANDLE_VALUE, создающий отображение в файл подкачки. Затем мы используем MapViewOfFileEx(), чтобы настроить отображение на две области памяти. К сожалению, нет никакого способа гарантировать, что переданные области памяти будут доступны. Мы можем зарезервировать их, а затем освободить непосредственно перед вызовом MapViewOfFileEx(), но все равно остается промежуток времени, когда, если нам очень не повезет, кто-то другой может прийти и выделить что-то в этом пространстве адресов. Возможно, нам придется повторить попытку отображения несколько раз, прежде чем оно будет успешным. Но после этого мы можем использовать буфер, не беспокоясь ни о чем.
Если вы знаете какие-нибудь изящные трюки с виртуальной памятью, не упомянутые здесь, пишите мне в твиттере в @niklasfrykholm.
Дополнения про Linux
Выше я написал, что «Linux допускает overcommit (чрезмерное выделение памяти)». Но, как я недавно обнаружил, на самом деле это не совсем так, или, по крайней мере, это очень сильное упрощение.
По умолчанию Linux допускает «некоторый» избыточный commit (определяется эвристически). Потому что если вы отключите overcommit, то будете тратить много памяти зря, поскольку процессы выделяют фактически не используемую память. С другой стороны, если вы разрешите слишком большой overcommit, вы можете столкнуться с ситуацией, когда процесс успешно выделил память, но при попытке получить к ней доступ, он не сможет этого сделать, потому что у системы не будет физической памяти. Для предотвращения таких ситуаций приходит OOM killer и убивает некоторые процессы.
Вы можете настроить систему, чтобы разрешить неограниченный overcommit (vm.overcommit_memory = 1) или указать ограничение (vm.overcommit_memory = 2). См. https://www.kernel.org/doc/Documentation/vm/overcommit-accounting
Но как разработчик вы не можете рассчитывать на то, что этот параметр будет установлен на определенное значение на машине пользователя. Вы должны убедиться, что работа вашей программы не зависит от этого параметра.
Это можно реализовать так же, как в Windows: разделить операции резервирования (reserve) и подтверждения (commit). Резервирование памяти не зависит от параметра overcommit_memory.
По документации mmap() это не совсем очевидно, но виртуальную память в Linux можно зарезервировать через вызов mmap() с PROT_NONE. После этого commit зарезервированной памяти можно сделать, используя системный вызов mprotect().
Примечание — Использование MAP_NORESERVE вместо PROT_NONE не работает, когда overcommit_memory = 2, поскольку в этом случае флаг MAP_NORESERVE игнорируется. См. https://lwn.net/Articles/627557/
Перевод статьи подготовлен специально для будущих студентов курса «Программист С».
Также приглашаем всех желающих зарегистрироваться на открытый онлайн-вебинар: «ООП на C: пишем видеоплеер».
