- PVSM.RU - https://www.pvsm.ru -
После того, как вы прочитали базовые шаги по написанию Hello World ядра из цикла имеющихся на Хабре статей, самое время приступить к серьезной разработке самых базовых инструментов: аллокатора кучи и планировщика.
Честно говоря я долго думал стоит ли начинать писать статьи и делать видеоуроки на столь изьезженную тему. Но страсть к системному программированию и отсутствие структурированной информации на русском языке все же подтолкнули меня на этот эксперимент. Посему, если труд мой окажется востребованным, статьи планирую выпускать не реже чем раз в месяц и не чаще чем раз в неделю.
Свою ОС я мечтал написать еще в десятом классе. Книга Таненбаума обладает удивительным свойством. Всяк кто к ней прикоснется рано или поздно начинает мечтать написать свою операционную систему. Вот только я тогда ничего не написал, после того как понял что на мастдае невозможно нормально скомпилить и слинковать чистый бинарник с сишным кодом. Пришлось изучать Linux, поступать в универ, идти на работу. Все бы ничего. Да только мечта осуществилась лишь через десять лет. Сейчас, верстая скучные формочки на React, я оглядываюсь назад, вспоминаю, с какой страстью я просиживал часами за дизассемблером и отладчиком, снимал упаковщики, ломал крякмисы, на ночь вместо школьных романов зачитывался статьями мыщьха… и понимаю что моя жизнь могла бы сложиться иначе. Совсем иначе. Если бы только у меня был человек, который смог бы мне помочь в самом начале. Но время ушло. Программы ломать стало трудно. Ядро Linux разрослось до неимоверных размеров. Появились гиппервизоры. Ассемблер Intel стал настолько большим что взглянув на один список команд в мануале пропадает всякий энтузиазм что либо о нем изучать. Хлеб пришлось зарабатывать в вебе. Да. Мир системного программирования пережил свои золотые годы.
Посему всем школьникам, чей энтузиазм еще не иссяк, я посвящаю подробный туториал на тему как взять и с нуля написать простейшее многозадачное микроядро ядро со своей оболочкой. А всех, у кого он еще не появился, хочу предостеречь, что дело это неблагодарное и малополезное, хотя и жутко интересное. А у молодости, как вы знаете, свои заботы.
Поехали!
Данная статья содержит видеоурок [1] снятый в моей домашней студии. Он посвещен непосредственно коду.
Приступим к разработке менеджера кучи.
extern void *kmalloc(size_t size);
extern void kfree(void *addr);
Для написания аллокатора кучи нужно хранить регионы свободных и занятых адресов. Проще всего это реализовать в виде направленного списка. Саму же реализацию направленого списка придется делать через статический массив.
struct slist_head_t
{
struct slist_head_t *prev;
struct slist_head_t *next;
bool is_valid;
void *data;
} attribute(packed);
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 kheap_entry_t
{
struct slist_head_t list_head; /* static (array placed) list */
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
};
В начале структуры kheap_entry_t стоит slist_head_t что позволяет безболезненно приводить тип записи кучи к элементу списка.
Теперь рассмотрим простейший алгоритм аллокатора кучи (kmalloc):
Алгоритм освобождения памяти будет похож (kfree):
Следующая статья будет посвящена реализации алгоритма кучи.
Напишем простейший планировщик. Задача будет выглядеть так:
struct task_t
{
struct clist_head_t list_head; /* cyclic list */
u_short tid; /* task id */
struct gp_registers_t gp_registers; /* general purpose registers */
struct op_registers_t op_registers; /* other purpose registers */
struct flags_t flags; /* processor flags */
u_int time; /* time of task execution */
bool reschedule; /* whether task need to be rescheduled */
u_short status; /* task status */
int msg_count_in; /* count of incomming messages */
struct message_t msg_buff[TASK_MSG_BUFF_SIZE]; /* task message buffer */
void *kstack; /* kernel stack top */
void *ustack; /* user stack top */
} attribute(packed);
struct clist_definition_t task_list = {
.head = null,
.slot_size = sizeof(struct task_t)
};
Мы уже умеем выделять память и поэтому организуем задачи как кольцевой список. Так удобнее брать для выполнения следующую задачу относительно текущей с нужным статусом (мы будем использовать статус TASK_RUNNING если задача выполняется). Для начала будем предполагать что все задачи выполняются в кольце защиты ядра (так проще отлаживать планировщик) и обойдемся одним стеком. В будущем прикрутим TSS.
С задачами разобрались, теперь само планирование. Добавляем в IDT обработчик таймера и разрешаем прерывание нужной линии IRQ в PIC. По прерыванию таймера (и в конце кода инициализации ядра) передаем управление планировщику, передав из прерывания таймера адрес возврата и адрес предварительно сохраненных регистров:
/*
* Handle IRQ0
* void asm_ih_timer(unsigned long *addr)
*/
asm_ih_timer:
cli
pushal
mov %esp,%ebp
mov %ebp,%ebx
pushl %ebx # ®
add $32,%ebx
pushl %ebx # &ret addr
call ih_timer
mov %ebp,%esp
popal
sti
iretl
В планировщике проверяем выполнялась ли какая либо задача в этот момент. Если да увеличиваем счетчик времени ее выполнения и смотрим не превышает ли оно квоту. Если нет спокойно возвращаемся. Если превышает, нужно перепланировать задачу. Сохраняем ее состояние (пригодится адрес сохраненных регистров и адрес возврата сохраненный в стеке прерыванием таймера).
/* save task state */
current_task->op_registers.eip = *ret_addr;
current_task->op_registers.cs = *(u16 *)((size_t)ret_addr + 4);
*(u32 *)(¤t_task->flags) = *(u32 *)((size_t)ret_addr + 6) | 0x200;
current_task->op_registers.u_esp = (size_t)ret_addr + 12;
current_task->gp_registers.esp = current_task->op_registers.u_esp;
memcpy(¤t_task->gp_registers, (void *)reg_addr, sizeof(struct gp_registers_t));
Берем адрес стека новой задачи и формируем там фрейм возврата для команды iret. После чего вызываем ассемблерную функцию переключения контекста.
/* prepare context for the next task */
next_task->op_registers.u_esp -= 4;
*(u32 *)(next_task->op_registers.u_esp) = (*(u16 *)(&next_task->flags)) | 0x200;
next_task->op_registers.u_esp -= 4;
*(u32 *)(next_task->op_registers.u_esp) = next_task->op_registers.cs;
next_task->op_registers.u_esp -= 4;
*(u32 *)(next_task->op_registers.u_esp) = next_task->op_registers.eip;
next_task->gp_registers.esp = next_task->op_registers.u_esp;
next_task->op_registers.u_esp -= sizeof(struct gp_registers_t);
memcpy((void *)next_task->op_registers.u_esp, (void *)&next_task->gp_registers, sizeof(struct gp_registers_t));
/* update current task pointer */
current_task = next_task;
/* run next task */
asm_switch_context(next_task->op_registers.u_esp);
Само переключение контекста выглядит так:
#
# Switch context
# void asm_switch_context(u32 esp)
#
asm_switch_context:
mov 4(%esp),%ebp # ebp = esp
mov %ebp,%esp
popal
sti
iretl
Планировщик готов.
Код полностью смотри в видеоуроке [1], прилагаемом к статье. Там рассматривается не только планировщик но еще и процесс загрузки, компиляции, и настройки IDT для тех кто подзабыл:
Автор: arsboretskiy
Источник [2]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/planirovshhik/328032
Ссылки в тексте:
[1] видеоурок: https://www.youtube.com/watch?v=-Uk6k_3juW4&t=5s
[2] Источник: https://habr.com/ru/post/464857/?utm_source=habrahabr&utm_medium=rss&utm_campaign=464857
Нажмите здесь для печати.