Réécriture de malloc

02 août 2024 г.

Table des matières

Partie obligatoire

Réécrire les fonctions malloc, free, et realloc.

Écrire aussi une fonction show_alloc_mem pour afficher les allocations de mémoire.

Comme le vrai malloc, la mémoire allouée doit être stockée dans des “zones” pré-allouées (bacs), sauf si la taille demandée est trop grande, auquel cas l’allocation doit être fitted.

Note
Les allocations fitted sont des allocations qui sont en dehors d’un bac, ce qui signifie qu’elles sont allouées directement avec un appel à mmap.

Deux types de zones sont nécessaires :

zones Tiny de taille N, stockant les allocations de taille 0 à n.
zones Petites de taille M, stockant les allocations de taille n+1 à m.
Grandes allocations, allocations fitted à partir de m+1.

La taille des zones doit être un multiple de la taille de page, déterminée par sysconf(_SC_PAGESIZE). Les allocations (et les allocations internes requises) doivent être exécutées avec mmap, les désallocations avec munmap.

Partie Bonus

Rendre les fonctions obligatoires thread-safe.
Impression d’informations supplémentaires (dump mémoire, historique des allocations…) par le biais de flags ou de fonctions supplémentaires.
Bacs dé-fragmentation des bacs
Flags de debug.

Explication du code de la partie obligatoire

Légèrement inspiré du malloc de la glibc de Debian.

Important
Lorsque les mots relatifs à l’allocation sont mis entre guillemets, ça signifie qu’il ne s’agit pas nécessairement d’une allocation. L’attribution d’une partie d’un bac n’est pas une allocation ; une allocation fitted est, elle, bien une allocation.

Puisque la plupart des explications ne sont pas liées à des allocations de mémoire réelles faites avec mmap, elles s’appliquent à des “allocations” bac ou fitted. Le fait qu’il s’agisse d’une attribution ou d’une allocation ne change pas la façon dont elle est organisée.

Explication brève de l’alignement mémoire

L’ordinateur lit la mémoire par sections de 4/8 octets, ou 32/64 bits ; ça détermine le nom de l’architecture.

Aligner la mémoire signifie placer les variables au début des sections de 4/8 octets. Si ce n’est pas respecté, ça cause :

Violation de contrainte : Une erreur d’alignement interrompt l’exécution des instructions.
Alignement non optimal : Deux fois 4 octets bien alignés sont lus, puis les 4 octets mal alignés sont extraits de ces 8 octets, ce qui prend plus de temps que la lecture de 4 octets bien alignés.

En prenant ça en compte, c’est pourquoi les compilateurs alignent automatiquement la mémoire lorsque c’est possible en remplissant la mémoire avec des char. Lorsque les champs d’une structure ne sont pas positionnés correctement ou que la taille totale d’une structure n’est pas un multiple de 4/8, elle prendra plus de mémoire qu’elle ne le devrait, à cause du remplissage.

Cependant, lors de l’attribution “libre” de valeurs en mémoire, il est nécessaire de faire attention à l’alignement afin d’éviter des ralentissements inutiles.

Chunks

Chaque “allocation” de mémoire (bac ou fitted) est précédée d’un en-tête. La combinaison d’une “allocation” de mémoire (données) et de son en-tête s’appelle un chunk.

L’en-tête contient les informations suivantes :

Taille de l’allocation (unsigned long).
Taille réelle de l’allocation (unsigned long).
Pointeur vers le chunk suivant (void *).
Pointeur vers le chunk précédent (void *).

Pour un total de 16/32 octets sur les architectures 32/64 bits. La structure elle-même est alignée sur la mémoire, le début des données est donc également aligné. La taille des données est toujours fixée à un multiple de 16, ce qui force l’alignement de la mémoire sur toutes les architectures.

La taille des données est souvent supérieure à ce qui a été demandé, afin de maintenir l’alignement de la mémoire. La partie des données qui correspond à la taille demandée par l’utilisateur (taille réelle) est appelée données fournies, le reste est appelé queue.

Pour résumer, voici comment un chunk est organisé en mémoire :

Section	Données stockées	Type de données
En-tête	Taille des données (size)	`unsigned long`
En-tête	Taille des données fournies (real_size)	`unsigned long`
En-tête	Pointeur sur le chunk suivant (next)	`void *`
En-tête	Pointeur sur le chunk précédent (prev)	`void *`
Données	Données fournies	Pas pertinent
Données	Queue	Pas pertinent

La taille des données fournies n’est utilisée que pour les informations de debug et pour show_alloc_mem.

Avantages et inconvénients

L’avantage de l’overhead plutôt qu’un carnet d’adresses exporté est qu’il est plus rapide de récupérer les données liées à un chunk avec un pointeur (dans free ou realloc par exemple), puisqu’il suffit de soustraire la taille de l’en-tête du pointeur pour récupérer son en-tête.

Il prend également moins de place puisqu’il ne contient pas de pointeurs sur les données.

Il nécessite également moins d’appels à mmap (qui sont assez lents) puisqu’il n’est pas alloué ailleurs ; les données et l’en-tête sont alloués en un seul appel.

L’inconvénient est qu’en cas d’écriture en dehors des limites des données fournies, ça pourrait corrompre les données d’en-tête et donc ruiner malloc… Mais personne n’est censé écrire en dehors des limites, n’est-ce pas ?

Bacs

De la même manière qu’un chunk, les bacs ont un en-tête qui les précède. Les seules différences sont que la taille correspond à la taille complète de la zone, en-tête inclus, que le champ de taille réelle n’est pas utilisé, et que les pointeurs pointent vers les bacs au lieu des chunks.

malloc

Lors de l’appel à malloc, si la taille n’est pas trop élevée pour un bac (auquel cas il effectue simplement une allocation fitted), malloc va itérer dans le bon bac (correspondant à la taille demandée) et trouver un chunk libre de la bonne taille. Ça permet d’éviter la fragmentation des bacs. S’il atteint la fin d’un bac et qu’il reste suffisamment d’espace dedans, il attribue un chunk dans le bac. S’il n’y a pas assez d’espace dans le bac, il en crée un nouveau.

Si la taille totale de plusieurs chunks contigus libre correspond à la taille du nouveau chunk, ils seront réunis en un seul chunk, encore une fois pour éviter la fragmentation.

free

Lors de l’appel à free, si la taille n’est pas trop élevée pour un chunk (il suffit alors de unmap le chunk et de modifier les pointeurs next/prev), il vérifiera si le chunk fourni se trouve à la fin d’un bac. Si c’est le cas, le chunk sera désattribué, puis il itère vers l’arrière pour trouver des chunks contigus afin de les désattribuer. Ça permet d’éviter la fragmentation du bac.

Si le bac est vide, il est désalloué pour réduire l’empreinte mémoire du programme.

realloc

Lors de l’appel à realloc, si la taille n’est pas trop élevée pour un bac (ce qui sera abordé dans quelques lignes), quelques vérifications sont effectuées :

Si la nouvelle taille est égale à la taille réelle actuelle, il retournera simplement le pointeur fourni.
Si la nouvelle taille est inférieure à la taille réelle actuelle, il ajustera la taille réelle du chunk et retournera le pointeur fourni.
Si elle est supérieure à la taille réelle actuelle, mais inférieure à la taille des données du chunk, il ajustera la taille réelle du chunk et retournera le pointeur fourni.

Dans les deux cas précédents, si le chunk se trouve à la fin d’un bac, le chunk sera étendu (s’il reste assez d’espace) ou tronqué pour s’adapter à la nouvelle taille.

Si la nouvelle taille est supérieure à la taille des données du chunk (ou à la taille restante du bac s’il se trouve à la fin d’un emplacement), il stockera les données du chunk dans un tampon, libérera le chunk, appellera malloc pour obtenir un nouveau chunk, et copiera le tampon dans les données du nouveau chunk.

De la même manière, si la taille est trop grande pour un bac (fitted), il essaiera d’étendre ou de réduire le chunk avec mmap. Si ça fonctionne, la taille du chunk et la taille réelle sont modifiées en conséquence et le pointeur fourni est retourné. Si ça ne fonctionne pas, il copiera les données du chunk dans le nouveau chunk et retournera un pointeur vers les données du nouveau chunk.

Explication du code de la partie bonus

Aucun des bonus ne nécessite vraiment d’explication, à part éventuellement la dé-fragmentation.

La prévention de la fragmentation est déjà couverte dans la partie obligatoire (honnêtement, pour faire ce bonus, il est recommandé de coder la partie obligatoire en pensant dès le départ à la dé-fragmentation).

Rendre la librairie thread-safe n’est pas si difficile ; l’implémentation la plus simple est de verrouiller/déverrouiller un mutex avant chaque appel des fonctions exposées. Ça pourrait éventuellement être optimisé, mais ce serait pour un gain minime à mon échelle.

Parce que c’est plus sympa, j’ai ajouté des macros pour exclure la logique thread-safe au moment du build lorsqu’elle n’est pas nécessaire.

J’ai également ajouté des informations de debug sur show_alloc_mem ajoutables lors du build avec un flag spécifique, il imprime un dump des chunks, ainsi que plus de détails sur les tailles des chunks et des bacs.