Эта статья обсуждалась на Hacker News.
В течение минувшего года я шлифовал мой подход к выделению регионов. Практика показывает, что это эффективный, простой и быстрый подход; обычно его используют в качестве средства для сборки мусора без издержек. В зависимости от того, что нам требуется, в аллокаторе может быть всего 7–25 строк кода — идеально для случаев, когда мы работаем без среды исполнения. Теперь, когда я окончательно сформулировал ключевые аспекты моего подхода, самое время их задокументировать и рассказать вам о том, что мне удалось выучить. Определённо, это не единственный возможный подход к выделению регионов. Я просто расскажу вам о приёмах, которые сам выработал для упрощения программ и искоренения ошибок.
Регион (арена) — это буфер памяти и смещение до этого буфера. Изначально это смещение равно нулю. Чтобы выделить объект, нужно взять указатель на него с заданным смещением, увеличить смещение на размер объекта, а затем вернуть указатель. Этим дело не ограничивается — например, нужно обеспечить выравнивание и доступность. До этого мы ещё дойдём. Объекты не высвобождаются каждый по отдельности. Напротив, сразу высвобождаются целые группы ранее выделенных объектов, и смещение откатывается к более раннему значению. Когда не предусмотрены собственные времена жизни для отдельных объектов, деструкторы писать также не требуется, а вашим программам не приходится прямо во время выполнения обходить структуры данных и убирать ненужные. Кроме того, больше можно не беспокоиться об утечках памяти.
Существует небольшая прослойка таких программ, для которых по определению требуется универсальный механизм выделения памяти — для решения задач, которые (как минимум, частично) не решаются путём простого линейного выделения. Это касается, в частности, сред выполнения, применяемых в большинстве языков программирования. Если вам нравится работать с регионами, старайтесь случайно не попасть в такую ситуацию, когда у вас чрезмерно гибкий API, и по его структуре вызывающая сторона может предположить, что под этим API расположен механизм универсального выделения памяти.
Итак, для затравки покажу пример выделения регионов в моём излюбленном стиле и сразу козырну многими аспектами моего подхода:
typedef struct {
uint8_t *data;
ptrdiff_t len;
} str;
typedef struct {
strlist *next;
str item;
} strlist;
typedef struct {
str head;
str tail;
} strpair;
// Определяется в другом месте
void towidechar(wchar_t *, ptrdiff_t, str);
str loadfile(wchar_t *, arena *);
strpair cut(str, uint8_t);
strlist *getlines(str path, arena *perm, arena scratch)
{
int max_path = 1<<15;
wchar_t *wpath = new(&scratch, wchar_t, max_path);
towidechar(wpath, max_path, path);
strpair pair = {0};
pair.tail = loadfile(wpath, perm);
strlist *head = 0;
strlist **tail = &head;
while (pair.tail.len) {
pair = cut(pair.tail, '\n');
*tail = new(perm, strlist, 1);
(*tail)->item = pair.head;
tail = &(*tail)->next;
}
return head;
}Обратите внимание на следующие детали: каждую из них мы позже обсудим более подробно:
getlinesпринимает два региона, «перманентный» и «черновой». Первый предназначен для объектов, которые мы будем возвращать вызывающей стороне. Второй нужен для временных объектов, жизнь которых заканчивается с возвратом функции. Их время жизни определяется в стеке, точно как у локальных переменных.Объекты явно не высвобождаются. Напротив, все выделения из чернового региона неявно высвобождаются после возврата. В эту операцию автоматически включаются и пути возврата ошибок.
Черновой регион возвращается методом копирования — речь идёт о копии «заголовка», а не региона памяти как такового. При выделении меняется лишь локальная копия, и в таком случае возврата она не переживёт. Такая семантика очевидна для вызывающей стороны, поэтому, скорее всего, на той стороне ничего не попутают.
Притом, что
wpathможно было бы сделать автоматической локальной переменной, для стека она относительно велика, поэтому выделяется в черновом регионе. В черновом регионе не составляет труда делать большие динамические выделения, такие, которые в стеке никогда не получились бы безопасными. Иными словами, это мыслимый вариант alloca! То же касается массивов переменной длины (VLA). Работая в черновом регионе, вы никогда и не подумаете воплотить ни одну из этих ужасных идей.Второй параметр, передаваемый new — это тип, то есть мы очевидно имеем дело с макросом. Как сейчас будет показано, здесь нет никакой сложной эквилибристики с макрокомандами, это просто удобный однострочник. Нет здесь и неявного приведения, а если тип окажется некорректным, то компилятор выдаст об этом диагностическое сообщение.
Несмотря на все операции выделения, здесь не применяется какой-нибудь единственный оператор
sizeof, а также не вычисляется размер. Дело в том, что вычисление размера — это серьёзный источник дефектов. Эта задача должна решаться при помощи специализированного кода.Если выделить память не удалось, то об этом никак не сообщается, в том числе не возвращается null. Если избавиться от этого бремени, то программы серьёзно упрощаются. Действительно, такие ошибки можно обрабатывать нелокально, на уровне региона.
Все выделения по умолчанию инициализируются со значением «ноль». Это способствует созданию более простых программ, не столь подверженных ошибкам. Если такой подход станет обходиться слишком дорого, то от него можно явно отказаться, не меняя значений по умолчанию.
См. также u-config.
Регион, подходящий для большинства случаев, может быть вот настолько прост:
typedef struct {
char *beg;
char *end;
} arena;
void *alloc(arena *a, ptrdiff_t size, ptrdiff_t align, ptrdiff_t count)
{
ptrdiff_t avail = a->end - a->beg;
ptrdiff_t padding = -(uintptr_t)a->beg & (align - 1);
if (count > (avail - padding)/size) {
abort(); // возможная политика на случай выхода за границы памяти
}
ptrdiff_t total = size * count;
char *p = a->beg + padding;
a->beg += padding + total;
return memset(p, 0, total);
}О, всего пара указателей! При выделении памяти все значения размера являются знаковыми, и так и должно быть. Беззнаковые значения размера исторически являются ещё одним распространённым источником дефектов — причём никакого выигрыша от беззнаковых значений мы не получаем. Кстати, вот вам домашнее задание. Поменяйте в alloc все ptrdiff_t на size_t, найдите дефекты, возникающие в результате, а затем исправьте их.
Параметр align в регионе позволяет обработать любые необычные варианты выравнивания. Оказывается, сделать это при помощи libc на удивление сложно. Поэтому оценить всю пользу предлагаемого решения можно только после того, как оно станет достаточно удобным.
Если вы ранее не встречались с uintptr_t в действии, то его функционал может показаться необычным. Чтобы выровнять beg, необходимо вычислить, на сколько байт нам потребуется продвинуть адрес (padding), пока линия выравнивания не разделит этот адрес на две равные части. Взяв align по модулю, можно вычислить, каков сдвиг в байтах с момента последнего выравнивания:
extra = addr % alignНевозможно производить числовые операции над таким адресом, поэтому в коде мы должны сперва преобразовать его в uintptr_t. Выравнивание всегда является степенью двух и, кстати, не может быть равно нулю, поэтому не беспокойтесь, что случайно разделите что-нибудь на ноль. Кроме того, это означает, что можно вычислить модуль, вычтя единицу и применив в качестве маски оператор И:
extra = addr & (align - 1)Но нам требуется знать, сколько байт остаётся до следующего выравнивания, а это обратная величина:
padding = -addr & (align - 1)Добавим сюда приведение uintptr_t – и получим код, находящийся в alloc.
Оператор if проверяет, достаточно ли у нас памяти, а одновременно также проверяет, нет ли переполнения при size*count. Если обе проверки провалены, то активируется политика, применяемая при выходе за границы памяти — то есть в данном случае вызывается abort. Настоятельно рекомендую, как минимум при тестировании, предусматривать хоть что-нибудь на месте abort на случай неудачного выделения памяти. Даже если вы думаете, что неудача исключена. Вполне возможно, что вы используете больше памяти, чем полагаете, поэтому при выходе за пределы памяти нужен явственный сигнал.
В качестве альтернативной политики попробуйте длинный переход к «обработчику». При работе с GCC и Clang такой приём даже не требует поддержки во время выполнения. В данном случае добавим к региону jmp_buf:
typedef struct {
char *beg;
char *end;
void **jmp_buf;
} arena;
void *alloc(...)
{
// ...
if (count > (avail - padding)/size) {
__builtin_longjmp(a->jmp_buf, 1);
}
// ...
}
bool example(..., arena scratch)
{
void *jmp_buf[5];
if (__builtin_setjmp(jmp_buf)) {
return 0;
}
scratch.jmp_buf = jmp_buf;
// ...
return 1;
}example возвращает вызывающей стороне отказ, если вся память окажется израсходована. При этом проверять отдельные операции выделения памяти не требуется и, благодаря неявному высвобождению регионов в черновике, очистка также не требуется. Если на вызываемой стороне, получающей черновой регион, не установлен собственный jmp_buf, то именно здесь и происходит возврат. В реальной программе, вероятно, следовало бы обернуть конструкцию setjmp в макрос.
Допустим, в некоторых случаях заполнение нулями окажется слишком дорогостоящим или избыточным. Добавим флаг, позволяющий отказаться от такого варианта:
void *alloc(..., int flags)
{
// ...
return flag&NOZERO ? p : memset(p, 0, total);
}Аналогично, в данном случае может наступать критический момент, в который мы удерживаем не память, а какой-то другой ресурс (блокировку, дескриптор файла), либо вы не хотите, чтобы неудачное выделение спровоцировало фатальные последствия. В любом случае, важно, чтобы не активировалась политика, которая применяется при выходе за границы памяти. Можно запросить «мягкий» отказ, поставив для этого специальный флаг, а затем выполнить обычную проверку на нулевой указатель:
void *alloc(..., int flags)
{
// ...
if (count > (avail - padding)/size) {
if (flags & SOFTFAIL) {
return 0;
}
abort();
}
// ...
}В большинстве нетривиальных программ, вероятно, будет стоять, как минимум один из этих флагов.
Кстати (если это не очевидно) выделять регион совсем не сложно:
arena newarena(ptrdiff_t cap)
{
arena a = {0};
a.beg = malloc(cap);
a.end = a.beg ? a.beg+cap : 0;
return a;
}Или же можно выделить память напрямую из операционной системы, например mmap, VirtualAlloc. Как правило, регион существует столько же, сколько и вся программа, поэтому о его высвобождении можете не беспокоиться. При работе с регионами также можно отключить любые механизмы, проверяющие утечки памяти).
Если вам потребуется несколько больше регионов, то всегда можно нарезать уже имеющиеся на более мелкие. В многопоточных приложениях каждый поток может обладать как минимум одним собственным (черновым) регионом.
Макрос new
Я показал alloc, но в программе найдётся всего несколько мест, где она должна будет вызываться напрямую. Чаще в таком случае применяется макрос, автоматически обрабатывающий детали. Мой макрос я назову new, но, конечно, если вы пишете на C++, то для этого макроса потребуется подобрать другое имя (make? PushStruct?):
#define new(a, t, n) (t *)alloc(a, sizeof(t), _Alignof(t), n)Такое приведение — это дополнительная проверка, совершаемая во время компиляции. В особенности она полезна для того, чтобы избегать ошибок, связанных с уровнями косвенности. Кроме того, так мы не позволяем напрямую использовать в обычном коде оператор sizeof, которым легко злоупотребить. Если решите добавить параметр flags, а данном типичном случае передайте здесь ноль. Не забывайте, что цель этого макроса — обеспечить простоту и надёжность при обычном выделении памяти.
Часто приходится выделять одиночные объекты, поэтому показатель count здесь будет равен 1. Если вам кажется, что это некрасиво, то можно сделать версию new с переменным количеством аргументов, где задаваемые по умолчанию значения заполняются автоматически. Отчасти именно поэтому я поставил count в самом конце!
#define new(...) newx(__VA_ARGS__,new4,new3,new2)(__VA_ARGS__)
#define newx(a,b,c,d,e,...) e
#define new2(a, t) (t *)alloc(a, sizeof(t), alignof(t), 1, 0)
#define new3(a, t, n) (t *)alloc(a, sizeof(t), alignof(t), n, 0)
#define new4(a, t, n, f) (t *)alloc(a, sizeof(t), alignof(t), n, f)Не так уж и просто, но в целом код получается более аккуратным:
thing *t = new(perm, thing);
thing *ts = new(perm, thing, 1000);
char *buf = new(perm, char, len, NOZERO);Отмечу: если sizeof следует избегать, то как быть с длинами массивов? Это часть проблемы! Едва и вам когда-нибудь понадобится размер массива; обычно требуется знать, сколько в нём элементов. Это касается и символьных (char) массивов. Поэтому давайте лучше определим макрос countof, который при помощи sizeof вычисляет как раз то значение, которое вам нужно. Я хотел бы иметь всю эту коллекцию:
#define sizeof(x) (ptrdiff_t)sizeof(x)
#define countof(a) (sizeof(a) / sizeof(*(a)))
#define lengthof(s) (countof(s) - 1)Да, можно преобразовать sizeof именно в такой макрос! Он не будет рекурсивно расширяться и в сухом остатке представляет собой оператор. countof, конечно же, также даёт не столь подверженное ошибкам знаковое значение счёта, поэтому пользователям не приходится возиться с size_t. lengthof статически производит строку заданной длины, завершаемую нулём.
char msg[] = "hello world";
write(fd, msg, lengthof(msg));
#define MSG "hello world"
write(fd, MSG, lengthof(MSG));Как улучшить alloc при помощи атрибутов
Как минимум, при работе с GCC и Clang, можно и далее улучшить alloc, сопроводив функцию тремя атрибутами:
__attribute((malloc, alloc_size(2, 4), alloc_align(3)))
void *alloc(...);malloc указывает, что не происходит совмещения имён между указателем, возвращённым alloc, и любым существующим объектом. Обеспечивает некоторые существенные оптимизации, в иных случаях недоступные. В основном эти оптимизации достигаются путём разрыва некоторых зависимостей, присущих циклам.
alloc_size отслеживает размер выделяемых регионов, что нужно для диагностики во время компиляции и контрольных утверждений во время выполнения (__builtin_object_size). Обычно для этого требуется ненулевой уровень оптимизации. Иными словами, вы будете время от времени получать предупреждения компилятора о том, что при обращении к объектам из данного региона фиксируется выход за границы, а при применении детектора неопределённого поведения (Undefined Behavior Sanitizer) проверка соблюдения границ будет выполняться прямо во время выполнения. Такой приём отлично дополняет фаззинг.
Теоретически, alloc_align также может обеспечить более качественную генерацию кода, но мне пока такого видеть не доводилось. Считайте этот вариант опциональным и низкоприоритетным. Здесь я упоминаю его только для полноты картины.
Размер и рост регионов
Насколько крупные регионы следует выделять? Ответ прост: в зависимости от того, сколько требуется для успешного завершения программы. Обычно нетронутая память в регионах обходится дёшево или вообще бесплатно. В большинстве программ здесь, пожалуй, следует задавать верхнее предельное значение, по превышении которого логично полагать, что что-то пошло не так. При помощи регионов такие случаи удаётся изящно обрабатывать, упрощать восстановление и продвигаться к бесперебойной эксплуатации.
Такой ответ удовлетворителен в большинстве случаев, но в нашем — недостаточен. Принято считать, что программа должна наращивать расход памяти по мере необходимости, но получать от операционной системы сигнал, если память расходуется слишком сильно. Правда, если вы сами когда-либо пробовали такой подход, то, возможно, замечали, что мейнстримовые операционные системы не слишком хорошо с ним справляются. Как правило, это приводит к нестабильности системы — пробуксовке, отказу драйверов. Может потребоваться перезагрузка.
Если вы всё равно намерены пойти таким путём, учтите, что на 64-битных хостах можно зарезервировать гигантское виртуальное адресное пространство и постепенно по мере необходимости фиксировать память. В Linux это означает, что придётся пойти на избыточную выдачу памяти, выделив при запуске системы максимально крупный регион, который будет зафиксирован по факту использования. Чтобы отменить фиксацию, воспользуйтесь MADV_FREE.\
В Windows при помощи VirtualAlloc можно обрабатывать резервирование и фиксацию по отдельности. Кроме смещения при выделении нужно предусмотреть смещение при фиксации. Затем нужно наращивать выделенный регион впереди от смещения, предусмотренного при выделении — по мере увеличения используемой памяти. Если вам доведётся вручную сбросить смещение, предусмотренное при выделении, то и фиксацию вы можете отменить или, как минимум, применить MEM_RESET. В какой-то момент фиксация может не удаться, из-за чего будет запущена политика, действующая при перерасходе памяти. Но сама система, вероятно, к этому моменту уже будет в плохом состоянии. Поэтому лучше воспользоваться abort, чтобы быстро всё высвободить.
Отмывание указателей (гнусная уловка)
Притом, что при выделении памяти вне региона не требуются специальные проверки ошибок, выделение региона как такового при запуске системы требует обработки ошибок. Было бы хорошо, если бы регион удавалось выделить вне.bss и передать эту работу загрузчику. Тогда как в принципе можно сделать большой глобальный массив char[], на который бы опирался ваш регион, это, строго говоря, не разрешается (строгое совмещение имён). «Чистый» регион.bss можно получить, немного поработав с ассемблерным кодом — .comm плюс ассемблер, чтобы перенести адрес в C, не привлекая для этого массив. Мне хотелось добиться более удобного и портируемого решения, и вот что у меня получилось:
arena getarena(void)
{
static char mem[1<<28];
arena r = {0};
r.beg = mem;
asm ("" : "+r"(r.beg)); // отмываем указатель
r.end = r.beg + countof(mem);
return r;
}Здесь asm принимает указатель и возвращает указатель ("+r"). Компилятору никак не «увидеть», что он на самом деле пуст, так что он возвращает тот же самый указатель. Регион будет подстрахован mem, но, отмывая адрес через asm, я открепляю указатель от той точки, в которой он возник. Теперь, на взгляд компилятора, это какой-то чужеродный указатель, предоставленный в ассемблере, а не указатель на mem. Никакая оптимизация не позволит избавиться от mem, так как здесь он представляет собой своеобразный чёрный ящик.
Думаю, это красивый фокус, пусть в реальных проектах он и неприменим.
Структуры данных, располагающие к работе с регионами
В моём первом примере я воспользовался связным списком для хранения строк. Эта структура данных отлично подходит и для работы с регионами. Реализовать связный список поверх региона можно всего в нескольких строках кода, и при этом не нужен никакой код, чтобы его «разрушать». Вот так просто.
Что насчёт ассоциативных массивов на основе регионов? Или динамических массивов на основе регионов? На каждый из этих случаев у меня есть быстрое и простое решение, но это уже история для следующей статьи!
