Язык программирования Си. Издание 3-е, исправленное - Брайан Керниган

При возникновении запроса на память просматривается список свободных блоков, пока не обнаружится достаточно большой блок. Такой алгоритм называется "поиском первого подходящего" в отличие от алгоритма "поиска наилучшего подходящего", который ищет наименьший блок из числа удовлетворяющих запросу. Если размер блока в точности соответствует требованиям, то такой блок исключается из списка и отдается в пользование. Если размер блока больше, чем требуется, от него отрезается нужная часть - она отдается пользователю, а ненужная оставляется в списке свободных блоков. Если блока достаточного размера не оказалось, то у операционной системы запрашивается еще один большой кусок памяти, который присоединяется к списку свободных блоков.

Процедура освобождения сопряжена с прохождением по списку свободных блоков, поскольку нужно найти подходящее место для освобождаемого блока. Если подлежащий освобождению блок примыкает с какой-то стороны к одному из свободных блоков, то он объединяется с ним в один блок большего размера, чтобы по возможности уменьшить раздробленность (фрагментацию) памяти. Выполнение проверки, примыкают ли блоки друг к другу, не составляет труда, поскольку список свободных блоков всегда упорядочен по возрастанию адресов.

Существует проблема, о которой мы уже упоминали в главе 5, состоящая в том, что память, выдаваемая функцией malloc, должна быть соответствующим образом выровнена с учетом объектов, которые будут в ней храниться. Хотя машины и отличаются друг от друга, но для каждой из них существует тип, предъявляющий самые большие требования на выравнивание, и, если по некоему адресу допускается размещение объекта этого типа, то по нему можно разместить и объекты всех других типов. На некоторых машинах таким самым "требовательным" типом является double, на других это может быть int или long.

Свободный блок содержит указатель на следующий блок в списке, свой размер и собственно свободное пространство. Указатель и размер представляют собой управляющую информацию и образуют так называемый "заголовок". Чтобы упростить выравнивание, все блоки создаются кратными размеру заголовка, а заголовок соответствующим образом выравнивается. Этого можно достичь, сконструировав объединение, которое будет содержать соответствующую заголовку структуру и самый требовательный в отношении выравнивания тип. Для конкретности мы выбрали тип 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 дает подходящий в смысле выравнивания указатель). Операции приведения типов позволяют нам сделать явными преобразования типов и даже справиться с плохо спроектированным интерфейсом системы. Несмотря на то, что наши рассуждения касались распределения памяти, этот общий подход применим и в других ситуациях.