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.

• L'application 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é respectivement .data et .kdata, pour leurs données.
  • Ces segments ont été partiellement remplis par les variables globales du programme au moment de leur 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 avec une API utilisateur malloc/free
    2. l'allocation de piles pour les threads avec une API ad hoc utilisée par le noyau.
  • 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 choisir leur taille à la création du thread, mais pas pour kO6).

• Nous avons donc 3 allocateurs dans kO6 :
  • un allocateur de variables dynamiques pour l'application ;
  • un allocateur de piles ‘’utilisateurs’’ pour les threads de l'application, mais utilisé par le noyau ;
  • 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 le segment .data. Ainsi l'allocateur de piles utilise la partie haute du segment .data et l'allocateur de variables utilise la partie basse.

• kO6 propose une API nommée list permettant de gérer les listes chaînées
  • Cette API est définie dans le fichier common/list.h et elle est utilisable par l'application et le noyau, notamment dans les allocateurs.
  • L'API list permets de chaîner des éléments de liste de type list_t, laquelle est une structure composée d'un double pointeur 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 type list_t qui sont chaînés entre eux, mais l'API list permets de retrouver le pointeur sur la structure porteuse de l'élément.
  • L'API list permets l'ajout et l'extraction d'éléments de liste au début, au milieu ou à la fin d'une liste.
  • L'API list permets aussi l'ajout d'élément en utilisant une relation d'ordre choisie par l'utilisateur pour obtenir des listes triées.
  • L'API list permets le parcours de tous les éléments d'une liste.

• L'allocateur de piles pour les threads.
  • C'est l'allocateur 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 qui utilise le bas de ce même segment.
  • 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.
  • Quand une pile est libérée et qu'elle est celle placée à l'adresse la plus basse, alors la place qu'elle occupait est rendue au noyau.
  • Le tri des piles libres permet d'augmenter la probabilité d'usage des piles placées en haut du segment .data et donc la libération des piles placées plus bas.

• L'allocateur de variables dynamiques pour l'application.
  • Cet allocateur gère un segment d'adresses nommé heap placé en bas du segment .data, situé juste après les variables globales et alignées sur les lignes de caches.
  • l'adresse limite du heap est nommée heap_end, c'est un pointeur.
  • 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 : (1) une taille (en nombre de lignes de cache) et (2) un état vide ou plein
  • Au début, le heap est vide (il ne contient pas de bloc), 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 le pointeur heap_end vers le haut (tant que cela n'entre pas en collision avec les piles de threads qui utilisent le haut du segment .data.
  • Cette demande de place a pour effet de créer un bloc vide.
  • L'API de cet allocateur est void * malloc(size_t) et void free(void *)
  • void * malloc(size) (politique de remplissage first fit)
    • 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 à l'état plein et le second à l'état vide.
    • Si l'allocateur ne trouve pas de bloc assez grand, alors il parcourt l'ensemble des blocs et si deux blocs voisins sont libres, il les réunit, puis il retente l'allocation. S'il échoue encore et 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é comme vide, c'est-à-dire non alloué.

• 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 bloc), les objets ont un nombre entier de lignes de cache. Le noyau doit pouvoir allouer et libérer ses objets très rapidement.
  • L'API de cet allocateur est void * kmalloc(size_t) et void free(void *, size_t)
  • void * kmalloc(size) (politique de remplissable slab)
    • L'allocateur d'objets du noyau gère un tableau de listes d'objets libres de même taille.
    • Au départ, toutes les listes d'objets libres sont vides.
    • Lorsqu'une demande d'allocation est faite pour une certaine taille T et que la liste des objets libres de cette taille T est vide alors l'allocateur alloue une dalle (ou slab en anglais) de 4kO.
    • Il découpe la dalle en autant d'objets que possible de la taille T demandée et il chaîne ces objets pour remplir la liste d'objets libres.
    • Pour allouer un objet, l'allocateur prend le premier objet de la liste des objets libres de la bonne taille.
  • void kfree(void *, size_t)
    • Pour libérer un objet, l'allocateur se contente de le remettre au début de la liste des objets libres de la bonne taille donnée en argument.
    • Lors de la libération d'un objet, il peut s'avérer que tous les objets d'une dalle X sont libres. Dans ce cas, l'allocateur retire de la liste d'objets libres tous les objets appartenant à la dalle X et il rend cette dalle à la liste des dalles libres.
  • Les listes d'objets libres se remplissent ou se vident dynamiquement.

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.

1. Quels sont les besoins d'allocation de l'application et du noyau ?
2. L'allocation dynamique est confrontée au problème de fragmentation de l'espace libre. Il y a deux types de fragmentation, définissez-les.
3. Pourquoi l'API list propose-t-elle un double chaînage pour ses éléments ?
4. Comment est-il possible de trouver le pointeur sur la structure à partir du pointeur sur l'un de ses champs ? Comment se nomme la macro (ce n'est pas une fonction) permettant ce service (la réponse est dans les slides du cours)
5. À quoi sert l'allocateur de piles user ? Qui demande l'allocation ? Qui utilise les piles ? Est-ce que ces piles ont une taille variable ?
6. Où sont allouées les piles user ? Peut-on en allouer autant que l'on veut ? dites pourquoi.
7. Est-ce que ces piles peuvent déborder ? Si oui, est-ce vraiment un problème et que propose kO6 pour ce problème ?
8. Que signifie que les objets alloués sont alignés sur les lignes de cache ? Et quels sont les bénéfices de cette contrainte ?
9. L'allocateur d'objets (nommés blocs dans le rappel de cours au-dessus) pour l'application utilise une politique first fit. Qu'est-ce que cela signifie ? Quels sont les autres ? Existe-t-il une politique meilleure que les autres et pour quel critère ?
10. Rappeler le nom des deux fonctions de l'API utilisateur de cet allocateur. Est-ce que ces fonctions font des appels système à chaque fois ? Si oui, quand et pourquoi ?
11. Pour libérer un objet alloué par l'allocateur de l'application, la fonction free() reçoit juste le pointeur rendu par malloc(). Comment la fonction free() connaît-elle la taille qui avait été allouée ?
12. L'allocateur d'objets du noyau utilise un mécanisme d'allocation par dalles ou slab en anglais, nommé slab allocator. Qu'est-ce qu'un slab ? Quelle est la taille d'un slab ? Quel est l'intérêt des slabs?
13. L'allocateur d'objets du noyau gère des listes d'objets libres. Quel rapport y a-t-il entre les objets alloués et les slabs ? À quel moment les slabs sont-ils alloués ? À quel moment les slabs sont-ils libérés ?
14. Lorsqu'on libère le dernier objet d'un slab, celui-ci est libéré, pensez-vous que cela puisse être un problème ? Si oui, avez-vous une solution ?
15. Les objets alloués par l'allocateur d'objets de kO6 font au maximum 4kO, pourquoi cette limite ? Est-ce un problème selon vous ?
16. Pour libérer un objet alloué par l'allocateur d'objets du noyau, on utilise la fonction kfree() qui prend en argument le pointeur alloué par kmalloc() et la taille allouée. Pourquoi demander la taille ? Est-ce une contrainte ?
17. Le premier usage des allocateurs est fait par la gestion des threads. Sur les trois allocateurs décrits ici, quels sont ceux qu’il utilise?
18. Chaque thread a désormais deux piles. Quelles tailles ont-elles ? À quoi servent-elles et pourquoi sont-elles utiles ? À quel moment bascule-t-on de l'une à l'autre ?

B. Travaux pratiques

Pour la partie pratique, vous allez devoir programmer un peu. Les premières questions sont assez faciles, les dernières un peu moins, faites ce que vous pouvez.

Dans le code, on peut voir qu'il existe un tableau Objects[] contenant de cases qu'il existe de taille d'objets possibles (mesurée en nombre de lignes) et dont chaque case contient le nombre d'objet libre de listes d'objets libres, indexé par les identifiants de slab (l'identifiant de slab est la taille des objets qu'il contient en nombre de lignes). Le tableau Objects contiens le nombre d'objets alloués. Il faudrait un autre tableau semblable contenant le nombre d'objets libres disponible.