2.6. Étude du chargeur et de l'éditeur de liens
Le but de cet exercice est d'approfondir le fonctionnement
du chargeur et de l'éditeur de liens, déjà vu dans la
deuxième partie.
Le résultat d'une compilation ou d'un assemblage est un
fichier dont les enregistrements décrivent non seulement la traduction du
module source dans le langage de la machine, mais aussi les informations
nécessaires pour relier ce module aux autres modules qui constitueront un
programme. Ces enregistrements peuvent prendre diverses formes, suivant qu'ils
contiennent le code ou les données du module, ou servent à
l'établissements des liaisons intermodules. Pour fixer les idées,
nous définissons le type de ces enregistrements dans une forme
Pascal.
t_nature = (entête, lien_à_satisfaire, lien_utilisable, code_absolu,
code_à_translater, code_avec_l_a_s, adresse_lancement, fin_module);
t_enregistrement = article
variante nature : t_nature dans
entête: ( identificateur_module : t_identificateur;
taille : entier );
lien_à_satisfaire: ( identificateur_l_a_s : t_identificateur );
lien_utilisable: ( identificateur_l_u : t_identificateur;
valeur_l_u : entier );
code_absolu, code_à_translater:
( adresse_code : entier;
valeur_code : entier );
code_avec_l_a_s: ( adr_code_l_a_s : entier;
numéro_l_a_s : entier;
valeur_code_l_a_s : entier );
adresse_lancement: ( adr_lanc : entier );
fin_module: ( ) ;
finarticle;
Remarques:
- La forme présentée par les modules objets, en
réalité, est en général plus complexe, mais plus
condensée.
- Le champ taille de
l'enregistrement entête
précise le nombre d'emplacements occupés par le module.
- Les
liens à satisfaire sont implicitement numérotés, à
partir de 1, suivant l'ordre d'apparition, dans le module, des enregistrements
lien_à_satisfaire qui les
contiennent.
On suppose que l'on dispose d'une
procédure lire_enrg qui assure la
lecture d'un enregistrement du fichier dans la variable
enrg de type
t_enregistrement défini ci-dessus.
On suppose, pour simplifier que dans le cas où on a une liste de modules,
cette procédure lire_enrg sait
où trouver successivement les modules de la liste, et qu'elle est
complétée par la fonction à résultat booléen
il_y_a_des_modules, ainsi que par la
procédure premier_module qui
prépare le positionnement sur le premier enregistrement du premier module
de la liste. Par ailleurs, on dispose d'une procédure
écrire_enrg pour écrire la
variable enrg sur un fichier.
A- Pour fixer les idées, supposons que notre
machine ait une mémoire de 10000 emplacements pouvant contenir chacun un
entier, qui peut représenter une donnée ou une instruction. Elle
dispose de 5 instructions qui sont codées comme suit:
LOAD <adresse> 10000 + adresse met MEMOIRE[adresse] dans l'accumulateur
ADD <constante> 20000 + constante ajoute la constante à l'accumulateur
MUL <constante> 30000 + constante multiplie l'accumulateur par la constante
STORE <adresse> 40000 + adresse met l'accumulateur dans MEMOIRE[adresse]
JMP <adresse> 50000 + adresse aller à l'instruction située à adresse
On
considère le module suivant:
NOM ESSAI nom du module
PUBLIC INCR
EXTERN SUITE
A: WORD =25 réservation d'un emplacement pour A initialisé à 25
B: WORD 1 réservation d'un emplacement pour B non initialisé
INCR: LOAD A
MUL 10
ADD 1
STORE B
JMP SUITE
FINA.1- Donner
la suite d'enregistrements que doit produire l'assembleur pour ce
module.
A.2- Lors d'une édition de liens d'un programme,
le module ESSAI est placé à
l'emplacement relatif 123 dans le programme
exécutable. SUITE est un lien
utilisable dans un autre module, à l'emplacement relatif
8. Cet autre module est placé
immédiatement derrière le module
ESSAI dans le programme exécutable.
Donner la suite des enregistrements produits par l'éditeur de liens en
provenance du module ESSAI.
A.3- Le chargeur place le programme à
l'emplacement 1042 de la mémoire.
Donner le contenu des emplacements de la mémoire qui contiennent ce
module.
B- La structure de ces enregistrements est utilisable
aussi bien dans les modules objets, entre les compilateurs et l'éditeur
de liens, que dans les programmes exécutables, entre l'éditeur de
liens et le chargeur. Expliquer pourquoi. Quels enregistrements ne doivent pas
se trouver dans un programme exécutable?
C- On se propose de construire l'éditeur de liens
en deux passages: le premier au cours duquel on fixe la carte d'implantation des
modules, et où on construit la table des liens, le second passage au
cours duquel on effectue la translation et où on établit les liens
entre les modules. On dispose, pour la gestion de cette table, de trois
procédures:
procédure entrer
(identificateur : t_identificateur; valeur : entier); ajoute une
entrée dans la table,
fonction recherche
(identificateur : t_identificateur; var valeur : entier):
booléen; recherche une entrée dans la table, retourne
vrai si cette entrée a été trouvée, et met
dans valeur celle qui était mémorisée dans la table
pour cet identificateur; retourne faux si l'entrée n'existe
pas.
procédure
modifier (identificateur : t_identificateur; valeur :
entier ); change la partie valeur de l'entrée de la table
associée à l'identificateur donné en
paramètre.
C.1- Définir la procédure de premier
passage pour l'ensemble des modules à relier en supposant que l'on
dispose d'une procédure
lire_liens_module qui traite les liens d'un
module.
C.2- Définir la procédure
lire_liens_module qui constitue la table
des liens.
C.3- Définir la procédure de second passage
pour l'ensemble des modules à relier en supposant que l'on dispose d'une
procédure traiter_module qui produit
les enregistrements relatifs à un module.
C.4- Définir la procédure
traiter_module.
D- Définir la procédure du chargeur, dont
la spécification, i.e. l'en-tête, est:
procédure charger ( nom : t_identificateur;
adresse_chargement, taille : entier);
qui
vérifie la concordance du nom avec celui du module exécutable,
contrôle que la zone mémoire définie par les
paramètres est compatible avec la définition du module et en
assure le chargement en mémoire à l'adresse fournie en
paramètre, la translation et le lancement.
Solution de l’exercice
2.6
2.6.1. Question A
2.6.1.1. Question A.1
Le module objet doit se présenter sous la forme
suivante:
< entête ESSAI 7 >
< lien_utilisable INCR 2 >
< lien_à_satisfaire SUITE >
< code_absolu 0 25 >
< code_à_translater 2 10000 >
< code_absolu 3 30010 >
< code_absolu 4 20001 >
< code_à_translater 5 40001 >
< code_avec_l_a_s 6 1 50000 >
< fin_module >
Remarquons
qu'il n'y a pas d'enregistrement pour l'emplacement correspondant à
l'objet B. On pourrait en mettre un si on
voulait lui donner une valeur initiale.
2.6.1.2. Question A.2
Lors de l'édition de liens, le module étant
placé à l'emplacement 123, il faut ajouter cette valeur aux
adresses internes. Comme il est de taille 7, le module placé
derrière lui sera placé à l'emplacement relatif 130. Comme
SUITE est un lien utilisable défini
comme emplacement relatif 8 de ce module, il est donc à l'emplacement
relatif 138 du programme. Les enregistrements produits par l'éditeur de
liens pour ce module sont donc les suivants:
< code_absolu 123 25 >
< code_à_translater 125 10123 >
< code_absolu 126 30010 >
< code_absolu 127 20001 >
< code_à_translater 128 40124 >
< code_à_translater 129 50138 >
2.6.1.3. Question A.3
Les emplacements occupés par ce module après
chargement sont définis comme suit:
1165 25
1166 ?
1167 11165
1168 30010
1169 20001
1170 41166
1171 51180
Le
programme étant en 1042, le module commence en 1042+123 = 1165. Par
ailleurs, le chargeur ajoute 1042 aux emplacements contenant un code à
translater. L'emplacement associé à
B a un contenu indéterminé,
puisqu'il n'est pas initialisé.
2.6.2. Question B
La structure de
t_enregistrement convient évidemment
pour les modules objets, puisqu'elle permet d'une part la définition des
liens à satisfaire et des liens utilisables, d'autre part la translation
de code et les liaisons vers d'autres modules par les enregistrements
code_avec_l_a_s. Notons que les liens
à satisfaire étant repérés dans ce cas par leur
numéro d'ordre, l'enregistrement
lien_à_satisfaire correspondant au
nième lien à
satisfaire doit se trouver avant les enregistrements
code_avec_l_a_s mentionnant ce
numéro n.
Pour un module exécutable, la structure convient aussi,
mais certains enregistrements ne devront pas se trouver dans un tel module. En
effet, un module exécutable ne peut contenir que les enregistrements
entête,
code_absolu,
code_à_translater,
adresse_lancement, ou
fin_module. On peut admettre aussi les
enregistrements lien_utilisable, mais les
enregistrements lien_à_satisfaire et
code_avec_l_a_s sont interdits.
2.6.3. Question C
2.6.3.1. Question C.1
Le premier passage doit construire la carte d'implantation des
modules, en fixant l'adresse origine de chaque module. C'est au cours de ce
premier passage que l'on fixe les valeurs des liens utilisables de l'ensemble
des modules. On peut aussi prendre en compte les liens à satisfaire, de
façon à permettre ensuite de compléter la liste des modules
avec d'autres provenant de bibliothèques, qui contiennent ces liens comme
liens utilisables, s'ils n'ont pas été trouvés dans la
liste initiale des modules. Nous identifierons les liens à satisfaire par
une valeur égale à -1. Le programme principal est le
suivant:
procédure premier_passage ;
var adr_implantation;
début adr_implantation := 0;
premier_module;
tantque il_y_a_des_modules faire
lire_liens_module ( adr_implantation );
fait;
tantque il_y_a_des_entrées_de_la_table_avec_valeur_négative faire
si un_module_bibliothèque_contient_un_tel_lien_utilisable alors
ajouter_ce_module_à_la_liste;
lire_liens_module ( adr_implantation );
finsi;
fait;
fin;
2.6.3.2. Question C.2
Pour faciliter l'écriture de la procédure de
lecture des liens d'un module, on définit deux procédures qui
effectuent l'adjonction d'un lien dans la table,
ajout_l_u et
ajout_l_a_s. Par ailleurs, nous
utiliserons une procédure erreur qui imprime le message fourni en
paramètre, et arrête le programme.
procédure ajout_l_u ( id : t_identificateur; val : entier );
var valeur : entier;
début si recherche ( id, valeur ) alors
si valeur = -1 alors { identificateur rencontré comme l_a_s }
modifier ( id, val );
sinon
erreur ("double définition"); {identificateur rencontré comme l_u }
finsi;
sinon entrer ( id, val ); { identificateur non encore rencontré }
finsi;
fin;
procédure ajout_l_a_s ( id : t_identificateur );
var valeur : entier;
début si non recherche ( id, valeur ) alors entrer ( id, -1 ); finsi;
fin;
procédure lire_liens_module ( var adresse : entier );
var adr_impl : entier;
début lire_enrg;
si enrg.nature <> entête alors erreur ( "pas en début de module" );
sinon
adr_impl := adresse;
adresse := adresse + enrg.taille;
ajout_l_u ( enrg.identificateur_module, adr_impl );
tantque enrg.nature <> fin_module faire
lire_enrg;
si enrg.nature = lien_à_satisfaire alors
ajout_l_a_s ( enrg.identificateur_l_a_s );
sinon si enrg.nature = lien_utilisable alors
ajout_l_u(enrg.identificateur_l_u,enrg.valeur_l_u + adr_impl);
finsi;
finsi;
fait;
finsi;
fin;
2.6.3.3. Question C.3
Le deuxième passage a pour but de faire un seul module
exécutable avec l'ensemble des modules de la liste augmentée
éventuellement de ceux provenant de la bibliothèque. Les
enregistrements relatifs à chacun des modules sont produits par la
procédure traiter_module. Il s'agit
ici de produire le premier enregistrement, d'exécuter cette
procédure sur chacun des modules et de produire le dernier
enregistrement.
procédure deuxième_passage ;
début enrg.nature := entête;
enrg.identificateur_module := nom_du_programme;
enrg.taille := taille_du_programme; { adr_implantation fin de passage 1 }
écrire_enrg;
premier_module;
tantque il_y_a_des_modules faire traiter_module; fait;
enrg.nature := fin_module;
écrire_enrg;
fin;
2.6.3.4. Question C.4
Le deuxième passage doit effectuer la translation des
modules et établir les liaisons intermodules, en utilisant la table des
liens construite au premier passage. Le traitement des enregistrements
code_avec_l_a_s nécessite de
disposer d'une table locale qui associe à chaque numéro de lien
à satisfaire sa valeur provenant de la table globale. Lors de la
recherche de ce lien dans la table globale, il doit normalement s'y trouver,
puisque le premier passage l'y a mis. Il peut cependant ne pas être
défini, si on n'a pas trouvé de lien utilisable
correspondant.
La procédure de traitement d'un module est
décomposée en un ensemble de procédures, chacune d'elles
correspondant au traitement à faire pour chaque enregistrement du module,
suivant sa nature.
var table_liens_à_satisfaire : tableau [ 0..500 ] de entier;
nb_las, base_impl : entier;
procédure traiter_lien_à_satisfaire;
var valeur : entier;
début si nb_las = 500 alors erreur("trop de liens à satisfaire dans module");
sinon
nb_las := nb_las + 1;
si recherche ( enrg.identificateur_l_a_s, valeur ) alors
si valeur = -1 alors
erreur ( "identificateur non défini", enrg.identificateur_l_a_s );
finsi;
sinon erreur ( "anomalie de fonctionnement" );
finsi;
table_liens_à_satisfaire [ nb_las ] := valeur;
finsi;
fin;
procédure traiter_code_absolu;
début enrg.adresse_code := enrg.adresse_code + base_impl;
écrire_enrg;
fin;
procédure traiter_code_à_translater;
début enrg.adresse_code := enrg.adresse_code + base_impl;
enrg.valeur_code := enrg.valeur_code + base_impl;
écrire_enrg;
fin;
procédure traiter_code_avec_l_a_s;
début enrg.adresse_code := enrg.adr_code_l_a_s + base_impl;
si enrg.numéro_l_a_s > nb_las alors erreur ( "module incorrect" );
sinon enrg.valeur_code := enrg.valeur_code_l_a_s +
table_liens_à_satisfaire [ enrg.numéro_l_a_s ];
finsi;
enrg.nature := code_à_translater;
écrire_enrg;
fin;
procédure traiter_adresse_lancement;
début enrg.adr_lanc := enrg.adr_lanc + base_impl;
écrire_enrg;
fin;
procédure traiter_module;
début lire_enrg;
si enrg.nature <> entête alors erreur ( "pas en début de module" );
sinsi recherche ( enrg.identificateur_module , base_impl ) alors
nb_las := 0;
tantque enrg.nature <> fin_module faire
lire_enrg;
cas enrg.nature dans
lien_à_satisfaire: traiter_lien_à_satisfaire;
code_absolu: traiter_code_absolu;
code_à_translater: traiter_code_à_translater;
code_avec_las: traiter_code_avec_las;
adresse_lancement: traiter_adresse_lancement;
lien_utilisable, fin_module : ;
autre : erreur ( "module incorrect" );
fincas;
fait;
sinon erreur ( "module non rencontré en premier passage" );
finsi;
fin;
2.6.4. Question D
La procédure ne présente pas de
difficulté particulière. On peut faire une procédure
interne ranger qui assure le contrôle
des adresses et le rangement en mémoire des valeurs successives,
éventuellement translatées. Cette vérification doit souvent
être faite, car le chargeur lui-même peut parfois accéder
à toute la mémoire, sans protection particulière. Il faut
aussi contrôler l'absence des enregistrements interdits. Enfin pour
pouvoir faire le lancement du programme, il faut contrôler la
présence de l'enregistrement correspondant, et vérifier son
paramètre.
procédure charger(nom: t_identificateur; adresse_chargement, taille: entier);
var adresse_init : entier;
adr_lanc_prés : booléen;
procédure ranger ( adr , val : entier );
début si adr < taille alors mémoire [ adresse_chargement + adr ] := val;
sinon erreur ( "module incorrect" );
finsi
fin;
{ corps de la procédure charger }
début lire_enrg;
si enrg.nature <> entête ou enrg.identificateur_module <> nom
ou enrg.taille > taille alors erreur ( "paramètres incompatibles" );
sinon
adr_lanc_prés := faux ;
tantque enrg.nature <> fin_module faire
lire_enrg;
cas enrg.nature dans
code_absolu: ranger ( enrg.adresse_code, enrg.valeur_code );
code_à_translater: ranger ( enrg.adresse_code,
enrg.valeur_code + adresse_chargement );
adresse_lancement:
si enrg.adr_lanc < taille alors
adresse_init := enrg.adr_lanc + adresse_chargement;
adr_lanc_prés := vrai;
sinon erreur ( "module incorrect" );
finsi;
fin_module, lien_utilisable: ;
autre : erreur ( "module non conforme" );
fincas;
fait;
si adr_lanc_prés alors compteur_ordinal := adresse_init;
sinon erreur ( "programme sans adresse de lancement" );
finsi;
finsi;
fin;