Разработка монолитной Unix подобной OS — Куча (4)

В предыдущей статье мы с вами реализовали системный журнал ядра. Теперь пришло время реализовать менеджер динамической памяти.

Оглавление

1. Система сборки (make, gcc, gas). Первоначальная загрузка (multiboot). Запуск (qemu). Библиотека C (strcpy, memcpy, strext).
2. Библиотека C (sprintf, strcpy, strcmp, strtok, va_list ...). Сборка библиотеки в режиме ядра и в режиме пользовательского приложения.
3. Системный журнал ядра. Видеопамять. Вывод на терминал (kprintf, kpanic, kassert).
4. Динамическая память, куча (kmalloc, kfree).
5. Организация памяти и обработка прерываний (GDT, IDT, PIC, syscall). Исключения.
6. Виртуальная память (каталог страниц и таблица страниц).
7. Процесс. Планировщик. Многозадачность. Системные вызовы (kill, exit, ps).
8. Файловая система ядра (initrd), elf и его внутренности. Системные вызовы (exec).
9. Драйверы символьных устройств. Системные вызовы (ioctl, fopen, fread, fwrite). Библиотека C (fopen, fclose, fprintf, fscanf).
10. Оболочка как полноценная программа для ядра.
11. Пользовательский режим защиты (ring3). Сегмент состояния задачи (tss).

Динамическая память ядра. Куча

Интерфейс кучи ядра будет выглядеть так:

void *kmalloc(size_t size);
void kfree(void *addr);

Поскольку кучи еще нет то записи о занятых и свободных регионах памяти придется хранить
в массиве ограниченного размера. Чем меньше размерность, тем меньше емкость кучи на
мелких фрагментах. В Linux, например, многие структуры ядра хранятся в переиспользуемой
памяти которая не меняет размера при освобождении (slab). Но нам еще далеко до этого,
ведь разработка — процесс итеративный.

Любой элемент, который намерен быть элементом списка организованном через массив
обязан реализовать интерфейс.

struct slist_head_t
{
  struct slist_head_t *prev;
  struct slist_head_t *next;
  bool is_valid;
  void *data;
} attribute(packed);

В C нет интерфейсов, но они и не нужны. Мы просто приводим указатель любого обьекта к типу struct slist_head_t * если этот обьект физически выглядит так:

struct my_list_entry_t
{
  struct slist_head_t list_head;
  ...
}

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

struct slist_definition_t
{
  size_t base;
  u_int slots;
  size_t slot_size;
  struct slist_head_t *head;
  struct slist_head_t *tail;
};

Функции для оперирования списком будут выглядеть так:

struct slist_head_t *slist_insert_entry_after(struct slist_definition_t *list, struct slist_head_t *pos);
struct slist_head_t *slist_insert_entry_before(struct slist_definition_t *list, struct slist_head_t *pos);
void slist_delete_entry(struct slist_definition_t *list, struct slist_head_t *entry);

Алгоритм функции вставки:
Найти свободный слот в массиве.
Заполнить его новым элементом.
Скорректировать указатели логически (не физически) смежных элементов списка.
Пометить слот как занятый.
Скорректировать начало и конец списка.

Алгоритм функции удаления из списка:
Скорректировать указатели логически (не физически) смежных элементов списка.
Скорректировать начало и конец списка.
Пометить слот как свободный.

Динамическая память описывается списком с элементами следующего вида:

struct kheap_entry_t
{
    struct slist_head_t list_head; /* should be at first */
    size_t addr;                   /* physical address */
    size_t size;                   /* memory block size */
    bool is_buzy;                  /* whether block used */
} attribute(packed);

Массив, описывающий динамическую память из таких записей выглядит так:

struct kheap_entry_t kheap_blocks[KHEAP_MAX_ENTRIES];

Определение списка регионов памяти выглядит так:

struct slist_definition_t kheap_list = {
    .head = null,
    .tail = null,
    .slot_size = sizeof(struct kheap_entry_t),
    .slots = KHEAP_MAX_ENTRIES,
    .base = (size_t)kheap_blocks};

Итак, мы описали динамическую память. Вся память в пределах определенного диапазона
делится на блоки произвольного размера, каждый из которых может быть либо пустым,
либо занятым. При этом каждый блок описывается элементом массива с флагом is_valid = true,
который является элементом списка.

Теперь рассмотрим простейший алгоритм аллокатора кучи (kmalloc):
Если нет свободных блоков, выделяем новый блок нужного размера (но не более чем максимальный размер кучи).

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

/*
 * Api - Kernel memory alloc
 */
extern void* kmalloc(size_t size)
{
    struct kheap_entry_t* current_data = null;
    struct slist_head_t* current = null;
    struct slist_head_t* head = kheap_list.head;

    assert(size > 0);

    /* try to use free block */
    for (current = head; current != null; current = current->next) {
        current_data = (struct kheap_entry_t*)current->data;

        if (current_data->is_buzy) {
            continue;
        }

        /* check size is not enough */
        if (current_data->size < size) {
            /* try to ask contribution from free left sibling */
            if (current->prev != null) {
                /* left sibling has found */
                struct slist_head_t* sibling = current->prev;
                struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)sibling->data;
                /* check whether left sibling is free */
                if (!sibling_data->is_buzy) {
                    /* ask lack from left sibling */
                    size_t lack = size - current_data->size;
                    sibling_data->size -= lack;
                    current_data->addr -= lack;
                    current_data->size += lack;
                    assert(current_data->size == size);
                    /* whether left sibling is collapsed */
                    if (sibling_data->size == 0) {
                        slist_delete_entry(&kheap_list, sibling);
                    }
                    /* occupy block */
                    current_data->is_buzy = true;
                    assert(current_data->addr >= KHEAP_START_ADDR);
                    assert(current_data->addr < KHEAP_END_ADDR);
                    return (void*)current_data->addr; /* suitable block has found */
                }
            }
            /* try to extend borders */
            if (current->next == null) {
                size_t heap_end_addr = current_data->addr + current_data->size;
                size_t lack = size - current_data->size;
                /* check free memory size is enought */
                if (heap_end_addr + lack < KHEAP_END_ADDR) {
                    /* occupy block */
                    current_data->size += lack;
                    current_data->is_buzy = true;
                    assert(current_data->addr >= KHEAP_START_ADDR);
                    assert(current_data->addr < KHEAP_END_ADDR);
                    return (void*)current_data->addr; /* suitable block has found */
                }
            }
        } else {
            /* occupy block */
            current_data->is_buzy = true;
            size_t surplus = current_data->size - size;
            bool is_sibling_bizy = false;
            /* try to contribute free right sibling */
            if (current->next != null) {
                /* sibling has found */
                struct slist_head_t* sibling = current->next;
                struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)sibling->data;

                /* check whether sibling is free */
                is_sibling_bizy = sibling_data->is_buzy;
                if (!is_sibling_bizy) {
                    /* give surplus to right sibling */
                    current_data->size -= surplus;
                    sibling_data->addr -= surplus;
                    sibling_data->size += surplus;
                    assert(current_data->size == size);
                }
            }
            /* try to give surplus to new right sibling */
            if (current->next == null || is_sibling_bizy) {
                {
                    struct slist_head_t* new_sibling;
                    new_sibling = slist_insert_entry_after(&kheap_list, current);
                    struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)new_sibling->data;

                    if (new_sibling != null) {
                        /* give surplus to new right sibling */
                        assert((size_t)new_sibling == (size_t)sibling_data);
                        current_data->size -= surplus;
                        assert(current_data->size > 0);
                        sibling_data->is_buzy = false;
                        sibling_data->addr = current_data->addr + current_data->size;
                        sibling_data->size = surplus;
                    }
                }
            }
            assert(current_data->addr >= KHEAP_START_ADDR);
            assert(current_data->addr < KHEAP_END_ADDR);
            return (void*)current_data->addr; /* suitable block has found */
        }
    }

    /* try to alloc new block */
    size_t heap_end_addr = KHEAP_START_ADDR;
    /* calculate heap end address */
    if (kheap_list.tail) {
        current = kheap_list.tail;
        current_data = (struct kheap_entry_t*)current->data;
        heap_end_addr = current_data->addr + current_data->size;
    }
    /* check free memory size is enought */
    if (heap_end_addr + size >= KHEAP_END_ADDR) {
        abort("heap size exceeded\n");
    }
    /* allocate new heap memory block */
    struct slist_head_t* tail = kheap_list.tail;
    current = slist_insert_entry_after(&kheap_list, kheap_list.tail);
    current_data = (struct kheap_entry_t*)current->data;
    assert((size_t)current == (size_t)current_data);
    current_data->addr = heap_end_addr;
    current_data->size = size;
    current_data->is_buzy = true;
    assert(current->next == null);
    assert(current->prev == tail);
    assert(current_data->addr >= KHEAP_START_ADDR);
    assert(current_data->addr < KHEAP_END_ADDR);
    return (void*)current_data->addr;
}

Алгоритм освобождения памяти будет похож (kfree):
Найти блок адрес которого начинается с освобождаемого адреса. Проверить что он занят. Пометить как свободный.

Если справа или слева есть свободный сосед обьединитьс с ним в один блок.

/*
 * Api - Kernel memory free
 */
extern void kfree(void* addr)
{
    struct slist_head_t* current = null;
    struct kheap_entry_t* current_data = null;
    struct slist_head_t* head = kheap_list.head;

    for (current = head; current != null; current = current->next) {
        current_data = (struct kheap_entry_t*)current->data;
        if (current_data->addr == (size_t)addr && current_data->is_buzy) {
            struct slist_head_t* prev = current->prev;
            struct slist_head_t* next = current->next;
            struct kheap_entry_t* prev_data = prev != null ? (struct kheap_entry_t*)prev->data : null;
            struct kheap_entry_t* next_data = next != null ? (struct kheap_entry_t*)next->data : null;

            /* free block */
            current_data->is_buzy = false;
            /* try to merge with free left sibling */
            if (prev != null && !prev_data->is_buzy) {
                prev_data->size += current_data->size;
                slist_delete_entry(&kheap_list, (struct slist_head_t*)current);
            }
            /* try to merge with free right sibling */
            if (next != null && !next_data->is_buzy) {
                current_data->size += next_data->size;
                slist_delete_entry(&kheap_list, (struct slist_head_t*)next);
            }

            return;
        }
    }

    abort("invalid address to free\n", addr);
}

На этом все. До следующих встреч!

Ссылки

А теперь, открывай видеоурок
И смотри параллельно git репозиторий (тебе нужна ветка lesson4)

Список литературы

1. James Molloy. Roll your own toy UNIX-clone OS.
2. Зубков. Ассемблер для DOS, Windows, Unix
3. Калашников. Ассемблер — это просто!
4. Таненбаум. Операционные системы. Реализация и разработка.
5. Роберт Лав. Ядро Linux. Описание процесса разработки.