После того, как вы прочитали базовые шаги по написанию Hello World ядра из цикла имеющихся на Хабре статей, самое время приступить к серьезной разработке самых базовых инструментов: аллокатора кучи и планировщика.
Честно говоря я долго думал стоит ли начинать писать статьи и делать видеоуроки на столь изьезженную тему. Но страсть к системному программированию и отсутствие структурированной информации на русском языке все же подтолкнули меня на этот эксперимент. Посему, если труд мой окажется востребованным, статьи планирую выпускать не реже чем раз в месяц и не чаще чем раз в неделю.
Свою ОС я мечтал написать еще в десятом классе. Книга Таненбаума обладает удивительным свойством. Всяк кто к ней прикоснется рано или поздно начинает мечтать написать свою операционную систему. Вот только я тогда ничего не написал, после того как понял что на мастдае невозможно нормально скомпилить и слинковать чистый бинарник с сишным кодом. Пришлось изучать Linux, поступать в универ, идти на работу. Все бы ничего. Да только мечта осуществилась лишь через десять лет. Сейчас, верстая скучные формочки на React, я оглядываюсь назад, вспоминаю, с какой страстью я просиживал часами за дизассемблером и отладчиком, снимал упаковщики, ломал крякмисы, на ночь вместо школьных романов зачитывался статьями мыщьха… и понимаю что моя жизнь могла бы сложиться иначе. Совсем иначе. Если бы только у меня был человек, который смог бы мне помочь в самом начале. Но время ушло. Программы ломать стало трудно. Ядро Linux разрослось до неимоверных размеров. Появились гиппервизоры. Ассемблер Intel стал настолько большим что взглянув на один список команд в мануале пропадает всякий энтузиазм что либо о нем изучать. Хлеб пришлось зарабатывать в вебе. Да. Мир системного программирования пережил свои золотые годы.
Посему всем школьникам, чей энтузиазм еще не иссяк, я посвящаю подробный туториал на тему как взять и с нуля написать простейшее многозадачное микроядро ядро со своей оболочкой. А всех, у кого он еще не появился, хочу предостеречь, что дело это неблагодарное и малополезное, хотя и жутко интересное. А у молодости, как вы знаете, свои заботы.
Поехали!
Данная статья содержит видеоурок снятый в моей домашней студии. Он посвещен непосредственно коду.
Приступим к разработке менеджера кучи.
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
Планировщик готов.
Код полностью смотри в видеоуроке, прилагаемом к статье. Там рассматривается не только планировщик но еще и процесс загрузки, компиляции, и настройки IDT для тех кто подзабыл:
Автор: arsboretskiy
