Le langage C
Neuvième partie
par Guilhem de Wailly
Dans cette série d'articles, nous présentons le langage C. Il ne s'agit pas de réécrire les ouvrages de référence donnés en annexe, mais de donner, au travers du C, une méthode de programmation basée sur la notion d'interface.
Au fur et à mesure de notre progression, nous décrirons les éléments indispensables du langage et conduirons le lecteur à consulter les ouvrages de références. Le but poursuivi est clairement de parvenir à construire des programmes de manière segmentée.
Dans cet article, nous décrivons la manière avec laquelle le compilateur C transforme en langage machine les appels de fonction et le passage des arguments.
Cette étude sommaire est nécessaire pour comprendre les mécanismes mis en Å“uvre pour utiliser les pointeurs et l'allocation dynamique que nous décrirons dans le prochain article.
Dans les articles précédents, nous avons abordé la programmation d'une bibliothèque : il s'agissait de la bibliothèque de calcul sur les nombres rationnels.
Ces articles nous ont permis d'appréhender la programmation en C dans un système Linux (ou autre). L'usage du compilateur gcc, de son compilateur gdb ou du débogueur ddd ont aussi été abordés.
Le dernier article décrivait la manière de construire une bibliothèque binaire. Deux modes de liaisons des bibliothèques ont été vus, que se soit les bibliothèques statiques ou les bibliothèques dynamiques.
Il existe d'autres outils liés à la programmation en C sous Linux, mais l'essentiel a été vu.
Dans cet article, nous allons revernir sur la programmation de la bibliothèque des nombres rationnels. En effet, la méthode utilisée jusqu'à maintenant permet de programmer des objets sans utiliser l'allocation dynamique en mémoire.
L'avantage de l'allocation statique utilisée est la simplicité de programmation : les objets sont simplement déclarés et utilisés dans une fonction, sans avoir à se préoccuper de leur allocation et désallocation en mémoire.
L'inconvénient est que le nombre d'objets créés est fixe et connu au moment de la compilation. On ne peut pas de cette manière concevoir de programmes s'adaptant à leur entrée en construisant et détruisant un nombre d'objets variables.
L'autre inconvénient de la méthode utilisée jusqu'à maintenant concerne les performances : en effet, le passage de structures de données par valeur, comme nous l'avons fait jusqu'à maintenant, duplique de manière intensive les objets dans la mémoire, pénalisant sérieusement la vitesse d'exécution des programmes.
L'allocation dynamique permet de concevoir des programmes construisant des objets dont le nombre est inconnu au moment de leur compilation. De plus, les objets sont passés par références, c'est à dire en utilisant une adresse. Les adresses sont manipulées par les fameux pointeurs du langage C, qui en fait, sont assez facile à comprendre malgré leur mauvaise réputation.
Le nouvel objectif est donc d'utiliser l'allocation dynamique pour construire les objets, et le passage par référence pour gagner en performance. Nous allons nous rendre compte que l'interface définie précédemment ne va pratiquement pas changer bien que la gestion de la mémoire va être radicalement modifiée.
Dans cet article, nous allons décrire le mécanisme mis en place par la compilation du langage C pour appeler les fonctions. Nous nous intéresserons plus particulièrement au passage des arguments. Cette description est nécessaire pour appréhender la différence entre le passage par valeur et par référence, d'une part, et l'utilisation des adresses mémoire au travers des pointeurs que nous verrons ultérieurement.
Pour décrire ce mécanisme, il nous faut nous placer au niveau de la machine. Pour cela, nous utiliserons un pseudo langage machine assez réaliste.
La pile est une structure de donnée qui fonctionne comme une pile d'assiettes. Dans un ordinateur, on manipule des mots mémoire (de 32 bits sur les processeurs Intel). Les actions possibles sur une pile sont les suivantes :
Par exemple, si une pile contient initialement la valeur 123, et que l'on empile les valeurs 4 et 5, nous obtenons :
| 104 | SP> | 104 | ||||
| 103 | 103 | 5 | ||||
| SP> | 102 | 102 | 4 | |||
| 101 | 123 | 101 | 123 | |||
| SB> | 100 | SB | 100 | |||
| Avant | Après | |||||
Les valeurs numériques sont les adresses en mémoire des cellules de la pile. Les valeurs d'adresses données sont des exemples. La pile contient des mots machine, de 32 bits sur une architecture Intel.
La pile est gérée par deux registres indiquant le sommet (Stack Pointer ou SP) et la base de la pile (Stack Base ou SB). La base de la pile est généralement allouée par le système d'exploitation.
Pour les langages comme C, un autre registre est utilisé pour repérer la position des arguments de la dernière fonction appelée : on l'appelle pointeur de cadre d'activation (Stack Frame ou SF). Son utilité est son fonctionnement sont décrits plus bas.
La pile a joué un rôle très important en informatique car elle a permis de concevoir des procédures qui peuvent se rappeler de manière récursive.
Actuellement, la pile est utilisée par pratiquement toues les langages informatiques, comme le langage C. Elle est réalisée de manière matérielle par le processeur pour gagner en performance.
L'instruction d'empilement généralement appelée push place au sommet de la pile la valeur en argument et incrémente le pointeur de pile SP. L'instruction de dépilement pop décrémente de pointeur de pile en plaçant le sommet de pile dans l'accumulateur.
Ces deux opérations sont exécutées de manière très rapide par le processeur. Les systèmes d'exploitation actuels gèrent de manière dynamique la taille de la pile, en allouant ou désallouant la pile en fonction des besoins. Ce ne fut pas toujours le cas, notamment avec DOS, ou certains se rappellerons du fameux "stack overflow".
Les programmes sont toujours constitués d'une succession d'instructions dans le langage de la machine. En général, on appelle le langage de la machine langage d'assemblage ou assembleur. En réalité, l'assembleur est encore un langage lisible par les humains (human readeable) qui est traduit en binaire. Aujourd'hui, peu de personnes programment en assembleur qui est complètement dépendant de la machine. On lui préfère le langage C qui peut être vu comme un langage d'assemblage portable entre système. Notre Linux favori est presque entièrement écrit en C avec seulement quelques parties en assembleur.
Ces instructions sont placées dans la mémoire de l'ordinateur. Le compilateur C traduit dans le langage de la machine le programme en C.
A tout moment, le micro-processeur connaît la position courante dans le programme, représentée par l'adresse de la prochaine instruction machine à exécuter.
Cette adresse est contenue dans l'un des registres du processeur. Ce registre est souvent appelé pointeur programme ou PC. Lorsqu'une instruction est exécutée, la valeur contenue dans ce registre est automatiquement incrémentée pour pointer vers l'instruction machine suivante.
Le programme est exécuté en séquence en partant de la première instruction. Certaines instructions du processeur permettent de modifier directement la valeur de ce registre. Cela se traduit par une rupture de la séquence d'exécution des instructions. Par exemple, une rupture de la séquence est introduite lorsque l'on effectue un test.
L'ordre dans lequel les instructions d'un programme sont exécutées est appelé flot de contrôle du programme. On considère souvent qu'un programme est constitué d'un flot de contrôle et d'un flot de données. Certains langages sont plus axés sur les données ; ils appartiennent aux langages à flots de données ou langage dataflow, comme les langages Sisal, Lustre ou Lambda-Flow.
Le langage Basic permet de contrôler directement le flot de contrôle avec l'instruction goto et le numéro des lignes du programme. Il ne possède pas (à l'origine) la notion de procédure. Il est donc impossible d'écrire des fonctions récursives dans le Basic originel.
En C, il n'est pas possible d'accéder directement au pointeur programme. On y accède indirectement au travers des instructions modifiant le flot de contrôle, comme le if, le while, le do…while, le goto, le for ou l'appel à une fonction. Nous verrons que l'instruction goto est très utile en C pour écrire le traitement des erreurs.
La structure des programmes C est essentiellement basée sur les fonctions et sur la séquence. C'est pour cette raison qu'il appartient à la famille des langages procéduraux ou impératifs, comme Algol, Pascal, Modula.
Le passage des arguments par valeur est le mode de fonctionnement par défaut dans le langage C. Considérons le fragment de code suivant :
int f (int a, int b) {
int x = a + b;
return x / 2;
}
Cette fonction retourne un entier et attend deux entiers comme arguments. Elle déclare une variable locale x qu'elle affecte avec la somme des deux arguments et retourne cette somme ; divisée par deux.
Que se passe-t-il dans la mémoire de l'ordinateur lorsque cette fonction est appelée avec des arguments comme dans :
f (1, 2 + 3);
Tout d'abord, les arguments sont évalués du premier au dernier et le résultat de cette évaluation est empilé sur la pile matérielle de l'ordinateur. L'entête de la fonction est exécutée, puis les variables locales sont allouées et initialisées, le cas échant. Le corps de la fonction est exécuté, puis la terminaison de la fonction. La valeur de retour d'une évaluation se trouve dans un registre du processeur. L'exécution se poursuit alors à l'instruction qui suit l'appel.
Nous allons maintenant détailler chacune de ces étapes.
L'appel à la fonction pourrait être traduit dans un pseudo langage machine en :
; premier argument
MOVE 1 A ; A <- 1
PUSH A ; SB[SP++] <- A
; second argument
MOVE 2 A ; A <- 2
MOVE 3 B ; B <- 3
ADD A B ; A <- A+B
PUSH A ; SB[SP++] <-A
; appel
CALL f ; PUSH PC; PC <- f; dépilage des arguments
POP ; A <-SB[--SP]
POP ; A <- SB[--SP]
Ceci pourrait être le langage machine produit par le compilateur C correspondant à l'appel à la fonction f. On suppose ici que le résultat de l'addition est toujours retourné dans le registre A. Les POP finaux restaurent l'état de la pile ; on remarque que le code appelant est responsable de la restauration alors qu'avec le langage Pascal, c'est l'appelé qui en la charge (Ceci permet d'écrire des fonctions ayant un nombre d'arguments variables, comme la fonction standard printf).
La pile de la machine pendant l'appel à la fonction f se transforme de la manière suivante :
| 106 | 106 | |||||
| 105 | SP> | 105 | ||||
| 104 | 104 | Pc | ||||
| 103 | 103 | 5 | ||||
| SP> | 102 | 102 | 1 | |||
| 101 | 101 | |||||
| SF SB> | 100 | SF SP> | 100 | |||
| Avant | Après | |||||
On retrouve tout d'abord sur la pile 1 et 5, le résultat de l'évaluation des arguments.
La valeur Pc est placée sur la pile par l'instruction CALL. Elle est la valeur du pointeur programme au moment ou le CALL est exécuté ; elle pointe donc sur le premier POP situé après le CALL. Cette valeur sera restaurée dans le pointeur programme lors du retour de la fonction.
Le registre SF reste inchangé pour l'instant, conservant sa valeur précédente.
Maintenant, l'appel à la fonction f est effectué et nous nous retrouvons à l'entrée de la fonction, juste avant la déclaration de la variable locale x.
L'entête de chaque fonction C est automatiquement généré par le compilateur C et ne nous est pas accessible. Il place au sommet de la pile la valeur du registre SF et place dans ce registre la du sommet de pile. L'entête pourrait ressembler à :
; entête des fonctions
PUSH SF ; SB[SP++] <-SF
MOVE SP SF ; SF <- SP
Lorsque l'entête est exécuté, nous avons une structure de pile suivante :
| 106 | SF SP> | 106 | ||||
| SP> | 105 | 105 | 100 | |||
| 104 | Pc | 104 | Pc | |||
| 103 | 5 | 103 | 5 | |||
| SP> | 102 | 1 | 102 | 1 | ||
| 101 | 101 | |||||
| SF SB> | 100 | SB> | 100 | |||
| Avant | Après | |||||
La valeur 100 empilée est l'ancienne valeur du registre de cadre SF. Ce registre est ensuite positionné au sommet de la pile.
Après que l'entête de la fonction ait été exécutée, le programme alloue dans la pile l'espace nécessaire aux variables locales et il les initialise le cas échéant.
Dans l'exemple, le programme réserve dans la pile une cellule pour la variable locale x. Cette variable est initialisée avec la somme des deux arguments. Nous obtenons donc la structure de pile suivante :
| 107 | SP> | 107 | ||||
| SF SP> | 106 | SF> | 106 | 6 | ||
| 105 | 100 | 105 | 100 | |||
| 104 | Pc | 104 | Pc | |||
| 103 | 5 | 103 | 5 | |||
| 102 | 1 | 102 | 1 | |||
| 101 | 101 | |||||
| SB> | 100 | SB> | 100 | |||
| Avant | Après | |||||
La fonction exécute ensuite son corps, puis elle se termine par le code de terminaison. La valeur de retour de l'appel à la fonction est placée dans l'accumulateur, A avec notre micro-processeur.
Le code de terminaison de la fonction dépile les variables locales, puis replace dans le registre de cadre l'ancienne valeur et exécute l'instruction machine de retour des fonctions. Cette instruction suppose que la valeur du pointeur programme se situe au sommet de la pile. Ce code pourrait être :
; variable locales
POP ; A <- SB[--SP]
; restauration de SF
MOVE A SF ; SF <- A
; dépilage de SF
POP ; A <- SB[--SP]
; retour à l'appelant
RET ; POP; PC <- A
Le dépilage et la restauration de registre de cadre transforment la pile en :
| SP> | 107 | 107 | ||||
| SF> | 106 | 6 | 106 | |||
| 105 | 100 | SP> | 105 | |||
| 104 | Pc | 104 | Pc | |||
| 103 | 5 | 103 | 5 | |||
| 102 | 1 | 102 | 1 | |||
| 101 | 101 | |||||
| SB> | 100 | SF SB> | 100 | |||
| Avant | Après | |||||
Puis l'instruction RET prend la valeur en sommet de pile et la place dans le pointeur de programme. Nous nous trouvons maintenant dans le code appelant, juste avant de dépiler les arguments. Lorsque les arguments sont dépilés, la pile se trouve dans l'état initial. Le registre A contient alors la valeur de retour de l'appel à la fonction f.
La bibliothèque des nombres rationnels que nous avons décrit dans les articles précédents utilise le mécanisme décrit ici pour passer les nombres rationnels aux fonctions. Rappelons que les nombres rationnels sont dans notre exemple représentés par une structure de données.
Lorsque ici, nous avons empilé des entiers correspondants aux arguments des fonctions, le programme des nombres rationnels empile la totalité du contenu de la structure des nombres rationnels.
Ecrivons :
/* définition d'une structure de donnée */
typedef struct {
int a, b, c;
} Obj;
/* fonction recevant en argument une
* structure
*/
int g (Obj o) {
return o.a;
}
/* fonction principale qui déclare un objet
* et le passe en argument
*/
void main (void) {
Obj o = {1, 2, 3};
g (o);
}
L'appel à la fonction f empile les entiers a, b et c de la structure o sur la pile. Il s'en trouve que l'objet o de main et l'objet o de g sont égaux dans le sens ou leur contenu est identique, mais différents dans le sens où ils occupent deux espaces en mémoire différents. Si la fonction f modifie le contenu de son objet o, le o de main ne sera pas modifié.
Le code assembleur préparant l'appel à la fonction g dans main pourrait être :
; premier argument:
; A contient l'adresse de o
MOVE o A ; A <- o
; empile o.a
PUSH [A+0] ; SB[SP++] <- [A+0]
; empile o.b
PUSH [A+1] ; SB[SP++] <- [A+1]
; empile o.c
PUSH [A+2] ; SB[SP++] <- [A+2]
; appel
CALL g ; PUSH PC; PC <- g;
; dépilage des arguments
POP ; A <- SB[--SP]
POP ; A <- SB[--SP]
POP ; A <- SB[--SP]
Lorsque le CALL est exécuté, la pile contient la recopie de la structure o :
| 106 | SP> | 106 | ||||
| 105 | 105 | Pc | ||||
| 104 | 104 | 3 | ||||
| 103 | 103 | 2 | ||||
| SP> | 102 | 102 | 1 | |||
| 101 | 101 | |||||
| SF SB> | 100 | SF SB> | 100 | |||
| Avant | Après | |||||
L'entête de la fonction g reste inchangée :
; entête des fonctions
PUSH SF ; SB[SP++] <- SF
MOVE SP SF ; SF <- SP
Après son exécution, la pile reçoit la valeur du registre de cadre qui est à son tour modifié pour recevoir la valeur du sommet de pile :
| 107 | SF SP> | 107 | ||||
| SP> | 106 | 106 | 100 | |||
| 105 | Pc | 105 | Pc | |||
| 104 | 3 | 104 | 3 | |||
| 103 | 2 | 103 | 2 | |||
| 102 | 1 | 102 | 1 | |||
| 101 | 101 | |||||
| SF SB> | 100 | SB> | 100 | |||
| Avant | Après | |||||
La fonction ne déclare pas de variable locale. Elle passe donc directement de l'entête au corps :
MOVE [SF-5] A ; A <- SB[SF-5]
Le corps place dans le registre A le contenu du champ a de la structure o. La structure o étant placée sur la pile, sont contenu est lu relativement par rapport au registre de cadre SF et une constante. Se code est indépendant de l'état initial de la pile.
La fonction exécute maintenant sont code de terminaison. Comme il n'y a pas de variables locales, il se réduit à :
; restauration de SF
MOVE A SF ; SF <- A
; dépilage de SF
POP ; A <- SB[--SP]
; retour à l'appelant
RET ; POP; PC <- A
L'exécution se poursuit. Dans l'exemple, la fonction exécute sa terminaison, puis le système d'exploitation reprend la main.
Le mode de passage des arguments du langage C est appelé passage par valeur : c'est la valeur de l'argument qui est dupliquée et passée à la fonction.
Dans le cas des structures de données, ce mode de fonctionnement n'est pas du tout efficace car le programme passe son temps à dupliquer les données. De plus, les risques de saturation de la mémoire allouée à la pile sont élevés.
L'autre mode de passage des arguments est le passage par référence : dans ce cas, ce n'est pas le contenu de la donnée qui est placée sur la pile, mais son emplacement en mémoire. L'emplacement en mémoire, ou adresse, occupe seulement un mot machine, c'est à dire 32 bits sur une architecture Intel.
Le langage C ne dispose que du passage par valeur, contrairement au langage Pascal ou C++. Cependant, il connaît la notion de "référence" plus connue sous le nom d'adresse.
Dans le prochain article, nous montrerons comment utiliser le passage par référence, puis nous tenterons d'évaluer le gain en performance en programmant un test. Alors nous serons près à utiliser l'allocation dynamique.
Guilhem de Wailly (gdw at free dot fr)