Le istruzioni: procedure e flusso di sviluppo

Luigi  Palopoli  

Procedure

•  L’u,lita’  di  un  computer  sarebbe  molto  limitata  se  non  si  potessero  chiamare  procedure  (o  funzioni)  

•  Possiamo  pensare  a  una  procedure  come  a  una  “spia”  che  fa  del  lavoro  per  noi  senza  che  noi  vogliamo  sapere  come  lo  fa  

•  La  cosa  importante  e’  di  me>ersi  d’accordo  su  un  protocollo  

Procedure

•  L’u,lita’  di  un  compute  sarebbe  molto  limitata  se  non  si  potessero  chiamare  procedure  (o  funzioni)  

•  Possiamo  pensare  a  una  procedure  come  a  una  “spia”  che  fa  del  lavoro  per  noi  senza  che  noi  vogliamo  sapere  come  lo  fa  

•  La  cosa  importante  e’  di  me>ersi  d’accordo  su  un  protocollo  

Protocollo

1.  me>er  i  parametri  in  un  posto  noto  2.  trasferire  il  controllo  alla  procedura  

1.  Acquisire  le  risorse  necessarie  2.  Eseguire  il  compito  3.  me>ere  i  valori  di  ritorno  in  pos,  no,  4.  Res,tuire  il  controllo  al  chiamante  

3.  Prendersi  il  valore  di  ritorno  e  “cancellare”  le  traccie  

Protocollo

•  Il  modo  in  cui  questo  protocollo  viene  messo  in  pra,ca  dipende  dall’archite>ura  e  dalle  convenzioni  di  chiamata  del  compilatore  

•  Ci  limi,amo  a  pochi  cenni  per  il  MIPS  

Protocollo di chiamata MIPS

•  L’idea  di  base  e’  di  cercare  di  laddove  possibile  i  registri,  perche’  sono  il  meccanismo  piu’  veloce  per  effe>uare  il  passaggio  dei  parametri  

•  Convenzione  per  il  MIPS  §  $a0,  ..$a3:  usa,  per  i  parametri  in  ingresso  §  $v0,  $v1    :  valori  di  ritorno  §  $ra                      :  indirizzo  di  ritorno  per  tornare  al  punto  di  partenza    

 

Protocollo di chiamata MIPS

•  Oltre  ai  registri,  l’hardware  MIPS  me>e  a  disposizione  l’istruzione  di  jump  and  link  (JAL)  che  effe>ua  il  salto  e  contemporaneamente  memorizza  in  ra  l’indirizzo  di  ritorno  §  L’indirizzo  che  viene  salvato  in  ra  e’  il  PC  (program  counter)  incrementato  di  4  (istruzione  sucessiva  alla  jal)  

•  Alla  fine  della  procedura  sara’  sufficiente  fare  un  salto        

 jr $ra!

!!

…e se i registri non bastano?

•  In  cer,  casi  I  registri  non  bastano  perche’  ho  piu’  parametri  di  quan,  ne  possano  contenere  I  registri    

•  In  tal  caso  si  una  lo  stack,  una  stru>ura  da,  ges,ta  con  disciplina  FIFO  in  cui  e’  possibile  me>ere  a  par,re  da  una  posizione  nota  alla  procedura  (puntata  dal  registro  fp)  I  parametri  in  piu’  

•  Lo  stack  si  puo’  usare  anche  me>ere  variabili  locali  (tramite  un’operazione  di  push)  e  salvare  registri  che  occorrera’  ripris,nare  in  seguito  

•  Alla  fine  della  procedura  si  puo’  ripulire  lo  stack  (operazione  pop)  riportandolo  alla  situazione  precedente  

Esempio

•  Consideriamo  la  procedura  in  C:  

int esempio_foglia(int g, int h, int i, int j) {! int f;!! f = (g+h) – (i+j);! return f;!}!

•  Cerchiamo  di  capire  come  verrebbe  trado>a  

Prologo

•  Per  prima  cosa  il  compilatore  sceglie  un’e,che>a  associata  all’indirizzo  di  entrata  della  procedura  (esempio_foglia)  §  In  fase  di  collegamento  (linking)  l’e,che>a  sara’  collegata  a  un’indirizzo  

•  La  prima  operazione  e’  quella  di  salvare  in  memoria  tuZ  I  registri  che  la  procedura  usa  in  modo  da  poterli  ripris,nare  in  seguito  

•  Tale  fase  e’  chiamata  prologo  e  potrebbe  richiedere  di  allocare  nello  stack  anche  spazio  per  le  variabili  locali  (se  i  registri  non  bastano).  

Prologo •  La  procedura  us  I  registri  s0,  t0,  t1;    •  Il  registro  SP  punta  alla  testa  dello  stack  (che  si  evolve  verso  il  basso)  •  Il  codice  del  prologo  e’  il  seguente:  

esempio_foglia: addi $sp, $sp, -12;!! ! ! ! !sw $t1, 8($sp)!! ! ! ! !sw $t0, 4($sp)!! ! ! ! !sw $s0, 0($sp)!

Decremen,amo  sp  di  12,  per  far  posto  a  3  

word    

Salvataggio  di  t1  in  sp+8  

Salvataggio  di  s0  in  sp+0  

Esecuzione della procedura

•  Dopo  il  prologo,  l’esecuzione  della  procedura:  

add $t0, $a0, $a1!add $t1, $a2, $a3!sub $s0, $t0, $t1!

In  t0  meZamo  g+h  

In  t1  meZamo  i+j  

In  s0  (g+h)-­‐(i+j)  

Epilogo

•  Dopo  aver  eseguito  la  procedura,  si  ripris,nano  i  registri  usa,  e  si  se>a  il  valore  di  ritorno  

add $v0, $s0, $zer0 !lw $s0, 0($sp)!lw $t0, 4($sp)!lw $t1, 8($sp)!addi $sp, $sp, 12!jr $ra!!

Trasferiamo  s0  in  v0  (valore  di  ritorno)  

Ripris,no  I  registri  prelevando  i  valori  

esa>amente  da  dove  li  avevo  messi  

Ripris,no  lo  stack  (tu>o  cio’  che  e’  so>o  sp  non  e’  significa,vo)  

Salto  al  punto  da  dove  sono  arrivato  

Evoluzione dello stack

Stack  prima  della  chiamata  

Stack  durante  l’esecuzione  della  

procedura  

Stack  dopo  la  chiamata  

Ulteriori complicazioni

•  In  realta’  le  cose  possono  complicarsi  per  via  di  §  Variabili  locali  §  Procedure  annidate  

•  Questo  si  risolve  usando  sempre  lo  stack  e  allocandovi  dentro  variabili  locali  e  valori  del  registro  ra  

•  Vediamo  un  esempio  

Procedure ricorsiva

•  Qui  (ma  sarebbe  lo  stesso  con  una  qualsiasi  funzione  che  chiama  un’altra  funzione)  abbiamo  due  problemi:  §  sovrascri>ura  di  $ra  che  mi  renderebbe  impossibile  il  ritorno  una  volta  finita  la  chiamata  innestata.  

§  Sovrascri>ura  di  $a0  usato  per  il  registro  n  

int fact(int n) {! if (n < 1) !

!return 1;! else!

!return n*fact(n-1);!}!

•  Consideriamo  il  seguente  esempio  

Procedure ricorsiva

Fact:!!addi $sp, $sp, -8 #Ci serve spazio per due oggetti!!sw $ra, 4($sp) #Salviamo ra!!sw $a0, 0($sp) #Salviamo a0!

•  Soluzione:  salvaguardare  il  registro  $ra,  a0  •  Vediamo  la  soluzione  •  Primo  step:  creiamo  spazio  nello  stack  e  salviamo  ra  e  a0  

•  Secondo  step,  tes,amo  se  n  <1  (ritornando  1  in  caso  afferma,vo):    

!slti $t0, $a0, 1 #t0 settato a 1 se n < 1!!beq $t0, $zero, L1 #Se n > 1 saltiamo a L1!

Procedure ricorsiva

•  Se  n  <=  1  chiudiamo  la  procedura        nota  che  non  ripris,niamo  ra  e  a0  (come  si  farebbe  normalmente,  perchè  non  li  abbiamo  cambia,)  

•  Se  n  >  1  decremen,amo  n  e  richiamiamo  fact    

!addi $v0, $zero, 1 #metodo del MIP per mettere in v0 1!!addi $sp, $sp, 8 #Ripuliamo lo stack!!jr $ra #Ritorniamo all’indirizzo di ritorno!

L1:!addi $a0, $a0, -1 #decrementiamo n!!jal fact #chiamiamo fact(n-1)!

Procedure ricorsiva

•  A  questo  punto  ripris,niamo  a0  e  ra  e  ripuliamo  lo  stack    !lw $a0, 0($sp) #Ripristino a0!

!lw $ra, 4($sp) #Ripristino ra!!addi $sp, $sp, 8 #ripulisco stack!

•  Non  ci  resta  che  mol,plicare  fact(n-­‐1),  che  è  in  v0,  per  n  e  ritornare  

!mul $v0, a0, $v0!!jr $ra!

Storage class

•  Le  variabili  in  C  sono  in  genere  associate  a  locazioni  di  memoria  

•  Si  cara>erizzano  per  §  Tipo  (int,  char,  float)  §  Storage  class  

•  Il  C  ha  due  possibili  storage  class  §  Automa,c  (variabili  locali  che  hanno  un  ciclo  di  vita  collegata  alla  funzione)  

§  Sta,c  sopravvivono  alle  chiamate  di  procedura.  Sono  essenzialmente  variabili  globali  o  definite  dentro  funzioni  come  sta,c  

•  Le  variabili  sta,che  sono  memorizzate  in  una  zona  di  memoria  (nel  MIPS  accessibile  a>raverso  il  registro  global  pointer,  $GP)  

Variabili locali

•  L’ul,mo  problema  è  cos,tuito  dalle  variabili  locali  

•  Quando  sono  poche,  si  riescono  a  usare  registri  

•  Quando  sono  tante  (ad  esempio  struct  complesse  o  array)  non  ci  sono  abbastanza  registri    

•  Quello  che  si  fa  è  allocare  le  variabili  locali  nello  stack  

Record di attivazione

•  Il  segmento  di  stack  che  con,ene  registri  salva,  e  variabili  locali  rela,ve  a  una  funzione  viene  chimata  record  di  aZvazione  (o  procedure  frame)  

•  Le  variabili  locali  vengono  individuate  tramite  un  offset  a  par,re  da  un  puntatore  

•  Il  puntatore  $sp  è  alle  volte  scomodo  come  base  perchè  cambia  durante  l’esecuzione  della  funzione  

•  Il  registro  $fp  (frame  pointer)  viene  sempre  mantenuto  costante  durante  la  funzione  e  può  essere  usato  come  base.  

Evoluzione dello stack

$fp  

$sp   $fp  

$sp  

Saved  arguments  registers  

Saved  return  address  Saved  

registers  Saved  

registers  

$fp  

$sp  

Prima  della  chaimata  

Durante  la  chiamata  

Dopo  la  chiamata  

Dati dinamici

•  In  aggiunta  a  variabili  globali  e  variabili  locali  abbiamo  anche  le  variabili  dinamiche  (quelle  che  vengono  allocata  con  malloc/free,  new/delete)  

•  Il  MIPS  ado>a  il  seguente  schema  di  memoria    

Resrved  

Text  

Sta,c  Data  

stack  

Dynamic  data  

$sp  

$gp  

$pc  

Lo  stack  procede  per  indirizzi  decrescen,  

Lo  heapprocede  per  indirizzi  crescen,  

Convenzioni sui registi •  In  base  alle  convenzioni,  l’uso  dei  registri  è  nella  sequente  tabella  

Nome   Numero   Uso   Preservare  

$zero   0   Valore  costante  0   n.a.  

$v0  -­‐  $v1   2-­‐3   Valori  di  ritorno  per  chiamate  di  funzioni  e  valuazione  di  espressioni  

No  

$a0-­‐$a3   4-­‐7   Argomen,     No  

$t0-­‐$t7   8-­‐15   Temporanei   No  

$s0  -­‐  $s7   16-­‐23   Salva,   Si  

$t8-­‐$t9   24-­‐25   Ulteriori  temporanei   No  

$gp   28   Puntatore  ai  globali   Si  

$sp   29   Putnatore  allo  stack   Si  

$fp   30   Frame  pointer   Si  

$ra   31   Return  Address   si  

Elaborazione

•  Per  quanto  le  ricorsioni  siano  elegan,  spesso  sono  causa  di  varie  inefficienze  

int sum(int n) {! if (n > 0) !

!return sum(n-1) + n;! else!

!return n;!}!

Never  hire  a  programmer  who  solve  the  factorial  with  a  recursion  

•  Consideriamo  la  seguente  funzione  

Elaborazione

•  Consideriamo  la  chiamata  sum  (2)  

Sum  (2)  

n  =  2  

Sum  (1)  

n  =  1  

Sum  (0)  

n  =  0  

2+sum(1)  

1+sum(0)  0  

1+0  

2+1  

Il  valore  di  ritorno  viene  costruito  Tornando  su  per  la  catena  di  chiamate.  Ogni  frame  di  aZvazione  deve  essere    Preservato  per  produrre  il  risutlato    

corre>o.  

Elaborazione

•  Consideriamo  ora  il  codice  così  modicato  

int sum(int n, int acc) {! if (n > 0) !

!return sum(n-1, acc+n);! else!

!return acc;!}!

•  Stavolta  la  chiamata  ricorsiva  è  l’ul,ma  cosa  che  la  funzione  fa  (si  limita  a  ritornare).    

•  Questa  ricorsione  viene  de>a  di  coda…ritorniamo  al  nostro  esempi  sum(2,0).  

Elaborazione

•  Consideriamo  la  chiamata  sum  (2)  

Sum  (2,0)  

n  =  2,  acc=0  

Sum  (1)  

n  =  1,  acc=  2  

Sum  (0)  

Sum(1,2)  

Sum(0,  3)  3  

3  

3  

n  =  0,  acc=  3  

In  questo  caso  lungo  I  rami  di  ro,orno  non  faccio  

Che  res,tuire  3.  Conservare  I  da,  nello  stack  

Di  aZvazione  è  inu,le.  Posso  usare  Un  unico  stack  di  aZvazione  e  svlogere  

La  ricorsione  in  itnerazione.    

Ottimizzazione

•  Alcuni  compilatori  riconoscono,  e  possono  oZmizzare  come  segue  (assumiamo  a0  =  n,  a1=acc)  

Sum: !slti $t0, $a0, 1 #t0=1 se a0 <= 0!! !bne $t0, $zero, sum_exit #se n <= 0 vai a sum_exit !! !add $a1, $a1, $a0 #somma n ad acc!! !addi $a0, $a0, -1 #sottrai 1 da n!! !j sum!

Sum_exit:!! !add $v0, $a1, $zer0! ! ! !#inderisci acc in v0!! !jr $ra!

•  Certo  se  se  ne  rende  conto  il  programmatore  e  lo  fa  dire>amente  è  meglio  :=)    

Comunicare

•  Fino  ad  ora  abbiamo  visto  come  un  computer  si  può  usare  per  fare  con,  

•  In  realtà  altre>anto  importante  è  la  capacità  per  un  computer  di  comunicare  tramite  tes,  

•  Questo  può  essere  fa>o  codificando  i  cara>eri  con  sequenze  di  bit  

Comunicare

•  Fino  ad  ora  abbiamo  visto  come  un  computer  si  può  usare  per  fare  con,  

•  In  realtà  altre>anto  importante  è  la  capacità  per  un  computer  di  comunicare  tramite  tes,  

•  Questo  può  essere  fa>o  codificando  i  cara>eri  con  sequenze  di  bit  

Codifica ASCII

•  Una  delle  codifiche  più  famose  e  usate  e  quella  ASCII  (su  7  bit)  

Istuzioni per caricare e scaricare byte

•  Il  fa>o  che  la  codifica  ASCII  sia  così  popolare  obbliga  in  sostanza  ad  avere  istruzioni  di  trasferimento  che  operano  sul  byte  

!lb $t0, 0($sp) #legge un byte dalla cima dello stack !! ! ! ! ! #e lo inserisce nei bit meno significativi!! ! ! ! ! # di t0!!sb $t0, 0($gp) # inserisci gli otto bit meno significativi!! ! ! ! ! #di to in $gp !

Esempio

•  In  C  una  stringa  è  un  array  di  byte  terminata  dal  cara>ere  0  

•  Consideriamo  il  seguente  programma  C    

void strcpy(char * x, char * y) {!!int i;!

!!i=0;!!while((x[i]=y[i])!=‘\0’)!! !i+= 1;!

}!!

Esempio

•  Vediamo  la  traduzione  in  assembler  MIPS  •  Prima  cosa  salviamo  nello  stack  s0  in  cui  me>eremo  i  

 Strcpy: !!addi $sp, $sp, -4 #creiamo nello stack spazio per a0!!sw ! ! $s0, 0($sp) #salviamo s0!

!

•  A  questo  punto  seZamo  i  a  0    addi $s0, $zero, $zero #i = 0+0!!

Esempio

•  Step  successivo  meZamo  in  t1  l’indirizzo  di  y[i]  (label  con  inizio  del  loop)      Contrariamente  ai  preceden,  esempi  sugli  array,  qui  non  abbiamo  bisogno  di  mol,plicare  per  4  perchè  l’accesso  è  al  singolo  byte  

L1: add $t1, $s0, $a1 #indirizzo di y[i] in t1 !!

Esempio

•  A  questo  punto  inseriamo  il  cara>ere  puntato  da  y[i]  in  t2      Notare  che  il  cara>ere  è  un  unsigned  byte  

•  Memorizziamo  y[i]  in  x[i]      usciamo  dal  loop  se  y[i]  è  0  

lbu $t2, 0($t1) #t2 = y[i] !!

add $t3, $s0, $a0 #indirizzo di x[i] in t1 !sb $t2, 0($t3) #x[i]=y[i]!

beq $t2, $zero, L2 #se y[i]==0 vai a L2!

Esempio

•  In  caso  nega,vo  chiudo  il  loop  incrementando  i      

•  Uscita  dalla  procedura  con  rispris,no  di  s0,  rimozione  dallo  stack  e  ritorno    

addi $s0, $s0, 1 #i = i +1 !j L1 #Salta a L1!

L2: lw $s0, 0($sp) #ripristino s0!!addi $sb, $sp, 4 #ripulitura dello stack!!jr $ra #ritorno!

E che ne è delle lettere accentate?

•  Ascii  va  bene  solo  per  l’alfabeto  inglese  •  Esiste  una  codifica  che  usa  16  bit  ed  è  ado>ata  in  Java  che  si  chiama  unicode.  

•  La  codifica  unicode  è  suddivisa  in  blocchi.    •  Ciascun  blocco  con,ene  un  numero  di  cara>eri  pari  a  un  mul,plo  di  16  §  Es  le>ere  greche  partono  da  X0370,  quelle  cirilliche  da  X0400  

Blocchi Unicode

Caricamento di mezza parola

•  Per  supportare  ques,  ,pi  di  da,  a  16  bit,  l’assembler  MIPS  me>e  a  disposizione  la  possibilità  di  caricare/scaricare  anche  metà  parola  (I  16  bit  meno  significa,vi)  in  e  da  un  registro  

lhu $t0, 0($sp) #legge mezza parola (unsigned)!Sh $t0, 0($gp) #memorizza mezza parola (Signed)!

Riepilogo sulle modalià di indirizzamnto

Operandi  Costan,,  caricamento/scaricamento  

Operazioni  su  registri  

Salto  condizionato  

Salto  incodizionato  

Toolchain  

A.K.A. quella roba per passare da codice ad eseguibile  

Non parliamo la stessa lingua  

Quando programmiamo usiamo linguaggi che sono più vicini a noi che al PC.  

Imparare una lingua è difficile  

•  Per poter parlare come dei nativi è necessario lavorare molto, e col PC è uguale scrivere in Assembly in maniera intelligente richiede una quantità di esperienza impressionante.  

•  È per questo che scriviamo in un linguaggio vicino a noi e facciamo fare il lavoro ad un traduttore.  

Toolchains - Overview  

Toolchain - Compilatore  

Toolchain - Compilatore  

•  Trasforma i linguaggi di alto livello in linguaggio Assembly.  

•  Spesso il risultato è migliore che farselo a mano  

Toolchain - Assembler  

Toolchain - Assembler  

u  Traduce un codice sorgente in linguaggio Assembly in file oggetto  

u  I file oggetto sono sequenze di istruzioni in linguaggio macchina, dati ed altre informazioni necessari al caricamento in memoria di un programma  

Assembler: Pseudoistruzioni  

u  Gli assembler accettano anche istruzioni che non vengono supportate dal processore ma che sono più comode da leggere: le pseudoistruzioni  

u  Queste vengono lette e convertite in sequenze di istruzioni accettate dalla CPU (e.g. move $t0, $t1 → add $t1, $t0, $zero)  

Assembler: numeri  

• L’assembler accetta numeri espressi in basi differenti: binario, ottale, decimale ed esadecimale  

Assembler: segmenti  

•  Contiene gli indirizzi per tutti i simboli:  u  Object File Header  u  Text Segment  u  Data Segment  u  Relocation Information  

u  Symbol Table (simboli → indirizzo)  u  Debugging Information  

Esempio Nome  

Procedura  

Dimensioni  

Caricamento  di  una  variable  X  di  cui  non  si  sa  l’indirizzo  

Chiamata  di  una  procedura  di  cui  no  si  sa  ancora  

l’indirizzo  

Informazioni  per  il  linker  

Intestazione file oggetto

Nome Procedura A Dimensione .text 100hex Dimensione .data 20hex

.text Indirizzo Istruzione 0 lw $a0, 0($gp)

4 jal 0 ... ...

.data 0 (X) ... ... Informazioni di Rilocazione Indirizzo Tipo di Istruzione Dipendenza

0 lw X

4 jal B

Tabella dei simboli Etichetta Indirizzo X - B -

Esempio: altra procedura

Intestazione file oggetto

Nome Procedura B Dimensione .text 200hex Dimensione .data 30hex

.text Indirizzo Istruzione 0 sw $a1, 0($gp)

4 jal 0 ... ...

.data 0 (Y) ... ... Informazioni di Rilocazione Indirizzo Tipo di Istruzione Dipendenza

0 sw Y

4 jal A

Tabella dei simboli Etichetta Indirizzo Y -

A -

Toolchain: Linker  

Toolchain: Linker  

•  Prende i file oggetto assemblati in precedenza e li collega tra di loro, in modo da chiamare le procedure corrette nei vari file oggetto.  

•  Il risultato è un file eseguibile, che è un file oggetto senza riferimenti irrisolti.  

Toolchain: Linker  

•  Sono presenti tre simboli nei file oggetto:  u  Defined symbols, simboli che possono

venir chiamati da altri file oggetto  

u  Undefined symbols, chiamate ai moduli dove i simboli sono stati soddisfatti  

u  Local symbols, simboli utilizzati all’interno di un file oggetto per aiutare la rilocazione  

Linker: simboli  

Linker: passi di linking  

Il linking è formato da tre passi:  1.  Caricare temporanemente in memoria codice e moduli  2.  Determinare gli indirizzi dei dati e delle etichette  

3.  Correggere i riferimenti interni ed esterni  

Ritorniamo all’esempio  

Ritorniamo all’esempio dei due file oggetto, uno nel quale viene definita la funzione A ed uno nel quale viene definita B.  

Intestazione file oggetto

Nome Procedura A Dimensione .text 100hex Dimensione .data 20hex

.text Indirizzo Istruzione 0 lw $a0, 0($gp)

4 jal 0 ... ...

.data 0 (X) ... ... Informazioni di Rilocazione Indirizzo Tipo di Istruzione Dipendenza

0 lw X

4 jal B

Tabella dei simboli Etichetta Indirizzo X - B -

Intestazione file oggetto

Nome Procedura B Dimensione .text 200hex Dimensione .data 30hex

.text Indirizzo Istruzione 0 sw $a1, 0($gp)

4 jal 0 ... ...

.data 0 (Y) ... ... Informazioni di Rilocazione Indirizzo Tipo di Istruzione Dipendenza

0 sw Y

4 jal A

Tabella dei simboli Etichetta Indirizzo Y -

A -

Esempio di linking - cont.  

•  Sia A che B hanno riferimenti non risolti (A, B, vari displacements).  

•  Per risolverli vengono caricati in memoria i files, usando le convenzioni del MIPS e poi vengono inseriti i riferimenti corretti.  

Allocazione memoria in MIPS  

Il segmento testo parte da 0x0040 0000  

I dati statici vengono caricati da 0x1000 0000, $gp viene usato per l’accesso applicando un displacement signed a 16 bit.  

Primo passo: Caricare in memoria  

•  Il segmento .text, in memoria, viene caricato a partire da 0x0040 0000, mentre .data a partire da 0x1000 0000.  

•  Usando le informazioni nei file headers si può sapere dove finiranno i segmenti .text e .data dei due file oggetto.  

Primo passo: Caricare in memoria  

Dimensione .text 300hex

Dimensione .data 50hex .text Indirizzo Istruzione 0040 0000hex lw $a0, 0($gp) [X]

0040 0004hex jal 0 [Procedure B]

... ...

0040 0100hex sw $a1, 0($gp) [Y]

0040 0104hex jal 0 [Procedure A]

... ...

.data Indirizzo 1000 0000hex (X)

... ...

1000 0020hex (Y)

... ...

Secondo passo: Risolvere gli indirizzi  

u  Le jump (jal) sono facili: basta recuperare l’indirizzo della prima istruzione della procedura ed usare quello  

u  I trasferimenti (lw, sw) richiedono di calcolare il displacement rispetto a $gp. Questo displacement è un signed a 16bit e si parte da 0x10008000.  

Intestazione file eseguibile

Dimensione .text 300hex

Dimensione .data 50hex .text Indirizzo Istruzione 0040 0000hex lw $a0, 0x8000($gp) 0040 0004hex jal 0x40 0100 ... ... 0040 0100hex sw $a1, 0x8020($gp) 0040 0104hex jal 0x40 0000 ... ... .data Indirizzo 1000 0000hex (X)

... ...

1000 0020hex (Y)

... ...

Loader  

Il loader è una procedura o un programma che carica un programma in memoria e lo esegue  

Loader  

Loader: Passaggi  1. Validazione (e.g. permessi, memoria disponibile)  2. Copia del programma in memoria  

3. Copia degli argomenti nello stack  

4. Inizializzazione dei registri  5. Salto all’entry point (i.e. _start)  

Libreria  

•  Una libreria è una collezione di file .o e di header file (con le signature delle procedure)

•  Per le librerie ci sono due modalità •  Statica •  Dinamica

•  Se si usa il linking statico il liniker valuta tutti i file oggetto della libreria “toccati” da una chiamata del modulo e collega I relativi moduli

•  Vantaggi: •  Codiv

Linking statico  

•  Se si usa il linking statico il liniker valuta tutti i file oggetto della libreria “toccati” da una chiamata del modulo e collega I relativi moduli

•  Vantaggi: •  Codice autocontenuto

•  Svantaggi: •  Potenziali dimensioni eseguibile

•  Usare moduli piccoli e con piccole interfaccie •  Necessità di ricompilare il tutto se si cambia

codice o libreria

Dynamic Linking  

L’idea del dynamic linking è di spostare il linking al tempo di caricamento •  Quando il programma viene caricato, a quel

punto vengono prelevate I vari moduli di libreria dal file system e viene creato l’eseguibile

•  Vantaggi •  Ridurre le dimensioni dell’eseguibile •  Condividere lo stesso codice di libreria tra più

processi. •  Volendo, si può effettuare una “lazy

relocation”: •  Inserire una chiamata a una prcedura dummy per ogni chiamta

di libreria che punta al dynamic linking  

Dynamic Linking  

•  Volendo, si può effettuare una “lazy relocation”:

•  Inserire una chiamata a una prcedura dummy per ogni chiamata di libreria che punta al dynamic linker

•  Alla prima chiamata viene risolto l’indirizzo e di lì in poi si usa