Таблица информационных записей
Таблица информационных записей о блоках. Размещается
через align/__free (не malloc/free). */
malloc_info *_heapinfo;
/* Количество информационных записей. */ static size_t heapsize;
/* Индекс поиска в информационной таблице. */ size_t _heapindex;
/* Ограничитель допустимых индексов в информационной таблице */ size_t _heaplimit;
#if 1 /* Adapted from Mike */
/* Счетчик больших блоков, размещенных для каждого из размеров
фрагментов. */
int _fragblocks[BLOCKLOG];
#endif
/* Списки свободных фрагментов по размерам.
*/ struct list _fraghead[BLOCKLOG];
/* Инструментальные переменные.
*/ size_t __chunks_used; size_t _bytes_used; size_t _chunks_free; size_t _bytes_free;
/* Имеем ли мы опыт? */
/* Are you experienced? */
int malloc initialized;
/* Выровненное размещение. */
static __ptr_t align __P ((size_t));
static __ptr_t
align (size)
size_t size; {
__ptr_t result;
unsigned long int adj;
[result = (*__morecore) (size);
adj = (unsigned long int) ((unsigned long int) ((char *) result -
(char *) NULL)) % BLOCKSIZE; lit (adj != 0)
{
adj = BLOCKSIZE - adj; (void) (*_morecore) (adj); result = (char *) result + adj;
}
return result;
/* Настроить все и запомнить, что у нас есть. */
/* Set everything up and remember that we have.
*/ static int initialize _ P ( (void) ) ; static int initialize ()
{ if ( malloc initialize hook)
(*__malloc_initialize_hook) ();
heaps ize = HEAP / BLOCKSIZE;
_heapinfo = (malloc_info *) align (heapsize * sizeof (malloc_info) ) ;
if (_heapinfo == NULL)
return 0;
memset (_heapinfo, 0, heapsize * sizeof (malloc_info) ) ; _heapinfo [0] . f ree. size = 0;
_heapinfo[0] .free. next = _heapinfo[0] . free.prev = 0; _heapindex = 0;
_heapbase = (char *) _heapinfo; __malloc_initialized = 1; return 1;
/* Получить выровненную память, инициализируя
или наращивая таблицу описателей кучи по мере необходимости. static _ ptr_t morecore _ P ( (size_t) ) ; static _ ptr_t ,Шогесоге (size)
size_t size;
_ ptr_t result;
malloc_info *newinfo, *oldinfo;
size_t newsize;
result = align (size) ; if (result == NULL) return NULL;
/* Проверить, нужно ли нам увеличить таблицу описателей. */ if ((size_t) BLOCK ((char *) result + size) > heapsize) I
newsize = heapsize;
while ( (size_t) BLOCK ((char *) result + size) > newsize)
newsize *= 2;
newinfo = (malloc_info *) align (newsize * sizeof (malloc_info) ) if (newinfo == NULL) {
(* _ morecore) (-size); return NULL; }
memset (newinfo, 0, newsize * sizeof (malloc_info) ) ; memcpy (newinfo, _heapinfo, heapsize * sizeof (malloc_info) ) ; oldinfo = _heapinfo;
newinfo[BLOCK (oldinfo) ] .busy. type = 0; newinfo [BLOCK (oldinfo) ] .busy. info. size
= BLOCKIFY (heapsize * sizeof (malloc_info) ) ; _heapinfo = newinfo; _free_internal (oldinfo) ; heapsize = newsize;
_heaplimit = BLOCK ((char *) result + size) ; return result; I
/* Выделить память из кучи. */ ptr t
Глава 4. Управление оперативнои
libcjnalloc (size) size_t size;
I
ptr_t result;
size t block, blocks, lastblocks, start; register size_t i; struct list *next;
/* Некоторые программы вызывают malloc (0) . Мы это допускаем. */
lif °
if (size == 0)
return NULL; #endif
if (! malloc initialized) if ( '.initialize () ) return NULL;
if ( _ malloc_hook != NULL)
return (*__malloc_hook) (size) ;
if (size < sizeof (struct list) ) size = sizeof (struct list) ;
/* Определить политику размещения на основании размера запроса. */ if (size <= BLOCKSIZE / 2) {
/* Маленькие запросы получают фрагмент блока.
Определяем двоичный логарифм размера фрагмента.
*/ register size_t log = 1; — size; while ( (size /= 2) != 0)
/* Просмотреть списки фрагментов на предмет свободного
фрагмента желаемого размера. */ next = _f raghead[ log] .next; if (next != NULL)
I
введение в операционные системы
/* Найдены свободные фрагменты этого размера.
Вытолкнуть фрагмент из списка фрагментов и вернуть его. Обновить счетчики блока nfree и first.
*/ result = ( _ ptr_t) next; next->prev->next = next->next; if (next->next != NULL)
next->next->prev = next->prev; block = BLOCK (result); if
( — _heapinf о [block] .busy. info. frag. nfree != 0)
_heapinfo [block] .busy. info. frag. first = (unsigned long int)
((unsigned long int) ((char *) next->next — (char *) NULL) % BLOCKSIZE) » log;
/* Обновить статистику. */
++_chunks_used;
_bytes_used += 1 « log;
--_chunks_f ree ;
_bytes_free -= 1 « log; t
else
/* Нет свободных фрагментов желаемого размера. Следует взять новый блок; поделить его на фрагменты и вернуть первый. */ result = _ libc_malloc (BLOCKSIZE) ; if (result == NULL)
return NULL; #if 1 /* Adapted from Mike */
++_fragblocks [log] ; #endif
/* Связать все фрагменты, кроме первого, в список свободных. */ for (i = 1; i < (size_t) (BLOCKSIZE » log); ++i) I
next = (struct list *) ((char *) result + (i « log)); next->next = _fraghead[log] .next; next->prev = &_fraghead[log] ; next->prev->next = next; if (next->next != NULL) next->next->prev = next;
}
/* Инициализировать счетчики nfree и first для этого блока. */ block = BLOCK (result); _heapinfо[block].busy.type = log;
_heapinfо[block].busy.info.frag.nfree = i — I; heapinfo[block].busy.info.frag.first = i — 1;
_chunks_free += (BLOCKSIZE » log) - 1;
_bytes_free += BLOCKSIZE - (1 « log); _bytes_used -= BLOCKSIZE - (1 « log);
} else
{
/* Большие запросы получают один или больше блоков.
Просмотреть список свободных циклически, начиная с точки, где мы были в последний раз. Если мы пройдем полный круг, не обнаружив достаточно большого блока, мы должны будем запросить еще память у системы. */
blocks = BLOCKIFY (size);
start = block = _heapindex;
while (_heapinfо[block].free.size < blocks)
block = _heapinfо[block].free.next; if (block == start)
/* Необходимо взять больше [памяти] у системы.
Проверить, не будет ли новая память продолжением последнего свободного блока; если это так, нам не надо будет запрашивать так много.
*/ block = _heapinfo[0].free.prev; lastblocks = _heapinfо[block].free.size; if (_heaplimit != 0 && block + lastblocks == _heaplimit &&
(*__morecore) (0) == ADDRESS (block + lastblocks) &&
(morecore ((blocks - lastblocks) * BLOCKSIZE)) != NULL)
tif 1
/* Adapted from Mike */ Л
Обратите внимание, что morecore() может изменить
и дудение в операционные системы
положение последнего блока, если она перемещает таблицу дескрипторов и старая копия таблицы сливается с последним блоком. */ block = _heapinfo[0].free.prev;
_heapinfо[block].free.size += blocks — lastblocks; #else
_heapinfо[block].free.size = blocks; tendif
_bytes_free += (blocks - lastblocks) * BLOCKSIZE; continue; }
result = raorecore (blocks * BLOCKSIZE); if (result == NULL)
return NULL; block = BLOCK (result);
_heapinfо[block].busy.type = 0; _heapinfo[block].busy.info.size = blocks;
++ chunks used;
_bytes_used += blocks * BLOCKSIZE; return result;
/* В этой точке мы [так или иначе] нашли подходящую запись в списке свободных. Понять, как удалить то, что нам нужно, из списка. */ result = ADDRESS (block); if (_heapinfо[block].free.size > blocks) {
/* Блок, который мы нашли, имеет небольшой остаток,
так что присоединить его задний конец к списку свободных. */ _heapinfо[block + blocks].free.size
= _heapinfo[block].free.size - blocks; _heapinfo[block + blocks].free.next
= _heapinfо[block].free.next; _heapinfo[block + blocks].free.prev
= _heapinfо[block].free.prev;
_heapinfo[_heapinfo[block].free.prev].free.next = _heapinfo[_heapinfo[block].free.next].free.prev
= _heapindex = block + blocks
else
I^H
/* Блок точно соответствует нашему запросу, поэтому
просто удалить его из списка. */ _heapinfo[_heapinfo[block] .free. next] .free.prev
= _heapinf о [block] . free.prev; _heapinfo[_heapinfo[block] .free.prev] .free. next
= _heapindex = _heapinf о [block] . free. next; — chunksf ree ;
_heapinf о [block] .busy. type = 0;
_heapinf о [block] .busy . info. size = blocks;
++_chunks_used;
_bytes_used += blocks * BLOCKSIZE;
_bytes_free -= blocks * BLOCKSIZE;
return result;
free. c:
/* Освободить блок памяти, выделенный "malloc1.
Copyright 1990, 1991, 1992 Free Software Foundation Написано в мае 1989 Mike Haertel.
GNU С Library является свободным программным обеспечением; вы можете перераспространять ее и/или модифицировать ее в соответствии с положениями GNU General Public License версии 2 или (по вашему выбору) любой более поздней версии.
Библиотека GNU С распространяется в надежде, что она будет полезна, но БЕЗ КАКИХ-ЛИБО ГАРАНТИЙ; даже без неявно предполагаемых гарантий
КОММЕРЧЕСКОЙ ЦЕННОСТИ или ПРИГОДНОСТИ для КОНКРЕТНОЙ ЦЕЛИ.
Подробнее см. GNU General Public License.
С автором можно связаться по электронной почте по адресу mike@ai.mit.edu, или Mike Haertel с/о Free Software Foundation. */
#ifndef _MALLOC_INTERNAL #define _MALLOC_INTERNAL tinclude <malloc.h> tendif
#ifdef __ELF_
tpragma weak free = __libc_free
#endif
/^Предоставляемая пользователем отладочная функция (hook) для 4free'. */ void (*__free_hook) __P ((__ptr_t __ptr));
/* Список блоков, вьщеленных memalign. */ struct alignlist *_aligned_blocks = NULL;
/* Вернуть память в кучу. Аналогична 'free' но не вызывает
__free_hook даже если он определен. */
void _free_internal (ptr)
__ptr_t ptr;
{
int type;
size_t block, blocks;
register size_t i;
struct list *prev, *next;
block = BLOCK (ptr);
type = _heapinfо[block].busy.type; switch (type) { case 0:
/* Собрать как можно больше статистики как можно раньше. */ — chunks used;
-I—----
_bytes_used -= heapinfo [block] .busy. info. size * BLOCKSIZE; bytes_free += heapinfo [block] .busy. info. size * BLOCKSIZE;
/* Найти свободный кластер, предшествующий этому в списке свободных .
Начать поиск с последнего блока, к которому было обращение. Это может быть преимуществом для программ, в которых выделение локальное. */ i = _heapindex; if (i > block)
while (i > block)
i = _heapinfo[i) . free.prev; else { do
i = __heapinfo[i] . free. next; while (i > 0 && i < block) ; i = _heapinfo [i] . free.prev; 1
/* Определить, как включить этот блок в список свободных. */
if (block == i + _heapinfo[i] . free. size) {
/* Слить этот блок с его предшественником. */ _heapinfo[i] .free. size += _heapinfo [block] .busy. info. size/block = i;
else
/* Действительно включить этот блок в список свободных. */
_heapinf о [block] . free. size = _heapinfo [block] .busy. info. size;
_heapinf о [block] .free. next = _heapinfo[i] . free. next;
_heapinf о [block] . free.prev = i;
_heapinfo[i] .free. next = block;
_heapinf о [_heapinfo [block] .free. next] .free.prev = block;
++chunksfree;
/* Теперь, поскольку блок включен, проверить, не можем ли мы
слить его с его последователем (исключая его последователя из списка и складывая размеры) . */
if (block + _heapinf о [block] . free. size == heapinfo [block] .free. next)
{ _heapinfo [block] .free. size
+= _heapinfo [_heapinfo [block] .free. next] . free. size; _heapinfo [block] .free. next
= _heapinfo[_heapinfo[block] .free. next] . free. next ; _heapinf о [_heapinfo[block] .free. next] .free. prev = block; — chunksf ree ;
/* Проверить, не можем ли мы вернуть память системе. */
blocks = _heapinf о [block] .free. size;
if (blocks >= FINAL_FREE_BLOCKS && block + blocks == _heaplimit
&& (*_morecore) (0) == ADDRESS (block + .blocks)) {
register size_t bytes = blocks * BLOCKSIZE; _heaplimit -= blocks;
(*__morecore) (-bytes); _heapinf о [_heapinf о [block] .free. prev] .free. next
= _heapinf о [block] . free. next; _heapinfo[_heapinfo[block] .free. next] .free. prev
= _heapinf о [block] . free. prev; block = _heapinf о [block] . free. prev; — _chunks_f ree ; _bytes_free -= bytes;
/* Установить следующий поиск, стартовать с этого блока. */
_heapindex = block; break;
default:
/* Собрать некоторую статистику. */
—_chunks_used; _bytes_used -= 1 « type; ++_chunks_free; bytes_free += 1 « type;
/* Получить адрес первого свободного фрагмента в этом блоке.
*/ prev = (struct list *) ((char *) ADDRESS (block) +
(_heapinfo[block].busy.info.frag.first « type));
#if 1 /* Adapted from Mike */
if (_heapinfо[block].busy.info.frag.nfree == (BLOCKSIZE » type) - 1
&& _fragblocks[type] > 1) #else
if (_heapinfо[block].busy.info.frag.nfree == (BLOCKSIZE » type) - 1)
#endif
lif 1 #endii
/* Если все фрагменты этого блока свободны, удалить их из списка фрагментов и освободить полный блок. */ /* Adapted from Mike */
— _f ragblocks [type] ;
next = prev;
for (i = 1; i < (size_t) (BLOCKSIZE » type)
next = next->next; prev->prev->next = next; if (next != NULL)
next->prev = prev->prev; _heapinf о [block] .busy. type = 0; _heapinf о [block] .busy . info. size = 1;
/* Следим за точностью статистики.
*/ ++_chunks_used; _bytes_used += BLOCKSIZE; _chunks_free -= BLOCKSIZE » type; _bytes_free -= BLOCKSIZE;
libc free (ADDRESS (block));
I
else if ( heapinfо[block].busy.info.frag.nfree != 0)
/* Если некоторые фрагменты этого блока свободны, включить этот фрагмент в список фрагментов после первого свободного фрагмента этого блока. */
next = (struct list *) ptr;
next->next = prev->next;
next->prev = prev;
prev->next = next;
if (next->next != NULL) next->next->prev = next;
++_heapinfо[block].busy.info.frag.nfree;
else
/* В этом блоке нет свободных фрагментов, поэтому включить этот фрагмент в список фрагментов и анонсировать, что это первый свободный фрагмент в этом блоке. */
prev = (struct list *) ptr;
_heapinfo [block] .busy. info. frag. nfree = 1;
_heapinfo [block] .busy. info. frag. first = (unsigned long int)
((unsigned long int) ((char *) ptr - (char *) NULL) % BLOCKSIZE » type) ; prev->next = _fraghead[type] .next; prev->prev = &_fraghead[type] ; prev->prev->next = prev; if (prev->next != NULL)
prev->next->prev = prev;
break;
/* Вернуть память в кучу. */ void
_ libc_free (ptr) _ ptr_t ptr; {
register struct alignlist *1;
if (ptr == NULL) return;
for (1 = _aligned_blocks; 1 != NULL; 1 = l->next) if (l->aligned == ptr)
{
l->aligned = NULL;
/* Пометить элемент списка как свободный. */
ptr = l->exact;
break;
if ( _ free_hook != NULL) (* _ free_hook) (ptr) ;
else
_free_internal (ptr) ;
#include <gnu-stabs . h>
#ifdef elf_alias
elf_alias (free, cfree) ;
#endif
К основным недостаткам этого алгоритма относится невозможность оценки времени поиска подходящего блока, что делает его неприемлемым для задач реального времени. Для этих задач требуется алгоритм, который способен за фиксированное (желательно, небольшое) время либо найти подходящий блок памяти, либо дать обоснованный ответ о том, что подходящего блока не существует.
Проще всего решить эту задачу, если нам требуются блоки нескольких фиксированных размеров (Рисунок 4.10). Мы объединяем блоки каждого размера в свой список. Если в списке блоков требуемого размера ничего нет, мы смотрим в список блоков большего размера. Если там что-то есть, мы разрезаем этот блок на части, одну отдаем запрашивающей программе, а вторую... Правда, если размеры требуемых блоков не кратны друг другу, что мы будем делать с остатком?
Для решения этой проблемы нам необходимо ввести какое-либо ограничение на размеры выделяемых блоков. Например, можно потребовать, чтобы эти размеры равнялись числам Фибоначчи (последовательность целых чисел, в которой Fi+1 = Fi + Fi-1. В этом случае, если нам нужно Fi байт, а в наличии есть только блок размера Fi+1, мы легко можем получить два блока — один требуемого размера, а другой — Fi-1, который тоже не пропадет. Да, любое ограничение на размер приведет к внутренней фрагментации, но так ли велика эта плата за гарантированное время поиска блока?
