Heap Allocator

Allocateur de mémoire en c

Écriture d'un allocateur de mémoire

Extrait pour un allocateur de mémoire en C

Allocateurs de mémoire 101 - Écrivez un allocateur de mémoire simple

Choses à considérer

• Alignement de la mémoire - rembourrage

Fonctions pour implémenter le plus haut niveau

 void * malloc ( size_t size );
void free ( void * ptr );
Block * merge_blocks ( Block * block );
// the above three will be implemented first later calloc and realloc 

Étapes à mettre en œuvre

• void initialize_allocator (size_t size)
  • Cette fonction sera appelée la première fois lorsqu'une demande d'allocation de mémoire sera envoyée. Il créera un grand bloc avec une certaine taille.

Détails de haut niveau de Chatgpt

1. Définissez la structure des données : vous aurez besoin d'une structure de données pour garder une trace de la taille et de l'état d'allocation de chaque bloc. Cela pourrait être une structure simple avec une taille et un drapeau indiquant si le bloc est libre ou non.

2. Initialisez le tas : lorsque votre programme commencera, vous devrez réserver un morceau de mémoire pour agir comme votre tas. Cela peut être fait en utilisant l'appel système mmap() .

3. Implémentez malloc() : Cette fonction doit trouver un bloc gratuit suffisamment grand pour satisfaire la demande. S'il n'existe pas de tel bloc, il devrait augmenter la taille du tas. Une fois qu'un bloc approprié est trouvé, il doit être marqué comme alloué et son adresse est retournée.

4. Implémentez free() : Cette fonction doit prendre un pointeur vers un bloc de mémoire, le marquer comme libre et potentiellement réduire la taille du tas si le bloc libéré est à la fin.

5. Implémentez realloc() : Cette fonction doit redimensionner un bloc alloué. Cela pourrait impliquer de trouver un nouveau bloc et de copier les anciennes données.

6. Gandage Fragmentation : Au fil du temps, le tas peut se fragmenter avec des blocs libres dispersés partout. Vous voudrez peut-être mettre en œuvre une stratégie pour défragmenter le tas, comme la fusion de blocs libres adjacents.

Pourquoi les blocs?

Dans le contexte d'un allocateur de tas, les "blocs" se réfèrent à des morceaux de mémoire dans le tas. Voici pourquoi vous en avez besoin et comment ils fonctionnent:

1. Pourquoi les blocs? : Lorsque vous gérez de la mémoire, il est utile de le diviser en morceaux gérables ou des "blocs". Chaque bloc peut être alloué et traité indépendamment. Cela permet une utilisation efficace de la mémoire, car vous pouvez allouer exactement autant de mémoire que vous en avez besoin, ni plus ni moins.

2. Structure du bloc : chaque bloc contient généralement des métadonnées autour du bloc (comme sa taille et si elle est gratuite ou allouée) et les données réelles stockées dans le bloc. Les métadonnées sont utilisées par l'allocateur pour gérer la mémoire.

3. Attribution : Lorsque vous appelez malloc() , l'allocateur recherche un bloc gratuit suffisamment grand pour contenir la quantité de données demandée. S'il en trouve un, il marque ce bloc comme alloué et renvoie un pointeur à la partie de données du bloc.

4. Deallocation : Lorsque vous appelez free() , l'allocateur marque le bloc comme gratuit, ce qui le rend disponible pour les allocations futures. Si le bloc libéré est à la fin du tas, l'allocateur peut également réduire la taille du tas pour libérer la mémoire.

5. Fragmentation : Au fil du temps, car les blocs sont alloués et traités, le tas peut se fragmenter. Cela signifie que la mémoire libre est divisée en petits blocs non contigus. Cela peut rendre difficile la recherche d'un bloc suffisamment grand pour un appel malloc() , même s'il y a suffisamment de mémoire libre totale. Pour gérer cela, les allocateurs incluent souvent la logique pour défragmenter le tas, comme la fusion de blocs libres adjacents.

Faire

1. Bug avec my_alloc. Si appelé plusieurs fois, le pointeur renvoie la même chose
2. Ajouter une libération de mémoire réelle de l'espace de processus, c'est-à-dire Munmap
   1. Actuellement, il y a un problème avec la fonction my_free. Le test pour lui renvoie un défaut SEG.
3. Comprendre et améliorer la pièce d'alignement / rembourrage des données. Alignement de la structure des données
4. Notre code est-il correct dans le sens des blocs qui ne sont pas créés d'une manière ou d'une autre là où les données pointées par le bloc devraient être.
5. Tests complets nécessaires pour le malloc