Geekly articles weekly

Développement d'un système d'exploitation monolithique de type Unix - Heap (4)

Dans l' article précédent, nous avons implémenté le journal système du noyau. Il est maintenant temps d'implémenter un gestionnaire de mémoire dynamique.

Table des matières


  1. Construisez le système (make, gcc, gas). Démarrage initial (multiboot). Lancez (qemu). Bibliothèque C (strcpy, memcpy, strext).
  2. Bibliothèque C (sprintf, strcpy, strcmp, strtok, va_list ...). Construction de la bibliothèque en mode noyau et en mode application utilisateur.
  3. Le journal système du noyau. Mémoire vidéo Sortie vers le terminal (kprintf, kpanic, kassert).
  4. Mémoire dynamique, tas (kmalloc, kfree).
  5. Organisation de la mémoire et gestion des interruptions (GDT, IDT, PIC, syscall). Exceptions
  6. Mémoire virtuelle (répertoire de pages et table de pages).
  7. Processus. Planificateur Multitâche. Appels système (kill, exit, ps).
  8. Le système de fichiers du noyau (initrd), elf et ses composants internes. Appels système (exec).
  9. Pilotes de périphériques de caractères. Appels système (ioctl, fopen, fread, fwrite). Bibliothèque C (fopen, fclose, fprintf, fscanf).
  10. Shell comme programme complet pour le noyau.
  11. Mode de protection utilisateur (ring3). Segment d'état de la tâche (tss).

Mémoire dynamique du noyau. Un tas


L'interface du tas du noyau ressemblera à ceci:

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

Puisqu'il n'y a pas encore de tas, les enregistrements des régions de mémoire occupées et libres devront être stockés.
dans un tableau de taille limitée. Plus la dimension est petite, plus la capacité du tas est faible de
petits fragments. Sous Linux, par exemple, de nombreuses structures de noyau sont stockées dans des fichiers réutilisables
mémoire qui ne change pas de taille une fois libérée (dalle). Mais nous en sommes encore loin,
parce que le développement est un processus itératif.

Tout élément qui a l'intention d'être un élément d'une liste organisée à travers un tableau
nécessaire pour implémenter une interface.

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

Il n'y a pas d'interfaces en C, mais elles ne sont pas nécessaires. Nous castons simplement le pointeur de n'importe quel objet sur le type struct slist_head_t * si cet objet ressemble physiquement à ceci:

 struct my_list_entry_t { struct slist_head_t list_head; ... }

Mais pour que l'algorithme généralisé connaisse la dimension du tableau dans lequel la liste sera stockée
et la taille de son élément, le premier et le dernier élément de la liste et l'adresse du tableau dans lequel
une liste est stockée, chaque fonction de la liste de fonctionnement aura besoin d'un autre pointeur
à la structure de définition de liste:

 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 fonctions de fonctionnement de la liste ressembleront à ceci:

 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);

Insérer un algorithme de fonction:
Trouvez un emplacement libre dans la baie.
Remplissez-le avec un nouvel élément.
Corrigez les pointeurs des éléments de liste adjacents logiquement (et non physiquement).
Marquer l'emplacement comme occupé.
Ajustez le début et la fin de la liste.

L'algorithme de la fonction à supprimer de la liste:
Corrigez les pointeurs des éléments de liste adjacents logiquement (et non physiquement).
Ajustez le début et la fin de la liste.
Marquer l'emplacement comme libre.

La mémoire dynamique est décrite par une liste avec les éléments suivants:

 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);

Un tableau décrivant la mémoire dynamique à partir de ces enregistrements ressemble à ceci:

 struct kheap_entry_t kheap_blocks[KHEAP_MAX_ENTRIES];

La définition d'une liste de régions mémoire ressemble à ceci:

 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};

Nous avons donc décrit la mémoire dynamique. Toute la mémoire dans une certaine plage
est divisé en blocs de taille arbitraire, chacun pouvant être soit vide,
soit occupé. De plus, chaque bloc est décrit par un élément de tableau avec le drapeau is_valid = true,
qui est 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 de l'excédent. Sinon, s'il est insuffisant et ce dernier, nous élargissons la limite du tas (mais pas plus que le maximum).

 /* * 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; }

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.

 /* * 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); }

C’est tout. Jusqu'à la prochaine fois!

Les références


Maintenant, ouvrez le didacticiel vidéo
Et regardez le dépôt git en parallèle (vous avez besoin d'une branche de leçon 4)

Les références


1. James Molloy. Faites rouler votre propre système d'exploitation jouet UNIX-clone.
2. Dents. Assembleur pour DOS, Windows, Unix
3. Kalachnikov. L'assembleur est facile!
4. Tanenbaum. Systèmes d'exploitation. Mise en œuvre et développement.
5. Robert Love. Noyau Linux Description du processus de développement.

Source: https://habr.com/ru/post/fr466831/

More articles:


All Articles