Трюки от Криса

Хакер, номер #093, стр. 093-146-1

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

Дефрагментация кучи

При интенсивном использовании кучи может сложиться такая ситуация, когда свободная память есть, но выделить ее не удается. Почему? Представим себе, что мы имеем 100 Мбайт свободной памяти в непрерывном блоке. Выделяем 10 блоков по 10 Мбайт, а затем освобождаем их через один, после чего пытаемся выделить блок размеров в 20 Мбайт, но… это не получатся! Несмотря на то, что мы имеем 50 Мбайт свободной памяти, эта память раздроблена на множество мелких кусочков. Вот потому-то некоторые и рекомендуют перезагружать Windows хотя бы раз в месяц.

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

А давай попробуем написать собственный дефрагментатор кучи! Это возможно (и совсем не сложно), если только наша программа придерживается определенных соглашений. В частности: адресует все ячейки внутри выделенного блока _только_ через базовый указатель, который в свою очередь является указателем на указатель. Непонятно? Ничего, несколько наглядных листингов все объяснят.

Вот классический пример использования кучи, делающий дефрагментацию динамической памяти невозможной:

foo(char* p)

{

static char *b = p;

…

}

char *p, x; int n;

…

p = malloc(BLOCK_SIZE);

x = p+n;

foo(x);

Выделив блок памяти p, программа получает указатель x, ссылающийся на некоторую ячейку внутри блока и передает его функции foo, которая сохраняется в статической переменной b, что делает блок p совершенно неперемещаемым, поскольку переменная b жестко привязана к своей ячейке памяти и ничего не знает про какие-то там блоки.

А вот другой вариант той же самой программы:

volatile char **p; int n;

…

p = my_malloc(BLOCK_SIZE);

foo(p, n);

Этот пример уже поддерживает возможность дефргаментации динамической памяти в однопоточных программах. В чем разница? Теперь функция my_malloc возвращает не указатель на выделенный блок, а указатель на переменную, хранящую указатель на выделенный блок. Функции foo передается уже не эффективный адрес ячейки памяти, а указатель-на-указатель p и смещение нужной ячейки относительно начала блока. Функция foo (и все остальные функции) не могут, не имеют права, хранить эффективные адреса в статических переменных или передавать их кому-либо еще. Вместо этого они при каждом обращении к ячейке должны выполнять операцию (*p+n), причем перемененная p должна быть объявлена как volatile, что запретит компилятору помещать ее в регистр.

Теперь наш менеджер кучи (представляющий собой надстройку над malloc) может беспрепятственно двигать блоки, высвобождая непрерывные регионы требуемой длинны. Для обеспечения когерентности и взаимной непротиворечивости дефргаментация должна осуществляться внутри вызова my_malloc, да и то, только в однопоточных программах. С многопоточными этот трюк не сработает, поскольку акт обращения к ячейкам памяти не является атомарным действием. Допустим, один поток вычислил эффективный адрес ячейки и только собрался к ней обратиться, как другой поток в это время передвинул блок на другое место! Следовательно, каждый поток должен иметь свою кучу, а передача данных от одного потока к другому обязана защищаться критическими секциями или другими средствами синхронизации.