{{{#!html

INDEX

}}} [[PageOutline]] **DOCS** → [__**[wiki:Howto-TP Config]**__] [__**[htdocs:cours/doc_MIPS32.pdf MIPS U]**__] [__**[wiki:Doc-MIPS-Archi-Asm-kernel MIPS K]**__] [__**[http://support.typora.io/Markdown-Reference markdown]**__] [__**[htdocs:files/CR031_TPx_Nom1_Nom2.md.tgz CR.md]**__] \\**COURS** → [__**[htdocs:cours/Archi-2-B1-reboot-2p.pdf 1]**__ __([htdocs:cours/Archi-2-B1-code-2p.pdf +code]__) __([htdocs:cours/Archi-2-B1-outils-2p.pdf +outils]__)] [__**[htdocs:cours/Archi-2-B2-interruptions-2p.pdf 2]**__] [__**[htdocs:cours/Archi-2-B3-cache-archi-2p.pdf 3]**__] [__**[htdocs:cours/Archi-2-B4-cache-perf-2p.pdf 4]**__] [__**[htdocs:cours/Archi-2-B5-threads-2p.pdf 5]**__] [__**[htdocs:cours/Archi-2-B6-alloc-2p.pdf 6]**__] [__**[htdocs:cours/Archi-2-B7-synchro-2p.pdf 7]**__] [__**[htdocs:cours/Archi-2-B8-initiateurs-2p.pdf 8]**__] [__**[htdocs:cours/Archi-2-B9-ZDL-2p.pdf 9]**__] \\**TME → ** [__**[wiki:AS6-TME-B1 1]**__] [__**[wiki:AS6-TME-B2 2]**__] [__**[wiki:AS6-TME-B3 3]**__] [__**[wiki:AS6-TME-B4 4]**__] [__**[wiki:AS6-TME-B5 5]**__] [__**[wiki:AS6-TME-B6 6]**__] [__**[wiki:AS6-TME-B7 7]**__] [__**[wiki:AS6-TME-B8 8]**__] [__**[wiki:AS6-TME-B9 9]**__] \\**CODE → ** [__**[htdocs:files/kO6a2bin.tgz gcc + soc]**__] [__**[htdocs:files/tp1.tgz 1]**__] [__**[htdocs:files/tp2.tgz 2]**__] [__**[htdocs:files/tp3.tgz 3]**__] [__**[htdocs:files/tp4.tgz 4]**__] [__**[htdocs:files/tp5.tgz 5]**__] [__**[htdocs:files/tp6.tgz 6]**__] [__**[htdocs:files/tp7.tgz 7]**__] [__**[htdocs:files/tp8.tgz 8]**__] [__**[htdocs:files/tp9.tgz 9]**__] {{{#!html

6 - Allocation dynamique de mémoire }}} Résumé des principes de l'allocation de mémoire vue en cours. - **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` 1. 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 ? {{{#!protected ------------------------------------------------------------------ ''' * Ici, il y en a 3. L'application a besoin de piles pour ses threads et de variables dynamiques. Le noyau a besoin de variables dynamiques pour rendre ses services. * Notez que, même si les piles des threads sont utilisées exclusivement par les threads quand ils exécutent le code de l'application en mode user, elles sont allouées par le noyau au moment de la création des threads. ''' }}} 1. 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. {{{#!protected ------------------------------------------------------------------ ''' * On parle de fragmentation pour nommer l'émiettement de l'espace libre qui se produit lorsqu'on effectue un grand nombre d'allocations puis de libérations de segments d'adresses de tailles différentes. * On parle de fragmentation externe pour l'espace entre objets alloués. * On parle de fragmentation interne pour l'espace inutilisé à l'intérieur des objets alloués, ce qui arrive quand on alloue plus que ce que l'utilisateur demande. * La fragmentation externe est d'autant plus grave que le nombre d'objets est grand et que leur taille est très différente. * Pour lutter contre la fragmentation, on peut aligner des objets alloués sur des segments par trop petit de sorte à toujours avoir des espaces utilisables entre les objets, mais cela crée une fragmentation interne. * On peut aussi gérer des ensembles d'objets de même taille. * En bref, dans le cas général, la fragmentation est inévitable, mais si l’on sait à l'avance quelles sont les tailles des objets alloués, alors on peut fortement la réduire. ''' }}} 1. Pourquoi l'API `list` propose-t-elle un double chaînage pour ses éléments ? {{{#!protected ------------------------------------------------------------------ ''' * Il ne faut pas seulement parcourir une liste, il faut aussi pouvoir ajouter ou extraire des éléments n'importe où. * Pour ajouter un élément devant un autre, il faut accéder à l'élément précédent et donc avoir un double chaînage. * Cela permet aussi d'ajouter très facilement en fin de liste puisque l'élément de fin de liste est celui qui précède la racine (si l’on construit une liste circulaire). ''' }}} 1. 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) {{{#!protected ------------------------------------------------------------------ ''' * Pour trouver le pointeur sur la structure porteuse d'un élément de liste, il faut connaître 3 choses : 1. l'adresse en mémoire de l'élément de liste, 1. le type C de la structure porteuse 1. le nom du champ de l'élément de liste dans la structure porteuse. * Le compilateur sait à quelle position le champ élément de liste (dont on lui donne le nom) se trouve dans la structure porteuse (dont on lui donne le type) et il peut déduire l'adresse de la structure porteuse à partir de l'adresse de l'élément avec une simple soustraction : adresse élément - position dans la structure * c'est la macro `list_item( &element, type_porteuse, nom_champ_élément)` * La question n'est pas posée, mais comprenez que c'est une macro, ce n'est pas une fonction parce que c'est un calcul fait par le compilateur. ''' }}} 1. À quoi sert l'allocateur de piles user ? Qui demande l'allocation ? Qui utilise les piles ? Est-ce que ces piles ont une taille variable ? {{{#!protected ------------------------------------------------------------------ ''' * L'allocateur de piles user sert pour les threads de l'application, il faut une pile par thread pour les contextes d'exécution des fonctions. * C'est le noyau qui fait l'allocation des piles lorsqu'il crée les threads et ce sont les threads qui les utilisent. * Dans l'état actuel de kO6, la taille des piles n'est pas paramétrable. ''' }}} 1. Où sont allouées les piles user ? Peut-on en allouer autant que l'on veut ? dites pourquoi. {{{#!protected ------------------------------------------------------------------ ''' * Les piles user sont allouées dans la partie haute du segment `.data`. * On ne peut pas en allouer autant qu'on veut parce que le segment n'est pas infini. * Le segment `.data` contient aussi les variables globales de l'application dans la partie basse et les piles ne doivent pas entrer en collision, pas d'intersection. ''' }}} 1. Est-ce que ces piles peuvent déborder ? Si oui, est-ce vraiment un problème et que propose kO6 pour ce problème ? {{{#!protected ------------------------------------------------------------------ ''' * Oui, les piles peuvent déborder, il n'y a aucun mécanisme pour se protéger. * Un mécanisme possible serait de lever des exceptions ''accès mémoire interdit'' lorsqu'on sortirait d'une pile, mais il n'y en a pas. * C'est un problème, parce que déborder une pile, c'est écraser des données. Le plus grave, c'est que la perte de donnée due à l'écrasement peut ne pas être visible avant plusieurs dizaines de millions de cycles et le debug devient particulièrement difficile. * Pour traiter ce problème, kO6 écrit au début et à la fin des piles, des nombres magiques qui ne devront jamais être écrasés si les piles sont correctement utilisées. Ces sont des sentinelles. * kO6 peut regarder périodiquement (par exemple à chaque commutation) que la pile n'a débordée, si les sentinelles sont toujours là. * Avec ce mécanisme, on ne peut pas détecter précisément quand le problème arrive, mais on a une fourchette temporelle d'un tick d'horloge, c'est déjà pas mal. ''' }}} 1. 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 ? {{{#!protected ------------------------------------------------------------------ ''' * Cela signifie que l'adresse de début des objets et leur taille sont des multiples de la taille d'une ligne de cache. * Il y a trois avantages : 1. ça limite la fragmentation externe puisque les trous entre les objets font au moins une ligne, et ils ont donc plus de chance d'être utilisés. 1. ça évite les faux partages. En effet, si l’on met dans une même ligne de cache des variables non partagées utilisées par plusieurs threads s'exécutant sur des cœurs différents, le mécanisme de cohérence de cache se met en route à chaque modification des variables alors que c'est inutile. 1. Si les structures de données allouées de manière dynamique sont alignées alors lorsqu'on lit le premier champ de la structure, on lit aussi les suivants et l’on bénéficie de la localité spatiale. C'est un gain en performance (certes mineur). ''' }}} 1. 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 ? {{{#!protected ------------------------------------------------------------------ ''' * L'allocation ''first-fit'' signifie que l'allocateur utilise le premier bloc libre assez grand pour l'objet alloué. Ce bloc libre est coupé en deux s'il est trop grand pour produire un nouveau bloc libre, mais plus petit parce qu’amputé de la partie allouée à l'objet. * On a aussi l'allocation ''next-fit'' qui consiste à ne pas partir du début dans la recherche d'un bloc libre, mais de l'endroit de la dernière affectation, et la l'allocation ''best-fit'' qui consiste à trouver un bloc libre de la bonne taille en premier. * Il en existe d'autres, leur but est d'augmenter les performances et de réduire la fragmentation. * Il n'y a pas de meilleures solutions, mais si on connaît la nature des besoins en termes d'allocation, on peut imaginer des mécanismes plus efficaces. ''' }}} 1. 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 ? {{{#!protected ------------------------------------------------------------------ ''' * `void * malloc(size_t)` et `void free(void *)`. * Non, ces fonctions ne font pas d'appel système à chaque fois. L'allocateur de la libc se fait allouer un segment assez grand par l'appel système `sbrk_heap` et ensuite, il alloue des segments (nommés blocs dans le cours) et les libère à la demande. * L'appel système, c'est pour demander un peu plus pour `malloc()`, mais `free()` ne demande jamais de réduire l'espace. ''' }}} 1. 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 ? {{{#!protected ------------------------------------------------------------------ ''' * Alors, `free()` doit retrouver la taille allouée. Il y avait plusieurs possibilités, celle choisie est la plus simple, elle consiste à ce que le premier mot du bloc alloué est utilisé pour stocker la taille du bloc. * Ainsi, si `free()` reçoit en argument l'adresse A, alors la taille du bloc est à l'adresse A-4. * Ce mot d'information est nommé `block_info`, il contient la taille en ligne de cache (ça économise des bits), un bit d'état (bloc `full` ou `empty`) et un numéro magic pour repérer d'éventuelles corruptions des données. ''' }}} 1. 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? {{{#!protected ------------------------------------------------------------------ ''' * Un slab est un segment d'adresses contenant des objets de même taille. * Pour kO6, il n'y a qu'une seule taille, une page de 4kO, mais normalement la taille des slabs dépend de la taille des objets. En effet, quand la taille du slab n'est pas un multiple de la taille de l'objet, il y a un fragment inutile créé dans le slab. Ce fragment est d'autant plus grand que les objets sont grands. C'est pourquoi au-delà de 1/8 de page (512 octets), on prend des slabs de 2, 4 ou 8 pages (des puissances de 2 pour des raisons que je n'aborderai pas ici). * Le principal intérêt de ce mécanisme c'est sa rapidité. En effet, lorsque l'allocateur a créé ses listes d'objets libres, en prendre un est très rapide, de même que le rendre. * Le second intérêt est la réduction de la fragmentation externe, limitée aux fragments non utilisés dans les slabs. ''' }}} 1. 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 ? {{{#!protected ------------------------------------------------------------------ ''' * En fait, la réponse est donnée dans la réponse précédente. Les slabs contiennent les objets libres et donc les futurs objets alloués. Notez que quand un objet est alloué, il n'est plus dans le slab, il y retourne quand il est libéré. * L'allocateur alloue un slab quand on lui demande un objet d'une certaine taille, mais que la liste des objets libres de cette taille est vide. L'allocateur demande alors un slab (ici, une page de 4kO) pour remplir la liste d'objets libres et en extraire finalement un. * L'allocateur recherche les slabs entièrement remplis d'objets libres et dans ce cas, il en retire tous les objets et rend le slab. ''' }}} 1. 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 ? {{{#!protected ------------------------------------------------------------------ ''' * La politique de rendre un slab dès qu'il est plein (qu'il ne contient que des objets libres) n'est pas forcément efficace. * En effet, si on alloue un objet d'une taille T, alors on ouvre un slab (on l'alloue) et si on le libère, alors on ferme le slab (on le libère). Si on fait ça en boucle, l'ouverture/fermeture (allocation/libération) des slabs est une perte de temps. * Il est sans doute préférable d'avoir toujours des listes d'objets libres non vides. On peut donc définir un seuil d'objets libres en dessous duquel ne pas descendre. ''' }}} 1. 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 ? {{{#!protected ------------------------------------------------------------------ ''' * 4kO est une taille standard utilisée pour la gestion de la mémoire des applications, et pour le système de fichiers. On ne le voit pas ici, mais le noyau gère en principe une mémoire physique découpée en pages (nommé parfois cadres). En fait, la mémoire est vue comme un réservoir de pages dans lequel le noyau peut piocher pour y mapper du code, des données, des morceaux de fichiers, etc. La page est un élément atomique. * Honnêtement, c'est difficile de dire si c'est vraiment un problème que les slabs fassent au plus une page. Ce que l'on peut dire, c'est qu'en biologie, "le besoin crée l'organe" et bien pour le système d'exploitation, le besoin doit créer la fonction, afin de ne pas créer des codes morts (jamais utilisés) qui sont des nids de bugs. Donc, tant que le besoin est absent, ce n'est pas un problème de ne pas avoir la fonction :-) ''' }}} 1. 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 ? {{{#!protected ------------------------------------------------------------------ ''' * `kfree()` demande la taille pour savoir dans quelle liste d'objets libre remettre l'objet. * Le `kfree()` de Linux ne le demande pas, mais je ne pense pas que cela soit une contrainte. On est dans le noyau et je ne pense pas que le noyau ait à libérer des objets dont il ignore le type et donc la taille. Par contre cette information donnée à `kfree()` permet de ne pas avoir besoin de la stocker quelque part lors de l'allocation (comme c'est fait pour l'allocateur de la libc). ''' }}} 1. 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? {{{#!protected ------------------------------------------------------------------ ''' * Le noyau utilise l'allocateur slab pour lui et l'allocateur de piles pour l'application lors de la création des threads. ''' }}} 1. 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 ? {{{#!protected ------------------------------------------------------------------ ''' * Il y a deux piles par thread : 1. La pile allouée dans la section `.data` sert aux contextes d'exécution des fonctions du thread quand le processeur est en mode user. Sa taille est `USTACK_SIZE`, c'est une variable de configuration du noyau définie dans `common/usermem.h` à 16 pages (64ko). 2. La pile allouée dans la structure `kthread_t` dans la section `.kdata` (dans le `kheap`, c'est le plus gros objet que l'allocateur slab peut allouer). Elle sert aux contextes d'exécution des fonctions du thread quand le processeur est en mode kernel. Sa taille est 4kO moins la place prise par les champs de la structure décrivant le thread et la table de sauvegarde du contexte du thread. * On bascule de l'une à l'autre quand on entre dans le noyau. * L'intérêt d'avoir deux piles. * C'est que l'utilisateur ne peut pas découvrir ce que le noyau a fait en observant la pile. * Quand on entre dans le noyau, on a toujours une pile vide (pas grande, mais suffisante), on a moins de risque de débordement. ''' }}} == = B. Travaux pratiques {{{#!html Il n'y a pas de corrigés de TPs }}} Commencez par récupérer le code de source de la séance tp6 (toujours accessible dans INDEX) Pour la partie pratique, vous allez devoir programmer un peu. Les premières questions sont assez faciles, les dernières un peu moins. Le but est de vous «forcer» à entrer dans le code et même des petites modifications suffisent. Les exercices sont classés par niveau de difficultés supposées (on est jamais à l'abri de surprises). En préalable de tous les exercices, quelques questions sur le code. Dans le répertoire `tp6` vous trouvez le répertoire `01_malloc` qui contient le code complet des allocateurs et la modification du code de `kentry` pour le changement de pile. {{{ 01_malloc ├── Makefile ├── common │   ├── debug_off.h // message de debug évolué │   ├── debug_on.h // expliqué plus tard │   ├── list.h // gestion des listes chaînée │   ├── syscalls.h │   └── usermem.h // déclaration des limites du segment data ├── kernel │   ├── Makefile │   ├── harch.c │   ├── harch.h │   ├── hcpu.h │   ├── hcpua.S // changement de pile dans le kentry │   ├── hcpuc.c │   ├── kernel.ld │   ├── kinit.c │   ├── klibc.c │   ├── klibc.h │   ├── kmemory.c // code des allocateurs slab et stack │   ├── kmemory.h // prototypes des allocateurs │   ├── ksyscalls.c │   ├── kthread.c // code de la gestion des threads │   └── kthread.h // prototypes et structure kthread_t ├── uapp │   ├── Makefile │   └── main.c └── ulib ├── Makefile ├── crt0.c ├── libc.c ├── libc.h ├── memory.c // code de l'allocateur first-fit ├── memory.h // prototype de l'allocateur ├── thread.c ├── thread.h // prototype et structure thread_t └── user.ld }}} == B.1. Transformer l'allocateur first-fit et allocateur next-fit L'allocateur first-fit parcourt la liste des blocs depuis le tout premier jusqu'à la fin à la recherche du premier bloc non plein assez grand pour l'objet à allouer. Pour transformer ce comportement en next-fit, il suffit de se souvenir du dernier bloc alloué. Ce changement est une petite optimisation, parce qu'on évite le parcours des blocs qui sont au début du heap et si le heap est plein de petits blocs occupés alors ce parcours peut être long. Dans le code ci-après, on peut voir la fonction `try_malloc()` appelée par la fonction `malloc()`. On voit que les blocs sont parcourus depuis `Heap.beg` le premier bloc jusqu'au dernier `Heap.end` (qui n'est pas vraiment un bloc, mais une frontière). Lisez le code et trouvez comment recommencer le prochain `try_malloc()` à partir de dernier bloc alloué. Ce n'est pas très difficile, mais il faut comprendre le code. **ulib/memory.c** {{{#!c static size_t CacheLineSize; // cache line size set by malloc_init() typedef struct block_info_s { // small structure always put at the beginning of each blocks unsigned full:1; // 1 full, 0 free (means empty) unsigned magic:7; // MAGIC_HEAP : magic number to check the corruption unsigned size:24; // Number of block_info to the next block_info } block_info_t; static struct heap_s { // user Heap block_info_t *beg; // Heap beginning block_info_t *end; // Heap end } Heap; // C Macros to align a pointer p to the current cache line address or the next one // For example, let the CacheLineSize is 0x10 Bytes (4 int), then // if p = 0x76543214 then LINE_FLOOR(p) = 0x76543210 and LINE_CEIL(p) = 0x76543220 #define LINE_FLOOR(p) (block_info_t *)FLOOR((size_t)(p),CacheLineSize) #define LINE_CEIL(p) (block_info_t *)CEIL((size_t)(p),CacheLineSize) #define BINFO_SZ sizeof(block_info_t) static void* try_malloc (size_t size) { size = CEIL (size+BINFO_SZ, CacheLineSize); // true required size in bytes size = size / sizeof (block_info_t); // in the heap size is in block_info_t block_info_t *oldnext, *newnext, *new; for (new = Heap.beg; // from the beginning of the Heap (new < Heap.end) && (new->full||(new->sizesize); // go to next block if (new > Heap.end) return NULL; // end reached without finding space new->full = 1; // space found, we put the block oldnext = new + new->size; // next block address before the cut newnext = LINE_CEIL(new+size); // find the new next block if (newnext != oldnext) { // if we need to cut the find block new->size = newnext - new; // new size of current block new->magic = MAGIC_HEAP; // to try detect Heap corruption newnext->size = oldnext - newnext; // new size of remaining space newnext->full = 0; // that is free space newnext->magic = MAGIC_HEAP; // to try detect Heap corruption } return (void *)(new + 1); // the allocated block after block_info } void * malloc (size_t size) { block_info_t *ptr = try_malloc (size); // Search for a block if (ptr == NULL) { // if no free space merge (Heap.beg); // merge all free blocks from the beginning. ptr = try_malloc (size); // try again to find a block } return ptr; // return what you have found } }}} == B.2. Transformer l'allocateur first-fit en allocateur best-fit Plus difficile, passer l'allocateur en best-fit. L'idée, c'est de ne pas toucher aux chaînages des blocs utilisés par first-fit. Il faut créer un second chaînage ordonné par taille des blocs libres en utilisant l'API `list` et l'utiliser pour trouver le bloc de la bonne taille. Il y a pleins de détails à régler, par exemple, décider de ce fait qu’on lors d'un ''merge'' des blocs libres parce que cela va impacter la liste ordonnée des blocs libres. Les maillons de ce second chaînage sera mis dans les blocs eux-mêmes, juste après le block_info. En fonction de votre niveau de programmation en C et de votre niveau de compréhension de l'algorithme, cela peut vous prendre de 1h à beaucoup... alors ce n'est vraiment pas important d'aller jusqu'au code. Par conséquent, je ne vous demande pas d'écrire le code, sauf si vous avez le temps et la motivation. En revanche, vous pouvez réfléchir à la manière de procéder et la décrire dans votre compte rendu. == B.3. Tester que les piles n'ont pas débordé Vous savez peut-être que dans un processeur disposant d'un mécanisme permettant à chaque application d'avoir son propre espace d'adressage (espace d'adressage virtuel), les accès à la mémoire passe par un composant de traduction d'adresses nommé **MMU** pour traduire les adresses virtuelles de l'application en adresses physiques de l'espace d'adressage physique où se trouvent les segments de mémoire physique (gérés par les bancs de mémoire). L'un des rôles de ce composant **MMU** (Memory Management Unit) est de tester la légalité des accès à la mémoire. Si le noyau attribue un segment d'adresses à une application. Si l'application tente d'accéder en dehors de ce segment, la MMU le détecte et prévient le noyau par une exception. C'est l'erreur fatale ''Segmentation Fault'' que vous avez certainement déjà eue. Le SoC **almo1** n'a pas de MMU, donc pas de gestion de mémoire virtuelle, toutefois nous voulons tester que les segments d'adresses définis pour les deux piles de threads ne débordent pas. Pour ce faire, les deux piles de threads (user et kernel) ont des nombres magiques (`MAGIC_STACK`) dans leur premier et dernier mot. Ces mots ne devraient jamais être écrasés, si cela se produit, c'est que les piles ont été corrompues ou qu'elles ont débordé. L'idée est de tester à intervalle régulier que les nombres magiques sont toujours présents, par exemple lors des changements de threads. C'est un bon moment parce qu'on peut tester que les piles du thread sortant n'ont pas débordé pendant son exécution et que les piles du thread entrant sont correctes avant de lui donner un cœur. **kernel/kthread.c** La fonction `sched_switch()` est la fonction de l'ordonnanceur de thread qui réalise le changement de thread. Dans cette fonction, `ThreadCurrent` est le pointeur sur la structure `kthread_t` du thread courant, c'est-à-dire, d'abord le thread sortant puis le thread entrant (2e instruction du `if`). {{{#!c static void sched_switch (void) { int th_curr = ThreadCurrentIdx; // get the current thread index int th_next = sched_elect (); // get a next ready thread if (th_next != th_curr) { // if it is not the same if (thread_save (ThreadCurrent->context)){ // Save current context, and return 1 ThreadCurrentIdx = th_next; // update ThreadCurrentIdx ThreadCurrent = ThreadTab[th_next]; // update ThreadCurrent thread_load (ThreadCurrent->context); // load context & exit from thread_save } // but with 0 as return value } ThreadCurrent->state= TH_STATE_RUNNING; // the chosen one is RUNNNIG } }}} Ajouter les lignes nécessaires pour tester la présence des nombres magiques, sinon c'est la panique :-) Vous pouvez utiliser la macro `PANIC_IF(cond,fmt,arg...)` qui, si `cond` est vrai, affiche un message définit par `fmt` et `arg...` et stoppe l'application par l'appel de `kpanic()`. Par exemple: {{{#!c PANIF_IF( A != 3 , "Argh, A is not equal to 2, it is %d", A); }}} == B.4. Faire en sorte que les listes d'objets libres du noyau ne retombent à 0 Si on alloue un objet d'une taille T et que la liste des objets libres de taille T est vide alors on ouvre un slab (on l'alloue). Si on libère l'objet de taille T, alors le slab est entièrement libre et on ferme le slab (on le libère). Si on fait ça en boucle, l'ouverture/fermeture (allocation/libération) des slabs est une perte de temps. Il est sans doute préférable d'avoir toujours des listes d'objets libres non vides. On peut donc définir un seuil d'objets libres en dessous duquel ne pas descendre. Dans le fichier `kernel/kmemory.c`, on peut voir qu'il existe un tableau `Objects[]` contenant autant de cases qu'il existe de taille d'objets possibles (mesurée en nombre de lignes) et dont chaque case contient le nombre d'objets alloués de cette taille. Ce tableau a 256 cases au maximum (si la ligne de cache fait 16 octets), la case 0 contient le nombre de pages allouées, la case 1 contient le nombre d'objets alloués d'1 ligne, la case 2 pour les objets de 2 lignes, etc. L'idée de ne pas demander la suppression de slab si le nombre d'objets occupé passe à 0. **kernel/kfree** {{{#!c void kfree (void * obj, size_t size) { size_t nbline= NBLINE(size) % MaxLinePage; // which slab to use size_t npage = (size_t)(obj - (void *)kmb)>>12; // relative page number from kmb PANIC_IF ((nbline>255)||(npage >= NbPages), // too big or outside of the region "\ncan't free object not allocated by kmalloc()"); // write a message then panic list_addfirst (&Slab[nbline], (list_t *)obj); // add it to the right free list Objects[nbline]--; // decr the number of obj of size nbline if (size == PAGE_SIZE) return; if (--Page[npage].alloc==0) { // splitted page and no more object left list_t *page = (list_t *)((size_t)obj & ~0xFFF); // address of the page containing obj list_foreach (&Slab[nbline], item) { // browse all item in free list size_t np_item = (size_t)((char*)item-kmb)>>12; // page number Page[] table if (np_item == npage) { // if current item is in the page list_unlink (item); // unlink it } } Page[npage].slab = 0; // since the page is empty, thus slab 0 list_addfirst (&Slab[0], (list_t *)page); // add the free page in slab[O] Objects[0]--; // decr the number of pages used } } }}} **Explication de l'usage du tableau `Page`** :\\Le tableau `Page[]` est un tableau de structures dont chaque case contient l'usage de la page : pour quel slab la page est utilisée et combien d'objets y sont alloués. Lors de la libération d'un objet du noyau par `kfree()`, l'allocateur remet l'objet dans la liste des objets libres de sa taille (le tableau de listes `Slab[]`) et il décrémente le compteur d'objets présents dans la page `--Page[npage].alloc` (`npage` identifie la page). Si la page ne contient plus d'objet alloué alors `kfree()` recherche les objets libres de même taille qui sont dans la page `npage` alors il les retire. Ensuite la page est libérée.\\Vous n'avez pas à changer ce fonctionnement, ce qu'il faut c'est ne pas l'invoquer si le nombre d'objet libre est en dessous d'un seuil.