IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Programmation avancée sous Linux


précédentsommairesuivant

11. Autres Outils de Développement

Le développement de programmes GNU/Linux rapides et fiables en C ou en C++ nécessite plus que la compréhension en surface du fonctionnement du système d'exploitation et des appels système. Dans cette annexe, nous présenterons des outils de développement permettant de détecter les erreurs à l'exécution comme l'utilisation incorrecte d'une zone mémoire allouée dynamiquement et de déterminer quelles parties du programme monopolisent le plus de temps d'exécution. L'analyse du code source d'un programme peut révéler certaines de ces informations; en utilisant ces outils d'analyse dynamique et en exécutant effectivement le programme, vous pouvez en obtenir beaucoup plus.

11-1. Analyse Statique de Programmes

Certaines erreurs de programmation peuvent être détectées en utilisant des outils d'analyse statique qui étudient le code source du programme. Si vous invoquez GCC avec l'option -Wall ou -pedantic, le compilateur affiche des avertissement sur les structures de programmation risquées ou potentiellement fausses. En éliminant de telles constructions, vous réduirez les risques de bugs et faciliterez la compilation de vos programmes sur d'autres variantes de GNU/Linux et même sur d'autres systèmes d'exploitation.

En utilisant diverses options, vous pouvez faire en sorte que GCC émette des avertissements sur un nombre impressionnant de structures de programmation douteuses. L'option -Wall active la plupart des vérifications. Par exemple, le compilateur affichera un avertissement sur un commentaire commençant au sein d'un autre commentaire, sur un type de retour incorrect pour la fonction main ou pour une fonction non void qui ne dispose pas d'instruction return. Si vous utilisez l'option -pedantic, GCC émet des avertissements pour tout ce qui ne respecte pas les normes ANSI C et ISO C++. Par exemple, l'utilisation de l'extension GNU asm provoque l'émission d'un avertissement avec cette option. Un petit nombre d'extensions GNU, comme l'utilisation des mots clés alternatifs commençant par %%__%% (deux tirets bas), ne déclencheront aucun message d'avertissement. Bien que la page info de GCC marque l'utilisation de ces options comme dépréciée, nous vous recommandons de les utiliser pour éviter la plupart des extensions GNU du langage car ces extensions ont tendance à changer au cours du temps et à interagir de façon néfaste sur l'optimisation du code.

Programme Coucou hello.c
Sélectionnez
main()
{
  printf("Coucou.\n");
}

Compilez le programme "Coucou" du Listing hello. Bien que GCC le compile sans rien dire, le code source n'obéit pas aux règles ANSI C. Si vous activez les avertissement en compilant avec les options -Wall -pedantic, GCC indique trois constructions douteuses.

 
Sélectionnez
% gcc -Wall -pedantic hello.c
hello.c:2: warning: return type defaults to "int"
hello.c: In function "main":
hello.c:3: warning: implicit declaration of function "printf"
hello.c:4: warning: control reaches end of non-void function

Ces avertissements indiquent les problèmes suivants:

  • Le type de retour de main n'est pas précisé;
  • La fonction printf est déclarée de façon implicite car <stdio.h> n'est pas inclus;
  • La fonction, implicitement déclarée comme renvoyant un int, ne renvoie en fait aucune valeur.

L'analyse du code source d'un programme ne permet pas de détecter toutes les erreurs de programmation et les lacunes. Dans la section suivante, nous présentons quatre outils aidant à à détecter les erreurs commises dans l'utilisation de mémoire allouée dynamiquement. Dans les sections suivantes, nous montrerons comment analyser le temps d'exécution d'un programme à l'aide du profiler gprof.

11-2. Détection des Erreurs d'Allocation Dynamique

Lorsque vous écrivez un programme, vous ne savez généralement pas quelle quantité de mémoire il nécessitera pour s'exécuter. Par exemple, une ligne lue à partir d'un fichier au moment de l'exécution peut avoir n'importe quelle taille. Les programmes C et C++ utilisent malloc, free et leurs variantes pour allouer dynamiquement de la mémoire pendant l'exécution du programme. Voici quelques règles sur l'utilisation de mémoire allouée dynamiquement:

  • Le nombre d'allocations (appels à malloc) doit correspondre exactement au nombre de libérations (appels à free);
  • Les lectures et écritures doivent se faire dans l'espace alloué, pas au delà;
  • La mémoire allouée ne doit pas être utilisée avant son allocation ou après sa libération.

Comme l'allocation et la libération dynamiques ont lieu durant l'exécution, les analyses statiques ne peuvent que rarement détecter les violations de ces règles. C'est pourquoi il existe des programmes de vérification mémoire qui exécutent le programme et collectent des informations pour déterminer si une telle violation a lieu. Voici un exemple de types de violations pouvant être détectés:

  • Lecture d'un emplacement mémoire avant allocation;
  • Écriture dans un emplacement mémoire avant son allocation;
  • Lecture d'une position se trouvant avant la zone allouée;
  • Écriture d'une position se trouvant avant la zone allouée;
  • Lecture d'une position se trouvant après la fin de la zone allouée;
  • Écriture d'une position se trouvant après la fin de cette zone;
  • Lecture d'un emplacement mémoire après sa libération;
  • Écriture dans un emplacement après sa libération;
  • Échec de la libération de la mémoire;
  • Double libération de mémoire;
  • Libération de mémoire non allouée.

Il est également utile d'être averti lors d'une demande d'allocation de zéro octet car il s'agit certainement d'une erreur de la part du programmeur.

Le Tableau outilsmem indique les fonctionnalités des quatre outils de diagnostic. Malheureusement, il n'existe pas d'outil diagnostiquant toutes les erreurs d'utilisation de la mémoire. De plus, aucun outil ne détecte l'écriture ou la lecture d'une zone non allouée, toutefois, une telle opération déclencherait probablement une erreur de segmentation. Ces outils ne détectent que les erreurs survenant durant l'exécution du programme. Si vous exécutez le programme avec des données qui ne nécessitent pas d'allocation mémoire, les outils ne détecteront aucun problème. Pour tester un programme de façon exhaustive, vous devez l'exécuter en utilisant différentes données d'entrée pour vous assurer que tous les chemins possible au sein de votre programme sont parcourus. De plus, vous ne pouvez utiliser qu'un seul outil à la fois, vous devez donc recommencer les mêmes tests avec plusieurs outils pour vous assurer d'avoir le plus de vérifications possibles.

Fonctionnalités de Différents Outils de Vérification Mémoire (X : prise en charge totale, O : détection occasionnelle)

Comportement erroné malloc mtrace ccmalloc Electric Fence
Lecture avant allocation        
Écriture avant allocation        
Lecture avant la zone allouée       X
Écriture avant la zone allouée O   O X
Lecture après la zone allouée       X
Écriture après la zone allouée     X X
Lecture après libération       X
Écriture après libération       X
Échec de libération   X X  
Double libération X   X  
Libération de mémoire non allouée   X X  
Allocation de taille nulle     X X

Dans les sections qui suivent, nous décrirons comment utiliser la vérification fournie par malloc et mtrace, qui sont les deux plus simples, puis nous nous intéresserons à ccmalloc et Electric Fence.

11-2-1. Programme de Test d'Allocation et de Libération Mémoire

Nous utiliserons les programme malloc-use du Listing mallocuse pour illustrer l'allocation, la libération et l'utilisation de la mémoire. Pour le lancer, passez-lui le nombre maximum de régions mémoire à allouer en premier argument. Par exemple, malloc-use 12 crée un tableau A avec 12 pointeurs de caractères qui ne pointent sur rien. Le programme accepte cinq commandes différentes:

  • Pour allouer b octets sur lesquels pointe l'entrée A[i], saisissez a i b. L'indice i peut être n'importe quel nombre non négatif inférieur à l'argument de ligne de commande;
  • Pour libérer la mémoire se situant à l'indice i, entrez d i;
  • Pour lire le p<sup>ème</sup> caractère de la mémoire allouée à l'indice i (comme avec A[i][p]), saisissez r i p. Ici, p peut avoir n'importe quelle valeur entière;
  • Pour écrire un caractère à la p<sup>ème</sup> position de la mémoire allouée à l'indice i, entrez w i p;
  • Lorsque vous avez terminé, saisissez q.

Nous présenterons le code du programme plus loin dans la Section A.2.7 et illustrerons comment l'utiliser.

11-2-2. Vérification par malloc

Les fonctions d'allocation mémoire fournies avec la bibliothèque C GNU peut détecter l'écriture en mémoire avant une zone allouée et la double libération.

La définition de la variable d'environnement MALLOC_CHECK_ à la valeur 2 provoque l'arrêt d'un programme lorsqu'une telle erreur est détectée (attention, la variable d'environnement se termine par un tiret bas). Il n'est pas nécessaire de recompiler le programme.

Voici un exemple de détection d'écriture à un emplacement mémoire juste avant le début d'une zone allouée:

 
Sélectionnez
% export MALLOC_CHECK_=2
% ./malloc-use 12
Please enter a command: a 0 10
Please enter a command: w 0 -1
Please enter a command: d 0
Aborted (core dumped)

la commande export active les vérifications de malloc. La valeur 2 provoque l'arrêt immédiat du programme lors de la détection d'une erreur.

L'utilisation de la vérification par malloc est avantageuse car elle ne nécessite aucune recompilation, mais l'étendue des vérifications est assez limitée. Fondamentalement, il s'agit de s'assurer que les structures de données utilisées pour l'allocation mémoire ne sont pas corrompues. C'est pourquoi il est possible de détecter une double libération du même emplacement mémoire. De plus, l'écriture juste avant le début d'une zone allouée peut être détectée facilement car le dispositif d'allocation mémoire stocke la taille de chaque zone allouée juste avant celle-ci. Aussi, une écriture juste avant la zone corrompt cette taille. Malheureusement, la vérification de cohérence ne peut avoir lieu que lorsque le programme appelle des routines d'allocation, pas lorsqu'il accède à la mémoire, aussi, un nombre important de lectures et d'écritures peuvent avoir lieu avant qu'une erreur ne soit détectée. Dans l'exemple précédent, l'écriture illégale n'a été détectée que lorsque la mémoire a été libérée.

11-2-3. Recherche de Fuites Mémoire avec mtrace

L'outil mtrace aide à diagnostiquer les erreurs les plus courantes lors de l'allocation dynamique de mémoire: la non concordance entre le nombre d'allocations et de libérations. L'utilisation de mtrace se fait en quatre étapes, mtrace est fourni avec la bibliothèque C GNU:

- Modifier le code source pour inclure <mcheck.h> et invoquer mtrace() dès le début du programme, au début de main. L'appel à mtrace active la surveillance des allocations et libérations mémoire;

- Indiquer le nom d'un fichier pour stocker les informations sur les allocations et libérations mémoire: % export MALLOC_TRACE=memory.log

- Exécuter le programme. Toutes les allocations et libérations sont stockées dans le fichier journal.

- Utiliser la commande mtrace pour analyser les allocations et libérations mémoire pour s'assurer que leur nombre concorde. % mtrace mon_programme $MALLOC_TRACE

Les messages émis par mtrace sont relativement simples à comprendre. Par exemple, avec notre exécution de malloc-use, ils seraient de ce type:

 
Sélectionnez
- 0000000000 Free 3 was never alloc'd malloc-use.c:39
Memory not freed:
-----------------
   Address     Size     Caller
0x08049d48      0xc  at malloc-use.c:30

Ces messages indiquent une libération de mémoire qui n'a jamais été allouée à la ligne 39 de malloc-use.c et une zone de mémoire allouée à la ligne 30 non libérée.

mtrace détecte les erreurs grace à l'analyse du fichier spécifié par la variable d'environnement MALLOC_TRACE, celui-ci contient la liste de toutes les allocations et libérations mémoire du programme. L'exécutable doit se terminer normalement pour que les données soient écrites. La commande mtrace analyse le fichier et dresse la liste des allocations et libérations qui n'ont pas de réciproque.

11-2-4. Utiliser ccmalloc

La bibliothèque ccmalloc détecte les erreurs mémoire en remplaçant les appels à malloc et free avec des instructions traçant leur utilisation. Si le programme se termine correctement, elle crée un rapport concernant les fuites mémoire et d'autres erreurs. La bibliothèque ccmalloc a été écrite par Armin Bierce.

Vous devrez probablement télécharger et installer la bibliothèque ccmalloc vous-même. Elle est disponible sur http://www.inf.ethz.ch/personal/biere/projects/ccmalloc/, décompressez les sources et lancez configure. Exécutez make et make install, copiez le fichier ccmalloc.cfg dans le répertoire d'où vous lancerez le programme que vous voulez contrôler et renommez la copie en .ccmalloc. Vous êtes maintenant prêt à utiliser ccmalloc.

Les fichiers objets du programme doivent être liés avec la bibliothèque ccmalloc et la bibliothèque de liaison dynamique. Ajoutez -lccmalloc et -ldl à votre commande d'édition de liens, par exemple:

 
Sélectionnez
% gcc -g -Wall -pedantic malloc-use.o -o ccmalloc-use -lccmalloc -ldl

Lancez votre programme pour créer un rapport. Par exemple, l'exécution de notre programme malloc-use de façon à ce qu'il ne libère pas une zone mémoire produit le rapport suivant:

 
Sélectionnez
% ./ccmalloc-use 12
file-name=a.out does not contain valid symbols
trying to find executable in current directory ...
using symbols from "ccmalloc-use"
(to speed up this search specify "file ccmalloc-use"
 in the startup file ".ccmalloc")
Please enter a command: a 0 12
Please enter a command: q.
---------------.
|ccmalloc report|
========================================================
| total # of|   allocated | deallocated |      garbage |
+-----------+-------------+-------------+--------------+
|     bytes |          60 |          48 |           12 |
+-----------+-------------+-------------+--------------+
|allocations|            2|            1|             1|
+------------------------------------------------------+
| number of checks: 1                                  |
| number of counts: 3                                  |
| retrieving function names for addresses ... done.    |
| reading file info from gdb ... done.                 |
| sorting by number of not reclaimed bytes ... done.   |
| number of call chains: 1                             |
| number of ignored call chains: 0                     |
| number of reported call chains: 1                    |
| number of internal call chains: 1                    |
| number of library call chains: 0                     |
========================================================
|
*100.0% = 12 Bytes of garbage allocated in 1 allocation
|       |
|       |        0x400389cb in <???>
|       |
|       |        0x08049198 in <main>
|       |                   at malloc-use.c:89
|       |
|       |        0x08048fdc in <allocate>
|       |                   at malloc-use.c:30
|       |
|       +-----> 0x08049647 in <malloc>
|                           at src/wrapper.c:284
|
+------------------------------------------------------

Les dernières lignes donnent la liste des appels de fonctions qui ont alloué de la mémoire sans la libérer.

Pour utiliser ccmalloc afin de diagnostiquer des écriture avant le début ou après la fin d'une zone mémoire allouée, vous devrez modifier le fichier .ccmalloc dans le répertoire du programme. Ce fichier est lu au démarrage du programme.

11-2-5. Electric Fence

Écrit par Bruce Perens, Electric Fence stoppe l'exécution du programme à la ligne exacte de la lecture ou de l'écriture en dehors d'une zone allouée. Il s'agit du seul outil qui détecte les lectures illégales. Il est inclus dans la plupart des distributions GNU/Linux, le code source est tout de même disponible sur http://www.perens.com/FreeSoftware/.

Comme pour ccmalloc, les fichiers objets de votre programme doivent être liés à la bibliothèque Electric Fence en ajoutant -lefence à la commande d'édition de liens, par exemple:

 
Sélectionnez

Electric Fence vérifie la validité des utilisations de la mémoire au cours de l'exécution du programme. Une mauvaise utilisation provoque une erreur de segmentation:

 
Sélectionnez
% ./emalloc-use 12
  Electric Fence 2.0.5 Copyright (C) 1987-1998 Bruce Perens.
Please enter a command: a 0 12
Please enter a command: r 0 12
Segmentation fault

En utilisant un débogueur, vous pouvez déterminer l'emplacement de l'action illégale.

Par défaut, Electric Fence ne diagnostique que les accès à des emplacements situés après la zone allouée. Pour activer la détection des accès à des emplacements situés avant la zone allouée à la place des accès à des zones situées après, utilisez cette commande:

 
Sélectionnez
% export EF_PROTECT_BELOW=1

Pour détecter les accès à des emplacements mémoire libérés, positionnez EF_PROTECT_FREE à 1. Des fonctionnalités supplémentaires sont décrites dans la page de manuel de libefence.

Electric Fence peut diagnostiquer des accès illégaux en mobilisant au moins deux pages mémoire pour toute allocation. Il place la zone allouée à la fin de la première page, ainsi, tout accès après la fin de la zone allouée provoque une erreur de segmentation. Si vous positionnez EF_PROTECT_BELOW à 1, il place la zone allouée au début de la seconde page. Comme chaque appel à malloc utilise deux pages mémoire, Electric Fence peut consommer une quantité importante de mémoire. N'utilisez cette bibliothèque qu'à des fins de débogage.

11-2-6. Choisir Parmi les Différents Outils de Débogage Mémoire

Nous avons présenté quatre outils distincts, incompatibles destinés à diagnostiquer de mauvaises utilisations de mémoire allouée dynamiquement. Alors comment un programmeur GNU/Linux peut-il s'assurer que la mémoire est utilisée correctement? Aucun outil ne garantit la détection de toutes les erreurs, mais l'utilisation de n'importe lequel d'entre eux augmente la probabilité d'en découvrir. Pour faciliter la détection d'erreurs concernant la mémoire allouée dynamiquement, développez et testez le code l'utilisant séparément du reste. Cela réduit le volume de code à analyser lors de la recherche de telles erreurs. Si vous écrivez vos programmes en C++, dédiez une classe à la gestion de la mémoire dynamique. Si vous programmez en C, minimisez le nombre de fonctions utilisant l'allocation et la libération. Lors des tests de ce code, assurez-vous qu'un seul outil s'exécute à la fois car ils sont incompatibles. Lorsque vous testez le programme, assurez-vous de varier la façon dont vous l'utilisez afin de tester toutes les portions de code.

Lequel de ces outils devriez-vous utiliser? Comme l'absence d'équilibre entre les allocations et les libérations est l'erreur la plus courante en matière de gestion dynamique de la mémoire, utilisez mtrace au début du processus de développement. Ce programme est disponible pour tous les système GNU/Linux et a été éprouvé. Après vous être assuré que les nombres d'allocations et de libérations sont identiques, utilisez Electric Fence pour détecter les accès mémoire invalides. Vous éliminerez ainsi presque toutes les erreurs mémoire. Lorsque vous utilisez Electric Fence, vous devez être attentif à ne pas effectuer trop d'allocations et de libérations car chaque allocation nécessite au moins deux pages mémoire. L'utilisation de ces deux outils vous permettra de détecter la plupart des erreurs.

11-2-7. Code Source du Programme d'Allocation Dynamique de Mémoire

Le Listing mallocuse présente le code source d'un programme illustrant l'allocation dynamique, la libération et l'utilisation de mémoire. Consultez la Section progtestalloc, Section progtestalloc, pour une description de son utilisation.

Dynamic Memory Allocation Checking Example malloc-use.c
Sélectionnez
/* Utilisation des fonctions C d'allocation mémoire.  */
/* Invoquez le programme en utilisant un argument précisant la taille du tableau.
   Ce tableau est composé de pointeurs sur des tableaux pouvant
   être alloués par la suite.
   Le programme accepte les commandes suivantes :
   o allouer de la mémoire :   a <indice> <taille>
   o libérer de la mémoire : d <indice>
   o lire un emplacement mémoire :  r <indice> <position-dans-la-mémoire-allouée>
   o écrire à un emplacement :   w <indice> <position-dans-la-mémoire-allouée>
   o quitter :              q
   L'utilisateur a la responsabilité de respecter les règles de l'allocation
   dynamique de la mémoire (ou non). */
#ifdef MTRACE
#include <mcheck.h>
#endif /* MTRACE */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
/* Alloue de la mémoire pour la taille spécifiée, renvoie une
   valeur différentes de zéro en cas de succès. */
void allocate (char** array, size_t size)
{
  *array = malloc (size);
}
/* Libère la mémoire.  */
void deallocate (char** array)
{
  free ((void*) *array);
}
/* Lit un emplacement mémoire.  */
void read_from_memory (char* array, int position)
{
  char character = array[position];
}
/* Écrit à un emplacement mémoire.  */
void write_to_memory (char* array, int position)
{
  array[position] = 'a';
}
int main (int argc, char* argv[])
{
  char** array;
  unsigned array_size;
  char command[32];
  unsigned array_index;
  char command_letter;
  int size_or_position;
  int error = 0;
#ifdef MTRACE
  mtrace ();
#endif /* MTRACE */
  if (argc != 2) {
    fprintf (stderr, "%s: taille-du-tableau\n", argv[0]);
    return 1;
  }
  array_size = strtoul (argv[1], 0, 0);
  array = (char **) calloc (array_size, sizeof (char *));
  assert (array != 0);
  /* Effectue ce que l'utilisateur demande. */
  while (!error) {
    printf ("Entrez une commande : ");
    command_letter = getchar ();
    assert (command_letter != EOF);
    switch (command_letter) {
    case 'a':
      fgets (command, sizeof (command), stdin);
      if (sscanf (command, "%u %i", &amp;array_index, &amp;size_or_position) == 2
          &amp;&amp; array_index < array_size)
        allocate (&amp;(array[array_index]), size_or_position);
      else
        error = 1;
      break;
    case 'd':
      fgets (command, sizeof (command), stdin);
      if (sscanf (command, "%u", &amp;array_index) == 1
           &amp;&amp; array_index < array_size)
        deallocate (&amp;(array[array_index]));
      else
        error = 1;
      break;
    case 'r':
      fgets (command, sizeof (command), stdin);
      if (sscanf (command, "%u %i", &amp;array_index, &amp;size_or_position) == 2
           &amp;&amp; array_index < array_size)
        read_from_memory (array[array_index], size_or_position);
      else
        error = 1;
      break;
    case 'w':
      fgets (command, sizeof (command), stdin);
      if (sscanf (command, "%u %i", &amp;array_index, &amp;size_or_position) == 2
           &amp;&amp; array_index < array_size)
        write_to_memory (array[array_index], size_or_position);
      else
        error = 1;
      break;
    case 'q':
      free ((void *) array);
      return 0;
    default:
      error = 1;
    }
  }
  free ((void *) array);
  return 1;
}

11-3. Profilage

Maintenant que votre programme est correct (espérons-le), nous allons voir comment améliorer ses performances. Avec l'aide du profileur gprof, vous pouvez déterminer les fonctions qui monopolisent le plus de temps d'exécution. Cela peut vous aider à déterminer les portions du programme à optimiser ou à réécrire pour qu'elles s'exécutent plus rapidement. Cela peut également vous aider à trouver des erreurs. Par exemple, vous pourriez détecter qu'une fonction est appelée beaucoup plus souvent que vous ne le supposiez.

Dans cette sections, nous décrirons comment utiliser gprof. La réécriture de code pour accélerer son exécution nécessite de la créativité et un certain soin dans le choix des algorithmes.

L'obtention d'informations de profilage demande de suivre trois étapes:

- Compiler et lier votre programme de façon à activer le profilage;

- Exécuter votre programme de façon à générer les données de profilage;

- Utiliser gprof pour analyser et afficher les données de profilage.

Avant d'illustrer ces différentes étapes, nous allons présenter une programme suffisamment important pour qu'il soit possible de le profiler.

11-3-1. Une Calculatrice Simplifiée

Pour illustrer le profilage, nous allons utiliser un programme faisant office de calculatrice. Pour nous assurer que son exécution prend suffisamment de temps, nous utiliserons des nombres monadiques pour les calculs, chose que nous ne ferions jamais dans un programme réel. Le code de ce programme est présenté à la fin de ce chapitre.

Un nombre monadique (ou unaire) est représenté par autant de symboles que la valeur qu'il représente. Par exemple, le nombre 1 est représenté par "x", 2 par "xx" et 3 par "xxx". Au lieu d'utiliser des x, notre programme représentera un nombre positif en utilisant une liste chaînée constituée d'autant d'éléments que la valeur du nombre. Le fichier number.c contient les fonctions pour créer le nombre 0, ajouter 1 à un chiffre, soustraire 1 d'un nombre et ajouter, soustraire et multiplier des nombres. Une autre fonction convertit une chaine représentant une nombre décimal positif en un nombre unaire et enfin, une dernière fonction permet de passer d'un nombre unaire à un int. L'addition est implantée en effectuant des additions successives du nombre un tandis que la soustraction utilise des soustractions répétitives du nombre 1. La multiplication utilise une répétition d'addtions. Les prédicats even et odd renvoient le nombre unaire 1 si et seulement si leur opérande est paire ou impaire (respectivement); sinon, ils renvoient le nombre unaire représentant 0. Ces deux prédicats s'appellent l'un l'autre, par exemple, un nombre est pair s'il vaut zéro ou si ce nombre moins un est impair.

La calculatrice accepte des expression postfixées(Dans la notation postfixée, un opérateur binaire est placé après ses opérandes plutôt qu'entre elles. Ainsi, pour multiplier 6 par 8, vous utiliseriez 6 8 x. Pour multiplier 6 et 8 puis ajouter 5 au résultat, vous utiliseriez 6 8 x 5 +.) sur une ligne et affiche la valeur de chaque expression -- par exemple:

 
Sélectionnez
% ./calculator
Veuillez saisir une expression postfixée :
2 3 +
5
Veuillez saisir une expression postfixée :
2 3 + 4 -
1

La calculatrice, définie dans calculator.c, lit chaque expression et stocke les valeurs intermédiaires sur une pile de nombres unaires, définie dans stack.c. La pile stocke ses nombres unaires dans une liste chaînée.

11-3-2. Collecter des Informations de Profilage

La première étape dans le profilage d'un programme est de marquer son exécutable de façon à ce qu'il collecte des informations de profilage. Pour cela, utilisez l'option de compilation -pg lors de la compilation et de l'édition de liens. Par exemple:

 
Sélectionnez
% gcc -pg -c -o calculator.o calculator.c
% gcc -pg -c -o stack.o stack.c
% gcc -pg -c -o number.o number.c
% gcc -pg calculator.o stack.o number.o -o calculator

Cette séquence de commandes active la collecte d'informations sur les appels de fonction et l'horodatage. Pour collecter des informations d'utilisation ligne par ligne, utilisez l'option de débogage -g. Pour compter le nombre d'exécutions de blocs de base, comme le nombre d'itérations des boubles do, utilisez -a.

La seconde étape est l'exécution du programme. Pendant son exécution, les données sont collectées dans un fichier nommé gmon.out, uniquement pour les portions de code qui ont été traversées. Vous devez varier les entrées du programme ou les commandes pour exécuter les sections du code que vous souhaitez profiler. Le programme doit se terminer normalement pour que le fichier de données de profilage soient écrites correctement.

11-3-3. Affichage des Données de Profilage

À partir du nom d'un exécutable, gprof analyse le fichier gmon.out pour afficher des informations sur le temps passé dans chaque fonction. Par exemple, examinons les données de profilage "brutes" pour le calcul de 1787 x 13 - 1918 en utilisant notre programme, elles sont fournies par la commande grpof ./calculator:

 
Sélectionnez
Flat profile:
Each sample counts as 0.01 seconds.
  %   cumulative   self             self    total
 time   seconds   seconds    calls ms/call ms/call name
 26.07      1.76     1.76 20795463    0.00    0.00 decrement_number
 24.44      3.41     1.65     1787    0.92    1.72 add
 19.85      4.75     1.34 62413059    0.00    0.00 zerop
 15.11      5.77     1.02     1792    0.57    2.05 destroy_number
 14.37      6.74     0.97 20795463    0.00    0.00 add_one
  0.15      6.75     0.01     1788    0.01    0.01 copy_number
  0.00      6.75     0.00     1792    0.00    0.00 make_zero
  0.00      6.75     0.00       11    0.00    0.00 empty_stack

Le parcours de la fonction decrement_number et des sous fonctions qu'elle appelle occupe 26,07% du temps d'exécution total du programme. Elle a été appelé 20795463 fois. Chaque exécution a nécessité 0,0 seconde -- autrement dit, un temps trop faible pour être mesuré. La fonction add a été invoquée 1787 fois, certainement pour calculer le produit. Chaque appel a demandé 0.92 secondes. La fonction copy_number a été invoquée 1788 fois, tandis que son exécution n'a nécessité que 0,15% du temps total d'exécution. Parfois, les fonctions mcount et profil utilisées pour le profilage apparaissent dans les données.

En plus des données brutes de profilage, qui indique le temps passé dans chacune des fonctions, gprof produit des graphes d'appel indiquant le temps passé dans chaque fonction et les fonctions qu'elle appelle dans le cadre d'une chaîne d'appels de fonctions:

 
Sélectionnez
index % time    self  children    called     name
                                                 <spontaneous>
[1]    100.0    0.00    6.75                 main [1]
                0.00    6.75       2/2           apply_binary_function [2]
                0.00    0.00       1/1792        destroy_number [4]
                0.00    0.00       1/1           number_to_unsigned_int [10]
                0.00    0.00       3/3           string_to_number [12]
                0.00    0.00       3/5           push_stack [16]
                0.00    0.00       1/1           create_stack [18]
                0.00    0.00       1/11          empty_stack [14]
                0.00    0.00       1/5           pop_stack [15]
                0.00    0.00       1/1           clear_stack [17]
-----------------------------------------------
                0.00    6.75       2/2           main [1]
[2]    100.0    0.00    6.75       2         apply_binary_function [2]
                0.00    6.74       1/1           product [3]
                0.00    0.01       4/1792        destroy_number [4]
                0.00    0.00       1/1           subtract [11]
                0.00    0.00       4/11          empty_stack [14]
                0.00    0.00       4/5           pop_stack [15]
                0.00    0.00       2/5           push_stack [16]
-----------------------------------------------
                0.00    6.74       1/1           apply_binary_function [2]
[3]     99.8    0.00    6.74       1         product [3]
                1.02    2.65    1787/1792        destroy_number [4]
                1.65    1.43    1787/1787        add [5]
                0.00    0.00    1788/62413059     zerop [7]
                0.00    0.00       1/1792        make_zero [13]

Le premier cadre indique que l'exécution de main a nécessité 100% des 6,75 secondes qu'a duré l'exécution du programme. Elle a appelé apply_binary_function deux fois, celle-ci ayant été appelé deux fois pendant toute la durée d'exécution du programme. L'appelant de main était <spontaneous>, ce qui signifie que le profileur n'a pas été capable de le déterminer. Le premier cadre montre également que string_to_number a appelé push_stack trois fois sur les cinq fois où celle-ci a été appelée. Le troisième cadre montre que l'exécution de product et des fonctions qu'il appelle a nécessité 99,8% du temps d'exécution total. Elle a été invoquée une seule fois depuis apply_binary_function.

Le graphe d'appel indique le temps total d'exécution d'une fonction et de ses fils. Si le graphe d'appel est un arbre, ce temps est simple à calculer, mais les fonction récursives doivent être traitées d'une manière spéciale. Par exemple, la fonction even appelle odd qui appelle even à son tour. Chaque cycle d'appel de ce genre bénéficie de son propre horodatage et est affiché individuellement dans le graphe d'appel. Considérons ces données venant du profilage de la séquence visant à déterminer si 1787 x 13 x 3 est pair:

 
Sélectionnez
-----------------------------------------------
                0.00    0.02       1/1           main [1]
[9]      0.1    0.00    0.02       1         apply_unary_function [9]
                0.01    0.00       1/1           even <cycle 1> [13]
                0.00    0.00       1/1806        destroy_number [5]
                0.00    0.00       1/13          empty_stack [17]
                0.00    0.00       1/6           pop_stack [18]
                0.00    0.00       1/6           push_stack [19]
-----------------------------------------------
[10]     0.1    0.01    0.00       1+69693   <cycle 1 as a whole> [10]
                0.00    0.00   34847             even <cycle 1> [13]
-----------------------------------------------
                               34847             even <cycle 1> [13]
[11]     0.1    0.01    0.00   34847         odd <cycle 1> [11]
                0.00    0.00   34847/186997954     zerop [7]
                0.00    0.00       1/1806        make_zero [16]
                               34846             even <cycle 1> [13]

La valeur 1+69693 dans le cadre [10] indique que le cycle 1 a été appelé une fois, tandis qu'au sein de ce cycle il y a eu 69693 appels de fonction. Le cycle a appelé la fonction even. L'entrée suivante montre que la fonction odd a été appelée 34847 par even.

Dans cette section, nous avons brièvement présenté une partie des fonctionalités de gprof. Les pages info donnent des informations sur d'autres fonctionalités utiles:

  • L'option -s affiche la somme des résultats pour plusieurs exécutions consécutives;
  • L'option -c permet d'identifier les fils qui auraient pu être appelés mais ne l'ont pas été;
  • L'option -l pour afficher des informations de profilage ligne par ligne.
  • L'option -A pour afficher le code source annoté avec les pourcentages de temps d'exécution.

Les pages info donnent également plus d'informations sur la façon d'interpréter les résultats de l'analyse.

11-3-4. Comment gprof Collecte les Données

Lors du profilage d'un exécutable, à chaque fois qu'une fonction est appelée, le compteur qui y est associé est incrémenté. De plus, gprof interrompt régulièrement l'exécution pour déterminer la fonction en cours. Ces exemples montrent comment le temps d'exécution est déterminé. Comme les interruptions d'horloge de Linux surviennent toutes les 0,01 secondes, l'arrêt de l'exécution ne peut avoir lieu qu'au maximum toutes les 0,01 secondes. Ainsi, le profilage de programmes s'exécutant très rapidement ou appelant peu souvent des fonctions qui s'exécutent rapidement pourrait être imprécis. Pour éviter cela, exécutez le programme plus longtemps ou additionnez les données de profilage de plusieurs exécutions. Reportez-vous à la documentation concernant l'option -s dans les pages info de groff pour plus d'informations.

11-3-5. Code Source de la Calculatrice

Le Listing calculator présente un programme qui calcule la valeur d'expressions postfixées.

Programme Principal de la calculatrice calculator.c
Sélectionnez
/* Effectue des calculs en utilisant des nombres unaires.  */
/* Saisissez des expressions utilisant la notation postfixée sur une ligne,
   par exemple : 602 7 5 - 3 * +
   Les nombres positifs sont saisis en utilisant une notation décimal. Les
   opérateurs "+", "-" et "*" sont acceptés. Les opérateurs unaires
   "even" et "odd" renvoient le nombre 1 si leur opérande est pair ou impair,
   respectivement. Les différents éléments doivent être séparés par des espaces.
   Les nombres négatifs ne sont pas pris en charge. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "definitions.h"
/* Applique la fonction binaire demandée aux opérandes obtenues depuis la pile
   et place le résultat sur la pile. Renvoie une valeur différente de zéro si
   tout se passe bien. */
int apply_binary_function (number (*function) (number, number),
                           Stack* stack)
{
  number operand1, operand2;
  if (empty_stack (*stack))
    return 0;
  operand2 = pop_stack (stack);
  if (empty_stack (*stack))
    return 0;
  operand1 = pop_stack (stack);
  push_stack (stack, (*function) (operand1, operand2));
  destroy_number (operand1);
  destroy_number (operand2);
  return 1;
}
/* Applique la fonction unaire demandée aux opérandes obtenues depuis la pile
   et place le résultat sur la pile. Renvoie une valeur différente de zéro si
   tout se passe bien. */
int apply_unary_function (number (*function) (number),
                          Stack* stack)
{
  number operand;
  if (empty_stack (*stack))
    return 0;
  operand = pop_stack (stack);
  push_stack (stack, (*function) (operand));
  destroy_number (operand);
  return 1;
}
int main ()
{
  char command_line[1000];
  char* command_to_parse;
  char* token;
  Stack number_stack = create_stack ();
  while (1) {
    printf ("Veuillez saisir une opération postfixée :\n");
    command_to_parse = fgets (command_line, sizeof (command_line), stdin);
    if (command_to_parse == NULL)
      return 0;
    token = strtok (command_to_parse, " \t\n");
    command_to_parse = 0;
    while (token != 0) {
      if (isdigit (token[0]))
        push_stack (&amp;number_stack, string_to_number (token));
      else if (((strcmp (token, "+") == 0) &amp;&amp;
                !apply_binary_function (&amp;add, &amp;number_stack)) ||
               ((strcmp (token, "-") == 0) &amp;&amp;
                !apply_binary_function (&amp;subtract, &amp;number_stack)) ||
               ((strcmp (token, "*") == 0) &amp;&amp;
                !apply_binary_function (&amp;product, &amp;number_stack)) ||
               ((strcmp (token, "even") == 0) &amp;&amp;
                !apply_unary_function (&amp;even, &amp;number_stack)) ||
               ((strcmp (token, "odd") == 0) &amp;&amp;
                !apply_unary_function (&amp;odd, &amp;number_stack)))
        return 1;
      token = strtok (command_to_parse, " \t\n");
    }
    if (empty_stack (number_stack))
      return 1;
    else {
      number answer = pop_stack (&amp;number_stack);
      printf ("%u\n", number_to_unsigned_int (answer));
      destroy_number (answer);
      clear_stack (&amp;number_stack);
    }
  }
  return 0;
}

Les fonctions du Listing number implante les nombres unaires en utilisant des listes chaînées vides.

Implantation d'un Nombre Unaire number.c
Sélectionnez
/* Opérations sur les nombres unaires.  */
#include <assert.h>
#include <stdlib.h>
#include <limits.h>
#include "definitions.h"
/* Crée un nombre représentant zéro.  */
number make_zero ()
{
  return 0;
}
/* Renvoie une valeur différente de zéro si le nombre représente un zéro.  */
int zerop (number n)
{
  return n == 0;
}
/* Soustrait 1 à un nombre positif.  */
number decrement_number (number n)
{
  number answer;
  assert (!zerop (n));
  answer = n->one_less_;
  free (n);
  return answer;
}
/* Ajoute 1 à un nombre.  */
number add_one (number n)
{
  number answer = malloc (sizeof (struct LinkedListNumber));
  answer->one_less_ = n;
  return answer;
}
/* Détruit un nombre.  */
void destroy_number (number n)
{
  while (!zerop (n))
    n = decrement_number (n);
}
/* Copie un nombre. Cette fonction n'est nécessaire qu'à
   cause de l'allocation mémoire. */
number copy_number (number n)
{
  number answer = make_zero ();
  while (!zerop (n)) {
    answer = add_one (answer);
    n = n->one_less_;
  }
  return answer;
}
/* Additionne deux nombres.  */
number add (number n1, number n2)
{
  number answer = copy_number (n2);
  number addend = n1;
  while (!zerop (addend)) {
    answer = add_one (answer);
    addend = addend->one_less_;
  }
  return answer;
}
/* Soustrait un nombre d'un autre.  */
number subtract (number n1, number n2)
{
  number answer = copy_number (n1);
  number subtrahend = n2;
  while (!zerop (subtrahend)) {
    assert (!zerop (answer));
    answer = decrement_number (answer);
    subtrahend = subtrahend->one_less_;
  }
  return answer;
}
/* Renvoie le produit de deux nombres.  */
number product (number n1, number n2)
{
  number answer = make_zero ();
  number multiplicand = n1;
  while (!zerop (multiplicand)) {
    number answer2 = add (answer, n2);
    destroy_number (answer);
    answer = answer2;
    multiplicand = multiplicand->one_less_;
  }
  return answer;
}
/* Renvoie une valeur différente de zéro si un nombre est
   pair.  */
number even (number n)
{
  if (zerop (n))
    return add_one (make_zero ());
  else
    return odd (n->one_less_);
}
/* Renvoie une valeur différente de zéro si un nombre est
   impair.  */
number odd (number n)
{
  if (zerop (n))
    return make_zero ();
  else
    return even (n->one_less_);
}
/* Convertit une chaîne représentant un entier décimal en un "number". */
number string_to_number (char * char_number)
{
  number answer = make_zero ();
  int num = strtoul (char_number, (char **) 0, 0);
  while (num != 0) {
    answer = add_one (answer);
    --num;
  }
  return answer;
}
/* Convertit un "number" en "unsigned int".  */
unsigned number_to_unsigned_int (number n)
{
  unsigned answer = 0;
  while (!zerop (n)) {
    n = n->one_less_;
    ++answer;
  }
  return answer;
}

La fonction du Listing stack implante une pile de nombre unaires en utilisant une liste chaînée.

Pile de Nombres Unaires stack.c
Sélectionnez
/* Implante une pile de "number"s.  */
#include <assert.h>
#include <stdlib.h>
#include "definitions.h"
/* Crée une pile vide.  */
Stack create_stack ()
{
  return 0;
}
/* Renvoie une valeur différente de zéro si la pile est vide.  */
int empty_stack (Stack stack)
{
  return stack == 0;
}
/* Supprime le number situé au sommet d'une pile non vide.
   Échoue si la pile est vide. */
number pop_stack (Stack* stack)
{
  number answer;
  Stack rest_of_stack;
  assert (!empty_stack (*stack));
  answer = (*stack)->element_;
  rest_of_stack = (*stack)->next_;
  free (*stack);
  *stack = rest_of_stack;
  return answer;
}
/* Ajoute un number au début de la pile.  */
void push_stack (Stack* stack, number n)
{
  Stack new_stack = malloc (sizeof (struct StackElement));
  new_stack->element_ = n;
  new_stack->next_ = *stack;
  *stack = new_stack;
}
/* Supprime tous les éléments de la pile.  */
void clear_stack (Stack* stack)
{
  while (!empty_stack (*stack)) {
    number top = pop_stack (stack);
    destroy_number (top);
  }
}

Le Listing definitions contient les déclaration de la pile et des nombres.

Fichier d'En-Tête pour number.c et stack.c definitions.h
Sélectionnez
#ifndef DEFINITIONS_H
#define DEFINITIONS_H 1
/* Implante un number en utilisant une liste chaînée.  */
struct LinkedListNumber
{
   struct LinkedListNumber*
                 one_less_;
};
typedef struct LinkedListNumber* number;
/* Implante une pile de numbers sous forme de liste chaînée. Utilise 0 pour
   représenter une pile vide. */
struct StackElement
{
   number        element_;
   struct        StackElement* next_;
};
typedef struct StackElement* Stack;
/* Opérations sur les piles de numbers. */
Stack create_stack ();
int empty_stack (Stack stack);
number pop_stack (Stack* stack);
void push_stack (Stack* stack, number n);
void clear_stack (Stack* stack);
/* Operations sur les numbers. */
number make_zero ();
void destroy_number (number n);
number add (number n1, number n2);
number subtract (number n1, number n2);
number product (number n1, number n2);
number even (number n);
number odd (number n);
number string_to_number (char* char_number);
unsigned number_to_unsigned_int (number n);
#endif /* DEFINITIONS_H */

précédentsommairesuivant

Copyright © 2007 Mark Mitchell, Jeffrey Oldham et Alex Samuel. Ce document ne peut être distribué que dans le respect des termes et conditions définies par l?Open Poublication License, v1.0 ou ultérieure (la dernière version est disponible sur http://www.opencontent.org/openpub/).