Note

Roadmap :

• reprendre les exemples en C en utilisant des int suite au changement dans le programme.

Remarque

Ce chapitre se concentre sur la manière dont un programme compilé gère la mémoire. Il est question, en particulier, de la notion de variable. Le modèle dans lequel on se place est celui du langage C où une variable est un emplacement mémoire.

Organisation de la mémoire

Note

Ici, je fais le choix d'une présentation assez informelle pour ne pas qu'elle soit trop liée à la réalité d'un compilateur en particulier.

Un programme compilé gère la mémoire d'un ordinateur de deux manières très différentes

• statiquement : c'est le cas des variables locales ou globales définies dans le programme. Au moment de la compilation, le compilateur dispose de l'information suffisante pour prévoir de la place en mémoire pour stocker ces données.
• dynamiquement : c'est le cas des objets dont la taille n'est connue qu'à l'exécution et peut varier selon l'état du programme. C'est alors au moment de l'exécution que le programme va faire une demande d'allocation pour obtenir une place mémoire.

En termes d'allocation statique, on peut distinguer plusieurs types de mémoire :

• les variables globales initialisées qui seront stockées dans le binaire et placées en mémoire dans une zone spécifique chargée avec le binaire
• les variables globales non initialisées dont seule la déclaration sera dans le binaire et qui seront allouées, placées en mémoire et initialisées à 0 au moment du chargement du binaire
• les variables locales et les paramètres qui sont placés dans une pile afin de les allouer uniquement au moment de l'exécution du bloc ou de la fonction

L'allocation dynamique utilise une zone mémoire appelée tas dont une possible organisation est développée dans la partie Réalisation d'un système d'allocation de mémoire.

Structure de la mémoire associée à un programme

Considérons le programme C suivant.

const int a  = 42;
int b[] = { 1, 2, 3 };
int c;

int f(int x, int y)
{
    int z = x;
    z = z * y;
    return z;
}

int main(int argc, char **argv)
{
    const int d = 1664;

    c = f(a, d);

    return 0;
}

Il est possible d'observer la manière dont sa mémoire sera répartie en utilisant la commande objdump :

$ gcc -c memoire.c
$ objdump -x memoire.o

memoire.o:     file format elf64-x86-64
memoire.o
architecture: i386:x86-64, flags 0x00000011:
HAS_RELOC, HAS_SYMS
start address 0x0000000000000000

Sections:
Idx Name          Size      VMA               LMA               File off  Algn
  0 .text         00000053  0000000000000000  0000000000000000  00000040  2**0
                  CONTENTS, ALLOC, LOAD, RELOC, READONLY, CODE
  1 .data         0000000c  0000000000000000  0000000000000000  00000094  2**2
                  CONTENTS, ALLOC, LOAD, DATA
  2 .bss          00000004  0000000000000000  0000000000000000  000000a0  2**2
                  ALLOC
  3 .rodata       00000004  0000000000000000  0000000000000000  000000a0  2**2
                  CONTENTS, ALLOC, LOAD, READONLY, DATA
  4 .comment      00000013  0000000000000000  0000000000000000  000000a4  2**0
                  CONTENTS, READONLY
  5 .note.GNU-stack 00000000  0000000000000000  0000000000000000  000000b7  2**0
                  CONTENTS, READONLY
  6 .eh_frame     00000058  0000000000000000  0000000000000000  000000b8  2**3
                  CONTENTS, ALLOC, LOAD, RELOC, READONLY, DATA
SYMBOL TABLE:
0000000000000000 l    df *ABS*  0000000000000000 memoire.c
0000000000000000 l    d  .text  0000000000000000 .text
0000000000000000 l    d  .data  0000000000000000 .data
0000000000000000 l    d  .bss   0000000000000000 .bss
0000000000000000 l    d  .rodata    0000000000000000 .rodata
0000000000000000 l    d  .note.GNU-stack    0000000000000000 .note.GNU-stack
0000000000000000 l    d  .eh_frame  0000000000000000 .eh_frame
0000000000000000 l    d  .comment   0000000000000000 .comment
0000000000000000 g     O .rodata    0000000000000004 a
0000000000000000 g     O .data  000000000000000c b
0000000000000000 g     O .bss   0000000000000004 c
0000000000000000 g     F .text  000000000000001f f
000000000000001f g     F .text  0000000000000034 main


RELOCATION RECORDS FOR [.text]:
OFFSET           TYPE              VALUE 
0000000000000042 R_X86_64_PLT32    f-0x0000000000000004
0000000000000048 R_X86_64_PC32     c-0x0000000000000004


RELOCATION RECORDS FOR [.eh_frame]:
OFFSET           TYPE              VALUE 
0000000000000020 R_X86_64_PC32     .text
0000000000000040 R_X86_64_PC32     .text+0x000000000000001f

On retrouve dans les sections mémoire :

• .text contenant le programme binaire
• .data contenant les variables globales initialisées et non constantes
• .bss contenant les variables globales non initialisées (ou initialisées à 0)
• .rodata contenant les variables globales initialisées mais constantes.

Ici, le schéma mémoire est un peu plus compliqué car une zone mémoire distincte est prévue pour les variables constantes initialisées pour des raisons de sécurité.

La pile et le tas sont automatiques et n'ont pas besoin de figurer dans le binaire, c'est pour cela qu'on ne les trouve pas dans la liste.

Dans cette description mémoire, on trouve la table des symboles qui décrit où vont se trouver en mémoire certaines variables.

Nom de variable	Sorte de déclaration	Section mémoire
a	constante globale initialisée	.rodata
b	globale initialisée	.data
c	globale non init.	.bss

La section suivante permettra de compléter le tableau en étudiant comment les paramètres et variables locales sont gérés. On remarque cependant qu'il n'y a pas de symboles pour ceux-ci. En effet, le nom des variables locales est a priori perdu après la compilation contrairement aux variables globales.

Pointeurs

Dans le modèle du C, une variable est un emplacement mémoire, et chaque emplacement mémoire possède une adresse : c'est le numéro de son premier octet. Une adresse est donc un simple entier, mais le C lui associe un type pour savoir comment interpréter ce qui s'y trouve.

Définition

Un pointeur est une valeur qui représente une adresse mémoire. Si T est un type, le type T * est celui des pointeurs vers une valeur de type T.

• Si x est une variable de type T, l'expression &x est l'adresse de x, de type T *.
• Si p est de type T *, l'expression *p désigne l'emplacement mémoire d'adresse p, vu comme une valeur de type T. On dit qu'on déréférence p.

#include <stdio.h>

int main(void)
{
    int x = 3;
    int *p = &x; // p contient l'adresse de x

    printf("adresse de x : %p, valeur pointée : %d\n", (void *)p, *p);
    *p = 4; // on écrit à l'adresse contenue dans p, donc dans x
    printf("x vaut maintenant %d\n", x);

    return 0;
}

Ce programme affiche par exemple :

adresse de x : 0x16bc467e0, valeur pointée : 3
x vaut maintenant 4

L'adresse affichée change d'une exécution à l'autre : x est une variable locale, placée dans la structure pile de main.

Remarque

• L'étoile joue deux rôles différents : dans une déclaration int *p, elle fait partie du type ; dans une expression *p, c'est l'opérateur de déréférencement. Attention, dans int *p, q; seule p est un pointeur, q est un int.
• *p peut être placé à gauche d'une affectation : *p = 4 modifie la mémoire pointée, pas p lui-même.
• Un pointeur est lui-même une variable, qui occupe 8 octets sur une architecture 64 bits, quel que soit le type pointé. On peut donc prendre son adresse : &p est de type int **.
• La valeur spéciale NULL (l'adresse 0) indique un pointeur qui ne pointe sur rien. La déréférencer est une erreur, voir la partie Protection mémoire.

Passage par adresse

En C, les paramètres d'une fonction sont passés par valeur : comme on l'a vu dans la partie Piles d'exécution, l'appel copie la valeur des arguments dans la structure pile de la fonction appelée. Modifier un paramètre ne modifie donc que cette copie.

Pour qu'une fonction puisse modifier une variable de l'appelant, on lui passe l'adresse de cette variable : c'est le passage par adresse. L'exemple classique est l'échange de deux variables.

void echange_faux(int a, int b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

void echange(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int main(void)
{
    int x = 1;
    int y = 2;

    echange_faux(x, y); // x = 1, y = 2 : seules les copies ont été échangées
    echange(&x, &y);    // x = 2, y = 1
    return 0;
}

Lors de l'appel echange(&x, &y), la structure pile de echange contient deux paramètres a et b qui sont des copies des adresses de x et de y. Ces adresses désignent des emplacements de la structure pile de main : *a = *b écrit donc directement dans x.

Remarque

C'est aussi ce mécanisme qui permet à une fonction de renvoyer plusieurs résultats, ou d'éviter de recopier une grosse structure en passant son adresse. On le retrouve dans scanf("%d", &n), qui doit écrire dans n.

Pointeurs et tableaux

Les éléments d'un tableau sont rangés de manière contiguë en mémoire. Dans presque toutes les expressions, un tableau t est converti automatiquement en l'adresse de sa première case &t[0].

On peut ajouter un entier à un pointeur : si p est de type T *, alors p + i est l'adresse située i cases de type T plus loin, c'est-à-dire i * sizeof(T) octets plus loin. C'est l'arithmétique des pointeurs. Par définition, t[i] est exactement *(t + i).

#include <stdio.h>

int somme(int *t, int n)
{
    int s = 0;
    for (int i = 0; i < n; i++) {
        s += t[i]; // identique à s += *(t + i);
    }
    return s;
}

int main(void)
{
    int t[4] = { 1, 2, 3, 4 };
    int *p = t; // t est converti en &t[0]

    printf("%d %d %d\n", *p, *(p + 2), p[3]);        // 1 3 4
    printf("%p %p\n", (void *)p, (void *)(p + 1));   // adresses distantes de 4
    printf("somme : %d\n", somme(t, 4));             // 10
    printf("somme de la fin : %d\n", somme(t + 2, 2)); // 7
    printf("%zu %zu\n", sizeof(t), sizeof(p));       // 16 8

    return 0;
}

Remarque

• Passer un tableau à une fonction revient donc à passer l'adresse de sa première case : le tableau n'est pas copié et la fonction peut le modifier. En revanche, sa taille est perdue, c'est pourquoi on passe toujours la longueur n en paramètre supplémentaire.
• Dans somme, sizeof(t) vaudrait 8, la taille d'un pointeur, et non la taille du tableau. C'est une erreur classique.
• L'appel somme(t + 2, 2) montre qu'on peut faire travailler une fonction sur une portion de tableau sans rien recopier.
• Un tableau n'est pas pour autant un pointeur : on ne peut pas écrire t = p, et sizeof(t) dans main donne bien 16 octets.
• Rien ne vérifie qu'un accès t[i] reste dans les bornes du tableau : un débordement lit ou écrit silencieusement dans une autre zone mémoire.

Pointeurs vers le tas

Les pointeurs sont indispensables pour l'allocation dynamique, présentée dans la partie suivante : la fonction malloc renvoie l'adresse d'une zone du tas, et la seule manière d'y accéder est de conserver ce pointeur. Contrairement à une variable locale, cette zone survit à la fin de la fonction qui l'a allouée, jusqu'à l'appel de free.

#include <assert.h>
#include <stdlib.h>

int *cree_tableau(int n, int v)
{
    int *t = malloc(n * sizeof(int));
    assert(t != NULL);
    for (int i = 0; i < n; i++) {
        t[i] = v;
    }
    return t;
}

int main(void)
{
    int *t = cree_tableau(5, 7);
    t[0] = 1;
    free(t); // c'est à l'appelant de libérer la zone
    t = NULL;
    return 0;
}

Erreurs classiques

Le compilateur ne vérifie pas qu'un pointeur désigne une zone valide. Les erreurs suivantes produisent un comportement indéterminé : le programme peut planter, afficher des valeurs absurdes ou sembler fonctionner normalement, ce qui les rend difficiles à détecter.

• Pointeur pendant (dangling pointer) : un pointeur vers une zone qui n'existe plus. C'est le cas d'un pointeur vers une variable locale d'une fonction terminée, dont la structure pile a été dépilée :

  int *adresse_locale(void)
  {
      int x = 42;
      return &x; // x disparaît avec la structure pile de l'appel
  }
  

  Le compilateur produit ici un avertissement. C'est aussi le cas d'un pointeur vers une zone du tas après son free, ce qui est plus sournois quand plusieurs pointeurs désignent la même zone :

  #include <stdlib.h>
  
  int main(void)
  {
      int *t = malloc(3 * sizeof(int));
      int *u = t; // u et t pointent sur la même zone
      free(t);
      u[0] = 1;   // u est un pointeur pendant
      return 0;
  }
  

• Double libération (double free) : appeler deux fois free sur la même adresse, ou appeler free sur une adresse qui ne provient pas de malloc. Des exemples sont donnés dans la partie Libération. Dans le système d'allocation réalisé plus loin, ce sont les assert de la fonction liberation qui détectent ces erreurs.

• Fuite mémoire : perdre le dernier pointeur vers une zone allouée avant de l'avoir libérée. La zone ne pourra plus jamais être libérée.

  int *t = malloc(3 * sizeof(int));
  t = malloc(5 * sizeof(int)); // la première zone n'est plus accessible
  free(t);
  

Remarque

• Une bonne habitude est d'affecter NULL à un pointeur juste après l'avoir libéré : une utilisation ultérieure provoque alors une erreur immédiate au lieu d'un comportement indéterminé, et free(NULL) ne fait rien.
• L'option de compilation -fsanitize=address de gcc et clang ajoute des vérifications à l'exécution. Le programme précédent s'arrête alors avec le message ERROR: AddressSanitizer: heap-use-after-free qui indique la ligne fautive. Sous Linux, elle signale aussi les fuites mémoire à la fin de l'exécution. Il est vivement conseillé de l'utiliser pendant la mise au point des programmes.

Portée d'un identificateur

En ce qui concerne une variable dans un programme, on peut définir deux notions d'apparence assez similaire.

D'une part la portée d'un identificateur qui correspond au texte du programme :

Définition

La portée d'un identificateur est définie par la zone du texte d'un programme dans laquelle il est possible d'y faire référence sans erreurs.

Remarque

Dans le langage C, un identificateur peut être utilisé dès sa déclaration mais tant que la variable n'est pas initialisée, le comportement n'est pas spécifié et il faut considérer cela comme une erreur. Le compilateur produit ainsi un avertissement quand on utilise le paramètre -Wall.

Dans le cas d'une définition, il est ainsi possible de faire référence à l'identificateur dans l'expression de son initialisation : int x = x. Ce cas est pathologique et le fait qu'on compte la ligne de déclaration dans la portée ne devrait pas inciter à écrire ce genre de code qui produira, de toute façon, une erreur avec les options -Wall -Werror sous clang (sous gcc, il faut ajouter l'option -Winit-self).

Dans le programme :

int a = 1;

int f (int x)
{
    int y = x + a;
    return y;
}

int g()
{
    int z = 3;
    return z + f(z);
}

La portée des identificateurs est :

Identificateur	Portée
a	1-13
x	3-7
y	5-7
f	3-13
g	9-13
z	11-13

Pour une fonction, afin de pouvoir écrire des fonctions récursives, l'identificateur est utilisable dès la fin de son en-tête, donc en particulier dans le corps de la fonction.

Comme la portée est une notion associée aux identificateurs, elle est indépendante de la notion de variables. Si on considère le programme suivant :

int f() 
{
    int i = 3;

    return i;
}

int g() 
{
    int i = 5;

    return i+1;
}

L'identificateur i a pour portée les lignes 3-6 et 10-13.

Un autre phénomène plus complexe peut se produire quand on redéfinit un identificateur dans sa portée.

Considérons le programme suivant

int f() 
{
    int i = 3;

    for (int j = 0; j < 3; j++) 
    {
        int i = 4;

        i += j;
    }

    return i;
}

Ici, l'identificateur i a pour portée les lignes 3-13 mais dans les lignes 7-10 il y a un phénomène dit de masquage où la première définition est cachée par la seconde.

L'identificateur associé à une variable globale a pour portée l'ensemble des lignes allant de sa déclaration à la fin du fichier.

Remarque

En C, la portée d'un identificateur est statique : elle dépend uniquement du texte du programme au moment de la compilation.

En Python, la portée d'un identificateur est également déterminée par le texte du programme, mais le fait qu'un identificateur soit effectivement défini à un endroit donné peut dépendre de l'exécution. Par exemple si on considère le programme Python

if condition:
    x = 3

Utiliser x après ces lignes provoque une erreur (NameError) ou non selon que la condition est réalisée ou non : cette vérification n'a lieu qu'à l'exécution.

Piles d'exécution, variables locales et paramètres

On a vu qu'en raison de leur durée de vie, les variables globales étaient allouées dès le chargement du programme. Pour les variables locales ainsi que la mécanique des appels, on utilise une pile.

Cette pile d'exécution est représentée en mémoire par un tableau et un indicateur de sommet de pile (le pointeur de pile).

Le remplissage de ce tableau s'effectue souvent des adresses hautes vers les adresses faibles : on empile en faisant diminuer les adresses.

Remarque

En fait, il existe des architectures où les adresses sont croissantes. Ce qui importe est que le tas et la pile aient des comportements opposés pour qu'ils puissent grandir dans la même zone mémoire.

Un compilateur peut faire le choix d'utiliser directement des registres processeurs pour les variables locales ou pour passer des paramètres à une fonction. Ici, pour simplifier, on va supposer que ce n'est pas le cas et que tout passe par la pile d'exécution.

Remarque

Afin de pouvoir appeler une fonction dans une bibliothèque potentiellement compilée avec un autre compilateur, il est nécessaire d'avoir une convention d'appels de fonctions. Une telle convention est appelée une interface applicative binaire (Application Binary Interface).

La convention System V AMD64 ABI qui est celle de Linux et macOS sur des architectures x86 64 bits consiste à utiliser des registres entiers pour les six premiers arguments entiers ou pointeurs et des registres flottants pour les huit premiers arguments flottants. Les arguments suivants sont alors passés sur la pile (donc dès le septième entier/pointeur ou neuvième flottant).

La convention cdecl qui est assez répandue sur les architectures x86 32 bits consiste à utiliser la pile. Par contre la valeur de retour est présente dans des registres comme pour la convention System V AMD64 ABI.

Lors d'un appel d'une fonction passant par la pile, on commence par empiler les paramètres (souvent de la droite vers la gauche) puis on empile l'adresse à laquelle doit revenir l'exécution une fois que la fonction aura terminé son exécution.

Au début de l'exécution de cette fonction, on sauvegarde sur la pile l'adresse de base de la structure pile de l'appelant (registre ebp en 32 bits), puis on déplace le sommet de pile pour réserver de la place pour les variables locales.

L'empreinte sur la pile d'un appel de fonction est appelée une structure pile (stack frame en anglais). La pile est alors organisée, depuis l'appel au point d'entrée du programme, par empilement et dépilement de structures piles.

Structure pile associée à un appel de fonction

Voici un exemple possible de l'état de la pile d'exécution lors de l'exécution d'un programme compilé avec la norme cdecl (Il suffit d'ajouter l'argument -m32 pour compiler en 32 bits). Sur cette figure, le sommet de pile (adresses les plus faibles) est en haut et la structure pile de main est en dessous.

int f(int a, int b)
{
    int c = 3;
    /* pile ici après l'appel en l13 */
    c = c + b;
    c = c * a;
    return c;
}

int main()
{
    int x = f(10,12);
}

Bloc d'activation de l'appel f(10,12) sur la pile

À chaque appel de fonction, on va donc empiler une structure de pile complète, puis la dépiler à la sortie. Ce mécanisme est essentiel pour permettre la récursivité car il permet d'effectuer plusieurs appels d'une même fonction sans risquer que la mémoire utilisée lors d'un des appels interfère avec un autre. On comprend également les limites de la récursivité ici car cet empilement successif de structures de piles peut dépasser la taille maximale de la pile d'exécution : on parle alors de dépassement de pile ou stack overflow en anglais.

Remarque

Il est possible de définir des variables locales qui soient situées au même emplacement mémoire pour tous les appels d'une fonction, en les déclarant avec le mot-clé static : on parle de variables locales statiques.

Ce mécanisme est essentiellement géré comme les variables globales et il ne sera pas développé dans la suite.

Note

Je me demande s'il faudrait parler plus précisément de la manière dont la pile est gérée avec les registres ebp/esp. Mais ça ne me semble pas apporter grand chose ici.

Allocation dynamique

Comme cela a été vu dans la section Organisation de la mémoire, il est possible d'allouer dynamiquement de la mémoire. Pour gérer cette allocation dynamique, on passe par une zone mémoire appelée le tas ainsi que par un mécanisme d'allocation et de libération de mémoire au niveau du système.

Pour l'utilisateur, cette gestion interne est transparente et on peut se contenter de considérer qu'il y a deux mécanismes :

• l'allocation mémoire où on demande à ce qu'une zone mémoire d'une certaine taille soit allouée
• la libération mémoire où on signale que la zone mémoire peut être récupérée par le système.

Naturellement, la mémoire d'un ordinateur étant finie, il est très important de libérer au plus tôt la mémoire non utilisée pour éviter d'épuiser la mémoire. Quand un programme ne libère pas toute la mémoire qu'il alloue, on parle de fuite mémoire. L'empreinte mémoire d'un tel programme peut alors croître jusqu'à rendre le programme ou le système inutilisable.

Allocation

Pour allouer une zone mémoire, on utilise la fonction malloc dans stdlib.h de signature :

void *malloc(size_t size)

Ici size indique le nombre d'octets à allouer et la fonction renvoie un pointeur vers le premier octet alloué. Comme la fonction ne connaît pas le type d'objets alloués, on utilise ainsi le type void *.

Ce type joue un rôle spécial : une valeur de type void * est convertie implicitement vers n'importe quel type pointeur, on peut donc affecter directement la valeur de retour sans rien avoir à écrire d'autre que l'appel à malloc :

char *t = malloc(n);

Remarque

Dans le langage C++ qui peut être vu comme un successeur de C, il est obligatoire de préciser ici le nouveau type à l'aide d'un transtypage. Pour convertir la valeur x vers le type char * on écrit alors (char *)x. Ainsi, pour allouer un tableau de n caractères, on utilisera :

char *t = (char *) malloc(n);

Bien que ce ne soit pas nécessaire en C, il est fréquent de rencontrer des programmes présentant de tels transtypages qui sont superflus mais corrects syntaxiquement en C.

Pour obtenir la taille à allouer, il peut être utile d'utiliser l'opérateur sizeof qui prend en entrée un type ou une valeur et renvoie sa taille. Ainsi on peut allouer un tableau de \(n\) entiers non signés ainsi :

unsigned int *t = malloc( sizeof(unsigned int) * n );

et cet appel ne dépend pas de la taille prise par un unsigned int sur l'architecture.

Une autre raison de l'utilisation de sizeof est l'extensibilité. Par exemple, si on a un struct point représentant des points en 2D :

struct point {
    float x;
    float y;
};

on peut allouer un tableau de \(n\) points ainsi :

struct point *t = malloc( sizeof(struct point) * n );

Si jamais on change la structure pour représenter des points en 3D ainsi :

struct point {
    float x;
    float y;
    float z;
};

il sera inutile de changer le code d'allocation du tableau car sizeof(struct point) tiendra compte automatiquement du changement.

Si jamais une erreur empêche d'allouer la mémoire - ce qui peut être le cas s'il n'y a plus de mémoire disponible - le pointeur renvoyé par malloc a la valeur spéciale NULL.

Remarque

La zone mémoire renvoyée par malloc n'est pas initialisée. On ne peut pas supposer qu'elle soit remplie de la valeur 0. Il faut donc manuellement initialiser la mémoire après le retour de malloc.

Libération

Pour libérer la mémoire, on utilise la fonction free également présente dans stdlib.h et dont la signature est :

void free(void *ptr);

Remarque

Il est très important d'utiliser uniquement un pointeur obtenu précédemment par un appel à malloc (et pas encore libéré) et de ne pas l'utiliser plus d'une fois.

Le programme suivant provoque une erreur free(): invalid pointer à l'exécution mais est détecté par un avertissement du compilateur : warning: attempt to free a non-heap object ‘a’.

#include <stdlib.h>

int main()
{
    int a;
    free(&a);
    return 0;
}

Le programme suivant alloue un tableau de deux char et appelle free sur l'adresse de la seconde case. En faisant cela, il n'y a pas d'avertissement car on appelle free sur un objet qui est effectivement sur le tas. On obtient alors à nouveau une erreur à l'exécution free(): invalid pointer.

#include <stdlib.h>

int main()
{
    char *a = malloc(2);
    free(&(a[1]));
    return 0;
}

Le programme suivant libère deux fois la mémoire et provoque l'erreur free(): double free detected in tcache 2 à l'exécution.

#include <stdlib.h>

int main()
{
    char *a = malloc(2);
    free(a);
    free(a);
    return 0;
}

Protection mémoire

Comme on l'a vu dans la première partie, quand un programme s'exécute il a un environnement mémoire constitué de plusieurs zones, parfois appelées segments, avec le droit d'écriture dans certaines d'entre elles.

Le système d'exploitation protège ainsi la mémoire et, au niveau matériel, l'unité de gestion de la mémoire connait les adresses accessibles à un programme. En cas d'accès anormal, le matériel provoque une erreur qui remonte au système d'exploitation qui termine l'exécution du programme avec une erreur souvent intitulée Segmentation fault.

Voici quelques exemples commentés produisant des erreurs de type segmentation fault à l'exécution.

Lecture à l'adresse 0 (pointeur NULL), ce qui provoque en pratique toujours une erreur sur les systèmes usuels. Même problème avec une adresse inaccessible ou invalide.

int main()
{
    int *a = 0;

    return a[0];
}

Écriture dans une zone en lecture seule comme le segment du code.

int main()
{
    int *a = (int*) (&main);
    // a pointe sur le corps de la fonction main

    *a = 0;

    return 0;
}

Réalisation d'un système d'allocation de mémoire

Note

Prérequis : listes chaînées

Afin de comprendre comment fonctionne le tas, et en particulier malloc et free, on va simuler ici ce comportement en allouant une grande plage de mémoire avec malloc et en gérant le découpage et l'allocation de celle-ci.

Pour gérer les blocs mémoires libres, on utilise une liste circulaire. Une liste circulaire est une liste chaînée avec un lien supplémentaire entre le premier et le dernier maillon, ce qui fait qu'on peut considérer n'importe quel maillon comme étant la tête de la liste.

Une liste chaînée :

Ici le dernier maillon comprend un pointeur qui ne pointe sur rien indiqué par \(\times\), en pratique il a la valeur NULL.

Une liste circulaire :

Le seul changement est donc de faire pointer le dernier maillon sur le premier. Le fait d'avoir préservé les valeurs dans les maillons permet ici de voir ce qu'est devenu le premier maillon, mais on peut accéder à cette liste par n'importe lequel de ces maillons.

Les nœuds de la liste circulaire des blocs auront pour valeur un triplet (adresse,taille,libre) qui indique qu'à l'adresse adresse il y a un bloc de taille octets et le booléen libre indique si ce bloc a été alloué ou non.

Pour cela on commence par définir une structure bloc et une fonction de création d'un bloc :

struct bloc {
    void *adresse;
    uint32_t taille;
    bool libre;
    struct bloc *suivant;
};

struct bloc *cree_bloc(void *adresse, uint32_t taille, bool libre)
{
    struct bloc *b = malloc(sizeof(struct bloc));
    b->adresse = adresse;
    b->taille = taille;
    b->libre = libre;
    return b;
}

Ce code nécessite d'inclure stdlib.h, stdint.h (pour uint32_t) et stdbool.h (pour bool), ainsi que assert.h et stdio.h pour la suite.

On définit ensuite deux variables globales :

• blocs_libres qui va pointer sur un maillon de la liste circulaire des blocs
• plage_memoire qui pointe sur l'adresse de la plage mémoire que l'on va gérer et servira à la libérer en sortie de programme.

struct bloc *blocs_libres;
void *plage_memoire;

La fonction creation_blocs_libres permet de créer la liste circulaire avec un premier bloc qui pointe sur lui-même et qui correspond à l'adresse que l'on va placer dans plage_memoire.

void creation_blocs_libres(uint32_t taille_bloc_initial)
{
    plage_memoire = malloc(taille_bloc_initial);
    blocs_libres = cree_bloc(plage_memoire, taille_bloc_initial, true);
    blocs_libres->suivant = blocs_libres; // boucle initiale
}

Pour libérer la liste à la sortie du programme, on définit la fonction destruction_blocs_libres qui présente ainsi le parcours usuel d'une liste circulaire : on procède comme pour une liste chaînée classique mais, au lieu d'utiliser un test bloc_courant->suivant == NULL pour l'arrêt, il faut se souvenir du premier bloc et tester pour voir si on est revenu au point de départ. On n'oublie pas de libérer l'espace plage_memoire à la fin.

void destruction_blocs_libres()
{
    struct bloc *premier_bloc = blocs_libres;
    struct bloc *bloc_courant = premier_bloc;

    // on boucle pour libérer chaque maillon
    while (true) {
        struct bloc *bloc_suivant = bloc_courant->suivant;
        free(bloc_courant);
        if (bloc_suivant == premier_bloc) break;
        bloc_courant = bloc_suivant;
    }

    // on libère la plage mémoire initiale
    free(plage_memoire);
}

Pour allouer \(t\) octets, on parcourt la liste des blocs jusqu'à trouver un bloc \(b\) libre de taille \(b.t\) telle que \(b.t \ge t\). Si un tel bloc n'existe pas, on renvoie le pointeur NULL signe d'un échec d'allocation. Sinon, on indique que le bloc est occupé, on va renvoyer l'adresse du bloc obtenu mais, si \(b.t > t\) on insère après \(b\) un nouveau bloc libre de taille \(b.t - t\). Dans tous les cas, on fait pointer la liste des blocs libres vers le bloc qui suit \(b\), qui est peut-être le bloc nouvellement créé et a de grandes chances d'être libre.

Ce mécanisme est implémenté dans la fonction allocation :

void *allocation(uint32_t taille)
{
    struct bloc *premier_bloc = blocs_libres;
    struct bloc *bloc_courant = premier_bloc;

    while (!bloc_courant->libre || bloc_courant->taille < taille)
    {
        bloc_courant = bloc_courant->suivant;
        if (bloc_courant == premier_bloc)
        {
            // Retour au point de départ : échec d'allocation
            return NULL;
        }
    }

    // bloc_courant pointe sur un bloc libre de bonne taille

    void *adresse = bloc_courant->adresse;
    bloc_courant->libre = false;
    if (bloc_courant->taille > taille) {
        // on le sépare en deux pour récupérer la place
        struct bloc *bloc_libre = cree_bloc((uint8_t *)adresse + taille,
                bloc_courant->taille - taille, true);
        bloc_courant->taille = taille;
        bloc_libre->suivant = bloc_courant->suivant;
        bloc_courant->suivant = bloc_libre;
    }

    // On pointe sur le bloc suivant qui est sûrement libre
    blocs_libres = bloc_courant->suivant;

    return adresse;
}

Pour libérer un bloc, on parcourt la liste jusqu'à trouver le bloc correspondant à l'adresse à libérer et on indique que le bloc est libre. Ici, il y a deux assert permettant de s'assurer que l'adresse est bien celle d'un bloc et que le bloc n'a pas déjà été libéré.

void liberation(void *adresse)
{
    struct bloc *premier_bloc = blocs_libres;
    struct bloc *bloc_courant = premier_bloc;

    while (bloc_courant->adresse != adresse)
    {
        bloc_courant = bloc_courant->suivant;
        // adresse invalide
        assert(bloc_courant != premier_bloc);
    }

    // pas de double libération
    assert(!bloc_courant->libre);

    // on libère l'adresse
    bloc_courant->libre = true;
}

Voici un premier programme de test de ces fonctions qui alloue 10 octets puis effectue plusieurs allocations. L'allocation de c échoue car il n'y a plus de place libre.

int main(void)
{
    creation_blocs_libres(10);

    uint8_t *a = allocation(5);
    uint8_t *b = allocation(3);
    uint8_t *c = allocation(3);
    liberation(b);
    uint8_t *d = allocation(2);

    printf("Allocation a:%p b:%p c:%p d:%p\n",
            (void *)a, (void *)b, (void *)c, (void *)d);

    destruction_blocs_libres();

    return 0;
}

Ce programme affiche alors

Allocation a:0x55c6c0c922a0 b:0x55c6c0c922a5 c:(nil) d:0x55c6c0c922a8

On remarque que d n'est pas placé à l'adresse libérée de b : la recherche commence au bloc pointé par blocs_libres, c'est-à-dire au bloc libre de 2 octets créé lors de l'allocation de b.

Voici l'évolution de la liste circulaire en présentant les maillons sous la forme :

L'évolution de la liste des blocs entre les lignes 3 et 9 est alors :

• Ligne 3

  

• Ligne 5

  

• Ligne 6

  

• Ligne 8

  

• Ligne 9

  

Cette méthode d'allocation a un défaut majeur : elle fragmente l'espace libre. Dans le programme suivant, il sera impossible d'allouer b car la liste circulaire contient deux blocs libres de 5 octets et non un bloc libre de 10 octets.

creation_blocs_libres(10);

uint8_t *a = allocation(5);
liberation(a);
uint8_t *b = allocation(10);

Remarque

On peut observer ce phénomène sur le diagramme précédent à la ligne 8 où deux blocs contigus sont libres et pourraient être fusionnés en un unique bloc de 5 octets.

On peut éviter cela en effectuant une phase de coalescence des blocs libres à la libération. Comme la liste circulaire est simplement chaînée, on ne peut fusionner un bloc libre qu'avec les blocs suivants. En utilisant une liste circulaire doublement chaînée, on pourrait également fusionner avec les blocs précédents.

Deux précautions sont nécessaires :

• les maillons de la liste sont rangés par adresses croissantes à partir du bloc d'adresse plage_memoire (les découpages insèrent toujours le nouveau bloc juste après le bloc découpé) ; le maillon qui suit le dernier bloc est donc le premier bloc de la plage, qui ne lui est pas contigu en mémoire : il ne faut pas les fusionner ;
• le maillon pointé par blocs_libres peut faire partie des maillons fusionnés et donc libérés : on fait alors pointer blocs_libres sur le bloc libéré.

Pour cela on change la fonction liberation ainsi :

void liberation(void *adresse)
{
    struct bloc *premier_bloc = blocs_libres;
    struct bloc *bloc_courant = premier_bloc;

    while (bloc_courant->adresse != adresse)
    {
        bloc_courant = bloc_courant->suivant;
        // adresse invalide
        assert(bloc_courant != premier_bloc);
    }

    // pas de double libération
    assert(!bloc_courant->libre);

    // on libère l'adresse
    bloc_courant->libre = true;

    premier_bloc = bloc_courant;
    bloc_courant = bloc_courant->suivant;

    // on fusionne avec les blocs libres suivants qui sont contigus
    while (bloc_courant != premier_bloc && bloc_courant->libre
            && bloc_courant->adresse != plage_memoire)
    {
        struct bloc* actuel = bloc_courant;
        premier_bloc->taille += bloc_courant->taille;
        bloc_courant = bloc_courant->suivant;
        free(actuel); // on libere le bloc inutile
    }

    premier_bloc->suivant = bloc_courant;
    // blocs_libres pointait peut-être sur un maillon libéré
    blocs_libres = premier_bloc;
}