Séance 5 — Allocation dynamique et structures chaînées

Propriété, tableau dynamique, listes, piles et files, erreurs du tas, intérieur de malloc

Séance 5 de Programmation C avancée : propriété, tableau dynamique, listes, piles et files, erreurs du tas, intérieur de malloc.

Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

Navigation conceptuelle

Amont. La Séance 3 a présenté le tas et les quatre fonctions malloc, calloc, realloc et free, avec les premières erreurs (fuite de mémoire, double free, accès après free) ; la Séance 4, les structures, l’opérateur -> et la structure auto-référentielle, dont un nœud alloué sur le tas.

Aval. La Séance 6 (pointeurs de fonctions et généricité) reprend les tableaux, listes, piles et files de cette séance pour les écrire une seule fois, quel que soit le type des éléments.

Objectifs

Dire, pour chaque bloc, qui l’alloue, qui le libère et jusqu’à quand il est valide (la propriété).
Programmer un tableau dynamique qui double sa capacité, justifier son coût amorti et éviter les pointeurs invalidés par realloc.
Insérer, chercher, supprimer et libérer dans une liste chaînée, avec un pointeur de pointeur pour modifier la tête.
Réaliser une pile et une file sur tableau dynamique et sur liste, et comparer leurs coûts.
Reconnaître une fuite, un double free, un use after free et un pointeur pendant dans un rapport de valgrind ou d’AddressSanitizer.
Lire les en-têtes des blocs de la glibc, et suivre la liste libre d’un allocateur first fit.

Les programmes de ce document

Tous les programmes ont été compilés et exécutés sur la même machine : x86-64, Linux 6.18, gcc 13.3.0 avec les options -std=c17 -Wall -Wextra -O0 -g, glibc 2.39, valgrind 3.22.0 ; -fsanitize=address s’y ajoute pour AddressSanitizer. L’aléa des adresses est désactivé (setarch -R), si bien que les adresses affichées se répètent d’une exécution à l’autre. Les sorties reproduites sont celles de ces exécutions ; dans les rapports, les lignes retirées sont remplacées par « ... » et le numéro du processus par PID. Les octets des grilles mémoire ont été relevés en mémoire sous gdb ; dans les grilles, les adresses sont simplifiées (0x10, 0x40, …) en gardant la disposition réelle, et l’adresse réelle est donnée dans le texte. Ce que le document dit de l’intérieur de malloc vaut pour la glibc 2.39 ; une autre bibliothèque peut s’y prendre autrement.

La propriété d’un bloc

Les structures de cette séance — un tableau qui grandit, une liste dont chaque élément est un bloc — multiplient les allocations. Le C ne libère rien de lui-même : pour chaque bloc, il faut savoir quel code le rendra, et jusqu’à quand les autres parties du programme peuvent s’en servir. C’est la question de la propriété.

Rappel de la Séance 3

appel	rend	à retenir
`malloc(n)`	un bloc de \(n\) octets, ou `NULL`	contenu indéterminé
`calloc(k, t)`	un bloc de \(k\times t\) octets à zéro, ou `NULL`
`realloc(p, n)`	le bloc redimensionné, ou `NULL`	peut déplacer le bloc ; en cas d’échec, `p` reste valide
`free(p)`	rien	`free(NULL)` est sans effet ; `p` ne doit plus servir

La Séance 3 a aussi montré trois erreurs : la fuite de mémoire, ou fuite (un bloc dont plus aucune variable ne garde l’adresse), le double free (que la glibc arrête par SIGABRT), et l’accès après free, un comportement indéfini qui, ce jour-là, lisait 1431655769, c’est-à-dire 0x55555559, un lien écrit par la glibc dans le bloc libéré. La section Section 6 explique d’où vient cette valeur.

Propriétaire, emprunt, transfert

Propriété d’un bloc

Le propriétaire d’un bloc est le code chargé de le libérer, une fois et une seule. La durée de vie du bloc va du malloc (ou calloc, realloc) au free. Une fonction qui rend un bloc qu’elle a alloué en transfère la propriété à l’appelant ; une fonction qui reçoit un pointeur sans le libérer l’emprunte : le bloc doit rester valide pendant toute la durée de l’emprunt.

La propriété n’est pas écrite dans le type : un char * peut désigner un tableau local, un littéral ou un bloc du tas. Elle s’écrit dans le contrat de chaque fonction (« rend un bloc que l’appelant libère », « ne garde pas l’adresse reçue »), et c’est ce contrat qui dit où placer chaque free. Le programme suivant range trois noms de villes de deux façons : par emprunt de l’adresse d’un tampon, et par copie possédée.

char *dupliquer(const char *s)
{
    char *d = malloc(strlen(s) + 1);
    if (d != NULL)
        strcpy(d, s);
    return d;
}
int main(void)
{
    const char *villes[3] = {"Thies", "Kaolack",
                             "Kolda"};
    char tampon[16];
    char *emprunt[3];
    char *copie[3];
    for (int i = 0; i < 3; i++) {
        strcpy(tampon, villes[i]);
        emprunt[i] = tampon;   /* emprunt */
        copie[i] = dupliquer(tampon);  /* copie */
    }
    for (int i = 0; i < 3; i++) {
        printf("%s, %s\n", emprunt[i], copie[i]);
        free(copie[i]);
    }
    return 0;
}

Sortie :

Kolda, Thies
Kolda, Kaolack
Kolda, Kolda

Sortie d’erreur sous valgrind :

All heap blocks were freed -- no leaks are possible

À chaque tour, strcpy réécrit tampon ; emprunt[i] reçoit l’adresse de tampon, la même aux trois tours, si bien qu’à la fin les trois cases désignent le même tableau, qui contient « Kolda ». dupliquer, elle, alloue un bloc par appel et y copie la chaîne : elle transfère la propriété de ce bloc à main, qui libère les trois blocs dans la dernière boucle. valgrind confirme qu’aucun bloc ne reste.

Trois erreurs, une même cause

Aucun propriétaire : fuite. Deux propriétaires : double free. Un emprunteur qui garde l’adresse au-delà de la durée de vie du bloc : pointeur pendant, puis use after free dès qu’il s’en sert. La section Section 5 montre ces trois erreurs dans une liste chaînée.

Le tableau dynamique

Un tableau du C a une longueur fixe ; un tableau alloué par malloc a une longueur choisie à l’exécution, mais toujours fixe une fois le bloc obtenu. Quand le nombre d’éléments n’est pas connu d’avance, le tableau doit grandir : c’est le rôle du tableau dynamique.

Taille et capacité

Tableau dynamique

Un tableau dynamique est une structure qui possède un bloc du tas et en garde deux nombres : la taille, nombre d’éléments rangés, et la capacité, nombre d’éléments que le bloc peut recevoir. Un ajout dans un bloc plein le réalloue avec une capacité plus grande, ici le double.

typedef struct {
    int *donnees;       /* bloc du tas */
    size_t taille;      /* elements ranges */
    size_t capacite;    /* places du bloc */
} Vecteur;
int vec_init(Vecteur *v, size_t cap)
{
    v->donnees = malloc(cap * sizeof(int));
    v->taille = 0;
    v->capacite = cap;
    return v->donnees != NULL;
}
int vec_ajouter(Vecteur *v, int x)
{
    if (v->taille == v->capacite) {
        size_t cap = v->capacite ? 2 * v->capacite : 1;
        int *t = realloc(v->donnees, cap * sizeof *t);
        if (t == NULL)
            return 0;   /* ancien bloc intact */
        v->donnees = t;
        v->capacite = cap;
    }
    v->donnees[v->taille] = x;
    v->taille++;
    return 1;
}
void vec_liberer(Vecteur *v)
{
    free(v->donnees);
    *v = (Vecteur){NULL, 0, 0};
}

vec_ajouter range l’élément à l’indice taille, puis incrémente la taille ; si le bloc est plein, elle demande d’abord à realloc un bloc deux fois plus grand (une capacité 0 passe à 1, sinon le bloc resterait vide). Le résultat de realloc passe par la variable t : écrire v->donnees = realloc(v->donnees, …) perdrait la seule adresse de l’ancien bloc si realloc échouait (il rend alors NULL et laisse l’ancien bloc intact), d’où une fuite. Le Vecteur possède son bloc : vec_liberer le rend et remet la structure dans l’état d’un tableau vide.

Exemple pas à pas : un tableau dynamique

int main(void)
{
    Vecteur v;
    vec_init(&v, 2);
    vec_ajouter(&v, 7);
    vec_ajouter(&v, 11);
    vec_ajouter(&v, 13);
    vec_ajouter(&v, 17);
    printf("%zu %zu\n", v.taille, v.capacite);
    vec_liberer(&v);
    return 0;
}

Après la ligne 37 : vec_init

Après la ligne 39

Après la ligne 40 : realloc en place

Ligne 42 : affichage

Sous gdb, v est en 0x7fffffffec50, dans la pile, et le bloc en 0x5555555592a0, dans le tas (les adresses de pile dépendent de l’environnement et du chemin du programme) ; la grille les place en 0x10 et 0x40. La ligne 37 demande 8 octets (deux int) : la glibc réserve un bloc de 32 octets dont 24 utiles, et range sa taille dans un en-tête de 8 octets, juste avant l’adresse rendue (0x21 : 32, et le bit 0 dont la section Section 6 donne le sens). Les cases jaunes sont les places de la capacité, les cases grises les octets utiles au-delà.

Les lignes 38 et 39 remplissent les deux places : taille rejoint capacite. À la ligne 40, le bloc est plein : realloc reçoit une demande de 16 octets. Le bloc en a 24 d’utiles : la glibc le garde en place, et l’adresse 0x40 comme l’en-tête restent les mêmes (le relevé sous gdb le confirme). capacite passe à 4, et 13 entre dans la troisième place. Après la ligne 41, le bloc est de nouveau plein : le prochain ajout demandera 32 octets, plus que les 24 utiles, et realloc devra trouver un autre bloc.

Sortie :

4 4

Coût amorti du doublement

Réallouer coûte cher quand le bloc est déplacé : realloc recopie alors tous les éléments. Le programme suivant compte, pour \(n\) ajouts à partir d’une capacité 1, les appels à realloc, les éléments à recopier si chaque appel déplaçait le bloc (le pire cas, cumulé dans pire), et les déplacements réels. Il compare le doublement à une croissance d’un élément à la fois.

/* n ajouts ; le tableau double (pas = 0) ou grandit de pas elements */
void mesurer(size_t n, size_t pas)
{
    size_t cap = 1, taille = 0, appels = 0, pire = 0, deplacements = 0;
    int *t = malloc(cap * sizeof(int));
    for (size_t i = 0; i < n; i++) {
        if (taille == cap) {
            size_t nc = pas == 0 ? 2 * cap : cap + pas;
            int *u = realloc(t, nc * sizeof(int));
            if (u == NULL)
                break;
            appels++;
            pire += taille;
            if (u != t)
                deplacements++;
            t = u;
            cap = nc;
        }
        t[taille] = (int)i;
        taille++;
    }
    printf("%-6s n = %7zu : %5zu realloc, %8.2f copies par ajout au pire, %zu deplacements\n",
           pas == 0 ? "double" : "+1", n, appels, (double)pire / n, deplacements);
    free(t);
}
int main(void)
{
    mesurer(1000, 0);
    mesurer(1000000, 0);
    mesurer(1000, 1);
    mesurer(100000, 1);
    return 0;
}

Sortie :

double n =    1000 :    10 realloc,     1.02 copies par ajout au pire, 0 deplacements
double n = 1000000 :    20 realloc,     1.05 copies par ajout au pire, 7 deplacements
+1     n =    1000 :   999 realloc,   499.50 copies par ajout au pire, 1 deplacements
+1     n =  100000 : 99999 realloc, 49999.50 copies par ajout au pire, 1 deplacements

En doublant, les réallocations ont lieu quand la taille vaut \(1, 2, 4, \dots, 2^{k-1}\), avec \(2^{k-1}<n\) : le pire cas recopie \(1+2+\dots+2^{k-1}=2^k-1\) éléments, moins de \(2n\). Pour 1000 ajouts, 10 appels et 1023 copies au pire, soit 1,02 copie par ajout ; pour un million, 20 appels et 1,05 copie par ajout. Un ajout coûte donc un temps constant en moyenne sur la suite des ajouts, même si certains ajouts recopient tout le tableau : c’est le coût amorti. En grandissant d’un élément, chaque ajout sauf le premier réalloue, et le pire cas recopie \(1+2+\dots+(n-1)=n(n-1)/2\) éléments : 499,5 copies par ajout pour 1000, 49 999,5 pour 100 000. Le coût par ajout croît comme \(n\).

Les déplacements réels sont rares ici : le bloc est le dernier du tas, et la glibc l’agrandit le plus souvent sur place. Dans un programme qui alloue d’autres blocs entre deux ajouts, le bloc suivant est occupé et realloc doit déplacer ; c’est ce que montre la section suivante.

Un pointeur dans le bloc, après `realloc`

int *t = malloc(2 * sizeof(int));
t[0] = 221;
int *premier = &t[0];  /* dans le bloc */
char *voisin = malloc(16);  /* suit t */
int *u = realloc(t, 8 * sizeof(int));
if (u == NULL)
    return 1;
t = u;
printf("t[0] = %d\n", t[0]);
printf("*premier = %d\n", *premier);
free(voisin);
free(t);

Compilateur :

s2_invalide.c:14:5: warning: pointer 'premier' may be used after 'realloc' [-Wuse-after-free]

Sortie :

t[0] = 221
*premier = 1431655769

Sortie d’erreur avec AddressSanitizer :

==PID==ERROR: AddressSanitizer: heap-use-after-free on address 0x502000000010
READ of size 4 at 0x502000000010 thread T0
    #0 0x555555555391 in main s2_invalide.c:14
...
0x502000000010 is located 0 bytes inside of 8-byte region [0x502000000010,0x502000000018)
freed by thread T0 here:
    #0 0x7ffff78fc778 in realloc asan_malloc_linux.cpp:85
    #1 0x5555555552ea in main s2_invalide.c:9
...
previously allocated by thread T0 here:
    #0 0x7ffff78fd9c7 in malloc asan_malloc_linux.cpp:69
    #1 0x55555555527e in main s2_invalide.c:5
...
SUMMARY: AddressSanitizer: heap-use-after-free s2_invalide.c:14 in main

premier reçoit l’adresse du premier élément. voisin occupe la place qui suit le bloc : realloc ne peut pas agrandir sur place, il alloue un nouveau bloc, y recopie les deux int, et libère l’ancien. t[0] lit 221 dans le nouveau bloc ; premier désigne toujours l’ancien, libéré : le lire est un use after free, que gcc signale déjà à la compilation. Sans outil, la lecture rend 1431655769, le lien que la glibc a écrit dans le bloc libéré. AddressSanitizer donne les trois lignes utiles : la lecture (ligne 14), le realloc qui a libéré le bloc (ligne 9), et l’allocation d’origine (ligne 5).

Invalidation

Après tout appel qui peut réallouer (un ajout dans un tableau dynamique), tout pointeur vers un élément du bloc est à recalculer. Un indice, lui, reste valide : garder i et écrire v.donnees[i].

La liste chaînée

Le tableau dynamique range ses éléments côte à côte, ce qui donne l’accès par indice mais oblige à déplacer le bloc pour grandir, et à décaler les éléments pour insérer au milieu. La liste chaînée fait le choix inverse.

Liste chaînée

Une liste chaînée est une suite de nœuds alloués un à un ; chaque nœud contient une valeur et l’adresse du nœud suivant (Séance 4), NULL pour le dernier. La liste est désignée par l’adresse de son premier nœud, la tête ; la liste vide est NULL. Chaque nœud est un bloc : la liste possède ses nœuds.

Insérer ou retirer un nœud ne déplace aucun autre élément : on réécrit un ou deux pointeurs. Un nœud ne change jamais d’adresse, si bien qu’un pointeur vers un nœud reste valide tant que le nœud est dans la liste. En contrepartie, atteindre le \(k\)^e élément parcourt \(k\) nœuds, et chaque nœud coûte un malloc : un Noeud de 16 octets (un int, 4 octets de padding, un pointeur) occupe un bloc de 32 octets de la glibc.

Insertion en tête : le pointeur de pointeur

Insérer en tête change la tête : la fonction doit modifier la variable de l’appelant qui la contient. Elle reçoit donc l’adresse de cette variable, un Noeud **.

typedef struct Noeud {
    int valeur;
    struct Noeud *suivant;
} Noeud;
void afficher(const Noeud *p)
{
    for (; p != NULL; p = p->suivant)
        printf("%d -> ", p->valeur);
    printf("NULL\n");
}
void liberer(Noeud **pt)
{
    Noeud *p = *pt;
    while (p != NULL) {
        Noeud *s = p->suivant;
        free(p);
        p = s;
    }
    *pt = NULL;
}
void inserer_tete(Noeud **pt, int v)
{
    Noeud *n = malloc(sizeof *n);
    n->valeur = v;
    n->suivant = *pt;
    *pt = n;
}
int main(void)
{
    Noeud *tete = NULL;
    inserer_tete(&tete, 12);
    inserer_tete(&tete, 5);
    afficher(tete);
    liberer(&tete);
    return 0;
}

Ligne 33 : l’appel, pt \(=\) &tete

Après la ligne 27

Après la ligne 28 : *pt = n

Second appel, après la ligne 27

Second appel, après la ligne 28

Ligne 35 : après les deux appels

Sous gdb, tete est en 0x7fffffffec60, dans le stack frame de main ; dans celui de inserer_tete, pt est en 0x7fffffffec38 et n en 0x7fffffffec48 ; les nœuds sont en 0x5555555592a0 et 0x5555555592c0 (les adresses de pile dépendent de l’environnement). La grille place pt en 0x18, n en 0x28, tete en 0x40 et les nœuds en 0x80 et 0xA0, avec les écarts réels.

À l’appel de la ligne 33, pt reçoit 0x40, l’adresse de tete, et non sa valeur. La ligne 27, n->suivant = *pt, lit tete à travers pt : NULL, si bien que le premier nœud est aussi le dernier. La ligne 28, *pt = n, écrit l’adresse du nœud dans tete, une variable de main : c’est l’effet que la fonction devait produire. Le second appel recrée un stack frame au même endroit ; pt contient encore 0x40, n->suivant reçoit l’ancienne tête 0x80, et tete passe à 0xA0. Le second nœud est 32 octets après le premier : 16 octets de nœud, 16 d’en-tête et d’arrondi. Le parcours de afficher part de tete et suit les champs suivant.

Sortie :

5 -> 12 -> NULL

Sans pointeur de pointeur

Avec un paramètre Noeud *, la fonction reçoit une copie de la tête :

typedef struct Noeud {
    int valeur;
    struct Noeud *suivant;
} Noeud;
void inserer_tete(Noeud *tete, int v)  /* copie */
{
    Noeud *n = malloc(sizeof *n);
    n->valeur = v;
    n->suivant = tete;
    tete = n;           /* la copie */
}
int main(void)
{
    Noeud *tete = NULL;
    inserer_tete(tete, 12);
    inserer_tete(tete, 5);
    printf("%p\n", (void *)tete);
    return 0;
}

Sortie :

(nil)

Sortie d’erreur sous valgrind :

16 bytes in 1 blocks are definitely lost in loss record 1 of 2
   at 0x4846828: malloc (vgpreload_memcheck)
   by 0x109185: inserer_tete (s3_mauvaise.c:9)
   by 0x1091CE: main (s3_mauvaise.c:17)
...
16 bytes in 1 blocks are definitely lost in loss record 2 of 2
   at 0x4846828: malloc (vgpreload_memcheck)
   by 0x109185: inserer_tete (s3_mauvaise.c:9)
   by 0x1091DF: main (s3_mauvaise.c:18)
...
   definitely lost: 32 bytes in 2 blocks
   indirectly lost: 0 bytes in 0 blocks

tete = n modifie le paramètre, une variable locale de inserer_tete ; la tete de main reste NULL. Les deux nœuds ont pourtant été alloués, et au retour plus aucune variable ne garde leur adresse : valgrind les compte comme definitely lost (deux blocs de 16 octets) et donne pour chacun la ligne de l’allocation et celle de l’appel.

Insertion en queue, recherche, parcours

Le pointeur de pointeur sert aussi à parcourir : pp désigne successivement tete, puis le champ suivant du premier nœud, puis celui du deuxième, jusqu’au champ qui vaut NULL. C’est là qu’un nœud ajouté en queue doit être rangé.

typedef struct Noeud {
    int valeur;
    struct Noeud *suivant;
} Noeud;
int inserer_queue(Noeud **pp, int v)
{
    while (*pp != NULL)     /* jusqu'au NULL */
        pp = &(*pp)->suivant;
    Noeud *n = malloc(sizeof *n);
    if (n == NULL)
        return 0;
    n->valeur = v;
    n->suivant = NULL;
    *pp = n;
    return 1;
}
Noeud *chercher(Noeud *p, int v)
{
    while (p != NULL && p->valeur != v)
        p = p->suivant;
    return p;               /* NULL : absent */
}
void afficher(const Noeud *p)
{
    for (; p != NULL; p = p->suivant)
        printf("%d -> ", p->valeur);
    printf("NULL\n");
}
void liberer(Noeud **pt)
{
    Noeud *p = *pt;
    while (p != NULL) {
        Noeud *s = p->suivant;  /* avant free */
        free(p);
        p = s;
    }
    *pt = NULL;
}
int main(void)
{
    Noeud *tete = NULL;
    inserer_queue(&tete, 4);
    inserer_queue(&tete, 9);
    inserer_queue(&tete, 2);
    afficher(tete);
    Noeud *x = chercher(tete, 9);
    printf("%d\n", x->suivant->valeur);
    printf("%p\n", (void *)chercher(tete, 6));
    liberer(&tete);
    printf("%p\n", (void *)tete);
    return 0;
}

Sortie :

4 -> 9 -> 2 -> NULL
2
(nil)
(nil)

Sortie d’erreur sous valgrind :

All heap blocks were freed -- no leaks are possible

Le même code d’inserer_queue traite la liste vide : *pp vaut alors NULL dès le départ, pp reste &tete, et *pp = n écrit dans tete. Sans pointeur de pointeur, il faudrait distinguer « liste vide » (modifier tete) et « liste non vide » (modifier le suivant du dernier nœud). chercher rend l’adresse du premier nœud qui porte la valeur, ou NULL ; afficher reçoit un const Noeud *, car elle ne modifie rien. L’insertion en queue parcourt toute la liste : elle coûte un temps proportionnel à sa longueur (la file de la section Section 4 évite ce parcours).

Exemple pas à pas : la suppression

void supprimer(Noeud **pp, int v)
{
    while (*pp != NULL && (*pp)->valeur != v)
        pp = &(*pp)->suivant;
    if (*pp != NULL) {
        Noeud *n = *pp;
        *pp = n->suivant;
        free(n);
    }
}
int main(void)
{
    Noeud *tete = nouveau(21, NULL);
    tete = nouveau(8, tete);
    tete = nouveau(3, tete);
    supprimer(&tete, 8);
    afficher(tete);
    liberer(&tete);
    return 0;
}

Après la ligne 46 : la liste

Ligne 47 : pp \(=\) &tete

Après la ligne 35

Après la ligne 37

Après la ligne 38

Après la ligne 39

Les nœuds sont alloués du dernier au premier : 21 en 0x5555555592a0, 8 en 0x5555555592c0, 3 en 0x5555555592e0, notés 0x40, 0x60 et 0x80 dans le schéma ; l’ordre de la liste n’est pas celui des adresses. Chaque nœud est dessiné avec ses deux champs, son adresse au-dessus, et une flèche part de chaque pointeur.

supprimer(&tete, 8) reçoit dans pp l’adresse de tete. Le premier test lit *pp, c’est-à-dire tete, puis la valeur du nœud désigné : 3, différent de 8. La ligne 35 fait avancer pp : &(*pp)->suivant est l’adresse du champ suivant du premier nœud, 0x88 (le relevé sous gdb donne 0x5555555592e8). Au test suivant, *pp vaut 0x60 et la valeur est 8 : la boucle s’arrête avec pp sur le champ à réécrire. n garde l’adresse du nœud à retirer, la ligne 38 écrit n->suivant (0x40) dans ce champ, et le premier nœud saute le deuxième ; la ligne 39 rend le bloc. Si le nœud cherché avait été le premier, pp serait resté &tete, et la ligne 38 aurait écrit dans tete : le même code traite les deux cas.

Sortie :

3 -> 21 -> NULL

Libération complète

Chaque nœud est un bloc : libérer une liste, c’est libérer chaque nœud. L’ordre compte : après free(p), le nœud p n’existe plus, et p->suivant ne se lit plus. La fonction liberer de s3_liste.c (lignes 31 à 40) lit donc le suivant dans s avant le free, puis met la tête de l’appelant à NULL : l’appelant garde une liste vide plutôt qu’une tête pendante (la dernière ligne de la sortie, (nil)). valgrind confirme que tous les blocs ont été rendus.

Piles et files

Une pile rend en premier le dernier élément rangé (last in, first out, LIFO) ; une file rend les éléments dans l’ordre d’arrivée (first in, first out, FIFO). Les deux se réalisent sur un tableau dynamique ou sur une liste.

Une pile, deux réalisations

Sur un Vecteur, empiler est vec_ajouter : le sommet est la fin du tableau. Sur une liste, empiler est inserer_tete : le sommet est la tête. Le programme suivant contient les fonctions des sections précédentes (lignes 3 à 42, non reproduites) et les deux fonctions de dépilement.

int vec_depiler(Vecteur *v, int *x)
{
    if (v->taille == 0)
        return 0;           /* pile vide */
    v->taille--;
    *x = v->donnees[v->taille];
    return 1;
}
int liste_depiler(Noeud **pt, int *x)
{
    Noeud *n = *pt;
    if (n == NULL)
        return 0;
    *x = n->valeur;
    *pt = n->suivant;
    free(n);
    return 1;
}
int main(void)
{
    Vecteur a;
    Noeud *b = NULL;
    int x;
    vec_init(&a, 2);
    for (int i = 1; i <= 5; i++) {
        vec_ajouter(&a, 10 * i);
        inserer_tete(&b, 10 * i);
    }
    while (vec_depiler(&a, &x))
        printf("%d ", x);
    printf("| ");
    while (liste_depiler(&b, &x))
        printf("%d ", x);
    printf("\n");
    free(a.donnees);
    return 0;
}

Sortie :

50 40 30 20 10 | 50 40 30 20 10

vec_depiler décrémente la taille et lit l’élément qui était au sommet ; le bloc garde sa capacité, prêt pour les empilements suivants. liste_depiler lit la valeur de la tête, avance la tête et libère l’ancien nœud. Les deux piles rendent 50, 40, 30, 20, 10 : l’ordre inverse de l’empilement. Les deux réalisations empilent et dépilent en temps constant (amorti pour le tableau).

Une file sur liste

Une file sur liste défile en tête et enfile en queue ; pour ne pas parcourir la liste à chaque ajout, la structure garde aussi l’adresse du dernier nœud.

typedef struct Noeud {
    int valeur;
    struct Noeud *suivant;
} Noeud;
typedef struct {
    Noeud *tete;            /* on defile ici */
    Noeud *queue;           /* on enfile ici */
} File;
int enfiler(File *f, int x)
{
    Noeud *n = malloc(sizeof *n);
    if (n == NULL)
        return 0;
    n->valeur = x;
    n->suivant = NULL;
    if (f->queue == NULL)
        f->tete = n;        /* file vide */
    else
        f->queue->suivant = n;
    f->queue = n;
    return 1;
}
int defiler(File *f, int *x)
{
    Noeud *n = f->tete;
    if (n == NULL)
        return 0;
    *x = n->valeur;
    f->tete = n->suivant;
    if (f->tete == NULL)
        f->queue = NULL;    /* file vide */
    free(n);
    return 1;
}
int main(void)
{
    File f = {NULL, NULL};
    int x;
    enfiler(&f, 4);
    enfiler(&f, 9);
    defiler(&f, &x);
    printf("%d ", x);
    enfiler(&f, 2);
    while (defiler(&f, &x))
        printf("%d ", x);
    printf("| %d\n", f.queue == NULL);
    return 0;
}

Sortie :

4 9 2 | 1

Les deux cas limites sont les transitions entre file vide et file non vide. Enfiler dans une file vide (queue == NULL) met à jour tete en plus de queue ; défiler le dernier nœud remet queue à NULL, sans quoi queue resterait un pointeur pendant vers le nœud libéré, et le prochain enfiler écrirait dans ce bloc. La dernière valeur affichée, 1, confirme que queue est revenue à NULL.

Une file circulaire

Sur un tableau, défiler en tête obligerait à décaler tous les éléments. La file circulaire garde l’indice du premier élément, debut, et le nombre d’éléments, n : les éléments occupent les cases debut, debut + 1, …, modulo la capacité.

typedef struct {
    int *t;
    size_t debut;       /* indice du premier */
    size_t n;           /* nombre d'elements */
    size_t cap;
} FileC;
/* double la capacite, remet dans l'ordre */
int agrandir(FileC *f)
{
    size_t c = 2 * f->cap;
    int *u = calloc(c, sizeof *u);
    if (u == NULL)
        return 0;
    for (size_t i = 0; i < f->n; i++)
        u[i] = f->t[(f->debut + i) % f->cap];
    free(f->t);
    f->t = u;
    f->debut = 0;
    f->cap = c;
    return 1;
}
int fc_enfiler(FileC *f, int x)
{
    if (f->n == f->cap && !agrandir(f))
        return 0;
    f->t[(f->debut + f->n) % f->cap] = x;
    f->n++;
    return 1;
}
int fc_defiler(FileC *f, int *x)
{
    if (f->n == 0)
        return 0;
    *x = f->t[f->debut];
    f->debut = (f->debut + 1) % f->cap;
    f->n--;
    return 1;
}
void etat(const FileC *f)
{
    printf("debut %zu, n %zu, cap %zu :", f->debut, f->n, f->cap);
    for (size_t i = 0; i < f->cap; i++)
        printf(" %d", f->t[i]);
    printf("\n");
}
int main(void)
{
    FileC f = {calloc(4, sizeof(int)), 0, 0, 4};
    int x;
    fc_enfiler(&f, 4);
    fc_enfiler(&f, 9);
    fc_enfiler(&f, 2);
    fc_defiler(&f, &x);
    fc_defiler(&f, &x);
    fc_enfiler(&f, 7);
    fc_enfiler(&f, 5);
    etat(&f);
    fc_enfiler(&f, 6);
    fc_enfiler(&f, 8);
    etat(&f);
    free(f.t);
    return 0;
}

Sortie :

debut 2, n 3, cap 4 : 5 9 2 7
debut 0, n 5, cap 8 : 2 7 5 6 8 0 0 0

Les trois premiers fc_enfiler remplissent les cases 0, 1 et 2 ; les deux fc_defiler rendent 4 et 9 et font passer debut à 2, sans effacer les cases. 7 va en case \((2+1)\bmod 4=3\), et 5 en case \((2+2)\bmod 4=0\), à la place de l’ancien 4 : la première ligne de la sortie montre 5 9 2 7, où 9 est une valeur déjà défilée. 6 occupe ensuite la case 1 : la file est pleine. Pour 8, agrandir alloue 8 cases et y recopie les éléments dans l’ordre de la file, à partir de debut : 2, 7, 5, 6 ; debut repart de 0. Un realloc aurait gardé l’ordre des cases, 5 6 2 7, et la file serait devenue incohérente.

Coût des opérations

opération	tableau dynamique	liste chaînée
ajout en fin	\(O(1)\) amorti	\(O(1)\) avec un pointeur `queue`, sinon \(O(n)\)
ajout en tête	\(O(n)\) (décalage)	\(O(1)\)
accès au \(k\)^e élément	\(O(1)\)	\(O(k)\)
recherche d’une valeur	\(O(n)\)	\(O(n)\)
suppression d’un élément trouvé	\(O(n)\) (décalage)	\(O(1)\) si l’on tient `pp`
mémoire par élément	sa taille, plus les places libres	un bloc : 32 octets pour un `int` (glibc)
pointeurs vers les éléments	invalidés par `realloc`	stables jusqu’à la suppression

Une pile se réalise aussi bien sur l’un que sur l’autre. Une file demande un tableau circulaire, ou une liste avec tete et queue. Le tableau range les éléments dans un seul bloc et donne l’accès par indice ; la liste évite toute recopie et garde chaque élément à la même adresse.

Les erreurs du tas

Les erreurs de propriété de la Séance 3 se retrouvent dans les structures chaînées, où chaque nœud est un bloc. Elles ne se voient pas toujours à l’exécution : un programme faux peut afficher une valeur plausible. Deux outils les détectent : valgrind, qui exécute le programme sans le recompiler, et AddressSanitizer, que gcc -fsanitize=address compile dans le programme. Les exemples réutilisent les fonctions nouveau, chercher, supprimer et liberer des sections précédentes.

La fuite d’une liste

int main(void)
{
    Noeud *tete = nouveau(21, NULL);
    tete = nouveau(8, tete);
    tete = nouveau(3, tete);
    printf("%d\n", tete->valeur);
    free(tete);
    return 0;
}

Sortie :

Sortie d’erreur sous valgrind :

32 (16 direct, 16 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
   at 0x4846828: malloc (vgpreload_memcheck)
   by 0x1091A5: nouveau (s5_fuite.c:9)
   by 0x1091FB: main (s5_fuite.c:19)
...
   definitely lost: 16 bytes in 1 blocks
   indirectly lost: 16 bytes in 1 blocks

Sortie d’erreur avec AddressSanitizer :

==PID==ERROR: LeakSanitizer: detected memory leaks
...
Direct leak of 16 byte(s) in 1 object(s) allocated from:
    #0 0x7ffff78fd9c7 in malloc asan_malloc_linux.cpp:69
    #1 0x555555555285 in nouveau s5_fuite.c:9
    #2 0x55555555532f in main s5_fuite.c:19
...
Indirect leak of 16 byte(s) in 1 object(s) allocated from:
    #0 0x7ffff78fd9c7 in malloc asan_malloc_linux.cpp:69
    #1 0x555555555285 in nouveau s5_fuite.c:9
    #2 0x55555555531a in main s5_fuite.c:18
...
SUMMARY: AddressSanitizer: 32 byte(s) leaked in 2 allocation(s).

free(tete) ne rend que le premier nœud. Le deuxième n’est plus désigné que par le champ suivant d’un bloc libéré : valgrind le classe definitely lost (16 octets). Le troisième est encore désigné, mais par le deuxième, lui-même perdu : indirectly lost (16 octets). valgrind regroupe les 32 octets sous la ligne de l’allocation du deuxième nœud (nouveau, ligne 9, appelée à la ligne 19). LeakSanitizer, la partie d’AddressSanitizer qui cherche les fuites à la fin du programme, donne la même répartition. Corriger, c’est appeler liberer(&tete).

Libération qui lit un nœud libéré

int main(void)
{
    Noeud *tete = nouveau(21, NULL);
    tete = nouveau(8, tete);
    tete = nouveau(3, tete);
    for (Noeud *p = tete; p; p = p->suivant)
        free(p);
    printf("liste liberee\n");
    return 0;
}

Compilateur :

s5_liberer.c:21:32: warning: pointer 'p' used after 'free' [-Wuse-after-free]

Fin du processus : signal SIGSEGV (Segmentation fault)

Sortie d’erreur avec AddressSanitizer :

==PID==ERROR: AddressSanitizer: heap-use-after-free on address 0x502000000058
READ of size 8 at 0x502000000058 thread T0
    #0 0x555555555383 in main s5_liberer.c:21
...
0x502000000058 is located 8 bytes inside of 16-byte region [0x502000000050,0x502000000060)
freed by thread T0 here:
    #0 0x7ffff78fc4d8 in free asan_malloc_linux.cpp:52
    #1 0x55555555535e in main s5_liberer.c:22
...
previously allocated by thread T0 here:
    #0 0x7ffff78fd9c7 in malloc asan_malloc_linux.cpp:69
    #1 0x555555555285 in nouveau s5_liberer.c:9
...
SUMMARY: AddressSanitizer: heap-use-after-free s5_liberer.c:21 in main

La boucle libère p, puis évalue p = p->suivant : elle lit un champ du nœud qu’elle vient de rendre, ce que gcc signale. Sans outil, free(p) a écrit à l’offset 8, là où était suivant, la clé de la glibc (aléatoire, section Section 6.2) : p reçoit cette clé, et free de cette adresse arrête le processus (ici SIGSEGV). Sous gdb, après le premier free, les 8 octets de p sont bien ceux de l’offset 8 du nœud libéré, et changent d’une exécution à l’autre. AddressSanitizer l’arrête plus tôt, à la première lecture : 8 octets (le pointeur suivant), à l’offset 8 d’un bloc de 16 octets libéré à la ligne 22.

Un pointeur pendant après une suppression

int main(void)
{
    Noeud *tete = nouveau(21, NULL);
    tete = nouveau(8, tete);
    tete = nouveau(3, tete);
    Noeud *x = chercher(tete, 8);
    supprimer(&tete, 8);
    printf("%d\n", x->valeur);
    liberer(&tete);
    return 0;
}

Sortie :

1431655769

Sortie d’erreur avec AddressSanitizer :

==PID==ERROR: AddressSanitizer: heap-use-after-free on address 0x502000000030
READ of size 4 at 0x502000000030 thread T0
    #0 0x555555555757 in main s5_pendant.c:49
...
0x502000000030 is located 0 bytes inside of 16-byte region [0x502000000030,0x502000000040)
freed by thread T0 here:
    #0 0x7ffff78fc4d8 in free asan_malloc_linux.cpp:52
    #1 0x555555555517 in supprimer s5_pendant.c:29
...
previously allocated by thread T0 here:
    #0 0x7ffff78fd9c7 in malloc asan_malloc_linux.cpp:69
    #1 0x5555555552e5 in nouveau s5_pendant.c:9
...
SUMMARY: AddressSanitizer: heap-use-after-free s5_pendant.c:49 in main

x reçoit l’adresse du nœud 8 ; supprimer retire ce nœud de la liste et le libère. x est désormais un pointeur pendant : il contient l’adresse d’un bloc qui n’existe plus. Sans outil, x->valeur lit 1431655769 ; avec un autre allocateur, ou plus tard dans le programme, la lecture pourrait rendre 8 ou la donnée d’un autre bloc. Le rapport d’AddressSanitizer se lit en quatre parties : quoi (une lecture de 4 octets, heap-use-after-free, au début d’un bloc de 16 octets), où (ligne 49), qui a libéré le bloc (supprimer, ligne 29) et qui l’avait alloué (nouveau, ligne 9).

Sous valgrind, la même lecture rend 8 :

Sortie :

Sortie d’erreur sous valgrind :

Invalid read of size 4
   at 0x109368: main (s5_pendant.c:49)
 Address 0x4a7e090 is 0 bytes inside a block of size 16 free'd
   at 0x484988F: free (vgpreload_memcheck)
   by 0x109290: supprimer (s5_pendant.c:29)
   by 0x109363: main (s5_pendant.c:48)
 Block was alloc'd at
   at 0x4846828: malloc (vgpreload_memcheck)
   by 0x1091C5: nouveau (s5_pendant.c:9)
   by 0x109324: main (s5_pendant.c:45)

valgrind remplace malloc et free par les siens et met de côté les blocs libérés au lieu de les réutiliser aussitôt : le contenu du nœud est intact, mais la lecture est signalée, avec la même information (Invalid read of size 4, le free dans supprimer, l’allocation dans nouveau).

Un double `free` par un pointeur pendant

int main(void)
{
    Noeud *tete = nouveau(21, NULL);
    tete = nouveau(8, tete);
    tete = nouveau(3, tete);
    Noeud *x = chercher(tete, 8);
    supprimer(&tete, 8);
    free(x);
    liberer(&tete);
    return 0;
}

Sortie d’erreur :

free(): double free detected in tcache 2

Fin du processus : signal SIGABRT (Aborted)

Sortie d’erreur avec AddressSanitizer :

==PID==ERROR: AddressSanitizer: attempting double-free on 0x502000000030 in thread T0:
    #0 0x7ffff78fc4d8 in free asan_malloc_linux.cpp:52
    #1 0x5555555556d4 in main s5_double.c:49
...
0x502000000030 is located 0 bytes inside of 16-byte region [0x502000000030,0x502000000040)
freed by thread T0 here:
    #0 0x7ffff78fc4d8 in free asan_malloc_linux.cpp:52
    #1 0x5555555554b7 in supprimer s5_double.c:29
...
previously allocated by thread T0 here:
    #0 0x7ffff78fd9c7 in malloc asan_malloc_linux.cpp:69
    #1 0x555555555285 in nouveau s5_double.c:9
...
SUMMARY: AddressSanitizer: double-free asan_malloc_linux.cpp:52 in free

free(x) rend une seconde fois le nœud déjà libéré par supprimer. La glibc le détecte ici, grâce à la clé qu’elle écrit dans un bloc libéré (section Section 6), et arrête le processus ; ce n’est pas une garantie, et un double free non détecté corrompt les listes internes de l’allocateur. AddressSanitizer nomme les deux free et l’allocation. Deux pointeurs vers un même bloc, c’est un propriétaire et un emprunteur : seul le propriétaire libère, et l’emprunteur ne doit plus servir après.

valgrind ou AddressSanitizer

	valgrind	AddressSanitizer
mise en œuvre	sans recompiler	`gcc -fsanitize=address`
bloc libéré	mis de côté, contenu gardé	mis en quarantaine, accès interdit
après l’erreur	continue	s’arrête
fuites	bilan en fin d’exécution	LeakSanitizer, en fin d’exécution
valeur non initialisée utilisée	signalée	non signalée

Les deux outils se complètent : AddressSanitizer détecte aussi les débordements de tableaux dans la pile (Séance 3), valgrind l’usage d’une valeur non initialisée : non pas la copie d’une telle valeur, mais son emploi dans un test, un appel système ou un affichage.

L’intérieur de `malloc`

free(p) ne reçoit qu’une adresse, et doit pourtant savoir combien d’octets rendre. L’allocateur range donc, devant chaque bloc, un en-tête qui en garde la taille. Cette section regarde les en-têtes de la glibc 2.39, puis construit un allocateur qui reprend les mêmes idées (Bryant et O’Hallaron, § 9.9).

En-tête et alignement

size_t demande[6] = {0, 1, 24, 25, 40, 100};
unsigned char *p[6];
for (int i = 0; i < 6; i++)
    p[i] = malloc(demande[i]);     /* avant tout printf */
for (int i = 0; i < 6; i++) {
    size_t entete = *(size_t *)(p[i] - 8);    /* 8 octets avant le bloc */
    size_t bloc = entete & ~(size_t)7;          /* sans les 3 bits de poids faible */
    printf("malloc(%3zu) : %p  en-tete 0x%02zx  bloc %3zu  utile %3zu\n",
           demande[i], (void *)p[i], entete, bloc, bloc - 8);
}
for (int i = 0; i < 6; i++)
    free(p[i]);

Sortie :

malloc(  0) : 0x5555555592a0  en-tete 0x21  bloc  32  utile  24
malloc(  1) : 0x5555555592c0  en-tete 0x21  bloc  32  utile  24
malloc( 24) : 0x5555555592e0  en-tete 0x21  bloc  32  utile  24
malloc( 25) : 0x555555559300  en-tete 0x31  bloc  48  utile  40
malloc( 40) : 0x555555559330  en-tete 0x31  bloc  48  utile  40
malloc(100) : 0x555555559360  en-tete 0x71  bloc 112  utile 104

Toutes les adresses rendues sont des multiples de 16, l’alignement le plus exigeant des types de base sur x86-64 : un bloc peut recevoir n’importe quel objet. Les 8 octets qui précèdent l’adresse contiennent la taille du bloc, en-tête compris. Cette taille est un multiple de 16 : le plus petit qui contient la demande plus 8 octets, avec un minimum de 32. malloc(0), malloc(1) et malloc(24) reçoivent donc tous un bloc de 32 octets, dont 24 utiles ; malloc(25) passe à 48. Comme la taille est un multiple de 16, ses 3 bits de poids faible servent d’indicateurs : le bit 0 vaut 1 quand le bloc précédent est occupé, d’où 0x21 pour un bloc de 32 octets. Lire avant le bloc, comme le fait ce programme, est un comportement indéfini : le programme sert seulement à observer l’allocateur.

Exemple pas à pas : un bloc libéré, puis réutilisé

char *a = malloc(20);
char *b = malloc(20);
strcpy(a, "Matam");
strcpy(b, "Podor");
uintptr_t ua = (uintptr_t)a;
free(a);
char *c = malloc(20);
strcpy(c, "Louga");
printf("%d\n", (uintptr_t)c == ua);
free(b);
free(c);

a est en 0x5555555592a0, son en-tête en 0x555555559298 ; la grille les place en 0x40 et 0x38. Les deux blocs de 32 octets se suivent : l’en-tête de b est en 0x58, juste après les 24 octets utiles de a. À la ligne 12, free(a) range le bloc dans le tcache, une liste de blocs libres par taille. Les 8 premiers octets du bloc reçoivent le lien vers le bloc libre suivant de même taille ; il n’y en a pas, et ce lien NULL est masqué par l’adresse du champ décalée de 12 bits : 0x5555555592a0 >> 12 \(=\) 0x555555559, d’où les octets 59 55 55 55 05 00 00 00. Lus comme un int, les 4 premiers donnent 0x55555559 \(=\) 1431655769, la valeur des lectures après free des sections précédentes. Les 8 octets suivants reçoivent une clé, tirée au hasard à chaque exécution, qui permet de détecter un double free ; la grille ne la montre pas (cases ··, comme les octets jamais écrits), puisque sa valeur change d’une exécution à l’autre. L’en-tête ne change pas.

Après la ligne 8

Après la ligne 12 : free(a)

Après la ligne 13 : c = malloc(20)

Après la ligne 14

À la ligne 13, malloc(20) demande un bloc de la même taille : la glibc reprend celui du tcache, c \(=\) 0x40, et efface la clé, mais pas le lien : un bloc rendu par malloc n’est pas initialisé. « Louga » recouvre ensuite le lien. L’affichage de la ligne 15 compare c à l’ancienne adresse de a, gardée en entier avant le free : elles sont égales. Un pointeur pendant vers a désignerait désormais les données de c.

Sortie :

Dernier libéré, premier servi

void *a = malloc(40);
void *b = malloc(40);
uintptr_t ua = (uintptr_t)a;    /* en entiers */
uintptr_t ub = (uintptr_t)b;
free(a);
free(b);                /* dernier libere */
void *e = malloc(24);   /* autre taille */
void *c = malloc(40);
void *d = malloc(40);
printf("a %#" PRIxPTR "\nb %#" PRIxPTR "\n", ua, ub);
printf("e %p\nc %p\nd %p\n", e, c, d);
free(c);
free(d);
free(e);

Sortie :

a 0x5555555592a0
b 0x5555555592d0
e 0x555555559300
c 0x5555555592d0
d 0x5555555592a0

Les blocs libérés de 48 octets attendent dans la liste de leur taille, où le dernier rendu est le premier repris : c reçoit l’ancien b, puis d l’ancien a. malloc(24) demande un bloc de 32 octets, d’une autre taille : il ne puise pas dans cette liste, et prend une place neuve, après b. Les adresses sont converties en entiers avant les free, parce qu’un pointeur vers un bloc libéré ne doit plus être utilisé, pas même comparé.

Un mini-allocateur

L’allocateur suivant gère un tableau statique de 64 octets avec les mêmes idées : un en-tête de 8 octets avant chaque bloc, des blocs de taille multiple de 16, et une liste libre des blocs disponibles, dont le lien s’écrit dans les données du bloc libre.

/* mini_alloc.h -- allocateur pedagogique : un tableau statique, en-tete de 8 octets, blocs multiples de 16,
   liste des blocs libres, premier bloc qui convient (first fit) */
#include <stddef.h>
#include <stdalign.h>
#ifndef TAILLE_TAS
#define TAILLE_TAS 64
#endif
typedef struct Bloc {
    size_t taille;          /* en-tete */
    struct Bloc *suivant;   /* si libre */
} Bloc;
static alignas(16) unsigned char tas[TAILLE_TAS];
static Bloc *libre = NULL;  /* liste libre */
static void mon_init(void)
{
    libre = (Bloc *)(tas + 8);
    libre->taille = TAILLE_TAS - 16;
    libre->suivant = NULL;
}
static void *mon_malloc(size_t n)
{
    size_t t = (n + 8 + 15) / 16 * 16;
    Bloc **pp = &libre;
    while (*pp != NULL && (*pp)->taille < t)
        pp = &(*pp)->suivant;
    if (*pp == NULL)
        return NULL;
    Bloc *b = *pp;
    if (b->taille - t >= 16) {      /* decoupe */
        Bloc *r = (Bloc *)((char *)b + t);
        r->taille = b->taille - t;
        r->suivant = b->suivant;
        *pp = r;
        b->taille = t;
    } else {
        *pp = b->suivant;   /* en entier */
    }
    return (char *)b + 8;
}
static void mon_free(void *p)
{
    Bloc *b = (Bloc *)((char *)p - 8);
    b->suivant = libre;  /* dans les donnees */
    libre = b;
}

Le premier en-tête est en tas + 8 : les données du premier bloc commencent en tas + 16, sur un multiple de 16, et comme toutes les tailles sont des multiples de 16, les données de chaque bloc le sont aussi. mon_malloc calcule la taille du bloc (demande plus en-tête, arrondie à 16), puis parcourt la liste libre avec un pointeur de pointeur, comme supprimer : pp désigne le pointeur à réécrire. Il prend le premier bloc assez grand (first fit). Si le reste fait au moins 16 octets, il le découpe : le reste devient un bloc libre qui prend la place du bloc choisi dans la liste. mon_free retrouve l’en-tête 8 octets avant l’adresse reçue et met le bloc en tête de la liste. Ce code lit et écrit les octets d’un tableau à travers un Bloc *, ce que la règle du type effectif (C17 6.5 §7) n’autorise pas : un allocateur réel s’appuie sur ce que garantit son compilateur, au-delà de la norme.

Exemple pas à pas : le mini-allocateur

mon_init();
char *a = mon_malloc(6);
strcpy(a, "Kolda");
int *b = mon_malloc(4);
*b = 221;
mon_free(a);
char *c = mon_malloc(8);
strcpy(c, "Fatick");
printf("c == a : %d\n", c == a);

Après la ligne 6 : mon_init

Après la ligne 7

Après la ligne 9

Après la ligne 11 : mon_free(a)

Après la ligne 12 : c = mon_malloc(8)

Après la ligne 13

tas est en 0x555555558020, dans .bss ; la grille donne les décalages dans tas, et les liens sont montrés de la même façon (le lien 0x28 vaut en réalité 0x555555558048). Après mon_init, un seul bloc libre de 48 octets commence en 0x08 : son en-tête, puis son lien NULL. mon_malloc(6) demande \(6+8=14\) octets, arrondis à 16 : le bloc libre est découpé, a reçoit 0x10, et le reste, 32 octets, devient le bloc libre en 0x18. mon_malloc(4) prend à son tour 16 octets de ce bloc, en 0x18 ; il reste un bloc libre de 16 octets en 0x28. 221 s’écrit dd 00 00 00 dans les données de b.

mon_free(a) met le bloc de a en tête de la liste : son lien, écrit dans ses données, vaut 0x28 et recouvre « Kolda », comme le lien du tcache recouvrait « Matam ». mon_malloc(8) demande 16 octets : le premier bloc de la liste, en 0x08, convient exactement et sort de la liste sans découpe, si bien que c \(=\) 0x10 \(=\) a. Aucun octet du tableau ne change à cette ligne : seule la variable libre passe de 0x08 à 0x28. « Fatick » recouvre ensuite le lien.

Sortie :

c == a : 1

Fragmentation

mon_free ne fusionne pas deux blocs libres voisins : après de nombreux appels, la mémoire libre peut être éparpillée en petits blocs dont aucun n’est assez grand pour une grande demande, alors que leur total le serait (l’exercice 3 en donne un cas). C’est la fragmentation. Un allocateur réel fusionne les blocs libres adjacents, ce que les en-têtes rendent possible : la glibc le fait pour les blocs qui ne restent ni dans le tcache ni dans les fastbins (Bryant et O’Hallaron, § 9.9.10).

Exercices corrigés

Les trois exercices reprennent les raisonnements de la séance sur des dumps : lire un tableau dynamique et l’en-tête de son bloc, dérouler une suppression par pointeur de pointeur, suivre la liste libre d’un allocateur. Les dumps sont ceux de programmes réels (tas de la glibc, tableau du mini-allocateur), avec des adresses abrégées.

Exercice 1 : un tableau dynamique dans un dump

Un Vecteur v (int *donnees; size_t taille; size_t capacite;) a été créé par vec_init(&v, 3), puis a reçu cinq vec_ajouter. La structure est recopiée en 0x00 ; son bloc, précédé des 8 octets de l’en-tête de la glibc, en 0x20 (adresses abrégées : donnees y est écrit 0x20).

Addr	+0	+1	+2	+3	+4	+5	+6	+7
`0x00`	`20`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x08`	`05`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x10`	`06`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x18`	`21`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x20`	`24`	`00`	`00`	`00`	`29`	`00`	`00`	`00`
`0x28`	`1b`	`00`	`00`	`00`	`1e`	`00`	`00`	`00`
`0x30`	`23`	`00`	`00`	`00`	`00`	`00`	`00`	`00`

Donner v.donnees, v.taille et v.capacite.
Donner les éléments rangés, et dire ce que contiennent les octets 0x34 à 0x37.
Lire l’en-tête du bloc : taille du bloc, octets utiles, nombre d’int qu’il peut recevoir.
On appelle vec_ajouter(&v, 39) puis vec_ajouter(&v, 28). Combien d’appels à realloc, avec quelle demande en octets ? Quelle capacité finale ? Un pointeur int *q = &v.donnees[1] pris avant ces ajouts est-il encore utilisable ?

Correction

La méthode : (1) découper la structure en champs de 8 octets (pointeur, puis deux size_t), en little-endian ; (2) lire l’en-tête, 8 octets avant les données ; (3) lire les éléments par groupes de 4 octets à partir de donnees ; (4) appliquer la règle de vec_ajouter : plein, le bloc double.

(a) Ligne 0x00 : 20 00 00 00 00 00 00 00, soit donnees \(=\) 0x20. Ligne 0x08 : taille \(=\) 5. Ligne 0x10 : capacite \(=\) 6. La capacité initiale était 3 : le quatrième ajout a trouvé le bloc plein et l’a fait passer à 6.

(b) À partir de 0x20, cinq int : 24 00 00 00 \(=\) 36, 29 00 00 00 \(=\) 41, 1b 00 00 00 \(=\) 27, 1e 00 00 00 \(=\) 30, 23 00 00 00 \(=\) 35. La sixième place, de 0x34 à 0x37 (\(\texttt{0x20}+5\times4\)), appartient au bloc mais ne contient aucun élément : sa valeur ne compte pas.

(c) En 0x18 : 0x21. Sans le bit 0 (bloc précédent occupé), le bloc mesure 32 octets, en-tête compris : 24 octets utiles, soit exactement 6 int. Les 12 octets demandés par vec_init avaient été arrondis à ce bloc ; le realloc de 24 octets du quatrième ajout a donc pu garder le bloc en place.

(d) vec_ajouter(&v, 39) : taille (5) est inférieure à capacite (6), aucun realloc ; 39 va dans la sixième place et taille passe à 6. vec_ajouter(&v, 28) : le bloc est plein, realloc reçoit \(2\times6\times4=48\) octets, la capacité passe à 12. Un seul appel à realloc. 48 octets demandent un bloc de 64 (en-tête 0x41), plus grand que les 32 actuels : ici le bloc a été déplacé. q désigne l’ancien bloc, libéré : il n’est plus utilisable, il faut recalculer &v.donnees[1].

Addr	+0	+1	+2	+3	+4	+5	+6	+7
`0x00`	`20`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x08`	`05`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x10`	`06`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x18`	`21`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x20`	`24`	`00`	`00`	`00`	`29`	`00`	`00`	`00`
`0x28`	`1b`	`00`	`00`	`00`	`1e`	`00`	`00`	`00`
`0x30`	`23`	`00`	`00`	`00`	`00`	`00`	`00`	`00`

Dans le dump corrigé, donnees est en orange, taille en bleu, capacite en violet, l’en-tête en gris, les éléments en vert et la place libre en jaune.

Erreur fréquente. Confondre taille et capacité : le bloc a 6 places, mais seuls 5 éléments sont rangés, et c’est taille qui borne le parcours. Autre erreur : lire l’en-tête comme 33 octets ; ses 3 bits de poids faible sont des indicateurs.

Exercice 2 : une suppression dans un dump

Trois nœuds Noeud (int valeur; Noeud *suivant;) ont été alloués l’un après l’autre ; le dump couvre leurs blocs, en-têtes compris (adresses abrégées : les champs suivant y sont écrits de même). Noeud *tete = (Noeud *)0x40;. La fonction supprimer est celle de la section Section 3.4.

Addr	+0	+1	+2	+3	+4	+5	+6	+7
`0x18`	`21`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x20`	`0f`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x28`	`60`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x30`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x38`	`21`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x40`	`06`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x48`	`20`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x50`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x58`	`21`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x60`	`09`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x68`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`

Donner la taille des blocs et celle d’un nœud.
Donner la liste, dans l’ordre, à partir de tete.
Dérouler supprimer(&tete, 15) : donner les valeurs successives de pp, les octets modifiés et le bloc libéré.
On appelle ensuite supprimer(&tete, 6). Que valent pp et tete ? Quels octets du dump l’affectation *pp = n->suivant modifie-t-elle ?

Correction

La méthode : (1) repérer les en-têtes, qui découpent le dump en blocs ; (2) lire chaque nœud à son offset (valeur à l’offset 0, 4 octets de padding, suivant à l’offset 8) ; (3) suivre les champs suivant à partir de tete ; (4) pour supprimer, retenir que pp désigne toujours le pointeur qui mène au nœud examiné.

(a) Les en-têtes sont en 0x18, 0x38 et 0x58 : 0x21, des blocs de 32 octets. Un nœud mesure 16 octets (4 de valeur, 4 de padding, 8 de suivant) ; les données de chaque bloc commencent en 0x20, 0x40 et 0x60, 8 octets après chaque en-tête.

(b) En 0x40 : valeur \(=\) 06 \(=\) 6, suivant (en 0x48) \(=\) 0x20. En 0x20 : 15 (0f), suivant \(=\) 0x60. En 0x60 : 9, suivant \(=\) NULL. La liste est 6, 15, 9 : l’ordre de la liste n’est pas celui des adresses.

(c) pp \(=\) &tete : *pp \(=\) 0x40, de valeur 6, différente de 15 ; pp prend &(*pp)->suivant \(=\) \(\texttt{0x40}+8=\texttt{0x48}\). *pp \(=\) 0x20, de valeur 15 : la boucle s’arrête. n \(=\) 0x20, et *pp = n->suivant écrit 0x60 dans les 8 octets en 0x48 : 60 00 00 00 00 00 00 00. Le bloc 0x20 est libéré (la glibc écrit alors dans ses 16 premiers octets, section Section 6.2). La liste devient 6, 9.

(d) pp \(=\) &tete, et *pp désigne déjà le nœud de valeur 6 : la boucle ne tourne pas. *pp = n->suivant écrit 0x60 dans tete, qui n’est pas dans le dump : aucun octet du dump n’est modifié par cette affectation, puis le bloc 0x40 est libéré. La liste devient 9, et tete \(=\) 0x60.

Addr	+0	+1	+2	+3	+4	+5	+6	+7
`0x18`	`21`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x20`	`0f`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x28`	`60`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x30`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x38`	`21`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x40`	`06`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x48`	`20`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x50`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x58`	`21`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x60`	`09`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x68`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`

Dans le dump corrigé, les en-têtes sont en gris, les valeurs en bleu, les champs suivant en orange, et le champ modifié en (c) en rose.

Erreur fréquente. Penser que supprimer le premier nœud est un cas à part : avec pp, il ne l’est pas, mais il faut alors que la fonction ait reçu &tete. Avec un Noeud *tete en paramètre, la tête de l’appelant ne changerait pas, et resterait un pointeur pendant vers le bloc libéré.

Exercice 3 : le tas du mini-allocateur

mini_alloc.h est compilé avec TAILLE_TAS égal à 96. Après quelques appels à mon_malloc et mon_free, le tableau tas contient les octets suivants (adresses : décalages dans tas ; les liens sont écrits de même). libre vaut tas + 0x18.

Addr	+0	+1	+2	+3	+4	+5	+6	+7
`0x00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x08`	`10`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x10`	`48`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x18`	`20`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x20`	`08`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x28`	`6f`	`72`	`00`	`00`	`00`	`00`	`00`	`00`
`0x30`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x38`	`10`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x40`	`ea`	`07`	`00`	`00`	`00`	`00`	`00`	`00`
`0x48`	`10`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x50`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x58`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`

Découper le tas en blocs, à partir de l’en-tête en 0x08 ; donner la taille de chacun.
Suivre la liste libre depuis libre : quels blocs sont libres, dans quel ordre ? Lesquels sont occupés ?
Interpréter les octets des blocs : 0x40 à 0x43 (un int), 0x28 à 0x2a.
Que rend mon_malloc(4) ? Quels octets écrit-il, et que devient la liste libre ?
Que rend ensuite mon_malloc(20) ? Combien d’octets sont pourtant libres ?

Correction

La méthode : (1) partir du premier en-tête et avancer de la taille lue pour trouver le suivant ; (2) suivre les liens à partir de libre, un lien étant écrit 8 octets après l’en-tête d’un bloc libre ; (3) pour mon_malloc, calculer la taille \(t\) du bloc, puis prendre le premier bloc de la liste de taille au moins \(t\), et le découper si le reste fait au moins 16 octets.

(a) En 0x08 : 10, un bloc de 16 octets, jusqu’à 0x18. En 0x18 : 20, 32 octets, jusqu’à 0x38. En 0x38 : 16, jusqu’à 0x48. En 0x48 : 16, jusqu’à 0x58, la fin des \(96-16=80\) octets gérés à partir de 0x08.

(b) libre \(=\) 0x18 ; le lien de ce bloc, en 0x20, vaut 0x08 ; celui du bloc 0x08, en 0x10, vaut 0x48 ; celui du bloc 0x48, en 0x50, vaut NULL. Les blocs libres sont, dans l’ordre de la liste, 0x18 (32), 0x08 (16) et 0x48 (16). Le bloc 0x38 n’est pas dans la liste : il est occupé. L’ordre de la liste montre que 0x18 a été libéré après 0x08.

(c) 0x40, données du bloc occupé : ea 07 00 00 \(=\) 0x7ea \(=\) 2026. En 0x28 : 6f 72 00, « or » et son terminateur : la fin d’une chaîne rangée dans le bloc 0x18 quand il était occupé (ici « Ziguinchor »), dont les 8 premiers octets ont été recouverts par le lien.

(d) \(t=(4+8+15)/16\times16=16\). Le premier bloc de la liste, 0x18, fait 32 octets : il convient, et le reste (\(32-16=16\)) permet une découpe. mon_malloc rend 0x18\(+8=\) 0x20 ; il écrit 16 dans l’en-tête 0x18, et crée en 0x28 un bloc libre : en-tête 16, lien 0x08 (l’ancien suivant de 0x18). libre devient 0x28, et la liste 0x28, 0x08, 0x48. Un best fit aurait pris le bloc 0x08, de 16 octets exactement, sans découper.

(e) \(t=(20+8+15)/16\times16=32\). Les trois blocs libres font 16 octets : aucun ne convient, mon_malloc rend NULL, alors que 48 octets sont libres. C’est la fragmentation ; la découpe de (d), imposée par le first fit, l’a aggravée.

Addr	+0	+1	+2	+3	+4	+5	+6	+7
`0x00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x08`	`10`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x10`	`48`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x18`	`20`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x20`	`08`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x28`	`6f`	`72`	`00`	`00`	`00`	`00`	`00`	`00`
`0x30`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x38`	`10`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x40`	`ea`	`07`	`00`	`00`	`00`	`00`	`00`	`00`
`0x48`	`10`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x50`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x58`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`

Dans le dump corrigé, les en-têtes sont en orange, les liens des blocs libres en vert, les données du bloc occupé en violet et le reste de chaîne en jaune.

Erreur fréquente. Lire le lien comme l’adresse des données du bloc suivant : le lien désigne l’en-tête (0x08), et les données sont 8 octets plus loin. Autre erreur : oublier les 8 octets d’en-tête dans le calcul de \(t\).

À retenir

Chaque bloc a un propriétaire, qui le libère une fois ; une fonction qui rend un bloc en transfère la propriété, une fonction qui reçoit un pointeur l’emprunte.
Un tableau dynamique garde sa taille et sa capacité, et double la capacité quand il est plein : un ajout coûte un temps constant amorti. Le résultat de realloc passe par un pointeur temporaire ; après un ajout qui peut réallouer, les pointeurs dans le bloc sont à recalculer.
Une liste chaînée relie des nœuds alloués un à un ; une fonction qui modifie la tête reçoit un Noeud **. Un pointeur de pointeur qui avance de champ suivant en champ suivant traite l’insertion en queue et la suppression sans cas particulier pour la tête.
Une liste se libère nœud par nœud, en lisant le suivant avant le free.
Une pile se réalise sur un tableau dynamique ou sur une liste, en \(O(1)\) ; une file, sur un tableau circulaire ou sur une liste avec tete et queue.
Fuite, double free, use after free et pointeur pendant passent souvent inaperçus à l’exécution ; valgrind et AddressSanitizer donnent l’accès fautif, le free et l’allocation.
La glibc aligne chaque bloc sur 16, range sa taille dans un en-tête de 8 octets, et écrit dans un bloc libéré le lien qui le chaîne aux autres blocs libres de sa taille ; le dernier libéré est le premier repris.
Un allocateur first fit parcourt sa liste libre, prend le premier bloc assez grand et découpe le reste ; sans fusion des blocs libres, la mémoire se fragmente.

structure	ajout	ce qu’elle possède
`Vecteur`	`vec_ajouter`, doublement	un bloc (`donnees`)
liste	`inserer_tete`, `inserer_queue` (`Noeud **`)	un bloc par nœud
pile	au sommet (fin du tableau, ou tête)	selon la réalisation
file	en queue ; défiler en tête	tableau circulaire, ou nœuds

Prochaine séance

La Séance 6 (pointeurs de fonctions et généricité) rend génériques ces structures : des éléments désignés par void *, une taille d’élément passée en paramètre, et des pointeurs de fonctions pour comparer, afficher ou libérer les éléments, comme dans qsort et bsearch.

Références

R. E. Bryant, D. R. O’Hallaron — Computer Systems: A Programmer’s Perspective, 3^e éd., Pearson, 2016 (§ 9.9 : allocation dynamique, en-têtes, liste libre, placement, découpe, fusion, fragmentation ; § 9.11 : erreurs de mémoire courantes).
R. C. Seacord — Effective C, 2^e éd., No Starch Press, 2024 (chap. 6 : mémoire allouée dynamiquement).
K. N. King — C Programming: A Modern Approach, 2^e éd., Norton, 2008 (chap. 17 : allocation dynamique, listes chaînées, pointeurs de pointeurs).
B. W. Kernighan, D. M. Ritchie — The C Programming Language, 2^e éd., Prentice Hall, 1988 (chap. 6 : structures auto-référentielles ; § 8.7 : un allocateur de mémoire).
ISO/IEC 9899:2018 (C17) : 6.2.4 (durée de vie des objets), 7.22.3 (fonctions de gestion de la mémoire).

La propriété d’un bloc

Rappel de la Séance 3

Propriétaire, emprunt, transfert

Le tableau dynamique

Taille et capacité

Exemple pas à pas : un tableau dynamique

Coût amorti du doublement

Un pointeur dans le bloc, après realloc

La liste chaînée

Insertion en tête : le pointeur de pointeur

Sans pointeur de pointeur

Insertion en queue, recherche, parcours

Exemple pas à pas : la suppression

Libération complète

Piles et files

Une pile, deux réalisations

Une file sur liste

Une file circulaire

Coût des opérations

Les erreurs du tas

La fuite d’une liste

Libération qui lit un nœud libéré

Un pointeur pendant après une suppression

Un double free par un pointeur pendant

valgrind ou AddressSanitizer

L’intérieur de malloc

En-tête et alignement

Exemple pas à pas : un bloc libéré, puis réutilisé

Dernier libéré, premier servi

Un mini-allocateur

Exemple pas à pas : le mini-allocateur

Exercices corrigés

Exercice 1 : un tableau dynamique dans un dump

Exercice 2 : une suppression dans un dump

Exercice 3 : le tas du mini-allocateur

À retenir

Prochaine séance

Références

Pour cette séance

Un pointeur dans le bloc, après `realloc`

Un double `free` par un pointeur pendant

L’intérieur de `malloc`