7. Heap

В прошлый раз, я споткнулся именно на этой статье. Уже подготовив перевод, я обнаружил некоторые ошибки в описании алгоритма и, пытаясь их исправить, полностью его переписал. Мой алгоритм в большей степени основан на алгоритме аллокатора Doug Lea, который используется (или когда-то использовался) в GNU libc. Поэтому, данная статья не является переводом оригинального цикла и алгоритм, представленный здесь отличается от алгоритма JamesM. Итак...

---

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

Как Вы наверное знаете, для динамического выделения памяти используется особая структура данных, часто называемая Heap (куча, хип). Тем не менее, не существует универсального алгоритма для выделения/освобождения памяти в хипе. На практике выбирают наиболее подходящий алгоритм, отвечающий требованиям производительности и сложности. Мы поставим перед собой задачу реализовать такой алгоритм, который будет:

• Понятным;
• Близким по духу к реально используемым алгоритмам;
• Простым (относительно) в отладке;

На последнем пункте хотелось бы остановиться особо. Лично я отлаживал алгоритм не в ядре, а в клиентском приложении, заменив вызовы функций для выделения новых страниц памяти на вызовы к malloc/free из libc. Однако вы можете воспользоваться встроенными возможностями Qemu/Bochs для отладки вашего ядра. Итак, приступим.

7.1. Описание структур данных 

В основе алгоритма лежит концепция блока памяти (chunk), который состоит из заголовка (header), тела (body) и послесловия (footer) (Термины не являются общеупотребительными и определены только в рамках данной статьи). Блок может находиться в одном из двух состояний: используемый в данный момент (allocated) и пустой (свободный, freed). В начале работы вся доступная область памяти представляет собой один непрерывный пустой chunk. Для блока определен минимальный размер - 16 байт. Максимальный размер ограничен только объемом доступной памяти (в реальных системах объем доступной памяти определяется при помощи так называемой карты памяти, которую можно запросить у BIOS). Таким образом блок в любой момент времени выравнен по размеру слова. Каждому свободному блоку соответствует дескриптор в связанном списке. Дескрипторы в списке отсортированы по возрастанию размера блока.
Заголовок блока содержит размер блока в байтах. Размер всегда кратен 8, поэтому младшие три бита зарезервированы под флаги, отражающие состояние блока.
PINUSE_BIT
      Если установлен, значит предыдущий блок в состоянии allocated.

CINUSE_BIT
      Если установлен, значит текущий блок в состоянии allocated.

RESERV_BIT
      Зарезервирован для будущих версий. Не используется.

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

7.2. Описание алгоритма

7.2.1. Allocation

Как уже говорилось, выделение памяти производится "блоками". Минимальный и максимальный размер блока ограничен.

1. Для запрошенного размера size рассчитываем размер блока bsize. Ищем в списке блок не меньший bsize. Так как список уже отсортирован, то это тривиальная задача;
• Если блок такого размера отсутствует в списке, тогда расширяем хип;
• Если в списке нет пустых блоков - тогда добавляем в него новый пустой блок;
• Иначе, меняем значение size в заголовке последнего пустого блока и перезаписываем послесловие;
• Рекурсивно вызываем функцию alloc в надежде на то, что теперь-то она найдет блок нужного размера.
2. Определяем не надо ли разделить блок на две части. В большинстве случаев мы будем делить блок на две и более частей, одна из которых потом будет помечена как используемая и возвращена из функции, а остальные добавлены в список в качестве новых пустых блоков;
3. Если блок должен начинаться с новой страницы, тогда мы должны изменить адрес начала нового используемого блока и создать новый пустой блок в неиспользуемой области памяти;
4. Записать заголовок и послесловие для нового блока;
5. Вернуть адрес начала тела блока.

7.2.2. Deallocation

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

int a = kmalloc(8); // Allocate 8 bytes: returns 0xC0080000 for sake of argument
int b = kmalloc(8); // Allocate another 8 bytes: returns 0xC0080008.
kfree(a);           // Release a
kfree(b);           // Release b
int c = kmalloc(16);// What will this allocation return? 

В данном примере мы дважды запрашиваем 8 байт. Затем мы освобождаем эту память. Если бы мы просто отметили блоки как пустые, то в связанном списке у нас хранились бы два дескриптора, которые указывают на два пустых блока по 8 байт каждый. При следующем выделении памяти (16 байт) ни один из этих блоков не будет соответствовать запрашиваемому размеру.

Лучшим решением было бы превратить два подряд идущих пустых блока в один. Это работает следующим образом: мы проверяем PINUSE_BIT, который хранит состояние блока, который находится "левее" текущего. Если этот флаг сброшен, значит "левее" освобождаемого блока находится еще один пустой блок. Далее, мы проверяем послесловие этого пустого блока и, зная, что там хранится размер, рассчитываем адрес соответствующего заголовка. Далее, мы выполняем необходимые проверки, и объединяем два блока в один, изменяя соответствующие поля в заголовке и в послесловии.

Аналогично, мы проверяем блок, расположенный непосредственно после текущего блока, и если это свободный блок, то объединяем его с текущим. Вносим этот новый пустой блок в список и все.

Отдельно отметим, что если мы освобождаем блок, который находится последним в хипе (после этого блока нет больше других блоков), то мы можем сократить размер хипа. Чтобы нам не приходилось регулярно расширять-сокращать размер хипа, мы зададим для него минимальный размер.

Алгоритм:

1. Найти адрес блока, воспользовавшись специальной функцией mem2chunk();
2. Выполнить проверку CINUSE_BIT;
3. Проверить значение PINUSE_BIT;
4. Если перед освобождаемым блоком находится пустой блок - производим объединение;
5. Если после освобождаемого блока находится пустой блок - производим объединение;
6. Если блок последний в хипе - сокращаем размер хипа;
7. Добавляем дескриптор блока в список.  

7.3. Двунаправленный связный список

Переходим к имплементации. Как обычно, я постараюсь сначала рассмотреть и объяснить вспомогательные функции, затем перейдем непосредственно к функциям для работы с хипом.

Первая структура данных, которая нам понадобится - это двунаправленный связный список. Эта структура данных будет часто использоваться в ядре, так что не плохо было бы вынести функции для работы с ней в отдельный модуль.

Мы не будем изобретать велосипед, а используем аналог двусвязного списка, который используется в ядре Linux. На мой взгляд это одна из лучших имплементаций этой структуры данных на С и было бы просто глупо ею не воспользоваться. Я только покажу интерфейс этой структуры, а более подробное описание и примеры использования можно найти здесь.

7.3.1. llist.h

#ifndef __LIST_H
#define __LIST_H
/* This file is from Linux Kernel (include/linux/list.h)
* and modified by simply removing hardware prefetching of list items.
* Here by copyright, credits attributed to where ever they belong.
*/
/*
* Simple doubly linked list implementation.
*
* Some of the internal functions ("__xxx") are useful when
* manipulating whole lists rather than single entries, as
* sometimes we already know the next/prev entries and we can
* generate better code by using them directly rather than
* using the generic single-entry routines.
*/
struct list_head {
    struct list_head *next, *prev;
};
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)
#define INIT_LIST_HEAD(ptr) do { \
    (ptr)->next = (ptr); (ptr)->prev = (ptr); \
    } while (0)
/*
* Insert a new entry between two known consecutive entries.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
static inline void __list_add(struct list_head *new,
                              struct list_head *prev,
                              struct list_head *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}
/**
* list_add - add a new entry
* @new: new entry to be added
* @head: list head to add it after
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/
static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}
/**
* list_add_tail - add a new entry
* @new: new entry to be added
* @head: list head to add it before
*
* Insert a new entry before the specified head.
* This is useful for implementing queues.
*/
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}
/**
* Delete a list entry by making the prev/next entries
* point to each other.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
static inline void __list_del(struct list_head *prev, struct list_head *next)
{
    next->prev = prev;
    prev->next = next;
}
/**
* list_del - deletes entry from list.
* @entry: the element to delete from the list.
* Note: list_empty on entry does not return true after this, the entry is in an undefined state.
*/
static inline void __list_del_entry(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
}
static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = (void *) 0;
    entry->prev = (void *) 0;
}
/**
* list_del_init - deletes entry from list and reinitialize it.
* @entry: the element to delete from the list.
*/
static inline void list_del_init(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    INIT_LIST_HEAD(entry);
}
/**
* list_move - delete from one list and add as another's head
* @list: the entry to move
* @head: the head that will precede our entry
*/
static inline void list_move(struct list_head *list, struct list_head *head)
{
    __list_del(list->prev, list->next);
    list_add(list, head);
}
/**
* list_move_tail - delete from one list and add as another's tail
* @list: the entry to move
* @head: the head that will follow our entry
*/
static inline void list_move_tail(struct list_head *list,
                                  struct list_head *head)
{
    __list_del(list->prev, list->next);
    list_add_tail(list, head);
}
/**
* list_empty - tests whether a list is empty
* @head: the list to test.
*/
static inline int list_empty(struct list_head *head)
{
    return head->next == head;
}
/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*/
#define list_entry(ptr, type, member) \
    ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
/**
* list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop counter.
* @head: the head for your list.
*/
#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); \
    pos = pos->next)
/**
* list_for_each_prev - iterate over a list backwards
* @pos: the &struct list_head to use as a loop counter.
* @head: the head for your list.
*/
#define list_for_each_prev(pos, head) \
    for (pos = (head)->prev; pos != (head); \
         pos = pos->prev)
/**
* list_for_each_safe - iterate over a list safe against removal of list entry
* @pos: the &struct list_head to use as a loop counter.
* @n: another &struct list_head to use as temporary storage
* @head: the head for your list.
*/
#define list_for_each_safe(pos, n, head) \
    for (pos = (head)->next, n = pos->next; pos != (head); \
         pos = n, n = \pos->next)
#endif // __LIST_H

Обратите особое внимание на макрос list_entry - в нем есть немного магии.

7.4. Heap

7.4.1. kheap.h 

Начнем с определения хипа и блока в нем:

#define KHEAP_START         0xC0000000
#define KHEAP_MIN_SIZE      0x100000
/**
 * @brief The heap struct
 * start_addr   The start of our allocated space
 * end_add      The end of our allocated space. May be expanded up to max_addr.
 * max_addr     The maximum address the heap can be expanded to.
 * supervisor   Should extra pages requested by us be mapped as supervisor-only?
 * readonly     Should extra pages requested by us be mapped as read-only?
 * head         The head of the list.
 */
typedef struct kernel_heap {
    size_t              start_addr;
    size_t              end_addr;
    size_t              max_addr;
    u8int               supervisor;
    u8int               readonly;
    struct list_head    head;
} heap_t;
/**
 * @brief The heap_chunk struct
 * prev_foot    The size of previous block if it is free
 * head         The header itself. Contains size + extra bits.
 * list         prev,next pointers. Set if block is free.
 */
typedef struct heap_chunk {
    size_t              prev_foot;
    size_t              head;
    struct list_head    list;
} hchunk_t;

Пусть наш хип располагается по адресу 0xC0000000, имеет минимальный размер 0x100000 байт. Вообще, в ядре может быть больше одного хипа (например один для user-space и один для kernel-space), но здесь мы не будем рассматривать такой случай. heap_t хранит в себе адрес начала хипа, текущий и максимальный размер, модификаторы, с которыми вызывается alloc_page при расширении хипа. Далее, мы определяем структуру для блока (heap_chunk). Тут есть одна хитрость: мы храним footer предыдущего блока в структуре заголовка для текущего блока. Соответственно, если предыдущий блок свободен, то там будет храниться его размер. В противном случае эти 4 байта также входят в область памяти, запрошенной пользователем и значение для них не определено.

Далее мы определяем интерфейс для работы с хипом:

/**
   Create a new heap.
**/
heap_t *create_heap(u32int placement_addr, u32int start, u32int end,
                    u32int max, u8int supervisor, u8int readonly);

/**
   Allocates a contiguous region of memory 'size' in size.
**/
void *alloc(size_t bytes, heap_t *heap);

/**
   Allocates a contiguous region of memory 'size' in size. it creates that block starting
   on a page boundary.
**/
void *paligned_alloc(size_t bytes, heap_t *heap);

/**
   Releases a block allocated with 'alloc'.
**/
void free(void *p, heap_t *heap);

Это просто декларация функций для работы с хипом. Они расширяют уже существующий интерфейс в kheap.h.

7.4.2. kheap.c

Начнем имплементировать работу с хипом с задания вспомогательных полезных констант и макросов:

#define SIZE_T_SIZE         (sizeof(size_t))
#define TWO_SIZE_T_SIZES    (SIZE_T_SIZE<<1)
#define SIZE_T_ZERO         ((size_t)0)
#define SIZE_T_ONE          ((size_t)1)
#define SIZE_T_TWO          ((size_t)2)
#define SIZE_T_FOUR         ((size_t)4)
#define PINUSE_BIT          (SIZE_T_ONE)
#define CINUSE_BIT          (SIZE_T_TWO)
#define RESERV_BIT          (SIZE_T_FOUR)
#define INUSE_BITS          (PINUSE_BIT|CINUSE_BIT)
#define FLAG_BITS           (INUSE_BITS|RESERV_BIT)
#define HCHUNK_SIZE         (sizeof(hchunk_t))
#define KMALLOC_ALIGNMENT   ((size_t)(2 * sizeof(void *)))
#define KMALLOC_ALIGN_MASK  (KMALLOC_ALIGNMENT - SIZE_T_ONE)
#define MIN_CHUNK_SIZE      ((HCHUNK_SIZE + KMALLOC_ALIGN_MASK) & ~KMALLOC_ALIGN_MASK)
#define CHUNK_OVERHEAD      (SIZE_T_SIZE)
#define MIN_REQUEST         (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE)
#define chunksize(ptr)      ((ptr)->head & ~(FLAG_BITS))
#define get_head(heap)      (&(heap)->head)
#define chunk2mem(ptr)      ((void*)((char*)(ptr) + TWO_SIZE_T_SIZES))
#define mem2chunk(ptr)      ((hchunk_t*)((char*)(ptr) - TWO_SIZE_T_SIZES))
#define pinuse(p)           ((p)->head & PINUSE_BIT)
#define cinuse(p)           ((p)->head & CINUSE_BIT)
#define ok_address(p, h)    (((size_t)(p) >= (h)->start_addr) && ((size_t)(p) < (h)->end_addr))
#define ok_inuse(p)         (((p)->head & INUSE_BITS) != PINUSE_BIT)
#define pad_request(req)    \
    (((req) + CHUNK_OVERHEAD + KMALLOC_ALIGN_MASK) & ~KMALLOC_ALIGN_MASK)
#define request2size(req)   (((req) < MIN_REQUEST) ? MIN_CHUNK_SIZE : pad_request(req))
#define chunk_plus_offset(p, s)     ((hchunk_t*)((char*)(p) + (s)))
#define chunk_minus_offset(p, s)    ((hchunk_t*)((char*)(p) - (s)))
#define set_pinuse(p)       ((p)->head |= PINUSE_BIT)
#define clear_pinuse(p)     ((p)->head &= ~PINUSE_BIT)
#define set_inuse(p,s) \
    ((p)->head = (((p)->head & PINUSE_BIT)|CINUSE_BIT|(s)), \
    (chunk_plus_offset(p, s))->head |= PINUSE_BIT)
#define set_size_and_pinuse(p, s) \
    ((p)->head = ((s)|PINUSE_BIT))
#define set_foot(p, s)      (chunk_plus_offset(p, s)->prev_foot = (s))

Здесь представлены основные константы, которые будут использоваться, а также ряд вспомогательных макросов для установки значений в поля структуры heap_chunk. Не будем сейчас подробно останавливаться на рассмотрении этих макросов - далее мы встретимся с каждым из них, и подробно рассмотрим какие функции каждый макрос выполняет.
Начнем рассмотрение алгоритма с вспомогательных функций. Одной из таких функций является find_smallest_chunk:

static hchunk_t *find_smallest_chunk(size_t bytes, heap_t* heap)
{
    hchunk_t * tmp = 0;
    struct list_head* iter;
    list_for_each(iter, get_head(heap)) {
        tmp = list_entry(iter, hchunk_t, list);
        if(chunksize(tmp) >= bytes)
        {
            break;
        }
    }
    if (iter == get_head(heap))
    {
        return 0;
    }
    return tmp;
}

Тут все просто. Поскольку наш список отсортирован в неубывающем порядке, мы просто пробегаемся по нему пока не найдем блок не меньший запрошенного размера. Здесь использован макрос chunksize() который принимает в качестве аргумента указатель на блок и возвращает его размер. Также здесь используется get_head(), который просто возвращает указатель на начало списка по указателю на heap_t.
Мы также должны определить функции для добавления блока в список и удаления блока из списка.

static void insert_chunk(hchunk_t *chunk, heap_t *heap)
{
    if(list_empty(get_head(heap)))
    {
        list_add_tail(&(chunk->list), get_head(heap));
    }
    else
    {
        struct list_head* iter;
        size_t csize = chunksize(chunk);
        list_for_each(iter, get_head(heap))
        {
            hchunk_t *tmp = list_entry(iter, hchunk_t, list);
            if(chunksize(tmp) >= csize)
            {
                break;
            }
        }
        list_add_tail(&(chunk->list), iter);
    }
}
#define remove_chunk(chunk)     __list_del_entry(&((chunk)->list))

При добавлении блока мы сравниваем его размер с размерами блоков в списке и добавляем его перед тем блоком, размер которого не меньше добавляемого. Таким образом мы поддерживаем список в упорядоченном состоянии, однако жертвуем временем работы алгоритма. Более оптимальным способом было бы использовать двоичное дерево, однако для простоты здесь используется линейная структура данных.
Создание хипа - это тривиальная задача. Тут все должно быть просто. Заметим только что при создании хипа мы также добавлем в него первый пустой блок, размер которого совпадает с размером хипа.

heap_t *create_heap(u32int placement_addr, u32int start,
                    u32int end, u32int max, u8int supervisor, u8int readonly)
{
    heap_t *heap = (heap_t *)placement_addr;

    // All our assumptions are made on start_addr and end_addr are page-aligned
    ASSERT(start % PAGE_SIZE == 0);
    ASSERT(end % PAGE_SIZE == 0);

    heap->start_addr = start;
    heap->end_addr = end;
    heap->max_addr = max;
    heap->supervisor = supervisor;
    heap->readonly = readonly;
    INIT_LIST_HEAD(get_head(heap));

    // Create first hole
    size_t hole_size = end - start;
    hchunk_t* hole = (hchunk_t*)start;
    hole->prev_foot = 0;
    set_size_and_pinuse(hole, hole_size);

    insert_chunk(hole, heap);

    return heap;
}

Обратите внимание что мы выставили флаг PINUSE_BIT для первого блока. В данном случае этот флаг будет сигнализировать нам что адреса "левее" данного блока нам недоступны.

7.4.2.1. Изменение размера хипа

Иногда нам потребуется менять размер хипа. Если у нас не останется свободного места, то нам потребуется запросить больше памяти. Если же количество свободного места очень велико - то мы вправе уменьшить размер хипа.

static void expand(size_t new_size, heap_t *heap)
{
    ASSERT(new_size > heap->end_addr - heap->start_addr);
    if(new_size % PAGE_SIZE)
    {
        new_size &= -PAGE_SIZE;
        new_size += PAGE_SIZE;
    }
    ASSERT(heap->start_addr + new_size <= heap->max_addr);
    size_t old_size = heap->end_addr - heap->start_addr;
    size_t i = old_size;
    while(i < new_size)
    {
        alloc_frame( get_page(heap->start_addr + i, 1, kernel_directory),
                     heap->supervisor, !heap->readonly);
        i += PAGE_SIZE;
    }
    heap->end_addr = heap->start_addr + new_size;
}

На мой взгляд приведенный код самодостаточен. В нем делаются некоторые проверки, затем мы изменяем значение параметра new_size (если это требуется) и запрашиваем необходимое количество страниц памяти, используя модификаторы.

static size_t contract(size_t new_size, heap_t *heap)
{
    ASSERT(new_size < heap->end_addr - heap->start_addr);
    if(new_size % PAGE_SIZE)
    {
        new_size &= -PAGE_SIZE;
        new_size += PAGE_SIZE;
    }
    if(new_size < KHEAP_MIN_SIZE)
        new_size = KHEAP_MIN_SIZE;
    size_t old_size = heap->end_addr - heap->start_addr;
    size_t i = old_size - PAGE_SIZE;
    while(i >= new_size)
    {
        free_frame(get_page(heap->start_addr + i, 0, kernel_directory));
        i -= PAGE_SIZE;
    }
    heap->end_addr = heap->start_addr + new_size;
    return new_size;
}

Аналогично тому как это было сделано в функции expand(), здесь мы по необходимости меняем значение параметра new_size, а затем проверяем не пытаемся ли мы освободить больше памяти чем положено. Затем просто возвращаем неиспользуемые страницы памяти обратно в ядро.

7.4.2.2. Allocation

Рассмотрим функцию выделения памяти по частям.

void *alloc(size_t bytes, heap_t *heap);
{
    size_t nb = request2size(bytes);
    hchunk_t *hole = find_smallest_chunk(nb, heap);
    if(hole == 0)
    {
        ... 
    }

Здесь мы посредством макроса request2size находим размер блока, соответствующий размеру выделяемой памяти bytes. Далее, мы ищем свободный блок, не меньший заданного размера. Если такой блок не найден - мы переходим к специальному обработчику. Код этого обработчика мы рассмотрим чуть позже.

    ASSERT( chunksize (hole) < nb);
    // Delete from list
    remove_chunk(hole);
    if(chunksize(hole) >= nb + MIN_CHUNK_SIZE) // We have to split the hole
    {
        // Calculate new hole size
        size_t size = chunksize(hole) - nb;
        // Set header for new chunk
        hchunk_t *new = chunk_plus_offset(hole, nb);
        new->head = size;
        // Add new hole to list
        insert_chunk(new, heap);
    }
    else
    {
        nb = chunksize(hole);
    }

Далее, мы удаляем найденный блок из списка и проверяем его размер. Если он больше запрошенного размера + минимальный размер блока, тогда мы разделяем этот блок на два блока. Пустой блок добавляем обратно в список.

    // Set header
    set_inuse(hole, nb);
    // Return pointer to memory
    return chunk2mem(hole);
_Lassert:
    monitor_write("Kernel Memory Corrupt.");
    PANIC();
    return 0;

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

Вот и вся функция. Просто, не правда ли? Теперь отдельно рассмотрим случай, если размер запрашиваемой области памяти больше, чем размер самого большого пустого блока.

    if(hole == 0)
    {
        // If we didn't find suitable hole
        // then expand the heap
        size_t old_size = heap->end_addr - heap->start_addr;
        size_t old_end_addr = heap->end_addr;
        expand(old_size + nb, heap);
        size_t new_size = heap->end_addr - heap->start_addr;
        // Find endmost header. (Not endmost in size, but in location).
        struct list_head *tmp = 0;
        if(!list_empty(get_head(heap)))
        {
            struct list_head *iter;
            list_for_each(iter, get_head(heap))
            {
                if(iter > tmp)
                {
                    tmp = iter;
                }
            }
        }
        hchunk_t *topchunk = 0;
        size_t csize = 0;
        if(tmp)
        {
            // Found the endmost free chunk. Check whether we should expand 

            // it or not.
            topchunk = list_entry(tmp, hchunk_t, list);
            if(!pinuse(topchunk) && cinuse(topchunk))
            {
                goto _Lassert;
            }
            size_t old_csize = chunksize(topchunk);
            if((size_t)chunk_plus_offset(topchunk, old_csize) != old_end_addr)
            {
                topchunk = 0;
            }
            else
            {
                remove_chunk(topchunk);
                csize = heap->end_addr - (size_t)topchunk;
            }
        }
        if(topchunk == 0)
        {
            // We haven't found free chunk - add one at the end.
            topchunk = (hchunk_t *)old_end_addr;
            csize = heap->end_addr - old_end_addr;
        }
        set_size_and_pinuse(topchunk, csize);
        insert_chunk(topchunk, heap);
        return alloc(bytes, heap);
    }

Этот обработчик довольно простой, хотя и объемный. Если мы не нашли пустой блок достаточного размера (hole == 0), тогда мы должны увеличить размер хипа (при помощи вызова expand()). Затем мы ищем последний пустой блок в наше хипе. Если находим, тогда увеличиваем его размер вместе с размером хипа и добавляем этот новый блок в список дескрипторов. Если не находим - то просто создаем новый пустой блок в добавленной памяти.

7.4.2.3. Освобождение памяти

Рассмотрим и эту функцию по частям.

void free(void *ptr, heap_t *heap)
{
    // Standard check if zero pointer passed
    if(ptr == 0)
        return ;
    // Check whether our heap contains ptr
    if(!ok_address(ptr, heap))
    {
        goto _Lassert;
    }
    // Find corresponding chunk
    hchunk_t *block = mem2chunk(ptr);
    // Check inuse flag
    if(!ok_inuse(block))
    {
        goto _Lassert;
    }
    size_t size = chunksize(block);

Начинаем со стандартных проверок: не передан ли нулевой указатель, является ли адрес, переданный в аргументе, указателем на выделенную область памяти. Затем находим указатель на заголовок соответствующего блока и его размер. Также мы проверяем что установлены сигнальные биты.

    // Check for previous chunk. If inuse bit not set,
    // then we can unify both free chunks
    if(!pinuse(block))
    {
        size_t prevsize = block->prev_foot;
        hchunk_t* prev = chunk_minus_offset(block, prevsize);
        if(!ok_address(prev, heap))
        {
            goto _Lassert;
        }
        size += prevsize;
        block = prev;
        // Remove chunk from ordered list
        remove_chunk(block);
    }

Здесь мы проверяем область памяти расположенную "левее" нашего блока. Если там находится еще один свободный блок, то мы их объединяем. Выяснить, находится ли "левее" нас свободный блок, мы можем посредством проверки служебного флага PINUSE.

    // Find addres of next chunk
    hchunk_t *next = chunk_plus_offset(block, size);
    if(ok_address(next, heap))
    {
        if(!pinuse(next))
        {
            goto _Lassert2;
        }
        // check whether next chunk is inuse or not
        if(cinuse(next))
        {
            // Clear PINUSE bit
            clear_pinuse(next);
        }
        else
        {
            size_t nextsize = chunksize(next);
            if((size_t)chunk_plus_offset(next, nextsize) > heap->end_addr)
            {
                goto _Lassert2;
            }
            // Remove next hole from the list
            remove_chunk(next);
            // And unify it with ours
            size += nextsize;
        }
    }

Этот участок кода тоже не должен вызвать затруднений. Здесь мы находим адрес следующего за нашим блока. Проверяем что он также является пустым блоком, и если это так, тогда объединяем его с нашим блоком.

    // If current block is the endmost one - we can contract
    if((size_t)chunk_plus_offset(block, size) == heap->end_addr)
    {
        size_t old_size = heap->end_addr - heap->start_addr;
        size_t new_size = (size_t)block - heap->start_addr;
        // Check header corruption
        if(new_size % PAGE_SIZE)
        {
            new_size += MIN_CHUNK_SIZE;
        }
        new_size = contract(new_size, heap);
        if(size > old_size - new_size)
        {
            // We are still exist, so resize chunk
            size -= old_size - new_size;
        }
        else
        {
            // We are no longer exist.
            size = 0;
            block = 0;
        }
    }
    else
    {
        // We should set footer for non-endmost chunk
        set_foot(block, size);
    }

Здесь мы проверяем является ли освобождаемый блок последним в хипе, и если это так, тогда пробуем уменьшить размер хипа. В противном случае просто перезаписываем послесловие.
При уменьшении размера хипа возможны два случая: если размер хипа уменьшается таким образом, что наш блок перестанет существовать (ветка 'else' во внутреннем условии), тогда мы должны сбросить значения адреса и размера удаляемого блока; однако может статься и так, что блок наш просто уменьшится в размерах - тогда просто учитываем это в переменной size.

    if(block && size)
    {
        // Add new free chunk to list
        set_size_and_pinuse(block, size);
        insert_chunk(block, heap);
    }
    return ;
_Lassert2:
    insert_chunk(block, heap);
_Lassert:
    monitor_write("Kernel Memory Corrupt.");
    PANIC();
}

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

7.4.2.4. paging.c

extern heap_t *kheap;

Добавляем декларацию переменной kheap, которая определена в файле kheap.c.

    /**
      * Map some pages in the kernel heap area.
      * Here we call get_page but not alloc_frame. This causes page_table_t's
      * to be created where necessary. We can't allocate frames yet because they need
      * to be identity mapped first below, and yet we can't increase placement_addres
      * between identity mapping and enabling the heap.
      */
    int i = 0;
    for(i = KHEAP_START; i < KHEAP_START + KHEAP_MIN_SIZE; i += PAGE_SIZE)
        get_page(i, 1, kernel_directory);

    // We should place heap_t structure before we turn paging on
    u32int kheap_addr = kmalloc(sizeof(heap_t));

Этот фрагмент добавляем в initialise_paging() перед тем как мы идентифицируем нашу таблицу от 0 до placement_addr. Поскольку наш хип начинается с адреса 0xC0000000, то для того чтобы записать что-то по этому адресу нам сначала необходимо создать несколько каталогов страниц. При создании этих каталогов изменится значение placement_addr, соответственно эти каталоги надо создать до цикла, который конформно отображает страницы памяти на адреса физической памяти (см. предыдущий урок). После такового отображения мы не должны изменять значение переменной placement_addr, чтобы не вызвать исключение Page Fault. Поэтому нам пришлось разделить функцию создания каталогов страниц и отображения этих страниц на адреса физической памяти.

    // Now allocate those pages we mapped earlier
    for(i = KHEAP_START; i < KHEAP_START + KHEAP_MIN_SIZE; i += PAGE_SIZE)
        alloc_frame( get_page(i, 0, kernel_directory), 0, 0 );

    // Before we enable paging, we must register our page fault handler
    register_interrupt_handler(14, page_fault);

    // Enable paging
    switch_page_directory(kernel_directory);

    // Initialise the kernel heap.
    kheap = create_heap(kheap_addr, KHEAP_START, 

            KHEAP_START + KHEAP_MIN_SIZE, 0xCFFFF000, 0, 0);

Теперь все. Осталось только дописать код в kmalloc/kfree с вызовом соответствующих alloc/free для случая когда kheap!=0:

    if(kheap)
    {
        void *addr;
        if(align)
        {
            addr = paligned_alloc(sz, kheap);
        }
        else
        {
            addr = alloc(sz, kheap);
        }

        if(phys != 0)
        {
            page_t *page = get_page((u32int)addr, 0, kernel_directory);
            *phys = page->frame*PAGE_SIZE + (((u32int)addr)& -PAGE_SIZE);
        }

        return (u32int)addr;
    }

7.5. Тестирование.

Проверяем как работают нашщи функции выделения/освобождения динамической памяти. Добавим в main.c следующий код:

    u32int a = kmalloc(8);
    initialise_paging();

    u32int b = kmalloc(8);
    u32int c = kmalloc(8);

    monitor_write("a: ");
    monitor_write_hex(a);

    monitor_write(", b: ");
    monitor_write_hex(b);

    monitor_write("\nc: ");
    monitor_write_hex(c);

    kfree(c);
    kfree(b);

    u32int d = kmalloc(12);
    monitor_write(", d: ");
    monitor_write_hex(d);

Здесь мы просто аллоцируем и освобождаем память и выводим на экран адреса, которые возвращаются нам при вызове функции kmalloc(). Если адрес переменной d равен адресу переменной b, значит наш механизм освобождения памяти работает. Вы можете самостоятельно поэкспериментировать с чередованием функций kmalloc/kfree. Кроме того, будет полезно посмотреть на то как работает механизм освобождения памяти с помощью отладчика.

В дальнейшем мы будем часто обращаться к созданным сегодня методам kmalloc/kfree, поскольку без механизма динамического выделения памяти было бы просто невозможно реализовать такие важные для любой ОС вещи, как многозадачность, очередь сообщений, файловую систему. Код, как обычно. уже на github.