Après avoir lu les étapes de base pour écrire des noyaux Hello World à partir de la série d'articles disponibles sur Habré, il est temps de commencer le développement sérieux des outils les plus élémentaires: l'allocateur de tas et le planificateur.
Important :
1. Cette série de leçons pour les débutants. Le but est de former une image holistique du monde. Pendant très longtemps, j'avais la théorie de Tanenbaum dans ma tête et je ne pouvais pas la relier à la pratique. Pour ceux qui ont la même chose - je dédie cet article.
2. Le code est le plus simple et le plus stupide, mais aussi clair que possible. Mon objectif est de vous donner une compréhension afin que vous puissiez écrire votre propre noyau, beaucoup plus cool que cela.
3. Je publierai le dépôt dès que je le considérerai prêt pour une large gamme. J'écris une petite partie, débogue et filme un tutoriel vidéo. Je n'ai pas de produit fini.
Honnêtement, j'ai longtemps pensé s'il valait la peine de commencer à écrire des articles et à faire des didacticiels vidéo sur un sujet aussi brûlant. Mais la passion pour la programmation système et le manque d'informations structurées en russe m'ont néanmoins poussé à cette expérience. Par conséquent, si mon travail est en demande, je prévois de publier des articles au moins une fois par mois et pas plus d'une fois par semaine.
J'ai rêvé d'écrire mon OS en dixième année. Le livre de Tanenbaum a une propriété étonnante. Quiconque y touche tôt ou tard commence à rêver d'écrire son propre système d'exploitation. Mais je n'ai rien écrit à ce moment-là , après avoir réalisé qu'il était impossible de compiler et de lier un binaire propre avec un code un mardi. J'ai dû étudier Linux, aller à l'université, aller travailler. Tout ne serait rien. Oui, seul un rêve s'est réalisé seulement dix ans plus tard. Maintenant, en fabriquant des moules ennuyeux sur React, je regarde en arrière, je me souviens de la passion avec laquelle j'ai passé des heures pour le démonteur et le débogueur, enlevé les emballeurs, cassé les boîtes de crack, j'ai lu beaucoup d'articles de romans scolaires la nuit ... et je comprends que ma vie aurait pu se dérouler différemment. Assez différent. Si seulement j'avais une personne qui pouvait m'aider au tout début. Mais le temps est révolu. Les programmes sont devenus difficiles à rompre. Le noyau Linux a atteint des tailles incroyables. Des hyperviseurs sont apparus. L'assembleur Intel est devenu si grand qu'en regardant une liste de commandes dans le manuel, tout enthousiasme pour en savoir plus disparaît. Nous devions gagner du pain sur le web. Oui Le monde de la programmation système a survécu à ses années d'or.
Par conséquent, à tous les étudiants dont l'enthousiasme n'est pas épuisé, je consacre un tutoriel détaillé sur la façon de prendre et d'écrire à partir de zéro le noyau du micro-noyau multitâche le plus simple avec son propre shell. Et je tiens à avertir tout le monde qu'il n'est pas encore apparu que c'est une affaire ingrate et inutile, bien que terriblement intéressante. Et la jeunesse, comme vous le savez, a ses propres préoccupations.
C'est parti!
Cet
article contient un didacticiel vidéo tourné dans mon home studio. Il est dédié directement au code.
Commençons par le développement du gestionnaire de tas.
extern void *kmalloc(size_t size); extern void kfree(void *addr);
Pour écrire un allocateur de tas, vous devez stocker les régions d'adresses libres et occupées. Ceci est plus facile à implémenter en tant que liste directionnelle. L'implémentation d'une liste dirigée elle-même devra se faire via un tableau statique.
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; };
Les éléments d'une telle liste limitée seront des enregistrements de régions de mémoire. De plus, entre les régions adjacentes, il ne peut y avoir de trous. Si de la mémoire libre est présente, elle est décrite par un élément de liste distinct.
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 };
Au début de la structure kheap_entry_t se trouve slist_head_t, qui vous permet de convertir sans peine le type d'enregistrement de segment de mémoire en un élément de liste.
Considérons maintenant l'algorithme d'allocation de tas le plus simple (kmalloc):
- S'il n'y a pas de blocs libres, sélectionnez un nouveau bloc de la taille requise (mais pas plus que la taille de segment de mémoire maximale).
- Sinon, nous parcourons tous les blocs libres. Si nous trouvons un bloc libre, regardez sa taille. Si cela suffit, prenez-le. S'il y a un surplus, créez un nouveau bloc vide de la taille du surplus. Sinon, s'il est insuffisant et ce dernier, nous élargissons la limite du tas (mais pas plus que le maximum).
L'algorithme sans mémoire sera similaire (kfree):
- Recherchez un bloc dont l'adresse commence par l'adresse à libérer. Vérifiez qu'il est occupé. Marquer comme gratuit.
- S'il y a un voisin libre Ă droite ou Ă gauche pour s'unir avec lui dans un bloc.
Le prochain article se concentrera sur l'implémentation de l'algorithme de tas.
Écrivons le planificateur le plus simple. La tâche ressemblera à ceci:
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) };
Nous savons déjà comment allouer de la mémoire et donc organiser les tâches comme une liste en anneau. Il est donc plus pratique de prendre la tâche suivante par rapport à la tâche actuelle avec le statut souhaité (nous utiliserons le statut TASK_RUNNING si la tâche est effectuée). Pour commencer, nous supposerons que toutes les tâches sont effectuées dans l'anneau de protection du noyau (il est plus facile de déboguer le planificateur) et nous nous débrouillerons avec une seule pile. À l'avenir, nous allons fixer TSS.
Nous avons trié les tâches, maintenant la planification elle-même. Ajoutez un gestionnaire de temporisation à l'IDT et activez l'interruption de la ligne IRQ souhaitée dans le PIC. En interrompant le temporisateur (et à la fin du code d'initialisation du noyau), nous transférons le contrôle au planificateur, en passant l'adresse de retour et l'adresse des registres précédemment enregistrés à partir de l'interruption du temporisateur:
/* * 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
Dans le planificateur, nous vérifions si une tâche a été effectuée à ce moment. Si c'est le cas, nous augmentons le compteur de son temps d'exécution et voyons s'il dépasse le quota. Sinon, revenez calmement. Si dépasse, vous devez replanifier la tâche. Nous sauvegardons son état (l'adresse des registres enregistrés et l'adresse de retour stockée dans la pile en interrompant le temporisateur seront utiles).
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));
Nous prenons l'adresse de pile de la nouvelle tâche et y formons un cadre de retour pour la commande iret. Ensuite, nous appelons la fonction assembleur pour changer de contexte.
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);
Le changement de contexte lui-mĂŞme ressemble Ă ceci:
# # Switch context # void asm_switch_context(u32 esp) # asm_switch_context: mov 4(%esp),%ebp # ebp = esp mov %ebp,%esp popal sti iretl
Le planificateur est prĂŞt.
Voir le code complet
dans le didacticiel vidéo joint à l'article. Il considère non seulement le planificateur, mais aussi le processus de chargement, de compilation et de configuration d'IDT pour ceux qui ont oublié: