Malloc : pourquoi faire un free après un malloc?

Malloc : pourquoi  faire un free après un malloc?

A EPITECH, au cours du 4ème semestre on réalise des projets d'envergures en programmation système en langage C. L’un d’entre eux m’a particulièrement marqué, c’est malloc.

Malloc, nous l’avons souvent utilisé dans "la piscine C" pour recoder la fonction strdup et dans bien d’autres projets. Je savais plus ou moins à quoi il servait mais de là à le recoder …

En plus, pour ajouter à la difficulté, je n’avais que très peu d’informations, même sur internet on ne trouvait pas grand-chose d’utile.

Ce que vous allez lire est une ébauche du fonctionnement général de malloc et le fruit de ma réflexion personnelle sur ce projet.

Évidemment, vous n’aurez pas la solution pour coder malloc. En tous cas, pour vous attaquer à malloc, il vous faudra connaitre tous les concepts du langage C notamment les pointeurs, les listes chainées et le fonctionnement de la mémoire sous UNIX.

 

Qu’est ce que malloc ?

void * malloc ( size_t size );

Malloc est une fonction de la libc qui permet d’allouer dynamiquement de la mémoire. En effet, sans cette fonction il serait impossible d’allouer la mémoire nécessaire au traitement des données. Cependant, le mécanisme d’allocation de mémoire est véritablement réalisé par la fonction sbrk.

 

Qu’est ce que sbrk ?

void * sbrk(intptr_t increment);

La fonction sbrk augmente l’espace d’adressage de n octets à chaque appel. C’est aussi une fonction de la libc C’est grâce à elle que l’allocation de mémoires est réellement possible.

Par conconséquent, malloc est un algorithme qui permet de gérer des blocs de mémoires dans un espace d’adressage alloués par sbrk.

 

Que fait réellement malloc alors ?

Malloc gère la mémoire allouée sous forme de blocs et fait appel à sbrk (le plus rarement que possible) quand il a besoin de plus d’espace mémoires.

En gros, lors d’une demande d’allocation mémoire, malloc regarde dans une liste si un bloc de la taille demandée est disponible pour le restituer. Cela, afin d’éviter de faire appel à sbrk.

En effet, il faut savoir que sbrk est une fonction très lourde qu’il faut éviter d’appeler. Cependant, si la taille du bloc que souhaite allouer malloc n’est pas disponible dans la liste, il fait appel à sbrk.

Ce dernier (sbrk) va donc augmenter l’espace d’adressage afin de permettre le stockage d’un nouveau bloc mémoire de n octets.

 

Malloc permet d’optimiser l’utilisation d’sbrk.

Illustration

Imaginez que vous ayez un espace mémoire de 1024ko préalablement alloué par sbrk et divisé en 4 blocs de 256octets non alloués (A, B, C et D) comme ci-dessous :

Allocation mémoire

On fait un malloc(256), malloc renvoie l’adresse d’un bloc de 256octets disponible. L’adresse de A est alors retournée et il devient indisponible dans la liste.

On fait un malloc(256) à nouveau, malloc renvoie l’adresse du bloc B et B est alors occupé.

On fait un malloc(256) de nouveau, malloc renvoie l’adresse du bloc C et C est alors occupé.

On fait encore un malloc(256), malloc renvoie l’adresse du bloc D et D est alors occupé.

Et encore un malloc(256). Malloc regarde dans sa liste et constate qu’il n’y a plus de blocs de 256octets de disponibles. Il fait donc appel à sbrk. Cependant, nous verrons plus en détail ce que fait malloc quand il fait appel à sbrk.

Par ailleurs,  tout le mécanisme de la gestion de la mémoire ne serait rien si on ne pouvait pas libérer de la mémoire. C’est pour cela qu’en parallèle on utilise la fonction free.

 

C’est quoi free ?

Free permet de libérer de la mémoire qui a été allouée. En principe, après usage de la mémoire, celle-ci doit être immédiatement libérée par free.

Observons ensemble son prototype :

 void free(void *ptr);

La fonction free prend en paramètre un pointeur sur le bloc de mémoire alloué et le libère.

 

Comment free libère la mémoire ?

En fait, free ne libère pas vraiment de la mémoire. Il va  tout simplement mettre dans une « freelist » l’adresse du bloc qui a été libéré. Ainsi la mémoire qui a été libérée pourra à nouveau être réutilisée.  Et, c’est de cette manière que la notion de gestion de mémoire prend tout son sens.

Démonstration de libération et d’allocation de mémoire

Imaginez cette fois une zone mémoire immense de 2^32 octets (4Go sous freeBSD) et une freelist vierge qui ne contient aucun bloc.

Malloc, au moment de la toute première demande d’allocation mémoire, vérifie dans cette freelist s’il n’y a pas déjà un bloc de la taille demandée disponible.

Évidemment, comme c’est la toute première demande d’allocation, il n’y a aucun bloc mémoire de disponible dans cette freelist. Malloc demande donc à sbrk de lui augmenter l’espace d’adressage pour stocker un nouveau bloc mémoire.

Admettons que sbrk alloue 1024ko lors de la première demande d’allocation. Nous aurons donc un espace de 1024ko pour stocker les futurs blocs mémoires comme ci-dessous :

Reprenons notre exemple précédent, nous nous étions arrêtés alors que tous les blocs avaient été alloués :

A = malloc(256) ;  B = malloc(256) ;  C = malloc(256) ; D = malloc(256) ;

E= malloc(256) ??? Que se passe t'il ??? Il  n'y a plus de blocs libres à allouer... Que fait malloc ?

Malloc regarde dans la freelist et constate qu’il n’y a plus de blocs de 256 octets de disponibles. Il fait donc appel à sbrk. Que se passe-t-il alors ? Ceci :

Malloc a demandé à sbrk de lui allouer un espace supplémentaire de 1024ko parce qu’il n’avait plus d’espace pour stocker le bloc E. En tout, nous avons maintenant un espace d’adressage de 2 * 1024ko soit 2048ko avec 5 blocs de 256 octets qui sont alloués.

Il nous reste donc  2048 – 5*256 soit 768 octets d’espace disponible pour stocker d’autres blocs mémoires.

Supposons maintenant que nous souhaitons libérer le bloc C. Nous faisons free(C), la zone d’adressage ressemble à cela :

En suite le bloc A, free(A) :

Puis nous souhaitons allouer 256 octets, malloc(256) :

Nous constatons que l’adresse du bloc A à de nouveau été renvoyée pour être réutilisée. Donc malloc lors d’une demande d’allocation de mémoire recherche d’abord dans sa freelist un bloc de la taille demandée avant d’appeler sbrk.

Par ailleurs, ceci est une piste de réflexion pour recoder la fonction malloc. Il y a donc plusieurs algorithmes qui partent du même principe.

Entre autres, je vous conseille vivement de lire les pages de ‘’man’’ de malloc et de free, de comprendre le mécanisme de la mémoire, de bien comprendre les pointeurs et les listes chainées en C.

En conclusion, le fait de ne pas avoir d’informations et de devoir aller les chercher m’a permis de comprendre le fonctionnement de la gestion de la mémoire.

Et j’ai compris maintenant pourquoi on nous bassine à faire un free après un malloc, j’espère que vous aussi ! Je vous dis à très bientôt pour un nouveau numéro ^^ !

 

Quelques sources :

http://www.cs.utk.edu/~huangj/cs360/360/notes/Malloc1/lecture.html

http://www.cs.utk.edu/~huangj/cs360/360/notes/Malloc2/lecture.html

 

0

Dites ce que vous pensez, laissez un commentaire !