TP — Séance 6 — Pointeurs de fonctions et généricité

Adresses du code, calculatrice par table de dispatch, qsort et bsearch, module générique testé

TP de la séance 6 de Programmation C avancée : adresse d’une fonction, types, tables de dispatch, rappels, qsort, conteneurs génériques.

Auteur

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

Objectif et organisation

Observer sur machine où vit le code d’une fonction, programmer une calculatrice en notation polonaise inverse par une table de dispatch, trier et chercher dans un catalogue avec qsort et bsearch, puis écrire et tester un petit module générique : échange, tri, tableau dynamique et liste. Le TP compte six étapes ; le dossier TP_S06_code_depart/ fournit les programmes, un Makefile et des tests. Chaque étape contient 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 reponses.txt, avec les sorties copiées.

Commandes

Décompresser TP_S06_code_depart.zip, se placer dans le dossier TP_S06_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 test                 # etapes 2 et 3 comparees a tests/, puis test_generique
make asan                 # versions *_asan (-fsanitize=address)
make valgrind             # test_generique sous valgrind --leak-check=full
make clean                # retirer les executables
setarch -R ./prog         # execution sans alea des adresses
nm ./prog | grep ' T '    # symboles de code, decalage dans l'executable
gdb -q ./prog             # break, run, up, print, x/8xb

Les adresses affichées diffèrent d’une machine à l’autre ; les questions portent sur les zones, les permissions, les écarts et les décalages.

Étape 1 : emplacement du code d’une fonction

etape1_adresses.c affiche, pour plusieurs fonctions et variables, leur adresse et la ligne de /proc/self/maps (la carte des zones du processus, Séance 3) qui la contient.

void zone(const char *nom, const void *p)
{
    FILE *f = fopen("/proc/self/maps", "r");
    char ligne[256];
    uintptr_t a = (uintptr_t)p;
    while (fgets(ligne, sizeof ligne, f) != NULL) {
        unsigned long debut, fin;
        char perm[5];
        if (sscanf(ligne, "%lx-%lx %4s", &debut, &fin, perm) == 3 && debut <= a && a < fin) {
            /* TODO 1 : afficher aussi le fichier projete (dernier champ de la ligne, sur la meme ligne) */
            printf("%-13s %14p  %s\n", nom, p, perm);
        }
    }
    fclose(f);
}
int main(void)
{
    int locale = 7;
    int *tas = malloc(sizeof *tas);
    int (*f)(int) = frais_envoi;
    /* conversion d'un pointeur de fonction en void * : non definie par C17, imposee par POSIX */
    zone("frais_envoi", (void *)frais_envoi);
    zone("frais_retrait", (void *)frais_retrait);
    zone("main", (void *)main);
    zone("compteur", &compteur);
    zone("tas", tas);
    zone("locale", &locale);
    zone("f (variable)", &f);
    printf("f(9000) = %d, f(800) = %d\n", f(9000), f(800));
    f = frais_retrait;
    printf("f(9000) = %d\n", f(9000));
    free(tas);
    return 0;
}

Modifier. Compléter le TODO 1 : afficher, sur la même ligne, le fichier projeté (le dernier champ de la ligne lue, obtenu par strrchr(ligne, ' ')). Compiler (make), exécuter avec setarch -R, copier la sortie.
Observer. Quelles permissions ont les zones de frais_envoi, compteur, tas et locale ? Laquelle est exécutable, lesquelles sont modifiables ?
Expliquer. Comparer les adresses des trois fonctions aux valeurs de nm ./etape1_adresses | grep ' T '. Quelle base le chargeur a-t-il ajoutée ? Relancer sans setarch : qu’est-ce qui change, qu’est-ce qui reste ?
Observer. Sous gdb : break zone, run, up, puis print f, print frais_envoi, x/8xb frais_envoi, print sizeof f, info symbol f. Interpréter chaque réponse.

Modifier. Recompiler sans PIE, puis comparer adresses et valeurs de nm :

gcc -std=c17 -Wall -Wextra -O0 -g -no-pie etape1_adresses.c -o etape1_adresses

Modifier. Ajouter, après le second appel de f, l’écriture d’un octet au début du code de frais_envoi, puis exécuter : que se passe-t-il, et pourquoi ?
```
unsigned char *code = (unsigned char *)(void *)frais_envoi;
fflush(stdout);
code[0] = 0xc3;
```

Étape 2 : calculatrice par table de dispatch

etape2_rpn.c évalue des expressions en notation polonaise inverse : les nombres s’empilent, chaque opérateur dépile deux opérandes et empile le résultat (1500 3 * 250 - vaut $1500\times3-250$). Les opérateurs sont choisis par une table de 128 pointeurs de fonctions indexée par le code ASCII du caractère. Le programme contient une erreur volontaire : aucune vérification avant l’appel.

static Operation table[128];            /* indice : code ASCII de l'operateur */
void init_table(void)
{
    table['+'] = addition;
    table['-'] = soustraction;
    /* TODO 1 : ranger produit, quotient et reste aux indices '*', '/' et '%' */
}
/* evaluer : 1 et *res si l'expression est correcte, 0 sinon */
int evaluer(const char *expr, long *res)
{
    long pile[16];
    int n = 0;
    const char *p = expr;
    while (*p != '\0') {
        if (*p == ' ') {
            p++;
            continue;
        }
        if (*p >= '0' && *p <= '9') {
            char *fin;
            if (n == 16)
                return 0;
            pile[n++] = strtol(p, &fin, 10);
            p = fin;
            continue;
        }
        unsigned char c = (unsigned char)*p++;
        /* TODO 2 : rendre 0 si l'operateur est inconnu, s'il manque un operande, ou pour une division par 0 */
        long b = pile[--n];
        long a = pile[--n];
        pile[n++] = table[c](a, b);
    }
    if (n != 1)
        return 0;
    *res = pile[0];
    return 1;
}
int main(void)
{
    const char *expr[7] = {
        "1500 3 * 250 -", "17500 4 / 3 %", "2 3 4 * +",
        "100 7 %", "5 +", "8 2 ^", "9 0 /",
    };
    init_table();
    for (int i = 0; i < 7; i++) {
        long r;
        if (evaluer(expr[i], &r))
            printf("%-16s = %ld\n", expr[i], r);
        else
            printf("%-16s : refusee\n", expr[i]);
    }
    return 0;
}

Observer. Compiler et exécuter le départ, puis la version etape2_rpn_asan (make asan). Que se passe-t-il, à quelle ligne ? Quelle valeur a table['*'], et pourquoi (classe de stockage de table, Séance 3) ?
Modifier. Compléter le TODO 1 et relancer. Quelle expression provoque maintenant l’arrêt, et pourquoi ?
Modifier. Compléter le TODO 2 : refuser un opérateur inconnu, une pile qui n’a pas deux opérandes, et une division ou un reste par 0. Vérifier avec make test que la sortie est celle de tests/attendu_etape2.txt.
Expliquer. Pourquoi c >= 128 doit-il être testé, alors que c vient d’un char ? Quel est l’intérêt d’une table de 128 cases face à un switch, et son coût en mémoire ?
Modifier. Ajouter un opérateur ^ (puissance entière, exposant positif) sans modifier evaluer. Combien de lignes du programme changent ?

Étape 3 : catalogue, `qsort` et `bsearch`

etape3_catalogue.c trie des lots d’oignons (ville, poids en kg, prix en FCFA) de trois façons : un index de pointeurs par poids, le tableau par prix, puis par ville pour une recherche par bsearch. Le comparateur de l’index contient une erreur volontaire.

typedef struct {
    char ville[12];
    int poids;                          /* kg */
    long prix;                          /* FCFA */
} Lot;
/* TODO 1 : prix croissant, puis poids decroissant */
int par_prix(const void *a, const void *b)
{
    (void)a;
    (void)b;
    return 0;
}
int par_ville(const void *a, const void *b)
{
    const Lot *x = a;
    const Lot *y = b;
    return strcmp(x->ville, y->ville);
}
/* TODO 2 : comparateur de bsearch, cle = une chaine */
int cle_ville(const void *cle, const void *e)
{
    (void)cle;
    (void)e;
    return 0;
}
/* index : tableau de Lot * (erreur volontaire dans ce comparateur) */
int index_par_poids(const void *a, const void *b)
{
    const Lot *x = a;
    const Lot *y = b;
    return (x->poids > y->poids) - (x->poids < y->poids);
}
void afficher(const Lot *l)
{
    printf("  %-10s %4d kg %6ld FCFA\n", l->ville, l->poids, l->prix);
}

Observer. Exécuter le départ : l’index est-il trié par poids ? Exécuter etape3_catalogue_asan : quel accès est signalé, dans quelle variable, à quel offset ?
Expliquer. Quel est le type d’un élément de index, et donc le vrai type des paramètres reçus par index_par_poids ? Pourquoi la lecture déborde-t-elle seulement pour certains appels ? Corriger le comparateur.
Modifier. Compléter le TODO 1 (prix croissant, puis poids décroissant) et le TODO 2 (comparateur de bsearch, la clé étant une chaîne). Vérifier avec make test.
Expliquer. Sedhiou et Tivaouane ont le même prix et le même poids : dans quel ordre sortent-ils, et cet ordre est-il garanti par la norme ?
Modifier. Appeler bsearch sur le tableau trié par prix avec cle_ville. Le résultat est-il fiable ? Pourquoi ?

Étape 4 : échange et tri génériques

Les étapes 4 à 6 complètent le module generique.c, déclaré dans generique.h, et le testent par test_generique.c : chaque test affiche ok ou ECHEC, et le programme rend le nombre d’échecs.

void echanger(void *a, void *b, size_t taille)
{
    /* TODO 4.1 : echanger les taille octets de a et de b, octet par octet */
    (void)a;
    (void)b;
    (void)taille;
}
void tri_insertion(void *base, size_t n, size_t taille, Comparateur cmp)
{
    /* TODO 4.2 : tri par insertion ; l'element i est en (char *)base + i * taille */
    (void)base;
    (void)n;
    (void)taille;
    (void)cmp;
}

Observer. make test : combien de tests échouent au départ ?
Modifier. Compléter le TODO 4.1 (echanger, octet par octet à travers deux unsigned char *) et le TODO 4.2 (tri_insertion, avec la signature de qsort). Relancer les tests de l’étape 4.
Observer. Combien d’appels au comparateur tri_insertion fait-il sur le tableau de 8 int du test ? Ajouter un compteur à un qsort sur le même tableau et comparer.
Expliquer. Pour le tableau de chaînes, pourquoi cmp_chaine convertit-il en const char *const * ? Que donnerait (Comparateur)strcmp ?
Modifier. Remplacer, dans un test, sizeof x par sizeof(float) pour l’échange de deux double. Le compilateur le signale-t-il ? Que donne le test ?

Étape 5 : le `VecteurG` et ses éléments

void vg_init(VecteurG *v, size_t taille_elem, size_t cap)
{
    v->donnees = malloc(cap * taille_elem);
    v->taille = 0;
    v->capacite = v->donnees != NULL ? cap : 0;
    v->taille_elem = taille_elem;
}
void *vg_elem(const VecteurG *v, size_t i)
{
    /* TODO 5.1 : adresse de l'element i */
    (void)v;
    (void)i;
    return NULL;
}
int vg_ajouter(VecteurG *v, const void *x)
{
    /* TODO 5.2 : si le bloc est plein, doubler la capacite (pointeur temporaire) ; copier taille_elem octets */
    (void)v;
    (void)x;
    return 0;
}
void vg_liberer(VecteurG *v, void (*lib)(void *))
{
    (void)lib;                          /* erreur volontaire : ce que possedent les elements n'est pas libere */
    free(v->donnees);
    *v = (VecteurG){NULL, 0, 0, v->taille_elem};
}

Modifier. Compléter le TODO 5.1 (vg_elem) et le TODO 5.2 (vg_ajouter, doublement par un pointeur temporaire, puis copie de taille_elem octets ; une capacité nulle passe à 1). Relancer les tests de l’étape 5.
Observer. Le test « qsort sur le bloc du vecteur » trie les éléments en place : quels arguments reçoit qsort ?
Observer. make valgrind : combien d’octets sont perdus, en combien de blocs, et où ont-ils été alloués ? Relier ce nombre aux noms des marchés.
Expliquer. vg_liberer contient une erreur volontaire : laquelle ? Que reçoit liberer_chaine, et pourquoi convertit-elle en char ** ?
Modifier. Corriger vg_liberer, puis vérifier sous valgrind que tous les blocs sont libérés.

Étape 6 : liste générique et contexte

int liste_ajouter_fin(NoeudG **pt, void *donnee)
{
    /* TODO 6.1 : avancer un pointeur de pointeur jusqu'au NULL final (Seance 5), puis y accrocher un noeud */
    (void)pt;
    (void)donnee;
    return 0;
}
void parcourir(const NoeudG *p, void (*f)(void *donnee, void *ctx), void *ctx)
{
    /* TODO 6.2 : appeler f(donnee, ctx) pour chaque noeud */
    (void)p;
    (void)f;
    (void)ctx;
}
void liste_liberer(NoeudG **pt, void (*lib)(void *))
{
    /* TODO 6.3 : liberer chaque donnee (si lib n'est pas NULL), puis chaque noeud ; *pt = NULL */
    (void)pt;
    (void)lib;
}

Modifier. Compléter les TODO 6.1 (ajout en fin par pointeur de pointeur, Séance 5), 6.2 (parcourir) et 6.3 (liste_liberer). Tous les tests doivent passer, sous valgrind et avec test_generique_asan.
Expliquer. Dans le test, compter et plus_grand reçoivent le même void *ctx : quel est son type réel dans chaque cas ? Pourquoi plus_grand reçoit-il l’adresse d’un pointeur ?
Modifier. Écrire une fonction de rappel afficher et l’appeler par parcourir(l, afficher, NULL) pour afficher les marchés.
Expliquer. Que se passerait-il si liste_liberer libérait le nœud avant sa donnée, ou si l’on passait free pour une liste dont les données sont des variables locales ?