Depois de ler as etapas básicas para escrever os kernels Hello World a partir da série de artigos disponíveis no Habré, é hora de começar o desenvolvimento sério das ferramentas mais básicas: alocador de heap e agendador.
Importante :
1. Esta série de lições para iniciantes. O objetivo é formar uma imagem holística do mundo. Durante muito tempo, tive a teoria de Tanenbaum em mente e não consegui conectá-la à prática. Para quem tem a mesma coisa - dedico este artigo.
2. O código é o mais simples e burro, mas o mais claro possível. Meu objetivo é fornecer um entendimento para que você possa escrever seu próprio kernel, muito mais interessante que isso.
3. Publicarei o repositório assim que o considerar pronto para uma ampla variedade. Escrevo uma pequena parte, depuro e filmo um tutorial em vídeo. Eu não tenho um produto acabado.
Sinceramente, pensei por um longo tempo se começaria a escrever artigos e a criar tutoriais em vídeo sobre um tópico tão deposto. Mas a paixão pela programação do sistema e a falta de informações estruturadas em russo me levaram a esse experimento. Portanto, se meu trabalho estiver em demanda, pretendo publicar artigos pelo menos uma vez por mês e não mais que uma vez por semana.
Eu sonhava em escrever meu sistema operacional na décima série. O livro de Tanenbaum tem uma propriedade incrível. Quem toca mais cedo ou mais tarde começa a sonhar em escrever seu próprio sistema operacional. Mas não escrevi nada, depois que percebi que era impossível compilar e vincular um binário limpo a um código em um dia de mast. Eu tive que estudar Linux, ir para a universidade, trabalhar. Tudo não seria nada. Sim, apenas um sonho se tornou realidade apenas dez anos depois. Agora, inventando moldes chatos no React, olho para trás, lembro da paixão com que passei horas pelo desmontador e depurador, removi os empacotadores, quebrou as caixas de crack, li muitos artigos de romances escolares à noite ... e entendo que minha vida poderia ter sido diferente. Bem diferente. Se ao menos eu tivesse uma pessoa que pudesse me ajudar desde o início. Mas o tempo acabou. Programas tornaram-se difíceis de interromper. O kernel do Linux cresceu para tamanhos incríveis. Apareceram hipervisores. O montador da Intel tornou-se tão grande que, olhando para uma lista de comandos no manual, qualquer entusiasmo por aprender sobre isso desaparece. Tivemos que ganhar pão na web. Sim O mundo da programação de sistemas sobreviveu a seus anos dourados.
Portanto, para todos os alunos cujo entusiasmo não se esgotou, dedico um tutorial detalhado sobre como pegar e escrever do zero o núcleo mais simples de microkernel multitarefa com seu próprio shell. E quero avisar a todos que ele ainda não pareceu que esse é um caso ingrato e inútil, embora terrivelmente interessante. E a juventude, como você sabe, tem suas próprias preocupações.
Vamos lá!
Este
artigo contém um tutorial em
vídeo filmado no meu home studio. É dedicado diretamente ao código.
Vamos começar com o desenvolvimento do gerenciador de heap.
extern void *kmalloc(size_t size); extern void kfree(void *addr);
Para escrever um alocador de heap, você precisa armazenar as regiões de endereços de disponibilidade. É mais fácil de implementar como uma lista direcional. A implementação de uma lista direcionada em si terá que ser feita através de uma matriz estática.
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; };
Os elementos dessa lista limitada serão registros de regiões da memória. Além disso, entre regiões adjacentes não pode haver orifícios. Se houver memória livre, ela será descrita por um item de lista separado.
struct kheap_entry_t { struct slist_head_t list_head; size_t addr; size_t size; bool is_buzy; } 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 };
No início da estrutura kheap_entry_t está slist_head_t, que permite converter sem dor o tipo de registro de heap em um item da lista.
Agora considere o algoritmo mais simples de alocador de heap (kmalloc):
- Se não houver blocos livres, selecione um novo bloco do tamanho necessário (mas não mais que o tamanho máximo da pilha).
- Caso contrário, examinamos todos os blocos livres. Se encontrarmos um bloco livre, observe seu tamanho. Se for o suficiente, pegue. Se houver um excedente, crie um novo bloco vazio do tamanho do excedente. Caso contrário, se for insuficiente e o último, expandiremos o limite do heap (mas não mais que o máximo).
O algoritmo sem memória será semelhante (kfree):
- Encontre um bloco cujo endereço comece com o endereço a ser liberado. Verifique se ele está ocupado. Marcar como livre.
- Se houver um vizinho livre à direita ou esquerda para se unir a ele em um quarteirão.
O próximo artigo se concentrará na implementação do algoritmo de heap.
Vamos escrever o agendador mais simples. A tarefa terá a seguinte aparência:
struct task_t { struct clist_head_t list_head; u_short tid; struct gp_registers_t gp_registers; struct op_registers_t op_registers; struct flags_t flags; u_int time; bool reschedule; u_short status; int msg_count_in; struct message_t msg_buff[TASK_MSG_BUFF_SIZE]; void *kstack; void *ustack; } attribute(packed); struct clist_definition_t task_list = { .head = null, .slot_size = sizeof(struct task_t) };
Já sabemos como alocar memória e, portanto, organizar tarefas como uma lista de toque. Portanto, é mais conveniente executar a tarefa a seguir em relação à atual com o status desejado (usaremos o status TASK_RUNNING se a tarefa for executada). Para começar, assumiremos que todas as tarefas são executadas no anel de proteção do kernel (é mais fácil depurar o agendador) e seguiremos com uma pilha. No futuro, apertaremos o TSS.
Nós resolvemos as tarefas, agora o próprio planejamento. Adicione um manipulador de timer ao IDT e ative a interrupção da linha IRQ desejada no PIC. Interrompendo o timer (e no final do código de inicialização do kernel), transferimos o controle para o agendador, passando o endereço de retorno e o endereço dos registros salvos anteriormente da interrupção do timer:
/* * 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
No planejador, verificamos se alguma tarefa foi executada neste momento. Nesse caso, aumentamos o contador de seu tempo de execução e veremos se ele excede a cota. Caso contrário, retorne com calma. Se exceder, você precisará reagendar a tarefa. Nós salvamos seu estado (o endereço dos registradores salvos e o endereço de retorno armazenado na pilha, interrompendo o temporizador será útil).
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));
Pegamos o endereço da pilha da nova tarefa e formamos um quadro de retorno para o comando iret. Então chamamos a função assembler para alternar o contexto.
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)); current_task = next_task; asm_switch_context(next_task->op_registers.u_esp);
A própria alternância de contexto é assim:
# # Switch context # void asm_switch_context(u32 esp) # asm_switch_context: mov 4(%esp),%ebp # ebp = esp mov %ebp,%esp popal sti iretl
O planejador está pronto.
Veja o código completo
no tutorial em vídeo anexado ao artigo. Ele considera não apenas o planejador, mas também o processo de carregamento, compilação e configuração do IDT para aqueles que esqueceram: