heap_allocator
1.0.0
Il s'agit d'un simple répartiteur de tas que j'ai écrit pour un système d'exploitation amateur sur lequel je travaille. J'ai écrit cet allocateur avec très peu de recherches, et il est conçu pour être aussi simple à comprendre que possible. Je pense que ce référentiel peut être utile à ceux qui sont nouveaux dans le développement de systèmes d'exploitation (comme moi) ou qui souhaitent voir une version simplifiée de fonctions comme malloc et free.
Il existe deux fichiers d'en-tête qui définissent le tas et la liste chaînée. pour compiler ce référentiel :
$ gcc main.c llist.c heap.c -o heap_test
$ ./heap_test
cela exécutera une démo de l'allocateur et imprimera des informations.
Afin d'initialiser ce tas, il faut prévoir une section de mémoire. Dans ce référentiel, cette mémoire est fournie par malloc (oui, en allouant un tas via un tas). Dans un paramètre de système d'exploitation, certaines pages devraient être mappées et fournies au tas (un scénario). Notez que les bacs de la structure heap_t ont également besoin de mémoire qui leur est allouée.
Lorsque la fonction init_heap est appelée, l'adresse de la structure de tas vide (avec les pointeurs bin alloués) doit être fournie. La fonction init_heap créera alors un gros morceau avec un en-tête (structure node_t ) et un pied de page (structure footer_t ). Pour déterminer la taille de ce morceau, la fonction utilise la constante HEAP_INIT_SIZE . Il l'ajoutera à l'argument start afin de déterminer où se termine le tas.
Chaque morceau de mémoire a une structure de nœud au début et une structure de pied de page à la fin. Le nœud contient la taille, que le morceau soit libre ou non, et deux pointeurs utilisés dans la liste doublement liée (suivant et précédent). La structure de pied de page contient simplement un pointeur vers l'en-tête (utilisé lors de la libération des morceaux adjacents). Le morceau à la fin du tas est appelé le morceau « sauvage ». Il s'agit du plus gros morceau et ses tailles minimale et maximale sont définies dans heap.h. contracter et agrandir le tas est aussi simple que de redimensionner cette partie sauvage. Des morceaux de mémoire libres sont stockés dans des "bacs", chaque bac n'est en fait qu'une liste doublement liée de nœuds de tailles similaires. La structure de tas contient un nombre défini de bacs ( BIN_COUNT dans tas.h). Pour déterminer dans quel bac placer un morceau, la taille du morceau est mappée à un index de bac par la fonction get_bin_index . Cette fonction de regroupement cohérente garantira que les morceaux peuvent être consultés et stockés de manière définie. Les morceaux sont triés au fur et à mesure qu'ils sont insérés dans les bacs, donc l'insertion des morceaux n'est pas O(1), mais cela facilite beaucoup la recherche des morceaux qui conviennent le mieux. Notez que la fonction de binning peut être définie comme l'utilisateur de ce tas se sent en forme. il peut être avantageux de déterminer une fonction de regroupement plus sophistiquée afin de faciliter la récupération rapide des morceaux.
La fonction heap_alloc prend l'adresse de la structure de tas à partir de laquelle allouer et une taille. La fonction utilise simplement get_bin_index pour déterminer où un morceau de cette taille DEVRAIT se trouver, bien sûr, il se peut qu'il n'y ait pas de morceau de cette taille. Si aucun fragment n'est trouvé dans le bac correspondant, le bac suivant sera vérifié. Cela continuera jusqu'à ce qu'un morceau soit trouvé, ou que le dernier bac soit atteint, auquel cas un morceau de mémoire sera simplement extrait du morceau sauvage. Si le morceau trouvé est suffisamment grand, il sera divisé. Afin de déterminer si un morceau doit être divisé, la quantité de métadonnées (surcharge) est soustraite de ce que notre allocation actuelle n'utilise pas. Si ce qui reste est supérieur ou égal à MIN_ALLOC_SZ , cela signifie que nous devons diviser ce morceau et placer les restes dans le bon bac. Une fois que nous sommes prêts à renvoyer le morceau que nous avons trouvé, nous prenons l'adresse du champ next et la renvoyons. Cela est dû au fait que les champs next et prev ne sont pas utilisés pendant qu'un morceau est alloué. L'utilisateur du morceau peut donc écrire des données dans ces champs sans affecter le fonctionnement interne du tas.
La fonction heap_free prend un pointeur renvoyé par heap_alloc . Il soustrait le décalage correct afin d'obtenir l'adresse de la structure du nœud. Au lieu de simplement placer le morceau dans le bon bac, les morceaux entourant le morceau fourni sont vérifiés. Si l’un de ces morceaux est libre, nous pouvons alors fusionner les morceaux afin de créer un morceau plus grand. Pour regrouper les morceaux, le pied de page est utilisé pour obtenir la structure de nœud du morceau précédent et la structure de nœud du morceau suivant. Par exemple, disons que nous avons un morceau appelé to_free . Pour obtenir le morceau avant ce morceau, nous soustrayons sizeof(footer_t) pour obtenir le pied de page du morceau précédent. Le pied de page contient un pointeur vers la tête du morceau précédent. Pour obtenir le morceau suivant, nous récupérons simplement le pied de page de to_free , puis ajoutons sizeof(footer_t) afin d'obtenir le morceau suivant. Une fois que tout cela est fait et que les tailles sont recalculées, le morceau est replacé dans un bac.
REMARQUE : ce code a été initialement compilé pour une machine 32 bits, cela signifie que lorsque ce code a été utilisé, il était acceptable de convertir un int en pointeur car ils ont tous deux la même taille. Sur un système 64 bits, le compilateur vous avertira de la différence de taille. Pour faire taire ces avertissements, j'ai utilisé uintptr_t lors de la conversion d'un entier non signé en un pointeur. Cela brouille un peu la lisibilité et certains transtypages et arithmétiques de pointeurs sont verbeux, alors gardez cela à l'esprit lors de la lecture du code.
