Allocation dynamique de mémoire

Vous pouvez lire les slides de cours pour voir les détails, mais voici le résumé des principes en quelques lignes.

• kO6 propose l'API list permettant de gérer les listes chaînées
  • Cet API est définie dans le fichier common/list.h utilisable par le noyau et par l'application.
  • L'API list chaîne des éléments de liste de type list_t, structure composée d'un double pointeurs pointant vers d'autres structures list_t.
  • Les éléments de liste sont embarqués dans des structures porteuses. Ce sont les éléments de liste qui sont chaînés, mais l'API list permet de retrouver le pointeur sur la structure porteuse.
  • L'API list permet l'ajout et l'extraction d'élément de liste au début, au milieu ou à la fin d'une liste. Elle permet aussi l'ajout d'élément en utilisant une relation d'ordre pour obtenir des listes triées.
  • L'API list permet le parcours de tous les éléments d'une liste.

• Le code user de l'application (on dira juste application dans la suite) et le noyau ont besoin d'allouer dynamiquement de la mémoire.
  • L'application et le noyau disposent chacun d'un segment d'adresse propre, nommés respectivement .data et .kdata, pour leurs données. Ces segments ont été partiellement remplis par des variables globales du programme au moment de son chargement en mémoire.
  • Les allocateurs dynamiques utilisent l'espace libre de ces segments data.
  • L'application a 2 besoins distincts d'allocation dynamiques :
    1. l'allocation de variables dynamiques,
    2. l'allocation de piles pour les threads.
  • Les différences entre ces deux types de types d'allocation sont les suivantes :
    • D'un côté, les variables dynamiques sont allouées par l'application en fonction de ses besoins. La taille des variables est quelconque, allant de quelques octets à plusieurs mégaoctets (tant que c'est possible dans la mémoire disponible).
    • D'un autre côté, les piles des threads sont certes dans l'espace utilisateur, mais elles sont allouées par le noyau au moment de la création des threads. Leur taille est standard et fixe (dans un vrai système, on peut les choisir leur taille, mais pas pour kO6).

• Nous avons donc 3 allocateurs dans kO6 :
  • un allocateur de piles utilisateurs pour les threads
  • un allocateur de variables dynamiques pour l'application
  • un allocateur de variables dynamiques pour le noyau
  • L'allocateur de piles utilisateur et l'allocateur de variables doivent partager la zone libre laissée dans la section .data. L'allocateur de pile utilise la partie haute de la section .data et l'allocateur de variable utilise la partie basse.

• L'allocateur de piles pour les threads
  • C'est le plus simple. Il alloue les piles en réservant un segment de taille fixe (USTACK_SIZE défini dans common/usermem.h) à partir du haut du segment data, tant que cela n'entre pas en collision avec l'allocateur de variables dynamiques.
  • Lors de la libération, la pile est mise dans une liste chaînée triée par adresses décroissantes en utilisant l'API list.
  • Lors de l'allocation, la liste de piles libres est consultée en premier, avant de créer une nouvelle pile.
  • Le tri des piles libres permet d'augmenter la probabilité d'usage des piles placées en haut du segment .data.
  • Quand une pile est libérée et qu'elle est la plus basse en adresse. Le segment qu'elle occupait est rendu au noyau.

• L'allocateur de variables dynamiques pour l'application
  • Cet allocateur dispose d'un segment d'adresse nommé heap placé en bas de la section .data, juste après les variables globales, aligné sur les lignes de caches.
  • l'adresse limite du heap est nommée heap_end
  • L'allocateur gère des blocs (il fallait bien donner un nom...)
    • Un bloc est un segment d'adresse aligné sur les lignes de caches.
    • Un bloc est défini par une taille (en nombre de lignes de cache) et un état vide ou plein
  • Au début, le heap n'a pas de place, alors il demande de la place au kernel avec l'appel système sbrk_heap qui lui octroie de l'espace en déplaçant heap_end vers le haut (tant que cela n'entre pas en collision avec les piles de threads qui utilisent le haut de la section .data.
  • Cette demande de place a pour effet de créer un bloc vide.
  • L'API de cet allocateur est void * malloc(size) et void free(void *)
  • void * malloc(size)
    • La fonction parcourt l'ensemble des blocs en commençant par le tout premier à la recherche d'un bloc vide assez grand pour contenir size.
    • Si la place restante est plus petite qu'une ligne de cache, alors l'ensemble du bloc est marqué comme plein.
    • Sinon, le bloc est scindé en deux blocs, le premier plein et le second vide.
    • Si l'allocateur ne trouve pas de bloc assez grand, alors il parcours l'ensemble des blocs et si deux blocs voisins sont libres, il les réunit, puis il retente l'allocation. S'il échoue encore, il sort avec NULL.
    • Quand l'allocateur a trouvé un bloc, il rend un pointeur dessus.
  • void free(void *)
    • La fonction vérifie que l'adresse en argument a bien été allouée par malloc().
    • Elle marque le bloc pointée comme vide.

• L'allocateur de variables dynamiques pour le noyau
  • Le noyau alloue des structures ou des tables pour rendre ses services, pour les threads, les devices drivers, les ressources de synchronisation, le système de fichiers, etc.
  • Nous appelons ces structures et ces tables des objets (pour leur donner un nom différent de block), les objets ont un nombre entier de lignes de cache.
  • Le noyau doit pouvoir allouer et libérer ses objets très rapidement.
  • L'allocateur d'objets gère des listes d'objets libres de même taille.
  • Pour allouer un objet, l'allocateur se contente de prendre le premier objet libre dans la liste des objets libres de la bonne taille.
  • Pour libérer un objet, l'allocateur se contente de remettre l'objet au début de la liste des objets libres de la bonne taille.
  • Au départ, toutes les listes sont vides.

(pas fini)

A. Questions de cours

La majorité des réponses aux questions sont dans le cours ou dans le rappel du cours donné au début de cette page, c'est voulu. Les questions suivent à peu près l'ordre du cours, elles sont simples, mais vous avez besoin de comprendre le cours pour y répondre :-) Quand une question vous demande si quelque chose est vrai ou faux, ne répondez pas juste "oui" ou "non », mais justifiez vos réponses avec une petite phrase. Le but de ces questions est d'évaluer vos connaissances, donc plus vous êtes précis, mieux c'est.

B. Travaux pratiques