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

Tableau dynamique, liste triée, pile, tas de la glibc et mini-allocateur sur machine

TP de la 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

Objectif et organisation

Programmer et observer sur machine les structures de la séance : un tableau dynamique et ses réallocations, un pointeur invalidé par realloc, une liste triée manipulée par pointeur de pointeur, une pile de caractères, les blocs libres de la glibc sous gdb, et un allocateur first fit comparé à un best fit. Le TP compte six étapes ; chaque étape fournit un programme du dossier TP_S05_code_depart/ (qui contient aussi un Makefile), avec des TODO à compléter et, quand c’est annoncé, une erreur volontaire. Les questions demandent d’observer une sortie, de l’expliquer avec le cours, puis de modifier le programme. Les réponses se notent dans un fichier reponses.txt, avec les sorties copiées.

Commandes

Décompresser TP_S05_code_depart.zip, se placer dans le dossier TP_S05_code_depart/ qu’il crée, puis lancer le conteneur depuis ce dossier :

docker run -it --rm --security-opt seccomp=unconfined \
    -v "$(pwd)":/workspace elbachirtoure/c-advanced-course:v2.0     # lancer le conteneur

Windows, PowerShell : -v "${PWD}:/workspace" à la place de -v "$(pwd)":/workspace ; Git Bash et autres cas : TP-1, étape 2. Dans le conteneur, ce dossier est /workspace :

make                      # compile tout (gcc -std=c17 -Wall -Wextra -O0 -g)
make etape1_vecteur       # un seul programme (apres une modification)
make -B prog              # recompiler meme a jour (relire les avertissements de gcc)
make asan                 # etape2_invalide_asan, etape3_liste_asan (-fsanitize=address)
make clean                # retirer les executables
setarch -R ./prog         # execution sans alea des adresses
valgrind --leak-check=full ./prog   # fuites et acces invalides au tas
gdb -q ./prog             # break, run, next, print, x/4gx

Les adresses affichées diffèrent d’une machine à l’autre ; les questions portent sur les tailles, les en-têtes, les écarts et l’ordre de réutilisation. Ce qui concerne l’intérieur de malloc vaut pour la glibc (ici 2.39).

Étape 1 : un tableau dynamique et ses réallocations

Le programme etape1_vecteur.c contient le type Vecteur du cours, une fonction entete qui lit les 8 octets qui précèdent un bloc (l’en-tête de la glibc, à des fins d’observation), et une fonction essai qui fait 40 ajouts à partir d’une capacité 1 et affiche chaque changement de capacité.

/* TODO 1 : ranger x a l'indice taille ; si le bloc est plein, doubler d'abord
   la capacite (0 devient 1) par realloc, en passant par un pointeur temporaire.
   Rendre 1, ou 0 si realloc echoue. */
int vec_ajouter(Vecteur *v, int x)
{
    (void)v;
    (void)x;
    return 0;
}

void vec_liberer(Vecteur *v)
{
    free(v->donnees);
    *v = (Vecteur){NULL, 0, 0};
}

/* en-tete du bloc de la glibc : les 8 octets qui precedent les donnees. Lire avant le
   bloc est un comportement indefini selon la norme : cette fonction sert seulement a
   observer la glibc 2.39, sans valgrind ni AddressSanitizer. */
size_t entete(const void *p)
{
    return *((const size_t *)p - 1);
}

/* n ajouts ; avec obstacle, un bloc de 24 octets est alloue apres chaque ajout */
void essai(int n, int obstacle)
{
    Vecteur v;
    char *autres[64];
    vec_init(&v, 1);
    size_t cap = v.capacite;
    uintptr_t adr = (uintptr_t)v.donnees;
    int deplacements = 0;
    printf("%s obstacle :\n", obstacle ? "avec" : "sans");
    for (int i = 0; i < n; i++) {
        vec_ajouter(&v, 10 * i);
        if (obstacle)
            /* TODO 2 : allouer ici un bloc de 24 octets */
            autres[i] = NULL;
        if (v.capacite != cap) {
            int bouge = (uintptr_t)v.donnees != adr;
            deplacements += bouge;
            printf("  ajout %2d : capacite %2zu, en-tete 0x%02zx, %s\n", i + 1,
                   v.capacite, entete(v.donnees), bouge ? "deplace" : "en place");
            cap = v.capacite;
            adr = (uintptr_t)v.donnees;
        }
    }
    printf("  %d deplacements, taille %zu, capacite %zu\n", deplacements, v.taille,
           v.capacite);
    if (obstacle)
        for (int i = 0; i < n; i++)
            free(autres[i]);
    vec_liberer(&v);
}

Modifier. Compléter le TODO 1 (vec_ajouter, doublement par un pointeur temporaire). Compiler, exécuter, et copier la sortie. Ni valgrind ni AddressSanitizer à cette étape : entete lit avant le bloc, un comportement indéfini que le programme commet seulement pour observer la glibc.
Observer. Pour chaque changement de capacité, relever l’en-tête. Vérifier qu’il vaut la taille du bloc plus 1, et que cette taille est le plus petit multiple de 16 au moins égal à 4 * capacite + 8, avec un minimum de 32.
Expliquer. Sans obstacle, presque toutes les réallocations se font en place. Laquelle déplace le bloc ? Indice : quel bloc la première exécution de printf alloue-t-elle sur le tas ?
Modifier. Compléter le TODO 2 (un bloc de 24 octets alloué après chaque ajout) et comparer le nombre de déplacements. Expliquer.
Modifier. Remplacer le doublement par cap = v->capacite + v->capacite / 2 + 1. Combien de changements de capacité pour 40 ajouts ? Conclure sur le coût amorti.

Étape 2 : un pointeur invalidé par `realloc`

etape2_invalide.c cherche le plus fort relevé de pluie, puis continue à remplir le tableau. Il contient une erreur volontaire : l’adresse du maximum est gardée pendant les ajouts.

int main(void)
{
    int pluie[] = {12, 48, 31, 7};      /* releves de Kolda, en mm */
    Vecteur v = {NULL, 0, 0};
    for (int i = 0; i < 4; i++)
        vec_ajouter(&v, pluie[i]);
    int *pmax = &v.donnees[0];          /* adresse du maximum */
    for (size_t i = 1; i < v.taille; i++)
        if (v.donnees[i] > *pmax)
            pmax = &v.donnees[i];
    char *etiquette = malloc(16);       /* un autre bloc, alloue entre-temps */
    for (int i = 0; i < 4; i++)
        vec_ajouter(&v, pluie[i] / 2);
    printf("maximum : %d, taille %zu, capacite %zu\n", *pmax, v.taille, v.capacite);
    free(etiquette);
    free(v.donnees);
    return 0;
}

Observer. Compiler et exécuter sans outil : la valeur affichée est-elle 48 ? Recompiler avec -fsanitize=address (make asan, puis ./etape2_invalide_asan) et copier les lignes ERROR, READ of size, freed by et la ligne suivante.
Expliquer. Quelle ligne libère le bloc que désigne pmax ? Pourquoi le bloc est-il déplacé (rôle de etiquette) ?
Modifier. Garder un indice imax au lieu de pmax, et vérifier que la sortie est correcte et qu’AddressSanitizer ne signale plus rien.

Étape 3 : une liste triée

etape3_liste.c construit une liste croissante à partir de sept relevés, puis retire toutes les occurrences d’une valeur. La fonction liberer contient une erreur volontaire.

/* TODO 1 : inserer v a sa place dans une liste croissante,
   avec un pointeur de pointeur (comme inserer_queue) ;
   rendre 1, ou 0 si malloc echoue */
int inserer_trie(Noeud **pp, int v)
{
    (void)pp;
    (void)v;
    return 0;
}

/* TODO 2 : retirer (et liberer) tous les noeuds de valeur v ; rendre leur nombre */
int supprimer_tous(Noeud **pp, int v)
{
    (void)pp;
    (void)v;
    return 0;
}

void afficher(const Noeud *p)
{
    for (; p != NULL; p = p->suivant)
        printf("%d -> ", p->valeur);
    printf("NULL\n");
}

void liberer(Noeud **pt)
{
    for (Noeud *p = *pt; p != NULL; p = p->suivant)
        free(p);
    *pt = NULL;
}

int main(void)
{
    int t[] = {42, 7, 19, 7, 88, 7, 3};
    Noeud *tete = NULL;
    for (int i = 0; i < 7; i++)
        inserer_trie(&tete, t[i]);
    afficher(tete);
    printf("%d noeuds retires\n", supprimer_tous(&tete, 7));
    afficher(tete);
    printf("%d noeuds retires\n", supprimer_tous(&tete, 3));
    afficher(tete);
    liberer(&tete);
    return 0;
}

Modifier. Compléter le TODO 1, inserer_trie, avec un pointeur de pointeur : pp avance tant que le nœud désigné a une valeur plus petite que v. Vérifier que la première ligne affichée est 3 -> 7 -> 7 -> 7 -> 19 -> 42 -> 88 -> NULL.
Modifier. Compléter le TODO 2, supprimer_tous. Quand un nœud est retiré, pp ne doit pas avancer : pourquoi ?
Observer. gcc avertit déjà à la compilation ; recopier l’avertissement. Exécuter avec AddressSanitizer (make asan, puis ./etape3_liste_asan) : quelle lecture est signalée, à quel offset du bloc ?
Modifier. Corriger liberer (lire le suivant avant le free), puis vérifier sous valgrind que tous les blocs sont libérés. Combien d’allocations valgrind compte-t-il, et pourquoi une de plus que de nœuds insérés ?

Étape 4 : une pile pour vérifier les parenthèses

etape4_parentheses.c vérifie qu’une expression est bien parenthésée : chaque ouvrante est empilée, chaque fermante dépile et doit correspondre au sommet, et la pile doit être vide à la fin. La pile est un tableau dynamique de caractères. La fonction verifier contient une erreur volontaire.

typedef struct {
    char *t;
    size_t n;
    size_t cap;
} Pile;

/* TODO 1 : empiler c au sommet ; la capacite part de 4 et double (realloc,
   pointeur temporaire) */
int empiler(Pile *p, char c)
{
    (void)p;
    (void)c;
    return 0;
}

/* TODO 2 : ranger le sommet dans *c et le retirer ; rendre 0 si la pile est vide */
int depiler(Pile *p, char *c)
{
    (void)p;
    (void)c;
    return 0;
}

char ouvrante(char c)
{
    return c == ')' ? '(' : (c == ']' ? '[' : '{');
}

/* 1 si bien parenthesee */
int verifier(const char *s, size_t *profondeur)
{
    Pile p = {NULL, 0, 0};
    *profondeur = 0;
    for (; *s != '\0'; s++) {
        char c;
        if (*s == '(' || *s == '[' || *s == '{') {
            empiler(&p, *s);
            if (p.n > *profondeur)
                *profondeur = p.n;
        } else if (*s == ')' || *s == ']' || *s == '}') {
            if (!depiler(&p, &c) || c != ouvrante(*s))
                return 0;
        }
    }
    int ok = p.n == 0;
    free(p.t);
    return ok;
}

int main(void)
{
    const char *e[] = {"{[(a + b) * c] - (d)}", "((x)", "[(])", "f(g(h(i(j(k)))))"};
    for (int i = 0; i < 4; i++) {
        size_t prof;
        int ok = verifier(e[i], &prof);
        printf("%-22s %s, profondeur %zu\n", e[i], ok ? "correcte" : "incorrecte",
               prof);
    }
    return 0;
}

Modifier. Compléter les TODO 1 et 2 (empiler, depiler). Vérifier les quatre verdicts et les profondeurs affichées.
Observer. Exécuter sous valgrind : combien d’octets sont perdus, et pour quelle expression ? Suivre l’exécution de verifier sur cette expression pour trouver le chemin sans free.
Modifier. Corriger verifier pour que la pile soit libérée sur tous les chemins, et vérifier sous valgrind.
Expliquer. Pour f(g(h(i(j(k))))), combien d’appels à realloc la pile fait-elle, et quelle capacité atteint-elle ?

Étape 5 : les blocs libres de la glibc, sous gdb

/* etape5_glibc.c -- TP Seance 5, etape 5 : observer les blocs libres de la glibc
   (sous gdb) et leur reutilisation.
   Compilation :
   gcc -std=c17 -Wall -Wextra -O0 -g etape5_glibc.c -o etape5_glibc */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>

int main(void)
{
    char *a = malloc(24);
    char *b = malloc(24);
    char *c = malloc(100);
    uintptr_t ua = (uintptr_t)a;
    uintptr_t ub = (uintptr_t)b;
    free(a);
    free(b);
    char *d = malloc(24);
    char *e = malloc(24);
    char *f = malloc(24);
    printf("a %#" PRIxPTR "\nb %#" PRIxPTR "\n", ua, ub);
    printf("c %p\nd %p\ne %p\nf %p\n", (void *)c, (void *)d, (void *)e, (void *)f);
    free(c);
    free(d);
    free(e);
    free(f);
    return 0;
}

Observer. Exécuter le programme : quelles adresses d, e et f reçoivent-elles ? Relier ces adresses à l’ordre des free.
Observer. Sous gdb : break 19, run, puis x/4gx a - 8 et x/4gx b - 8. Repérer l’en-tête de chaque bloc et ses 16 premiers octets.
Expliquer. Le premier mot de a vaut ua >> 12 (print/x ua >> 12) : c’est le lien NULL masqué. Le premier mot de b vaut (ub >> 12) ^ ua : le vérifier par print/x, et en déduire vers quel bloc pointe le lien de b. Que remarquer sur le second mot des deux blocs ?
Observer. next, next, puis print/x d et print/x e. Expliquer pourquoi f ne reprend aucun des deux blocs, et pourquoi c n’intervient pas.

Étape 6 : first fit et best fit

etape6_mini.c reprend le mini-allocateur du cours sur un tableau de 128 octets ; la découpe est isolée dans une fonction prendre. Le scénario alloue trois blocs, en libère deux, puis demande 8 puis 36 octets.

void *mon_malloc(size_t n)          /* first fit */
{
    size_t t = (n + 8 + 15) / 16 * 16;
    Bloc **pp = &libre;
    while (*pp != NULL && (*pp)->taille < t)
        pp = &(*pp)->suivant;
    return *pp == NULL ? NULL : prendre(pp, t);
}

/* TODO 2 : best fit.
   Parcourir toute la liste, garder l'adresse du pointeur (Bloc **) qui mene
   au plus petit bloc de taille >= t, puis appeler prendre ;
   rendre NULL si aucun bloc ne convient. */
void *mon_malloc_best(size_t n)
{
    (void)n;
    return NULL;
}

void mon_free(void *p)
{
    Bloc *b = (Bloc *)((char *)p - 8);
    b->suivant = libre;
    libre = b;
}

/* TODO 1 : afficher quoi, puis chaque bloc de la liste libre : son decalage dans
   tas (0x%02tx) et sa taille */
void afficher_liste(const char *quoi)
{
    printf("%-20s libre : (a completer)\n", quoi);
}

void scenario(int best, const char *nom)
{
    mon_init();
    char *a = mon_malloc(40);
    char *b = mon_malloc(4);
    char *c = mon_malloc(20);
    mon_free(b);
    mon_free(a);
    afficher_liste("apres les free");
    char *d = best ? mon_malloc_best(8) : mon_malloc(8);
    if (d == NULL)
        printf("%s : mon_malloc(8) -> NULL\n", nom);
    else
        printf("%s : mon_malloc(8) -> 0x%02tx\n", nom, (unsigned char *)d - tas);
    afficher_liste("");
    char *e = best ? mon_malloc_best(36) : mon_malloc(36);
    if (e == NULL)
        printf("%s : mon_malloc(36) -> NULL\n", nom);
    else
        printf("%s : mon_malloc(36) -> 0x%02tx\n", nom, (unsigned char *)e - tas);
    (void)c;
}

Modifier. Compléter le TODO 1, afficher_liste, qui affiche chaque bloc de la liste libre (décalage dans tas et taille). Avant d’exécuter, prévoir à la main la liste libre après les deux free ; comparer.
Observer. Avec le first fit, quel bloc mon_malloc(8) prend-il, et pourquoi mon_malloc(36) échoue-t-il alors qu’il reste 64 octets libres ?
Modifier. Compléter le TODO 2, mon_malloc_best. Comparer les deux scénarios.
Modifier. Écrire un scénario où le best fit échoue alors que le first fit réussit (indice : le best fit laisse de petits restes). Le décrire en trois lignes dans reponses.txt.