2.10. Édition de liens de 5 modules

On dispose de 5 modules compilés, mémorisés dans les fichiers cmpdisk.o, cmpfile.o, disk_io.o, lsbrk.o, printstr.o. Ces 5 modules constituent la base d'un programme, qui nécessite en plus des modules de bibliothèque.

On dispose d'un premier outil, appelé listliens, qui imprime les liens des modules, en indiquant leur type ainsi que éventuellement leur valeur. Le résultat de l'application de cet outil sur les 5 modules est donné en table 1, où las signifie lien à satisfaire et lu lien utilisable.

On dispose également d'un second outil, appelé taille, qui donne la taille d'un module objet, c'est-à-dire le nombre d'emplacements occupés par ce module. Le résultat de l'application de cet outil sur les 5 modules est donné en table 2.

On se propose de faire l'édition des liens des 5 modules dans l'ordre suivant :

cmpdisk.o, cmpfile.o, disk_io.o, lsbrk.o, printstr.o.

A- Quel est la place et le rôle de l'éditeur de liens dans la chaîne de production de programmes.

B- En supposant que l'éditeur de liens suit l'algorithme présenté dans le livre, définir les adresses d'implantations des modules, en justifiant votre réponse.

C- Donner le contenu de la table des liens après prise en compte des liens des 5 modules (premier passage). Expliquez votre raisonnement.

`cmpdisk.o:`	`las`	`bloc_transfer_dr`
	`las`	`close_printer`
	`las`	`compare_file`
	`lu`	`compare_hierarch`	`1862`
	`las`	`exit`
	`lu`	`exit_prog`	`2820`
	`lu`	`file_error`	`422`
	`las`	`free`
	`las`	`get_memory`
	`lu`	`main`	`2460`
	`las`	`open_drive`
	`las`	`open_printer`
	`las`	`print_string`
`cmpfile.o:`	`las`	`bloc_transfer_dr`
	`lu`	`compare_file`	`200`
	`las`	`file_error`
`disk_io.o:`	`lu`	`bloc_transfer_dr`	`2118`
	`las`	`exit`
	`las`	`exit_prog`
	`las`	`get_memory`
	`lu`	`open_drive`	`236`
	`las`	`print_string`
`lsbrk.o:`	`las`	`exit_prog`
	`lu`	`get_memory`	`0`
	`las`	`lmalloc`
	`las`	`print_string`
`printstr.o:`	`lu`	`ask_confirm`	`758`
	`lu`	`close_printer`	`1028`
	`las`	`getchar`
	`lu`	`open_printer`	`996`
	`lu`	`print_string`	`340`
	`las`	`write`
table 1. résultat de `"listliens"`

	`cmpdisk.o`	`3376`
	`cmpfile.o`	`644`
	`disk_io.o`	`3862`
	`lsbrk.o`	`82`
	`printstr.o`	`1196`
	table 2. résultat de "`taille`"

D- Donner la liste des références croisées en expliquant votre raisonnement.

E- Certains liens ne sont pas définis. Donner lesquels. Comment seront-ils satisfaits?

F- Indiquer les liens qui ne sont à satisfaire dans aucun module. Sachant que le module du fichier cmpdisk.o est le programme principal dont l'adresse de lancement est main, et que les autres modules sont des sous programmes de service pouvant être utilisés dans d'autres programmes, précisez pour chacun d'eux s'il vous paraît logique de les trouver en tant que lien utilisable.

G- Dans quel ordre faudrait-il mettre les modules dans une bibliothèque, sachant que l'éditeur de lien la parcourt séquentiellement.

H- En vous inspirant de la question F, voyez-vous une utilisation particulière de l'outil listliens?

Solution de l'exercice 2.10

2.10.1. Question A

La construction de programmes peut devenir relativement complexe lorsque la taille du programme devient importante. Pour cela, on est amené à découper les programmes en modules. Chacun des modules peut être compilé de façon séparée. L'éditeur de liens a pour but de constituer un programme exécutable à partir d'un ensemble de modules. Le chargeur peut ensuite mettre en mémoire ce programme exécutable pour l'exécuter.

Le rôle de l'éditeur de liens se présente sous plusieurs aspects :

Assurer une fonction de placement des modules dans le programme exécutable. Ces modules ont été compilés de façon à pouvoir s'exécuter à un certain emplacement mémoire. Il s'agit de faire en sorte que tous les modules occupent des espaces disjoints à l'exécution (sauf si on désire utiliser des techniques de recouvrement qui ne seront pas abordées ici). La méthode la plus simple consistera à les mettre les uns derrière les autres en tenant compte de leur taille.
Translater les modules de façon à permettre leur bon fonctionnement dans l'espace qui leur a été attribué.
Relier les modules entre eux. Si l'on désire faire un programme avec un ensemble de modules, c'est que ces modules doivent coopérer pour cette exécution. Ceci veut dire que des sous programmes ou des variables appartenant à un module doivent pouvoir être utilisé par un autre module. Pour cela on a introduit la notion de lien représentant un tel depuis un module vers un autre. La partie du lien qui se trouve dans le module qui cherche à accéder à l'objet s'appelle le lien à satisfaire et la partie du lien qui est situé dans le module qui fourni l'objet s'appelle le lien utilisable. Relier consiste à associer les liens à satisfaire aux liens utilisables correspondants.
Compléter la liste des modules avec des modules en bibliothèque. Une liste initiale de modules est fournie à l'éditeur de liens qui relie les liens à satisfaire aux liens utilisables correspondants. Il est possible que certains liens à satisfaire ne correspondent à aucun lien utilisable d'un module de la liste. L'éditeur de liens utilisent ces liens à satisfaire pour rechercher dans les bibliothèques de modules s'il peut en trouver un qui contienne ce lien comme lien utilisable. Lorsqu'il en trouve, il ajoute ce module à la liste.

2.10.2. Question B

En faisant l'édition de liens des 5 modules dans l'ordre indiqué, les modules seront placés dans le programme exécutable dans cet ordre, les uns derrière les autres, en commençant à 0 pour le premier.

	`cmpdisk.o`	`0`
	`cmpfile.o`	`3376`
	`disk_io.o`	`4020`
	`lsbrk.o`	`7882`
	`printstr.o`	`7964`
	carte d'implantation des modules

Les modules de bibliothèques éventuels seront mis après, c'est-à-dire commenceront en 9160.

2.10.3. Question C.

Au cours du premier passage, l'éditeur de lien fixe la carte d'implantation des modules comme indiqué dans la question précédente. En même temps, il prend en compte l'ensemble des liens de ces modules, pour les mettre dans la table des liens. Pour chacun des liens trouvés dans un module, on effectue le traitement suivant :

S'il s'agit d'un lien utilisable, on modifie sa valeur en lui ajoutant l'adresse de début d'implantation du module, et on le recherche dans la table.

S'il y est comme lien utilisable, il y a double définition et on ne modifie pas la table.
S'il y est comme lien à satisfaire, on change son état en lien utilisable et on y met sa valeur.
S'il n'existe pas dans la table, on l'ajoute comme lien utilisable avec sa valeur.

S'il s'agit d'un lien à satisfaire, on le recherche dans la table.

S'il n'existe pas, il est rajouté comme lien à satisfaire.
S'il existe, la table n'est pas modifiée.

Appliquons ce traitement aux liens des modules fournis. Les liens du premier module sont entrés dans la table, soit comme lien à satisfaire, soit comme lien utilisable avec sa valeur (à laquelle on ajoute 0).	`las`	`bloc_transfer_dr`
	`las`	`close_printer`
	`las`	`compare_file`
	`lu`	`compare_hierarch`	`1862`
	`las`	`exit`
	`lu`	`exit_prog`	`2820`
	`lu`	`file_error`	`422`
	`las`	`free`
	`las`	`get_memory`
	`lu`	`main`	`2460`
	`las`	`open_drive`
	`las`	`open_printer`
	`las`	`print_string`
Le deuxième module conduit simplement à la modification du lien `compare_file`, qui devient utilisable, avec la valeur 3376+200=3576. Le troisième module, quant à lui, conduit à la transformation en liens utilisables d'une part de `bloc_transfer_dr` dont la valeur est maintenant 4020+2118=6138 et d'autre part de `open_drive` dont la valeur est maintenant 4020+236=4256.	`las`	`bloc_transfer_dr`	`6138`
	`las`	`close_printer`
	`las`	`compare_file`	`3576`
	`lu`	`compare_hierarch`	`1862`
	`las`	`exit`
	`lu`	`exit_prog`	`2820`
	`lu`	`file_error`	`422`
	`las`	`free`
	`las`	`get_memory`
	`lu`	`main`	`2460`
	`las`	`open_drive`	`4256`
	`las`	`open_printer`
	`las`	`print_string`
Le quatrième module transforme le lien `get_memory` en lien utilisable, avec la valeur 7882+0=7882, et ajoute le lien `lmalloc` comme lien à satisfaire.	`las`	`bloc_transfer_dr`	`6138`
	`las`	`close_printer`
	`las`	`compare_file`	`3576`
	`lu`	`compare_hierarch`	`1862`
	`las`	`exit`
	`lu`	`exit_prog`	`2820`
	`lu`	`file_error`	`422`
	`las`	`free`
	`las`	`get_memory`	`7882`
	`lu`	`main`	`2460`
	`las`	`open_drive`	`4256`
	`las`	`open_printer`
	`las`	`print_string`
	`las`	`lmalloc`

Enfin, le cinquième module conduit à la transformation en liens utilisables de `close_printer` avec la valeur 7964+1028=8992, `open_printer` avec la valeur 7964+996=8960 et `print_string` avec la valeur 7964+340=8304. De plus, sont ajoutés à la table le lien `ask_confirm` comme lien utilisable avec la valeur 7964+758= 8722, et les liens `get_char` et `write` comme liens à satisfaire.	`las`	`bloc_transfer_dr`	`6138`
	`las`	`close_printer`	`8992`
	`las`	`compare_file`	`3576`
	`lu`	`compare_hierarch`	`1862`
	`las`	`exit`
	`lu`	`exit_prog`	`2820`
	`lu`	`file_error`	`422`
	`las`	`free`
	`las`	`get_memory`	`7882`
	`lu`	`main`	`2460`
	`las`	`open_drive`	`4256`
	`las`	`open_printer`	`8960`
	`las`	`print_string`	`8304`
	`las`	`lmalloc`
	`lu`	`ask_confirm`	`8722`
	`las`	`getchar`
	`las`	`write`

2.10.4. Question D.

La liste des références croisées est obtenue en indiquant pour chaque lien, le module dans lequel il est défini en tant que lien utilisable (normalement il y en a au plus un), et la liste des modules dans lequel il apparaît en tant que lien à satisfaire.

lien	utilisable	à satisfaire
`bloc_transfer_dr`	`disk_io.o`	`cmpdisk.o, cmpfile.o`
`close_printer`	`printstr.o`	`cmpdisk.o`
`compare_file`	`cmpfile.o`	`cmpdisk.o`
`compare_hierarch`	`cmpdisk.o`
`exit`		`cmpdisk.o, disk_io.o`
`exit_prog`	`cmpdisk.o`	`disk_io.o, lsbrk.o`
`file_error`	`cmpdisk.o`	`cmpfile.o`
`free`		`cmpdisk.o`
`get_memory`	`lsbrk.o`	`cmpdisk.o, disk_io.o`
`main`	`cmpdisk.o`
`open_drive`	`disk_io.o`	`cmpdisk.o`
`open_printer`	`printstr.o`	`cmpdisk.o`
`print_string`	`printstr.o`	`cmpdisk.o, disk_io.o, lsbrk.o`
`lmalloc`		`lsbrk.o`
`ask_confirm`	`printstr.o`
`getchar`		`printstr.o`
`write`		`printstr.o`

2.10.5. Question E.

Les liens qui restent à satisfaire dans la table des liens après traitement des 5 modules ne sont pas définis, puisqu'ils n'ont pas été trouvés utilisables dans l'un de ces modules. Il s'agit de exit, free, lmalloc, getchar et write. Ces liens devront être satisfaits au moyen de modules de bibliothèques. De fait, il s'agit de procédures courantes, qui font appel au système :

exit permet de terminer l'exécution du programme,

free et lmalloc servent à la gestion dynamique de la mémoire,

getchar et write sont des procédures d'entrées sorties.

L'éditeur de liens recherchera les modules de bibliothèque qui contiennent comme lien utilisable ces liens restant à satisfaire dans la table.

2.10.6. Question F.

La liste des références croisées de la question D montre que compare_hierarch, main et ask_confirm sont définis comme lien utilisables dans un module, mais ne sont mentionnés comme lien à satisfaire dans aucun.

Le lien main étant l'adresse de lancement, il doit être utilisable pour que l'éditeur de lien puisse définir cette adresse de lancement dans le programme exécutable.
Le lien ask_confirm étant dans un module qui peut être utilisé par d'autres programmes, il est probable que ce module offre des possibilités qui ne sont pas utilisées dans ce programme, mais peuvent l'être dans d'autres.
Le lien compare_hierarch se trouve dans le programme principal, sans être utilisé dans un autre module. On peut en déduire que le fait que ce lien soit utilisable est inutile, et devrait être corrigé : le lien devrait rester interne au module cmpdisk.o.

2.10.7. Question G.

Le tableau des références croisées permet de construire le graphe des liens entre les modules. On trace un arc d'un module A vers un module B, s'il y a un lien à satisfaire dans A qui est utilisable dans B. Notons que dans ce cas, le module A devrait être placé avant le module B en bibliothèque pour que l'éditeur de liens ajoute B s'il a déjà ajouté A.

On peut constater sur le graphe ainsi obtenu qu'il y a plusieurs cycles. Ainsi le module cmpdisk.o doit être placé avant le module cmpfile.o, à cause du lien compare_file, mais ce module cmpfile.o doit être placé avant cmpdisk.o à cause du lien file_error. Cependant, le module cmpdisk.o est un programme principal; il ne devrait donc pas faire l'objet d'un chargement automatique, mais être le module de départ qui entraîne le chargement des autres. Il doit donc être mis en premier. Le reste du graphe impose alors la séquence complète, qui est donc : cmpdisk.o, cmpfile.o, disk_io.o, lsbrk.o, printstr.o.

2.10.8. Question H.

Lors de la question F, nous avons pu constater que notre programme principal exportait sans doute inutilement le lien compare_hierarch. L'outil listliens en listant les liens utilisables et les liens à satisfaire permet au programmeur de vérifier qu'un module exporte (liens utilisables) et importe (liens à satisfaire) juste ce qui doit l'être.