long.
typedef long Align; /* для выравнивания по границе long */
union header { /* заголовок блока: */
struct {
union header *ptr; /* след. блок в списке свободных */
unsigned size; /* размер этого блока */
} s;
Align x; /* принудительное выравнивание блока */
};
typedef union header Header;
Поле Align нигде не используется: оно необходимо только для того, чтобы каждый заголовок был выровнен по самому "худшему" варианту границы.
Затребованное число символов округляется в malloc до целого числа единиц памяти размером в заголовок (именно это число и записывается в поле size (размер) в заголовке); кроме того, в блок входит еще одна единица памяти - сам заголовок. Указатель, возвращаемый функцией malloc, указывает на свободное пространство, а не на заголовок. Со свободным пространством пользователь может делать что угодно, но, если он будет писать что-либо за его пределами, то, вероятно, список разрушится.
Поскольку память, управляемая функцией malloc, не обладает связностью, размеры блоков нельзя вычислить по указателям, и поэтому без поля, хранящего размер, нам не обойтись.
Для организации начала работы используется переменная base. Если freep есть NULL (как это бывает при первом обращении к malloc), создается "вырожденный" список свободного пространства; он содержит один блок нулевого размера с указателем на самого себя. Поиск свободного блока подходящего размера начинается с этого указателя (freep), т. е. с последнего найденного блока; такая стратегия помогает поддерживать список однородным. Если найденный блок окажется слишком большим, пользователю будет отдана его хвостовая часть; при этом потребуется только уточнить его размер в заголовке найденного свободного блока. В любом случае возвращаемый пользователю указатель является адресом свободного пространства, размещающегося в блоке непосредственно за заголовком.
static Header base; /* пустой список для нач. запуска */
static Header *freep = NULL; /* начало в списке своб. блоков */
/* malloc: универсальный распределитель памяти */
void *malloc(unsigned nbytes) {
Header *p, *prevp;
Header *morecore(unsigned);
unsigned nunits;
nunits = (nbytes + sizeof(Header) - 1) / sizeof (Header) + 1;
if ((prevp = freep) == NULL) { /* списка своб. памяти еще нет */
base.s.ptr = freep = prevp = &base;
base.s.size = 0;
}
for (p = prevp-›s.ptr; ; prevp = p, p = p-›s.ptr) {
if (p-›s.size ›= nunits) { /* достаточно большой */
if (p-›s.size == nunits) /* точно нужного размера */
prevp-›s.ptr = p-›s.ptr;
else { /* отрезаем хвостовую часть */
p-›s.size -= nunits;
p += p-›s.size;
p-›s.size = nunits;
}
freep = prevp;
return (void *)(p+1);
}
if (p == freep) /* прошли полный цикл по списку */
if ((p = morecore(nunits)) == NULL) return NULL; /* больше памяти нет */
}
}
Функция morecore получает память от операционной системы. Детали того, как это делается, могут не совпадать в различных системах. Так как запрос памяти у системы - сравнительно дорогая операция, мы бы не хотели для этого каждый раз обращаться к malloc. Поэтому используется функция morecore, которая запрашивает не менее NALLOC единиц памяти; этот больший кусок памяти будет "нарезаться" потом по мере надобности. После установки в поле размера соответствующего значения функция morecore вызывает функцию free и тем самым включает полученный кусок в список свободных областей памяти.
#define NALLOC 1024 /* миним. число единиц памяти для запроса */
/* morecore: запрашивает у системы дополнительную память */
static Header * morecore(unsigned nu)
{
char *cp, *sbrk(int);
Header *up;
if (nu < NALLOC)
nu = NALLOC;
cp = sbrk(nu * sizeof(Header));
if (cp == (char *) -1) /* больше памяти нет. */
return NULL;
up = (Header *) cp;
up->s.size = nu;
free((void *)(up+1));
return freep;
}
Системный вызов sbrk(n) в UNIXе возвращает указатель на n байт памяти или -1, если требуемого пространства не оказалось, хотя было бы лучше, если бы в последнем случае он возвращал NULL. Константу -1 необходимо привести к типу char *, чтобы ее можно было сравнить с возвращаемым значением. Это еще один пример того, как операция приведения типа делает функцию относительно независимой от конкретного представления указателей на различных машинах. Есть, однако, одна "некорректность", состоящая а том, что сравниваются указатели на различные блоки, выдаваемые функцией sbrk. Такое сравнение не гарантировано стандартом, который позволяет сравнивать указатели лишь в пределах одного и того же массива. Таким образом, эта версия malloc верна только на тех машинах, в которых допускается сравнение любых указателей.
В заключение рассмотрим функцию free. Она просматривает список свободной памяти, начиная с freep, чтобы подыскать место для вставляемого блока. Искомое место может оказаться или между блоками, или в начале списка, или в его конце. В любом случае, если подлежащий освобождению блок примыкает к соседнему блоку, он объединяется с ним в один блок. О чем еще осталось позаботиться, - так это о том, чтобы указатели указывали в нужные места и размеры блоков были правильными.
/* free: включает блок в список свободной памяти */
void free(void *ар) {
Header *bp, *p;
bp = (Header *)ap -1; /* указатель на заголовок блока */
for (p = freep; !(bp › p && bp s.ptr); p = p-›s.ptr)
if (p ›= p-›s.ptr && (bp › p || bp s.ptr)) break; /* освобождаем блок в начале или в конце */
if (bp + bp-›s.size - p-›s.ptr) { /* слить с верхним */
bp-›s.size += p-›s.ptr-›s.size; /* соседом */
bp-›s.ptr = p-›s.ptr-›s.ptr;
} else bp-›s.ptr = p-›s.ptr;
if (p + p-›s.size == bp) { /* слить с нижним соседом */
p-›s.size += bp-›s.size;
p-›s.ptr = bp-›s.ptr;
} else p-›s.ptr = bp;
freep = p;
}
Хотя выделение памяти по своей сути - машинно-зависимая проблема, с ней можно справиться, что и иллюстрирует приведенная программа, в которой машинная зависимость упрятана в очень маленькой ее части. Что касается проблемы выравнивания, то мы разрешили ее с помощью typedef и union (предполагается, что sbrk дает подходящий в смысле выравнивания указатель). Операции приведения типов позволяют нам сделать явными преобразования типов и даже справиться с плохо спроектированным интерфейсом системы. Несмотря на то, что наши рассуждения касались распределения памяти, этот общий подход применим и в других ситуациях.
Упражнение 8.6. Стандартная функция calloc(n, size) возвращает указатель на n элементов памяти размера size, заполненных нулями. Напишите свой вариант calloc, пользуясь функцией malloc или модифицируя последнюю.
Упражнение 8.7. Функция malloc допускает любой размер, никак не проверяя его на правдоподобие: free предполагает, что размер освобождаемого блока - правильный. Усовершенствуйте эти программы таким образом, чтобы они более тщательно контролировали ошибки.
Упражнение 8.8. Напишите программу bfree(p, n), освобождающую произвольный блок p, состоящий из n символов, путем включения его в список свободной памяти, поддерживаемый функциями malloc и free. C помощью bfree пользователь должен иметь возможность в любое время добавить в список свободной памяти статический или внешний массив.