1. Écrire un programme testant la fonction sur quelques exemples.

   On pourra utiliser le tableau {0, 2, 4, 6, 8} et chercher les valeurs entre 0 et 9.

2. Dans quels cas la fonction ne produit-elle pas l’effet souhaité ?

Aidons Bob à corriger sa fonction en utilisant le programme gdb.

gdb est un débogueur, comme python tutor mais en ligne de commande.

Pour pouvoir l’utiliser sur un programme C, il faut ajouter l’option -g lors de la compilation de ce dernier.

On exécute ensuite gdb en lui fournissant l’exécutable comme paramètre :

$ gdb --quiet ./mon_programme
Reading symbols from ./mon_programme...
(gdb)

Si gdb vous demande si vous voulez activer debuginfod, répondez no.

3. À ce stade, le programme de Bob est prêt à être lancé dans l’environnement de débogage. Taper la commande run pour démarrer son exécution.

   Si une erreur de la forme cannot exec: -c ... se produit, il faut ajouter au fichier ~/.bashrc la ligne export SHELL=/bin/bash (et créer le fichier s’il n’existe pas)

Le programme se comporte comme attendu : mal dans certains cas. On peut l’interrompre avec la combinaison Ctrl C.

4. Déterminer à quoi correspondent les différentes informations dans le message donné par gdb.

5. L’exécution du programme est juste interrompue. Le programme n’est pas tué. On peut reprendre son exécution avec la commande continue (ou c) ou exécuter instruction par instruction avec la commande next (ou n).

   Essayez ces deux commandes.

6. Pour visualiser l’état des variables du programme, deux commandes sont utiles : print <nom de variable> et display <nom de variable>.

• print left : affiche la valeur de la variable left (si elle existe à l’endroit où le programme a été interrompu)
• display left : comme print left mais le contenu de la variable est affiché à chaque fois que le programme est interrompu.

Affichez pas à pas l’état des variables pour identifier la source du problème de la fonction dichotomie de Bob.

Pour quitter gdb, on peut utiliser la commande quit ou bien utiliser la combinaison Ctrl D.

7. (Pour aller plus loin) Plutôt que d’exécuter péniblement instruction par instruction, on peut demander à gdb de poursuivre l’exécution jusqu’à une instruction particulière du programme. On appelle ça un point d’arrêt (ou breakpoint). Pour définir un point d’arrêt on peut indiquer :

   • le nom de la fonction sur laquelle s’arrêter : (gdb) break dichotomie
   • le nom du fichier avec le numéro de la ligne de l’instruction : break main.c:20

   En lançant le programme avec run ou en poursuivant son exécution avec continue, gdb interrompra l’exécution quand il tombera sur l’instruction indiqué par un point d’arrêt.

   Identifiez une ligne de la fonction dichotomie qui pourrait servir de point d'arrêt puis testez à nouveau.

Dans cette exercice, on propose de configurer vscodium (présent sur les machines de TP) afin d’y intégrer gdb. L’intégration d’un debugger se fait via une extension. Parmi les possibilités vous est suggéré l’extension Native Debug.

Une fois installée, une configuration minimale¹ peut être réalisée en créant le fichier .vscode/launch.json à la racine de votre répertoire de travail² :

{
    "version": "0.2.0",
    "configurations": [
        {
            "name": "Debug with gdb",
            "request": "launch",
            "type": "gdb",
            // Exécutable à déboguer
            "target": "${fileBasenameNoExtension}",
            // Dossier d'exécution
            "cwd": "${fileDirname}",
            // Quelques options de QoL
            "stopAtEntry": true, 
            "valuesFormatting": "prettyPrinters",
        }
    ]
}

Cette configuration vous permettra de déboguer l’exécutable produit à partir du fichier source affiché dans VSCodium.

1. Installer (si nécessaire) et configurer cette extension.

Pour passer à la pratique, voici un programme présentant plusieurs problèmes qu’on peut constater à la compilation et à l’exécution.

#include <stdio.h>
#include <stdlib.h>

struct Cell {
    int value;
    struct Cell *next;
};

struct Cell *cell_new(int value) {
    struct Cell *p = malloc(sizeof *p);
    if (p == NULL)
        exit(2);
    p->value = value;
    return p;
}

void sort_insert(struct Cell **head, struct Cell *cell) {
    if (*head == NULL) {
        *head = cell;
        return;
    }
    if ((*head)->value >= cell->value) {
        cell->next = *head;
        *head = cell;
        return;
    }
    sort_insert(&((*head)->next), cell);
}

void power2(struct Cell *list) {
    if (list == NULL)
        return;
    list->value = list->value * list->value;
    power2(list->next);
}

void list_free(struct Cell *list) {
    if (list == NULL)
        return;
    free(list);
    list_free(list->next);
}

void list_print(struct Cell *list) {
    if (list == NULL)
        printf("\n");
    else {
        printf("%d ", list->value);
        list_print(list);
    }
}

int main(int argc, char **argv) {
    struct Cell *list = NULL;
    for (int j = 0; j < 5; ++j) {
        for (int i = 0; i < 5; ++i)
            sort_insert(&list, cell_new((i * 17 + j * 19) % 23));
        list_print(list);
        power2(list);
        list_print(list);
        list_free(list);
    }
    return 0;
}

2. Compiler le programme (sans oublier l’option -g) et constater le problème déjà signalée à la compilation, et l’erreur à l’exécution.

3. Ouvrir le panneau latéral Run and Debug (Ctrl Maj D) et démarrer le débogage du fichier courant en cliquant sur le triangle vert (F5). Cela lance gdb sur votre programme et exécute la commande run.

4. Identifier les différentes informations disponibles. Parmi les bouttons de la barre d’actions, lesquels correspondent à des commandes gdb vues en cours ?

5. En utilisant les bouttons pour exécuter pas à pas, identifier l’instruction de la fonction main qui est problématique.

6. Il est possible d’ajouter un point d’arrêt à une instruction en cliquant sur le point rouge qui apparaît en survolant le numéro de la ligne correspondante. Utiliser cette fonctionnalité pour déterminer si le soucis vient du code de la fonction suspecte ou bien de la donnée.

7. Corriger cette erreur sans oublier de recompiler votre programme.

8. Reprendre la question 6 pour corriger la dernière erreur (Hint: la correction est simple).

Le code suivant ne se comporte pas comme attendu.

#include <stdio.h>
#include <string.h>

typedef struct {
    char *mots[256];
    int taille;
} Dico;

/* Insertion triée */
void inserer_mot(Dico *dico, char *mot) {
    int i;
    if (dico->taille >= 256)
        return;

    for (i = dico->taille - 1; i >= 0 && strcmp(dico->mots[i], mot) > 0; i--) {
        dico->mots[i + 1] = dico->mots[i];
    }
    dico->mots[i + 1] = mot;

    dico->taille++;
}

void afficher_dico(Dico *dico) {
    int i;
    for (i = 0; i < dico->taille; i++)
        printf("%s\n", dico->mots[i]);
}

int main() {
    Dico dico = {0};
    char mot[256] = "";

    dico.taille = 0;

    /* Mots de base */
    inserer_mot(&dico, "zoo");
    inserer_mot(&dico, "anaconda");
    inserer_mot(&dico, "mitochondrie");

    printf("Dico de base\n"
           "============\n");
    afficher_dico(&dico);
    printf("------------\n");

    /* Ajout de mots de l'utilisateur, Ctrl D pour stopper la saisie */
    while (scanf(" %s", mot) > 0) {
        inserer_mot(&dico, mot);
    }

    printf("Dico complet\n"
           "============\n");
    afficher_dico(&dico);
    printf("------------\n");

    return 0;
}

1. Tester et constater le problème.

2. En utilisant gdb depuis le terminal, placer un point d’arrêt avant la saisie utilisateur, observer l’évolution du contenu du dictionnaire dico avec la commande print ou display après chaque ajout.

   On peut placer le point d’arrêt via la commande (gdb) break mon_programme.c:47 où 47 est le numéro de la ligne du while

3. Comment faudrait-il corriger le programme afin qu’il liste les mots entrés par l’utilisateur ?

1. Diagnostiquer le problème à l’aide de gdb.

   Hint: on pourra utiliser la commande backtrace pour examiner la pile d’appel

2. Quelle(s) ligne(s) semblent concernée(s) ?

1. Tester la fonction sur des tableaux de 100, 1000, 10000, 100000 entrées.
2. Quel est le problème ?
3. Proposer une solution.

Ce code calcule bêtement et récursivement la somme de deux entiers.

#include <stdio.h>

int add(int a, int b) {
    if (a < 0) return add(a + 1, b - 1);
    if (a > 0) return add(a - 1, b + 1);
    return b;
}

int main(void) {
    for (int i = 1; i < 10000000; i *= 10) {
        printf("add(%d, %d)\t= %d\n", i - 1, 1, add(i - 1, 1));
    }
    return 0;
}

On ne cherchera pas ici à trouver une solution mais à comprendre le problème.

1. Sachant que la pile est un espace de taille limitées (8Mo sur les machines de TP sous Linux), estimer à l’aide de gdb la taille de l’espace mémoire réservé dans la pile à chaque appel de la fonction add.

On souhaite calculer les valeurs du triangle de Pascal données par la fonction binomiale : \[binomial(p, n) = \frac{n!}{p!(n-p)!}\]

1. Exprimer en fonction de \(n\) la valeur de \(binomial(1, n)\)
2. Tester le programme suivant. Observe-t-on les valeurs attendues ?

int factoriel(int n) {
    if (n == 0) return 1;
    return n * factoriel(n-1);
}
int binomial(int p, int n) {
    return factoriel(n) / (factoriel(p) * factoriel(n - p));
}

int main(void) {
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < i; j++) {
            printf(" %d", binomial(j, i));
        }
        printf("\n");
    }
    return 0;
}

Lorsqu’on écrit un programme et que ce dernier ne se comporte pas comme attendu, il s’agit généralement d’une erreur dans l’écriture du code.

Ici, l’erreur n’est pas algorithmique, pas de pointeur non plus, ce qui rend sa détection compliquée. L’erreur se cache en fait sur les limites de représentation des valeurs en C.

En effet, dans le calcul de la binomiale, on calcule des factorielles. La factorielle de 13 vaut 6’227’020’800 là où la valeur maximale d’un int sur nos machines est de \(2^{31}-1\) soit 2’147’483’648.

En ajoutant lors de la compilation l’option -fsanitize=undefined, on peut demander au programme de diagnostiquer lui même ce genre de problème.

1. Ajouter -fsanitize=undefined lors de la compilation et tester à nouveau le programme.

Cette option intègre l’outil de détection de comportements dit non définis (Undefined Behavior ou UB). On peut le retrouver dans la nature sous le nom UBSan.

Pour corriger le problème, on peut :

• changer le type int pour le type long int laissant un peu plus de marge pour le calcul
• changer la méthode de calcul de la fonction binomial, en changeant astucieusement l’ordre des multiplications et divisions notamment

Dans le cas général, si le dépassement de capacité est un risque nuisible, on doit vérifier qu’il n’ait pas lieu avant de faire le calcul.³

(Ça passe ou ça casse)

En C, un programme qui marche n’est pas toujours un programme correct. Par exemple, le programme suivant est louche mais ne provoque pas nécessairement d’erreur ni même de fuite mémoire.

#include <stdio.h>
#include <stdlib.h>

struct Cellule {
    struct Cellule *suivant;
    int valeur;
};
typedef struct Cellule Cellule, *Liste;

Cellule *extraitTete(Liste *liste) {
    Cellule *cell = *liste;
    // Si la liste est non vide, on retire la cellule de tête
    if (*liste) *liste = (*liste)->suivant;
    return cell;
}

Cellule *insereTete(Liste liste, int valeur) {
    Cellule *tete = malloc(sizeof(Cellule));
    if (tete == NULL) return NULL;
    tete->suivant = liste;
    tete->valeur = valeur;
    return tete;
}

void afficheListe(Liste l) {
    for (Cellule *cell = l; cell != NULL; cell = cell->suivant) {
        printf("%d,", cell->valeur);
    }
    printf("\n");
}

void liberer(Liste *l) {
    while (*l) {
        free(extraitTete(l));
    }
}

int main() {
    Liste l = NULL;
    for (int i = 1; i < 9; i++) {
        l = insereTete(l, (i * 7) % 13);
    }
    afficheListe(l);

    Cellule *cell = extraitTete(&l);
    liberer(&l);

    for (int i = 1; i < 8; i++) {
        l = insereTete(l, - (i * 7) % 13);
    }
    afficheListe(cell); // Affiche les valeurs de `l` ??

    liberer(&cell);

    return 0;
}

1. Proposer une explication. Quelle erreur est la cause du problème ?

Pour établir un diagnostic on utilisera deux outils. Le premier, valgrind, n’intervient qu’une fois l’exécutable produit.

$ valgrind ./mon_programme
==4105== Memcheck, a memory error detector
==4105== Copyright (C) 2002-2024, and GNU GPL'd, by Julian Seward et al.
==4105== Using Valgrind-3.24.0 and LibVEX; rerun with -h for copyright info
==4105== Command: ./mon_programme
==4105==
4,10,3,9,2,8,1,7,
==4105== Invalid read of size 4
==4105==    at 0x10920F: afficheListe (main.c:28)
==4105==    by 0x10937F: main (main.c:52)
==4105==  Address 0x4a68228 is 8 bytes inside a block of size 16 free'd
==4105==    at 0x484575B: free (vg_replace_malloc.c:989)
==4105==    by 0x109268: liberer (main.c:35)
==4105==    by 0x109319: main (main.c:47)
==4105==  Block was alloc'd at
==4105==    at 0x4842794: malloc (vg_replace_malloc.c:446)
==4105==    by 0x1091C7: insereTete (main.c:19)
==4105==    by 0x1092E3: main (main.c:42)
...

valgrind simule une partie des opérations de la machine et intercepte les accès mémoire afin de vérifier s’ils sont corrects lors de l’exécution du programme.

Dans l’exemple précédent, valgrind détecte que le programme accède à 4 octets d’un bloc de 16 octets alloué dans insereTete mais libéré depuis dans la fonction liberer.

La seconde méthode consiste à intégrer directement à l’exécutable le code permettant ce type de diagnostic. Celui-ci peut alors être plus fin et ralentit moins l’exécution du programme que valgrind.

Pour cela, on compile le programme en ajoutant aux options l’option -fsanitize=address. Cette option active l’AddressSanitizer (ou ASan) en l’intégrant à l’exécutable. Cela a pour effet de contrôler les accès mémoire et les allocations dynamiques.

2. Compiler en intégrant cette option et exécuter le programme.

Cette fois-ci le programme plante et fournit un message verbeux indiquant le problème, la ligne de code le provoquant en ajoutant ensuite des informations relative à la zone mémoire concernée.

Le code suivant isole la partie erronée d’un code plus gros et est adapté pour l’exercice.

Ce code initialise un tableau à partir de la valeur passée en argument au programme dans la ligne de commande et indique si la valeur par défaut est utilisé ou si c’est celle de l’utilisateur qui est utilisée.

$ ./mon programme 42
Initialisation par défaut ? Non
$ ./mon programme
Initialisation par défaut ? Oui

Voici le code en question.

#include <stdio.h>
#include <stdlib.h>

#define SIZE 2

int main(int argc, char *argv[]) {
    long init = argc > 1 ? atoi(argv[1]) : 0;
    long ok = argc > 1;
    long tab[SIZE][SIZE];
    for (int m = SIZE; m >= 0; m--) {
        for (int n = SIZE; n >= 0; n--) {
            tab[m][n] = init;
        }
    }
    fprintf(stderr, "Initialisation par défaut ? ");
    if (ok)
        fprintf(stderr, "Non\n");
    else
        fprintf(stderr, "Oui\n");
    // ...
    return 0;
}

1. Tester en spécifiant la valeur 0 comme argument du programme.⁴
2. Proposer une explication.
3. Tester avec ASan.
4. L’explication donnée à la question 2 est-elle correcte ? Proposer une nouvelle explication dans le cas contraire.

#include <stdio.h>

#define SIZE 25

int main(void) {
    // Calcul des premiers nombes de fibonacci
    int n, m;
    int tab[SIZE] = {1, 1};
    for (m = 2; m <= SIZE; m++) {
        tab[m] = 0;
        for (n = m - 2; n < m; n++)
            tab[m] += tab[n];
    }
    // Puis affichage
    for (m = 0; m < SIZE; m++) {
        printf("%d ", tab[m]);
    }
    return 0;
}