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

Tableau dynamique, listes, files, erreurs du tas, allocateurs

TD 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

Lire un tableau dynamique, une liste et le tas d’un allocateur dans un dump, dérouler les fonctions du cours (vec_ajouter, inserer_queue, supprimer, file circulaire, mon_malloc), calculer des coûts de réallocation, et reconnaître les erreurs de gestion du tas. Machine x86-64 little-endian : int 4 octets, size_t et pointeurs 8 ; struct Noeud { int valeur; struct Noeud *suivant; } mesure 16 octets (suivant à l’offset 8). Les fonctions sont celles du cours ; les adresses sont écrites en hexadécimal et 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éé avec une capacité 2, puis a reçu trois vec_ajouter. La structure est recopiée en 0x40 ; son bloc du tas, précédé de l’en-tête de la glibc, en 0x60.

Addr	+0	+1	+2	+3	+4	+5	+6	+7
`0x40`	`60`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x48`	`03`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x50`	`04`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x58`	`21`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x60`	`78`	`00`	`00`	`00`	`4b`	`00`	`00`	`00`
`0x68`	`36`	`01`	`00`	`00`	`00`	`00`	`00`	`00`

Donner v.donnees, v.taille, v.capacite, puis les éléments rangés.
Lire l’en-tête : taille du bloc, octets utiles. Le troisième ajout a-t-il pu garder le bloc en place ? Justifier.
On continue les ajouts jusqu’à 100 éléments. Donner la suite des capacités, le nombre d’appels à realloc et le nombre d’éléments recopiés si chaque appel déplaçait le bloc.
Combien d’octets le dernier realloc demande-t-il ? Quelle taille de bloc la glibc réserve-t-elle (même règle d’arrondi qu’en cours) ? Quel en-tête attendre ?

Exercice 2 : trois stratégies de croissance

Un tableau part d’une capacité 2 et reçoit \(n\) ajouts. Quand il est plein, sa capacité devient \(2c\) (doublement), \(c + c/2\) en division entière (facteur 1,5) ou \(c + 10\) (pas fixe).

Pour \(n = 100\), écrire la suite des capacités de chaque stratégie, puis remplir le tableau (copies : éléments recopiés si chaque realloc déplaçait le bloc).

stratégie appels à realloc copies au pire

doublement

facteur 1,5

pas de 10
Pour \(n = 10\,000\), le doublement donne 13 appels et 16 382 copies, le facteur 1,5 donne 22 appels et 24 283 copies, le pas de 10 donne 1000 appels et 4 997 000 copies. Rapporter chaque nombre de copies à \(n\) et conclure sur le coût amorti de chaque stratégie.
Quelle stratégie gaspille le plus de places libres juste après une réallocation ? Proposer un argument pour le facteur 1,5.

Exercice 3 : une liste dans le tas

Trois nœuds ont été alloués l’un après l’autre ; le dump couvre leurs blocs, en-têtes compris (les champs suivant sont écrits en adresses abrégées). Noeud *tete = (Noeud *)0x140;

Addr	+0	+1	+2	+3	+4	+5	+6	+7
`0x118`	`21`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x120`	`1b`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x128`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x130`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x138`	`21`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x140`	`0e`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x148`	`60`	`01`	`00`	`00`	`00`	`00`	`00`	`00`
`0x150`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x158`	`21`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x160`	`03`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x168`	`20`	`01`	`00`	`00`	`00`	`00`	`00`	`00`

Donner la liste dans l’ordre depuis tete, avec l’adresse de chaque nœud.
Dérouler inserer_queue(&tete, 50) : valeurs successives de pp, puis les 8 octets écrits par *pp = n et leur adresse, sachant que le nouveau nœud est alloué en 0x180.
Dérouler ensuite supprimer(&tete, 14) : que devient tete ? Quel bloc est libéré ? Donner la liste.
Que fait supprimer(&tete, 99) ? Donner la valeur finale de pp.

Exercice 4 : une file circulaire

Une FileC de capacité 3 (t mis à zéro par calloc, debut \(=\) n \(=\) 0) reçoit, dans l’ordre : enfiler 2, enfiler 4, defiler, enfiler 6, enfiler 8, defiler, enfiler 1, enfiler 3. Remplir le tableau après chaque opération (pour un defiler, noter la valeur rendue).

opération	rendu	`debut`	`n`	`t` (toutes les cases)
`enfiler 2`
`enfiler 4`
`defiler`
`enfiler 6`
`enfiler 8`
`defiler`
`enfiler 1`
`enfiler 3`

Exercice 5 : diagnostiquer

Pour chaque programme (les fonctions vec_ajouter, enfiler, dupliquer sont celles du cours, sauf mention), dire ce qui est incorrect, ce qu’en dit AddressSanitizer (type d’erreur, lecture ou écriture, taille), et proposer une correction.

/* (a) */
Vecteur v = {malloc(2 * sizeof(int)), 0, 2};
char *journal = malloc(32);
vec_ajouter(&v, 18);
int *premier = &v.donnees[0];
for (int i = 1; i <= 4; i++)
    vec_ajouter(&v, 18 + i);
printf("%d\n", *premier);

/* (b) */
void vider(Noeud *t)
{
    while (t != NULL) {
        Noeud *s = t->suivant;
        free(t);
        t = s;
    }
}
/* dans main, apres une liste d'un noeud */
vider(tete);
if (tete != NULL)
    printf("%d\n", tete->valeur);

/* (c) defiler, version du programme */
int defiler(File *f)
{
    Noeud *n = f->tete;
    int x = n->valeur;
    f->tete = n->suivant;
    free(n);
    return x;
}
/* dans main */
File f = {NULL, NULL};
enfiler(&f, 7);
printf("%d\n", defiler(&f));
enfiler(&f, 9);
printf("%d\n", defiler(&f));

/* (d) */
char *ville = dupliquer("Matam");
ville = dupliquer("Podor");
printf("%s\n", ville);
free(ville);

Sans AddressSanitizer, (a) et (b) affichent tous deux 1431655769, et (c), exécuté avec sa sortie redirigée vers un fichier, par ./prog > s.txt, s’arrête sur SIGSEGV en laissant s.txt vide. Expliquer ces trois comportements. Lancé dans un terminal, sans redirection, (c) affiche pourtant 7 avant de s’arrêter : pourquoi ?

Exercice 6 : first fit et best fit

mini_alloc.h est compilé avec TAILLE_TAS égal à 128. Après quelques appels, tas contient les octets suivants (décalages dans tas, liens compris) ; libre \(=\) tas + 0x38.

Addr	+0	+1	+2	+3	+4	+5	+6	+7
`0x00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x08`	`20`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x10`	`54`	`61`	`6d`	`62`	`61`	`63`	`6f`	`75`
`0x18`	`6e`	`64`	`61`	`00`	`00`	`00`	`00`	`00`
`0x20`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x28`	`10`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x30`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x38`	`30`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x40`	`28`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x48`	`75`	`69`	`73`	`00`	`00`	`00`	`00`	`00`
`0x50`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x58`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x60`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x68`	`10`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x70`	`4b`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x78`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`

Découper le tas en blocs depuis l’en-tête en 0x08, puis suivre la liste libre. Quels blocs sont occupés ? Que contiennent-ils (0x10 à 0x1b ; 0x70) ? Que sont les octets 0x48 à 0x4a ?
Avec le first fit du cours : que rendent mon_malloc(4), puis mon_malloc(40) ? Donner les octets écrits et la liste libre après chaque appel.
Même question, à partir du même état, avec un best fit (le plus petit bloc libre assez grand).
Conclure : dans quel cas le first fit fragmente-t-il la mémoire ?

Exercice 7 (approfondissement) : les en-têtes de la glibc

Un programme appelle a = malloc(10), b = malloc(40), c = malloc(70), remplit les blocs, puis appelle free(b). Le dump commence 8 octets avant a ; les adresses sont abrégées (a \(=\) 0x10), mais les octets sont ceux de la mémoire (adresses réelles de la forme 0x55555555a...). Les 8 octets en 0x38 diffèrent à chaque exécution.

Addr	+0	+1	+2	+3	+4	+5	+6	+7
`0x08`	`21`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x10`	`11`	`11`	`11`	`11`	`11`	`11`	`11`	`11`
`0x18`	`11`	`11`	`00`	`00`	`00`	`00`	`00`	`00`
`0x20`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x28`	`31`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x30`	`5a`	`55`	`55`	`55`	`05`	`00`	`00`	`00`
`0x38`	`de`	`00`	`59`	`76`	`00`	`67`	`d7`	`97`
`0x40`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x48`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x50`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x58`	`51`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x60`	`33`	`33`	`33`	`33`	`33`	`33`	`33`	`33`

Repérer les trois en-têtes. Donner la taille de chaque bloc, ses octets utiles, et l’intervalle des demandes malloc(n) qui reçoivent un bloc de cette taille.
Quel bloc est libre ? Comment le voir dans ses 16 premiers octets ? Peut-on retrouver ce que contenait le bloc ? Justifier à partir du dump.
Le programme appelle ensuite malloc(36), puis malloc(20). Quelle adresse abrégée chacun rend-il ?

Pour cette séance

Le cours

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

Les slides

Slides de la séance 5

À lire en ligne

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

À télécharger

Code de départ du TP (ZIP, 6 Ko)

Retour au sommet

stratégie	appels à `realloc`	copies au pire
doublement
facteur 1,5
pas de 10