Алгоритмы динамического управления памятью
/* Настроить все и запомнить, что у нас есть. */
/* 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 -1; heapinfo[block].busy.info.frag.first = i -1;
_chunks_free += (BLOCKSIZE >> log) -1;
_bytes_free += BLOCKSIZE -(1 << log); _bytes_used -= BLOCKSIZE -(1 << log);
} else
{